Practical Robust Localization over Large-Scale Wireless Ethernet Networks 10th Annual International Conference on Mobile Computing and Networking (MOBICOM) September 28, 2004 Philadelphia, PA Andreas Haeberlen Eliot Flannery Andrew Ladd Algis Rudys Dan Wallach Lydia Kavraki Rice University Houston, TX 2004 Andreas Haeberlen, Rice University 1 Motivation Goal: Locate a device in a building

Location-aware computing has many interesting applications: Navigation Asset tracking Tourist/visitor guides Advertising Finding resources Visitor tracking Content redirection Robot navigation Sensor networks

Intruder detection The ideal localization system: Cheap Easy to deploy Accurate Robust 2004 Andreas Haeberlen, Rice University 2 Related Work Solutions with special hardware Good accuracy Expensive Hard to deploy Example: Cricket [Priyantha 2000] 2004 Andreas Haeberlen, Rice University Ultrasound

beacons 3 Related Work Bayesian localization [Ladd 2002] Good accuracy Inexpensive hardware But: Not practical! Needs many days of training Does not work with different hardware Accuracy varies during the day 2004 Andreas Haeberlen, Rice University 4 Overview Improvements over [Ladd 2002]:

Drastic reduction in training time Adapts to different hardware Robust against untrained variations Techniques used: Topological localization Simplified signal model Calibration 2004 Andreas Haeberlen, Rice University 5 Training Occurrences 802.11 wireless signal propagation is complex

Need training Operator visits every location, measures signal strength Result: A signal map of the entire building Observed signal strength 2004 Andreas Haeberlen, Rice University 6 Markov Localization Signal map P(o j | si ) Observed RSSI Location estimate i o

Bayes' formula i 1 P (o j | si ) i New location estimate i 1 2004 Andreas Haeberlen, Rice University To localize 1. Initialize vector of location estimates 2. Perform a base station scan 3. Update estimate using Bayes' formula 4. Repeat steps 2-3 until estimates

converge 7 Topological regions Occupancy grid Regions 2004 Andreas Haeberlen, Rice University Many applications do not need 1-2 meter precision Can trade metric resolution for lower training time Localize to regions Offices Hallway segments Parts of larger rooms Reduces training effort by an order of magnitude

8 Gaussian signal model Occurrences Gap Minor mode Occurrences Observed signal strength Observed signal strength 2004 Andreas Haeberlen, Rice University Previous methods keep a histogram of signal strengths Problems

Overtraining Undertraining Use Gaussian as an approximation! More robust Saves memory Needs less training 9 Experiment: Duncan Hall Duncan Hall: >200 offices, classrooms, seminar rooms Total area: 158 x 75 meters 2004 Andreas Haeberlen, Rice University 10

Duncan Hall Architecture Large open spaces (low signal variation) Clerestory ceiling (reflections) 2004 Andreas Haeberlen, Rice University Metal air ducts (distortions) 11 Experiment: Duncan Hall Data collection: Manually created 510 cells, ~3x5m each Collected 100 BS scans/cell (51249 total) 28 man-hours were sufficient! Experiments: Partition data set

Training data Testing data 51249 scans 2004 Andreas Haeberlen, Rice University 12 Results: Static localization Accuracy for cell: 70-80% Base stations 80-90% 90-95% >95% worst case (localizes to adjacent cells) Result: Excellent accuracy over the entire building 2004 Andreas Haeberlen, Rice University

13 Results: Static localization II For 95% accuracy: Histogram: 84 scans Gaussian: 30 scans Experiment: Use only N scans/cell for training Result: Gaussian needs a lot less training data This is in addition to gains from topology model 2004 Andreas Haeberlen, Rice University 14 Source: [Tao 2003] 0.18 Signal Strength

140 100 0.12 60 0.06 20 3am 1. 2. 9am 3pm 9pm 3am 0.00 Probability of registering signal strength

Problem: Untrained variations Differences in hardware, software, or antenna Observed signal strength changes over time 2004 Andreas Haeberlen, Rice University 15 Signal strength (new card) Calibration: New Hardware 256 i2=mi1+c 192 128 64 0 0 64 128 192

256 Signal strength (reference card) Approximate relationship between 'old' and 'new' values by a linear function Invert function, apply it to each observation 2004 Andreas Haeberlen, Rice University 16 Signal strength (11am) Calibration: Time-of-day 256 i2=mi1+c 192 Parameters 128

64 0 0 64 128 192 256 Signal strength (nighttime) Linear approximation works for time-ofday variations, too! Learn parameters using calibration 2004 Andreas Haeberlen, Rice University 17 Mobility: Markov chains

5% 5% 5% 60% 90% 5% 5% 5% 2004 Andreas Haeberlen, Rice University Goal: Track location while user is moving Problem: Markov localization tends to 'lag' for mobile agent Need a motion model for the user Use markov chain to model possible cellto-cell transitions 18

"It doesn't work any more!" Base stations were upgraded to 802.11a/b/g New IOS software New radio module 2.4 GHz radio module What we did: Configured new BSSIDs Ran calibration once System works, delivers good accuracy! 2004 Andreas Haeberlen, Rice University

19 Results: Mobility - Movie - Experiment on 09/23/04 (after 802.11a/b/g upgrade) 2004 Andreas Haeberlen, Rice University 20 Conclusions Topological localization delivers good accuracy with a reasonable training effort Gaussian sensor model is more robust and requires less training time than histogram-based model Training data can be adapted for use with different hardware and under

different conditions System is deployed in a large office building and in practical use 2004 Andreas Haeberlen, Rice University 21