Nothing Special   »   [go: up one dir, main page]

Skip to main content
Log in

A Brownian Motion Restricted K-Nearest Neighbor Algorithm for Indoor Positioning

  • Research
  • Published:
Wireless Personal Communications Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

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

  1. 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

    Article  Google Scholar 

  2. 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

    Article  Google Scholar 

  3. 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

    Article  Google Scholar 

  4. 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

    Article  Google Scholar 

  5. 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

    Article  Google Scholar 

  6. Yang, C., & Shao, H. (2015). WiFi-based indoor positioning. IEEE Communications Magazine, 53(3), 150–157. https://doi.org/10.1109/MCOM.2015.7060497

    Article  Google Scholar 

  7. 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

    Article  Google Scholar 

  8. 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

    Article  Google Scholar 

  9. 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

  10. 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

    Article  Google Scholar 

  11. 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

    Article  Google Scholar 

  12. 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

    Article  Google Scholar 

  13. 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

  14. 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

  15. 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

    Book  Google Scholar 

  16. 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

  17. 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

    Article  Google Scholar 

  18. 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

  19. 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

  20. 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

    Article  Google Scholar 

  21. 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

  22. 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

  23. 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

  24. 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

  25. 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

    Article  Google Scholar 

  26. 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

    Article  Google Scholar 

  27. 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

    Article  Google Scholar 

  28. 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

    Article  Google Scholar 

  29. 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

    Article  Google Scholar 

  30. 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

    Article  Google Scholar 

  31. 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

    Article  Google Scholar 

  32. 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

    Article  Google Scholar 

  33. 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

    Article  Google Scholar 

  34. 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

  35. 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

  36. 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

    Article  Google Scholar 

  37. 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

    Article  Google Scholar 

  38. 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

    Article  Google Scholar 

  39. 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

    Article  MathSciNet  Google Scholar 

  40. Ray, D. S. (1999). Notes on Brownian motion and related phenomena. https://doi.org/10.48550/ARXIV.PHYSICS/9903033

  41. 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

  42. Brockmann, D., Hufnagel, L., & Geisel, T. (2006). The scaling laws of human travel. Nature, 439(7075), 462–465. https://doi.org/10.1038/nature04292

    Article  Google Scholar 

  43. 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

  44. 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

  45. 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

    Article  Google Scholar 

  46. 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

  47. 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

  48. 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/

  49. 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

    Article  Google Scholar 

  50. 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

    Article  Google Scholar 

  51. 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

  52. 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

  53. 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

  54. 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

  55. 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

    Article  Google Scholar 

  56. 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

  57. 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

    Article  Google Scholar 

  58. 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

  59. 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

  60. 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

  61. 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

    Article  Google Scholar 

  62. Mori, H. (1965). Transport, collective motion, and Brownian motion. Progress of theoretical physics, 33(3), 423–455.

    Article  Google Scholar 

  63. 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

    Article  MathSciNet  Google Scholar 

  64. 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

    Article  MathSciNet  Google Scholar 

  65. 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

    Article  Google Scholar 

  66. 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

    Article  Google Scholar 

  67. 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

  68. 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

    Article  Google Scholar 

Download references

Funding

The authors received no specific funding for this study.

Author information

Authors and Affiliations

Authors

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

Correspondence to Wu Huang.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11277-024-11640-z

Keywords

Navigation