HEURISTIC ALGORITHMS FOR FINDING THE MINIMUM STEINER TREE IN THE PROBLEM OF OPTIMIZING THE DEPLOYMENT AND MOTION CONTROL OF SEVERAL FLYING INFORMATION AND TELECOMMUNICATION ROBOTS
DOI:
https://doi.org/10.20535/2411-2976.22022.53-61Keywords:
flying information and telecommunication robots, mobile episodic radio network, algorithm, topology, locationAbstract
Background. The article explores the problem of combining the motion control of existing FITRs and the deployment of new FITRs so that the number of new FITRs deployed to support the communication of terrestrial subscribers can be minimized. This problem is formulated as the Steiner Minimum Tree Problem (SMT) with existing mobile Steiner points with a constraint on the edges length of the network graph.
Objective. Improve the mathematical model for ensuring the connectivity of episodic radio networks using FITRs and improve the algorithms for providing the connectivity of episodic radio networks using FITRs.
Methods. The two algorithms (deploying new FITRs before moving existing FITRs, and moving existing FITRs before deployment of new FITRs) separate the problem and solve the deployment problem, the movement one after the other. In contrast, the algorithm for deploying new FITRs while moving existing FITRs optimizes the deployment problem and the control of movement across and solves these two problems simultaneously.
Results. A proposed method includes three heuristic algorithms for placing new FITRs, taking into account the movement of existing FITRs (that is, considering scenarios for moving existing FITRs: deploying new FITRs before, after, or during the movement of existing FITRs) for the SMT problem with existing mobile Steiner points with a constraint on the edges length of the network graph.
Conclusions. Evaluation of the effectiveness of the proposed algorithms in various scenarios shows that algorithms taking into account the movement of existing FITRs are always more efficient (in terms of the number of newly added FITRs) than an algorithm without taking into account the movement of existing FITRs.
References
O. Lysenko, S. Valuiskyi, P. Kirchu, and A. Romaniuk, «Optimal control of telecommunication aeroplatform in the area of emergency», Information and Telecommunication Sciences, vol. 4, no. 1, pp. 14–20, 2013.
S. Valuiskyi, A. Lysenko, T. Pryshchepa, and S. Chumachenko, «The problem of finding a rational topology of wireless sensor networks using UAVs», Second International Scientific-Practical Conference Problems of Infocommunications Science and Technology (PIC S&T), pp. 213–215, 2015.
O. Lysenko, V. Romaniuk, O. Tachinina, and S. Valuiskyi, «The problems of control in wireless sensor and mobile ad-hoc networks», Integrated Computer Technologies in Mechanical Engineering, vol. 1113, pp. 385–402, 2020.
M. Zhu, F. Liu, Z. Cai, and M. Xu, «Maintaining connectivity of Manets through multiple unmanned aerial vehicles», Mathematical Problems in Engineering, vol. 2015, pp. 1–14, 2015.
O. Zinchenko, «Bespilotnye letatelnye apparaty: primenenie v celyah aerofotosemki dlya kartografirovaniya (chast 1)», Racurs, 2011. [Online]. Available: https://racurs.ru/press-center/articles/bespilotnye-letatelnye-apparaty/UAV-for-mapping-1/.
M. Yevtodyeva and S. Tselitsky, «Military unmanned aerial vehicles: Trends in development and production», Pathways to Peace and Security, vol. 2, pp. 104–111, 2019.
«Primenenie BPLA v usloviyah boevyh dejstvij», Albatros, 05-Jun-2019. [Online]. Available: https://www.alb.aero/about/articles/primenenie-bpla-v-usloviyakh-boevykh-deystviy/
