Accuracy characterization for metropolitan-scale Wi-Fi localization

ABSTRACT

Location systems have long been identified as an important component of emerging mobile applications. Most research on location systems has focused on precise location in indoor environments. However, many location applications (for example, location-aware web search) become interesting only when the underlying location system is available ubiquitously and is not limited to a single office environment. Unfortunately, the installation and calibration overhead involved for most of the existing research systems is too prohibitive to imagine deploying them across, say, an entire city. In this work, we evaluate the feasibility of building a wide-area 802.11 Wi-Fi-based positioning system. We compare a suite of wireless-radio-based positioning algorithms to understand how they can be adapted for such ubiquitous deployment with minimal calibration. In particular, we study the impact of this limited calibration on the accuracy of the positioning algorithms. Our experiments show that we can estimate a user's position with a median positioning error of 13-40 meters (depending upon the characteristics of the environment). Although this accuracy is lower than existing positioning systems, it requires substantially lower calibration overhead and provides easy deployment and coverage across large metropolitan areas.

REFERENCES

• 1: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 2: P. Bahl and V. N. Padmanabhan. RADAR: An In-Building RF-Based User Location and Tracking System. In Proceedings of IEEE Infocom 00, April 2000.
• 3: Dodgeball.com. Mobile social software. http://www.dodgeball.com/.
• 4: E911 and E112 Resources. http://www.globallocate.com/.
• 5: P. Enge and P. Misra. The Global Positioning System. Proceedings of the IEEE (Special Issue on GPS), pages 3--172, January 1999.
• 6: D. Fox, J. Hightower, L. Liao, D. Schulz, and G. Borriello. Bayesian filtering for location estimation. IEEE Pervasive Computing, 2(3):24--33, July-September 2003.
• 7: Google.com. Google local: Find local businesses and services on the web. http://local.google.com/.
• 8: B. G. Griswold et al. Using mobile technology to create opportunistic interaction on a university campus. In Proceedings of UBICOMP Workshop on Supporting Spontaneous Interaction in Ubiquitous Computing Settings, September 2002.
• 9: F. Gustafsson, F. Gunnarsson, N. Bergman, U. Forssell, J. Jansson, R. Karlsson, and P.-J. Nordlund. Particle Filters for Positioning, Navigation and Tracking. IEEE Transactions on Signal Processing, 50:425--435, February 2002.
• 10: 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]
• 11: Jeffrey Hightower , Gaetano Borriello, Location Systems for Ubiquitous Computing, Computer, v.34 n.8, p.57-66, August 2001 [doi>10.1109/2.940014]
• 12: J. Hightower and G. Borriello. Accurate, Flexible, and Practical Location Estimation for Ubiquitous Computing. In Proceedings of International Conference on Ubiquitous Computing (UBICOMP), 2004.
• 13: J. Hightower and G. Borriello. Particle filters for location estimation in ubiquitous computing: A case study. In Proceedings of International Conference on Ubiquitous Computing (UBICOMP), 2004.
• 14: Kismet. http://www.kismetwireless.net/.
• 15: J. Krumm, G. Cermak, and E. Horvitz. RightSPOT: A Novel Sense of Location for a Smart Personal Object. In Proceedings of International Conference on Ubiquitous Computing (UBICOMP), October 2003.
• 16: J. Krumm and E. Horvitz. Locadio: Inferring motion and location from wi-fi signal strengths. In Proceedings of International Conference on Mobile and Ubiquitous Systems: Networking and Services (MobiQuitous'04), 2004.
• 17: 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]
• 18: A. LaMarca et al. Place lab: Device positioning using radio beacons in the wild. In Proceedings of International Conference on Pervasive Computing (Pervasive), June 2005.
• 19: C. Ma, G.-I. Jee, G. MacGougan, G. Lachapelle, S. Bloebaum, G. Cox, L. Garin, and J. Shewfelt. Gps signal degradation modeling. In Proceedings of International Technical Meeting of the Satellite Division of the Institute of Navigation, Sept. 2001.
• 20: NetStumbler. http://www.netstumbler.com.
• 21: P.-J. Norlund, F. Gunnarsson, and F. Gustafsson. Particle Filters for Positioning in Wireless Networks. In Proceedings of EUSIPCO, September 2002.
• 22: D. J. Patterson, L. Liao, D. Fox, and H. Kautz. Inferring High-Level Behavior from Low-Level Sensors. In Proceedings of International Conference on Ubiquitous Computing (UBICOMP), 2003.
• 23: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, Cambridge University Press, New York, NY, 1992
• 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: M. Rabinowitz and J. Spilker. A new positioning system using television synchronization signals. http://www.rosum.com/.
• 26: 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.
• 27: B. N. Schilit, N. Adams, R. Gold, M. Tso, and R. Want. The PARCTAB Mobile Computing System. In Proceedings of Workshop on Workstation Operating Systems, pages 34--39, Oct. 1993.
• 28: I. Smith et al. Social disclosure of place: From location technology to communication practices. In Proceedings of International Conference on Pervasive Computing (Pervasive), May 2005.
• 29: 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]
• 30: Yahoo! Inc. Yahoo local: Find businesses and services near you. http://local.yahoo.com/.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network monitoring

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.5 Local and Wide-Area Networks
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Management