Power Point Presentation - Radar 04

RADAR: an in-building RF-based location and tracking system. & Enhancements to the RADAR user location and tracking system Paramvir Bahl, Venkata Padmanabhan and Anand Balachandran

by Pandurang Kamat 11/07/2003

About the Authors § Paramvir (“Victor”) Bahl (Microsoft Research) § Ph.D. from University of Massachusetts Amherst § senior researcher and a manager in the Systems and Networking Research Group. § wide interests in mobile computing and wireless networking : low-power RF comm.; ubiquitous wireless Internet access/services; indoor location determination; self organizing, self configuring multi-hop wireless networks; and real-time audiovisual wireless communications. § founder of ACM SIGMOBILE, ACM Mobile Computing and Communications Review and MobiSys § Over 50 papers and 34 patents in the wireless, communications and DSP domains

§ Venkata Padmanabhan (Microsoft Research) § Ph.D. from UC Berkeley. § wide-area and wireless networking, Web performance, and mobile computing. § involved in projects on network performance measurement, network tomography, Internet geography, peer-to-peer networking, and wireless user tracking.

§ Anand Balachandran (UCSD) : Joining Intel § Computer Science Ph.D. student. (background in Chemical Engineering) § research interests : wireless networking; wireless Internet; infrastructure and ad-hoc networks; and mobile computing.

Outline § The problem of locating users inside buildings § Related Work § The RADAR system § Performance of the basic RADAR system § Enhancements to the RADAR system. § Implementation Insights § Concluding Remarks

Introduction § The goal is to enable the mobile user to interact effectively with his/her surroundings § Granularity of the required location information varies for applications § coarse grained : nearby printer § fine grained : book in a library

Related Work § IR-based § Active Badge system § badge emits unique IR signal every 10 seconds § sensors placed at known locations in the building pick up the unique Ids and relay to centralized location manager software § Pros: provides accurate information § Cons: § Scales poorly due to limited IR range § Installation and maintenance costs for special hardware § Poor performance in presence of sunlight (rooms with windows)

§ RF based § § § §

3D-iD system by Pinpoint Corp. Antennas emit RF signals at 2.4 GHz, tags respond with the ID code. Location is triangulated based on multiple antennas Cons: § High cost § Specialized hardware

Related Work § Wide-area cellular based § signal attenuation, Angle of Arrival (AOA), Time Difference of Arrival (TDOA) § indoor effectiveness reduced due to multiple reflections suffered by the RF signal and inability of hardware to provide fine-grain time synchronization

§ Others § using ultrasound signals, magnetic fields etc. § GPS: Ineffective indoors § drawbacks: specialized hardware, high cost and range limited

The RADAR system § Software system built on a deployment of off-the-shelf wireless LAN technology. § In an RF network, the energy level or signal strength (SS) of a packet is a function of the receiver’s (mobile user’s) location and hence can be used to infer the user location with respect to the Access Points (APs). § A Radio Map of the building is created. This is a database of marked locations in the building and the observed (or estimated) signal strength of the beacons signal strength of the beacons emanating from the APs as recorded at these locations. § Example entry in Radio Map : (x, y, z, ssi (i =1..n)) § where (x, y, z) is the physical coordinates of the location where the signal is recorded and ssi is the signal strength of the beacon signal emanating from the ith AP.

Creating the Radio Map Method 1 : § A mobile user walks around the building and at different locations records the physical co-ordinates and signal strengths of the beacon packets from each AP within range. Method 2 : § The radio map is constructed using a mathematical model of indoor RF propagation § Method 1 is “more” accurate but cumbersome.

Locating the User § The mobile measures the signal strength of each of the APs within range. It then searches through the Radio Map database to determine the signal strength tuple that best matches the signal strengths it has measured. § Nearest Neighbor in Signal Space (NNSS) algorithm is the search technique. § The NNSS algorithm computes the Euclidean distance (in signal space) between each SS tuple in the Radio Map (ss1, ss2, ss3) and the measured SS tuple (ss’1 , ss’2 , ss’3). sqrt( (ss1 - ss’1)2 + (ss2 - ss’2)2 + (ss3 - ss’3) 2 ) § The tuple minimizing the Euclidean distance is the winner. § NNSS-Avg. picks k-neighbors and averages the location (better estimate)

The early RADAR § Hardware from Wavelan (NICs). Base stations were PCs with “Digital Roamabout” (using Wavelan NIC) § Operates in 2.4 Ghz ISM band. § Data rate up to 2 Mbps § The Base stations had FreeBSD 3.0. The wavelan driver extracts SS and SNR info from firmware. § The mobile host sends out udp packets that are picked up by base stations in pre-deployment stage. § Tuples < t, bs, ss > § The BS also records following info. Sent by mobile host : § d : orientation of host antenna (only 4 possibilities considered)

§ Unified tuple (x, y, d, ss, snr) Used mean ss and snr

Empirical Method § About 20 samples collected for (70 locations * 4 direction). § Empirical: Pick one tuple from the database and use NNSS to predict its location. Then compare to stored value. Other methods : § Random: Pick a random location… (really !!) § Strongest BS: Base station recording strongest signal at run-time

Improving Empirical Method § Average from multiple neighbors § Not too beneficial beyond 3 neighbor avg.

Improving Empirical Method contd. § Increased data points § For this experiment about 40 data points would have been enough. § Not much benefit offered beyond a threshold.

§

Impact of number of samples at runtime § §

§

Impact of user orientation §

§

1 sample = only 30% worse error distance 2 samples mean = 11 % worse Better to have apriori, directional samples

Tracking the mobile user. § §

sequence of “tracking stationary user” sliding window of 10 samples

Radio Propogation Model Method § Problems with Empirical approach: § §

Effort required May need to repeat effort on moving BS.

§ Multipath phenomenon §

walls, floors, other obstructions..

§ Rayleigh fading model § Dominant LOS component ignored

§

Rician distribution model § §

§

LOS component given due weightage. complex and difficult to model

Wall Attenuation Factor (WAF) model § §

flexible with different building layouts. considers only walls as factors in attenuation. Ignores floors.

Wall Attenuation Factor Model

§ P(d0) : signal power at reference distance § d : Trx - Rcv distance § C : max # of walls upto which AF makes a difference § n : rate at which path loss increases with distance § nW : # of walls between Trx and Rcv § WAF : Wall Attenuation Factor

§ Experimentally determine: § WAF = 3.1 dBm § C=4 § n and P(d0)

Wall Attenuation Factor Model contd. § Signal strength vs. T-R distance

Wall Attenuation Factor Model contd.

§ Results with using Radio propagation model § 50th percentile: 4.3 m resolution as compared to 2.94 m of empirical and 8.16 Strongest BS. § 25th percentile: 1.86 m resolution as compared to 1.92 m of empirical and 4.94 Strongest BS.

New RADAR Testbed § Hardware (APs and NICs) from Aironet Communications. § Operates in 2.4 Ghz ISM band. § IEEE802.11b network with data rate up to 11Mbps.

New RADAR testbed contd. § new (Aironet) vs. old (WaveLAN) Testbed § 3 APs considered. § Long Tail – due to Signal Aliasing.

Fig: CDF of the Error Distance

Effect of Number of Access Points § Little benefit beyond 3 APs § Noise in SS limits accuracy.

Fig: Impact of the number of APs on the error distance.

RADAR Enhancements § Continuous user tracking § Profiling the environment § Testing for multiple floors

Continuous User Tracking § Use past-location information to improve accuracy of future guesses. § Physical contiguity constraint § Also used to anticipate handoffs in cellular networks.

§ Positive side effect: problem of aliasing is alleviated. § Viterbi-like algorithm § Original Viterbi algorithm is used by receivers to determine the most likely message transmitted over noisy channel.

Viterbi-like algorithm § Each time ss tuple is obtained by mobile host, NNSS is run to determine k neighbors § A history of depth h (latest h entries) of such k-sets is maintained. § This collection can be viewed as a graphs shown in fig 1; with edges only between vertices in consecutive sets. § Edges weighted using Euclidean distance as metric. § The shortest path, using least weighted edges, is the user’s most likely trajectory. § Lag of h ss samples before guessing.

Profiling the environment § The problem: § RF signal reflection, defractions and scattering create a hostile environment for SS based location systems. § The Multipath phenomenon. § The People factor.

§ The solution: § Multiple Radio Maps for multiple environments. § Use APs to calibrate the environment. § Question: how to we choose the right map in real time ?

Profiling the environment (contd.) § Each AP records signal strength samples extracted from beacons and packets received from other APs within range. § For each other AP, say APi, it computes the mean, mi, of the received signal strength samples over a sliding window w samples. § It uses mi together with the pre-computed mean ( e) and standard deviation ( e) of the signal strength corresponding to each environmental state, e, to estimate the likelihood that the received signal strength samples are in conformance with that environmental state. § Assume Gaussian (normal) distribution, N( e, e) for the signal strength. § For each environmental state e, the likelihood of match determined by pair of APs are multiplied together to obtain an overall estimate of the likelihood of the environmental state being e. § The environment emax with the highest likelihood of match is then guessed to be the true environmental state.

Profiling the environment (contd.)

Profiling the environment (contd.) § Performance § Experiment done for “busy” and “non-busy” hours. § Marked improvement in “error distance”.

RADAR on Multiple Floors § 3 floor experiment § Took points with same (x,y) on each floor. § RADAR works well in multi-floor environment. § Found that aliasing is not that big an issue in vertical space.

Implementation Insights § Effects of Multiple Channels § Neighboring APs are on different channels (frequency re-use requirements) § Mobile has to scan all channels in “active-scan” mode of beacons. § The overhead for switching and waiting can be significant.

§ Solution: § Synchronize the mobile APs and do “just-in-time” channel switching.

Implementation Insights § WiLIB § Created WiLIB, a software library to provide user-level access to underlying wireless hardware. § Access signal strength, noise floor at Tx and Rx, MAC address to Tx. § Provides list of APs from where beacon can be heard by WNIC. § WNIC can be configured for a specific channel.

Concluding Remarks § We looked at the basic RADAR system. § Analyzed empirical and radio model methods of preparing radio maps § Looked at the enhancements to the basic system. § A continuous user tracking technique using a viterbi-like algorithm to disambiguate user locations and alleviate signal aliasing. § An Access Point based environmental profiling scheme that’s resilient to variations in radio propagation environment. § Experimental validation in multi-floor environment. § Real world: § Highly available RF propogation environment. § Cost of APs->”light” APs