INVESTIGATING MULTIPATH MESSAGE ROUTING ALGORITHMS THROUGH THREE-DIMENSIONAL GRAPH MODELS OF AUV NETWORKS
Abstract
This paper examines a class of telecommunication networks with mobile nodes, an important subclass within which is the so-called geography-aware networks. Their distinguishing feature is the availability of information about the geographic coordinates of all nodes in the network to each individual node, whereby each node is aware of the complete topology of the network graph, which enables rapid identification of the required number of information transmission routes between any two nodes. The purpose of this article is to investigate multipath routing algorithms. To this end, we propose a method for the automatic synthesis of adequate test models capable of representing networks of virtually unlimited complexity. The proposed solution is based on a compositional approach, in which a relatively simple network fragment that satisfies given constraints is first formed, and then the resulting model is constructed as a composition of copies of this fragment. To investigate the efficiency of multipath routing algorithms, we propose a compositional method for the random synthesis of test models of complex networks that satisfy constraints on distances between the vertices. This method was applied to the investigation of two routing algorithms, resulting in a large body of illustrative model data. The obtained results, presented in the form of graphs, demonstrate an increase in the gain in message transmission time as the queue length in the target flow grows. While the efficiency of multipath routing is insignificant under low network load conditions, its usefulness increases with growing network load. A similar increase in efficiency is demonstrated when transitioning from an algorithm that does not allow intersecting paths to an algorithm that allows such intersections.
References
1. Hentati A.I., Fourati L.C. Comprehensive survey of UAVs communication networks, Comput. Stand. Interfaces, 2020, Vol. 72, Art. 103451.
2. Inzartsev A.V., Kiselev L.V., Kostenko V.V., Matvienko Yu.V., Pavin A.M., Shcherbatyuk A.F. Podvodnye robototekhnicheskie kompleksy: sistemy, tekhnologii, primenenie [Underwater robotic systems: sys-tems, technologies, applications]. Vladivostok: Institut problem morskikh tekhnologiy Dal'nevos-tochnogo otdeleniya Rossiyskoy akademii nauk, 2018, 368 p.
3. Inzartsev A.V., Eliseenko G.D., Pavin A. M., Panin M.A. Obnaruzhenie i obsledovanie lokal'nykh donnykh ob"ektov s pomoshch'yu gruppy spetsializirovannykh avtonomnykh podvodnykh ob"ektov [Detection and inspection of local bottom objects using a group of specialized autonomous underwater objects], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2018, No. 1.
4. Kuznetsov K.A., Paramonov A.I., Mutkhanna A.S.A., Kucheryavyy A.E. Model' i metody marshrutizatsii trafika v seti svyazi s ispol'zovaniem BPLA [Model and methods of traffic routing in a communication network using UAVs], Tr. uchebnykh zavedeniy svyazi [Proceedings of Educational Institutions of Communication], 2024, Vol. 10, No. 4, pp. 62-72.
5. Kormen T.Kh., Leyzerson Ch.I., Rivest R.L., Shtayn K. Algoritmy: postroenie i analiz [Algorithms: con-struction and analysis]. Moscow: Vil'yams, 2010, 1296 p.
6. Shuvalov V.P., Varaksina I.Yu. Klassifikatsiya metodov mnogoputevoy marshrutizatsii [Classification of multipath routing methods], T-comm, 2014, No. 1.
7. Bogatyrev V.A., Bogatyrev S.V., Bogatyrev A.V. Control of Multipath Transmissions in the Nodes of Switching Segments of Reserved Paths, 2022 International Conference on Information, Control, and Communication Technologies (ICCT), 2022, pp. 1-5. DOI: 10.1109/ICCT56057.2022.9976839.
8. Eremenko A.S. Potokovaya model' mnogoputevoy marshrutizatsii po neperesekayushchimsya putyam v telekommunikatsionnoy seti [Flow model of multipath routing along non-intersecting paths in a tele-communication network], Problemy telekommunikatsiy [Problems of Telecommunications], 2015,
No. 1, pp. 85-93.
9. Zuo, Y., Ling, Z., Yuan, Y.A. Hybrid multi-path routing algorithm for industrial wireless mesh networks, J Wireless Com Network, 2013, 82 (2013).
10. Venkatesh K., Srinivas L., Krishnan M.M., Shanthini A. QoS improvisation of delay sensitive communi-cation using SDN based multipath routing for medical applications, Future Generation Computer Sys-tems, 2019, 93, pp. 256-65.
11. Ducatelle F, Di Caro GA, Gambardella L.M. Ant agents for hybrid multipath routing in mobile ad hoc networks, Proceedings of the Second Annual Conference on Wireless On-demand Network Systems and Services (WONS 2005). St Moritz, 19–21 January 2005, pp. 44-53.
12. Sahhaf S., Tavernier W., Colle D., Pickavet M. Adaptive and reliable multipath provisioning for media transfer in SDN-based overlay networks, Computer Communications, 2017, 106, pp. 107-16.
13. Koryachko V.P., Perepelkin D.A. Razrabotka i issledovanie matematicheskoy modeli mnogoputevoy adaptivnoy marshrutizatsii v setyakh svyazi s balansirovkoy nagruzki [Development and research of a mathematical model of multipath adaptive routing in communication networks with load balancing], El-ektrosvyaz' [Electrosvyaz], 2014, No. 12.
14. Rajasekaran K., Balasubramanian K. Energy Conscious based Multipath Routing Algorithm in WSN, International Journal of Computer Network and Information Security (IJCNIS), 2016, Vol. 8, No. 1, pp. 27-34.
15. Gruzlikov A.M., Kolesov N.V., Litunenko E.G., Tyul'nikov V.S. Mnogoputevaya marshrutizatsiya v setyakh s uskorennoy dostavkoy soobshcheniy [Multipath routing in networks with accelerated message delivery], Nauchno-tekhnicheskiy vestnik informatsionnykh tekhnologiy, mekhaniki i optiki [Scientific and Technical Bulletin of Information Technology, Mechanics and Optics], 2026, No. 1, pp. 62-72.
16. Gruzlikov A.M., Kolesov N.V., Litunenko E.G., Skorodumov Yu.M. Optimizatsiya informatsionnykh obmenov v seti avtonomnykh abonentov [Optimization of information exchanges in the network of au-tonomous subscribers], TiSU [Theory and Control Systems], 2022, No. 6.
17. Frieze A., Karonsky M. Introduction to random graphs. Cambridge University Press, 2025, 698 p.
18. van der Hofstad R. Random graphs and complex networks. Vol. 2. Eindhoven University Press, 2024, 508 p.
19. Prüfer H. Neuer Beweis eines Satzes über Permutationen, Arch. Math. Phys., 1918.
20. Gruzlikov A.M., Kolesov N.V., Tolmacheva M.V., Skorodumov Yu.M. Grafovyy podkhod k naznacheni-yu zadaniy v raspredelennykh sistemakh real'nogo vremeni [Graph approach to task assignment in dis-tributed real-time systems], TiSU [Theory and Control Systems], 2014, No. 4, pp. 28-38.
