Wireless mesh network transit link topology optimization method and system

• US 8,885,519 B2
• Filed: 05/31/2011
• Issued: 11/11/2014
• Est. Priority Date: 05/13/2008
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Aguirre, Mariano, Macintosh, Douglas W.M.
• Primary Examiner(s): VU, HOANG-CHUONG Q
• Application Number:
  US13/118,842
• Publication Number:
  US 20110228705A1
• Time in Patent Office: 1,260 Days
• Field of Search: 370/229, 370/231, 370/254, 370/255, 370/338, 370/351
• 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 of generating a routing topology for a wireless network, the method comprising:

determining, by a computer system, a plurality of potential paths through the wireless network from an originating node to an edge node, wherein the wireless network comprises one or more internal nodes, each of the one or more internal nodes having at least one transit link, each potential path comprising at least one hop, wherein determining each potential path comprises;

(a) temporarily eliminating a transit link having a worst radio frequency parameter 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 until no transit links remain eligible for elimination;

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

determining, by the computer system, based on the calculated metric, a preferred path of the plurality of potential paths through the wireless network from the originating node to the edge node; and

configuring, by the computer system, the wireless network to route traffic from the originating node to the edge node using the preferred path, wherein said configuring the wireless network comprises blocking one or more wireless links between nodes in the wireless network.

2. The method of claim 1, wherein determining the 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 respective potential path.

5. The method of claim 4, further comprising normalizing the RSSI in the forward direction and the RSSI in the reverse direction to generate a normalized RSSI for each hop of each potential path.

6. The method of claim 5, wherein generating the normalized RSSI 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 the 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 1, wherein determining whether the internal node meets connectivity requirements comprises:

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

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

9. The method of claim 1, wherein determining the 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.

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

a wireless communication interface configured to communicate with one or more internal nodes of the wireless network, each of the one or more internal nodes having at least one transit link; and

a routing topology generator configured to;

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

(a) temporarily eliminating a transit link having a worst radio frequency parameter 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 until no transit links remain eligible for elimination;

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

determine, based on the calculated metric, a preferred path of the plurality of potential paths through the wireless network from the originating node to the edge node; and

configure the wireless network to route traffic from the originating node to the edge node using the preferred path, wherein said configuring the wireless network comprises blocking one or more wireless links between nodes in the wireless network.

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

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

13. The configuration manager of claim 12, 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 respective potential path.

14. The configuration manager of claim 13, wherein the routing topology generator operates to normalize the RSSI in the forward direction and the RSSI in the reverse direction to generate a normalized RSSI for each hop of each potential path.

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

16. The configuration manager of claim 13, wherein the routing topology manager operates to determine the 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.

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

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

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

18. The configuration manager of claim 10, wherein the routing topology generator operates to determine the 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.

19. A non-transitory, computer accessible memory medium storing program instructions for generating a routing topology for a wireless network, wherein the program instructions are executable by a processor to:

determine a plurality of potential paths through the wireless network from an originating node to an edge node, wherein the wireless network comprises one or more internal nodes, each of the one or more internal nodes having at least one transit link, each potential path comprising at least one hop, wherein determining each potential path comprises;

(a) temporarily eliminating a transit link having a worst radio frequency parameter 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 until no transit links remain eligible for elimination;

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

determine, based on the calculated metric, a preferred path of the plurality of potential paths through the wireless network from the originating node to the edge node; and

configure the wireless network to route traffic from the originating node to the edge node using the preferred path, wherein said configuring the wireless network comprises blocking one or more wireless links between nodes in the wireless network.