Self-configuring localization systems: Design and Experimental Evaluation

ABSTRACT

Embedded networked sensors promise to revolutionize the way we interact with our physical environment and require scalable, ad hoc deployable and energy-efficient node localization/positioning.This paper describes the motivation, design, implementation, and experimental evaluation (on sharply resource-constrained devices) of a self-configuring localization system using radio beacons. We identify beacon density as an important parameter in determining localization quality, which saturates at a transition density. We develop algorithms to improve localization quality by (i) automating placement of new beacons at low densities (HEAP) and (ii) rotating functionality among redundant beacons while increasing system lifetime at high densities (STROBE).

REFERENCES

• 1: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 2: Bahl, P. and Padmanabhan, V. N. 2000. Radar: An in-building user location and tracking system. In Proceedings of IEEE Infocom 2000, vol. 2. IEEE, New York, 775--84.
• 3: Bulusu, N., Heidemann, J., and Estrin, D. 2000. GPS-less low cost outdoor localization for very small devices. IEEE Personal Communications Magazine 7, 5 (Oct.), 28--34.
• 4: Adaptive Beacon Placement, Proceedings of the The 21st International Conference on Distributed Computing Systems, p.489, April 16-19, 2001
• 5: Cerpa, A. and Estrin, D. 2002. Ascent: Adaptive self-configuring network topologies. In Proceedings of IEEE Infocom 2002, vol. 2. IEEE, New York.
• 6: Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys, A constant-factor approximation algorithm for the k-median problem (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.1-10, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301257]
• 7: Cox, I. J. 1991. Blanche---an experiment in guidance and navigation of an autonomous robot vehicle. IEEE Tracsactions on Robotics and Automation 7, 2, 193--204.
• 8: Doherty, L., Pister, K. S., and Ghaoui, L. E. 2001. Convex position estimation in wireless sensor networks. In Proceedings of IEEE Infocom 2001, vol. 3. IEEE, Anchorage, Alaska, 1655--1663.
• 9: 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]
• 10: Girod, L. 2000. Development and Characterization of an Acoustic Rangefinder. Tech. Rep. USC-CS-TR-00-728, University of Southern California.
• 11: Girod, L. and Estrin, D. 2001. Robust range estimation for localization in ad hoc sensor networks. http://lecs.cs.ucla.edu/ girod/papers/NLOS.ps.
• 12: Guibas, L., Lin, D., Latombe, J. C., LaValle, S., and Motwani, R. 2000. Visibility-based pursuit evasion in a polygonal environment. International Journal of Computational Geometry Applications.
• 13: Wendi Rabiner Heinzelman , Anantha Chandrakasan , Hari Balakrishnan, Energy-Efficient Communication Protocol for Wireless Microsensor Networks, Proceedings of the 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, January 04-07, 2000
• 14: Hightower, J., Want, R., and Borriello, G. 2000. Spoton: An indoor 3d location sensing technology based on rf signal strength. UW CSE 2000-02-02, University of Washington, Seattle, WA. February.
• 15: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 16: Hofmann-Wellenhoff, B., Lichtenegger, H., and Collins, J. 1997. Global Positioning System: Theory and Practice. Springer-Verlag, Berlin, 4th ed.
• 17: Chalermek Intanagonwiwat , Ramesh Govindan , Deborah Estrin, Directed diffusion: a scalable and robust communication paradigm for sensor networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.56-67, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345920]
• 18: Kaiser, W. J. 2000. Wins ng 1.0 transceiver power dissipation.
• 19: 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]
• 20: B. Krishnamachari , R. Bejar , S. Wicker, Distributed Problem Solving and the Boundaries of Self-Configuration in Multi-hop Wireless Networks, Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS'02)-Volume 9, p.297.2, January 07-10, 2002
• 21: US Wireless Corporation. http://www.uswcorp.com/USWCMainPages/our.htm.
• 22: Meguerdichian, S., Koushanfar, F., Potkonjak, M., and Srivastava, M. B. 2001. Coverage problems in wireless ad hoc sensor networks. In Proceedings of IEEE Infocom 2001. IEEE, Anchorage, Alaska.
• 23: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 24: 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]
• 25: Theodore S. Rappaport, Wireless Communications: Principles and Practice, IEEE Press, Piscataway, NJ, 1996
• 26: RF Monolitithics, I. http://www.rfm.com.
• 27: Royer, E. and Toh, C. 1999. A review of current routing protocols for ad-hoc mobile wireless networks. IEEE. Personal Communications. April 1999. Citeseer.ng.nec.com/royer99review.html.
• 28: Savvides, A., Boulis, A., Kaushanafar, F., Potkonjak, M., Karavas, V., and Srivastava, M. B. 2000. Dynamic location discovery in ad-hoc wireless networks. Tech. Rep. TM-UCLA-NESL-2000-07-001, University of California at Los Angeles. July.
• 29: 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]
• 30: Schurgers, C., Tsiatsis, V., and Srivastava, M. B. 2002. Stem: Topology management for eneregy efficient sensor networks. In IEEE Aerospace Conference 2002, Big Sky, MT, USA.
• 31: Sebastian Thrun , Dieter Fox , Wolfram Burgard , Frank Dallaert, Robust Monte Carlo localization for mobile robots, Artificial Intelligence, v.128 n.1-2, p.99-141, May 2001 [doi>10.1016/S0004-3702(01)00069-8]
• 32: VOR. Very high frequency omnirange. http://www.allstar.fiu.edu/aero/VOR.htm.
• 33: Ward, A., Jones, A., and Hopper, A. 1997. A new location technique for the active office. IEEE Personal Communications Magazine 4, 5 (October), 42--47.
• 34: Greg Welch , Gary Bishop , Leandra Vicci , Stephen Brumback , Kurtis Keller , D'nardo Colucci, The HiBall Tracker: high-performance wide-area tracking for virtual and augmented environments, Proceedings of the ACM symposium on Virtual reality software and technology, p.1-ff., December 20-22, 1999, London, United Kingdom [doi>10.1145/323663.323664]
• 35: Ya Xu , John Heidemann , Deborah Estrin, Geography-informed energy conservation for Ad Hoc routing, Proceedings of the 7th annual international conference on Mobile computing and networking, p.70-84, July 2001, Rome, Italy [doi>10.1145/381677.381685]
• 36: Ye, W., Heidemann, J., and Estrin, D. 2002. An energy efficient mac protocol for wireless sensor networks. In Proceedings of IEEE Infocom 2002, vol. 2. IEEE, New York.
• 37: Ye, W., Vaughan, R. T., Sukhatme, G. S., Heidemann, J., Estrin, D., and Mataric, M. J. 2001. Evaluating control strategies for wireless-networked robots using an integrated robot and network simulation. In Proceedings of ICRA-2001, Seoul, Korea.

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.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Reliability

Keywords:
Location, localization, self-configuration, sensor networks