Accurate and Efficient Indoor Location by Dynamic Warping in Sequence-Type Radio-map

Abstract

An efficient way to overcome the calibration challenge and RSS dynamics in radio-map-based indoor localization is to collect radio signal strength (RSS) along indoor paths and conduct localization by sequence matching. But such sequence-based indoor localization suffers problems including indoor path combinational explosion, random RSS miss-of-detection during user movement, and user moving speed disparity in online and offline phases. To address these problems, this paper proposes an undirected graph model, called WarpMap to efficiently calibrate and store the sequence-type radio-map. It reduces RSS sequence signature storage complexity from O(2N) to O(N) where N is the number of path crosses. An efficient on-line candidate path extraction algorithm is developed in it to find a set of the most possible candidate paths for matching with the on-line collected RSS sequence. Then, to determine the user's exact location, a sub-sequence dynamic time warping (SDTW) algorithm is proposed, which matches the online collected RSS sequence with the sequential RSS signatures of the candidate paths. We show the SDTW algorithm is highly efficient and adaptive, which localizes user without backtracking of warping path. Extensive experiments in office environments verified the efficiency and accuracy of WarpMap, which can be calibrated within thirty minutes by one person for 1100m2 area and provides overall nearly 20% accuracy improvements than the state-of-the-art of radio-map method.

References

1. J. C. Aguilar Herrera, P. G. Plöger, A. Hinkenjann, J. Maiero, M. Flores, and A. Ramos. Pedestrian Indoor Positioning Using Smartphone Multi-sensing, Radio Beacons, User Positions Probability Map and IndoorOSM Floor Plan Representation. 2014.
2. P. Bahl and V. Padmanabhan. RADAR: an in-building RF-based user location and tracking system. In IEEE INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, volume 2, pages 775--784 vol.2, 2000.
3. D. U. Chuan-Ming. Application of baidu map api in small geographic information system. Geomatics 8 Spatial Information Technology, 2011.
4. X. Geng, Y. Wang, H. Feng, and Z. Chen. Hybrid radio-map for noise tolerant wireless indoor localization. In 2014 IEEE 11th International Conference on Networking, Sensing and Control (ICNSC), pages 233--238, Apr. 2014.
5. I. Haque and C. Assi. Profiling-Based Indoor Localization Schemes. IEEE Systems Journal, Early Access Online, 2013.
6. R. Harle. A Survey of Indoor Inertial Positioning Systems for Pedestrians. IEEE Communications Surveys Tutorials, 15(3):1281--1293, 2013.
7. F.J. Harris. On the use of harmonic analysis with the discrete fourier transform. Proceedings of the IEEE, 66(1):51--83, 1978.
8. J. Hightower and G. Bordello. UbiComp 2004: Ubiquitous Computing: 6th International Conference, Nottingham, UK, September 7--10, 2004. Proceedings, chapter Particle Filters for Location Estimation in Ubiquitous Computing: A Case Study, pages 88--106. Springer Berlin Heidelberg, Berlin, Heidelberg, 2004.
9. V. Honkavirta, T. Perälä, S. Ali-Löytty, and R. Piché. A comparative survey of wlan location fingerprinting methods. In WPNC, pages 243--251, 2009.
10. Y. Ji, S. Biaz, S. Wu, and B. Qi. Impact of Building Environment on the Performance of Dynamic Indoor Localization. In Wireless and Microwave Technology Conference, 2006. WAMICON '06. IEEE Annual, pages 1--5, Dec. 2006.
11. I. T. Jolliffe. Principal Component Analysis. Springer-Verlag, 1986.
12. T. King, S. Kopf, T. Haenselmann, C. Lubberger, and W. Effelsberg. Compass: A probabilistic indoor positioning system based on 802.11 and digital compasses. In Proceedings of the 1st International Workshop on Wireless Network Testbeds, Experimental Evaluation 8 Characterization, WiNTECH '06, pages 34--40, New York, NY, USA, 2006. ACM.
13. M. Levandowsky and D. Winter. Distance between sets. Nature, 234(5323):34--35, 1971.
14. S. Z. Li and A. Jain, editors. Encyclopedia of Biometrics, chapter Dynamic Time Warping (DTW), pages 231--231. Springer US, Boston, MA, 2009.
15. C.-C. Lo, L.-Y. Hsu, and Y.-C. Tseng. Adaptive radio maps for pattern-matching localization via inter-beacon co-calibration. Pervasive Mob. Comput., 8(2):282--291, Apr. 2012.
16. G. Map. http://www.google.com/maps. 2018.
17. M. Molina-García, J. Calle-Sánchez, J. I. Alonso, A. Fernández-Durán, and F. B. Barba. Enhanced In-Building Fingerprint Positioning Using Femtocell Networks. Bell Labs Technical Journal, 18(2):195--211, Sept. 2013.
18. M. Müller. Information Retrieval for Music and Motion. Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2007.
19. L. Ni, Y. Liu, Y. C. Lau, and A. Patil. LANDMARC: indoor location sensing using active RFID. In Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, 2003. (PerCom 2003), pages 407--415, 2003.
20. J.-O. Nilsson, A. K. Gupta, and P. Handel. Foot-mounted inertial navigation made easy. In International Conference on Indoor Positioning and Indoor Navigation, volume 27, page 30th, 2014.
21. J.-O. Nilsson, I. Skog, P. Handel, and K. Hari. Foot-mounted INS for everybody - an open-source embedded implementation. In Position Location and Navigation Symposium (PLANS), 2012 IEEE/ION, pages 140--145, Apr. 2012.
22. S. J. Pan, J. T. Kwok, Q. Yang, and J. J. Pan. Adaptive Localization in a Dynamic WiFi Environment Through Multi-view Learning. In Proceedings of the 22Nd National Conference on Artificial Intelligence - Volume 2, AAAI'07, pages 1108--1113, Vancouver, British Columbia, Canada, 2007. AAAI Press.
23. H. Sakoe. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, 26:43--49, 1978.
24. P. Scholl, S. Kohlbrecher, V. Sachidananda, and K. Van Laerhoven. Fast indoor radio-map building for RSSI-based localization systems. In 2012 Ninth International Conference on Networked Sensing Systems (TNSS), pages 1--2, 2012.
25. M.J. Shensa. Discrete wavelet transform: Wedding the a trous and mallat algorithms. IEEE Transactions on Signal Processing, 40(10):2464--2482, 1992.
26. Y. Shu, K. G. Shin, T. He, and J. Chen. Last-mile navigation using smartphones. In Proceedings of the 21st Annual International Conference on Mobile Computing and Networking, MobiCom '15, pages 512--524, New York, NY, USA, 2015. ACM.
27. L. Song and Y. Wang. Multiple target counting and tracking using binary proximity sensors: Bounds, coloring, and filter. In Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '14, pages 397--406, New York, NY, USA, 2014. ACM.
28. X. Su and T. M. Khoshgoftaar. A survey of collaborative filtering techniques. Advances in Artificial Intelligence, 2009(12):4, 2009.
29. Y. Tian, R. Gao, K. Bian, F. Ye, T. Wang, Y. Wang, and X. Li. Towards ubiquitous indoor localization service leveraging environmental physical features. In 2014 Proceedings IEEE TNFOCOM, pages 55--63, Apr. 2014.
30. C. Vamos and M. Craciun. Polynomial Fitting. Springer Netherlands, 2012.
31. H. Wang, S. Sen, A. Elgohary, M. Farid, M. Youssef, and R. R. Choudhury. No need to war-drive: Unsupervised indoor localization. In Proceedings of the 10th International Conference on Mobile Systems, Applications, and Services, MobiSys '12, pages 197--210, New York, NY. USA, 2012. ACM.
32. Z. 1. Wu, C. h. Li, J. K. y. Ng, and K. R. p. h. Leung. Location Estimation via Support Vector Regression. IEEE Transactions on Mobile Computing, 6(3):311--321, Mar. 2007.
33. Z. Xiao, H. Wen, A. Markham, and N. Trigoni. Lightweight map matching for indoor localisation using conditional random fields. In IPSN-14 Proceedings of the 13th International Symposium on Information Processing in Sensor Networks, pages 131--142, Apr. 2014.
34. Z. Yang and Y. W. and. Adamap: Adaptive radiomap for indoor localization. In Ad-hoc, Mobile, and Wireless Networks - 14th International Conference, ADHOC-NOW 2015, Athens, Greece, June 29 - July 1, 2015, Proceedings, pages 134--147, 2015.
35. Z. Yang, C. Wu, and Y. Liu. Locating in fingerprint space: Wireless indoor localization with little human intervention. In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, Mobicom '12, pages 269--280, New York, NY, USA, 2012. ACM.
36. J. Yin, Q. Yang, and L. Ni. Learning Adaptive Temporal Radio Maps for Signal-Strength-Based Location Estimation. IEEE Transactions on Mobile Computing, 7(7):869--883, 2008.
37. J. Yin, Q. Yang, and L. M. Ni. Adaptive temporal radio maps for indoor location estimation. In 3rd IEEE International Conference on Pervasive Computing and Communications (PerCom 2005), 8--12 March 2005, Kauai Island, HI, USA, pages 85--94, 2005.
38. M. Youssef and A. Agrawala. The horus wlan location determination system. In Proceedings of the 3rd International Conference on Mobile Systems, Applications, and Services, MobiSys '05, pages 205--218, New York, NY, USA, 2005. ACM.
39. F. Zampella, A. Jimenez R, and F. Seco. Robust indoor positioning fusing PDR and RF technologies: The RFID and UWB case. In 2013 International Conference on Indoor Positioning and Indoor Navigation (IPIN), pages 1--10, Oct. 2013.