Development of algorithms of self-organizing network for reliable data exchange between autonomous robots

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.

dependability, message delivery, guaranteed data delivery, overlay network, autonomous robot, group interaction, multi-agent robotic system

1. Lavrov 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.)

2. Guss 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.)

3. 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.)

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: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;20(1):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;18(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–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;1: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: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;63: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:152–163. DOI: 10.1109/IoTDI.2015.40.

13. Stoica I. et al. Internet indirection infrastructure. ACM SIGCOMM Computer Communication Review. ACM. 2002;3(4):73–86.

14. Ripeanu 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.

15. Leibowitz 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.

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. Berlin, Heidelberg: Springer. 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:1–6. DOI: 10.1109/ICCCNT45670.2019.8944505.

19. 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.)

20. Kumar 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.

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. Berlin, Heidelberg: Springer; 2001.

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.

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

24. 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.

25. Ermakov 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.

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:1–5. DOI: 10.1109/FarEastCon.2019.8934727.

27. Polovko А.М., 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.)