Power and delay sensitive ad-hoc communication networks

• US 20050111428A1
• Filed: 11/25/2003
• Published: 05/26/2005
• Est. Priority Date: 11/25/2003
• Status: Active Grant

• 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
• Granted Patent: US 7,414,977 B2
• Time in Patent Office: Days
• US Class Current: 370/344
• 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;

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

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

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

2. The method of claim 1, further comprising:

determining a delay cost associated with each route; and

selecting the a particular route having a least delay cost.

3. The method of claim 1, further comprising:

associating a time of discovery with each route; and

selecting the particular route having a most recent time of discovery.

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

5. The method of claim 1, further comprising:

storing a routing in each node.

6. The method of claim 1, further comprising:

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

7. The method of claim 6, 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.

8. The method of claim 6, 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 α

<

β

<

γ

.

9. The method of claim 1, in which the discovering uses dynamic source routing.

10. The method of claim 1, in which the discovering uses ad-hoc on-demand distance vector routing.

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

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 the residual power of the intermediate nodes; and

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

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.

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

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

means for determining a power cost associated with each route according 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.