The method of placing the base stations of the local positioning system in the work area with obstacles

This article discusses the existing methods of positioning the base stations of the local positioning system in the work area. The choice of the station placement method largely determines the final accuracy and economic feasibility of the entire designed system. A review of the scientific literature has shown that there is currently no universal method for placing base stations in the positioning work area. Existing solutions implement either one of the standard approaches of station placement on a grid, or embody a method of sorting through many combinations of placements. The method of placing stations on a grid is not adapted to the conditions of designing a positioning system in a complex-shaped work area divided internally by various partitions and massive objects, since it does not take into account the peculiarities of radio signal propagation. The method of sorting through various combinations of base station placement in most software implementations is reduced to minimizing the influence of a geometric factor (Geometric Dilution of Precision - GDOP) on the measurement error of distances to stations and also does not take into account the distortion of the navigation signal introduced when passing through various obstacles. Therefore, the development of a methodology for the placement of base stations of a local positioning system is an urgent problem and the article is devoted to its solution. According to the proposed methodology, the working area containing massive obstacles on its area is divided into convex free subdomains in accordance with a greedy algorithm, in which the base stations are arranged. As a result of the work on the article, the principles for the operation of the base station placement methodology are outlined and a universal algorithm for station placement in work areas with obstacles is proposed.

1. Fokin G.A. Search model for topology of local range-measuring system in 5G positioning as per pre-set geometric factor. Radiotekhnicheskie i telekommunikatsionnye sistemy = Radio Engineering and Telecommunication Systems. 2021;(4):27–38. (In Russ.). https://doi.org/10.24412/2221-2574-2021-444-27-38

2. Ahlander J., Posluk M. Deployment Strategies for High Accuracy and Availability Indoor Positioning with 5G. URL: https://www.diva-portal.org/smash/record.jsf?pid=diva2:1440620 (Accessed 10th March 2024).

3. Rajagopal N., Chayapathy S., Sinopoli B., Rowe A. Beacon placement for range-based indoor localization. In: 2016 International Conference on Indoor Positioning and Indoor Navigation (IPIN), 04-07 October 2016, Alcala de Henares, Spain. IEEE; 2016. P. 1–8. https://doi.org/10.1109/IPIN.2016.7743626

4. O’Rourke J. Art Gallery Theorems and Algorithms. New York: Oxford University Press Oxford; 1987. 282 p.

5. Famili A., Stavrou A., Wang H., Park J.-M. iDROP: Robust Localization for Indoor Navigation of Drones with Optimized Beacon Placement. IEEE Internet of Things Journal. 2023;10(16):14226–14238. https://doi.org/10.1109/JIOT.2023.3280084

6. Löffler S., Becker I., Bückert C., Hofstedt P. Enhanced Optimal Beacon Placement for Indoor Positioning: A Set Variable Based Constraint Programming Approach. In: Informatics in Control, Automation and Robotics – 20th International Conference, ICINCO 2023: Proceedings of the 20th International Conference on Informatics in Control, Automation and Robotics (ICINCO 2023): Volume 1, 13-15 November, Rome, Italy. SCITEPRESS – Science and Technology Publications; 2023. P. 70–79. https://doi.org/10.5220/0012203400003543

7. Bais A., Kiwan H., Morgan Y. On Optimal Placement of Short Range Base Stations for Indoor Position Estimation. Journal of Applied Research and Technology. 2014;12(5):886–897. https://doi.org/10.1016/S1665-6423(14)70595-4

8. Wu Z., Yao Z., Lu M. Optimal Beacon Deployment for Positioning in Cluttered Indoor Environments. IEEE Sensors Journal. 2023;23(4):4256–4266. https://doi.org/10.1109/JSEN.2023.3234562

9. Krizhanovskii M.N., Ivanov V.S., Litvinov S.V., Tikhonova O.V. Programma razbieniya mnozhestva bazovykh stantsii lokal'noi sistemy pozitsionirovaniya na peresekayushchiesya gruppy: publ. 25.04.2024. Software copyright registration Certificate № 2024619654.

10. Krizhanovsky M.N. Modeling of the algorithm for taking into account obstacles in the calculation of location in short-range positioning systems. Voprosy elektromekhaniki. Trudy VNIIEM = Electromechanical matters. VNIIEM studies. 2023;192(1):14–20. (In Russ.).

11. Lee B., Woo D.-M., Park M.-K., Kim S. Development of self-localizer using collaboration of trilateration and triangulation. In: 2014 11th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD), 19-21 August 2014, Xiamen, China. IEEE; 2014. P. 729–733. https://doi.org/10.1109/FSKD.2014.6980926