Automatic route configuration in hierarchical wireless mesh networks

• US 7,899,027 B2
• Filed: 08/26/2005
• Issued: 03/01/2011
• Est. Priority Date: 03/23/2005
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Castagnoli, Neal Dante, Friday, Robert J.
• Primary Examiner(s): Appiah; Charles N.
• Assistant Examiner(s): AJIBADE AKONAI, OLUMIDE
• Application Number:
  US11/213,287
• Publication Number:
  US 20060215582A1
• Time in Patent Office: 2,013 Days
• Field of Search: 455/67.11, 455/67.13, 455/41.2, 455/502, 370/229, 370/238, 370/238.1, 370/254, 370/328, 370/329, 370/351, 370/352, 370/353, 370/354, 370/355, 370/356, 370/408, 370/255, 370/406, 370/252, 370/253, 370/256, 370/230, 370/338, 370/350, 370/503, 709/238, 709/239, 709/240, 709/241, 709/242
• US Class Current: 370/350
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Methods, apparatuses and systems directed to routing configuration in a hierarchical wireless mesh network. In one implementation, the present invention uses neighbor messages to allow routing nodes to discover one another and configure a hierarchical routing configuration. In one implementation, the present invention provides a neighbor and adjacency protocol that provides for automatic mesh configuration and loop-free mesh topologies.

Claims

1. A wireless routing node for use in a hierarchical wireless mesh network, comprising:

a wireless network interface for communicating with one or more routing nodes;

a processor;

a memory storing an adjacency data structure comprising path information for at least one neighboring routing node;

a routing node application, stored in the memory, comprising instructions operable to cause the processor and the wireless routing node to;

discover neighboring routing nodes;

exchange path information with discovered routing nodes;

determine whether any discovered routing node is not available to be a parent routing node;

select, from the available discovered routing nodes, the wireless routing node'"'"'s own parent routing node based at least in part on the path information;

set a synchronization timer;

perform synchronization with the selected parent routing node;

establish the selected parent routing node as a parent for the wireless routing node in response to synchronization being completed before the synchronization timer times out;

select a new parent routing node in response to the synchronization timer timing out prior to completion of synchronization;

wherein to discover neighboring routing nodes and exchange path metric information, the routing node application further comprises instructions operable to cause the processor and the wireless routing node to transmit neighbor request messages; and

receive neighbor response messages from neighboring routing nodes;

wherein a neighbor response message transmitted from a first routing node includes a first throughput metric indicative of the throughput of the most constrained link in a path from the first routing node to the root routing node; and

wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to compute a second throughput metric indicative of the throughput of the link between the wireless routing node and the first routing node; and

store the lesser of the first and second throughput metric in the entry of the adjacency data structure corresponding to the first routing node.

2. The wireless routing node of claim 1 wherein the neighbor request message identifies a parent routing node.

3. The wireless routing node of claim 1 wherein the neighbor request message identifies at least one descendant routing node in the hierarchical wireless mesh network.

4. The wireless routing node of claim 1 wherein the wireless network interface comprises a plurality of antennas, and wherein the neighbor request message identifies the antenna used to transmit the neighbor request message.

5. The wireless routing node of claim 1 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

detect, during reception of a neighbor request message from a first routing node, an attribute of the radio-frequency (RF) signal carrying the neighbor request message;

include the detected attribute in a neighbor response message transmitted to the first routing node.

6. The wireless routing node of claim 5 wherein the attribute is the signal-to-noise ratio (SNR) of the RF signal.

7. The wireless routing node of claim 1 wherein the neighbor response message includes mesh routing information comprising the number of routes to one or more root routing nodes and, for each route, the number of hops to the respective root routing node, and a distance vector of MAC addresses representing the hops in the route.

8. The wireless routing node of claim 1 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

receive a neighbor response message from a first routing node, wherein the neighbor response message includes the signal attribute detected by the first routing node during receipt of a neighbor request message;

detect, during reception of the neighbor response message from a routing node, an attribute of the radio-frequency (RF) signal carrying the neighbor response message.

9. The wireless routing node of claim 8 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

compute a signal attribute for the link between the wireless routing node and the first routing node based on evaluation of the detected signal attribute and the signal attribute in the neighbor response message.

10. The wireless routing node of claim 1 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

receive a neighbor request message from a first routing node requesting adoption as a child routing node;

transmit a neighbor response message to the first routing node indicating acceptance of the request.

11. The wireless routing node of claim 1 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

store the exchanged path information in the adjacency data structure in entries corresponding to each discovered routing node;

and

periodically select a parent routing node based at least in part on the path metric information stored in the adjacency data structure.

12. The wireless routing node of claim 1 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

apply at least one criterion to received neighbor messages;

and

conditionally discard received neighbor messages based on the at least one criterion.

13. The wireless routing node of claim 1 wherein the first and second throughput metrics are based on detected signal-to-noise ratios.

14. The wireless routing node of claim 1 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

select, as the parent routing node, the routing node in the adjacency data structure associated with the best throughput metric.

15. The wireless routing node of claim 1 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

compute an adjusted throughput metric for a selected set of routing nodes based on the stored throughput metric and the number of hops in the path from each corresponding routing node to the root routing node.

16. The wireless routing node of claim 15 wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to

select, as the parent routing node, the routing node in the adjacency data structure associated with the best adjusted throughput metric.

17. In a wireless routing node operable in a hierarchal mesh network, the hierarchical mesh network comprising a root routing node, a method comprising:

discovering neighboring routing nodes;

exchanging path information with the discovered neighboring routing nodes, wherein the path information comprises signal attribute information corresponding to the respective links between the wireless routing node and the discovered neighboring routing nodes, and routing information characterizing the path from a given routing node to the root routing node;

determining whether any discovered routing node is not available to be a parent routing node; and

selecting, based on the path information, the wireless routing node'"'"'s own parent routing node from the available discovered routing nodes;

setting a synchronization timer;

performing synchronization with the selected parent routing node;

establishing the selected parent routing node as a parent for the wireless routing node in response to synchronization being completed before the synchronization timer times out;

selecting a new parent routing node in response to the synchronization timer timing out prior to completion of synchronization;

transmitting neighbor request messages; and

receiving neighbor response messages from neighboring routing nodes;

wherein a neighbor response message transmitted from a first routing node includes a first throughput metric indicative of the throughput of the most constrained link in a path from the first routing node to the root routing node; and

wherein the method further comprises computing a second throughput metric indicative of the throughput of the link between the wireless routing node and the first routing node; and

storing the lesser of the first and second throughput metric in the entry of the adjacency data structure corresponding to the first routing node.

18. The method of claim 17 further comprising

storing the exchanged path information in an adjacency data structure comprising entries corresponding to each of the discovered routing nodes.

19. The method of claim 17 wherein the neighbor request message identifies a parent routing node.

20. The method of claim 17 wherein the neighbor request message identifies at least one descendant routing node in the hierarchical wireless mesh network.

21. The method of claim 17 wherein the wireless routing node comprises a plurality of antennas, and wherein the neighbor request message identifies the antenna used to transmit the neighbor request message.

22. The method of claim 17 further comprising

detecting, during reception of a neighbor request message from a first routing node, an attribute of the radio-frequency (RF) signal carrying the neighbor request message;

including the detected attribute in a neighbor response message transmitted to the first routing node.

23. The method of claim 22 wherein the attribute is the signal-to-noise ratio (SNR) of the RF signal.

24. The method of claim 17 wherein the neighbor response message includes mesh routing information comprising the number of routes to one or more root routing nodes and, for each route, the number of hops to the respective root routing node, and a distance vector of MAC addresses representing the hops in the route.

25. The method of claim 17 further comprising

receiving a neighbor response message from a first routing node, wherein the neighbor response message includes the signal attribute detected by the first routing node during receipt of a neighbor request message;

detecting, during reception of the neighbor response message from a routing node, an attribute of the radio-frequency (RF) signal carrying the neighbor response message.

26. The method of claim 25 further comprising

computing a signal attribute for the link between the wireless routing node and the first routing node based on evaluation of the detected signal attribute and the signal attribute in the neighbor response message.

27. The method of claim 17 further comprising

receiving a neighbor request message from a first routing node requesting adoption as a child routing node;

transmitting a neighbor response message to the first routing node indicating acceptance of the request.

28. The method of claim 17 further comprising

storing the exchanged path information in the adjacency data structure in entries corresponding to each discovered routing node;

and

periodically selecting a parent routing node based at least in part on the path metric information stored in the adjacency data structure.

29. The method of claim 17 further comprising

applying at least one criterion to received neighbor messages;

and

conditionally discarding received neighbor messages based on the at least one criterion.

30. The method of claim 17 wherein the first and second throughput metrics are based on detected signal-to-noise ratios.

31. The method of claim 17 further comprising

selecting, as the parent routing node, the routing node in the adjacency data structure associated with the best throughput metric.

32. The method of claim 17 further comprising

computing an adjusted throughput metric for a selected set of routing nodes based on the stored throughput metric and the number of hops in the path from each corresponding routing node to the root routing node.

33. The method of claim 32 further comprising

selecting, as the parent routing node, the routing node in the adjacency data structure associated with the best adjusted throughput metric.

34. A wireless routing node for use in a hierarchical wireless mesh network, comprising:

means for wirelessly communicating with one or more routing nodes;

means for discovering neighboring routing nodes;

means for exchanging path information with the discovered neighboring routing nodes, wherein the path information comprises signal attribute information corresponding to the respective links between the wireless routing node and the discovered neighboring routing nodes, and routing information characterizing the path from a given routing node to the root routing node;

means for determining whether any discovered routing node is not available to be a parent routing node; and

means for selecting, based on the path information, the wireless routing node'"'"'s own parent routing node from the available discovered routing nodes;

means for setting a synchronization timer;

means for performing synchronization with the selected parent routing node;

means for establishing the selected parent routing node as a parent for the wireless routing node in response to synchronization being completed before the synchronization timer times out;

means for selecting a new parent routing node in response to the synchronization timer timing out prior to completion of synchronization;

wherein to discover neighboring routing nodes and exchange path metric information, the routing node application further comprises instructions operable to cause the processor and the wireless routing node to transmit neighbor request messages; and

receive neighbor response messages from neighboring routing nodes;

wherein a neighbor response message transmitted from a first routing node includes a first throughput metric indicative of the throughput of the most constrained link in a path from the first routing node to the root routing node; and

wherein the routing node application further comprises instructions operable to cause the processor and the wireless routing node to compute a second throughput metric indicative of the throughput of the link between the wireless routing node and the first routing node; and

store the lesser of the first and second throughput metric in the entry of the adjacency data structure corresponding to the first routing node.