Robust distributed node localization with error management

ABSTRACT

Location knowledge of nodes in a network is essential for many tasks such as routing, cooperative sensing, or service delivery in ad hoc, mobile, or sensor networks. This paper introduces a novel iterative method ILS for node localization starting with a relatively small number of anchor nodes in a large network. At each iteration, nodes are localized using a least-squares based algorithm. The computation is lightweight, fast, and any-time. To prevent error from propagating and accumulating during the iteration, the error control mechanism of the algorithm uses an error registry to select nodes that participate in the localization, based on their relative contribution to the localization accuracy. Simulation results have shown that the active selection strategy significantly mitigates the effect of error propagation. The algorithm has been tested on a network of Berkeley Mica2 motes with ultrasound TOA ranging devices. We have compared the algorithm with more global methods such as MDS-MAP and SDP-based algorithm both in simulation and on real hardware. The iterative localization achieves comparable location accuracy in both cases, compared to the more global methods, and has the advantage of being fully decentralized.

REFERENCES

• 1: N. Bulusu, J. Heidemann, and D. Estrin, "Gps-less low cost outdoor localization for very small devices," IEEE Personal Communications Magazine vol.7, pp.28--34, October 2000.
• 2: Andreas Savvides , Heemin Park , Mani B. Srivastava, The n-hop multilateration primitive for node localization problems, Mobile Networks and Applications, v.8 n.4, p.443-451, August 2003 [doi>10.1023/A:1024544032357]
• 3: Yi Shang , Wheeler Ruml , Ying Zhang , Markus Fromherz, Localization from Connectivity in Sensor Networks, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.961-974, November 2004 [doi>10.1109/TPDS.2004.67]
• 4: L. Doherty, K. S. J. Pister, and L. E. Ghaoui, "Convex position estimation in wireless sensor networks," in Proceedings of IEEE Infocom vol.3, pp.1655--1663, April 2001.
• 5: Pratik Biswas , Yinyu Ye, Semidefinite programming for ad hoc wireless sensor network localization, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984630]
• 6: Xuanlong Nguyen , Michael I. Jordan , Bruno Sinopoli, A kernel-based learning approach to ad hoc sensor network localization, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.134-152, August 2005 [doi>10.1145/1077391.1077397]
• 7: D. Niculescu and B. Nath, "Ad hoc positionin system (APS)," in GLOBECOM (1),pp. 2926--2931,2001.
• 8: 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
• 9: L. Kleinrock and J. Silvester, "Optimum transmission radii for packet radio networks or why six is a manic number," in Proc. IEEE National Telecommunications Conference pp.4.3.1 .4.3.5, 1978.
• 10: David Moore , John Leonard , Daniela Rus , Seth Teller, Robust distributed network localization with noisy range measurements, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031502]
• 11: H. Lim and J. Hou, "Localization for anisotropic sensor networks,"in Proc. IEEE InfoComm05 (Miami,FL), 2005.
• 12: Y. Zhang, M. Yim, L. Ackerson, D. Duff, and C. Eldershaw, "Stam: A system of trackin and mapping in real environments," IEEE, Wireless Communications Magazine December 2004.
• 13: Jose A. Costa , Neal Patwari , Alfred O. Hero, III, Distributed weighted-multidimensional scaling for node localization in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.2 n.1, p.39-64, February 2006 [doi>10.1145/1138127.1138129]
• 14: Laurent El Ghaoui , Hervé Lebret, Robust Solutions to Least-Squares Problems with Uncertain Data, SIAM Journal on Matrix Analysis and Applications, v.18 n.4, p.1035-1064, Oct. 1997 [doi>10.1137/S0895479896298130]
• 15: H. Hindi and S. Boyd, "Robust solutions to l 1 ,l 2 ,and l 8uncertain linear approximation problems using convex optimization,"in Proceedings of the American Control Conference vol.6,pp.3487--3491,1998.
• 16: K. Whitehouse, "Calamari: A localization system for sensor networks,"2003. http://www.cs.berkeley.edu/kamin/calamari.
• 17: Alexander T. Ihler , John W. Fisher, III , Randolph L. Moses , Alan S. Willsky, Nonparametric belief propagation for self-calibration in sensor networks, Proceedings of the third international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984656]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms

Keywords:
ad hoc network, formation, self localization, sensor network, target localization