Indoor Localization Performance Optimization Using Modified kd-Tree Algorithm

Document Type : Research Article

Authors

Department of Computer Engineering, Faculty of Engineering, Arak University, Sardasht, Arak, Iran.

Abstract

In this paper, we present a new method for improving the efficiency of indoor localization algorithms, in terms of running time and error rate, using the KD-tree data structure. One of the main challenges of indoor localization algorithms in large environments is the high processing overhead of these algorithms due to the high volume of input data and lack of processing resources in users' mobile devices. In the proposed method in this paper, we first cluster the fingerprint database. Then, with the help of a newly proposed method, a modified KD-tree is implemented according to the conditions of the clusters. This tree is a decision-making structure to select one specific cluster where the user stands there. Finally, when a user entered, using a few simple comparisons in the KD-tree, the desired cluster is found and only information about that cluster is passed to the localization algorithm, to compare and predict the user’s location. The results of the implementation of this method on the fingerprint data set of the Faculty of Engineering at Arak University show that the proposed method reduces the running times and errors to less than half the values, compared to the time of not using the proposed method.

Keywords

Main Subjects

References

[1] Yungeun Kim, Hyojeong Shin, Yohan Chon, and Hojung Cha. Crowdsensing-based Wi-Fi radio map management using a lightweight site survey. Computer Communications, 60:86--96, 2015. [ bib | DOI ]
[2] Faheem Zafari, Athanasios Gkelias, and Kin K Leung. A Survey of Indoor Localization Systems and Technologies. IEEE Communications Surveys & Tutorials, 21(3):2568--2599, 2019. [ bib | DOI ]
[3] Suining He and S-H Gary Chan. Wi-Fi Fingerprint-Based Indoor Positioning: Recent Advances and Comparisons. IEEE Communications Surveys & Tutorials, 18(1):466--490, 2015. [ bib | DOI ]
[4] Huthaifa Obeidat, Wafa Shuaieb, Omar Obeidat, and Raed Abd-Alhameed. A Review of Indoor Localization Techniques and Wireless Technologies. Wireless Personal Communications, 119(1):289–327, 2021. [ bib | DOI ]
[5] Navneet Singh, Sangho Choe, and Rajiv Punmiya. Machine Learning Based Indoor Localization Using Wi-Fi RSSI Fingerprints: An Overview. IEEE Access, 9:127150 -- 127174, 2021. [ bib | DOI ]
[6] Priya Roy and Chandreyee Chowdhury. A Survey of Machine Learning Techniques for Indoor Localization and Navigation Systems. Journal of Intelligent & Robotic Systems, 101(3):1--34, 2021. [ bib | DOI ]
[7] Tian Yang, Adnane Cabani, and Houcine Chafouk. A Survey of Recent Indoor Localization Scenarios and Methodologies. Sensors, 21(23), 2021. [ bib | DOI ]
[8] Teemu Roos, Petri Myllymäki, Henry Tirri, Pauli Misikangas, and Juha Sievänen. A Probabilistic Approach to WLAN User Location Estimation. International Journal of Wireless Information Networks, 9(3):155–164, 2002. [ bib | DOI ]
[9] Mu Zhou, Yaohua Li, Muhammad Junaid Tahir, Xiaolong Geng, Yong Wang, and Wei He. Integrated Statistical Test of Signal Distributions and Access Point Contributions for Wi-Fi Indoor Localization. IEEE Transactions on Vehicular Technology, 70(5):5057 -- 5070, 2021. [ bib | DOI ]
[10] Hamada Rizk, Ahmed Elmogy, and Hirozumi Yamaguchi. A Robust and Accurate Indoor Localization Using Learning-Based Fusion of Wi-Fi RTT and RSSI. Sensors, 22(7), 2022. [ bib | DOI ]
[11] Fatemeh Ali Asgari Renani, Hossein Ghaffarian, and Mastaneh Chegeni. Indoor Path Tracking Using Combination of Viterbi and WKNN. Journal of Computing and Security, 8(2):19--26, 2021. [ bib | DOI ]
[12] Jiancun Fan, Susu Chen, Xinmin Luo, Ying Zhang, and Geoffrey Ye Li. A Machine Learning Approach for Hierarchical Localization Based on Multipath MIMO Fingerprints. IEEE Communications Letters, 23(10):1765--1768, 2019. [ bib | DOI ]
[13] Ahmet Çağdas Seçkin and Aysun Coskun. Hierarchical Fusion of Machine Learning Algorithms in Indoor Positioning and Localization. Applied Sciences, 9(18), 2019. [ bib | DOI ]
[14] Daniel Alshamaa, Farah Mourad-Chehade, and Paul Honeine. A Weighted Kernel-Based Hierarchical Classification Method for Zoning of Sensors in Indoor Wireless Networks. In 2018 IEEE 19th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC), pages 1--5. IEEE, 2018. [ bib | DOI ]
[15] Hossein Ghaffarian. Reducing Search Area in Indoor Localization Applications. Wireless Personal Communications, 117(2), 2021. [ bib | DOI ]
[16] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509–517, 1975. [ bib | DOI ]
[17] Maria Mercè Pons Crespo. Design, analysis and implementation of new variants of kd-trees. Master's thesis, Universitat Politècnica de Catalunya, 2010. [ bib ]
[18] Dengxiu Yu, Hao Xu, CL Philip Chen, Wenjie Bai, and Zhen Wang. Dynamic Coverage Control Based on K-Means. IEEE Transactions on Industrial Electronics, 69(5):5333--5341, 2021. [ bib | DOI ]
[19] Jesús Estupiñán Ricardo, Jorge Juan Domínguez Menéndez, Ignacio Fernando Barcos Arias, Jorge Manuel Macías Bermúdez, and Noel Moreno Lemus. Neutrosophic K-means for the analysis of earthquake data in Ecuador. Neutrosophic Sets and Systems, 44(1), 2021. [ bib | DOI ]
[20] Zhen-Song Chen, Xuan Zhang, Witold Pedrycz, Xian-Jia Wang, Kwai-Sang Chin, and Luis Martínez. K-means clustering for the aggregation of HFLTS possibility distributions: N-two-stage algorithmic paradigm. Knowledge-Based Systems, 227:107230, 2021. [ bib | DOI ]
[21] Shashank Reddy Vadyala, Sai Nethra Betgeri, Eric A Sherer, and Amod Amritphale. Prediction of the number of COVID-19 confirmed cases based on K-means-LSTM. Array, 11:100085, 2021. [ bib | DOI ]
[22] Malika Charrad, Nadia Ghazzali, Veronique Boiteau, and Azam Niknafs. Determining the Best Number of Clusters in a Data Set. https://cran.rproject.org/web/packages/NbClust/NbClust.pdf, Date Accessed: Dec. 30, 2022. [ bib ]
[23] Leonard Kaufman and Peter J Rousseeuw. Finding groups in data: an introduction to cluster analysis. John Wiley & Sons, 2009. [ bib ]
[24] Gints Jekabsons and Vadim Zuravlyov. Refining Wi-Fi based indoor positioning. In Proceedings of 4th International Scientific Conference Applied Information and Communication Technologies (AICT), Jelgava, Latvia, pages 87--95, 2010. [ bib | DOI ]
[25] Jian Pei Jiawei Han, Micheline Kamber. Data Mining: Concepts and Techniques. Elsevier, 2011. [ bib ]
Journal of Computing and Security
Volume 9, Issue 2
July 2022
Pages 55-64

Files

History

  • Receive Date: 06 April 2022
  • Revise Date: 03 November 2022
  • Accept Date: 14 November 2022

Share

How to cite

Statistics