Preview

Надежность

Расширенный поиск

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

https://doi.org/10.21683/1729-2646-2020-20-2-

Аннотация

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


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


Для описания алгоритмов и архитектуры оверлейной самоорганизующейся сети использовались общепринятые методы построения децентрализованных сетей с нулевой конфигурацией. В результате работы были предложены общие принципы функционирования спроектированной сети, описана структура сообщений для алгоритма доставки, произведено выделение служебных маршрутизируемых потоков данных, описаны алгоритмы пересылки сообщений между узлами сети, разработаны алгоритмы сбора и синхронизации глобального статуса сети.


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


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

Об авторах

Александр Васильевич Ермаков
АлтГТУ
Россия

аспирант кафедры ИВТиИБ АлтГТУ

656038, Алтайский край, г. Барнаул, пр. Ленина, 46, УИТП, ОРИС, Ермакову А.В.

Вклад в работу: обзор литературы, разработка алгоритмов.


Лариса Иннокентьевна Сучкова
АлтГТУ
Россия

д.т.н., проректор по учебной работе АлтГТУ

656038, Алтайский край, г. Барнаул, пр. Ленина, 46, проректору по УР, Сучковой Л.И.

Вклад в работу: формализация требований и постановка задачи.


Список литературы

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. – С. 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. – 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-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). – IEEE, 2016. – С. 152-163. DOI: 10.1109/IoTDI.2015.40

13. Stoica I. et al. Internet indirection infrastructure // ACM SIGCOMM Computer Communication Review. – ACM, 2002. – Т. 32. – No. 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. – IEEE, 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. – Springer, Berlin, Heidelberg, 2011. – С. 155-174. DOI: 10.1007/978-3-642-22263-4_9

18. Tandon N., Patel N. K. An Efficient Implementation of Multichannel Transceiver for Manet Multinet Environment // 2019 10th International Conference on Computing, Communication and Networking Technologies (ICCCNT). – IEEE, 2019. – С. 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. – Т. 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. – 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. – Т. 31. – №. 4. – С. 149-160.

23. Feng J., Li J. Google protocol buffers research and application in online game // IEEE conference anthology. – IEEE, 2013. – С. 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. – С. 1-5. DOI: 10.1109/FarEastCon.2019.8934727

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


Дополнительные файлы

1. Рисунок 1 – Пример оверлейной сети, построенной поверх IP-сети
Тема
Тип Рисунок
Посмотреть (189KB)    
Метаданные
2. Рисунок 2 – Диаграмма последовательности обработки принятого сообщения узлами-соседями на примерах проверки доступности узла-соседа и информировании изменений в статусе сети
Тема
Тип Рисунок
Посмотреть (23KB)    
Метаданные
3. Рисунок 3 – Схема работы системы для алгоритма лавинной маршрутизации
Тема
Тип Рисунок
Посмотреть (63KB)    
Метаданные
4. Рисунок 4 – Сравнение временных задержек доставки пакета стандартными протоколами при наличии потерь пакетов в сети. а) TCP, 0% потерь, б) TCP, 5% потерь, в) TCP, 10% потерь, г) UDP, 0% потерь, д) UDP, 5% потерь, е) UDP, 10% потерь
Тема
Тип Рисунок
Посмотреть (311KB)    
Метаданные
5. Рисунок 5 – Сравнение временных задержек доставки пакета внутри оверлейной сети при наличии дефектов сети
Тема
Тип Рисунок
Посмотреть (191KB)    
Метаданные

Для цитирования:


Ермаков А.В., Сучкова Л.И. Разработка алгоритмов для надёжного обмена данными между автономными роботами на основе принципов самоорганизующейся сети. Надежность. 2020;20(2). https://doi.org/10.21683/1729-2646-2020-20-2-

Просмотров: 14


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1729-2646 (Print)
ISSN 2500-3909 (Online)