sustainНадежностьDependability1729-26462500-3909RAMS Journal Limited liability company10.21683/1729-2646-2020-20-2-35-42sustain-372Research ArticleФУНКЦИОНАЛЬНАЯ НАДЕЖНОСТЬ И ФУНКЦИОНАЛЬНАЯ ЖИВУЧЕСТЬ. ТЕОРИЯ И ПРАКТИКАFUNCTIONAL DEPENDABILITY AND FUNCTIONAL SURVIVABILITY. THEORY AND PRACTICEРазработка алгоритмов для надежного обмена данными между автономными роботами на основе принципов самоорганизующейся сетиDevelopment of algorithms of self-organizing network for reliable data exchange between autonomous robotsЕрмаковА. В.ErmakovA. V.

Александр В. Ермаков – аспирант кафедры ИВТиИБ

656038, Алтайский край, г. Барнаул, пр. Ленина, 46

Alexander V. Ermakov, post-graduate student, IT and Information Security Department

656038, Altai Krai, Barnaul, 46 Lenina Ave., Administration of Information and Telecommunication Support, Information Systems Development Unit, k.a. of Ermakov A.V.

tour0@ya.ruСучковаЛ. И.SuchkovaL. I.

Лариса И. Сучкова – доктор технических наук, проректор по учебной работе

656038, Алтайский край, г. Барнаул, пр. Ленина, 46

Larisa I. Suchkova, Doctor of Engineering, Prorector for Learning and Teaching

656038, Altai Krai, Barnaul, 46 Lenina Ave., k.a. of Suchkova L.I., Prorector for Learning and Teaching

li.suchkova@yandex.ruАлтайский государственный технический университет им. И.И. ПолзуноваРоссияPolzunov Altai State Technical UniversityRussian Federation2020080620202023542Copyright © Ермаков А.В., Сучкова Л.И., 20202020Ермаков А.В., Сучкова Л.И.Ermakov A.V., Suchkova L.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.dependability.ru/jour/article/view/372

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

Factors affecting the reliability of data transmission in networks with nodes with periodic availability were considered. The principles of data transfer between robots are described; the need for global connectivity of communications within an autonomous system is shown, since the non-availability of information on the intentions of other robots reduces the effectiveness of the robotics system as a whole and affects the fault tolerance of a team of independent actors performing distributed activities. It is shown that the existing solutions to the problem of data exchange based on general-purpose IP networks have drawbacks; therefore, as the basis for organizing autonomous robot networks, we used developments in the domain of topological models of communication systems allowing us to build self-organizing computer networks. The requirements for the designed network for reliable message transfer between autonomous robots are listed, the option of organizing reliable message delivery using overlay networks, which expand the functionality of underlying networks, is selected. An overview of existing popular controlled and non-controlled overlay networks is given; their applicability for communication within a team of autonomous robots is evaluated. The features and specifics of data transfer in a team of autonomous robots are listed. The algorithms and architecture of the overlay self-organizing network were described by means of generally accepted methods of constructing decentralized networks with zero configurations. As a result of the work, general principles of operation of the designed network were proposed, the message structure for the delivery algorithm was described; two independent data streams were created, i.e. service and payload; an algorithm for sending messages between network nodes and an algorithm for collecting and synchronizing the global network status were developed. In order to increase the dependability and fault tolerance of the network, it is proposed to store the global network status at each node. The principles of operation of a distributed storage are described. For the purpose of notification on changes in the global status of the network, it is proposed to use an additional data stream for intra-network service messages. A flood routing algorithm was developed to reduce delays and speed up the synchronization of the global status of a network and consistency maintenance. It is proposed to provide network connectivity using the HELLO protocol to establish and maintain adjacency relations between network nodes. The paper provides examples of adding and removing network nodes, examines possible scalability problems of the developed overlay network and methods for solving them. It confirms the criteria and indicators for achieving the effect of self-organization of nodes in the network. The designed network is compared with existing alternatives. For the developed algorithms, examples of latency estimates in message delivery are given. The theoretical limitations of the overlay network in the presence of intentional and unintentional defects are indicated; an example of restoring the network after a failure is set forth.

надежностьдоставка сообщенийгарантированная доставка данныховерлейная сетьавтономный роботгрупповое взаимодействиемультиагентная робототехническая системаdependabilitymessage deliveryguaranteed data deliveryoverlay networkautonomous robotgroup interactionmulti-agent robotic systemReferencesЛавров Д.Н. Принципы построения протокола гарантированной доставки сообщений // Математические структуры и моделирование. 2018. № 4(48). С. 139–146. DOI: 10.25513/2222-8772.2018.4.139-146Lavrov D.N. Principles of building a protocol for guaranteed message delivery. Mathematical structures and modeling. 2018;4(48):139-146. DOI: 10.25513/22228772.2018.4.139-146. (in Russ.)Гусс С.В., Лавров Д.Н. Подходы к реализации сетевого протокола обеспечения гарантированной доставки при мультимаршрутной передаче данных // Математические структуры и моделирование. 2018. № 2(46). С. 95–101. DOI: 10.25513/2222-8772.2018.2.95-101Guss S.V., Lavrov D.N. Approaches to implementing a secure delivery network protocol for multipath data transfer. Mathematical structures and modeling. 2018;2(46):95-101. DOI: 10.25513/2222-8772.2018.2.95-101. (in Russ.)Сорокин А.А., Дмитриев В.Н. Описание систем связи с динамической топологией сети при помощи модели «мерцающего» графа // Вестник Астраханского государственного технического университета. Серия: Управление, вычислительная техника и информатика. 2009. № 2. С. 134–139.Sorokin A.A., Dmitriev V.N. Description of communication systems with dynamic network topology by means of model “flickering” graph. Vestnik of Astrakhan State Technical University. Series: management, computer science and informatics. 2009;2:134-139. (in Russ.)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.02Parker L.E. Distributed Intelligence: Overview of the Field and its Application in Multi-Robot Systems. AAAI Fall Symposium: Technical Report, FS-07-06. 2008:5–14. DOI: 10.14198/JoPha.2008.2.1.02.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.Ota J. Multi-agent robot systems as distributed autonomous systems. Advanced engineering informatics. 2006;20(1):59-70. DOI: 10.1016/j.aei.2005.06.002.Arai T. et al. Advances in multi-robot systems // IEEE Transactions on robotics and automation. 2002. Vol. 18. No. 5. P. 655–661.Arai T. et al. Advances in multi-robot systems. IEEE Transactions on robotics and automation. 2002;18(5):655–661.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.Krieger M.J.B., Billeter J.B., Keller L. Ant-like task allocation and recruitment in cooperative robots. Nature. 2000;406(6799):992–995. DOI: 10.1038/35023164.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.008645Winfield A.F.T., Nembrini J. Safety in numbers: Fault tolerance in robot swarms. International Journal on Modelling Identification and Control. 2006;1:30–37. DOI: 10.1504/IJMIC.2006.008645.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.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:31–42. DOI: 10.1145/1080829.1080833.Srinivasan S. Design and use of managed overlay networks: дис. Georgia Institute of Technology, 2007.Srinivasan S. Design and use of managed overlay networks. Georgia Institute of Technology; 2007.Clark D. et al. Overlay Networks and the Future of the Internet // Communications and Strategies. 2006. Vol. 63. P. 109.Clark D. et al. Overlay Networks and the Future of the Internet. Communications and Strategies. 2006;63:109.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.40Benson 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:152–163. DOI: 10.1109/IoTDI.2015.40.Stoica I. et al. Internet indirection infrastructure // ACM SIGCOMM Computer Communication Review. ACM, 2002. Vol. 32. No. 4. P. 73–86.Stoica I. et al. Internet indirection infrastructure. ACM SIGCOMM Computer Communication Review. ACM. 2002;3(4):73–86.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.990433Ripeanu M. Peer-to-peer architecture case study: Gnutella network. Proceedings first international conference on peer-to-peer computing. IEEE. 2001:99–100. DOI: 10.1109/P2P.2001.990433.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.1210295Leibowitz N., Ripeanu M., Wierzbicki A. Deconstructing the kazaa network. Proceedings the Third IEEE Workshop on Internet Applications. WIAPP. 2003:112–120. DOI: 10.1109/WIAPP.2003.1210295.Dingledine R., Mathewson N., Syverson P. Tor: The second-generation onion router. Naval Research Lab Washington DC, 2004.Dingledine R., Mathewson N., Syverson P. Tor: The second-generation onion router. Naval Research Lab Washington DC; 2004.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_9Herrmann 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. Berlin, Heidelberg: Springer. 2011:155–174. DOI: 10.1007/9783-642-22263-4_9.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.8944505Tandon 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:1–6. DOI: 10.1109/ICCCNT45670.2019.8944505.Кудряшова Э.Е., Вовченко А.В., Олейников Р.А. Исследование сети NЕТSUКUКU на основе фрактальных множеств // Вестник Международной академии системных исследований. Информатика, экология, экономика. 2008. Т. 11. № 1. С. 55–57.Kudriashova E.E., Vovchenko A.V., Oleynikov R.O. [A study of the NЕТSUКUКU fractal set-based network]. Vestnik Mezhdunarodnoy akademii sistemnykh issledovaniy. Informatika, ekologiya, ekonomika. 2008. 11(1):55-57. (in Russ.)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.1013Kumar A. et al. Ulysses: a robust, low-diameter, lowlatency peer-to-peer network. European transactions on telecommunications. 2004. 15(6):571–587. DOI: 10.1002/ett.1013.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.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. Berlin, Heidelberg: Springer; 2001.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.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.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.6784954Feng J., Li J. Google protocol buffers research and application in online game. IEEE conference anthology. 2013:1–4. DOI: 10.1109/ANTHOLOGY.2013.6784954.Ермаков А.В., Сучкова Л.И. Реализация протокола передачи данных между интеллектуальными автономными роботами. Свидетельство о государственной регистрации программы для ЭВМ № 2019666759 от 13 декабря 2019 г.Ermakova A.V., Suchkova L.I. [Implementation of the data communication protocol between smart autonomous robots]. Certificate of official registration of computer software no. 2019666759 of December 13, 2019.Ермаков А. В., Сучкова Л. И. Проектирование сетевой коммуникационной среды для реализации управления в коллективе автономных роботов // ЮжноСибирский научный вестник. 2019. Т. 2. № 4 С. 28–31. DOI: 10.25699/SSSB.2019.28.48969Ermakov A.V., Suchkova L.I. Designing a network communication environment for the implementation of the management system in the autonomous robots team. South-Siberian Scientific Bulletin. 2019;2(4):28–31. DOI: 10.25699/SSSB.2019.28.48969.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.8934727Ermakov 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:1–5. DOI: 10.1109/FarEastCon.2019.8934727.Половко А. М., Гуров С. В. Основы теории надежности: 2-е изд., перераб. и доп. СПб.: БХВ-Петербург, 2006. 702 с.: ил. ISBN 5-94157-541-6Polovko А.М., Gurov S.V. [Introduction into the dependability theory: study guide: second edition, updated and revised]. Saint Petersburg: BHV-Peterburg; 2006. ISBN 5-94157-541-6. (in Russ.)

The authors declare that there are no conflicts of interest present.