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

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

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

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: Regarding the Intelligence in Distributed Intelligent Systems. – 2007. – С. 1-6.

5. Ota J. Multi-agent robot systems as distributed autonomous systems //Advanced engineering informatics. – 2006. – Т. 20. – №. 1. – С. 59-70.

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

7. Krieger M. J. B., Billeter J. B., Keller L. Ant-like task allocation and recruitment in cooperative robots //Nature. – 2000. – Т. 406. – №. 6799. – С. 992. Режим доступа: https://serval.unil.ch/resource/serval:BIB_EE7009999976.P001/REF.pdf

8. Winfield A. F. T., Nembrini J. Safety in numbers: Fault tolerance in robot swarms // International Journal on Modelling Identification and Control. – 2006. – Т. 1. – С. 30-37.

9. Bicket J. et al. Architecture and evaluation of an unplanned 802.11 b mesh network //Proceedings of the 11th annual international conference on Mobile computing and networking. – ACM, 2005. – С. 31-42. – Режим доступа: http://www.cs.cmu.edu/~srini/15-744/readings/roofnet-mobicom05.pdf

10. Srinivasan S. Design and use of managed overlay networks : дис. – Georgia Institute of Technology, 2007. – Режим доступа: https://smartech.gatech.edu/bitstream/handle/1853/14501/srinivasan_sridhar_200705_phd.pdf

11. Clark D. et al. Overlay Networks and the Future of the Internet //Communications and Strategies. – 2006. – Т. 63. – С. 109.

12. Andersen D. et al. Resilient overlay networks. – ACM, 2001. – Т. 35. – No. 5. – С. 131-145. – Режим доступа: https://dspace.mit.edu/bitstream/handle/1721.1/86657/48995363-MIT.pdf

13. Stoica I. et al. Internet indirection infrastructure //ACM SIGCOMM Computer Communication Review. – ACM, 2002. – Т. 32. – No. 4. – С. 73-86. – Режим доступа: http://citris-uc.org/files/2003-03-20-Microsoft/pdfs/stoica_internet_infrastructure.pdf

14. Ripeanu M. Peer-to-peer architecture case study: Gnutella network //Proceedings first international conference on peer-to-peer computing. – IEEE, 2001. – С. 99-100. – Режим доступа: http://people.cs.uchicago.edu/matei/PAPERS/gnutella-rc.pdf

15. Leibowitz N., Ripeanu M., Wierzbicki A. Deconstructing the kazaa network //Proceedings the Third IEEE Workshop on Internet Applications. WIAPP 2003. – IEEE, 2003. – С. 112-120. – Режим доступа: https://www.globus.org/sites/default/files/kazaa.pdf

16. Dingledine R., Mathewson N., Syverson P. Tor: The second-generation onion router. – Naval Research Lab Washington DC, 2004. – Режим доступа: https://svn.torproject.org/svn/projects/design-paper/tor-design.pdf

17. Zantout B. et al. I2P data communication system //Proceedings of ICN. – 2011. – С. 401-409.

18. Macker J. Mobile ad hoc networking (MANET): Routing protocol performance issues and evaluation considerations. – 1999. – Режим доступа: https://tools.ietf.org/html/rfc2501.html

19. Pumo A. L. Overview of the Netsukuku network //arXiv preprint arXiv:0705.0815. – 2007.

20. Kumar A. et al. Ulysses: a robust, low‐diameter, low‐latency peer‐to‐peer network //European transactions on telecommunications. – 2004. – Т. 15. – №. 6. – С. 571-587. – Режим доступа: https://onlinelibrary.wiley.com/doi/abs/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. – С. 329-350. – Режим доступа: https://link.springer.com/chapter/10.1007/3-540-45518-3_18

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