SCALABLE SENSOR LOCALIZATION FOR WIRELESS SENSOR NETWORKS

• US 20070005292A1
• Filed: 06/21/2006
• Published: 01/04/2007
• Est. Priority Date: 06/22/2005
• Status: Active Grant

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: JIN, HOLLY
• Granted Patent: US 7,970,574 B2
• Time in Patent Office: Days
• US Class Current: 702/150
• CPC Class Codes: G01S 5/0289 of multiple transceivers, e.g. in ad hoc networks
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Adaptive rule-based methods to solve localization problems for ad hoc wireless sensor networks are disclosed. A large problem may be solved as a sequence of very small subproblems, each of which is solved by semidefinite programming relaxation of a geometric optimization model. The subproblems may be generated according to a set of sensor/anchor selection rules and a priority list. The methods scale well and provide improved positioning accuracy. A dynamic version may be used for estimating moving sensors locations in a real-time environment. The method may use dynamic distance measurement updates among sensors, and utilizes subproblem solving for static sensor localization. Methods to deploy sensor localization algorithms in clustered distributed environments are also provided, permitting application to arbitrarily large networks. In addition, the methods may be used to solve sensor localizations in 2D or 3D space. A preprocessor may be used for localization of networks without absolute position information.

Claims

1. A method for estimating locations of wireless sensors in a wireless sensor network, the method comprising the acts of:

obtaining pair-wise distance measurements between a sensor whose location is unknown and an anchor sensor whose location is known and between sensors whose locations are unknown;

formulating a subproblem to include a subset of anchor sensors whose locations are known and to further include a subset of sensors whose locations are unknown;

determining a location of at least one of the sensors in the subset of sensors within a tolerable error by solving the subproblem using a semidefinite programming relaxation;

classifying the at least one sensor whose location has been determined within a tolerable error as a new anchor sensor; and

iteratively repeating the acts of formulating, determining, and classifying.

2. The method as claimed in claim 1, wherein the act of formulating the subproblem comprises the acts of:

selecting one or more candidates for the subset of sensors; and

prioritizing each of the candidates based on a type of anchor sensor to which the candidate is relatively localized.

3. The method as claimed in claim 1, wherein the act of formulating the subproblem comprises the acts of:

selecting one or more candidates for the subset of anchor sensors; and

prioritizing each of the candidates based on shortness of the distance measurements.

4. The method as claimed in claim 1, further comprising the act of:

setting a maximum number of sensors to be included in the subset of sensors.

5. The method as claimed in claim 1, wherein the sensors are static.

6. The method as claimed in claim 1, wherein the sensors are located within a two-dimensional space.

7. The method as claimed in claim 1, wherein the wireless sensor network comprises at least 1,000 sensors.

8. The method as claimed in claim 1, wherein the wireless sensor network comprises at least 10,000 sensors.

9. The method as claimed in claim 1, wherein the act of determining a location of at least one of the sensors in the subset of sensors by solving the subproblem using the semidefinite programming relaxation comprises solving the following model:

$\mathrm{minimize}<br><br>\underset{\left(\mathrm{ij}\right)\in <br><br>N_1}{\sum <br><br>}<br><br>\left({\mathrm{\alpha <br><br>}}_{\mathrm{ij}}^{+}+{\mathrm{\alpha <br><br>}}_{\mathrm{ij}}^{-}\right)+\underset{\left(i,k\right)\in <br><br>N_2}{\sum <br><br>}<br><br>\left({\mathrm{\alpha <br><br>}}_{\mathrm{ik}}^{+}+{\mathrm{\alpha <br><br>}}_{\mathrm{ik}}^{-}\right)$ $\mathrm{subject}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{to}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{diag}<br><br>\left(A_I^T<br><br>{\mathrm{ZA}}_I\right)=b_I,<br><br>{\left(\begin{array}{c}{e}_{\mathrm{ij}}\\ 0\end{array}\right)}^T<br><br>Z<br><br>\left(\begin{array}{c}{e}_{\mathrm{ij}}\\ 0\end{array}\right)-{\mathrm{\alpha <br><br>}}_{\mathrm{ij}}^{+}+{\mathrm{\alpha <br><br>}}_{\mathrm{ij}}^{-}={\left({\hat{d}}_{\mathrm{ij}}\right)}^2<br><br>\forall <br><br>\left(i,j\right)\in <br><br>N_1,<br><br>{\left(\begin{array}{c}{e}_i\\ -a_k\end{array}\right)}^T<br><br>Z<br><br>\left(\begin{array}{c}{e}_i\\ -a_k\end{array}\right)-{\mathrm{\alpha <br><br>}}_{\mathrm{ik}}^{+}+{\mathrm{\alpha <br><br>}}_{\mathrm{ik}}^{-}={\left({\hat{d}}_{\mathrm{ik}}\right)}^2<br><br>\forall <br><br>\left(i,k\right)\in <br><br>N_2,<br><br>{\left(\begin{array}{c}{e}_{\mathrm{ij}}\\ 0\end{array}\right)}^T<br><br>Z<br><br>\left(\begin{array}{c}{e}_{\mathrm{ij}}\\ 0\end{array}\right)\ge <br><br>r_{\mathrm{ij}}^2<br><br>\forall <br><br>\left(i,j\right)\in <br><br>{\stackrel{\_}{N}}_1,<br><br>{\left(\begin{array}{c}{e}_i\\ -a_k\end{array}\right)}^T<br><br>Z<br><br>\left(\begin{array}{c}{e}_{\mathrm{ij}}\\ 0\end{array}\right)\ge <br><br>r_{\mathrm{ik}}^2<br><br>\forall <br><br>\left(i,k\right)\in <br><br>{\stackrel{\_}{N}}_2,<br><br>Z\ge <br><br>0,{\mathrm{\alpha <br><br>}}_{\mathrm{ij}}^{+},{\mathrm{\alpha <br><br>}}_{\mathrm{ij}}^{-},{\mathrm{\alpha <br><br>}}_{\mathrm{ik}}^{+},{\mathrm{\alpha <br><br>}}_{\mathrm{ik}}^{-}\ge <br><br>0,<br><br>i,j=1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},s,<br><br>k=s+1,\mathrm{\dots <br><br>}<br><br>\text{\hspace{1em}<br><br>},n,$

wherein S represents how many sensors have unknown locations;

wherein n represents how many total sensors are in the network;

wherein X=(x₁ x₂ . . . x_s) comprises a 2×

s matrix to be determined;

wherein {circumflex over (d)}_ij represents a distance measurement between sensor i whose location is unknown and sensor j whose location is unknown;

wherein {circumflex over (d)}_ik represents a distance measurement between sensor i whose location is unknown and anchor sensor k whose location is known;

wherein 2n+n(n+1)/2 pair-wise distance measurements exist;

wherein N₁={(i,j) with known {circumflex over (d)}_ij and i<

j};

wherein N₁={(i,j) with unknown {circumflex over (d)}_ij and i<

j};

wherein N₂={(i, k) with known {circumflex over (d)}_ik};

wherein N₂={(i, k) with unknown {circumflex over (d)}_ik};

wherein α

_ij represents a squared Euclidean distance ∥

x_i−

x_j∥

² from sensor i to sensor j;

wherein r_ij represents the range within which sensor i and sensor j can detect each other;

wherein r_ik represents the range within which sensor i and anchor sensor k can detect each other;

wherein α

_ik represents a difference between ({circumflex over (d)}_ik)² and ∥

x_i−

a_k∥

² from sensor i to anchor sensor k;

wherein e_ij comprises a zero column vector except for 1 in location i and −

1 in location, such that ∥

x_i−

x_j∥

² e_ij^TX^T Xe_ij;

wherein e_i comprises a zero column vector except for 1 in location i, such that

${<br><br>x_i-a_k<br><br>}^2={\left(\begin{array}{c}{e}_i\\ -a_j\end{array}\right)}^T<br><br>{\left(X<br><br>\text{\hspace{1em}<br><br>}<br><br>I\right)}^T<br><br>\left(X<br><br>\text{\hspace{1em}<br><br>}<br><br>I\right)<br><br>\left(\begin{array}{c}{e}_i\\ -a_k\end{array}\right);<br><br>$

wherein Y is defined to be X^T X;

wherein

$A_I=\left(\begin{array}{ccc}0& 0& 0\\ 1& 0& 1\\ 0& 1& 1\end{array}\right);<br><br>$

wherein

$b_I=\left(\begin{array}{c}1\\ 1\\ 2\end{array}\right);<br><br>$

wherein

$Z_1\equiv <br><br>\left(\begin{array}{cc}Y& X^T\\ X& I\end{array}\right)\succcurlyeq <br><br>0;<br><br>$

and

wherein the solution is given by

$\stackrel{\_}{Z}=\left(\begin{array}{cc}\stackrel{\_}{Y}& {\stackrel{\_}{X}}^T\\ \stackrel{\_}{X}& I\end{array}\right).$

10. The method as claimed in claim 1, wherein the act of determining a location of at least one of the sensors in the subset of sensors by solving the subproblem using the semidefinite programming relaxation comprises the act of:

if pair-wise distance measurements between one of the sensors and less than three anchor sensors are known, considering a location of a neighboring anchor sensor whose distance measurement to one of the other anchor sensors is known.

11. The method as claimed in claim 1, wherein the act of determining a location of at least one of the sensors in the subset of sensors by solving the subproblem using the semidefinite programming relaxation comprises the acts of:

if a first distance measurement between one of the sensors and a first anchor sensor is known, and a second distance measurement between said sensor and a second anchor sensor is unknown, considering a location of a neighboring anchor sensor whose distance measurement to the first anchor is known; and

locating said sensor at a middle point between two points at which a first circle representing a radio range of the first anchor sensor intersects with a second circle representing a radio range of the neighboring anchor sensor.

12. The method as claimed in claim 1, wherein at least one of the sensors is moving.

13. The method as claimed in claim 12, further comprising the acts of:

iteratively repeating the following acts at each tracking instant in a plurality of tracking instants;

identifying static sensors;

identifying dynamic sensors;

updating a distance matrix {circumflex over (d)},

wherein

$\hat{d}=\left(\begin{array}{cc}\mathrm{DIST}<br><br>\text{\hspace{1em}<br><br>}<br><br>11& \mathrm{m\_distance}\\ {\mathrm{m\_distance}}^{\mathrm{\prime <br><br>}}& \mathrm{DIST}<br><br>\text{\hspace{1em}<br><br>}<br><br>22\end{array}\right);<br><br>$

wherein DIST11 represents an s by s matrix representing distance measurements among s dynamic sensors;

wherein m_distance represents an s by m matrix representing distance measurements among s dynamic sensors with m static sensors; and

wherein DIST22 represents an m by m matrix representing distance measurements among m static sensors;

formulating an updated subproblem model based on the static sensors, dynamic sensors, and updated {circumflex over (d)}; and

obtaining locations of the dynamic sensors by solving the updated subproblem.

14. The method as claimed in claim 13 wherein the act of identifying dynamic sensors comprises the act of:

detecting a distance change between two tracking instants.

15. The method as claimed in claim 1, further comprising the acts of:

partitioning the network into a plurality of clusters;

determining a priority for each of the clusters; and

determining locations of sensors in each of the clusters,

wherein clusters of different priorities are localized sequentially in order of priority, and

wherein clusters of equal priorities are localized substantially in parallel.

16. The method as claimed in claim 15, wherein the act of determining a priority for each of the clusters is based on total number of anchor sensors in each cluster.

17. The method as claimed in claim 15, wherein the act of determining a priority for each of the clusters is based on priority for a neighboring cluster.

18. The method as claimed in claim 15, wherein the act of determining a priority for each of the clusters is based on total number of anchor sensors in each neighboring cluster.

19. The method as claimed in claim 15, wherein each sensor is included in only one cluster and wherein each cluster comprises a cluster head.

20. The method as claimed in claim 1, wherein the sensors are located within a three-dimensional space.

21. The method as claimed in claim 20, wherein the act of determining a location of at least one of the sensors in the subset of sensors by solving the subproblem using the semidefinite programming relaxation comprises the act of:

if pair-wise distance measurements between one of the sensors and less than four anchor sensors are known, considering a location of a neighboring anchor sensor whose distance measurement to one of the other anchor sensors is known.

23. A machine-readable medium having machine-executable instructions for performing the method recited in claim 1.

22. A method for estimating relative locations of wireless sensors in a wireless sensor network, wherein no absolute locations are known, the method comprising the acts of:

for each sensor in the network, obtaining a pair-wise distance measurement between each sensor and a neighboring sensor;

selecting a first surrogate anchor sensor having a greatest number of known distance measurements to other sensors;

selecting a second surrogate anchor sensor,

wherein a distance between the second surrogate anchor sensor and the first surrogate anchor sensor is known,

wherein a distance between the second surrogate anchor sensor and a third sensor is known,

wherein a distance between the first surrogate anchor sensor and the third sensor is known, and

wherein the second surrogate anchor sensor, the second surrogate anchor sensor, and the third sensor are not in a straight line;

selecting the third sensor as the third surrogate anchor;

assigning a location to the first surrogate anchor sensor;

determining a location of the second surrogate anchor sensor;

determining a location of the third surrogate anchor sensor;

formulating a subproblem to include the anchor sensors whose locations are known and to further include a subset of sensors whose locations are unknown;

determining a location of at least one of the sensors in the subset of sensors by solving the subproblem using a semidefinite programming relaxation;

classifying the at least one sensor whose location has been determined within a tolerable error as an anchor sensor; and

iteratively repeating the acts of formulating a subproblem, determining a location of at least one of the subset of sensors, and classifying the at least one sensor whose location has been determined.

24. A machine-readable medium having machine-executable instructions for performing the method recited in claim 22.

25. A wireless sensor network comprising:

a plurality of nodes, comprising sensors with unknown locations and anchor sensors with known locations,

wherein each node comprises a network interface operable to exchange data with one or more other nodes; and

a control station operable to communicate with one or more nodes,

wherein the control station is operable to determine at least one distance between two sensors whose locations are unknown,

wherein the control station is operable to determine at least one distance between one of the sensors whose location is unknown and one of the anchor sensors whose location is known, and

wherein the control station comprises a control module operable to iteratively repeat the following acts;

formulate a subproblem to include a subset of anchor sensors whose locations are known and to further include a subset of sensors whose locations are unknown;

determine locations of at least one of the sensors in the subset of sensors by solving the subproblem using a semidefinite programming relaxation; and

classify the at least one sensor whose location has been determined within a tolerable error as a new anchor sensor.