Power and delay sensitive ad-hoc communication networks

• US 7,414,977 B2
• Filed: 11/25/2003
• Issued: 08/19/2008
• Est. Priority Date: 11/25/2003
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Zhang, Jinyun, Sahinoglu, Zafer, Orlik, Philip
• Primary Examiner(s): Nguyen; Chau
• Assistant Examiner(s): Kang; Suk Jin
• Application Number:
  US10/722,031
• Publication Number:
  US 20050111428A1
• Time in Patent Office: 1,729 Days
• Field of Search: 370/238, 370/318, 370/311
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/28 for reactive routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: Y02D 30/00 Reducing energy consumption in communication networks
• CPC Class Codes: Y02D 30/70 in wireless communication networks

Abstract

An ad-hoc wireless communication network includes multiple nodes. Each node maintains a routing table. The routing table is constructed by broadcasting route request packets from a source node. The request packet includes an address of a destination node. Intermediate nodes in the network receiving the request packet, determine power and delay cost associated with the intermediate node participating in the route. If the cost is less than a threshold value, then the intermediate node participates in the routing of packets for other nodes. The intermediate node then sends a reply packet back to the source node. The reply packet includes the intermediate node addresses, as well as the power and delay costs. The source can thus construct the routing table. The source node can select a particular node for transferring application data packets based on either the power cost, the delay cost or both costs.

Claims

1. A method for maximizing residual power along routes in a wireless network including a plurality of battery operated nodes, comprising:

discovering a plurality of routes from a destination node to a source node via intermediate nodes of the network using dynamic source routing (DSR);

measuring a residual power in the battery of each intermediate node;

determining a power cost associated with each route according to the residual power of the intermediate nodes;

selecting a particular route for transferring data from the source node to the destination node, the particular route having a least power cost;

including the particular route in a routing table in a packet, in which the routing table is an ordered list of intermediate node addresses;

determining a delay cost associated with each route;

selecting a particular route having a least delay cost; and

including the least delay cost in each transmitted packet; and

transmitting each packet in the network using the DSR, and in which each packet includes the routing table.

2. The method of claim 1, further comprising:

associating a time of discovery with each route;

selecting the particular route having a most recent time of discovery; and

including a time stamp indicating the time that the particular route was discovered in the routing table in each transmitted packet.

3. The method of claim 1, in which the network is ad-hoc.

4. The method of claim 1, further comprising:

storing a routing table in each node.

5. The method of claim 1, further comprising:

quantizing the residual power to a power level to determine the power cost.

6. The method of claim 5, further comprising:

participating in the route if the power level is a least power level;

not participating in the route if the power level is a highest level; and

participating in the route if the power level is an intermediate power level, and increasing the power cost according to the power level.

7. The method of claim 5, in which an initial power of an n^th node is E joules, and the residual power in the n^th node at time t is R(t) joules, and the power cost for using n^th node as an intermediate node is P(n), and the power level L(t) of the n^th is determined by

if R(t)≦

E*α

, then L(t)=3;

else if E*α

<

R(t)≦

E*β

, then L(t)=2;

else if E*β

<

R(t)≦

E*γ

, then L(t)=1;

else L(t)=0/

where α

,β

, and γ

are numbers less than 1.0 and monotonically increasing according to α

<

β

<

γ

.

8. The method of claim 1, in which the discovering uses ad-hoc on-demand distance vector routing, and includes the routing table in each transmitted packet.

11. The method of claim 1, in which the routing table includes a delay cost and the power cost of the route.

12. The method of claim 1, further comprising:

updating the routing table in each packet when the packet is transmitted.

13. The method of claim 1, further comprising:

including, in each packets, an amount of residual power in each node along the particular route.

9. A method for maximizing residual power along routes in a wireless network including a plurality of nodes, each node having an address and a battery, comprising:

broadcasting a request packet, the request packet including the address of a source node and the address of a destination address using dynamic source routing (DSR);

receiving the request packet in an intermediate node;

measuring a residual power in the battery of the intermediate node;

determining a power cost associated with each route according to the residual power of the intermediate nodes;

sending a reply packet to the source node, the reply packet including the address of the intermediate node and the power cost;

determining a delay cost associated with each route;

selecting a particular route having a least delay cost;

including the least delay cost in each transmitted packet; and

repeating the broadcasting , receiving, measuring, determining and the sending until the request packet reaches the destination node;

constructing a route in a routing table in the source node from the reply packets, the route having the associated power cost;

selecting a particular route for transferring a data packet from the source node to the destination node, the particular route having a least power cost;

including the particular route in a routing table in a packet, in which the routing table is an ordered list of intermediate node addresses; and

transmitting each packet in the network using the DSR, and in which each packet includes the routing table.

10. A wireless network including a plurality of battery operated nodes, comprising:

means for discovering a plurality of routes from a destination node to a source node via intermediate nodes of the network using dynamic source routing;

means for measuring a residual power in the battery of each intermediate node;

means for determining a power cost associated with each route according to the residual power of the intermediate nodes; and

means for selecting a particular route for transferring data from the source node to the destination node, the particular route having a least power cost, in which the particular route is included in a routing table in a packet, in which the routing table is an ordered list of intermediate node addresses;

determining a delay cost associated with each route;

selecting a particular route having a least delay cost;

including the least delay cost in each transmitted packet and each packet in the network using the dynamic source routing, and in which each packet includes the routing table.