Error characteristics and calibration-free techniques for wireless LAN-based location estimation

ABSTRACT

Using wireless LAN technology for location estimation provides alternate means to enable location-based applications without investment in sensor network infrastructure and special hardware. However, the main drawback of wireless LAN-based location systems is calibration of signal strength as a function of location in spatially high-density, which consumes manual labor and needs to be carried out repeatedly. In this paper, we analyze empirical error characteristics of calibration-based location algorithms such as triangulation in various spatial densities of calibration, using commercially available wireless LAN products. Then, we propose Triangular Interpolation and eXtrapolation (TIX), a calibration-free location algorithm, and present empirical performance evaluation. TIX can achieve mean distance error within 5.4 m, which is comparable to within 4.7 m errors of the calibration-based algorithms. We also present theoretical analysis on error characteristics of the location algorithms deriving accuracy limits and quantifying the effect of RF measurement and calibration.

REFERENCES

• 1: Bahl, P., and Padmannabhan, V., N. RADAR: An In-Building RF-based Location and Tracking System. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM '00). Tel-Aviv, Israel, March 2000.
• 2: Bahl, P., and Padmannabhan, V., N. Enhancements to the RADAR User Location and Tracking System. Technical Report MSR-TR-2000-12, Microsoft Research, February 2000.
• 3: Prasithsangaree, P., Krishnamurthy, P., and Chrysanthis, P., K. On Indoor Position Location with Wireless LANs. In Proceedings of the IEEE Personal, Indoor and Mobile Radio Communications (PIMRC '02). Lisbon, Portugal, September 2002.
• 4: Pandya, D., Jain, R., and Lupu, E. Indoor Location Using Multiple Wireless Technologies. In Proceedings of the IEEE Personal, Indoor and Mobile Radio Communications (PIMRC '03). Beijing, China, September 2003.
• 5: Gwon, Y., Jain, R., and Kawahara, T. Robust Indoor Location Estimation of Stationary and Mobile Users. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM '04). Hong Kong, China, March 2004.
• 6: Samilagic, A., and Kogan, D. Location Sensing and Privacy in a Context-aware Computing Environment. IEEE Wireless Communications, Vol. 9 No.5. October 2002.
• 7: Krumm, J., and Platt, J. Minimizing Calibration Effort for an Indoor 802.11 Device Location Measurement System. Technical Report MSR-TR-2003-82, Microsoft Research, November 2003.
• 8: 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]
• 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: Dragoş Niculescu , Badri Nath, Error characteristics of ad hoc positioning systems (aps), Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989463]
• 11: The linux-wlan™ Project. http://www.linux-wlan.co

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: Measurement techniques

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Interpolation formulas; Extrapolation

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
RF-based location estimation, calibration, extrapolation, interpolation, static scene analysis, triangulation, wireless LAN