Enforcing fairness in ad hoc mesh networks

• US 20070127419A1
• Filed: 12/01/2005
• Published: 06/07/2007
• Est. Priority Date: 12/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sapek, Adam
• Granted Patent: US 8,149,694 B2
• Time in Patent Office: Days
• US Class Current: 370/338
• CPC Class Codes: H04W 28/22 Negotiating communication rate
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 48/16 Discovering, processing access restriction or access information
• CPC Class Codes: H04W 72/121 for groups of terminals or users
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A self-adaptive algorithm to enforce fairness executes on nodes in an ad hoc wireless network. Each node is configured to measure or estimate the utilization of the RF channel in its neighborhood and then share this information with its neighboring nodes. In this way, the nodes learn about the traffic flows within their neighborhood and may determine the competing flows. Based on the information about the competing flows, each node then determines the fair share of RF channel usage. The fair share may be computed by dividing the total time that all competing flows use the RF channel by the number of competing flows. Traffic flows using more than the computed fair share of channel access are slowed down to allow more access to the RF channel for flows that are not getting their fair share.

Claims

1. A computer-implemented method for enforcing fairness in an ad hoc wireless network, comprising:

determining a channel usage for competing flows;

determining a fair share of channel usage based on the determined channel usage for the competing flows; and

adjusting a flow rate for at least one of the nodes within the network based on the determined fair share.

2. The computer-implemented method of claim 1, wherein determining the channel usage for competing flows comprises determining the channel usage for each node within a neighborhood of the network.

3. The computer-implemented method of claim 2, further comprising broadcasting the channel usage information to other nodes within the neighborhood.

4. The computer-implemented method of claim 1, wherein determining the fair share of channel usage comprises determining a number of the competing flows and dividing a time that the competing flows utilize the channel by the number of competing flows.

5. The computer-implemented method of claim 1, wherein adjusting the flow rate for at least one of the nodes within the network based on the determined fair share comprises dropping packets.

6. The computer-implemented method of claim 1, wherein determining the channel usage for competing flows comprises determining a time it takes to transmit packets for each of the competing flows.

7. The computer-implemented method of claim 6, wherein determining the time it takes to transmit packets for the competing flows comprises performing the calculation:

(S/B)*(1/1−

p) for each of the competing flows;

where S is a size of the packet;

B is a bandwidth; and

p is a probability of packet loss.

8. The computer-implemented method of claim 7, wherein adjusting the flow send rate for the at least one of the nodes within the network based on the determined fair share comprises determining when a flow exceeds the fair share.

9. A computer-readable medium having computer-executable instructions for enforcing channel usage for flows;

comprising;

determining a channel usage for a channel through a node;

determining a neighborhood channel usage for a neighborhood that is associated with the node;

determining a fair share channel usage based on the neighborhood channel usage and the channel usage for the channel through the node; and

adjusting a flow rate for at least one of the nodes within the network based on the determined fair share channel usage.

10. The computer-readable medium of claim 9, further comprising broadcasting the channel usage for the channel through the node to other nodes within the neighborhood.

11. The computer-readable medium of claim 10, wherein determining the fair share of channel usage comprises determining an average flow for competing flows.

12. The computer-readable medium of claim 10, further comprising adjusting a link metric to determine a more efficient route.

13. The computer-readable medium of claim 12, wherein dropping packets comprises determining at least one of:

when the flow of the node exceeds the fair share channel usage;

when the flow of the node is close to the fair share channel usage; and

when the flow equals the fair share channel usage.

14. The computer-readable medium of claim 13, further comprising performing at least one of:

adjusting the packet drop rate quickly when the flow exceeds the fair share channel usage;

adjusting the packet drop rate slowly when the flow is close to the fair share channel usage and resetting the packet drop rate when the flow equals the fair share channel usage.

15. An apparatus for enforcing fairness in an ad hoc wireless mesh network, comprising:

a processor;

a network interface unit configured to connect to the ad hoc wireless mesh network and that is configured to send and receive flows through a channel; and

an algorithm configured to perform steps, including;

determining a channel usage for the flows through the channel;

processing neighborhood channel usage information;

determining a fair share channel usage; and

adjusting a flow rate.

16. The apparatus of claim 15, wherein the algorithm is further configured to broadcast the channel usage for the flows through the channel.

17. The apparatus of claim 16, wherein determining the fair share channel usage comprises determining an average flow for competing flows.

18. The apparatus of claim 17, wherein adjusting the flow rate for at least one of the nodes within the network based on the determined fair share comprises performing dropping packets at a determined rate.

19. The apparatus of claim 15, wherein dropping packets comprises determining at least one of:

when the flow of the node exceeds the fair share channel usage;

when the flow of the node is close to the fair share channel usage; and

when the flow equals the fair share channel usage and adjusting the packet drop rate quickly when the flow exceeds the fair share channel usage;

adjusting the packet drop rate slowly when the flow is close to the fair share channel usage;

quickly decreasing the packet drop rate when the flow is less than the fair share; and

maintaining the packet drop rate when the flow equals the fair share channel usage.

20. The apparatus of claim 15, wherein determining the channel usage for the flows through the channel comprises determining a number of channels used and determining the channel usage for each of the number of channels.