SpotFi: Decimeter Level Localization Using WiFi

1 SpotFi: Decimeter Level Localization Using WiFiManikanta Kotaru, Kiran Joshi, Dinesh Bharadia, Sachin KattiStanford UniversityStanford, CA, USA{mkotaru, krjoshi, dineshb, paper presents the design and implementation of SpotFi,an accurate indoor Localization system that can be deployedon commodity wifi infrastructure. SpotFi only uses in-formation that is already exposed by wifi chips and doesnot require any hardware or firmware changes, yet achievesthe same accuracy as state-of-the-art Localization makes two key technical contributions. First, SpotFiincorporates super-resolution algorithms that can accuratelycompute the angle of arrival (AoA) of multipath componentseven when the access point (AP) has only three , it incorporates novel filtering and estimation tech-niques to identify AoA of direct path between the localiza-tion target and AP by assigning values for each path depend-ing on how likely the particular path is the direct path.}

2 Ourexperiments in a multipath rich indoor environment showthat SpotFi achieves a median accuracy of 40 cm and is ro-bust to indoor hindrances such as obstacles and Concepts Information systems Location based services;Sensornetworks; Global positioning systems; Networks Loca-tion based services;KeywordsIndoor Localization ; Wireless; wifi ; OFDM; CSI1. INTRODUCTIONI ndoor Localization systems Using wifi infrastructure sho-uld ideally satisfy the following three requirements: Deployable: They should be easily deployable on exist-ing commodity wifi infrastructure without requiring anyhardware or firmware changes at the access points (APs);they should only work with information like RSSI andCSI (Channel State Information) that is already exposedby commodity, deployed to make digital or hard copies of all or part of this work for personalor classroom use is granted without fee provided that copies are not made ordistributed for profit or commercial advantage and that copies bear this noticeand the full citation on the first page.

3 Copyrights for components of this workowned by others than the author(s) must be honored. Abstracting with credit ispermitted. To copy otherwise, or republish, to post on servers or to redistribute tolists, requires prior specific permission and/or a fee. Request permissions 15, August 17 - 21, 2015, London, United Kingdomc 2015 Copyright held by the owner/author(s). Publication rights licensed toACM. ISBN 978-1-4503-3542-3/15/08.. $ : Universal: They should be able to localize any target de-vice that has a commodity wifi chip and nothing should not require the target to have any other hard-ware, be it sensors such as accelerometers, gyroscopes,barometers, cameras, etc., or radios such as UWB, ultra-sound, Bluetooth LE, etc. Accurate: They should be accurate, ideally as accurate asthe best known Localization systems that use wireless sig-nals (even including those that do not satisfy the abovetwo requirements). To the best of our knowledge, themost accurate such Localization systems are ArrayTrack [1]and Ubicarse [2] and these systems achieve an accuracyranging from30 50cm in office environments.

4 Achiev-ing such accuracy would be the the above three requirements are satisfied, we can imagineindoor Localization becoming a ubiquitous service like GPSthat can be installed onalready deployed wifi infrastructureand made available to any device with a wifi , to the best of our knowledge, no system that sat-isfies all three requirements exists. RSSI based systems aredeployable and universal, but are not accurate; their medianaccuracy ranges from 2 4 m [3, 4, 5]. Recent techniquesthat rely on angle of arrival (AoA) estimation such as Ar-rayTrack and LTEye [6] are accurate and universal but arenot deployable as they require hardware modifications. Forexample, ArrayTrack uses six to eight antennas whereas typ-ical APs have three, and LTEye requires motorized rotatingantennas which are not found on deployed APs. Other tech-niques that combine inputs from multiple sensors such asUbicarse [2] are accurate and deployable but not universal;they require that the target device has access to other sens-ing modes such as accelerometers, gyroscopes, etc.

5 , whichwould not be found on many devices ( , laptops, Nestthermostats). We refer the reader to Sec. 2 for a more de-tailed survey of related work and where different systems liewith respect to the above main contribution of this paper is a Localization sys-tem that satisfies all the three requirements above. We presentSpotFi, an indoor Localization system that provides a medianaccuracy of 40 cm Using standard, commodity off-the-shelfWiFi radios, which is comparable to the best performing sys-tems such as ArrayTrack [1] and Ubicarse [2]. SpotFi re-quires no hardware or baseband firmware changes/additionsat the APs, nor does it need any calibration or fingerprintingof the environment. SpotFi s Localization targets also haveminimal requirements, they only require a commodity incorporates three techniques that enable it to achievethis combination of accuracy and deployment simplicity: Super-resolution AoA Estimation: The first componentof SpotFi is a super-resolution AoA estimation algorithm, , it accurately resolves all the AoAs of the indoor mul-tipath in spite of Using just three antennas which is stan-dard in wifi deployments today.

6 The number of anten-nas limits the number of multipath components that onecan resolve. As prior work has noted [1, 2, 7, 8, 9], themore antennas there are, more multipath AoAs can beresolved more accurately. Our insight is that the multi-path not only creates measurable changes in CSI acrossantennas because of AoA but also affects CSI across sub-carriers because of time of flight (ToF, time taken by thesignal to reach the AP from the Localization target). Using this fact, instead of just estimating AoA, SpotFicombines CSI values across subcarriers and antennas tojointly estimate AoA and ToF of each path. In the pro-cess, SpotFi creates a virtual sensor array with numberof elements greater than the number of multipath com-ponents, thus overcoming the constraint of limited an-tennas. Our unique insight here is that these joint AoAand ToF estimation algorithms can be implemented us-ing the CSI information that is already exposed by thecommodity wifi cards.

7 Using the AoA and ToF parame-ters estimated from CSI, we empirically demonstrate that,in commodity wifi deployments, although the estimatedToF values are different from the absolute ToFs, the jointestimation procedure provides AoA accuracy that is com-parable to systems that require twice as many antennas [8]or non-standard configurations such as rotating antennasused in radar [6, 2]. Robust Direct Path Identification: SpotFi aims to findthe AoA of the direct path component in the multipathsignal from the target. However among the AoA esti-mates from the previous algorithm, the one correspond-ing to the direct path may be erroneous or may not evenexist due to several practical reasons such as noisy CSI,obstructed targets, weak signal strength from the targetand so on. The second key component of SpotFi is anovel algorithm that assigns values for each path depend-ing on the likelihood that the particular path is the directpath.

8 This metric assignment algorithm enables SpotFi toeliminate AoA estimates that are very likely to be in errorand not belonging to the direct path component, therebyavoiding making large errors in Localization . Localization : The final step is a Localization algorithmthat incorporates both the direct path AoA estimate fromthe above two steps as well as RSSI information avail-able from each of the APs to calculate the location of thetarget. Our key contribution here is a framework that ap-propriately weights the information from different APs totake into account how likely it is that the AoA measure-ment reported by each AP corresponds to the actual directpath between the target and that AP. This weighting of in-formation enables SpotFi to select information from APswith higher confidence metric and improve implemented SpotFi Using Intel 5300 commodity WiFicards. We strived to evaluate it under the same environmentsas the best performing systems ArrayTrack and Ubicarse [1,2]; we describe the testbed in Sec.

9 4. Our experiments showthat SpotFi achieves a median Localization error of 40 cm,and the 80thpercentile error is m. To put these num-bers in context, the best performing prior system achievesa median error of 40 cm Using 6 antennas per AP, whereasour APs have only three. We also show that SpotFi works ro-bustly in challenging scenarios; for example, it achieves verygood accuracy even when the target has strong direct pathsto only a couple of APs. Finally, we also show that SpotFiis lightweight and requires CSI measurements for only tenpackets from the target to localize RELATED WORKI ndoor Localization Using wireless infrastructure is a well-studied problem. There is a large body of research which,for conciseness, we classify into four types: RSSI based ,fingerprinting based , antenna array based , and time based approaches:This class of systems measuresthe RSSI from the target at multiple APs, combines themvia triangulation along with a propagation model to locatethe target [3, 10, 4, 5, 11, 12, 13].

10 These systems are easyto deploy as RSSI values are easily available in current the best known systems in this space tend to achievea median accuracy of around 2 4 m [3, 4], and the 80thpercentile error is often as high as 5 m due to insufficientmodeling of RSSI which in practice depends not only on thelocation of the target but also on the changing based approaches:The idea of these ap-proaches is that one would collect fingerprints such as thevector of RSSIs from a specific location to all the APs inrange, and if in the future a target were at the same location,it would exhibit the same fingerprint, enabling us to local-ize [14, 15, 16, 17, 18, 19, 20, 21, 22]. The best known suchsystems provide around m of median accuracy [14], andtail accuracy on the order of m. However these systemsare difficult to deploy since they require an expensive and re-curring fingerprinting operation any time there are changesin the environment ( , when the furniture is moved).