SiFi: Pushing the Limit of Time-Based WiFi Localization Using a Single Commodity Access Point

Abstract

There has been a booming interest in developing WiFi localization using multi-antenna (MIMO) access points (APs). Recent advances have demonstrated promising results that break the meter-accuracy barrier using commodity APs. Yet these state-of-the-art solutions require either multiple APs that are not necessarily available in practice, or multiple-channel measurements that disrupt normal data communication. In this paper, we present SiFi, a single AP-based indoor localization system that for the first time achieves sub-meter accuracy with a single channel only. The SiFi design is based on a key observation: with MIMO, the multiple (typically three) antennas of an AP are frequency-locked; although the accurate Time-of-Arrival (ToA) estimation on commodity APs is fundamentally limited by the imperfect time and frequency synchronization between the transmitter and receiver, there should be only one value for the ToA distortion that can cause three direct-path ToAs of the antennas to intersect at a single point, i.e., the position of the target. We develop the theoretical foundations of SiFi and demonstrate its realworld implementation with off-the-shelf WiFi cards. Our implementation introduces no hardware modification and is fully compatible with concurrent data transmission. It achieves a median accuracy of 0.93 m, which significantly outperforms the best known single AP single channel solution.

References

1. 2009. IEEE 802.11n-2009 standard. (2009). http://standards.ieee.org/getieee802/download/802.11n-2009.pdf.
2. 2016. Wi-Fi Tags. (2016). http://www.ekahau.com/real-time-location-system/technology/wi-fi-tags.
3. Fadel Adib, Zachary Kabelac, Dina Katabi, and Robert C Miller. 2014. 3D Tracking via Body Radio Reflections.. In Proc. of USENIX NSDI.
4. Marcello Ascione, Aniello Buonanno, Michele D'Urso, Leopoldo Angrisani, and Rosario Schiano Lo Moriello. 2013. A new measurement method based on music algorithm for through-the-wall detection of life signs. IEEE Transactions on Instrumentation and Measurement 62, 1 (2013), 13--26.
5. Paramvir Bahl and Venkata N Padmanabhan. 2000. RADAR: An In-Building RF-based User Location and Tracking System. In Proc. of IEEE INFOCOM.
6. Arthur J Barabell. 1983. Improving the resolution performance of eigenstructure-based direction-finding algorithms. In Proc. of IEEE ICASSP.
7. Gilles Celeux and Gérard Govaert. 1995. Gaussian parsimonious clustering models. Pattern recognition 28, 5 (1995), 781--793.
8. Yuchi Chen, Wei Gong, Jiangchuan Liu, and Yong Cui. 2018. I Can Hear More: Pushing the Limit of Ultrasound Sensing on Off-the-Shelf Mobile Devices. In Proc. of IEEE INFOCOM.
9. Krishna Chintalapudi, Anand Padmanabha Iyer, and Venkata N Padmanabhan. 2010. Indoor Localization Without the Pain. In Proc. of ACM MobiSys.
10. Baron Gaspard Riche de Prony. 1795. Essai éxperimental et analytique: sur les lois de la dilatabilité de fluides élastique et sur celles de la force expansive de la vapeur de ląŕalkool, a différentes temperatures. Journal de ląŕécole polytechnique 1, 22 (1795), 24--76.
11. Haishi Du, Ping Li, Hao Zhou, Wei Gong, Gan Luo, and Panglong Yang. 2018. WordRecorder: Accurate Acoustic-based Handwriting Recognition Using Deep Learning. In Proc. of IEEE INFOCOM.
12. Tolga Eren, OK Goldenberg, Walter Whiteley, Yang Richard Yang, A Stephen Morse, Brian DO Anderson, and Peter N Belhumeur. 2004. Rigidity, computation, and randomization in network localization. In Proc. of IEEE INFOCOM.
13. Xiaoyi Fan, Wei Gong, and Jiangchuan Liu. 2017. i2tag: RFID mobility and activity identification through intelligent profiling. ACM Transactions on Intelligent Systems and Technology (TIST) 9, 1 (2017), 5.
14. Jon Gjengset, Jie Xiong, Graeme McPhillips, and Kyle Jamieson. 2014. Phaser: Enabling Phased Array Signal Processing on Commodity WiFi Access Points. In Proc. of ACM MobiCom.
15. W. Gong, S. Chen, J. Liu, and Z. Wang. 2018. MobiRate: Mobility-Aware Rate Adaptation Using PHY Information for Backscatter Networks. In Proceedings of IEEE INFOCOM.
16. Wei Gong and Jiangchuan Liu. 2017. Robust Indoor Wireless Localization Using Sparse Recovery. In Proc. of IEEE ICDCS.
17. Daniel Halperin, Wenjun Hu, Anmol Sheth, and David Wetherall. 2011. Tool release: gathering 802.11 n traces with channel state information. ACM SIGCOMM Computer Communication Review 41, 1 (2011), 53--53.
18. Guangjie Han, Huihui Xu, Trung Q Duong, Jinfang Jiang, and Takahiro Hara. 2013. Localization algorithms of wireless sensor networks: a survey. Telecommunication Systems (2013), 1--18.
19. Yingbo Hua and Tapan K Sarkar. 1990. Method for Estimating Parameters of bxponentially Damped/Undamped Sinusoids in Noise. IEEE Transactions on Acoustics, Speech and Signal Processing 38, 5 (1990), 814--824.
20. Suman Jana and Sneha Kumar Kasera. 2008. On Fast and Accurate Detection of Unauthorized Wireless Access Points Using Clock Skews. In Proc. of ACM MobiCom.
21. Manikanta Kotaru, Kiran Joshi, Dinesh Bharadia, and Sachin Katti. 2015. Spotfi: Decimeter Level Localization Using WiFi. In Proc. of ACM SIGCOMM.
22. Swarun Kumar, Stephanie Gil, Dina Katabi, and Daniela Rus. 2014. Accurate Indoor Localization With Zero Start-up Cost. In Proc. of ACM MobiCom.
23. Swarun Kumar, Ezzeldin Hamed, Dina Katabi, and Li Erran Li. 2014. LTE Radio Analytics Made Easy and Accessible. In Proc. of ACM SIGCOMM.
24. Wenjing Liao and Albert Fannjiang. 2016. MUSIC for Single-Snapshot Spectral Estimation: Stability and Super-resolution. Applied and Computational Harmonic Analysis 40, 1 (2016), 33--67.
25. Alex T Mariakakis, Souvik Sen, Jeongkeun Lee, and Kyu-Han Kim. 2014. SAIL: Single Access Point-Based Indoor Localization. In Proc. of ACM MobiSys.
26. Hariharan Rahul, Haitham Hassanieh, and Dina Katabi. 2011. SourceSync: A Distributed Wireless Architecture for Exploiting Sender Diversity. In Proc. of ACM SIGCOMM.
27. Hariharan Rahul, Swarun Kumar, and Dina Katabi. 2012. MegaMIMO: Scaling Wireless Capacity with User Demands. In Proc. of ACM SIGCOMM.
28. Ralph O Schmidt. 1986. Multiple emitter location and signal parameter estimation. IEEE Transactions on Antennas and Propagation 34, 3 (1986), 276--280.
29. Souvik Sen, Jeongkeun Lee, Kyu-Han Kim, and Paul Congdon. 2013. Avoiding Multipath to Revive Inbuilding WiFi Localization. In Proc. of ACM MobiSys.
30. Michael Speth, Stefan A Fechtel, Gunnar Fock, and Heinrich Meyr. 1999. Optimum receiver design for wireless broad-band systems using OFDM. I. IEEE Transactions on Communications 47, 11 (1999), 1668--1677.
31. Petre Stoica and Nehorai Arye. 1989. MUSIC, Maximum Likelihood, and Cramer-Rao Bound. IEEE Transactions on Acoustics, Speech and Signal Processing 37, 5 (1989), 720--741.
32. Petre Stoica and Randolph L Moses. 1997. Introduction to spectral analysis. Vol. 1. Prentice hall Upper Saddle River.
33. Deepak Vasisht, Swarun Kumar, and Dina Katabi. 2016. Decimeter-Level Localization with a Single WiFi Access Point. In Proc. of USENIX NSDI.
34. Jiang Xiao, Zimu Zhou, Youwen Yi, and Lionel M Ni. 2016. A survey on wireless indoor localization from the device perspective. ACM Computing Surveys (CSUR) 49, 2 (2016), 25.
35. Yaxiong Xie, Zhenjiang Li, and Mo Li. 2015. Precise Power Delay Profiling with Commodity WiFi. In Proc. of ACM MobiCom.
36. Jie Xiong and Kyle Jamieson. 2013. ArrayTrack: A Fine-Grained Indoor Location System. In Proc. of USENIX NSDI.
37. Jie Xiong, Karthikeyan Sundaresan, and Kyle Jamieson. 2015. ToneTrack: Leveraging Frequency-Agile Radios for Time-Based Indoor Wireless Localization. In Proc. of ACM MobiCom.
38. Zheng Yang, Yunhao Liu, and X-Y Li. 2009. Beyond trilateration: On the localizability of wireless ad-hoc networks. In Proc. of IEEE INFOCOM.
39. Zheng Yang, Chenshu Wu, and Yunhao Liu. 2012. Locating in Fingerprint Space: Wireless Indoor Localization with Little Human Intervention. In Proc. of ACM MobiCom.
40. Zheng Yang, Zimu Zhou, and Yunhao Liu. 2013. From RSSI to CSI: Indoor localization via channel response. ACM Computing Surveys (CSUR) 46, 2 (2013), 25.
41. Moustafa Youssef and Ashok Agrawala. 2005. The Horus WLAN Location Determination System. In Proc. of USENIX MobiSys.

Index Terms

• Networks

  • Network services

    • Location based services

  • Network types

    • Mobile networks