System and method for link quality routing using a weighted cumulative expected transmission time metric

• US 20050286426A1
• Filed: 03/15/2005
• Published: 12/29/2005
• Est. Priority Date: 06/23/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Padhye, Jitendra D., Zill, Brian D., Draves, Richard P. Jr.
• Granted Patent: US 7,616,575 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• 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/124 using a combination of metrics
• CPC Class Codes: H04W 16/14 Spectrum sharing arrangements between different networks
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A system and method for link quality routing uses a weighted cumulative expected transmission time path metric. A system for routing in a multi-hop ad hoc network, and a method for measuring the link quality of a route in the network, include assignment of a weight to a link in accordance with an expected transmission time of a packet over the link, and a combining of individual link weights for a route into a path metric. The path metric accounts for interference among links that use a shared channel. In the calculation of the path metric, the expected transmission times of links that interfere with one another are added, while the expected transmission times for non-interfering links are considered separately.

Claims

1. A system for routing in an ad hoc network, the system comprising:

a mechanism for assigning a weight to a link; and

a mechanism for combining individual link weights for a route into a path metric, wherein the path metric accounts for interference among links that use a shared channel.

2. The system of claim 1, wherein the ad hoc network includes one or more nodes having multiple radio transceivers.

3. The system of claim 1, wherein the ad hoc network includes one or more nodes having multiple heterogeneous radio transceivers.

4. The system of claim 1, wherein assigning a weight to the link further comprises determining the weight from a measurement of an expected number of times a packet is transmitted on the link to get the packet successfully across the link, multiplied by a bandwidth measurement for the link.

5. The system of claim 4, wherein the measurement of the expected number of times a packet is transmitted on the link to get the packet successfully across the link comprises an ETX measurement.

6. The system of claim 4, wherein the bandwidth measurement is determined empirically.

7. The system of claim 4, wherein the bandwidth measurement is determined using a packet pairs technique.

8. The system of claim 1, wherein the path metric comprises a weighted average,

$(1-\beta$

) * ∑

i = 1 n ⁢

W i + β

* max 1 ≤

j ≤

k ⁢

X j

wherein n is the number of links in the route,

W_i is the weight for link i,

X_j is the sum of weights on channel j,

k is the number of channels,

and β

is a parameter subject to 0≦

β

≦

1.

9. The system of claim 8, wherein the sum of weights on channel j (i.e., X_j) is calculated by,

$X_j=\sum _{}$

Hop ⁢

 

⁢

i ⁢

 

⁢

is ⁢

 

⁢

on ⁢

 

⁢

channel ⁢

 

⁢

j ⁢

W i ⁢

 

⁢

1 ≤

j ≤

k

such that a total path throughput is dominated by a bottleneck channel, wherein the bottleneck channel is the channel which has the largest X_j value.

10. The system of claim 8, wherein the weight for link i comprises a measurement of an expected number of times a packet is transmitted on link i to get the packet successfully across link i, multiplied by a bandwidth measurement for link i.

11. In a multi-hop network, a method for measuring link quality of a route from a source node to a destination node, the route comprising a plurality of links, the method comprising:

for each link in the route, assigning a weight in accordance with a performance of the link; and

combining the assigned link weights for the route into a path metric, wherein the path metric accounts for interference among links that use a shared channel.

12. The method of claim 11, wherein the multi-hop network includes one or more nodes having multiple radio transceivers.

13. The method of claim 11, wherein the multi-hop network includes one or more nodes having multiple heterogeneous radio transceivers.

14. The method of claim 11, wherein the performance of the link comprises a measurement of an expected number of times a packet is transmitted on the link to get the packet successfully across the link, multiplied by a bandwidth measurement for the link.

15. The method of claim 14, wherein the bandwidth measurement is determined empirically.

16. The method of claim 14, wherein the bandwidth measurement is determined using a packet pairs technique.

17. The method of claim 14, wherein combining the assigned link weights for the route into the path metric comprises:

calculating a sum of the expected transmission times for the links in the route;

for each channel used by one or more of the links, determining a subset of the links that share the channel;

calculating a sum of the expected transmission times for the links in each subset;

determining a subset having a maximum sum; and

calculating the path metric as (1−

β

) multiplied by the sum of the expected transmission times for the links in the route plus β

multiplied by the sum of the expected transmission times for the subset having the maximum sum, wherein β

is a parameter subject to 0≦

β

≦

1.

18. A computer-readable medium having stored thereon computer-executable instructions for measuring link quality of a route from a source node to a destination node, the route comprising a plurality of links, the computer-executable instructions comprising:

for each link in the route, assigning a weight in accordance with an expected transmission time of a packet over the link; and

combining the assigned link weights for the route into a path metric, wherein the path metric accounts for interference among links that use a shared channel.

19. The computer-readable medium of claim 18, wherein the expected transmission times comprises a measurement of an expected number of times a packet is transmitted on the link to get the packet successfully across the link, multiplied by a bandwidth measurement for the link.

20. The computer-readable medium of claim 18, wherein combining the assigned link weights for the route into the path metric comprises:

calculating a sum of the expected transmission times for the links in the route;

for each channel used by one or more of the links, determining a subset of the links that share the channel;

calculating a sum of the expected transmission times for the links in each subset;

determining a subset having a maximum sum; and

calculating the path metric as (1−

β

) multiplied by the sum of the expected transmission times for the links in the route plus β

multiplied by the sum of the expected transmission times for the subset having the maximum sum, wherein β

is a parameter subject to 0≦

β

≦

1.