1. Home
  2. Vol 8, No 2 (2024)
  3. Yaro

Improved Fingerprint-Based Localization Based on Sequential Hybridization of Clustering Algorithms

Abdulmalik Shehu Yaro, Filip Maly, Pavel Prazak, Karel Malý

Abstract


The localization accuracy of a fingerprint-based localization system is dependent on several factors, one of which is the accuracy and efficiency at which the fingerprint database is clustered. Most highly efficient and accurate clustering algorithms have high time-dependent computational complexity (CC), which tends to limit their practical applicability. A technique that has yet to be explored is the sequential hybridization of multiple low-time CC clustering algorithms to produce a single moderate-time CC clustering algorithm with high localization accuracy. As a result, this paper proposes a clustering algorithm with a moderate time CC that is based on the sequential hybridization of the closest access point (CAP) and improved k-means clustering algorithms. The performance of the proposed sequential hybrid clustering algorithm is determined and compared to the modified affinity propagation clustering (m-APC), fuzzy c-mean (FCM), and 2-CAP algorithms presented in earlier research works using four experimentally generated and publicly available fingerprint databases. The performance metrics considered for the comparisons are the position root mean square error (RMSE) and clustering time based on big O notation. The simulation results show that the proposed sequential hybrid clustering algorithm has improved localization accuracy with position RMSEs of about 54%, 77%, and 52%, respectively, higher than those of the m-APC, FCM, and 2-CAP algorithms. In terms of clustering time, it is 99% and 79% faster than the m-APC and FCM algorithms, respectively, but 90% slower than the 2-CAP algorithm. The results have shown that it is possible to develop a clustering algorithm that has a moderate clustering time with very high localization accuracy through sequential hybridization of multiple clustering algorithms that have a low clustering time with poor localization accuracy.

 

Doi: 10.28991/ESJ-2024-08-02-02

Full Text: PDF


Keywords


Clustering; Closest AP; k-NN; Sequential Hybrid; localization Accuracy; RSS; k-Means.

References


Yaro, A. S., Malý, F., & Malý, K. (2023). A Two-Nearest Wireless Access Point-Based Fingerprint Clustering Algorithm for Improved Indoor Wireless Localization. Emerging Science Journal, 7(5), 1762–1770. doi:10.28991/ESJ-2023-07-05-019.

Yong, Y. F., Tan, C. K., Tan, I. K., & Tan, S. W. (2023). C-VoNNI: a precise fingerprint construction for indoor positioning systems using natural neighbor methods with clustering-based Voronoi diagrams. The Journal of Supercomputing, 1-28. doi:10.1007/s11227-023-05855-3.

Yaro, A. S., Maly, F., & Maly, K. (2023). Improved Indoor Localization Performance Using a Modified Affinity Propagation Clustering Algorithm with Context Similarity Coefficient. IEEE Access, 11, 57341–57348. doi:10.1109/ACCESS.2023.3283592.

Shang, S., & Wang, L. (2022). Overview of Wi-Fi fingerprinting-based indoor positioning. IET Communications, 16(7), 725–733. doi:10.1049/cmu2.12386.

Al Mamun, M. A., Anaya, D. V., & Yuce, M. R. (2021). FaStER: Fast, Stable, Expendable and Reliable Radio Map for Indoor Localization. 2021 IEEE International Symposium on Inertial Sensors and Systems (INERTIAL), Kailua-Kona, United States. doi:10.1109/inertial51137.2021.9430464.

Khoo, H. W., Ng, Y. H., & Tan, C. K. (2022). Enhanced Radio Map Interpolation Methods Based on Dimensionality Reduction and Clustering. Electronics, 11(16), 2581. doi:10.3390/electronics11162581.

Yaro, A. S., Maly, F., & Prazak, P. (2023). A Survey of the Performance-Limiting Factors of a 2-Dimensional RSS Fingerprinting-Based Indoor Wireless Localization System. Sensors, 23(5), 2545. doi:10.3390/s23052545.

Singh, N., Choe, S., & Punmiya, R. (2021). Machine Learning Based Indoor Localization Using Wi-Fi RSSI Fingerprints: An Overview. IEEE Access, 9, 127150–127174. doi:10.1109/ACCESS.2021.3111083.

Quezada-Gaibor, D., Torres-Sospedra, J., Nurmi, J., Koucheryavy, Y., & Huerta, J. (2021). Lightweight Wi-Fi Fingerprinting with a Novel RSS Clustering Algorithm. 2021 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Lloret de Mar, Spain. doi:10.1109/ipin51156.2021.9662612.

Ezhumalai, B., Song, M., & Park, K. (2021). An efficient indoor positioning method based on Wi-Fi RSS fingerprint and classification algorithm. Sensors, 21(10), 3418. doi:10.3390/s21103418.

Xu, D., & Tian, Y. (2015). A Comprehensive Survey of Clustering Algorithms. Annals of Data Science, 2(2), 165–193. doi:10.1007/s40745-015-0040-1.

Abed, A., & Abdel-Qader, I. (2019). RSS-fingerprint dimensionality reduction for multiple service set identifier-based indoor positioning systems. Applied Sciences (Switzerland), 9(15), 3137. doi:10.3390/app9153137.

Bakhthemmat, A., & Izadi, M. (2020). Decreasing the execution time of reducers by revising clustering based on the futuristic greedy approach. Journal of Big Data, 7(1), 6. doi:10.1186/s40537-019-0279-z.

Baldini, G., Giuliani, R., Steri, G., Sanchez, I., & Gentile, C. (2017). The application of the Symbolic Aggregate Approximation algorithm (SAX) to radio frequency fingerprinting of IoT devices. 2017 IEEE Symposium on Communications and Vehicular Technology (SCVT), Leuven, Belgium. doi:10.1109/scvt.2017.8240312.

Chiang, M. C., Tsai, C. W., & Yang, C. S. (2011). A time-efficient pattern reduction algorithm for k-means clustering. Information Sciences, 181(4), 716–731. doi:10.1016/j.ins.2010.10.008.

Klus, L., Quezada-Gaibor, D., Torres-Sospedra, J., Lohan, E. S., Granell, C., & Nurmi, J. (2020). RSS Fingerprinting Dataset Size Reduction Using Feature-Wise Adaptive k-Means Clustering. 12th International Congress on Ultra-Modern Telecommunications and Control Systems and Workshops (ICUMT), Brno, Czech. doi:10.1109/icumt51630.2020.9222458.

Li, A., Fu, J., Shen, H., & Sun, S. (2021). A Cluster-Principal-Component-Analysis-Based Indoor Positioning Algorithm. IEEE Internet of Things Journal, 8(1), 187–196. doi:10.1109/JIOT.2020.3001383.

Sagheer, N. S., & Yousif, S. A. (2021). Canopy with k-means clustering algorithm for big data analytics. AIP Conference Proceedings. doi:10.1063/5.0042398.

Liu, S., DE Lacerda, R., & Fiorina, J. (2021). WKNN indoor Wi-Fi localization method using k-means clustering based radio mapping. 2021 IEEE 93rd Vehicular Technology Conference (VTC2021-Spring), Helsinki, Finland. doi:10.1109/vtc2021-spring51267.2021.9448961.

Zhao, H. (2022). Design and Implementation of an Improved K-Means Clustering Algorithm. Mobile Information Systems, 2022, 1–10. doi:10.1155/2022/6041484.

Arthur, D., & Vassilvitskii, S. (2007). K-means++: The advantages of careful seeding. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 7-9 January, 2007, New Orleans, United States.

Celebi, M. E., Kingravi, H. A., & Vela, P. A. (2013). A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Systems with Applications, 40(1), 200–210. doi:10.1016/j.eswa.2012.07.021.

Bi, J., Huang, L., Cao, H., Yao, G., Sang, W., Zhen, J., & Liu, Y. (2021). Improved indoor fingerprinting localization method using clustering algorithm and dynamic compensation. ISPRS International Journal of Geo-Information, 10(9), 613. doi:10.3390/ijgi10090613.

Sadowski, S., Spachos, P., & Plataniotis, K. N. (2020). Memoryless Techniques and Wireless Technologies for Indoor Localization with the Internet of Things. IEEE Internet of Things Journal, 7(11), 10996–11005. doi:10.1109/JIOT.2020.2992651.

Alhmiedat, T. (2023). Fingerprint-Based Localization Approach for WSN Using Machine Learning Models. Applied Sciences, 13(5), 3037. doi:10.3390/app13053037.

Moreira, A., Silva, I., Meneses, F., Nicolau, M. J., Pendao, C., & Torres-Sospedra, J. (2017). Multiple simultaneous Wi-Fi measurements in fingerprinting indoor positioning. 2017 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Sapporo, Japan. doi:10.1109/ipin.2017.8115914.

Torres-Sospedra, J., Moreira, A., Mendoza-Silva, G. M., Joao Nicolau, M., Matey-Sanz, M., Silva, I., Huerta, J., & Pendao, C. (2019). Exploiting Different Combinations of Complementary Sensor’s data for Fingerprint-based Indoor Positioning in Industrial Environments. 2019 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Pisa, Italy. doi:10.1109/ipin.2019.8911758.

Wu, Y., Jia, Z., Dai, Y., & Wang, W. (2022). Research on Wi-Fi Location Fingerprint Positioning Algorithm Based on DPC-FCM Clustering. Wireless Communications and Mobile Computing, 2022, 1–7. doi:10.1155/2022/8347084.


Full Text: PDF

DOI: 10.28991/ESJ-2024-08-02-02

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Abdulmalik Shehu Yaro, Filip Maly, Pavel Prazak, Karel Malý