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


УДК 65.012.122

Маршрутизация в сетях автономных необитаемых подводных аппаратов

Грузликов А.М., Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М.


Читать статью полностью 
Язык статьи - русский

Ссылка для цитирования:
Грузликов А.М., Колесов Н.В., Литуненко Е.Г., Скородумов Ю.М. Маршрутизация в сетях автономных необитаемых подводных аппаратов // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21, № 6. С. 984–990. doi: 10.17586/2226-1494-2021-21-6-984-990


Аннотация
Предмет исследования. Автономные необитаемые подводные аппараты имеют широкий спектр применений, но их ограниченные возможности затрудняют использование некоторых функций, критических по времени выполнения. Для координации совместных действий между агентами применяется мультиагентный подход с обменом информацией. Для сетей автономных подводных аппаратов информационное взаимодействие осуществляется с использованием средств звукоподводной связи, особенностью которой является ненаправленное излучение, ограничение по скорости (килобиты в секунду) и радиусу обмена информацией. Это приводит к необходимости планирования маршрута обмена с использованием узлов в качестве ретрансляторов. Рассмотрены вопросы маршрутизации обменов для таких сетей. Исследование направлено на решение проблемы упорядочивания в каждом из аппаратов последовательности сообщений на этапе сеанса передачи. МетодПроблема упорядочения сообщений сведена к известной задаче flow shop планирования по суммарному критерию оптимизации — минимизация среднего времени пребывания работы в системе. Представлен алгоритм планирования сеансов связи, основанный на понятии разрешимого класса систем. На основании информационного взаимодействия между абонентами предложено соотнести состояние сети с одним из разрешимых классов систем с последующим применением алгоритма планирования. Основные результаты. Рассмотрен алгоритм планирования обменов. Сформулированы и доказаны утверждения для четырех известных разрешимых классов систем. Приведены результаты моделирования работы алгоритма. Практическая значимость. Разработанный алгоритм позволяет сократить суммарное время информационного обмена в сети автономных необитаемых подводных аппаратов и может использоваться специалистами при проектировании аппаратуры средств звукоподводной связи.

Ключевые слова: автономный подводный аппарат, маршрутизация, разрешимый класс систем, звукоподводная связь, суммарный критерий оптимизации, минимум среднего времени

Благодарности. Работа выполнена при поддержке гранта РФФИ 19-08-00052.

Список литературы
  1. Федосов В.П., Тарасов С.П., Пивнев П.П., Воронин В.В., Кучерявенко С.В., Легин А.А., Ломакина А.В., Франц В.А. Сети связи для подводных автономных роботизированных комплексов. Ростов-на-Дону, Таганрог: ЮФУ, 2018. 178 с.
  2. Туфанов И.Е., Щербатюк А.Ф. Некоторые результаты морских испытаний централизованной системы управления группой морских роботов // Управление большими системами. 2016. № 59. С. 233–246.
  3. Тель Ж. Введение в распределенные алгоритмы. М.: МЦНМО, 2009. 616 с.
  4. Nawaz M., Enscore Jr. E.E., Ham I. A Heuristic algorithm for the m-machine, n-job flow-shop sequencing problem // Omega. 1983. V. 11. N 1. P. 91–95. https://doi.org/10.1016/0305-0483(83)90088-9
  5. Bruker P. Scheduling Algorithms. Leipzig: Springer, 2007. 371 p. https://doi.org/10.1007/978-3-540-69516-5
  6. Liu J.W.S. Real-Time Systems. NJ: Prentice Hall, 2000. 600 p.
  7. Bocewicz G., Banaszak Z.A. Declarative approach to cyclic steady state space refinement: periodic process scheduling // International Journal of Advanced Manufacturing Technology. 2013. V. 67. N 1-4. P. 137–155. https://doi.org/10.1007/s00170-013-4760-0
  8. 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. V. 67. N 1-4. P. 231–241. https://doi.org/10.1007/s00170-013-4769-4
  9. 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
  10. Лазарев А.А. Теория расписаний. Методыиалгоритмы. М.: ИПУРАН, 2019. 408 с.
  11. Wang J.-B., Xia Z.-Q. Flow shop scheduling with deteriorating jobs under dominating machines // Omega. 2006. V. 34. N 4. P. 327–336. https://doi.org/10.1016/j.omega.2004.10.006
  12. 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. V. 88. N 5-8. P. 1535–1546. https://doi.org/10.1007/s00170-016-8828-5
  13. Грузликов А.М., Колесов Н.В., Скородумов Ю.М., Толмачева М.В. Планирование заданий в распределенных системах реального времени // Известия РАН. Теория и системы управления. 2017. № 2. C. 67–76. https://doi.org/10.7868/S000233881702010X
  14. Харди Г.Г., Литтльвуд Дж.Е., Полиа Г. Неравенства. М.: Государственное издательство иностранной литературы, 1948. 456 с.
  15. 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.
  16. Taillard E. Benchmarks for basic scheduling problems // European Journal of Operational Research. 1993. V. 64. N 2. P. 278–285. https://doi.org/10.1016/0377-2217(93)90182-M


Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License
Информация 2001-2024 ©
Научно-технический вестник информационных технологий, механики и оптики.
Все права защищены.

Яндекс.Метрика