<div>
	Routing in networks of autonomous underwater vehicles</div>

Andelexar M. Gruzlikov , Nikolay V. Kolesov, Elizaveta G. Litunenko, Yuri M. Skorodumov

2021 , VOLUME 21, NUMBER 6 ( november-december )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

doi: 10.17586/2226-1494-2021-21-6-984-990

Routing in networks of autonomous underwater vehicles

A. M. Gruzlikov, N. V. Kolesov, E. G. Litunenko, Y. M. Skorodumov

Read the full article

Article in Russian

For citation:

Gruzlikov A.M., Kolesov N.V., Litunenko E.G., Skorodumov Yu.M. Routing in networks of autonomous underwater vehicles. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2021, vol. 21, no. 6, pp. 984–990 (in Russian). doi: 10.17586/2226-1494-2021-21-6-984-990

Abstract

Autonomous underwater vehicles have a wide range of applications, but their limited capabilities make it difficult to perform some time critical functions. To coordinate joint actions between agents, it is proposed to use a multi-agent approach with information exchange. For networks of autonomous underwater vehicles, information interaction is carried out with sound underwater communication equipment, which shows non-directional radiation and imposes limitations on speed (kilobits per second) and on the radius of information exchange. This results in the need for planning an exchange route using nodes as repeaters. The paper considers issues of routing exchanges for such networks. The research focuses on the problem of ordering the sequence of messages in each of the devices at the stage of the transmission session. The issue of ordering messages is reduced to the well-known problem of flow shop planning according to the total optimization criterion that is minimizing the average time spent by job in the system. The authors present an algorithm for scheduling communication sessions based on the concept of a resolvable class of systems. Based on information interaction between subscribers, it is proposed to correlate the state of the network with one of the resolvable classes of systems with the subsequent application of the scheduling algorithm. The main results involve the analysis of an algorithm for scheduling exchanges and present a model of its operation. Assertions are formulated and proved for four known decidable classes of systems. The developed algorithm makes it possible to reduce the total time of information exchange in the network of autonomous underwater vehicles and can be used by specialists in the design of equipment for sound underwater communications.

Keywords: autonomous underwater vehicle, routing, solvable class of systems, sound underwater communications, total optimization criterion, minimum average time

Acknowledgements. This work was supported by Russian Foundation for Basic Research (Russian Federation), project No. 19-08-00052.

References

Fedosov V.P., Tarasov S.P., Pivnev P.P., Voronin V.V., Kucheryavenko S.V., Legin A.A., Lomakina A.V., Frants V.A. Communication Networks for Underwater Autonomous Robotic Complexes. Rostov-on-Don, Taganrog, Southern Federal University Publ., 2018, 178 p. (in Rusian)
Tuphanov I., Scherbatyuk А. Some marine trial results of centralized control system for marine robot group. Large-Scale Systems Control, 2016, no. 59, pp. 233–246. (in Russian)
Tel G. Introduction to Distributed Algorithms. Cambridge University Press, 2000, 596 p.
Nawaz M., Enscore Jr. E.E., Ham I. A Heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 1983, vol. 11, no. 1, pp. 91–95. https://doi.org/10.1016/0305-0483(83)90088-9
Bruker P. Scheduling Algorithms. Leipzig, Springer, 2007, 371 p. https://doi.org/10.1007/978-3-540-69516-5
Liu J.W.S. Real-Time Systems. NJ, Prentice Hall, 2000, 600 p.
Bocewicz G., Banaszak Z.A. Declarative approach to cyclic steady state space refinement: periodic process scheduling. International Journal of Advanced Manufacturing Technology, 2013, vol. 67, no. 1-4, pp. 137–155. https://doi.org/10.1007/s00170-013-4760-0
Korytkowski P., Rymaszewski S., Wiśniewski T. Ant colony optimization for job shop scheduling using multi-attribute dispatching rules. International Journal of Advanced Manufacturing Technology, 2013, vol. 67, no. 1-4, pp. 231–241. https://doi.org/10.1007/s00170-013-4769-4
Pinedo M.L., Scheduling. Theory: Algorithms and Systems. Springer Science and Business Media, 2016, 670 p. https://doi.org/10.1007/978-3-319-26580-3
Lazarev A.A. Scheduling Theory. Methods and Algorithms. Moscow, V.A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, 2019, 408 p. (in Russian)
Wang J.-B., Xia Z.-Q. Flow shop scheduling with deteriorating jobs under dominating machines. Omega, 2006, vol. 34, no. 4, pp. 327–336. https://doi.org/10.1016/j.omega.2004.10.006
Gruzlikov A.M., Kolesov N.V., Skorodumov I.M., Tolmacheva M.V. Using solvable classes in flowshop scheduling. International Journal of Advanced Manufacturing Technology, 2017, vol. 88, no. 5-8, pp. 1535–1546. https://doi.org/10.1007/s00170-016-8828-5
Gruzlikov A.M., Kolesov N.V., Skorodumov Y.M., Tolmacheva M.V. Task scheduling in distributed real-time systems. Journal of Computer and Systems Sciences International, 2017, vol. 56, no. 2, pp. 236–244. https://doi.org/10.1134/S1064230717020101
Hardy G.H., Littlewood J.E., Pólya G. Inequalities. Cambridge. Cambridge Univ. Press, 1934, 314 p.
Heidergott B., Olsder G.J., van der Woude J. Max Plus at work, Princeton Series in Applied Mathematics. Princeton, Princeton University Press, 2006, 226 p.
Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research, 1993, vol. 64, no. 2, pp. 278–285. https://doi.org/10.1016/0377-2217(93)90182-M

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License