Efficient Beacon Deployment for Large-scale Positioning

Pin-Han Ho

¹ School of Computer Science and Information Engineering, Shanghai Institute of Technology, Shanghai, China

² School of Electronics and Information, Nantong University, Jiangsu, China

³ Department of Electrical and Computer Engineering, University of Waterloo, Canada

Instant and precise localization of indoor mobile users is fundamental for supporting various sophisticated location-aware services. Using Bluetooth low-power beacons for mobile user positioning has been reported as an effective approach, where the beacon deployment positioning (BDP) problem has been defined. The paper introduces a novel approach for solving large-scale BDP problems, aiming to significantly reduce beacon consumption from existing solutions with much less computation complexity. Extensive simulations are conducted to verify the proposed algorithm, whose beacon consumption is about 1.14 to 1.67 times and 0.2 to 0.48 times compared to those of the Mixed Integer Linear Program (ILP) and a naive iBeacon solution respectively. We have also observed that the running time scales well with the growth of the number of Test Positions and attenuation factors.

BLE beacon, positioning algorithm, heuristic, ILP, entropy

Wei He, Pin-Han Ho, Dong Wang, Lizhong Xiao (2021). Efficient Beacon Deployment for Large-scale Positioning. Journal of Networking and Network Applications, Volume 1, Issue 2, pp. 40–48. https://doi.org/10.33969/J-NaNA.2021.010201.

[1] A. Mackey, P. Spachos, and K. Plataniotis, “Smart parking system based on bluetooth low energy beacons with particle filtering,” IEEE Systems Journal, vol. PP, pp. 1–12, 02 2020.

[2] D. Lin and Z. Mi, “Electric fence planning for dockless bike-sharing services,” Journal of Cleaner Production, vol. 206, 09 2018.

[3] W. He and P.-H. Ho, “On achieving cyber-physical real-time snapshot acquisition in billboard/signage networks,” IEEE Internet of Things Journal, vol. 3, pp. 1–1, 12 2016.

[4] A. Ito, Y. Hiramatsu, H. Hatano, M. Sato, M. Fujii, Y. Watanabe, F. Sato, and A. Sasaki, “Navigation system for sightseeing using ble beacons in a historic area,” in 2016 IEEE 14th International Symposium on Applied Machine Intelligence and Informatics (SAMI), 2016, pp. 171–176.

[5] K. Shuang, X. Ren, Q. Yang, R. Li, and J. Loo, “Aela-dlstms: Attention-enabled and location-aware double lstms for aspect-level sentiment classification,” Neurocomputing, vol. 334, pp. 25 – 34, 2019. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S0925231218315054.

[6] C.-K. Ke, M. Wu, Y. Chan, and K. Lu, “Developing a ble beacon-based location system using location fingerprint positioning for smart home power management,” Energies, vol. 11, p. 3464, 12 2018.

[7] P. Spachos and K. Plataniotis, “Ble beacons in the smart city: Applica-tions, challenges, and research opportunities,” IEEE Internet of Things Magazine, vol. 3, pp. 14–18, 03 2020.

[8] M. Gao, X. Zhang, T. Zhang, C. Chen, Z. Wang, Z. Lu, W. Ding, and J. Ouyang, “An experimental study on wechat-based large scale indoor localization system,” in 2018 IEEE 24th International Conference on Parallel and Distributed Systems (ICPADS), 2018, pp. 330–338.

[9] W. He, P.-H. Ho, and J. Tapolcai, “Beacon deployment for unambiguous positioning,” IEEE Internet of Things Journal, vol. 4, no. 5, pp. 1370–1379, 10 2017.

[10] “Estimote power levels.” [Online]. Available: https://forums.estimote.com/t/measured-power-values/2977

[11] A. Mackey, P. Spachos, L. Song, and K. Plataniotis, “Improving ble beacon proximity estimation accuracy through bayesian filtering,” IEEE Internet of Things Journal, vol. PP, pp. 1–1, 01 2020.

[12] Blasio, de, Rodr´ıguez-Rodr´ıguez, Garc´ıa, Carmelo, and Quesada-Arencibia, Alexis, “Beacon-related param of bluetooth low energy: Development of a semi-automatic system to study their impact on indoor positioning systems,” Sensors, vol. 19, p. 3087, 07 2019.

[13] G. Piccinni, G. Avitabile, G. Coviello, and C. Talarico, “Modeling of a re-configurable indoor positioning system based on software defined radio architecture,” in 2018 New Generation of CAS (NGCAS), 11 2018, pp. 174–177.

[14] H. Cheng, H. Liu, W. Wang, and J. Li, “A compact and cost-effective ble beacon with multiprotocol and dynamic content advertising for iot application,” IEEE Internet of Things Journal, vol. 7, pp. 2309–2320, 03 2020.

[15] C. Han, A. Misra, and S. Cheng, “Mobility-driven ble transmit-power adaptation for participatory data muling,” in 2018 IEEE 24th Interna-tional Conference on Parallel and Distributed Systems (ICPADS), 12 2018, pp. 962–971.

[16] S. S. Chawathe, “Beacon placement for indoor localization using blue-tooth,” in Int. IEEE Conference on Intelligent Transportation Systems (ITSC), Oct 2008, pp. 980–985.

[17] W. He, D. Wang, Y. Xiong, L. Chen, and Y. Liu, “On bounded positioning via bluetooth,” Jounal of Technology, in Chinese, under review.

[18] R. Luo and T.-J. Hsiao, “Indoor localization system based on hybrid wi-fi/ble and hierarchical topological fingerprinting approach,” IEEE Transactions on Vehicular Technology, vol. PP, pp. 1–1, 09 2019.

[19] S. Safavi, U. A. Khan, S. Kar, and J. M. F. Moura, “Distributed localization: A linear theory,” Proceedings of the IEEE, vol. 106, no. 7, pp. 1204–1223, 7 2018.

[20] R. M. Buehrer, H. Wymeersch, and R. M. Vaghefi, “Collaborative sensor network localization: Algorithms and practical issues,” Proceedings of the IEEE, vol. 106, no. 6, pp. 1089–1114, 6 2018.

[21] J. B. Andersen, T. S. Rappaport, and S. Yoshida, “Propagation mea-surements and models for wireless communications channels,” IEEE Communications Magazine, vol. 33, no. 1, pp. 42–49, Jan 1995.

[22] E. A. Doumith, S. A. Zahr, and M. Gagnaire, “Monitoring-tree: An inno-vative technique for failure localization in WDM translucent networks,” in GLOBECOM, 2010, pp. 1–6.

[23] W. He, P.-H. Ho, B. Wu, and J. Tapolcai, “On identifying SRLG failures in all-optical networks,” Optical Switching and Networking, vol. 10, no. 1, pp. 77 – 88, 2013, advances in Optical Networks Control and Management. [Online]. Available: http://www.sciencedirect.com/science/article/pii/S1573427712000641.