Ranking Nodes in Networks with Topologies Arranged as Directed Acyclic Graphs

• US 20110116389A1
• Filed: 11/13/2009
• Published: 05/19/2011
• Est. Priority Date: 11/13/2009
• Status: Active Grant

• Current Assignee: Di Wang, Jinyun Zhang, Zhifeng Tao
• Original Assignee: Di Wang, Jinyun Zhang, Zhifeng Tao
• Inventors: Tao, Zhifeng, Wang, Di, Zhang, Jinyun
• Granted Patent: US 8,270,313 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04W 40/125 using a measured number of retransmissions as a link metric
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

Embodiments of the invention disclose a system and a method for determining a rank of a node in a multi-hop wireless network, wherein the network includes a gateway node, client nodes, and relay nodes, wherein a node p(i) is a default parent of the node i having a rank, and the network uses a directed acyclic graph (DAG) topology. The method comprises steps of transmitting at least one data packet from the node to the default parent node over a wireless link; counting a number of successful transmissions of most recent transmissions of data packets; determining an expected transmission time (ETX) for the wireless link based on the number of successful transmissions in the most recent transmissions; and assigning a rank R(i) to the node based on the rank of the parent node and the ETX.

Claims

1. A method for determining a rank of a node i in a multi-hop wireless network, wherein the network includes a gateway node, client nodes, and relay nodes, wherein a node p(i) is a default parent of the node i having a rank R(p(i)), and wherein a topology of the network is according to a directed acyclic graph (DAG), comprising steps of:

transmitting at least one data packet from the node i to the node p(i) over a link L(i, p(i));

counting a number s of successful transmissions of m data packets, wherein m is a number of most recent transmissions from the node i to the node p(i);

determining an expected transmission time (ETX) for the link L(i, p(i) according to ETX(i, p(i))=m/s; and

assigning a rank R(i) to the node i as R(p(i))·

ETX(i, p(i))+A, wherein A is a constant.

2. The method of claim 1, further comprising:

assigning a rank to the gateway node, wherein the rank assigned to the gateway node is a constant.

3. The method of claim 1, wherein the constant A is 1.

4. The method of claim 1, further comprising:

assigning an initial value of 1 to the ETX(i, p(i)).

5. The method of claim 1, further comprising:

repeating, in response to the transmitting, the counting and the determining to update the ETX(i, p(i)).

6. The method of claim 1, further comprising:

determining the number s via a media access control (MAC) layer feedback mechanism.

7. The method of claim 1, further comprising:

acquiring a parent list of the node i, wherein the parent list includes a node k;

acquiring a rank R(k) of the node k; and

acquiring an ETX(i, k) of a link from the node i to the node k.

8. The method of claim 7, wherein the node k advertises the rank R(k).

9. The method of claim 7, further comprising:

acquiring the rank R(p(i)) of the default parent of the node i.

10. The method of claim 7, further comprising:

selecting the default parent based on the ETX of each link between the node i and each node in the parent list, and the rank of each node in the parent list.

11. The method of claim 1, further comprising:

acquiring the rank R(p(i)) of the default parent of the node i;

determining the ETX(i, p(i)); and

updating the rank R(i) in response to changes in values of the ETX(i, p(i)) and/or the rank R(p(i)).

12. The method of claim 11, further comprising:

transmitting a message indicative of the updated rank R(i).

13. The method of claim 1, wherein the network is an advanced metering infrastructure

14. The method of claim 7, further comprising:

determining, for each node in the parent list, a temporary rank; and

transmitting a message indicative of the updated rank R(i), if a ratio between the temporary rank and the rank R(i) is greater than a threshold.

15. The method of claim 1, wherein the network is an advanced metering infrastructure (AMI) network, and the node i is a meter node.

16. A method for determining a rank of a node i in a multi-hop wireless network, wherein the network includes a gateway node, client nodes, and relay nodes, wherein a node p(i) is a default parent of the node i having a rank R(p(i)), and wherein the network uses a directed acyclic graph (DAG) topology, comprising steps of:

transmitting at least one data packet from the node i to the node p(i) over a wireless link;

counting a number of successful transmissions of most recent transmissions of data packets;

determining an expected transmission time (ETX) for the wireless link based on the number of successful transmissions in the most recent transmissions; and

assigning a rank R(i) to the node i as R(p(i))·

ETX(i, p(i))+A, wherein ETX(i, p(i)) is the ETX of the wireless link, and A is a constant.

17. The method of claim 16, further comprising:

acquiring the rank of the default parent of the node i.

18. The method of claim 16, further comprising:

assigning an initial value of 1 to the ETX(i, p(i)).

19. The method of claim 16, further comprising:

repeating, in response to the transmitting, the counting and the determining to update the ETX(i, p(i)).

20. A system for determining a rank of a node i in a multi-hop wireless network, wherein the network includes a gateway node, client nodes, and relay nodes, wherein a node p(i) is a default parent of the node i having a rank R(p(i)), and wherein a topology of the network is according to a directed acyclic graph (DAG), comprising

means for transmitting at least one data packet from the node i to the node p(i) over a link L(i, p(i));

means for counting a number s of successful transmissions of m data packets, wherein m is a number of most recent transmissions from the node i to the node p(i);

means for determining an expected transmission time (ETX) for the link L(i, p(i)) according to ETX(i, p(i))=m/s; and

means for assigning a rank R(i) to the node i as R(p(i))·

ETX(i, p(i))+A, wherein A is a constant.