Localization and routing in sensor networks by local angle information

ABSTRACT

Location information is useful both for network organization and for sensor data integrity. In this article, we study the anchor-free 2D localization problem by using local angle measurements. We prove that given a unit disk graph and the angles between adjacent edges, it is NP-hard to find a valid embedding in the plane such that neighboring nodes are within distance 1 from each other and non-neighboring nodes are at least distance &sqrt;2/2 away. Despite the negative results, however, we can find a planar spanner of a unit disk graph by using only local angles. The planar spanner can be used to generate a set of virtual coordinates that enable efficient and local routing schemes such as geographical routing or approximate shortest path routing. We also proposed a practical anchor-free embedding scheme by solving a linear program. We show by simulation that it gives both a good local embedding, with neighboring nodes embedded close and non-neighboring nodes far away, and a satisfactory global view such that geographical routing and approximate shortest path routing on the embedded graph are almost identical to those on the original (true) embedding.

REFERENCES

• 1: Aspnes, J., Goldenberg, D., and Yang, Y. R. 2004. On the computational complexity of sensor network localization. In Proceedings of the 1st International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), 32--44.
• 2: Pratik Biswas , Yinyu Ye, Semidefinite programming for ad hoc wireless sensor network localization, Proceedings of the 3rd international symposium on Information processing in sensor networks, April 26-27, 2004, Berkeley, California, USA [doi>10.1145/984622.984630]
• 3: Borg, I. and Groenen, P. 1997. Modern Multidimensional Scaling: Theory and Applications. Springer.
• 4: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, p.48-55, August 20-20, 1999, Seattle, Washington, United States [doi>10.1145/313239.313282]
• 5: 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]
• 6: Bryant, V. W. 1989. Straight line representation of planar graphs. Elem. Math. 44, 64--66.
• 7: 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]
• 8: Doherty, L., Ghaoui, L. E., and Pister, S. J. 2001. Convex position estimation in wireless sensor networks. In Proceedings of the Annual Joint Conference of the Computer and Communications Societies (IEEE Infocom), vol. 3. 1655--1663.
• 9: Efrat, A., Erten, C., Forrester, D., Iyer, A., and Kobourov, S. G. 2006. Force-Directed approaches to sensor localization. In Proceedings of the 8th Workshop on Algorithm Engineering and Experiments (ALENEX), 108--118.
• 10: Fáry, I. 1948. On straight line representations of planar graphs. Acta Scientiarum Mathematicarum (Szeged) 11, 229--233.
• 11: Jie Gao , Leonidas J. Guibas , John Hershberger , Li Zhang , An Zhu, Geometric spanner for routing in mobile networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501422.501424]
• 12: Cyril Gavoille , David Peleg , Stéphane Pérennes , Ran Raz, Distance labeling in graphs, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.210-219, January 07-09, 2001, Washington, D.C., United States
• 13: David K. Goldenberg , Pascal Bihler , Ming Cao , Jia Fang , Brian D. O. Anderson , A. Stephen Morse , Y. Richard Yang, Localization in sparse networks using sweeps, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161103]
• 14: Gotsman, C. and Koren, Y. 2004. Distributed graph layout for sensor networks. In Proceedings of the International Symposium on Grpah Drawing.
• 15: Hofmann-Wellenhof, B., Lichtenegger, H., and Collins, J. 2001. Global Positioning Systems: Theory and Practice, 5 ed. Springer.
• 16: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 17: 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]
• 18: Fabian Kuhn , Roger Wattenhofer , Yan Zhang , Aaron Zollinger, Geometric ad-hoc routing: of theory and practice, Proceedings of the twenty-second annual symposium on Principles of distributed computing, p.63-72, July 13-16, 2003, Boston, Massachusetts [doi>10.1145/872035.872044]
• 19: Fabian Kuhn , Aaron Zollinger, Ad-hoc networks beyond unit disk graphs, Proceedings of the 2003 joint workshop on Foundations of mobile computing, p.69-78, September 19, 2003, San Diego, CA, USA [doi>10.1145/941079.941089]
• 20: Li, X.-Y., Calinescu, G., and Wan, P.-J. 2002. Distributed construction of planar spanner and routing for ad hoc networks. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom), 1268--1277.
• 21: Zang Li , Wade Trappe , Yanyong Zhang , Badri Nath, Robust statistical methods for securing wireless localization in sensor networks, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 22: 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]
• 23: 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]
• 24: Niculescu, D. and Nath, B. 2001. Ad hoc positioning system (APS). In Proceedings of the IEEE Conference and Exhibition on Global Telecommunications (GlobeCom), 2926--2931.
• 25: Niculescu, D. and Nath, B. 2003. Ad hoc positioning system (APS) using AOA. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom), Vol. 22. 1734--1743.
• 26: 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]
• 27: 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]
• 28: Rajmohan Rajaraman, Topology control and routing in ad hoc networks: a survey, ACM SIGACT News, v.33 n.2, June 2002 [doi>10.1145/564585.564602]
• 29: Ananth Rao , Sylvia Ratnasamy , 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]
• 30: 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]
• 31: 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]
• 32: 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]
• 33: 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
• 34: Kamin Whitehouse , David Culler, A robustness analysis of multi-hop ranging-based localization approximations, Proceedings of the 5th international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127825]
• 35: Kamin Whitehouse , Chris Karlof , Alec Woo , Fred Jiang , David Culler, The effects of ranging noise on multihop localization: an empirical study, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 36: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]

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

General Terms:
Algorithms, Design, Theory

Keywords:
Sensor networks, embedding, geographical routing, localization, planar spanner subgraph, wireless networks