Maximum lifetime routing in wireless ad-hoc networks

• US 20060206857A1
• Filed: 12/20/2002
• Published: 09/14/2006
• Est. Priority Date: 12/20/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Liu, Zhen, Sankar, Arvind
• Granted Patent: US 7,801,042 B2
• Time in Patent Office: Days
• US Class Current: 717/104
• 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 use in a node of a distributed network for routing packets, the method comprising the steps of:

maintaining queues for storing packets, 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; and

determining a route 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.

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

3. The method of claim 1, wherein one or more packets are sent, over a link, from a queue of the node to a queue of a neighboring node when the height of the queue of the node is greater than the height of the queue of the neighboring node.

4. The method of claim 1, wherein one or more packets are received, over a link, in a queue of the node from a queue of a neighboring node when the height of the queue of the node is less than the height of the queue of the neighboring node.

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

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

7. The method of claim 1, wherein packets are routed at least one of to and from the node in rounds such that throughput requirements are substantially satisfied while substantially maximizing a lifetime associated with the distributed network.

8. The method of claim 1, wherein the network lifetime has an upper bound and a lower bound associated therewith.

9. The method of claim 1, wherein the route determining 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.

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

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

equalizing the queues at each node of the distributed network;

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; and

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

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

13. The method of claim 11, 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 one neighboring node.

14. The method of claim 11, 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 lifetime associated with the distributed network.

15. Apparatus for use in a node of a distributed network for routing packets, the apparatus comprising:

a memory; and

at least one processor coupled to the memory and operative to;

(i) maintain queues for storing packets, 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; and

(ii) determine a route 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.

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

17. The apparatus of claim 15, wherein one or more packets are sent, over a link, from a queue of the node to a queue of a neighboring node when the height of the queue of the node is greater than the height of the queue of the neighboring node.

18. The apparatus of claim 15, wherein one or more packets are received, over a link, in a queue of the node from a queue of a neighboring node when the height of the queue of the node is less than the height of the queue of the neighboring node.

19. The apparatus of claim 15, further wherein the node receives broadcast information from at least one neighboring node pertaining to the height of at least one queue of one neighboring node.

20. The apparatus of claim 15, further wherein the node broadcasts information to at least one neighboring node pertaining to the height of at least one queue of the node.

21. The apparatus of claim 15, wherein packets are routed at least one of to and from the node in rounds such that throughput requirements are substantially satisfied while substantially maximizing a lifetime associated with the distributed network.

22. The apparatus of claim 15, wherein the network lifetime has an upper bound and a lower bound associated therewith.

23. The apparatus of claim 15, further wherein the route determining operation accounts 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 apparatus of claim 15, wherein the distributed network changes one of statically and dynamically.

25. An article of manufacture for use in a node of a distributed network for routing packets, comprising a machine readable medium containing one or more programs which when executed implement the steps of:

maintaining queues for storing packets, 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; and

determining a route 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.