Разработка алгоритмов для надежного обмена данными между автономными роботами на основе принципов самоорганизующейся сети

Рассмотрены факторы, влияющие на надежность передачи данных в сетях с узлами с периодической доступностью. Приведены принципы передачи данных между роботами, показана необходимость глобальной связности коммуникаций внутри автономной системы, так как отсутствие информации о намерениях других автономных роботов понижает эффективность робототехнической системы в целом и отрицательно влияет на отказоустойчивость в условиях распределения работ в коллективе независимых исполнителей поставленного задания. Показано, что существующие решения задачи обмена данными на основе IP-сетей общего назначения обладают рядом недостатков, поэтому в качестве основы организации сетевого взаимодействия автономных роботов использовались наработки в области топологических моделей систем связи, что позволяет строить самоорганизующиеся сети. Перечислены требования к проектируемой сети для надежной передачи сообщений между автономными роботами, выбран вариант организации надежной доставки сообщений с помощью оверлейных сетей, позволяющих расширить функционал сетей со стабильной конфигурацией. Приведен обзор существующих управляемых и неуправляемых оверлейных сетей, произведена оценка их применимости для коммуникации внутри коллектива автономных роботов. Описаны требования к механизму обмена данными в связи с особенностями и спецификой работы коллектива автономных роботов. Для описания алгоритмов и архитектуры оверлейной самоорганизующейся сети использовались общепринятые методы построения децентрализованных сетей с нулевой конфигурацией. В результате работы были предложены общие принципы функционирования спроектированной сети, описана структура сообщений для алгоритма доставки, произведено выделение служебных маршрутизируемых потоков данных, описаны алгоритмы пересылки сообщений между узлами сети, разработаны алгоритмы сбора и синхронизации глобального статуса сети. Для повышения надежности и отказоустойчивости работы сети предложено хранение глобального статуса сети на каждом из узлов. Описаны принципы функционирования распределенного хранилища данных. Для информирования об изменениях в статусе сети предложено использование отдельного канала управления для внутрисетевых служебных сообщений, не пересекающегося с передаваемыми данными. Разработан алгоритм лавинной маршрутизации для уменьшения задержек и ускорения процесса синхронизации глобального статуса сети и поддержки его консистентности. Предложено использовать hello-протокол для установки и поддержания соседских отношений между узлами сети. Приведены примеры добавления и удаления узлов сети, рассмотрены возможные проблемы масштабируемости разрабатываемой сети и способы их решения. Подтверждены критерии и показатели достижения эффекта самоорганизации отдельных узлов в сеть. Произведено сравнение спроектированной сети с существующими аналогами. Для разработанных алгоритмов приведены примеры расчетных оценок временных задержек доставки сообщений. Указаны теоретические ограничения оверлейной сети при наличии преднамеренных и непреднамеренных дефектов, а также приведен пример восстановления работоспособности сети после сбоя.

надежность, доставка сообщений, гарантированная доставка данных, оверлейная сеть, автономный робот, групповое взаимодействие, мультиагентная робототехническая система

1. Лавров Д.Н. Принципы построения протокола гарантированной доставки сообщений // Математические структуры и моделирование. 2018. № 4(48). С. 139–146. DOI: 10.25513/2222-8772.2018.4.139-146

2. Гусс С.В., Лавров Д.Н. Подходы к реализации сетевого протокола обеспечения гарантированной доставки при мультимаршрутной передаче данных // Математические структуры и моделирование. 2018. № 2(46). С. 95–101. DOI: 10.25513/2222-8772.2018.2.95-101

3. Сорокин А.А., Дмитриев В.Н. Описание систем связи с динамической топологией сети при помощи модели «мерцающего» графа // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. 2009. № 2. С. 134–139.

4. Parker L.E. Distributed Intelligence: Overview of the Field and its Application in Multi-Robot Systems // AAAI Fall Symposium: Technical Report, FS-07-06. 2008. P. 5–14. DOI: 10.14198/JoPha.2008.2.1.02

5. Ota J. Multi-agent robot systems as distributed autonomous systems //Advanced engineering informatics. 2006. Vol. 20. No. 1. P. 59-70. DOI: 10.1016/j.aei.2005.06.002.

6. Arai T. et al. Advances in multi-robot systems // IEEE Transactions on robotics and automation. 2002. Vol. 18. No. 5. P. 655–661.

7. Krieger M. J. B., Billeter J. B., Keller L. Ant-like task allocation and recruitment in cooperative robots // Nature. 2000. Vol. 406. No. 6799. P. 992–995. DOI: 10.1038/35023164.

8. Winfield A. F. T., Nembrini J. Safety in numbers: Fault tolerance in robot swarms // International Journal on Modelling Identification and Control. 2006. Vol. 1. P. 30–37. DOI: 10.1504/IJMIC.2006.008645

9. Bicket J. et al. Architecture and evaluation of an unplanned 802.11 b mesh network // Proceedings of the Annual International Conference on Mobile Computing and Networking, MOBICOM. ACM, 2005. P. 31–42. DOI: 10.1145/1080829.1080833.

10. Srinivasan S. Design and use of managed overlay networks: дис. Georgia Institute of Technology, 2007.

11. Clark D. et al. Overlay Networks and the Future of the Internet // Communications and Strategies. 2006. Vol. 63. P. 109.

12. Benson K.E. et al. Resilient overlays for IoT-based community infrastructure communications // 2016 IEEE First International Conference on Internet-of-Things Design and Implementation (IoTDI). 2016. P. 152–163. DOI: 10.1109/IoTDI.2015.40

13. Stoica I. et al. Internet indirection infrastructure // ACM SIGCOMM Computer Communication Review. ACM, 2002. Vol. 32. No. 4. P. 73–86.

14. Ripeanu M. Peer-to-peer architecture case study: Gnutella network // Proceedings first international conference on peer-to-peer computing. IEEE, 2001. P. 99–100. DOI: 10.1109/P2P.2001.990433

15. Leibowitz N., Ripeanu M., Wierzbicki A. Deconstructing the kazaa network // Proceedings the Third IEEE Workshop on Internet Applications. WIAPP, 2003. IEEE, 2003. P. 112–120. DOI: 10.1109/WIAPP.2003.1210295

16. Dingledine R., Mathewson N., Syverson P. Tor: The second-generation onion router. Naval Research Lab Washington DC, 2004.

17. Herrmann M., Grothoff C. Privacy-implications of performance-based peer selection by onion-routers: a real-world case study using I2P // International Symposium on Privacy Enhancing Technologies Symposium. Springer, Berlin, Heidelberg, 2011. С. 155–174. DOI: 10.1007/9783-642-22263-4_9

18. Tandon N., Patel N. K. An Efficient Implementation of Multichannel Transceiver for Manet Multinet Environment // 10th International Conference on Computing, Communication and Networking Technologies (ICCCNT). IEEE, 2019. P. 1–6. DOI: 10.1109/ICCCNT45670.2019.8944505

19. Кудряшова Э.Е., Вовченко А.В., Олейников Р.А. Исследование сети NЕТSUКUКU на основе фрактальных множеств // Вестник Международной академии системных исследований. Информатика, экология, экономика. 2008. Т. 11. № 1. С. 55–57.

20. Kumar A. et al. Ulysses: a robust, low-diameter, low-latency peer-to-peer network // European transactions on telecommunications. 2004. Vol. 15. No. 6. P. 571–587. DOI: 10.1002/ett.1013

21. Rowstron A., Druschel P. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems // IFIP/ACM International Conference on Distributed Systems Platforms and Open Distributed Processing. Springer, Berlin, Heidelberg, 2001.

22. Stoica I. et al. Chord: A scalable peer-to-peer lookup service for internet applications // ACM SIGCOMM Computer Communication Review. 2001. Vol. 31. No. 4. P. 149–160.

23. Feng J., Li J. Google protocol buffers research and application in online game // IEEE conference anthology. IEEE, 2013. P. 1–4. DOI: 10.1109/ANTHOLOGY.2013.6784954

24. Ермаков А.В., Сучкова Л.И. Реализация протокола передачи данных между интеллектуальными автономными роботами. Свидетельство о государственной регистрации программы для ЭВМ № 2019666759 от 13 декабря 2019 г.

25. Ермаков А. В., Сучкова Л. И. Проектирование сетевой коммуникационной среды для реализации управления в коллективе автономных роботов // ЮжноСибирский научный вестник. 2019. Т. 2. № 4 С. 28–31. DOI: 10.25699/SSSB.2019.28.48969

26. Ermakov A., Suchkova L. Development of Data Exchange Technology for Autonomous Robots Using a Self-Organizing Overlay Network // 2019 International Multi-Conference on Industrial Engineering and Modern Technologies (FarEastCon). IEEE, 2019. P. 1–5. DOI: 10.1109/FarEastCon.2019.8934727

27. Половко А. М., Гуров С. В. Основы теории надежности: 2-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2006. 702 с.: ил. ISBN 5-94157-541-6