WIRELESS MESH NETWORK TRANSIT LINK TOPOLOGY OPTIMIZATION METHOD AND SYSTEM

• US 20110228705A1
• Filed: 05/31/2011
• Published: 09/22/2011
• Est. Priority Date: 05/13/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: MACINTOSH, Douglas W.M., AGUIRRE, Mariano
• Granted Patent: US 8,885,519 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04W 40/16 based on interference
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 84/22 with access to wired networks

Abstract

A method and configuration manager generates a routing topology for a wireless mesh network. The wireless mesh network has a plurality of internal nodes, at least one edge node, and at least one originating device. A plurality of potential routing solutions is determined which contain a plurality of paths through the wireless mesh network from the at least one originating device to the at least one edge node such that data communicated from the at least one originating device reaches the at least one edge node in no more than a predetermined number of hops. Each potential routing solution is based on at least one measured wireless communication parameter between internal nodes. Metric calculations for each potential routing solution are computed to determine a preferred routing solution. The wireless mesh network is configured to route traffic using the preferred routing solution.

Claims

1. A method of generating a routing topology for a wireless network, the method comprising:

determining a plurality of potential paths through the wireless network from an originating node to an edge node, each path comprising at least one hop;

calculating a metric for each potential path, the metric based on at least one radio frequency parameter measured for each hop in the potential path;

determining a preferred path based on the calculated metric; and

configuring the wireless network to route traffic from the originating node to the edge node.

2. The method of claim 1, wherein determining a plurality of potential paths comprises eliminating potential paths having a hop count greater than a predetermined maximum hop count.

3. The method of claim 1, wherein the metric for each potential path is based on at least one received signal strength indication (RSSI).

4. The method of claim 3, wherein the metric for each potential path is based on a RSSI in a forward direction and a RSSI in a reverse direction for each hop in the potential path.

5. The method of claim 4, further comprising normalizing the RSSI values for each hop of each potential path.

6. The method of claim 5, wherein normalizing the RSSI values for each hop comprises multiplying the RSSI in the forward direction by the RSSI in the reverse direction for each hop.

7. The method of claim 4, wherein determining a plurality of potential paths through the wireless network comprises:

creating an ordered list using a random arrangement of internal nodes;

performing a link elimination process using the ordered list to produce a potential path; and

responsive to determining that the potential path is unique, storing the potential path in an array.

8. The method of claim 7, wherein each internal node has at least one transit link having a forward direction and a reverse direction;

and

the link elimination process comprises;

(a) temporarily eliminating a transit link having a lowest normalized RSSI value for an internal node;

(b) determining whether the internal node meets connectivity requirements;

(c) responsive to determining that the internal node meets connectivity requirements, permanently eliminating the transit link; and

repeating steps (a), (b) and (c) for each internal node according to an order of the ordered list until no transit links remain eligible for elimination.

9. The method of claim 8, wherein determining whether the internal node meets connectivity requirements comprises:

determining that the internal node includes only two transit links; and

determining that the path from the originating node to the edge node is at most three hops long.

10. The method of claim 1, wherein determining a plurality of potential paths through the wireless network comprises:

creating an ordered list using a random arrangement of internal nodes;

performing a link elimination process using the ordered list to produce a potential path; and

responsive to determining that the potential path is unique, storing the potential path in an array.

11. A configuration manager for a wireless network, the configuration manager comprising:

a wireless communication interface operable to communicate with nodes of the wireless network; and

a routing topology generator operating to;

determine a plurality of potential paths through the wireless network from an originating node to an edge node, each path comprising at least one hop;

calculate a metric for each potential path, the metric based on at least one radio frequency parameter measured for each hop in the potential path;

determine a preferred path based on the calculated metric; and

configure the wireless network to route traffic from the originating node to the edge node.

12. The configuration manager of claim 11, wherein the routing topology generator operates to determine a plurality of potential paths by eliminating potential paths having a hop count greater than a predetermined maximum hop count.

13. The configuration manager of claim 11, wherein the metric for each potential path is based on at least one received signal strength indication (RSSI).

14. The configuration manager of claim 13, wherein the metric for each potential path is based on a RSSI in a forward direction and a RSSI in a reverse direction for each hop in the potential path.

15. The configuration manager of claim 14, wherein the routing topology generator operates to normalize the RSSI values for each hop of each potential path.

16. The configuration manager of claim 15, wherein routing topology generator operates to normalize the RSSI values for each hop by multiplying the RSSI in the forward direction by the RSSI in the reverse direction for each hop.

17. The configuration manager of claim 14, wherein the routing topology manager operates to determine a plurality of potential paths through the wireless network by:

creating an ordered list using a random arrangement of internal nodes;

performing a link elimination process using the ordered list to produce a potential path; and

responsive to determining that the potential path is unique, storing the potential path in an array.

18. The configuration manager of claim 17, wherein each internal node has at least one transit link having a forward direction and a reverse direction;

and

the link elimination process comprises;

(a) temporarily eliminating a transit link having a lowest normalized RSSI value for an internal node;

(b) determining whether the internal node meets connectivity requirements;

(c) responsive to determining that the internal node meets connectivity requirements, permanently eliminating the transit link; and

repeating steps (a), (b) and (c) for each internal node according to an order of the ordered list until no transit links remain eligible for elimination.

19. The configuration manager of claim 18, wherein determining whether the internal node meets connectivity requirements comprises:

determining that the internal node includes only two transit links; and

determining that the path from the originating node to the edge node is at most three hops long.

20. The configuration manager of claim 11, wherein the routing topology generator operates to determine a plurality of potential paths through the wireless network by:

creating an ordered list using a random arrangement of internal nodes;

performing a link elimination process using the ordered list to produce a potential path; and

responsive to determining that the potential path is unique, storing the potential path in an array.