Robust distributed network localization with noisy range measurements

ABSTRACT

This paper describes a distributed, linear-time algorithm for localizing sensor network nodes in the presence of range measurement noise and demonstrates the algorithm on a physical network. We introduce the probabilistic notion of robust quadrilaterals as a way to avoid flip ambiguities that otherwise corrupt localization computations. We formulate the localization problem as a two-dimensional graph realization problem: given a planar graph with approximately known edge lengths, recover the Euclidean position of each vertex up to a global rotation and translation. This formulation is applicable to the localization of sensor networks in which each node can estimate the distance to each of its neighbors, but no absolute position reference such as GPS or fixed anchor nodes is available.

We implemented the algorithm on a physical sensor network and empirically assessed its accuracy and performance. Also, in simulation, we demonstrate that the algorithm scales to large networks and handles real-world deployment geometries. Finally, we show how the algorithm supports localization of mobile nodes.

REFERENCES

• 1: Bulusu, N., Heidemann, J., and Estrin, D. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7, 5 (October 2000), 28-34.
• 2: S. Capkun , M. Hamdi , J. Hubaux, GPS-Free Positioning in Mobile ad-hoc Networks, Proceedings of the 34th Annual Hawaii International Conference on System Sciences ( HICSS-34)-Volume 9, p.9008, January 03-06, 2001
• 3: Doherty, L., Pister, K. S. J., and Ghaoui, L. E. Convex position estimation in wireless sensor networks. In Proc. IEEE INFOCOM (Anchorage, AK, April 2001).
• 4: Eren, T., Goldenberg, D., Whiteley, W., Yang, Y. R., Morse, A. S., Anderson, B. D. O., and Belhumeur, P. N. Rigidity, computation, and randomization in network localization. In Proc. IEEE INFOCOM (March 2004).
• 5: Deborah Estrin , Ramesh Govindan , John Heidemann, Embedding the Internet: introduction, Communications of the ACM, v.43 n.5, p.38-41, May 2000 [doi>10.1145/332833.332836]
• 6: Grabowski, R., and Khosla, P. Localization techniques for a team of small robots. In Proc. IEEE IROS (Maui, Hawaii, October 2001).
• 7: Bruce Hendrickson, Conditions for unique graph realizations, SIAM Journal on Computing, v.21 n.1, p.65-84, Feb. 1992 [doi>10.1137/0221008]
• 8: Horn, B. K. P. Closed form solution of absolute orientation using unit quaternions. Journal of the Optical Society A 4, 4 (April 1987), 629--642.
• 9: Ji, X., and Zha, H. Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling. In Proc. IEEE INFOCOM (March 2004).
• 10: Laman, G. On graphs and rigidity of plane skeletal structures. J. Engineering Math 4 (1970), 331--340.
• 11: Nagpal, R., Shrobe, H., and Bachrach, J. Organizing a global coordinate system from local information on an ad hoc sensor network. In Proc. IPSN (Palo Alto, CA, April 2003), pp. 333--348.
• 12: Niculescu, D., and Nath, B. DV based positioning in ad hoc networks. Kluwer journal of Telecommunication Systems (2003), 267--280.
• 13: Dragoş Niculescu , Badri Nath, Error characteristics of ad hoc positioning systems (aps), Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989463]
• 14: Patwari, N., III, A. O. H., Perkins, M., Correal, N. S., and O'Dea, R. J. Relative location estimation in wireless sensor networks. IEEE Trans. Signal Process. 51, 8 (August 2003), 2137--2148.
• 15: Priyantha, N. B., Balakrishnan, H., Demaine, E., and Teller, S. Anchor-free distributed localization in sensor networks. Tech. Rep. 892, MIT Lab. for Comp. Sci., April 2003.
• 16: Nissanka B. Priyantha , Anit Chakraborty , Hari Balakrishnan, The Cricket location-support system, Proceedings of the 6th annual international conference on Mobile computing and networking, p.32-43, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345917]
• 17: Chris Savarese , Jan M. Rabaey , Koen Langendoen, Robust Positioning Algorithms for Distributed Ad-Hoc Wireless Sensor Networks, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.317-327, June 10-15, 2002
• 18: Savvides, A., Garber, W., Adlakha, S., Moses, R., and Srivastava, M. B. On the error characteristics of multihop node localization in ad-hoc sensor networks. In Proc. IPSN (Palo Alto, CA, April 2003), pp. 317--332.
• 19: Andreas Savvides , Chih-Chieh Han , Mani B. Strivastava, Dynamic fine-grained localization in Ad-Hoc networks of sensors, Proceedings of the 7th annual international conference on Mobile computing and networking, p.166-179, July 2001, Rome, Italy [doi>10.1145/381677.381693]
• 20: Saxe, J. B. Embeddability of weighted graphs in k-space is strongly NP-hard. In Proc. 17th Allerton Conf. Commun. Control Comput. (1979), pp. 480--489.
• 21: Simic, S. N., and Sastry, S. Distributed localization in wireless ad hoc networks. Tech. Rep. UCB/ERL M02/26, UC Berkeley, December 2001.
• 22: Adam Smith , Hari Balakrishnan , Michel Goraczko , Nissanka Priyantha, Tracking moving devices with the cricket location system, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990088]
• 23: Seth Teller , Jiawen Chen , Hari Balakrishnan, Pervasive Pose-Aware Applications and Infrastructure, IEEE Computer Graphics and Applications, v.23 n.4, p.14-18, July 2003 [doi>10.1109/MCG.2003.1210859]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

General Terms:
Algorithms, Design, Experimentation

Keywords:
localization, location-awareness, mobility, pervasive computing, sensor networks, tracking