Wireless mesh network transit link topology optimization method and system

• US 7,978,632 B2
• Filed: 05/13/2008
• Issued: 07/12/2011
• Est. Priority Date: 05/13/2008
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: AGUIRRE, Mariano, MACINTOSH, Douglas W. M.
• Primary Examiner(s): Sheikh, Ayaz R
• Assistant Examiner(s): Wong, Blanche
• Application Number:
  US12/119,666
• Publication Number:
  US 20090285124A1
• Time in Patent Office: 1,155 Days
• Field of Search: None
• US Class Current: 370/255
• 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 for generating a routing topology for a wireless mesh network, the wireless mesh network having a plurality of internal nodes, at least one edge node, and at least one originating device, each internal node including at least one transit link having a forward direction and a reverse direction, the method comprising:

determining a plurality of potential routing solutions containing 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 quantity of hops, each potential routing solution based on at least one measured wireless communication parameter between internal nodes, determining the plurality of potential routing solutions through the wireless mesh network including;

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

performing a link elimination process using the ordered list to produce a routing solution; and

responsive to determining that the routing solution is unique, storing the routing solution in an array;

evaluating metric calculations for each potential routing solution to determine a preferred routing solution; and

configuring the wireless mesh network to route traffic using the preferred routing solution; and

the link elimination process including;

a) receiving a received signal strength indication (“

RSSI”

) value for both the forward direction and the reverse direction for each transit link of each internal node in the plurality of internal nodes;

b) normalizing the RSSI values for each transit link to produce normalized RSSI values;

c) temporarily eliminating the transit link having the lowest normalized RSSI value on the internal node;

d) verifying that the internal node meets connectivity requirements;

e) responsive to verifying that the internal node meets connectivity requirements, permanently eliminating the transit link; and

f) repeating steps c) through e) for each internal node according an order arranged by the ordered list until no transit links remain eligible for elimination.

2. The method of claim 1, wherein the preferred routing solution establishes a predetermined quantity of transit links for each internal node.

3. The method of claim 1, wherein each internal node is a wireless access point.

4. The method of claim 1, wherein normalizing the RSSI values for each transit link includes multiplying the RSSI value for the forward direction by the RSSI value for the reverse direction.

5. The method of claim 1, wherein the connectivity requirements include:

each internal node includes only two transit links; and

data communicated from at least one client computer reaches the at least one edge node in three hops or less.

6. The method of claim 1, wherein the metric calculations include at least one of hop count metrics, node distribution metrics, and performance score metrics.

7. The method of claim 6, wherein the hop count metrics include a quantity of internal nodes that are a given quantity of hops away from an edge node for each quantity of hops less than or equal to the predetermined quantity of hops.

8. The method of claim 7, wherein each amount of internal nodes that are a given quantity of hops away from an edge node for each quantity of hops less than or equal to the predetermined quantity of hops are weighted according to different weight values, wherein each corresponding weight value is greater for a lower quantity of hops.

9. The method of claim 6, wherein the node distribution metrics include at least one of an average number of internal nodes per edge node, a greatest number of internal nodes assigned to any individual edge node, and a least number of internal nodes assigned to any individual edge node.

10. The method of claim 6, wherein the performance score metrics are determined by:

determining a path probability for each path in each potential routing solution;

adding the path probabilities determined for each potential routing solution together to produce a total path probability for each potential routing solution; and

dividing the total path probability for each potential routing solution by the amount of internal nodes in the potential routing solution.

11. The method of claim 1, wherein the wireless mesh network includes a plurality of edge nodes, the paths of the preferred routing solution are evenly distributed among the plurality of edge nodes.

12. A configuration manager for configuring a wireless mesh network, the wireless mesh network having a plurality of internal nodes and at least one edge node, each internal node including at least one transit link having a forward direction and a reverse direction, the configuration manager comprising:

a wireless communication interface, the wireless communication interface facilitating wireless communication between the configuration manager and the plurality of internal nodes and for communication between the configuration manager and the at least one edge node; and

a routing topology generator communicatively coupled to the wireless communication interface, the routing topology generator;

determining a plurality of potential routing solutions containing 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 quantity of hops, each potential routing solution based on at least one measured wireless communication parameter between internal nodes, determining the plurality of potential routing solutions through the wireless mesh network including;

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

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

responsive to determining that the potential routing solution is unique, storing the potential routing solution in an array;

evaluating metric calculations for each potential routing solution to determine a preferred routing solution; and

configuring the wireless mesh network to route traffic using the preferred routing solution; and

the link elimination process including;

a) receiving a received signal strength indication (“

RSSI”

) value for both the forward direction and the reverse direction for each transit link of each internal node in the plurality of internal nodes;

b) normalizing the RSSI values for each transit link to produce normalized RSSI values;

c) temporarily eliminating the transit link having the lowest normalized RSSI value on the internal node;

d) verifying that the internal node meets connectivity requirements;

e) responsive to verifying that the internal node meets connectivity requirements, permanently eliminating the transit link; and

f) repeating steps c) through e) for each internal node according an order arranged by the ordered list until no transit links remain eligible for elimination.

13. A method of generating a routing topology in a wireless network having a plurality of internal nodes, at least one edge node, and at least one originating node, the method comprising:

generating a normalized received signal strength indicator (RSSI) associated with each of a plurality of transit links of an internal node; and

for each internal node, iteratively eliminating a transit link with a lowest normalized RSSI until a minimum topology is reached such that all edge nodes are reachable from any internal node within a predetermined number of hops.

14. The method of claim 13, wherein the normalized RSSI is obtained from a product of an uplink RSSI and a downlink RSSI.

15. The method of claim 13, wherein the predetermined number of hops is three or less.

16. The method of claim 13, wherein the transit links are iteratively eliminated for each internal node in an order of internal nodes determined by a random ordered list of internal nodes.

17. The method of claim 16, wherein a minimum topology is determined for each of a plurality of different lists of internal nodes ordered randomly.

18. The method of claim 17, wherein a performance metric is determined for each minimum topology and the minimum topology having a best performance metric is selected.

19. The method of claim 17, wherein a performance metric includes at least one of a number of internal nodes that are not more than one hop away from an edge node, an average number of internal nodes per edge node, a greatest number of internal nodes assigned to an edge node, a least number of internal modes assigned to an edge node.