Practical robust localization over large-scale 802.11 wireless networks

ABSTRACT

We demonstrate a system built using probabilistic techniques that allows for remarkably accurate localization across our entire office building using nothing more than the built-in signal intensity meter supplied by standard 802.11 cards. While prior systems have required significant investments of human labor to build a detailed signal map, we can train our system by spending less than one minute per office or region, walking around with a laptop and recording the observed signal intensities of our building's unmodified base stations. We actually collected over two minutes of data per office or region, about 28 man-hours of effort. Using less than half of this data to train the localizer, we can localize a user to the precise, correct location in over 95% of our attempts, across the entire building. Even in the most pathological cases, we almost never localize a user any more distant than to the neighboring office. A user can obtain this level of accuracy with only two or three signal intensity measurements, allowing for a high frame rate of localization results. Furthermore, with a brief calibration period, our system can be adapted to work with previously unknown user hardware. We present results demonstrating the robustness of our system against a variety of untrained time-varying phenomena, including the presence or absence of people in the building across the day. Our system is sufficiently robust to enable a variety of location-aware applications without requiring special-purpose hardware or complicated training and calibration procedures.

REFERENCES

• 1: G. Abowd, K. Lyons, and K. Scott. The Rhino project, Aug. 1998. http://www.cc.gatech.edu/fce/uvid/rhino.html.
• 2: Gregory D. Abowd , Christopher G. Atkeson , Jason Hong , Sue Long , Rob Kooper , Mike Pinkerton, Cyberguide: a mobile context-aware tour guide, Wireless Networks, v.3 n.5, p.421-433, Oct. 1997 [doi>10.1023/A:1019194325861]
• 3: The ACX100/ACX111 wireless network driver project. http://acx100.sourceforge.net.
• 4: P. Bahl and V. N. Padmanabhan. Enhancements to the RADAR user location and tracking system. Technical Report MSR-TR-2000-12, Microsoft Research, Feb. 2000.
• 5: P. Bahl and V. N. Padmanabhan. RADAR: An in-building RF-based user location and tracking system. In Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), volume 2, pages 775--784, Tel Aviv, Israel, Mar. 2000.
• 6: Barry Brumitt , Brian Meyers , John Krumm , Amanda Kern , Steven A. Shafer, EasyLiving: Technologies for Intelligent Environments, Proceedings of the 2nd international symposium on Handheld and Ubiquitous Computing, p.12-29, September 25-27, 2000, Bristol, UK
• 7: 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.
• 8: Wolfram Burgard , Armin B. Cremers , Dieter Fox , Dirk Hähnel , Gerhard Lakemeyer , Dirk Schulz , Walter Steiner , Sebastian Thrun, The interactive museum tour-guide robot, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.11-18, July 1998, Madison, Wisconsin, United States
• 9: Paul Castro , Patrick Chiu , Ted Kremenek , Richard R. Muntz, A Probabilistic Room Location Service for Wireless Networked Environments, Proceedings of the 3rd international conference on Ubiquitous Computing, p.18-34, September 30-October 02, 2001, Atlanta, Georgia, USA
• 10: Guanling Chen , David Kotz, A Survey of Context-Aware Mobile Computing Research, Dartmouth College, Hanover, NH, 2000
• 11: H. Choset and K. Nagatani. Topological simultaneous localization and mapping (SLAM): Toward exact localization without explicit localization. IEEE Transactions on Robotics and Automation, 17(2):125--137, Apr. 2001.
• 12: I. Cox. Blanche - An experiment in guidance and navigation of an autonomous robot vehicle. IEEE Transactions on Robotics and Automation, 7(2):193--204, 1991.
• 13: Anind K. Dey , Gregory D. Abowd, CybreMinder: A Context-Aware System for Supporting Reminders, Proceedings of the 2nd international symposium on Handheld and Ubiquitous Computing, p.172-186, September 25-27, 2000, Bristol, UK
• 14: A. K. Dey, G. D. Abowd, and D. Salber. A context-based infrastructure for smart environments. In Proceedings of the First International Workshop on Managing Interactions in Smart Environments, Dublin, Ireland, Dec. 1999.
• 15: Gregory Dudek , Michael Jenkin, Computational principles of mobile robotics, Cambridge University Press, New York, NY, 2000
• 16: Ekahau, Inc. website. http://www.ekahau.com/.
• 17: Federal Communications Commission Report and Order 96-264: Revision of the commission's rules to ensure compatibility with Enhanced 911 emergency calling systems, July 1996. http://www.fcc.gov/Bureaus/Wireless/Orders/1996/fcc96264.txt.
• 18: Dieter Fox , Wolfram Burgard , Frank Dellaert , Sebastian Thrun, Monte Carlo localization: efficient position estimation for mobile robots, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.343-349, July 18-22, 1999, Orlando, Florida, United States
• 19: D. Fox, W. Burgard, and S. Thrun. Markov localization for mobile robots in dynamic environments. Journal of Artificial Intelligence Research, (JAIR), 11:391--427, Nov. 1999.
• 20: Y. Gwon, R. Jain, and T. Kawahara. Robust indoor location estimation of stationary and mobile users. In Proceedings The 23rd Conference of the IEEE Communications Society (INFOCOM), Hong Kong, Mar. 2004.
• 21: 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]
• 22: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 23: J. Hightower, R. Want, and G. Borriello. SpotON: An indoor 3D location sensing technology based on RF signal strength. Technical Report UW CSE 00-02-02, Department of Computer Science and Engineering, University of Washington, Seattle, WA, Feb. 2000.
• 24: 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
• 25: 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]
• 26: Institute of Electrical and Electronics Engineers, Inc. ANSI/IEEE Standard 802.11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, 1999.
• 27: 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]
• 28: John Krumm , Steve Harris , Brian Meyers , Barry Brumitt , Michael Hale , Steve Shafer, Multi-Camera Multi-Person Tracking for EasyLiving, Proceedings of the Third IEEE International Workshop on Visual Surveillance (VS'2000), p.3, July 01-01, 2000
• 29: J. Krumm and J. Platt. Minimizing calibration effort for an indoor 802.11 device location measurement system. Technical Report MSR-TR-2003-82, Microsoft Research, Seattle, WA, Nov. 2003.
• 30: B. Kuipers and Y.-T. Byun. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Journal of Robotics and Autonomous Systems, 8(1--2):47--63, Nov. 1991.
• 31: Andrew M. Ladd , Kostas E. Bekris , Algis Rudys , Lydia E. Kavraki , Dan S. Wallach , Guillaume Marceau, Robotics-based location sensing using wireless ethernet, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570674]
• 32: S. Lenser and M. Veloso. Sensor resetting localization for poorly modelled mobile robots. In Proceedings of ICRA-2000, The International Conference on Robotics and Automation, Detroit, MI, Apr. 2000.
• 33: T. Liu, P. Bahl, and I. Chlamtac. Mobility modeling, location tracking, and trajectory prediction in wireless ATM networks. IEEE Journal on Selected Areas in Communications, 16(6):922--936, Aug. 1998.
• 34: T. Logsdon. Understanding the Navstar: GPS, GIS and IVHS. Second edition. Van Nostrand Reinhold, New York, 1995.
• 35: Natalia Marmasse, comMotion: a context-aware communication system, CHI '99 extended abstracts on Human factors in computing systems, May 15-20, 1999, Pittsburgh, Pennsylvania [doi>10.1145/632716.632910]
• 36: R. Nagpal, H. Shrobe, and J. Bachrach. Organizing a global coordinate system from local information on an ad hoc sensor network. In Proceedings of the Second International Workshop on Information Processing in Sensor Networks (IPSN), Palo Alto, CA, Apr. 2003.
• 37: D. Niculescu and B. Nath. Ad hoc positioning system (APS) using AOA. In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), San Francisco, CA, Mar. 2003.
• 38: D. Niculescu and B. Nath. DV based positioning in ad hoc networks. Kluwer Journal of Telecommunication Systems, 22(1--4):267--280, Jan. 2003.
• 39: 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]
• 40: 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]
• 41: Nissanka B. Priyantha , Allen K.L. Miu , Hari Balakrishnan , Seth Teller, The cricket compass for context-aware mobile applications, Proceedings of the 7th annual international conference on Mobile computing and networking, p.1-14, July 2001, Rome, Italy [doi>10.1145/381677.381679]
• 42: Emilio Remolina , Benjamin Kuipers, Towards a general theory of topological maps, Artificial Intelligence, v.152 n.1, p.47-104, January 2004 [doi>10.1016/S0004-3702(03)00114-0]
• 43: T. Roos, P. Myllymaki, H. Tirri, P. Misikangas, and J. Sievanan. A probabilistic approach to WLAN user location estimation. International Journal of Wireless Information Networks, 9(3), July 2002.
• 44: 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]
• 45: A. Smailagic, D. Siewiorek, J. Anhalt, D. Kogan, and Y. Wang. Location sensing and privacy in a context aware computing environment. Pervasive Computing, 2001.
• 46: J. Small, A. Smailagic, and D. P. Siewiorek. Determining user location for context aware computing through the use of a wireless LAN infrastructure, Dec. 2000. http://www-2.cs.cmu.edu/~aura/docdir/small00.pdf.
• 47: C. Steger, P. Radosavljevic, and P. Frantz. 802.11b operating in a mobile channel: Performance and challenges. In Communications Design Conference, San Jose, CA, Sept. 2003.
• 48: Ping Tao , Algis Rudys , Andrew M. Ladd , Dan S. Wallach, Wireless LAN location-sensing for security applications, Proceedings of the 2003 ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941311.941314]
• 49: S. Thrun. Probabilistic algorithms in robotics. AI Magazine, 21(4):93--109, 2000.
• 50: S. Thrun and A. Bucken. Integrating grid-based and topological maps for mobile robot navigation. In Proceedings of the AAAI Thirteenth National Conference on Artificial Intelligence, Portland, Oregon, Aug. 1996.
• 51: S. Thrun and A. Bucken. Learning maps for indoor mobile robot navigation. Technical Report CMU-CS-96-121, Carnegie Mellon University, Computer Science Department, Pittsburgh, PA, Apr. 1996.
• 52: Sebastian Thrun , Wolfram Burgard , Dieter Fox, A Probabilistic Approach to Concurrent Mapping and Localization for Mobile Robots, Machine Learning, v.31 n.1-3, p.29-53, April/May/June 1998 [doi>10.1023/A:1007436523611]
• 53: 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]
• 54: Sebastian Thrun , Jens-Steffen Gutmann , Dieter Fox , Wolfram Burgard , Benjamin J. Kuipers, Integrating topological and metroc maps for mobile robot navigation: a statistical approach, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.989-995, July 1998, Madison, Wisconsin, United States
• 55: 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]
• 56: A. Ward, A. Jones, and A. Hopper. A new location technique for the active office. IEEE Personal Communications, 4(5):42--47, Oct. 1997.
• 57: R. Yamamoto, H. Matsutani, H. Matsuki, T. Oono, and H. Ohtsuka. Position location technologies using signal strength in cellular systems. In Proc. of the 53rd IEEE Vehicular Technology Conference, Rhodes, Greece, May 2001.
• 58: Moustafa A. Youssef , Ashok Agrawala , A. Udaya Shankar, WLAN Location Determination via Clustering and Probability Distributions, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.143, March 23-26, 2003

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.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.3 Microcomputers
          Subjects: Portable devices (e.g., laptops, personal digital assistants)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo); Markov processes

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics
          Subjects: Sensors
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical

General Terms:
Algorithms, Design, Experimentation, Measurement

Keywords:
802.11, Bayesian methods, location-aware computing, mobile systems, topological localization, wireless networks