Systems and methods for constrained anisotropic diffusion routing within an ad hoc network

• US 20040010492A1
• Filed: 05/28/2003
• Published: 01/15/2004
• Est. Priority Date: 05/28/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Zhao, Feng, Haussecker, Horst W.
• Granted Patent: US 7,194,463 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: H04L 45/025 Updating only a limited number of routers, e.g. fish-eye update
• CPC Class Codes: H04L 45/14 Routing performance; Theoretical aspects
• CPC Class Codes: H04W 40/04 based on wireless node resources
• CPC Class Codes: H04W 40/20 based on geographic position or location
• 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
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

This invention describes methods and systems for tasking nodes in a distributed ad hoc network. A node is selected to participate in a data gathering or a routing task based on its potential contribution to information gain and the cost associated with performing the task such as communication bandwidth usage. This invention describes methods and systems for implementing various selection strategies at each node, using local knowledge about the network. For resource-limited sensor networks, the information-driven data gathering and routing strategies significantly improve the scalability and quality of sensing systems, while minimizing resource cost.

Claims

1. A method for selecting a data routing path in an ad hoc network having a plurality of nodes, comprising:

transmitting a task query to a current node of the plurality of nodes from a previous node of the plurality of nodes; and

selecting a next node from the plurality of nodes based on a trade-off between an information gain regarding the task query that is provided by the next node and a cost for obtaining the information gain at that next node.

2. The method according to claim 1, wherein each node comprises one or more sensing devices microprocessors, storage devices, and communication links.

3. The method according to claim 2, wherein the one or more sensing devices include one or more microphones, vibration sensors, photo cells, thermometers, cameras, magnetomers, infra-red sensors, chemical sensors and biological sensors.

4. The method according to claim 1, wherein:

the task query comprises a request for information about a target located adjacent to at least one node of the plurality of nodes;

the information gain comprises a quality of information generated by the next node about the target; and

the cost for obtaining the information gain comprises a cost of transmitting the obtained information gain to at least the previous node.

5. The method according to claim 1, wherein transmitting the task query comprises wirelessly transmitting the task query.

6. The method according to claim 1, wherein transmitting the task query comprises transmitting the task query over a wired connection.

7. The method according to claim 1, further comprising transmitting the task query to the next node.

8. The method according to claim 1, further comprising transmitting multiple task queries to multiple nodes.

9. The method according to claim 8, wherein transmitting the multiple queries to the multiple nodes comprises transmitting the multiple queries to the multiple nodes substantially simultaneously.

10. The method according to claim 1, further comprising transmitting a belief state and the task query to the next node.

11. The method according to claim 10, wherein transmitting the belief state comprises transmitting a description about a physical phenomenon being monitored.

12. A method according to claim 9, further comprising updating the belief state based on sensor data at local or remote node.

13. The method according to claim 12, further comprising transmitting the updated belief state and the task query to the next node.

14. The method according to claim 1, wherein selecting the next node comprises selecting the next node only from neighboring nodes of the current node.

15. The method according to claim 14, wherein the neighboring nodes are determined by a specific range.

16. The method according to claim 15, wherein the specified range is a communication distance.

17. The method according to claim 1, further comprising determining the information gain based on a reduction of a residual uncertainty for an estimation task.

18. The method according to claim 1, further comprising determining the cost based on a consumption of bandwidth.

19. The method according to claim 1, further comprising determining the cost based on a consumption of energy.

20. The method according to claim 1, further comprising determining the trade-off based on an optimization of an objective function of the information gain and the cost.

21. The method according to claim 1, further comprising:

determining the information gain based on an ability of the next node to perform a task specified by the task query; and

determining the cost based on a resource cost for the next node to perform the task.

22. A method for selecting a data routing path in a sensor network with a plurality of queried sensors and a plurality of unqueried sensors, comprising:

determining a current belief state at a current sensor based on information obtained from the plurality of queried sensors;

selecting a set of neighboring sensors from the plurality of unqueried sensors;

determining an information utility function value that indicates an information quality for information obtained from each of the plurality of queried sensors, the indicated information quality based on a set of predefined information quality parameters;

determining a cost function value that indicates at least one of power and bandwidth usage required to transmit information obtained from each of the neighboring sensors;

determining a weighted sum of the information utility function value and the cost function value;

applying the determined weighted sum to the selected set of neighboring sensors to select a next sensor from the selected set of neighboring sensors;

determining a new belief state for the next sensor based on the current belief state and information obtained by the current sensor; and

transmitting at least the new belief state to the next sensor.

25. The network according to claim 22, wherein the next node selecting circuit, routine or application further transmits the query to the selected next node.

26. The network according to claim 22, each of the plurality of nodes further comprising a belief state updating circuit, routine or application, wherein:

the query is associated with a belief state regarding a target;

the belief state updating circuit, routine or application updates the belief state based on the selected next node; and

the next node selecting circuit, routine or application transmits the updated belief state and the query to the selected next node.

27. The network according to claim 22, wherein the neighboring node information stored in the memory is information only about nodes within a specified neighboring range of the current node.

28. The network according to claim 25, wherein the specified range is a specified communication distance.

29. The network according to claim 22, wherein each node comprises a sensor.

30. The network according to claim 22, wherein the information gain comprises a quality of information generated by the next node about a target.

31. The network according to claim 22, wherein the cost includes a consumption of a bandwidth.

32. The network according to claim 22, wherein the cost includes a consumption of energy.

33. The network according to claim 22, wherein the information gain comprises an ability for the next node to perform a task specified in the query, and the cost includes a resource cost for the next node to perform the task.

34. The network according to claim 22, wherein two queries are sent to two nodes simultaneously.

23. A method for creating a data routing path in a sensor network, the data routing path comprising a sequence of data path sensors selected from the sensor network, the method comprising:

determining a current belief state for a current sensor in the sequence of data path sensors, the current belief state providing an estimate of a target state for a target that the sensor network is monitoring and tracking based on information obtained from the sequence of data path sensors;

selecting a set of neighboring sensors from the sensor network not including the sequence of data path sensors, each of the neighboring sensors being within a specified range of the current sensor;

determining an information utility function value that indicates an information quality for data available to the current sensor from each of the neighboring sensors, the indicated information quality based on a set of predefined information quality parameters;

determining an energy conservation function value that indicates at least one of power and bandwidth usage required to transmit data between the current sensor and each of the neighboring sensors;

determining a weighted sum of the information utility function value and the energy conservation function value;

applying the determined weighted sum to each of the neighboring sensor to generate a set of evaluation results;

adding a next sensor to the sequence of data path sensors, wherein the next sensor is selected from the selected set of neighboring sensors based on the set of evaluation results;

determining a new belief state for the next sensor based on the current belief state and information obtained by the current sensor; and

transmitting at least the new belief state to the next sensor.

24. A network comprising a plurality of nodes, each of the plurality of nodes comprising:

an objective function evaluating circuit, routine or application;

a next node selecting circuit, routine or application; and

a memory which stores neighboring nodes information and evaluation information for evaluating information gain and cost associated with data routing, wherein;

the objective function evaluating circuit, routine or application extracts the neighboring nodes information and the evaluation information from the memory in response to a query, and evaluates an objective function which balances between information gain and cost when routing the query to the neighboring nodes; and

the next node selecting circuit, routine or application selects a next node from the neighboring nodes based on the evaluation of the objective function.

35. A sensor for a sensor network, comprising:

a memory that stores neighboring sensor information and objective function evaluation information, the neighboring sensor information including sensor types and locations of neighboring sensors, the objective function evaluation information including parameters usable in balancing between information gain and costs regarding data routing;

an objective function evaluating circuit, routine or application that evaluates a trade-off between information gain available from each of the neighboring sensors and power and bandwidth requirements when carrying data from each of the neighboring sensors based on the stored objective function evaluation information; and

a next sensor selecting circuit, routine or application that selects a next sensor from the neighboring sensors based on results of the evaluation of the objective function.

36. A network comprising a plurality of nodes, each of the plurality of nodes comprising:

an objective function evaluating circuit, routine or application;

a next node selecting circuit, routine or application; and

a memory which stores continuing nodes information and evaluation information for evaluating information gain and cost associated with data routing, wherein;

the objective function evaluating circuit, routine or application extracts the continuing nodes information and the evaluation information from the memory in response to a query, and evaluates an objective function which balances between information gain and cost when routing the query to the continuing nodes; and

the next node selecting circuit, routine or application selects a next node from the continuing nodes based on the evaluation of the objective function.