Information driven routing in ad hoc sensor networks

• US 7,720,993 B2
• Filed: 12/17/2003
• Issued: 05/18/2010
• Est. Priority Date: 12/17/2003
• Status: Expired due to Fees

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Zhao, Feng, Liu, Juan
• Primary Examiner(s): Najjar; Saleh
• Assistant Examiner(s): SHAW, ROBERT A
• Application Number:
  US10/736,748
• Publication Number:
  US 20050138200A1
• Time in Patent Office: 2,344 Days
• Field of Search: 709/238
• US Class Current: 709/238
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04W 40/00 Communication routing or communication path finding
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

A sensor network routing is formulated as a joint optimization problem taking into account routing cost and information aggregation. Information gain is used explicitly to optimize the routing path. The optimization approach involves a shortest path algorithm in a modified network graph. A method is provided that routes queries from an arbitrary entry point to high activity network sensor regions using inputs from sensor nodes along the path to refine the message. The multiple step look-ahead approach provides deadlock avoidance and routing around sensor network holes. For point-to-point query routing, a method based on real-time A* (RTA*) search is provided to find a path which takes detours efficiently to maximize information aggregation. Future information expected to be gained along the path from an arbitrary node to an exit node may be estimated to allow the selection of a successor sensor node.

Claims

1. A method of routing at least one information query from one or more sensor network entry points in a network of sensor nodes to one or more destination nodes in a vicinity of physical phenomena of interest in the network, the method comprising:

selecting a destination node by computing a utility of a plurality of network sensor nodes and selecting a node with highest utility to be the destination node wherein the computed utility indicates information gain;

establishing a leader node;

using a multiple step lookup procedure to determine a path between the leader node and the destination node that is optimum with respect to utility; and

routing at least one information query to the destination node based on the path,

a locus of all possible paths from a current node in the path to the destination node that can be traversed within a specified path length forms an ellipse with the destination node as one focus point and the current node as another focus point, the ellipse is sampled with four candidate points,

a maximum utility among four paths corresponding to the four candidate points, is assigned as the utility of the ellipse; and

the four paths start at the current node, end at the destination node, and traverse one of the ellipse'"'"'s minor axis or major axis.

2. A method of routing an information query of claim 1, wherein the multiple step lookup procedure comprises:

determining a minimum number of hops required to reach the destination node from the leader node;

determining all possible paths of the minimum number of hops or less from the leader node to the destination node;

determining the utilities of all possible minimum number of hops paths;

selecting a minimum number of hops path that traverses nodes the sum of whose utilities is the greatest; and

selecting a first node in the selected minimum number of hops path and passing leadership from the leader node to the first node, wherein the first node becomes the leader node.

3. A system to route information via a network of sensor nodes from a leader node to a destination node, the system comprising:

a destination node selection mechanism that determines a utility of a plurality of nodes and selects a node with a highest utility to be the destination node;

wherein the determined utility indicates information gain;

establishing a leader node;

a processing mechanism that determines a minimum number of hops required to reach the destination node from a current leader node;

a processing mechanism that determines a number of possible paths within a specified number of hops or less from the current leader node to the destination node;

a path selection mechanism that selects a minimum hop path that traverses nodes the sum of whose utilities is the greatest; and

a selection mechanism that selects a first node in the selected minimum hop path and passes leadership from the current leader node to the first node, wherein the first node becomes the current leader node

a locus of all possible paths from a current node in the path to the destination node that can be traversed within a specified path length forms an ellipse with the destination node as one focus point and the current node as another focus point, the ellipse is sampled with four candidate points,

a maximum utility among four paths corresponding to the four candidate points, is assigned as the utility of the ellipse; and

the four paths start at the current node, end at the destination node, and traverse one of the ellipse'"'"'s minor axis or major axis.

4. The system of claim 3, further comprising:

a leadership transfer mechanism that changes leadership from one node to another node.

8. The system of claim 3, wherein the sensor nodes comprise different types of sensors.

9. The system of claim 3, wherein the sensor nodes comprise acoustic sensors.

10. The system of claim 3, wherein the sensor nodes comprise seismic sensors.

5. A point-to-point routing method for routing a query via a network of sensor nodes including a source sensor node and a destination sensor node, the method comprising:

selecting a source sensor node and a destination sensor node;

establishing a neighborhood around the source sensor node;

determining costs associated with communication that has already occurred along paths to sensor nodes in the neighborhood around the source sensor node and costs associated with going forward along paths to sensor nodes in the neighborhood around the source sensor node;

determining information gain based on network sensor nodes already visited for a number of paths in the neighborhood around the source sensor node and to be visited for a number of paths in the neighborhood around the source sensor node; and

conducting an RTA* type forward search to relay a query from the source sensor node to the destination sensor node based on the determined cost and the determined information gain,

a locus of all possible paths from a current node in the path to the destination sensor node that can be traversed within a specified path length forms an ellipse with the destination sensor node as one focus point and the current node as an other focus point, the ellipse is sampled with four candidate points,

a maximum utility among four paths corresponding to the four candidate points, is assigned as the utility of the ellipse; and

the four paths start at the current node, end at the destination sensor node, and traverse one of the ellipse'"'"'s minor axis or major axis.

6. A method of routing information about the location of an event via a network of sensor nodes including a leader node and a destination node, the method comprising:

selecting a destination node by computing a utility of a plurality of nodes and selecting a node with a highest utility to be the destination node;

wherein the utility indicates information gain

establishing a leader node;

determining a minimum number of hops required to reach the destination node from the leader node;

determining all possible paths within a specified number of hops or less from the leader node to the destination node;

selecting a path within a specified number of hops or less from the leader node to the destination node that traverses nodes the sum of whose utilities is the greatest;

selecting a first node in the selected path and passing leadership from the leader node to the first node, wherein the first node becomes the leader node

a locus of all possible paths from a current node in the path to the destination node that can be traversed within a specified path length forms an ellipse with the destination node as one focus point and the current node as an other focus point, the ellipse is sampled with four candidate points,

a maximum utility among four paths corresponding to the four candidate points, is assigned as the utility of the ellipse; and

the four paths start at the current node, end at the destination node, and traverse one of the ellipse'"'"'s minor axis or major axis.

7. A method of routing a query about a location of an event of interest via a network of sensor nodes, the method comprising:

determining a source sensor node;

establishing a neighborhood around the source sensor node;

determining communication costs, including costs associated with communication that has already occurred along paths to sensor nodes in the neighborhood around the source sensor node and costs associated with going forward along paths to sensor nodes in the neighborhood around the source sensor node;

determining information gain based already visited for a number of paths to sensor nodes in the neighborhood around the source sensor node and to be visited for a number of paths to sensor nodes in the neighborhood around the source sensor node;

forming a belief state about the location of the event of interest based on the determined communication costs and determined information gain;

determining a destination based on the location of an event of interest

routing the query based on the belief state, wherein a locus of all possible paths from a current node in the path to the destination that can be traversed within a specified path length forms an ellipse with the destination node as one focus point and the current node as an other focus point,

the ellipse is sampled with four candidate points, a maximum utility among four paths corresponding to the four candidate points, is assigned as the utility of the ellipse; and

the four paths start at the current node, end at the destination, and traverse one of the ellipse'"'"'s minor axis or major axis.

11. A method of information-directed query routing along a path from a source node to a destination node in a network of sensor nodes, the method comprising:

selecting a source sensor node and a destination sensor node;

determining a path from the source node to the destination node that is more efficient in terms of communication cost than other paths from the source node to the destination node; and

maximally aggregating gain of information about an event along the path; and

routing a query based on the determined cost and aggregated information gain, wherein

a locus of all possible paths from a current node in the path to the destination node that can be traversed within a specified path length forms an ellipse with the destination node as one focus point and the current node as an other focus point, the ellipse is sampled with four candidate points,

a maximum utility among four paths corresponding to the four candidate points, is assigned as the utility of the ellipse; and

the four paths start at the current node, end at the destination node, and traverse one of the ellipse'"'"'s minor axis or major axis.

15. The method of claim 11, wherein maximally aggregating gain of information about the event of interest along the path comprises finding a path that includes detours around sensor network holes and at least one path ending.

12. A method of point-to-point routing of query information regarding a phenomenon of interest in a sensor network having a plurality of sensor nodes along a path from an entry point node to an exit point, the method comprising:

establishing a leader node;

maximally aggregating information about a phenomenon of interest along a path from an entry point node to an exit point by estimating information expected to be gained from the entry node to the exit point node;

selecting a successor leader node based on the estimated information expected to be gained;

routing query information based on the maximally aggregated information, wherein

a locus of all possible paths from a current node in the path to the exit point that can be traversed within a specified path length forms an ellipse with the exit point as one focus point and the current node as an other focus point, the ellipse is sampled with four candidate points,

a maximum utility among four paths corresponding to the four candidate points, is assigned as the utility of the ellipse; and

the four paths start at the current node, end at the exit point, and traverse one of the ellipse'"'"'s minor axis or major axis.

13. The method of claim 12, wherein estimating the information expected comprises establishing and moving a frontier and iteratively expanding nodes on the frontier until the exit point is reached.

14. The method of claim 12, further comprising:

obtaining network node sensor measurements to refine target estimates of the exit point wherein the exit point is the location of an event of interest.