Interference aware routing in multi-radio wireless mesh networks

• US 8,532,023 B2
• Filed: 06/30/2007
• Issued: 09/10/2013
• Est. Priority Date: 09/20/2006
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Buddhikot, Milind M., Miller, Scott C., Subramanian, Anand Prabhu
• Primary Examiner(s): Kincaid, Lester
• Assistant Examiner(s): HERRERA, DIEGO D
• Application Number:
  US11/772,140
• Publication Number:
  US 20080069034A1
• Time in Patent Office: 2,264 Days
• Field of Search: 370/328
• US Class Current: 370/328
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04W 40/125 using a measured number of retransmissions as a link metric
• CPC Class Codes: H04W 40/14 based on stability
• CPC Class Codes: H04W 40/16 based on interference

Abstract

A method and system using inter-node interference data to improve the routing of data within a wireless mesh network.

Claims

1. A method adapted for use in a node of a wireless mesh network comprising a plurality of nodes, the method comprising:

determining, for each of a plurality of links supporting any of a plurality of data transmission paths, a long term link quality (LTLQ) parameter;

determining, for each of said plurality of links, an interference aware routing metric (iAWARE) parameter associated with any respective proximate links;

adapting the LTLQ parameter of each of said plurality of links according to the respective iAWARE parameter to determine thereby a link quality parameter; and

routing data according to said link quality parameter.

2. The method of claim 1, wherein said LTLQ parameter comprises an Expected Transmission Count (ETX) parameter.

3. The method of claim 1, wherein said LTLQ parameter comprises an Expected Transmission Time (ETT) parameter.

4. The method of claim 1, wherein said step of adapting comprises scaling said LTLQ parameter using said respective iAWARE parameter.

5. The method of claim 1, further comprising:

determining, for each of said plurality of data paths, a sum of the quality parameters of the links forming the data path; and

selecting the data path having a most favorable sum of quality parameters.

6. The method of claim 5, further comprising:

updating a routing table according to the selected data path.

7. The method of claim 1, further comprising:

selecting a least interfering channel for routing data to a next network node.

8. The method of claim 1, wherein said iAWARE parameter is calculated according to the following equation:

9. The method of claim 2, wherein said ETX parameter is determined using a forward delivery ratio d_f and a reverse delivery ratio d_r for each link, the forward delivery ratio d_f comprising a measured probability that a data packet successfully arrives at the recipient node, the reverse delivery ratio d_r comprising a measured probability that an ACK packet is successfully received from the recipient node.

10. The method of claim 2, wherein said ETT parameter is calculated according to the following equation:

11. The method of claim 1, wherein each node within the wireless mesh network determines the LTLQ parameter associated with its links to surrounding nodes.

12. The method of claim 11, wherein each nodes propagates to a network manager the LTLQ parameter associated with its links to surrounding nodes.

13. The method of claim 1, wherein the step of routing comprises using the said link quality parameter to route via any one of multiple available radio frequencies per link.

14. The method of claim 13, wherein an Ad-hoc On-demand Distance Vector (AODV) Multiple-Radio (AODV-MR) routing protocol is used to route data.

15. The method of claim 1, wherein link metrics for a path are captured during a route discovery process in which:

each node propagates toward a destination node a route request (RREQ) message having appended thereto a corresponding channel identifier and link metric; and

each node propagates a route reply (RREP) message toward a source node having appended thereto a corresponding channel identifier and link metric.

16. The method of claim 15, wherein link metrics within at least one of the RREQ and RREP messages are used to improve packet routing within a routing protocol.

17. The method of claim 16, wherein:

each node propagates a route error (RERR) message toward a source node upon detecting a break in an active link.

18. The method of claim 16, wherein:

each node performs a local repair of a broken active link.

19. A system, comprising:

an input/output circuit adapted to receive data streams;

a memory, for storing computer instructions for a method of processing the received data stream; and

a processor, for executing the computer instructions;

wherein while executing the computer instructions the processor operates to perform a method comprising;

determining, for each of a plurality of links supporting any of a plurality of data transmission paths, a long term link quality (LTLQ) parameter;

determining, for each of said plurality of links, an interference aware routing metric (iAWARE) parameter associated with any respective proximate links;

adapting the LTLQ parameter of each of said plurality of links according to the respective iAWARE parameter to determine thereby a link quality parameter; and

routing data according to said link quality parameter.

20. A computer program product stored on non-transitory readable medium wherein computer instructions, when processed by a computer, adapt the operation of the computer to perform a method of routing data in a wireless mesh network, the method comprising:

determining, for each of a plurality of links supporting any of a plurality of data transmission paths, a long term link quality (LTLQ) parameter;

determining, for each of said plurality of links, an interference aware routing metric (iAWARE) parameter associated with any respective proximate links;

adapting the LTLQ parameter of each of said plurality of links according to the respective iAWARE parameter to determine thereby a link quality parameter; and

routing data according to said link quality parameter.

21. Apparatus for routing data in a wireless mesh network, comprising:

means for determining, for each of a plurality of links supporting any of a plurality of data transmission paths, a long term link quality (LTLQ) parameter;

means for determining, for each of said plurality of links, an interference aware routing metric (iAWARE) parameter associated with any respective proximate links;

means for adapting the LTLQ parameter of each of said plurality of links according to the respective iAWARE parameter to determine thereby a link quality parameter; and

means for routing data according to said link quality parameter.