Article

Practical robust localization over large-scale 802.11 wireless networks

Authors:

Lydia E. KavrakiAuthors Info & Claims

MobiCom '04: Proceedings of the 10th annual international conference on Mobile computing and networking

Pages 70 - 84

https://doi.org/10.1145/1023720.1023728

Published: 26 September 2004 Publication History

Get Access

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.]]

Google Scholar

[2]

G. D. Abowd, C. G. Atkeson, J. Hong, S. Long, R. Kooper, and M. Pinkerton. Cyberguide: a mobile context-aware tour guide. Wireless Networks, 3(5):421--433, Oct. 1997.]]

Digital Library

Google Scholar

[3]

The ACX100/ACX111 wireless network driver project. http://acx100.sourceforge.net.]]

Google Scholar

[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.]]

Google Scholar

[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.]]

Crossref

Google Scholar

[6]

B. Brumitt, B. Meyers, J. Krumm, A. Kern, and S. Shafer. EasyLiving: Technologies for intelligent environments. In Proceedings of the 2nd International Symposium on Handheld and Ubiquitous Computing, Bristol, UK, Sept. 2000.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[8]

W. Burgard, A. Cremers, D. Fox, D. Hahnel, G. Lakemeyer, D. Schulz, W. Steiner, and S. Thrun. The interactive museum tour-guide robot. In Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI), Madison, WI, July 1998.]]

Digital Library

Google Scholar

[9]

P. Castro, P. Chiu, T. Kremenek, and R. R. Muntz. A probabilistic room location service for wireless networked environments. In Proceedings of the Third International Conference on Ubiquitous Computing (Ubicomp), Atlanta, GA, Sept. 2001.]]

Digital Library

Google Scholar

[10]

G. Chen and D. Kotz. A survey of context-aware mobile computing research. Technical Report TR-2000-381, Department of Computer Science, Dartmouth College, Nov. 2000.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[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.]]

Crossref

Google Scholar

[13]

A. K. Dey and G. D. Abowd. Cybreminder: A context-aware system for supporting reminders. In Proceedings of the Second International Symposium on Handheld and Ubiquitous Computing, Bristol, UK, Sept. 2000.]]

Digital Library

Google Scholar

[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.]]

Google Scholar

[15]

G. Dudek and M. Jenkin. Computational Principles of Mobile Robotics. Cambridge University Press, Cambridge, UK, 2000.]]

Digital Library

Google Scholar

[16]

Ekahau, Inc. website. http://www.ekahau.com/.]]

Google Scholar

[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.]]

Google Scholar

[18]

D. Fox, W. Burgard, F. Dellaert, and S. Thrun. Monte Carlo localization: Efficient position estimation for mobile robots. In Proc. of the Sixteenth National Conference on Artificial Intelligence (AAAI-99), pages 343--349, Orlando, Florida, 1999.]]

Digital Library

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[21]

T. He, C. Huang, B. M. Blum, J. A. Stankovic, and T. Abdelzaher. Range-free localization schemes for large scale sensor networks. In Proceedings of the Ninth Annual International Conference on Mobile Computing and Networking (MOBICOM), San Diego, CA, Sept. 2003.]]

Digital Library

Google Scholar

[22]

J. Hightower and G. Borriello. Location systems for ubiquitous computing. IEEE Computer, 34(8):57--66, Aug. 2001.]]

Digital Library

Google Scholar

[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.]]

Google Scholar

[24]

J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System architecture directions for networked sensors. In Proceedings of the Ninth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX), Cambridge, MA, Nov. 2000.]]

Digital Library

Google Scholar

[25]

L. Hu and D. Evans. Localization for mobile sensor networks. In Proceedings of the Tenth Annual International Conference on Mobile Computing and Networking (MOBICOM), Philadelphia, PA, Sept. 2004.]]

Digital Library

Google Scholar

[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.]]

Google Scholar

[27]

C. Intanagonwiwat, R. Govindan, and D. Estrin. Directed diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM), Boston, MA, Aug. 2000.]]

Digital Library

Google Scholar

[28]

J. Krumm, S. Harris, B. Meyers, B. Brumitt, M. Hale, and S. Shafer. Multi-camera multi-person tracking for EasyLiving. In Third IEEE International Workshop on Visual Surveillance, Dublin, Ireland, July 2000.]]

Digital Library

Google Scholar

[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.]]

Google Scholar

[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.]]

Crossref

Google Scholar

[31]

A. M. Ladd, K. E. Bekris, A. Rudys, G. Marceau, L. E. Kavraki, and D. S. Wallach. Robotics-based location sensing using wireless Ethernet. In Proceedings of the Eighth Annual International Conference on Mobile Computing and Networking (MOBICOM), Atlanta, GA, Sept. 2002.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[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.]]

Digital Library

Google Scholar

[34]

T. Logsdon. Understanding the Navstar: GPS, GIS and IVHS. Second edition. Van Nostrand Reinhold, New York, 1995.]]

Google Scholar

[35]

N. Marmasse. comMotion: a context-aware communication system. In CHI Extended Abstracts on Human Factors in Computing Systems, Pittsburgh, PA, May 1999.]]

Digital Library

Google Scholar

[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.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[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.]]

Digital Library

Google Scholar

[39]

G. J. Pottie and W. J. Kaiser. Wireless integrated network sensors. Communications of the ACM, 43(5):51--58, May 2000.]]

Digital Library

Google Scholar

[40]

N. Priyantha, A. Chakraborty, and H. Balakrishman. The Cricket location support system. In Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 32--43, Boston, MA, Aug. 2000.]]

Digital Library

Google Scholar

[41]

N. Priyantha, A. Miu, H. Balakrishman, and S. Teller. The Cricket Compass for context-aware mobile applications. In Proceedings of the Seventh Annual International Conference on Mobile Computing and Networking (MOBICOM), pages 1--14, Rome, Italy, July 2001.]]

Digital Library

Google Scholar

[42]

E. Remolina and B. Kuipers. Towards a general theory of topological maps. Artificial Intelligence, 152(1):47--104, Jan. 2004.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[44]

A. Savvides, C.-C. Han, and M. B. Strivastava. Dynamic fine-grained localization in ad-hoc networks of sensors. In Proceedings of the Seventh Annual International Conference on Mobile Computing and Networking (MOBICOM), Rome, Italy, July 2001.]]

Digital Library

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[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.]]

Google Scholar

[48]

P. Tao, A. Rudys, A. M. Ladd, and D. S. Wallach. Wireless LAN location-sensing for security applications. In Proceedings of the Second ACM Workshop on Wireless Security (WiSe), San Diego, CA, Sept. 2003.]]

Digital Library

Google Scholar

[49]

S. Thrun. Probabilistic algorithms in robotics. AI Magazine, 21(4):93--109, 2000.]]

Digital Library

Google Scholar

[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.]]

Digital Library

Google Scholar

[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.]]

Google Scholar

[52]

S. Thrun, W. Burgard, and D. Fox. A probabilistic approach to concurrent mapping and localization for mobile robots. Machine Learning, 31(1-3):29--53, 1998.]]

Digital Library

Google Scholar

[53]

S. Thrun, D. Fox, W. Burgard, and F. Dellaert. Robust Monte Carlo localization for mobile robots. Artificial Intelligence, 101:99--141, 2000.]]

Digital Library

Google Scholar

[54]

S. Thrun, J.-S. Gutmann, D. Fox, W. Burgard, and B. Kuipers. Integrating topological and metric maps for mobile robot navigation: A statistical approach. In Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Conference on Innovative Applications of Artificial Intelligence, pages 989--995, Madison, WI, July 1998.]]

Digital Library

Google Scholar

[55]

R. Want, A. Hopper, V. Falco, and J. Gibbons. The Active Badge location system. ACM Transactions on Information Systems, 10:91--102, Jan. 1992.]]

Digital Library

Google Scholar

[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.]]

Crossref

Google Scholar

[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.]]

Crossref

Google Scholar

[58]

M. Youssef, A. Agrawala, and A. U. Shankar. WLAN location determination via clustering and probability distributions. In Proceedings of the IEEE International Conference on Pervasive Computing and Communications (PerCom), Fort Worth, TX, Mar. 2003.]]

Digital Library

Google Scholar

Cited By

View all

Ashraf IZikria YGarg SHur SPark YGuizani M(2024)Enabling Technologies and Techniques for Floor IdentificationACM Computing Surveys10.1145/367887857:1(1-48)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3678878
Yu MWan JLiu YSun CZhou B(2024)Improved Bluetooth-Based Indoor Localization for Devices Heterogeneity Using Back- Propagation Neural NetworkIEEE Sensors Journal10.1109/JSEN.2024.342923724:17(27763-27776)Online publication date: 1-Sep-2024
https://doi.org/10.1109/JSEN.2024.3429237
Yuan YLu QLiu XYu YMa KLiu Z(2024)Adaptive Fingerprint Database Update Method Based on Gaussian Process Regression for Indoor LocalizationIEEE Sensors Journal10.1109/JSEN.2024.340309824:14(23140-23149)Online publication date: 15-Jul-2024
https://doi.org/10.1109/JSEN.2024.3403098
Show More Cited By

Index Terms

Recommendations

Robotics-based location sensing using wireless ethernet
MobiCom '02: Proceedings of the 8th annual international conference on Mobile computing and networking

A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This paper describes the design, implementation and analysis of a system for determining position inside a building from measured RF ...
Robotics-based location sensing using wireless Ethernet

A key subproblem in the construction of location-aware systems is the determination of the position of a mobile device. This article describes the design, implementation and analysis of a system for determining position inside a building from measured ...
Large-scale Measurements of Wireless Network Behavior
SIGCOMM '15: Proceedings of the 2015 ACM Conference on Special Interest Group on Data Communication

Meraki is a cloud-based network management system which provides centralized configuration, monitoring, and network troubleshooting tools across hundreds of thousands of sites worldwide. As part of its architecture, the Meraki system has built a ...

Reviews

Reviewer: Jiyong Ma

Automatic localization of mobile devices is an important research area in context-aware mobile computing, one that seeks to provide information about user and mobile device states, including the characteristics of the surrounding environment, and the user's social situation and location. Among these states, location is an important context that is used to track the user's position. It is a challenging task to design an unobtrusive, cheap, accurate, and scalable indoor location-sensing system. In this paper, the authors demonstrate a practical solution that can accurately localize a mobile computing device with a standard 802.11 card. The location inference techniques are based on statistical learning algorithms, such as Gaussian models, hidden Markov models, and Bayesian inference. An efficient and fast training approach is discussed, and a hardware adaptation algorithm for different implementations of 802.11 is also described. The authors showed that their system is robust against a variety of time varying influence factors, such as the presence or absence of people and electronic devices, including microwave ovens. The system can correctly localize a user's position over 95 percent of the time, across an entire building. The significant contribution of this paper is its report on the large-scale experiment conducted by the authors: the wireless location-sensing system was deployed in an office building with over 12,000 square meters of floor space. The experiment has enriched the practice of research in automatic localizing mobile devices. The experiment results also confirmed previous findings, that the signal intensity values reported by some hardware with different 802.11 implementations can be closely approximated by a linear relationship. Further research might be focused on developing a standard corpus that could be shared among researchers in this community to evaluate different algorithms; the corpus could include different influence factors, such as hardware, or different building environments. In addition, some techniques from pattern recognition and signal processing could be used in this field. For those interested in context-aware mobile computing, this paper is definitely worth reading. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

MobiCom '04: Proceedings of the 10th annual international conference on Mobile computing and networking

September 2004

384 pages

ISBN:1581138687

DOI:10.1145/1023720

General Chair:
Zygmunt J. Haas
Cornell University
,
Program Chairs:
Samir R. Das
Stony Brook University, SUNY
,
Ravi Jain
DoCoMo USA Labs

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 September 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MobiCom04

Sponsor:

MobiCom04: Tenth Annual International Conference on Mobile Computing and Networking

September 26 - October 1, 2004

PA, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 440 of 2,972 submissions, 15%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

375
Total Citations
View Citations
3,466
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ashraf IZikria YGarg SHur SPark YGuizani M(2024)Enabling Technologies and Techniques for Floor IdentificationACM Computing Surveys10.1145/367887857:1(1-48)Online publication date: 7-Oct-2024
https://dl.acm.org/doi/10.1145/3678878
Yu MWan JLiu YSun CZhou B(2024)Improved Bluetooth-Based Indoor Localization for Devices Heterogeneity Using Back- Propagation Neural NetworkIEEE Sensors Journal10.1109/JSEN.2024.342923724:17(27763-27776)Online publication date: 1-Sep-2024
https://doi.org/10.1109/JSEN.2024.3429237
Yuan YLu QLiu XYu YMa KLiu Z(2024)Adaptive Fingerprint Database Update Method Based on Gaussian Process Regression for Indoor LocalizationIEEE Sensors Journal10.1109/JSEN.2024.340309824:14(23140-23149)Online publication date: 15-Jul-2024
https://doi.org/10.1109/JSEN.2024.3403098
Yang YShen ZDeng QLiu WJiang HXie X(2024)CORAL: Recognition and Locating of Contextual Objects With Unmodulated Acoustic SignalsIEEE Internet of Things Journal10.1109/JIOT.2024.343026211:20(33734-33743)Online publication date: 15-Oct-2024
https://doi.org/10.1109/JIOT.2024.3430262
Yang YYang QZhang THuang W(2024)A Brownian Motion Restricted K-Nearest Neighbor Algorithm for Indoor PositioningWireless Personal Communications10.1007/s11277-024-11640-zOnline publication date: 30-Oct-2024
https://doi.org/10.1007/s11277-024-11640-z
Jiang XZhao ZLi ZHong F(2023)Echo-ID: Smartphone Placement Region Identification for Context-Aware ComputingSensors10.3390/s2309430223:9(4302)Online publication date: 26-Apr-2023
https://doi.org/10.3390/s23094302
Yang SZhang DSong RYin PChen Y(2023)Multiple WiFi Access Points Co-Localization Through Joint AoA EstimationIEEE Transactions on Mobile Computing10.1109/TMC.2023.3239377(1-16)Online publication date: 2023
https://doi.org/10.1109/TMC.2023.3239377
Zheng ZLi YLiao ZXue YKuang JZhuang YZhang P(2023)The Necessity of Modeling Location Uncertainty of Fingerprints for Ubiquitous PositioningIEEE Sensors Journal10.1109/JSEN.2023.328982623:16(18413-18422)Online publication date: 15-Aug-2023
https://doi.org/10.1109/JSEN.2023.3289826
Sun SLi YWang XMoran BRowe W(2023)Exploiting Environmental Information Using HsMMs for Smartphone User TrackingIEEE Sensors Journal10.1109/JSEN.2023.323664223:4(4043-4051)Online publication date: 15-Feb-2023
https://doi.org/10.1109/JSEN.2023.3236642
Chen CKia S(2023)Self-Localizing On-Demand Portable Wireless Beacons for Coverage Enhancement of RF Beacon-Based Indoor Localization SystemsIEEE Journal of Indoor and Seamless Positioning and Navigation10.1109/JISPIN.2023.33381861(180-186)Online publication date: 2023
https://doi.org/10.1109/JISPIN.2023.3338186
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Robotics-based location sensing using wireless ethernet

Robotics-based location sensing using wireless Ethernet

Large-scale Measurements of Wireless Network Behavior

Reviews

Access critical reviews of Computing literature here