Distributed localization using noisy distance and angle information

ABSTRACT

Localization is an important and extensively studied problem in ad-hoc wireless sensor networks. Given the connectivity graph of the sensor nodes,along with additional local information (e.g. distances, angles, orientations etc.), the goal is to reconstruct the global geometry of the network. In this paper, we study the problem of localization with noisy distance and angle information. With no noise at all, the localization problem with both angle (with orientation) and distance information is trivial. However, in the presence of even a small amount of noise, we prove that the localization problem is NP hard.Localization with accurate distance information and relative angle information is also hard. These hardness results motivate our study of approximation schemes. We relax the non-convex constraints to approximating convex constraints and propose linear programs (LP) for two formulations of the resulting localization problem, which we call the weak deployment and strong deployment problems.These two formulations give upper and lower bounds on the location uncertainty respectively: No sensor is located outside its weak deployment region, and each sensor can be anywhere in its strong deployment region without violating the approximate distance and angle constraints. Though LP-based algorithms are usually solved by centralized methods, we propose distributed, iterative methods, which are provably convergent to the centralized algorithm solutions. We give simulation results for the distributed algorithms, evaluating the convergence rate, dependence on measurement noises,and robustness to link dynamics.

REFERENCES

• 1: J. Aspnes, D. Goldenberg, and Y. R. Yang. On the computational complexity of sensor network localization. In Proc. 1st Internat. Workshop on Algorithmic Aspects of Wireless Sensor Networks pages 32--44,2004.
• 2: 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]
• 3: Heinz Breu , David G. Kirkpatrick, Unit disk graph recognition is NP-hard, Computational Geometry: Theory and Applications, v.9 n.1-2, p.3-24, Jan. 1998 [doi>10.1016/S0925-7721(97)00014-X]
• 4: Jehoshua Bruck , Jie Gao , Anxiao (Andrew) Jiang, Localization and routing in sensor networks by local angle information, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062713]
• 5: Mihai Bǎdoiu , Erik D. Demaine , Mohammad Taghi Hajiaghayi , Piotr Indyk, Low-dimensional embedding with extra information, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997866]
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: L. Doherty, L. E. Ghaoui, and S. J. Pister. Convexposition estimation in wireless sensor networks. In Proc. IEEE INFOCOM vol 3,pages 1655--1663, 2001.
• 8: C. Gotsman and Y. Koren. Distributed graph layout for sensor networks. In Proc. Internat. Symposium on Grpah Drawing pages 273--284,2004.
• 9: Saikat Guha , Rohan Murty , Emin Gün Sirer, Sextant: a unified node and event localization framework using non-convex constraints, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062715]
• 10: Tian He , Chengdu Huang , Brian M. Blum , John A. Stankovic , Tarek Abdelzaher, Range-free localization schemes for large scale sensor networks, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938995]
• 11: B. Hofmann-Wellenhof, H. Lichtenegger,and J. Collins. Global Positioning Systems: Theory and Practice Springer, 5th ed., 2001.
• 12: Fabian Kuhn , Thomas Moscibroda , Roger Wattenhofer, Unit disk graph approximation, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022634]
• 13: 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]
• 14: Thomas Moscibroda , Regina O'Dell , Mirjam Wattenhofer , Roger Wattenhofer, Virtual coordinates for ad hoc and sensor networks, Proceedings of the 2004 joint workshop on Foundations of mobile computing, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1022630.1022633]
• 15: D. Niculescu and B. Nath. Ad hoc positioning system (APS).In Proc. IEEE GLOBECOM pages 2926--2931, 2001.
• 16: D. Niculescu and B. Nath. Ad hoc positioning system (APS)using AOA. In Proc. IEEE INFOCOM vol 22(1), pages 1734--1743, 2003.
• 17: 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]
• 18: R. O'Dell , R. Wattenhofer, Theoretical aspects of connectivity-based multi-hop positioning, Theoretical Computer Science, v.344 n.1, p.47-68, 11 November 2005 [doi>10.1016/j.tcs.2005.06.026]
• 19: N. B. Priyantha, H. Balakrishnan, E. D. Demaine, and S. Teller. Mobile-assisted localization in wireless sensor networks. In Proc. INFOCOM 2005.
• 20: 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]
• 21: Ananth Rao , Christos Papadimitriou , Scott Shenker , Ion Stoica, Geographic routing without location information, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938996]
• 22: 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]
• 23: 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]
• 24: Yi Shang , Wheeler Ruml , Ying Zhang , Markus P. J. Fromherz, Localization from mere connectivity, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778439]
• 25: Anthony Man-Cho So , Yinyu Ye, Theory of semidefinite programming for sensor network localization, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design, Theory

Keywords:
linear programming, localization, sensor networks