N.I. Petukhov1, D.V. Tsaregorodtsev2, R.S. Kulikov3, A.P. Malyshev4

1−4 National Research University «MPEI» (Moscow, Russia)

In this paper, the problem of minimization of the number of local navigation system (LNS) reference points (RPs) and RPs’ location optimization is posed according to the criterion of ensuring the factor of geometric dilution of precision (GDOP) averaged over the space is not worse than a given one. According to authors’ best knowledge, this is the first time such a problem has been posed and solved. An approximate numerical solution to the problem based on a genetic algorithm is proposed. The effectiveness of the proposed method is assessed by simulating the placement of a different number of ranging LNS RPs in rooms of various configurations and comparing the result with the quasi-optimal result of a complete numerical search of all possible locations of the LNS anchors. The conclusion is made on the applicability of the proposed method for solving the problem and the prospects of building on its basis a tool for automating the development of positional LNS to reduce the development time and the cost of infrastructure.

Petukhov N.I., Tsaregorodtsev D.V., Kulikov R.S., Malyshev A.P. Application of genetic algorithm for determining the locations of reference points of local navigation system and minimizing their number. Radiotekhnika. 2021. V. 85. № 9. P. 27−40.  DOI: https://doi.org/10.18127/j00338486-202109-03 (In Russian)

1. GLONASS. Principy postroenija i funkcionirovanija. Pod red. A.I. Perova, V.N. Harisova. Izd. 4-e, pererab. i dop. M.: Radiotehnika. 2010.
2. GLONASS. Modernizacija i perspektivy razvitija. Monografija. Pod red. A.I. Perova. M.: Radiotehnika. 2020 (In Russian).
3. Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press. 1975 (In Russian).
4. Goldberg D. Genetic Algorithms in Search, Optimization, and Machine Learning. Massachusetts: Addison-Wesley. 1989. ISBN 0201157675.
5. Gladkov L.A., Kurejchik V.V., Kurejchik V.M. Geneticheskie algoritmy: Ucheb. posobie. Pod red. V.M. Kurejchika. Rostov-na-Donu: OOO «Rostizdat». 2004 (In Russian).
6. Panchenko T.V. Geneticheskie algoritmy: Ucheb.-metodich. posobie. Pod red. Ju.Ju. Tarasevicha. Astrahan': Izdatel'skij dom «Astrahanskij universitet». 2007 (In Russian).
7. Perov A.I., Ustinov A.Ju. Obobshhennyj geometricheskij faktor v radionavigacionnyh sistemah s ispol'zovaniem psevdosputnikov. Radiotehnika. 2015. № 12. S. 101-110 (In Russian).
8. Svidetel'stvo o gosudarstvennoj registracii programmy dlja JeVM № 2016613197 (RF). Programma dlja ocenki geometricheskogo faktora sputnikovoj radionavigacionnoj sistemy s uchetom lokal'nogo funkcional'nogo dopolnenija psevdosputnikov: № 2016610533: zajavl. 27.01.2016: opubl. 21.03.2016. A.Ju. Ustinov, A.I. Perov; zajavitel' federal'noe gosudarstvennoe bjudzhetnoe obrazovatel'noe uchrezhdenie vysshego professional'nogo obrazovanija «Nacional'nyj issledovatel'skij universitet «MJeI» (In Russian).
9. Ash Joshua N, Moses Randolph L. On optimal anchor node placement in sensor localization by optimization of subspace principal angles. IEEE International Conference on Acoustics, Speech and Signal Processing. 2008.
10. Suwatthikul Charuwalee, Chantaweesomboon Witsarawat, Manatrinon Supatra, Athikulwongse Krit, Kaemarungsi Kamol. Implication of Anchor Placement on Performance of UWB Real-Time Locating System. IEEE 8th International Conference of Information and Communication Technology for Embedded Systems (IC-ICTES). Chonburi, Thailand. 2017.
11. https://www.sewio.net/the-dilution-of-precision-anchor-geometry. Dostup 15 avgusta 2021 g. (In Russian).
12. Soldatkin S.V., Chernyh S.V., Boev A.E., Rukovishnikov N.N. Razrabotka prilozhenija po opredeleniju geometricheskogo faktora dlja lokal'nyh navigacionnyh sistem. Tezisy dokladov 27-j Mezhdunar. nauch.-tehnich. konf. studentov i aspirantov «Radiojelektronika, jelektrotehnika i jenergetika» (Moskva, 11–12 marta 2021 g.). M.: OOO «Centr poligraficheskih uslug «RADUGA». 2021. S. 79 (In Russian).