Back to results
US 7,925,730 B1Granted
Localization for sensor networks
AssigneeAT&T Intellectual Property II, L.P.
InventorsCraig Gotsman, Yehuda Koren
Life of this patent
Estimating the term…
Abstract
A method and system for sensor network localization including communicating with a plurality of directly neighboring sensor nodes to determine a patch in a sensor network, localizing the patch, generating a system of equations from computed local coordinates of the patch, incorporating global coordinates of a plurality of sensor nodes into the system of equations, and solving the equations using a distributed equation solver is described. The described methods and systems have utility in the arts of military, radio, police, fire, rescue, business, travel, and other diverse applications.
Claims11
A method for localization of a sensor network comprising:
- communicating with a plurality of neighboring sensor nodes of a plurality of sensor nodes to determine a patch in the sensor network including determining original distances between a portion of the plurality of neighboring sensor nodes, wherein a location of each of the plurality of sensor nodes in the sensor network is unknown;
- localizing the patch, the localizing comprising:
- estimating missing distances within the patch,
- computing coordinates of the patch using multidimensional scaling, and
- refining a result of the computing using stress minimization based only on the original distances;
- generating a system of equations from the coordinates of the patch to merge the patch with other patches to create a layout of the sensor network, wherein the system of equations comprises:
- patch-induced equations comprising first coordinates of each of the plurality of sensor nodes of the patch expressed in a global layout as an affine combination of second coordinates of the neighboring sensor nodes of each of the plurality of sensor nodes, and
- anchor-induced equations comprising the first coordinates of a set of the plurality of sensor nodes for which the location of each of the set of the plurality of sensor nodes is unknown and is inferred, wherein the location of each of the set of the plurality of sensor nodes is inferred by determining a largest clique in the sensor network and localizing the largest clique using a multidimensional scaling technique so as to adopt the set of the plurality of sensor nodes in the clique as anchors;
- and
- solving the system of equations using a distributed equation solver to compute the layout of the sensor network including global coordinates of each of the plurality of sensor nodes in the sensor network.
7 more elements
A plurality of sensor nodes communicably linked in a sensor network, each of the sensor nodes being configured to:
- communicate with a plurality of directly neighboring sensor nodes of the plurality of sensor nodes to determine a patch in the sensor network including determining original distances between a portion of the plurality of directly neighboring sensor nodes, wherein a location of each of the plurality of sensor nodes in the sensor network is unknown;
- localize the patch by estimating missing distances within the patch, computing coordinates of the patch using multidimensional scaling, and refining a result of the computing using stress minimization based only on the original distances;
- generate a system of equations from the coordinates of the patch to merge the patch with other patches to create a layout of the sensor network, wherein the system of equations comprises:
- patch-induced equations comprising first coordinates of each of the plurality of sensor nodes expressed in a global layout as an affine combination of second coordinates of the directly neighboring sensor nodes of each of the plurality of sensor nodes, and
- anchor-induced equations comprising the first coordinates of a set of the plurality of sensor nodes for which the location of each of the set of the plurality of sensor nodes is unknown and is inferred, wherein the location of each of the set of the plurality of sensor nodes is inferred by determining a largest clique in the sensor network and localizing the largest clique using a multidimensional scaling technique so as to adopt the set of the plurality of sensor nodes in the clique as anchors;
- and
- solve the system of equations using a distributed equation solver to compute the layout of the sensor network including global coordinates of each of the plurality of sensor nodes in the sensor network.
4 more elements
A non-transitory computer readable medium, the computer readable medium containing instruction stored thereon for execution by a computer the instructions including:
- communicating with a plurality of directly neighboring sensor nodes of a plurality of sensor nodes to determine a patch in a sensor network including determining original distances between a portion of the plurality of directly neighboring sensor nodes, wherein a location of each of the plurality of sensor nodes in the sensor network is unknown;
- localizing the patch, the localizing comprising:
- estimating missing distances within the patch,
- computing coordinates of the patch using multidimensional scaling, and
- refining a result of the computing using stress minimization based only on the original distances;
- generating a system of equations from the coordinates of the patch to merge the patch with other patches to create a layout of the sensor network, wherein the system of equations comprises:
- patch-induced equations comprising first coordinates of each of the plurality of sensor nodes expressed in a global layout as an affine combination of second coordinates of the directly neighboring sensor nodes of each of the plurality of sensor nodes, and
- anchor-induced equations comprising the first coordinates of a set of the plurality of sensor nodes for which the location of each of the set of the plurality of sensor nodes is unknown and is inferred, wherein the location of each of the set of the plurality of sensor nodes is inferred by determining a largest clique in the sensor network and localizing the largest clique using a multidimensional scaling technique so as to adopt the set of the plurality of sensors in the clique as anchors;
- and
- solving the system of equations using a distributed equation solver to compute the layout of the sensor network including global coordinates of each of the plurality of sensor nodes in the sensor network.
7 more elements
Dependencies are inferred from the claim text.