Abstract
In the indoor positioning method based on traditional KNN, the Received Signal Strength Indicator (RSSI) is commonly utilized as fingerprint information for measuring similarity, with the selection of the most matching K reference points (RPs) for positioning. However, ensuring the accuracy of the KNN fingerprint positioning method requires the collection of a substantial amount of fingerprint information and is susceptible to the complexity and stability of the indoor environment. Consequently, we propose a novel algorithm called Brownian Motion Restricted K-Nearest Neighbor (BMR-KNN). In the BMR-KNN method, we leverage the assumption that the tester’s activity exhibits a degree of adherence to the principles of Brownian motion. We utilize this assumption as prior knowledge to correct the results obtained from the KNN positioning algorithm based on RSSI. Furthermore, we propose a dynamic K value allocation algorithm (DKAA) for automatic optimization of the K value within the KNN positioning algorithm. Despite utilizing the previous location and time information, BMR-KNN achieves real-time positioning without requiring knowledge of the user’s exact moving speed and direction. Experimental evaluations conducted on two public datasets demonstrate that the new algorithm outperforms other advanced methods, including the optimal traditional KNN, and reduces the average positioning error to 3.31 m to the greatest extent.
Similar content being viewed by others
Data Availability
The datasets generated during and/or analysed during the current study are available in the IndoorLoc Database repository, https://indoorloc.uji.es/
References
Hegarty, C. J., & Chatre, E. (2008). Evolution of the global navigation satellite system (GNSS). Proceedings of the IEEE, 96(12), 1902–1917. https://doi.org/10.1109/JPROC.2008.2006090
Roy, P., & Chowdhury, C. (2021). A survey of machine learning techniques for indoor localization and navigation systems. Journal of Intelligent & Robotic Systems, 101(3), 63. https://doi.org/10.1007/s10846-021-01327-z
Liu, H., Darabi, H., Banerjee, P., & Liu, J. (2007). Survey of wireless indoor positioning techniques and systems. IEEE Transactions on Systems, Man, and Cybernetics Part C (Applications and Reviews), 37(6), 1067–1080. https://doi.org/10.1109/TSMCC.2007.905750
Liu, F., Liu, J., Yin, Y., Wang, W., Hu, D., Chen, P., & Niu, Q. (2020). Survey on WiFi-based indoor positioning techniques. IET Communications, 14(9), 1372–1383. https://doi.org/10.1049/iet-com.2019.1059
Alikhani, N., Moghtadaiee, V., & Ghorashi, S. A. (2020). Fingerprinting based indoor localization considering the dynamic nature of Wi-Fi signals. Wireless Personal Communications, 115(2), 1445–1464. https://doi.org/10.1007/s11277-020-07636-0
Yang, C., & Shao, H. (2015). WiFi-based indoor positioning. IEEE Communications Magazine, 53(3), 150–157. https://doi.org/10.1109/MCOM.2015.7060497
Bi, S., Wang, C., Shen, J., Xiang, W., Ni, W., Wang, X., Wu, B., & Gong, Y. (2023). A novel RFID localization approach to smart self-service borrowing and returning system. Computer Modeling in Engineering & Sciences, 135(1), 527–538. https://doi.org/10.32604/cmes.2022.022298
Dong, Z. Y., Xu, W. M., & Zhuang, H. (2019). Research on ZigBee indoor technology positioning based on RSSI. Procedia Computer Science, 154, 424–429. https://doi.org/10.1016/j.procs.2019.06.060
Hallberg, J., Nilsson, M., & Synnes, K. (2003). Positioning with bluetooth. In 10th International Conference on Telecommunications, 2003. ICT 2003. Conference Proceedings, Papeete, Tahiti, French Polynesia: IEEE. vol. 2, pp. 954–958. https://doi.org/10.1109/ICTEL.2003.1191568
Liu, S., Jiang, Y., & Striegel, A. (2014). Face-to-face proximity estimation using bluetooth on smartphones. IEEE Transactions on Mobile Computing, 13(4), 811–823. https://doi.org/10.1109/TMC.2013.44
Chon, H. D., Jun, S., Jung, H., & An, W. (2004). Using RFID for accurate positioning. Journal of Global Positioning Systems, 3(1 & 2), 32–39. https://doi.org/10.5081/jgps.3.1.32
Want, R., Hopper, A., Falcão, V., & Gibbons, J. (1992). The active badge location system. ACM Transactions on Information Systems, 10(1), 91–102. https://doi.org/10.1145/128756.128759
Yu, X., Li, Q., Queralta, J. P., Heikkonen, J., & Westerlund, T. (2021). Applications of UWB Networks and positioning to autonomous robots and industrial systems. In 2021 10th Mediterranean Conference on Embedded Computing (MECO). pp. 1–6. https://doi.org/10.1109/MECO52532.2021.9460266
Salamah, A. H., Tamazin, M., Sharkas, M. A., & Khedr, M. (2016). An enhanced WiFi indoor localization system based on machine learning. In 2016 International Conference on Indoor Positioning and Indoor Navigation (IPIN). Alcala de Henares, Spain, IEEE. pp. 1–8. https://doi.org/10.1109/IPIN.2016.7743586
Jondhale, S. R., Maheswar, R., & Lloret, J. (2022). Received signal strength based target localization and tracking using wireless sensor networks. Springer International Publishing. https://doi.org/10.1007/978-3-030-74061-0
Rusli, M. E., Ali, M., Jamil, N., & Din, M. M. (2016). An improved indoor positioning algorithm based on RSSI-trilateration technique for internet of things (IOT). In 2016 International Conference on Computer and Communication Engineering (ICCCE), Kuala Lumpur, Malaysia: IEEE. pp. 72–77. https://doi.org/10.1109/ICCCE.2016.28
Xie, Y., Wang, K., & Huan, H. (2022). BPNN based indoor fingerprinting localization algorithm against environmental fluctuations. IEEE Sensors Journal, 22(12), 12002–12016. https://doi.org/10.1109/JSEN.2022.3172860
Alfakih, M., Keche, M., & Benoudnine, H. (2015). Gaussian mixture modeling for indoor positioning WIFI systems. In 2015 3rd International Conference on Control, Engineering & Information Technology (CEIT), Tlemcen, Algeria: IEEE. pp. 1–5. https://doi.org/10.1109/CEIT.2015.7233072
Del Mundo, L. B., Ansay, R. L. D., Festin, C. A. M., & Ocampo, R. M. (2011). A comparison of wireless fidelity (Wi-Fi) fingerprinting techniques. In ICTC 2011 Presented at the 2011 International Conference on ICT Convergence (ICTC), Seoul, Korea (South): IEEE. pp. 20–25. https://doi.org/10.1109/ICTC.2011.6082543
Torres-Sospedra, J., Montoliu, R., Trilles, S., Belmonte, Ó., & Huerta, J. (2015). Comprehensive analysis of distance and similarity measures for Wi-Fi fingerprinting indoor positioning systems. Expert Systems with Applications, 42(23), 9263–9278. https://doi.org/10.1016/j.eswa.2015.08.013
Haeberlen, A., Flannery, E., Ladd, A. M., Rudys, A., Wallach, D. S., & Kavraki, L. E. (2004). Practical robust localization over large-scale 802.11 wireless networks. In Proceedings of the 10th annual international conference on Mobile computing and networking. Philadelphia PA USA: ACM. pp. 70–84. https://doi.org/10.1145/1023720.1023728
Mingzhe, X., Jiabin, C., Chunlei, S., Nan, L., & Kong, C. (2015). The indoor positioning algorithm research based on improved location fingerprinting. In The 27th Chinese Control and Decision Conference (2015 CCDC). Qingdao, China: IEEE. pp. 5736–5739. https://doi.org/10.1109/CCDC.2015.7161827
Kaemarungsi, K. (2006). Distribution of WLAN received signal strength indication for indoor location determination. In 2006 1st International Symposium on Wireless Pervasive Computing, Phuket, Thailand: IEEE. pp. 1–6. https://doi.org/10.1109/ISWPC.2006.1613601
Bahl, P., & Padmanabhan, V. N. (2000). RADAR: an in-building RF-based user location and tracking system. In Proceedings IEEE INFOCOM 2000. Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies (Cat. No.00CH37064) Tel Aviv, Israel: IEEE. vol. 2, pp. 775–784. https://doi.org/10.1109/INFCOM.2000.832252
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. https://doi.org/10.1109/JIOT.2020.2992651
Li, C., Qiu, Z., & Liu, C. (2017). An improved weighted K-nearest neighbor algorithm for indoor positioning. Wireless Personal Communications, 96(2), 2239–2251. https://doi.org/10.1007/s11277-017-4295-z
Zhang, J., & Mao, H. (2022). WKNN indoor positioning method based on spatial feature partition and basketball motion capture. Alexandria Engineering Journal, 61(1), 125–134. https://doi.org/10.1016/j.aej.2021.04.078
Jondhale, S. R., Mohan, V., Sharma, B. B., Lloret, J., & Athawale, S. V. (2022). Support vector regression for mobile target localization in indoor environments. Sensors, 22(1), 358. https://doi.org/10.3390/s22010358
Brunato, M., & Battiti, R. (2005). Statistical learning theory for location fingerprinting in wireless LANs. Computer Networks, 47(6), 825–845. https://doi.org/10.1016/j.comnet.2004.09.004
Wang, Y., Xiu, C., Zhang, X., & Yang, D. (2018). WiFi indoor localization with CSI fingerprinting-based random forest. Sensors, 18(9), 2869. https://doi.org/10.3390/s18092869
Fang, S.-H., & Lin, T.-N. (2008). Indoor location system based on discriminant-adaptive neural network in IEEE 802.11 environments. IEEE Transactions on Neural Networks, 19(11), 1973–1978. https://doi.org/10.1109/TNN.2008.2005494
Jondhale, S. R., Wakchaure, M. A., Agarkar, B. S., & Tambe, S. B. (2022). Improved generalized regression neural network for target localization. Wireless Personal Communications, 125(2), 1677–1693. https://doi.org/10.1007/s11277-022-09627-9
Du, C., Peng, B., Zhang, Z., Xue, W., & Guan, M. (2020). KF-KNN: Low-cost and high-accurate FM-based indoor localization model via fingerprint technology. IEEE Access, 8, 197523–197531. https://doi.org/10.1109/ACCESS.2020.3031089
Güvenc, İ. (2003). Enhancements to RSS based indoor tracking systems using Kalman filters (PhD Thesis). Citeseer. Retrieved from https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=4cceb3a3389307cff15413e74df93ab90ea6e7ed
Chen, L.-H., Chen, G.-H., Jin, M.-H., & Wu, E. H.-K. (2010). A Novel RSS-Based Indoor Positioning Algorithm Using Mobility Prediction. In 2010 39th International Conference on Parallel Processing Workshops (ICPPW), San Diego, CA, USA: IEEE. pp. 549–553. https://doi.org/10.1109/ICPPW.2010.80
Lin, C.-H., Chen, L.-H., Wu, H.-K., Jin, M.-H., Chen, G.-H., Garcia Gomez, J. L., & Chou, C.-F. (2021). An indoor positioning algorithm based on fingerprint and mobility prediction in RSS fluctuation-prone WLANs. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(5), 2926–2936. https://doi.org/10.1109/TSMC.2019.2917955
Browning, R. C., Baker, E. A., Herron, J. A., & Kram, R. (2006). Effects of obesity and sex on the energetic cost and preferred speed of walking. Journal of Applied Physiology, 100(2), 390–398. https://doi.org/10.1152/japplphysiol.00767.2005
Mohler, B. J., Thompson, W. B., Creem-Regehr, S. H., Pick, H. L., & Warren, W. H. (2007). Visual flow influences gait transition speed and preferred walking speed. Experimental Brain Research, 181(2), 221–228. https://doi.org/10.1007/s00221-007-0917-0
Kahane, J. (1997). A century of interplay between taylor series, fourier series and brownian motion. Bulletin of the London Mathematical Society, 29(3), 257–279. https://doi.org/10.1112/S0024609396002913
Ray, D. S. (1999). Notes on Brownian motion and related phenomena. https://doi.org/10.48550/ARXIV.PHYSICS/9903033
Shin, I., Lee, S., & Chong, S. (2007). Human mobility patterns and their impact on routing in human-driven mobile networks. Proceedings of Hotnets-VI, Atlanta, GA. Retrieved from https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=addd570ec7b34d360cb660d2eddc9a776501978c
Brockmann, D., Hufnagel, L., & Geisel, T. (2006). The scaling laws of human travel. Nature, 439(7075), 462–465. https://doi.org/10.1038/nature04292
Bruce, A., & Gordon, G. (2004). Better motion prediction for people-tracking. In Proceedings of the International Conference on Robotics & Automation (ICRA), Barcelona, Spain. Retrieved from http://www.cs.ucf.edu/~gitars/cap6938/bruce04better.pdf
Arndt, M., & Berns, K. (2012). Optimized mobile indoor robot navigation through probabilistic tracking of people in a wireless sensor network. In ROBOTIK 2012; 7th German Conference on Robotics. Retrieved from https://ieeexplore.ieee.org/abstract/document/6309534
Einstein, A. (1905). Über die von der molekularkinetischen Theorie der Wärme geforderte Bewegung von in ruhenden Flüssigkeiten suspendierten Teilchen. Annalen der Physik. https://doi.org/10.1002/andp.19053220806
Wu, D., Xu, Y., & Ma, L. (2009). Research on RSS based Indoor Location Method. In 2009 Pacific-Asia Conference on Knowledge Engineering and Software Engineering, Shenzhen, TBD, China: IEEE. pp. 205–208. https://doi.org/10.1109/KESE.2009.67
Rizos, C., Dempster, A. G., Li, B., & Salter, J. (2007). Indoor positioning techniques based on wireless LAN. Retrieved from https://opus.lib.uts.edu.au/handle/2100/170
Shi, K., Ma, Z., Zhang, R., Hu, W., & Chen, H. (2015). Support vector regression based indoor location in IEEE 802.11 environments. Mobile Information Systems, 2015. Retrieved from https://www.hindawi.com/journals/misy/2015/295652/
Zou, H., Jin, M., Jiang, H., Xie, L., & Spanos, C. J. (2017). WinIPS: WiFi-based non-intrusive indoor positioning system with online radio map construction and adaptation. IEEE Transactions on Wireless Communications, 16(12), 8118–8130. https://doi.org/10.1109/TWC.2017.2757472
Xie, Y., Wang, Y., Nallanathan, A., & Wang, L. (2016). An improved K-nearest-neighbor indoor localization method based on spearman distance. IEEE Signal Processing Letters, 23(3), 351–355. https://doi.org/10.1109/LSP.2016.2519607
Peng, Y., Fan, W., Dong, X., & Zhang, X. (2016). An iterative weighted KNN (IW-KNN) based indoor localization method in bluetooth low energy (BLE) environment. In 2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld), Toulouse: IEEE. pp. 794–800. https://doi.org/10.1109/UIC-ATC-ScalCom-CBDCom-IoP-SmartWorld.2016.0127
Gu, F., Shi, L., Guo, H., & Shang, J. (2023). Deep Fingerprint metric learning for KNN-based indoor localization. In GLOBECOM 2023—2023 IEEE Global Communications Conference. pp. 182–188. https://doi.org/10.1109/GLOBECOM54140.2023.10437360
Wang, J., Shi, F., Wan, P., Chen, M., & Jiang, F. (2023). An improved particle swarm optimization indoor positioning method based on the weighted adaptive KNN algorithm. In 2023 IEEE/CIC International Conference on Communications in China (ICCC). pp. 1–5. https://doi.org/10.1109/ICCC57788.2023.10233671
Liu, S., De Lacerda, R., & Fiorina, J. (2022). Performance analysis of adaptive K for weighted K-nearest neighbor based indoor positioning. In 2022 IEEE 95th Vehicular Technology Conference: (VTC2022-Spring), Helsinki, Finland: IEEE. pp. 1–5. https://doi.org/10.1109/VTC2022-Spring54318.2022.9860699
Oh, J., & Kim, J. (2018). AdaptiveK-nearest neighbour algorithm for WiFi fingerprint positioning. ICT Express, 4(2), 91–94. https://doi.org/10.1016/j.icte.2018.04.004
Umair, M. Y., Ramana, K. V., & Yang Dongkai. (2014). An enhanced K-nearest neighbor algorithm for indoor positioning systems in a WLAN. In 2014 IEEE Computers, Communications and IT Applications Conference, Beijing, China: IEEE. pp. 19–23, https://doi.org/10.1109/ComComAp.2014.7017163
Lee, I., Kwak, M., & Han, D. (2016). A dynamic k -nearest neighbor method for WLAN-based positioning systems. Journal of Computer Information Systems, 56(4), 295–300. https://doi.org/10.1080/08874417.2016.1164000
Hu, J., Liu, H., & Liu, D. (2018). Toward a dynamic K in K-nearest neighbor fingerprint indoor positioning. In 2018 IEEE International Conference on Information Reuse and Integration (IRI). pp. 308–314. https://doi.org/10.1109/IRI.2018.00054
Hu, J., & Hu, C. (2023). A WiFi indoor location tracking algorithm based on improved weighted K nearest neighbors and Kalman filter. IEEE Access, 11, pp. 32907–32918. https://doi.org/10.1109/ACCESS.2023.3263583
Zibaei, S. A., & Ali Abbaspour, R. (2023). Evaluation of Improved K-Nearest Neighbors for Indoor Positioning System in Real Complex Buildings. In 2023 9th International Conference on Web Research (ICWR). pp. 12–19. https://doi.org/10.1109/ICWR57742.2023.10139137
Delsaulx, J. (1877). Thermo-dynamic origin of the Brownian motions. The Monthly Microscopical Journal, 18(1), 1–7. https://doi.org/10.1111/j.1365-2818.1877.tb00093.x
Mori, H. (1965). Transport, collective motion, and Brownian motion. Progress of theoretical physics, 33(3), 423–455.
Acosta, A. (1985). On the functional form of Lévy’s modulus of continuity for Brownian motion. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 69(4), 567–579. https://doi.org/10.1007/BF00532667
Mandelbrot, B. B., & Van Ness, J. W. (1968). Fractional Brownian motions, fractional noises and applications. SIAM Review, 10(4), 422–437. https://doi.org/10.1137/1010093
Saffman, P. G., & Delbrück, M. (1975). Brownian motion in biological membranes. Proceedings of the National Academy of Sciences, 72(8), 3111–3113. https://doi.org/10.1073/pnas.72.8.3111
Zheng, X., Su, H., Wei, Z., & Hu, S. (2017). New method for indoor positioning by using wireless communication base stations. Electronics Letters, 53(20), 1385–1386. https://doi.org/10.1049/el.2016.3913
Torres-Sospedra, J., Montoliu, R., Martinez-Uso, A., Avariento, J. P., Arnau, T. J., Benedito-Bordonau, M., & Huerta, J. (2014). UJIIndoorLoc: A new multi-building and multi-floor database for WLAN fingerprint-based indoor localization problems. In 2014 International Conference on Indoor Positioning and Indoor Navigation (IPIN), Busan, South Korea: IEEE. pp. 261–270. https://doi.org/10.1109/IPIN.2014.7275492
Torres-Sospedra, J., Montoliu, R., Mendoza-Silva, G. M., Belmonte, O., Rambla, D., & Huerta, J. (2016). Providing databases for different indoor positioning technologies: pros and cons of magnetic field and Wi-Fi based positioning. Mobile Information Systems, 2016, 1–22. https://doi.org/10.1155/2016/6092618
Funding
The authors received no specific funding for this study.
Author information
Authors and Affiliations
Contributions
The authors confirm contribution to the paper as follows: conceptualization, Y.Y. and Q.Y; methodology, Y.Y.; software, Y.Y. and Q. Y.; validation, Y.Y and Q.Y.; investigation, Q.Y.; data curation, Y.Y. and Q.Y.; supervision and guide, T.Z.; writing—original draft preparation, Y.Y. and Q.Y; writing—review, T. Z. and W. H.; writing—editing, Y.Y. and Q.Y. All authors have read and agreed to the published version of the manuscript.
Corresponding author
Ethics declarations
Conflicts of interest
The authors declare that they have no conflicts of interest to report regarding the present study.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Yuting Yang and Qingqing Yang are considered co-first authors.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Yang, Y., Yang, Q., Zhang, T. et al. A Brownian Motion Restricted K-Nearest Neighbor Algorithm for Indoor Positioning. Wireless Pers Commun (2024). https://doi.org/10.1007/s11277-024-11640-z
Accepted:
Published:
DOI: https://doi.org/10.1007/s11277-024-11640-z