The Horus WLAN location determination system

ABSTRACT

We present the design and implementation of the Horus WLAN location determination system. The design of the Horus system aims at satisfying two goals: high accuracy and low computational requirements. The Horus system identifies different causes for the wireless channel variations and addresses them to achieve its high accuracy. It uses location-clustering techniques to reduce the computational requirements of the algorithm. The lightweight Horus algorithm helps in supporting a larger number of users by running the algorithm at the clients.We discuss the different components of the Horus system and its implementation under two different operating systems and evaluate the performance of the Horus system on two testbeds. Our results show that the Horus system achieves its goal. It has an error of less than 0.6 meter on the average and its computational requirements are more than an order of magnitude better than other WLAN location determination systems. Moreover, the techniques developed in the context of the Horus system are general and can be applied to other WLAN location determination systems to enhance their accuracy. We also report lessons learned from experimenting with the Horus system and provide directions for future work.

REFERENCES

• 1: http://www.cs.umd.edu/users/moustafa/Downloads.htm.
• 2: http://www.hpl.hp.com/personal/Jean_Tourrilhes/.
• 3: http://www.orinocowireless.com.
• 4: Ronald Azuma, Tracking requirements for augmented reality, Communications of the ACM, v.36 n.7, p.50-51, July 1993 [doi>10.1145/159544.159581]
• 5: Bahl, P., and Padmanabhan, V. N. Radar: An In-Building RF-based User Location and Tracking System. In IEEE Infocom 2000 (March 2000), vol. 2, pp. 775--784.
• 6: Bahl, P., Padmanabhan, V. N., and Balachandran, A. Enhancements to the RADAR User Location and Tracking System. Tech. Rep. MSR-TR-00-12, Microsoft Research, February 2000.
• 7: George Edward Pelham Box , Gwilym M. Jenkins, Time Series Analysis: Forecasting and Control, Prentice Hall PTR, Upper Saddle River, NJ, 1994
• 8: 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
• 9: Castro, P., and Muntz, R. Managing Context for Smart Spaces. IEEE Personal Communications (OCTOBER 2000).
• 10: Guanling Chen , David Kotz, A Survey of Context-Aware Mobile Computing Research, Dartmouth College, Hanover, NH, 2000
• 11: Enge, P., and Misra, P. Special issue on GPS: The Global Positioning System. Proceedings of the IEEE (January 1999), 3--172.
• 12: Gwon, Y., Jain, R., and Kawahara, T. Robust Indoor Location Estimation of Stationary and Mobile Users. In IEEE Infocom (March 2004).
• 13: 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]
• 14: Todd D. Hodes , Randy H. Katz , Edouard Servan-Schreiber , Lawrence Rowe, Composable ad-hoc mobile services for universal interaction, Proceedings of the 3rd annual ACM/IEEE international conference on Mobile computing and networking, p.1-12, September 26-30, 1997, Budapest, Hungary [doi>10.1145/262116.262121]
• 15: Krishnan, P., Krishnakumar, A., Ju, W. H., Mallows, C., and Ganu, S. A System for LEASE: Location Estimation Assisted by Stationary Emitters for Indoor RF Wireless Networks. In IEEE Infocom (March 2004).
• 16: 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
• 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: Robert J. Orr , Gregory D. Abowd, The smart floor: a mechanism for natural user identification and tracking, CHI '00 extended abstracts on Human factors in computing systems, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/633292.633453]
• 19: 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]
• 20: Teemu Roos , Petri Myllymäki , Henry Tirri, A Statistical Modeling Approach to Location Estimation, IEEE Transactions on Mobile Computing, v.1 n.1, p.59-69, January 2002 [doi>10.1109/TMC.2002.1011059]
• 21: Roos, T., Myllymaki, P., Tirri, H., Misikangas, P., and Sievanen, J. A Probabilistic Approach to WLAN User Location Estimation. International Journal of Wireless Information Networks 9, 3 (July 2002).
• 22: Smailagic, A., Siewiorek, D. P., Anhalt, J., Kogan, D., and Wang, Y. Location Sensing and Privacy in a Context Aware Computing Environment. Pervasive Computing (2001).
• 23: Stallings, W. Wireless Communications and Networks, first ed. Prentice Hall, 2002.
• 24: Tekinay, S. Special issue on Wireless Geolocation Systems and Services. IEEE Communications Magazine (April 1998).
• 25: The Institute of Electrical and Electronics Engineers, Inc. IEEE Standard 802.11 - Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications.
• 26: 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]
• 27: Yeo, J., Banerjee, S., and Agrawala, A. Measuring traffic on the wireless medium: experience and pitfalls. In Technical Report, CS-TR 4421, Department of Computer Science, University of Maryland, College Park (Dec. 2002).
• 28: Youssef, M. Horus: A WLAN-Based Indoor Location Determination System. PhD thesis, University of Maryland at College Park, May 2004. Submitted for SigMobile Dissertation Page.
• 29: Moustafa Youssef , Mohamed Abdallah, Multivariate Analysis for Probabilistic WLAN Location Determination Systems, Proceedings of the The Second Annual International Conference on Mobile and Ubiquitous Systems: Networking and Services, p.353-362, July 17-21, 2005 [doi>10.1109/MOBIQUITOUS.2005.41]
• 30: Youssef, M., and Agrawala, A. Small-Scale Compensation for WLAN Location Determination Systems. In IEEE WCNC 2003 (March 2003).
• 31: Youssef, M., and Agrawala, A. Handling Samples Correlation in the Horus System. In IEEE Infocom (March 2004).
• 32: Youssef, M., and Agrawala, A. On the Optimality of WLAN Location Determination Systems. In Communication Networks and Distributed Systems Modeling and Simulation Conference (January 2004).
• 33: 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
• 34: Youssef, M., Agrawala, A., Shankar, A. U., and Noh, S. H. A Probabilistic Clustering-Based Indoor Location Determination System. Tech. Rep. UMIACS-TR 2002-30 and CS-TR 4350, University of Maryland, College Park, March 2002. http://www.cs.umd.edu/Library/TRs/.

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.4 Distributed Systems
          Subjects: Network operating systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Management