Selection of routing paths based upon path qualities of a wireless routes within a wireless mesh network

• US 20050129005A1
• Filed: 01/27/2005
• Published: 06/16/2005
• Est. Priority Date: 12/29/2000
• Status: Active Grant

• Current Assignee: ABB Power Grids Switzerland AG (ABB Limited)
• Original Assignee: Tropos Networks Incorporated (ABB Limited)
• Inventors: Srikrishna, Devabhaktuni, Chari, Amalavoyal
• Granted Patent: US 7,058,021 B2
• Time in Patent Office: Days
• US Class Current: 370/356
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: H04W 40/32 for defining a routing cluster membership
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

The invention includes an apparatus and method for determining an optimal route based upon path quality of routes to an access node of a wireless mesh network. The method includes receiving routing packets at the access node through at least one wireless route. Each routing packet including route information that identifies the wireless route of the routing packet. A success ratio of a number of successfully received routing packets versus a number of transmitted routing packets is determined over a period of time T1, for each wireless route. The wireless route having a greatest success ratio is first selected, as are other wireless routes that have success ratios within a predetermined amount of the greatest success ratio. Of the first selected routes, routing packets are at the access node through the first selected routes. Again, each routing packet including route information that identifies the wireless route of the routing packet. A success long ratio of a number of successfully received routing packets versus a number of transmitted routing packets is determined over a period of time T2, wherein T2 is substantially greater than T1, for each first selected route. The wireless route having a greatest success long ratio are second selected, as are other wireless routes that have success long ratios within a second predetermined amount of the greatest success long ratio. The second selected routes having a greatest throughput are third selected. An optimal wireless route based upon the third selected routes is determined.

Claims

1. A method of determining an optimal route based upon path quality of routes to an access node of a wireless mesh network, the method comprising:

receiving routing packets at the access node through at least one wireless route;

each routing packet including route information that identifies the wireless route of the routing packet, the route information identifying all other access nodes of the wireless route between a routing packet originating gateway and the access node;

first selecting at least one wireless route through a first screening measure, the first screening measure providing a criteria for allowing selection of wireless routes; and

determining an optimal wireless route based upon at least one first selected routes.

2. The method of determining an optimal route of claim 1, wherein first selecting the wireless routes comprises:

determining a success ratio of a number of successfully received routing packets versus a number of transmitted routing packets over a period of time T1, for each wireless route; and

first selecting at least one of the wireless routes having a greatest success ratio, and other wireless routes that have success ratios within a predetermined amount of the greatest success ratio.

3. The method of determining an optimal route of claim 1, wherein the routing packets are beacons.

4. The method of determining an optimal route of claim 3, wherein the beacons are initially transmitted by at least one gateway.

5. The method of determining an optimal route of claim 3, wherein the beacons are transmitted according to an 802.11 protocol.

6. The method of determining an optimal route of claim 1, wherein a predetermined number of routing packets are transmitted from at least one gateway over a unit of time.

7. The method of determining an optimal route of claim 1, wherein determining an optimal wireless route based upon at least one first selected routes comprises:

of the at least one first selected routes, receiving routing packets at the access node through at least one first selected route;

each routing packet including route information that identifies the wireless route of the routing packet;

second selecting at least one first selected wireless routes through a second screening measure, the second screening measure providing a criteria for allowing selection of wireless routes; and

determining an optimal wireless route based upon at least one second selected routes.

8. The method of determining an optimal route of claim 2, wherein determining an optimal wireless route based upon at least one first selected routes comprises:

of the at least one first selected routes, receiving routing packets at the access node through at least one first selected route;

each routing packet including route information that identifies the wireless route of the routing packet;

second selecting at least one first selected wireless routes through a second screening measure, the second screening measure providing a criteria for allowing selection of wireless routes; and

determining an optimal wireless route based upon at least one second selected routes.

9. The method of determining an optimal route of claim 8, wherein second selecting the wireless routes through a second screening measure comprises:

determining a success long ratio of a number of successfully received routing packets versus a number of transmitted routing packets over a period of time T2, wherein T2 is substantially greater than T1, for each first selected route; and

second selecting the wireless route having a greatest success long ratio, and other wireless routes that have success long ratios within a second predetermined amount of the greatest success long ratio.

10. The method of determining an optimal route of claim 7, wherein determining an optimal wireless route based upon at least one second selected routes comprises:

third selecting at least one second selected routes having a greatest throughput.

11. The method of determining an optimal route of claim 10, wherein the second selected routes having a greatest throughput are the second selected paths having a minimal number of wireless hops.

12. The method of determining an optimal route of claim 10, wherein if the at least one third selected routes include a default routing path, then the default routing path is determined to be the optimal route.

13. The method of determining an optimal route of claim 12, wherein the default routing path is a previously determined optimal route.

14. The method of determining an optimal route of claim 10, wherein if the at least one third selected routes does not include a default routing path, then selecting the default routing path if the success long ratio of the default routing path is greater than the success long ratios of the third selected routes.

15. The method of determining an optimal route of claim 10, wherein if the at least one third selected routes does not include a default routing path, then selecting at least one of the third selected routes if the success long ratio of the default routing path is less than the success long ratios of the third selected routes.

16. The method of determining an optimal route of claim 1, wherein determining an optimal wireless route based upon at least one first selected routes comprises:

third selecting the at least one first selected routes having a greatest throughput.

17. A method of determining an optimal route based upon path quality of routes to an access node of a wireless mesh network, the method comprising:

receiving routing packets at the access node through at least one wireless route;

each routing packet including route information that identifies the wireless route of the routing packet, the route information identifying all other access nodes of the wireless route between a routing packet originating gateway and the access;

first selecting at least one of the wireless routes having a greatest throughput; and

determining an optimal wireless route based upon the first selected routes.

18. The method of determining an optimal route based of claim 17, wherein determining an optimal wireless route based upon the first selected routes comprises:

determining a success ratio of a number of successfully received routing packets versus a number of transmitted routing packets over a period of time T1, for each first selected route;

second selecting at least one of the first wireless route having a greatest success ratio, and other first selected routes that have success ratios within a predetermined amount of the greatest success ratio; and

determining an optimal wireless route based upon the second selected routes.

19. The method of determining an optimal route of claim 18, wherein determining an optimal wireless route based upon at least one second selected routes comprises:

of the at least one second selected routes, receiving routing packets at the access node through at least one second selected route;

each routing packet including route information that identifies the wireless route of the routing packet;

determining a success long ratio of a number of successfully received routing packets versus a number of transmitted routing packets over a period of time T2, wherein T2 is substantially greater than T1, for each second selected route;

third selecting at least one wireless routes having a greatest success long ratio, and other wireless routes that have success long ratios within a second predetermined amount of the greatest success long ratio; and

determining an optimal wireless route based upon at least one third selected routes.

20. A wireless access node comprising:

means for receiving routing packets at the access node through at least one wireless route;

each routing packet including route information that identifies the wireless route of the routing packet the route information identifying all other access nodes of the wireless route between a routing packet originating gateway and the access;

means for first selecting at least one of the wireless routes through a first screening measure the first screening measure providing a criteria for allowing selection of wireless routes; and

means for determining an optimal wireless route based upon at least one first selected routes.

21. The wireless access node of claim 20, wherein wherein means for first selecting the wireless routes comprises:

means for determining a success ratio of a number of successfully received routing packets versus a number of transmitted routing packets over a period of time T1, for each wireless route; and

means for first selecting at least one of the wireless routes having a greatest success ratio, and other wireless routes that have success ratios within a predetermined amount of the greatest success ratio.

22. (canceled)

23. (canceled)

24. (canceled

25. (canceled)

26. (canceled)

27. (canceled)