Congestion management in an ad-hoc network based upon a predicted information utility

• US 7,966,419 B2
• Filed: 07/03/2006
• Issued: 06/21/2011
• Est. Priority Date: 07/03/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Liu, Juan, Huang, Qingfeng, Greene, Daniel H., Reich, James E., Mosko, Marc E.
• Primary Examiner(s): Strange; Aaron
• Assistant Examiner(s): BUI, JONATHAN A
• Application Number:
  US11/428,437
• Publication Number:
  US 20080002573A1
• Time in Patent Office: 1,814 Days
• Field of Search: 709/238, 709/240, 709/242, 709/243
• US Class Current: 709/238
• CPC Class Codes: H04L 47/2458 Modification of priorities while in transit
• CPC Class Codes: H04W 24/00 Supervisory, monitoring or testing arrangements
• CPC Class Codes: H04W 28/021 in wireless networks with changing topologies, e.g. ad-hoc networks self-organizing networks H04W84/18
• CPC Class Codes: H04W 28/0231 based on communication conditions dynamic wireless traffic scheduling definition based on channel quality criteria H04W72/54
• CPC Class Codes: H04W 28/0289 Congestion control load shedding arrangements in network planning H04W16/08; performing reselection for handling the traffic H04W36/22; wireless traffic scheduling H04W72/12
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

A method of managing traffic in an ad hoc network determines local data traffic levels at a node, and uses the local data traffic levels to define a criteria. The criteria is applied to a microutility associated with the data sample to determine if the data sample should be propagated, temporarily delayed or dropped.

Claims

1. A method of managing traffic in an ad hoc network, comprising:

determining local data traffic levels at a mobile recipient node in an ad hoc network;

using the local data traffic levels and battery power at the mobile recipient node to define a threshold;

receiving a data sample from a data source node, the data sample having a microutility generated at the data source node that represents a predicted usefulness of the data by the mobile recipient node, wherein the microutility includes coordinates of the data source node, a target geographic area for distribution in the mobile network, and the distance the data sample has traveled since generation; and

applying the threshold to the microutility accompanying the data sample at the mobile recipient node, wherein the associated microutility value for the distance the data sample has traveled since generation in the data sample is less than the threshold, causing the data sample to be either discarded or temporarily delayed.

2. The method of claim 1, wherein determining local data traffic levels further comprises determining local data traffic levels at the node and neighboring nodes.

3. The method of claim 2, wherein determining local data traffic levels further comprises exchanging information with neighboring nodes.

4. The method of claim 3, wherein exchanging information with neighboring nodes further comprise authenticating information exchanged with neighboring nodes.

5. The method of claim 2, wherein exchanging information with neighboring nodes further comprises one of exchanging information out of band or through explicit management packets.

6. The method of claim 2, wherein exchanging information with neighboring nodes further comprises updating a central repository.

7. The method of claim 2, wherein exchanging information with neighboring nodes further comprises exchanging recent histories of microutilities by one of data packets, explicit management packets, or updating a central repository.

8. The method of claim 1, wherein determining local data traffic further comprises measuring queue length at the node.

9. The method of claim 1, wherein determining local data traffic levels further comprises measuring historic queue lengths where recent queue lengths have a larger effect than less recent queue lengths.

10. The method of claim 1, wherein determining local data traffic levels further comprises measuring a local queue delay.

11. The method of claim 1, wherein determining local data traffic levels further comprises measuring historic local queue lengths, where recent queue lengths have a larger effect than less recent queue lengths.

12. The method of claim 1, wherein determining local data traffic levels further comprises measuring packet-size weighted queue length.

13. The method of claim 1, wherein determining local data traffic levels further comprises measuring historic packet-size weighted queue lengths, where recent queue lengths have a larger effect than less recent queue lengths.

14. The method of claim 1, wherein determining local data traffic levels further comprises retrieving a neighbor congestion measure from a data packet received from a neighboring node and combining the neighbor congestion measure with a local congestion measure.

15. The method of claim 1, the method further comprising including information about local data traffic levels in outgoing data transmissions.

16. The method of claim 1, wherein using the local data traffic levels to define a criteria further comprises using the microutilities of recently received data samples to determine the threshold.

17. The method of claim 16, wherein using the microutilities of recently received data samples further comprises using the microutilities to rescale the microutility of the data sample before the threshold is applied.

18. The method of claim 1, wherein determining local traffic levels further comprises using a different measure of local traffic levels over time.

19. The method of claim 1, wherein determining local traffic levels further comprises using an area traffic summary.

20. The method of claim 1, wherein determining local traffic levels further comprises using an extended view of traffic.

21. An article of non-transitory computer-readable media containing instructions that, when executed, cause the computer to:

determine local data traffic levels at a mobile recipient node in an ad hoc network;

use the local data traffic levels and battery power at the mobile recipient node to define a threshold;

receive a data sample from a data source node, the data sample having a microutility generated at the data source node that represents a predicted usefulness of the data by the mobile recipient node, wherein the microutility includes coordinates of the data source node, a target geographic area for distribution in the mobile network, and the distance the data sample has traveled since generation; and

applying the threshold to the microutility accompanying the data sample at the mobile recipient node, wherein the associated microutility value for the distance the data sample has traveled since generation in the data sample is less than the threshold, causing the data sample to be either discarded or temporarily delayed.

22. The article of claim 21, wherein the instructions that cause the computer to determine the local data traffic levels further comprises determining local data traffic levels at the node and neighboring nodes.

23. The article of claim 21, wherein the instructions that cause the computer to determine the local data traffic levels further causes the computer to measure one of:

queue length at the node, a local queue delay, or a packet-size weighted queue length.

24. The article of claim 21, wherein the instructions that cause the computer to determine the local data traffic levels further cause the computer to determine one of:

a different measure of local traffic levels over time, an area traffic summary, or an extended view of traffic.