research-article

Practical approximate indoor nearest neighbour locating with crowdsourced RSSIs

Authors:

Xiaochun YangAuthors Info & Claims

World Wide Web, Volume 24, Issue 3

Pages 747 - 779

https://doi.org/10.1007/s11280-021-00868-5

Published: 01 May 2021 Publication History

Abstract

In the indoor space, finding the nearest neighbour is of great importance in location-based services. Received Signal Strength Indication (RSSI) has received much attention due to its simplicity and compatibility with existing hardware, which has been widely used for indoor localization. Existing indoor nearest neighbour search methods are based on the real walking distance, which need ground survey and much labor work to measure many real distances. Crowdsourcing is a low-cost and efficient way to collect the RSSI of indoor space without expert surveyors and designated coordinates for RSSI collection points. The crowdsourced RSSIs can reflect the location of indoor objects and RSSI-based localization method is the simplistic method as it needs low hardware requirements, low deployment cost and no survey indoor distance. So we study how to search the nearest neighbour of indoor objects with crowdsourced RSSIs. To address this problem, we propose a graph with interval weights, called I-graph, which can connect the RSSIs and represent the topology of indoor space. We also construct a search tree index D-tree, which can index the graph with interval weights and search the nearest neighbour objects efficiently. We also propose a novel distance metric for RSSI and study the relationship between the RSSI distance and the indoor distance. To locate nearest neighbour of indoor objects with crowdsourced RSSIs, we devise efficient search algorithms and pruning strategies for computing the nearest neighbour query. We demonstrate the efficiency and effectiveness of the proposed solution through extensive experiments with two real data sets.

References

[1]

Bahl P and Padmanabhan VN Radar: an in-building rf based user location and tracking system IEEE 2000 2 775-784

[2]

Chen, Y., Kobayashi, H.: Signal strength based indoor geolocation. In: IEEE International Conference on Communications (2002)

[3]

Elhamshary, M.M., Alzantot, M.F., Youssef, M.: Justwalk: A crowdsourcing approach for the automatic construction of indoor floorplans. IEEE Trans. Mob. Comput.: 1–1 (2018)

[4]

Fernando, S., Christian, P., Jimenez, A.R., Wolfram, B.: Improving rfid-based indoor positioning accuracy using gaussian processes. In: International Conference on Indoor Positioning and Indoor Navigation (IPIN), vol. 1, pp 1–8. IEEE (2010)

[5]

Hasani M, Talvitie J, Sydanheimo L, Lohan ES, and Ukkonen L Hybrid wlan-rfid indoor localization solution utilizing textile tag IEEE Antennas Wirel. Propag. Lett. 2015 14 1358-1361

[6]

Hightower, J., Borriello, G., Want, R.: Spoton: An indoor 3d location sensing technology based on rf signal strength. UW CSE Technical Report (2000)

[7]

Hua, L., Xin, C., Jensen, C.: A foundation for efficient indoor distance-aware query processing. In: ICDE, vol. 41, pp. 438–449 (2012)

[8]

Jekabsons, G., Zuravlyov, V.: Refining wi-fi based indoor positioning. AICT :87–95 (2010)

[9]

Jensen, C., Kolar, J., Pedersen, T.B., Timko, I.: Nearest neighbor queries in road networks. In: Proceedings of the 11th ACM International Symposium on Advances in Geographic Information Systems, pp. 1–8. ACM (2003)

[10]

Kiers, M., Krajnc, E., Dornhofer, M., Bischof, W.: Evaluation and improvements of an rfid based indoor navigation system for visually impaired and blind people. In: International Conference on Indoor Positioning and Indoor Navigation (2011)

[11]

Kolahdouzan, M., Shahabi, C.: Voronoi-based k nearest neighbor search for spatial network databases. In: VLDB, vol. 30, pp. 840–851 (2004)

[12]

Luo, C., Hong, H., Chan, M.C.: Piloc: A self-calibrating participatory indoor localization system. In: IPSN, pp. 143–153. IEEE (2014)

[13]

Ming, J., Hu, N., Niu, X., Zhang, Y.: Study on the personnel localization algorithm of the underground mine based on rssi technology. In: IEEE International Conference on Communication Software and Networks, pp. 408–411 (2017)

[14]

Ni LM, Liu Y, Lau YC, and Patil AP Landmarc: indoor location sensing using active rfid Wirel. Netw. 2004 10 6 701-710

[15]

Mu, Z., Liu, Y., Wei, N., Xie, L., Tian, Z.: Secure mobile crowdsourcing for wlan indoor localization. In: IEEE INFOCOM 2018 - IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS) (2018)

[16]

Niu, J., Long, C., Wang, B., Rodriguees, J.J.P.C.: Wicloc:an indoor localization system based on wifi fingerprints and crowdsourcing. In: IEEE International Conference on Communications (2015)

[17]

Roussopoulos, N., Kelley, S., Vincent, F.: Nearest neighbor queries. In: SIGMOD, vol. 24, pp. 71–79. ACM (1995)

[18]

Roy W, Andy H, Veronica F, and Jonathan G The active badge location system ACM Trans. Inf. Syst. (TOIS) 1992 10 1 91-102

[19]

Siddhartha, S., Kamalika, C., Dheeraj, S., Pravin, B.: Location determination of a mobile device using ieee 802.11 b access point signals. In: Wireless Communications and Networking, 2003. WCNC 2003. 2003 IEEE, vol. 3, pp. 1987–1992. IEEE (2003)

[20]

Sun, J., Yang, X., Wang, B.: Crowdsourced indoor localization for diverse devices with rssi sequences. In: WISA, pp. 614–625 (2019)

[21]

Thomas, K., Stephan, K., Thomas, H., Christian, L., Wolfgang, E.: 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 And Characterization, pp. 34–40. ACM (2006)

[22]

Wu C, Yang Z, and Liu Y Smartphones based crowdsourcing for indoor localization J. Locat. Based Serv. 2015 14 2 444-457

[23]

Xie, X., Lu, H., Pedersena, T.B.: Efficient distance-aware query evaluation on indoor moving objects. In: IEEE International Conference on Data Engineering, pp. 434–445 (2013)

[24]

Xue W, Qiu W, Hua X, and Yu K Improved wi-fi rssi measurement for indoor localization IEEE Sens. J. 2017 PP 99 1-1

[25]

Yang, B., Lu, H., Jensen, C.S.: Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space. In: International Conference on Extending Database Technology, pp. 335–346 (2010)

[26]

Yang, Q., Pan, S.J., Zheng, V.W.: Estimating location using wi-fi. In: IEEE 2007 ICDM Contest, pp. 8–13 (2008)

[27]

Yang, S., Dessai, P., Verma, M., Gerla, M.: Freeloc: Calibration-free crowdsourced indoor localization. In: INFOCOM, 2013 Proceedings IEEE (2013)

[28]

Yiu ML, Mamoulis N, and Papadias D Aggregate nearest neighbor queries in road networks IEEE Trans. Knowl. Data Eng. 2005 17 6 820-833

[29]

Yiu S, Dashti M, Claussen H, and Perez-Cruz F Wireless rssi fingerprinting localization Signal Process. 2017 131 235-244

[30]

Zhao Y, Wong WC, Feng T, and Garg HK Calibration-free indoor positioning using crowdsourced data and multidimensional scaling IEEE Trans. Wirel. Commun. 2020 19 3 1770-1785

[31]

Zhong, R., Li, G., Tan, K.L., Zhou, L.: G-tree: An efficient index for knn search on road networks. In: CIKM, pp. 39–48 (2013)

[32]

Zhou S, Ogihara A, Nishimura S, and Jin Q Analyzing the changes of health condition and social capital of elderly people using wearable devices Health Inf. Sci. Syst. 2018 6 1 4

[33]

Zhu, M., Zhang, H.: Research on model of indoor distance measurement based on receiving signal strength. In: International Conference on Computer Design and Applications (ICCDA), vol. 5, pp. V5–54 (2010)

Cited By

Chan HLiu TLi HLu H(2023)Time-constrained indoor keyword-aware routing: foundations and extensionsGeoinformatica10.1007/s10707-023-00489-227:3(375-426)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s10707-023-00489-2
Li MJiang FPei C(2022)Improvement of triangle centroid localization algorithm based on PIT criterion (ITCL-PIT) for WSNsEURASIP Journal on Wireless Communications and Networking10.1186/s13638-022-02109-32022:1Online publication date: 21-Mar-2022
https://dl.acm.org/doi/10.1186/s13638-022-02109-3
Sun JWang BSong XYang X(2021)Data Cleaning for Indoor Crowdsourced RSSI SequencesWeb and Big Data10.1007/978-3-030-85899-5_20(267-275)Online publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-85899-5_20

Index Terms

Practical approximate indoor nearest neighbour locating with crowdsourced RSSIs

Index terms have been assigned to the content through auto-classification.

Recommendations

Data Cleaning for Indoor Crowdsourced RSSI Sequences
Web and Big Data
Abstract
Received Signal Strength Indication (RSSI) has been increasingly deployed in indoor localization and navigation. Comparing with traditional fingerprint-based methods, crowdsourced method can collect RSSIs without expert surveyors and designated ...
A Polygonal Method for Ranging-Based Localization in an Indoor Wireless Sensor Network

In this paper, we propose an indoor localization method in a wireless sensor network based on IEEE 802.15.4 specification. The proposed method follows a ranging-based approach using not only the measurements of received signal strength (RSS) but also ...
Accurate and Low-cost Mobile Indoor Localization with 2-D Magnetic Fingerprints
CrowdSenSys '17: Proceedings of the First ACM Workshop on Mobile Crowdsensing Systems and Applications

Indoor localization is particularly valuable in many indoor application scenarios, such as shopping malls and airports. An indoor localization system on smartphones should be low-power as well as accurate. In this paper, we present Turnin - a completely ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image World Wide Web

World Wide Web Volume 24, Issue 3

May 2021

300 pages

ISSN:1386-145X

Issue’s Table of Contents

© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 May 2021

Accepted: 15 February 2021

Revision received: 02 December 2020

Received: 29 June 2020

Author Tags

Qualifiers

Research-article

Funding Sources

Key Technologies Research and Development Program
Fundamental Research Funds for the Central Universities
National Natural Science Foundation of China
Ten Thousand Talent Program
Distinguished Professor of Liaoning Province
CCF Huawei database innovation research program

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chan HLiu TLi HLu H(2023)Time-constrained indoor keyword-aware routing: foundations and extensionsGeoinformatica10.1007/s10707-023-00489-227:3(375-426)Online publication date: 1-Jul-2023
https://dl.acm.org/doi/10.1007/s10707-023-00489-2
Li MJiang FPei C(2022)Improvement of triangle centroid localization algorithm based on PIT criterion (ITCL-PIT) for WSNsEURASIP Journal on Wireless Communications and Networking10.1186/s13638-022-02109-32022:1Online publication date: 21-Mar-2022
https://dl.acm.org/doi/10.1186/s13638-022-02109-3
Sun JWang BSong XYang X(2021)Data Cleaning for Indoor Crowdsourced RSSI SequencesWeb and Big Data10.1007/978-3-030-85899-5_20(267-275)Online publication date: 23-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-85899-5_20

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents