Dynamic fine-grained localization in Ad-Hoc networks of sensors

ABSTRACT

The recent advances in radio and em beddedsystem technologies have enabled the proliferation of wireless microsensor networks. Such wirelessly connected sensors are released in many diverse environments to perform various monitoring tasks. In many such tasks, location awareness is inherently one of the most essential system parameters. It is not only needed to report the origins of events, but also to assist group querying of sensors, routing, and to answer questions on the network coverage. In this paper we present a novel approach to the localization of sensors in an ad-hoc network. We describe a system called AHLoS (Ad-Hoc Localization System) that enables sensor nodes to discover their locations using a set distributed iterative algorithms. The operation of AHLoS is demonstrated with an accuracy of a few centimeters using our prototype testbed while scalability and performance are studied through simulation.

REFERENCES

• 1: P. Bahl, V. Padmanabhan, RADAR: An In-Building RF-based User Location and Tracking System Proceedings of INFOCOM 2000 Tel Aviv, Israel, March 2000, p775-84, vol. 2
• 2: AVL Information Systems, Inc , http://www.avlinfosys.com/
• 3: Deborah Estrin , Ramesh Govindan , John Heidemann , Satish Kumar, Next century challenges: scalable coordination in sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.263-270, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313556]
• 4: 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]
• 5: Jinyang Li , John Jannotti , Douglas S. J. De Couto , David R. Karger , Robert Morris, A scalable location service for geographic ad hoc routing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.120-130, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345931]
• 6: K. Amouris, S. Papavassiliou, M. Li A Position-Based Multi-Zone Routing Protocol for Wide Area Mobile Ad-Hoc Networks, Proceedings of VTC 99
• 7: G. Turing, W. Jewell and T. Johnston, Simulation of Urban Vehicle-Monitoring Systems IEEE Transactions on Vehicular Technology, Vol VT-21, No1. Page 9-16, February 1972
• 8: W. Foy Position-Location Solution by Taylor Series Estimation IEEE Transactions of Aerospace and Electronic Systems Vol. AES-12, No. 2, pages 187-193, March 1976
• 9: J. Caffery and G. Stuber, Subscriber Location in CDMA Cellular Networks IEEE Transactions on Vehicular Technology, Vol. 47 No.2, pages 406-416, May 1998
• 10: J. Caffery and G. Stuber, Overview of Radiolocation in CDMA Cellular Systems IEEE Communications Magazine, April 1999
• 11: J. Beutel, Geolocation in a PicoRadio Environment Masters Thesis, UC Berkeley. July 1999.
• 12: Wireless Intergated Network Systems(WINS) http://wins.rsc.rockwell.com/
• 13: Atmel AS90LS8535, http://www.atmel.com/atmel/products/prod200.htm
• 14: DR3000 ASH Radio Module, http://www.rfm.com/products/data/dr3000.pdf
• 15: M. Melkonian, Getting by without an RTOS Embedded Systems Programming, September 2000
• 16: RFM Software Designer's Guide, http://www.rfm.com/corp/apnotes.htm
• 17: Polaroid 6500 ultrasonic ranging kit, http://www.acroname.com/robotics/parts/R11- 6500.html
• 18: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 19: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 20: Jerry D. Gibson, Mobile Communications Handbook, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 21: N. Bulusu, J. Heidemann and D. Estrin, GPS-less Low Cost Outdoor Localization For Very Small Devices, IEEE Personal Communications Magazine, Special Issue on Networking the Physical World, August 2000.
• 22: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 23: WaveLAN White specs, www.wavelan.com products
• 24: UCB/LBNL/VINT Network Simulator - ns (version 2) http://www.isi.edu/nsnam/ns/
• 25: W. Greene, Econometric Analysis, Third Edition, Prentice Hall 1997
• 26: D. J. Dayley and B. M. Bell, A Method for GPS Positioning IEE Trans., Aerosp. Electron. Syst., 1996, 32,(3),pp. 1148-54
• 27: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992
• 28: LORAN http://www.navcen.uscg.mil/loran/Default.htm#Link
• 29: Andy Harter , Andy Hopper , Pete Steggles , Andy Ward , Paul Webster, The anatomy of a context-aware application, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.59-68, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313476]
• 30: A. Harter, A. Hooper A New Location Technique for the Active Office IEEE Personal Communications vol 4,(No. 5), October 1997, pp. 42-47
• 31: S. Meguerdichian , F. Koushanfar, M. Potkonjak and M. B. Srivastava Coverage Problems in Wireless Ad-hoc Sensor Networks, In proceedings of Infocom 2001, Ankorange, Alaska
• 32: Mani Srivastava , Richard Muntz , Miodrag Potkonjak, Smart kindergarten: sensor-based wireless networks for smart developmental problem-solving enviroments, Proceedings of the 7th annual international conference on Mobile computing and networking, p.132-138, July 2001, Rome, Italy [doi>10.1145/381677.381690]
• 33: D. E. Manolakis, Efficient Solution and Performance Analysis of 3-D Position Estimation by Trilateration IEEE Transactions on Aerospace and Electronic Systems vol 32, p1239-48, October 1996
• 34: E. Kaplan, Understanding GPS Principles and Applications Artech House, 1996
• 35: L. Doherty, K. Pister and L. E. Ghaoui, Convex Optimization Methods for Sensor Node Position Estimation Proceedings of INFOCOM 2001, Anchorage, Alaska, April 2001

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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management
      C.2.4 Distributed Systems

General Terms:
Experimentation, Measurement, Performance, Theory

Keywords:
localization, location discovery, wireless sensor networks