Systems and methods for constrained anisotropic diffusion routing within an ad hoc network
First Claim
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.
10 Assignments
0 Petitions
Accused Products
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.
-
Citations
36 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
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. - View Dependent Claims (25, 26, 27, 28, 29, 30, 31, 32, 33, 34)
-
-
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.
-
Specification