Determining bidirectional path quality within a wireless mesh network

• US 20050068970A1
• Filed: 10/19/2004
• Published: 03/31/2005
• Est. Priority Date: 12/29/2000
• Status: Active Grant

• Current Assignee: Hitachi Energy Switzerland AG (Hitachi, Ltd.)
• Original Assignee: Tropos Networks Incorporated (ABB Limited)
• Inventors: Srikrishna, Devabhaktuni, Chari, Amalavoyal Narasimha, Arutyunov, Roman, Hong, B. William
• Granted Patent: US 7,551,562 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• 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/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• 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/30 for proactive 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 communicating link quality information between access nodes. A first step includes a first access node transmitting first routing packets. A second step includes a second access node receiving at least one of the first routing packets over a first direction of a first link. A third step includes the second access node transmitting second routing packets. A fourth step includes the first access node receiving at least one of the second routing packets over a second direction of the first link, and determining a first direction link quality of the first link based upon the second routing packets.

Claims

1. A method of communicating link quality information between access nodes, comprising:

a first access node transmitting first routing packets;

a second access node receiving at least one of the first routing packets over a first direction of a first link;

the second access node transmitting second routing packets;

the first access node receiving at least one of the second routing packets over a second direction of the first link, and determining a first direction link quality of the first link based upon the second routing packets.

2. The method of communicating link quality information of claim 1, wherein the first access node is downstream from the second access node, and the first access node makes a routing decision to a gateway based at least partially upon first direction link quality information within the second routing packets.

3. The method of communicating link quality information of claim 1, further comprising the first access node determining a second direction link quality of the first link based upon the second routing packets.

4. The method of communicating link quality information of claim 3, wherein the first access node is downstream from the second access node, and the first access node makes a routing decision to a gateway based at least partially upon the first direction link quality of the first link and the second direction link quality of the first link.

5. The method of communicating link quality information of claim 1, wherein the first direction link quality is determined by the second access node determining a percentage routing packets per unit of time received by the second access node.

6. The method of communicating link quality information of claim 1, wherein the second access node advertises the first direction link quality within the second routing packets.

7. The method of communicating link quality information of claim 3, wherein the second direction link quality is determined by determining a percentage of second routing packets per unit of time received by the first access node.

8. The method of communicating link quality information of claim 1, further comprising:

a third access node receiving at least one of the first routing packets over a first direction of a second link from the first access node;

the third access node transmitting third routing packets;

the first access node receiving at least one of the third routing packets over a second direction of the second link, and determining a first direction link quality of the second link based upon the third routing packets.

9. The method of communicating link quality information of claim 8, further comprising the first access node selecting a route through at least one of the second node and the third node at least partially based upon the first direction link quality of the first direction of the first link and the first direction link quality of the first direction of the second link.

10. The method of communicating link quality information of claim 1, wherein the routing packets are beacons that include routing information.

11. The method of communicating link quality information of claim 1, wherein the second access node is a gateway of a wireless mesh network.

12. The method of communicating link quality information of claim 8, wherein at least one of the second access node and the third access node is a gateway of a wireless mesh network.

13. The method of communicating link quality information of claim 10, wherein the beacons are transmitted according to an 802.11 protocol.

14. The method of communicating link quality information of claim 1, wherein routing packets transmitted by the first access node and the second access node include information of neighboring access nodes, the information including forward and reverse link qualities.

15. A wireless mesh network comprising:

at least one gateway, the at least one gateway transmitting beacons;

at least one access node receiving the beacons from the gateway, the at least one access node selecting a routing path to the gateway based at least partially upon an upstream link quality of a link between the at least one gateway and the at least one access node.

16. The wireless mesh network of claim 15, further comprising the at least one access node selecting the routing path to the gateway based at least partially upon a downstream link quality of a link between the at least one gateway and the at least one access node.

17. The wireless mesh network of claim 15, further comprising multi-hop access nodes that are more than one hop away from the at least one gateway, the multi-hop access nodes receiving beacons from upstream access nodes.

18. The wireless mesh network of claim 17, wherein access node upstream link quality is determined by beacons transmitted by the at least one access node or at least one multi-hop access node.

19. The wireless mesh network of claim 17, wherein access node downstream link quality is determined by beacons transmitted by at least one of a gateway or an upstream access node.

20. The wireless mesh network of claim 15, wherein the gateways generate a set number of beacons per unit of time.

21. The wireless mesh network of claim 19, wherein downstream access nodes determine the downstream link quality by determining what percentage of the beacons transmitted by a gateway or an upstream access node are successfully received by the access node.

22. The wireless mesh network of claim 17, wherein gateways and upstream access nodes determine the upstream link quality by determining what percentage of the beacons transmitted by a downstream access node are successfully received by the gateway or upstream access node.

23. The wireless mesh network of claim 22, wherein beacons transmitted by gateways and upstream access nodes include information of the upstream link quality between the gateways and upstream access nodes, and the downstream access node.

24. The wireless mesh network of claim 22, wherein downstream access nodes that receive the beacons transmitted by the gateways and upstream access nodes select routing paths to the gateways based at least partially upon information within the received beacons.

25. The wireless mesh network of claim 24, wherein the information within the received beacons includes upstream link qualities within routing paths to at least one gateway.

26. The wireless mesh network of claim 17, wherein downstream access nodes that receive the beacons transmitted by the gateways and upstream access nodes select routing paths to the gateways based at least partially upon a quality parameter of the received beacons.

27. The wireless mesh network of claim 17, wherein routing path selections are based at least partially upon uplink path qualities within available routing paths from each multi-hop access node to at least one gateway.

28. The wireless mesh network of claim 17, wherein routing path selections are based at least partially upon downlink path qualities of available routing paths from each multi-hop access node to at least one gateway.

29. The wireless mesh network of claim 27, wherein the uplink path quality of each routing path is determined by a worst uplink quality within the uplink path.

30. The wireless mesh network of claim 27, wherein the uplink path quality of each routing path is determined by a product of uplink qualities within the uplink path.

31. The wireless mesh network of claim 28, wherein the downlink path quality of each path is determined by a worst downlink quality within the downlink path.

32. The wireless mesh network of claim 28, wherein the downlink path quality of each path is determined by a product of downlink qualities within the uplink path.

33. The wireless mesh network of claim 17, wherein the routing selections include a weighting between uplink path qualities and downlink path qualities.

34. The wireless mesh network of claim 33, wherein the weighting is dependent upon the characteristics of data traffic between the access node and the gateway.

35. The wireless mesh network of claim 17, wherein at least one access node repopulates beacons lost in reception, ensuring that at least one access node transmits the same set number of beacons per unit of time.

37. The wireless mesh network of claim 16, wherein the repopulated beacons include origination of new beacons that identify a source of the beacons.

38. The wireless mesh network of claim 15, wherein the upstream link quality is determined by at least one of an SNR of the beacons received by the gateway or upstream access node, or a PER of beacons received by the gateway or upstream access node.

39. The wireless mesh network of claim 16, wherein the downstream link quality is determined by at least one an SNR of the beacons received by the access node, or a PER of beacons received by the access node.

36. The wireless mesh network of claim 36, wherein the repopulated beacons include retransmission of modified received beacons.

40. A method of routing a data path within a mesh network, comprising:

at least one gateway transmitting beacons;

at least one access node receiving the beacons from the gateway;

the at least one access node selecting a routing path to the gateway based at least partially upon an upstream link quality of a link between the at least one gateway and the at least one access node.

41. The method of claim 40, further comprising the at least one access node selecting the routing path to the gateway based at least partially upon a downstream link quality of a link between the at least one gateway and the at least one access node.

42. The method of claim 40, further comprising multi-hop access nodes receiving beacons from upstream access nodes.

43. The method of claim 42, wherein upstream link quality is determined by beacons transmitted by at least one downstream access node.

44. The method of claim 42, wherein downstream link quality is determined by beacons transmitted by at least one of a gateway or an upstream access node.

45. The method of claim 42, wherein the gateways generate a set number of beacons per unit of time.

46. The method of claim 45, wherein downstream access nodes determine a downlink quality by determining what percentage of the beacons transmitted by a gateway or an upstream access node are successfully received by the downstream access node.

47. The method of claim 42, wherein the gateways and upstream access nodes determine an uplink quality by determining what percentage of the beacons transmitted by a downstream access node are successfully received by the gateway or upstream access node.

48. The method of claim 43, wherein beacons transmitted by gateways and upstream access nodes include information of the uplink quality.

49. The method of claim 44, wherein downstream access nodes that receive the beacons transmitted by the gateways and upstream access nodes select routing paths to the gateways bases upon information within the received beacons.

50. The method of claim 49, the routing path selections are based upon uplink path qualities and downlink path qualities of available routing paths from the downstream access node to at least one gateway.

51. A wireless access node comprising:

means for receiving routing packets from at least one of an upstream access node or an upstream gateway;

means for determining upstream link qualities of a data path to at least one gateway from the routing packets;

means for means for determining downstream link qualities of a data path to at least one gateway from the routing packets;

means for selecting an optimal data path to a gateway based upon the upstream link qualities and downstream link qualities of all available data paths