Maximum lifetime routing in wireless ad-hoc networks

• US 7,801,042 B2
• Filed: 12/20/2002
• Issued: 09/21/2010
• Est. Priority Date: 12/20/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Sankar, Arvind, Liu, Zhen
• Primary Examiner(s): Yao; Kwang B
• Assistant Examiner(s): Cehic; Kenan
• Application Number:
  US10/537,590
• Publication Number:
  US 20060206857A1
• Time in Patent Office: 2,832 Days
• Field of Search: 370/235, 370/230.1, 370/231, 370/236.1, 370/236.2, 370/389, 370/238, 370/351, 370/237, 370/412, 370/429, 455/445, 709238-244
• US Class Current: 370/235
• 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/38 Flow based routing
• CPC Class Codes: H04W 28/02 Traffic management, e.g. flow control or congestion control
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/08 based on transmission power
• CPC Class Codes: H04W 40/10 based on available power or energy
• 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

Routing techniques are provided that meet performance objectives associated with an ad-hoc network environment and the like. The techniques of invention serve to substantially maximize the lifetime of the network. In one aspect of the invention, a packet routing technique for use in a node of a distributed network comprises the following steps/operations. Queues for storing packets are maintained, wherein at least one queue is associated with a link existing between the node and a neighboring node, and a queue has a height associated therewith. A route is then determined for one or more packets stored in the queues based on heights of queues at neighboring nodes, such that energy constraints associated with the node and the neighboring nodes are substantially maximized. As mentioned, the distributed network is preferably a mobile ad-hoc network wherein the node and the at least one neighboring node communicate over a wireless link.

Claims

1. A method for routing packets in a distributed network including a plurality of nodes, the nodes being coupled via links and the nodes having queues associated with the links, the method comprising the steps of:

injecting a packet flow into the distributed network at a corresponding source node, wherein the packet flow is stored in an overflow buffer of the source node in response to a height of at least a given queue of the source node exceeding a threshold;

equalizing the queues at each node of the distributed network wherein an integer number of packets in each queue is maintained;

pushing the packet flow in the distributed network such that packets are moved from a queue with a higher height to a queue with a lower height in a manner that substantially minimizes power dissipation at affected nodes in order to prevent exhaustion of any energy reserve associated with an affected node; and

absorbing the packet flow at a corresponding sink node such that heights of queues at the sink node are set to zero;

wherein each queue has a potential function associated therewith, the potential function of a given queue being a function of the height of the given queue, and wherein packets are routed so as to minimize the sum of the potential functions of the queues of the nodes of the distributed network wherein the potential function comprises a constraint based at least in part on respective energy reserves associated with affected nodes and an amount of energy required to move packets between the affected nodes.

2. The method of claim 1, wherein the distributed network is a mobile ad-hoc network, and further wherein a node and at least one neighboring node communicate over a wireless link.

3. The method of claim 1, further comprising the step of a node receiving broadcast information from at least one neighboring node pertaining to the height of at least one queue of the at least one neighboring node.

4. The method of claim 1, wherein the injecting, equalizing, pushing and absorbing steps are performed for a number of rounds such that throughput requirements are substantially satisfied while substantially maximizing a time period prior to exhaustion of an energy reserve associated with any node of the distributed network.

5. The method of claim 4, wherein the time period has an upper bound and a lower bound associated therewith.

6. The method of claim 1, further comprising the step of a node broadcasting information to at least one neighboring node pertaining to the height of at least one queue of the broadcasting node.

7. The method of claim 1, wherein the pushing step further comprises accounting for at least one of:

(i) idle power consumption associated with a node;

(ii) computation power consumption associated with a node;

(iii) a periodic recharge associated with a node;

(iv) one or more edge constraints; and

(v) power consumption associated with receiving a packet at a node.

8. The method of claim 1, wherein the distributed network changes one of statically and dynamically.

9. Apparatus for use in a node of a distributed network, the distributed network including a plurality of nodes, the nodes being coupled via links and the nodes having queues associated with the links, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to perform the steps of;

injecting a packet flow into the distributed network at a corresponding source node, wherein the packet flow is stored in an overflow buffer of the source node in response to a height of at least a given queue of the source node exceeding a threshold;

equalizing the queues at each node of the distributed network wherein an integer number of packets in each queue is maintained;

pushing the packet flow in the distributed network such that packets are moved from a queue with a higher height to a queue with a lower height in a manner that substantially minimizes power dissipation at affected nodes in order to prevent exhaustion of any energy reserve associated with an affected node; and

absorbing the packet flow at a corresponding sink node such that heights of queues at the sink node are set to zero;

wherein each queue has a potential function associated therewith, the potential function of a given queue being a function of the height of the given queue, and wherein packets are routed so as to minimize the sum of the potential functions of the queues of the nodes of the distributed network wherein the potential function comprises a constraint based at least in part on respective energy reserves associated with affected nodes and an amount of energy required to move packets between the affected nodes.

10. The apparatus of claim 9, wherein the distributed network is a mobile ad-hoc network, and further wherein a node and at least one neighboring node communicate over a wireless link.

11. The apparatus of claim 9, wherein the processor is further operative to perform the step of receiving broadcast information from at least one neighboring node pertaining to the height of at least one queue of the at least one neighboring node.

12. The apparatus of claim 9, wherein the processor is further operative to perform the injecting, equalizing, pushing and absorbing steps for a number of rounds such that throughput requirements are substantially satisfied while substantially maximizing a time period prior to exhaustion of an energy reserve associated with any node of the distributed network.

13. The apparatus of claim 12, wherein the time period has an upper bound and a lower bound associated therewith.

14. The apparatus of claim 9, wherein the processor is further operative to perform the step of broadcasting information to at least one neighboring node pertaining to the height of at least one queue of the broadcasting node.

15. The apparatus of claim 9, wherein the pushing step further comprises accounting for at least one of:

(i) idle power consumption associated with a node;

(ii) computation power consumption associated with a node;

(iii) a periodic recharge associated with a node;

(iv) one or more edge constraints; and

(v) power consumption associated with receiving a packet at a node.

16. The apparatus of claim 9, wherein the distributed network changes one of statically and dynamically.

17. A non-transitory, tangible computer readable medium for use in a node of a distributed network for use in a node of a distributed network, the distributed network including a plurality of nodes, the nodes being coupled via links and the nodes having queues associated with the links, the non-transitory, tangible computer readable medium containing one or more programs which when executed by a processor implement the steps of:

injecting a packet flow into the distributed network at a corresponding source node, wherein the packet flow is stored in an overflow buffer of the source node in response to a height of at least a given queue of the source node exceeding a threshold;

equalizing the queues at each node of the distributed network wherein an integer number of packets in each queue is maintained;

pushing the packet flow in the distributed network such that packets are moved from a queue with a higher height to a queue with a lower height in a manner that substantially minimizes power dissipation at affected nodes in order to prevent exhaustion of any energy reserve associated with an affected node; and

absorbing the packet flow at a corresponding sink node such that heights of queues at the sink node are set to zero;

wherein each queue has a potential function associated therewith, the potential function of a given queue being a function of the height of the given queue, and wherein packets are routed so as to minimize the sum of the potential functions of the queues of the nodes of the distributed network wherein the potential function comprises a constraint based at least in part on respective energy reserves associated with affected nodes and an amount of energy required to move packets between the affected nodes.

18. The article of claim 17, wherein the distributed network is a mobile ad-hoc network, and further wherein a node and at least one neighboring node communicate over a wireless link.

19. The article of claim 17, wherein the one or more programs further implement the step of receiving broadcast information from at least one neighboring node pertaining to the height of at least one queue of the at least one neighboring node.

20. The article of claim 17, wherein the one or more programs further implement the injecting, equalizing, pushing and absorbing steps for a number of rounds such that throughput requirements are substantially satisfied while substantially maximizing a time period prior to exhaustion of an energy reserve associated with any node of the distributed network.

21. The article of claim 20, wherein the time period has an upper bound and a lower bound associated therewith.

22. The article of claim 17, wherein the processor is further operative to perform the step of broadcasting information to at least one neighboring node pertaining to the height of at least one queue of the broadcasting node.

23. The article of claim 17, wherein the pushing step further comprises accounting for at least one of:

(i) idle power consumption associated with a node;

(ii) computation power consumption associated with a node;

(iii) a periodic recharge associated with a node;

(iv) one or more edge constraints; and

(v) power consumption associated with receiving a packet at a node.

24. The article of claim 17, wherein the distributed network changes one of statically and dynamically.