A high-accuracy, low-cost localization system for wireless sensor networks

ABSTRACT

The problem of localization of wireless sensor nodes has long been regarded as very difficult to solve, when considering the realities of real world environments. In this paper, we formally describe, design, implement and evaluate a novel localization system, called Spotlight. Our system uses the spatio-temporal properties of well controlled events in the network (e.g., light), to obtain the locations of sensor nodes. We demonstrate that a high accuracy in localization can be achieved without the aid of expensive hardware on the sensor nodes, as required by other localization systems. We evaluate the performance of our system in deployments of Mica2 and XSM motes. Through performance evaluations of a real system deployed outdoors, we obtain a 20cm localization error. A sensor network, with any number of nodes, deployed in a 2500m2 area, can be localized in under 10 minutes, using a device that costs less than $1000. To the best of our knowledge, this is the first report of a sub-meter localization error, obtained in an outdoor environment, without equipping the wireless sensor nodes with specialized ranging hardware.

REFERENCES

• 1: A. Arora , P. Dutta , S. Bapat , V. Kulathumani , H. Zhang , V. Naik , V. Mittal , H. Cao , M. Demirbas , M. Gouda , Y. Choi , T. Herman , S. Kulkarni , U. Arumugam , M. Nesterenko , A. Vora , M. Miyashita, A line in the sand: a wireless sensor network for target detection, classification, and tracking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.605-634, 5 December 2004 [doi>10.1016/j.comnet.2004.06.007]
• 2: P. Bahl, V.N. Padmanabhan, "RADAR: An In-Building RF-based User Location and Tracking System", in Proceedings of Infocom, 2000.
• 3: M. Broxton, J. Lifton, J. Paradiso, "Localizing a Sensor Network via Collaborative Processing of Global Stimuli", in Proceedings of EWSN, 2005.
• 4: N. Bulusu, J. Heidemann, D. Estrin, "GPS-less Low Cost Outdoor Localization for Very Small Devices", in IEEE Personal Communications Magazine, 2000.
• 5: P. Corke, R. Peterson, D. Rus, "Networked Robots: Flying Robot Navigation Using a Sensor Net", in ISSR, 2003.
• 6: L. Doherty, L. E. Ghaoui, K. Pister, "Convex Position Estimation in Wireless Sensor Networks", in Proceedings of Infocom, 2001.
• 7: P. Dutta, M. Grimmer, A. Arora, S. Bibyk, D. Culler, "Design of a Wireless Sensor Network Platform for Detecting Rare, Random, and Ephemeral Events", in Proceedings of IPSN, 2005.
• 8: E. Elnahrawy, X. Li, R. Martin, "The Limits of Localization using RSSI", in Proceedings of SECON, 2004.
• 9: D. Fox, W. Burgard, S. Thrun, "Markov Localization for Mobile Robots in Dynamic Environments", in Journal of Artificial Intelligence Research, 1999.
• 10: D. Fox, W. Burgard, F. Dellaert, S. Thrun, "Monte Carlo Localization: Efficient Position Estimation for Mobile Robots", in Conference on Artificial Intelligence, 2000.
• 11: D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, S. Wicker, "Complex Behaviour at Scale: An Experimental Study of Low Power Wireless Sensor Networks", in Technical Report, UCLA-TR 01-0013, 2001.
• 12: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using 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.990096]
• 13: 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]
• 14: 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]
• 15: Y. Kwon, K. Mechitov, S. Sundresh, W. Kim, G. Agha, "Resilient Localization for Sensor Networks in Outdoor Environments", UIUC Technical Report, 2004.
• 16: 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]
• 17: K. Lorincz, M. Welsh, "MoteTrack: A Robust, Decentralized Approach to RF-Based Location Tracking", in Proceedings of Intl. Workshop on Location and Context-Awareness, 2005.
• 18: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 19: 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]
• 20: R. Nagpal, H. Shrobe, J. Bachrach, "Organizing a Global Coordinate System for Local Information on an Adhoc Sensor Network", in A.I Memo 1666. MIT A.I. Laboratory, 1999.
• 21: D. Niculescu, B. Nath, "DV-based Positioning in Adhoc Networks" in Telecommunication Systems, vol. 22, 2003.
• 22: E. Osterweil, T. Schoellhammer, M. Rahimi, M. Wimbrow, T. Stathopoulos, L.Girod, M. Mysore, A.Wu, D. Estrin, "The Extensible Sensing System", CENS-UCLA poster, 2004.
• 23: B.W. Parkinson, J. Spilker, "Global Positioning System: theory and applications", in Progress in Aeronautics and Astronautics, vol. 163, 1996.
• 24: Pubudu N. Pathirana , Nirupama Bulusu , Andrey V. Savkin , Sanjay Jha, Node Localization Using Mobile Robots in Delay-Tolerant Sensor Networks, IEEE Transactions on Mobile Computing, v.4 n.3, p.285-296, May 2005 [doi>10.1109/TMC.2005.43]
• 25: 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]
• 26: N. Priyantha, H. Balakrishnan, E. Demaine, S. Teller, "Mobile-Assisted Topology Generation for Auto-Localization in Sensor Networks", in Proceedings of Infocom, 2005.
• 27: 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]
• 28: Y. Shang, W. Ruml, "Improved MDS-Based Localization", in Proceedings of Infocom, 2004.
• 29: M. Sichitiu, V. Ramadurai,"Localization of Wireless Sensor Networks with a Mobile Beacon", in Proceedings of MASS, 2004.
• 30: Gyula Simon , Miklós Maróti , Ákos Lédeczi , György Balogh , Branislav Kusy , András Nádas , Gábor Pap , János Sallai , Ken Frampton, Sensor network-based countersniper system, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031497]
• 31: R. Stoleru, T. He, J.A. Stankovic, "Walking GPS: A Practical Solution for Localization in Manually Deployed Wireless Sensor Networks", in Proceedings of EmNetS, 2004.
• 32: John A. Stankovic, Security in wireless sensor networks, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, p.65-65, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029103]
• 33: Robert Szewczyk , Alan Mainwaring , Joseph Polastre , John Anderson , David Culler, An analysis of a large scale habitat monitoring application, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031521]
• 34: K. Whitehouse, A. Woo, C. Karlof, F. Jiang, D. Culler, "The Effects of Ranging Noise on Multi-hop Localization: An Empirical Study", in Proceedings of IPSN, 2005.
• 35: Kamin Whitehouse , David Culler, Calibration as parameter estimation in sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570747]
• 36: Pei Zhang , Christopher M. Sadler , Stephen A. Lyon , Margaret Martonosi, Hardware design experiences in ZebraNet, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031522]
• 37: Selco Products Co. "Construction and Characteristics of CdS Cells", product datasheet, 2004.

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

Keywords:
event distribution, laser, localization, wireless sensor network