Localization in sparse networks using sweeps

ABSTRACT

Determining node positions is essential for many next-generation network functionalities. Previous localization algorithms lack correctness guarantees or require network density higher than required for unique localizability. In this paper, we describe a class of algorithms for fine-grained localization called Sweeps. Sweeps correctly finitely localizes all nodes in bilateration networks. Sweeps also handles angle measurements and noisy measurements. We demonstrate the practicality of our algorithm through extensive simulations on a large number of networks, upon which it consistently localizes one-thousand-node networks of average degree less than five in less than two minutes on a consumer PC.

REFERENCES

• 1: Recursive Position Estimation in Sensor Networks, Proceedings of the Ninth International Conference on Network Protocols, p.35, November 11-14, 2001
• 2: B. Anderson, P. Belhumeur, T. Eren, D. Goldenberg, A. Morse, W. Whiteley, and Y. R. Yang. Global properties of easily localizable sensor networks. Preprint Australian National University, 2005.
• 3: James Aspnes , Tolga Eren , David K. Goldenberg , A. Stephen Morse , Walter Whiteley , Yang Richard Yang , Brian D. O. Anderson , Peter N. Belhumeur, A Theory of Network Localization, IEEE Transactions on Mobile Computing, v.5 n.12, p.1663-1678, December 2006 [doi>10.1109/TMC.2006.174]
• 4: J. Aspnes, D. Goldenberg, and Y. R. Yang. On the computational complexity of sensor network localization. In Proceedings of the First International Workshop on Algorithmic Aspects of Wireless Sensor Networks, Turku, Finland, July 2004.
• 5: P. Bahl and V. N. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In Proceedings of IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000.
• 6: Bonnie Berger , Jon Kleinberg , Tom Leighton, Reconstructing a three-dimensional model with arbitrary errors, Journal of the ACM (JACM), v.46 n.2, p.212-235, March 1999 [doi>10.1145/301970.301972]
• 7: P. Biswas, T.-C. Liang, K.-C. Toh, T.-C. Wang, and Y. Ye. Semidefinite programming approaches to sensor network localization with noisy distance measurements. IEEE Transactions on Automation Science and Engineering, 2006.
• 8: 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]
• 9: N. Bulusu, J. Heidemann, and D. Estrin. GPS-less low-cost outdoor localization for very small devices. IEEE Personal Communications Magazine, 7(5):28--34, Oct. 2000.
• 10: 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
• 11: K. Chintalapudi, R. Govindan, G. Sukhatme, and A. Dhariwal. Ad-hoc localization using ranging and sectoring. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.
• 12: Jorge Cortés , Francesco Bullo, Coordination and Geometric Optimization via Distributed Dynamical Systems, SIAM Journal on Control and Optimization, v.44 n.5, p.1543-1574, 2005 [doi>10.1137/S0363012903428652]
• 13: L. Doherty, K. S. J. Pister, and L. E. Ghaoui. Convex position estimation in wireless sensor networks. In Proceedings of IEEE INFOCOM, Anchorage, AK, Apr. 2001.
• 14: T. Eren, D. Goldenberg, W. Whiteley, Y. R. Yang, A. S. Morse, B. D. O. Anderson, and P. N. Belhumeur. Rigidity, computation, and randomization in network localization. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.
• 15: J. Fang, M. Cao, A. S. Morse, and B. D. O. Anderson. Localization of sensor networks using Sweeps. In Proceedings of the IEEE Conference on Decision and Control, San Diego, CA, Dec. 2006.
• 16: J. Fang, M. Cao, A. S. Morse, and B. D. O. Anderson. Sequential localization of networks. In Proceedings of Seventeenth International Symposium on Mathematical Theory of Networks and Systems, Kyoto, Japan, July 2006.
• 17: D. Goldenberg, A. Krishnamurthy, W. Maness, Y. R. Yang, A. Young, A. S. Morse, A. Savvides, and B. D. O. Anderson. Network localization in partially localizable networks. In Proceedings of IEEE INFOCOM, Miami, FL, Apr. 2005.
• 18: Andreas Haeberlen , Eliot Flannery , Andrew M. Ladd , Algis Rudys , Dan S. Wallach , Lydia E. Kavraki, Practical robust localization over large-scale 802.11 wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023728]
• 19: 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]
• 20: Lingxuan Hu , David Evans, Localization for mobile sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023726]
• 21: X. Ji and H. Zha. Sensor positioning in wireless ad-hoc sensor networks with multidimensional scaling. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.
• 22: G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 4:331--340, 2002.
• 23: Koen Langendoen , Niels Reijers, Distributed localization in wireless sensor networks: a quantitative comparison, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.43 n.4, p.499-518, 15 November 2003 [doi>10.1016/S1389-1286(03)00356-6]
• 24: H. Lim and J. Hou. Localization for anisotropic sensor networks. In Proceedings of IEEE INFOCOM,Miami,FL, Apr. 2005.
• 25: H. Lim, L. Kung, J. Hou, and H. Luo. Zero-configuration, robust indoor localization: theory and experimentation. In Proceedings of IEEE INFOCOM, Barcelona, Spain, Apr. 2006.
• 26: J. Lin, A. S. Morse, and B. D. O. Anderson. The multi-agent rendezvous problem - The asynchronous case. In Proceedings of the 43rd IEEE Conference on Decision and Control, Paradise Island, Bahamas, 2004.
• 27: J. McLurkin and J. Smith. Distributed algorithms for dispersion in indoor environments using a swarm of autonomous mobile robots. In Proceedings of Distributed Autonomous Robotic Systems Conference, 2004.
• 28: 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]
• 29: D. Niculescu and B. Nath. Ad-hoc positioning system. In Proceedings of IEEE Globecom, San Antonio, TX, Nov. 2001.
• 30: D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AOA. In Proceedings of IEEE INFOCOM,San Francisco, CA, Apr. 2003.
• 31: Dragoş Niculescu , Badri Nath, VOR base stations for indoor 802.11 positioning, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023727]
• 32: N. Priyantha, H. Balakrishnan, E. Demaine, and S. Teller. Mobile-assisted localization in wireless sensor networks. In Proceedings of IEEE INFOCOM, Miami, FL, Apr. 2005.
• 33: 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]
• 34: 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
• 35: 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]
• 36: Y. Shang and W. Ruml. Improved MDS-based localization. In Proceedings of IEEE INFOCOM, Hong Kong, Apr. 2004.
• 37: 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]
• 38: Radu Stoleru , Tian He , John A. Stankovic , David Luebke, A high-accuracy, low-cost localization system for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098921]
• 39: C. Wang and L. Xiao. Locating sensors in concave environments. In Proceedings of IEEE INFOCOM, Barcelona, Spain, Apr. 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

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, Performance

Keywords:
controlled mobility, global rigidity, localization, sweeps