Practical Robust Localization over Large Scale 802 11 Wireless Networks Andreas Haeberlen Eliot Flannery Andrew M Ladd Rice University Rice University Rice University ahae cs rice edu ef cs rice edu aladd cs rice edu Algis Rudys Dan S Wallach Lydia E Kavraki Rice University Rice University Rice University arudys cs rice edu dwallach cs rice edu kavraki cs rice edu ABSTRACT General Terms 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 locationaware applications without requiring special purpose hardware or complicated training and calibration procedures Algorithms Design Experimentation Measurement Keywords 802 11 wireless networks mobile systems topological localization Bayesian methods location aware computing 1 INTRODUCTION A practical scheme for mobile device location awareness has long been a target of mobility research Many interesting applications including systems like EasyLiving 6 and the Rhino Project 1 among others 2 13 14 35 would benefit from a practical locationsensing system Until now however indoor location sensing systems have either required specialized hardware involved lengthy training steps or had poor precision A practical scheme should have relatively low training time achieve high accuracy use widely deployed off the shelf hardware and be robust in the face of untrained variations Most previous indoor location sensing schemes have been based on occupancy grid models of the environment Such schemes divide the environment into a coordinate grid with one to two meter precision and attempt to map a device s location to a point on that grid Occupancy grid systems require lengthy training at each point in the grid to achieve usable accuracy Many location aware applications however do not need one to two meter precision for the location of a mobile device We use a topological model of our environment in which the building is divided into cells which each map to a region in our building i e a specific office or a hallway segment and we map a device s location to a cell instead of a point In this way we trade off some metric resolution for a dramatic reduction in training time Room or region level granularity of location provides sufficient context for many location aware applications Additionally operating at a coarser granularity leads to an improvement in localization robustness and allows localization to occur with fewer samples and thus operate at a higher frame rate We present a high precision topological location inference technique based on Bayesian inference and using the 802 11 wireless network protocol Most significant in our work is the scale We deployed our wireless location sensing system in our entire office building which is over 12 000 square meters in area Our technique can localize a device to one of 510 cells in the building within Categories and Subject Descriptors C 2 1 Computer Systems Organization Network Architecture and Design Wireless communication G 3 Mathematics of Computing Probability and Statistics Markov processes Probabilistic algorithms I 2 9 Computing Methodologies Robotics Sensors I 5 1 Pattern Recognition Models Statistical 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 To copy otherwise to republish to post on servers or to redistribute to lists requires prior specific permission and or a fee MobiCom 04 Sept 26 Oct 1 2004 Philadelphia Pennsylvania USA Copyright 2004 ACM 1 58113 868 7 04 0009 5 00 70 seconds it succeeded in over 95 of all attempts When the localization is off it is almost always off by only one cell e g it thinks you are in the adjacent office A training time of around 60 seconds per room is sufficient thus a small team can measure an entire office building in an evening Our techniques are robust even against time of day variation including the presence or absence or large groups of people in the same room as the platform being localized Furthermore our techniques allow us to calibrate and use 802 11 implementations different from the system used to initially measure the building Our system supports both static localization and dynamic tracking at speeds of over 3 m s We describe our basic localization system and report its performance in Section 2 Our analysis and experimental results on timevarying phenomena are presented in Section 3 Section 4 presents our calibration technique which is designed to compensate for variations in hardware and time varying phenomena We discuss our results in Section 5 and present our conclusions in Section 6 1 meter accuracy with a short training time although they do not detail how their system works A number of localization techniques have been developed for other wireless technologies For instance in part as a result of the FCC s E911 initiative 17 a number of systems have used RF signal intensity to determine the location of cellular phones 33 57 However in the field of outdoor location