Enforcing fairness in ad hoc mesh networks

• US 8,149,694 B2
• Filed: 12/01/2005
• Issued: 04/03/2012
• Est. Priority Date: 12/01/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Sapek, Adam
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): Ng, Fan
• Application Number:
  US11/292,156
• Publication Number:
  US 20070127419A1
• Time in Patent Office: 2,315 Days
• Field of Search: None
• US Class Current: 370/230
• 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:

monitoring entire flows between mesh nodes within the ad hoc wireless network;

on each of the mesh nodes within the ad hoc wireless network, using a processor in determining a channel usage for flows between mesh nodes within the ad hoc wireless network;

wherein the mesh nodes within the ad hoc wireless network transmit and receive data packets from other mesh nodes within the network;

wherein each of the flows is a stream of packets between two endpoints on the ad hoc wireless network;

wherein at least one of the flows within the ad hoc wireless network includes one or more intervening mesh nodes between the two endpoints;

wherein each of the mesh nodes shares the channel usage with each of its neighbors that are within a range by transmitting the channel usage;

wherein the one or more intervening mesh nodes between the two endpoints and the two endpoints each determine the channel usage;

determining an average flow for competing flows among the flows;

determining a fair share of channel usage based on the determined channel usage for the competing flows and the average flow 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 tangible computer-readable storage medium having computer-executable instructions for enforcing channel usage for flows;

comprising;

monitoring entire flows between mesh nodes within the ad hoc wireless network;

at mesh nodes within an ad hoc wireless network, determining a channel usage for a channel through the mesh node and sharing the channel usage with neighbors of the mesh 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;

wherein determining the fair share of channel usage comprises determining an average flow for competing flows;

wherein each of the competing flows is a stream of packets between two endpoints on the ad hoc wireless network;

wherein at least one of the competing flows within the ad hoc wireless network includes one or more intervening mesh nodes between the two endpoints;

wherein the one or more intervening mesh nodes between the two endpoints and the two endpoints each determine the channel usage; 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 storage 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 storage medium of claim 10, further comprising adjusting a link metric to determine a more efficient route.

12. The computer-readable storage medium of claim 11, 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.

13. The computer-readable storage medium of claim 12, 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.

14. 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;

wherein each of the flows is a stream of packets between two endpoints on the ad hoc wireless mesh network;

wherein at least one of the flows within the ad hoc wireless network includes one or more intervening mesh nodes between the two endpoints; and

an algorithm configured to perform steps using the processor, including;

determining a channel usage for the flows through the channel between mesh nodes within the ad hoc wireless network;

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;

sharing the channel usage information with neighbors by each of the mesh nodes that determine the channel usage information transmitting the channel usage information;

processing neighborhood channel usage information;

determining a fair share channel usage; and

adjusting a flow rate.

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

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

17. The apparatus of claim 16, 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.

18. The apparatus of claim 14, 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.

19. The apparatus of claim 14, 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.