|
СПЕЦИАЛЬНЫЙ ВЫПУСК
Augmented data routing algorithms for satellite delay-tolerant networks. Development and validation
[О подходе к разработке и валидации алгоритмов маршрутизации на разрывных сетях]
A. A. Fedorov, I. V. Soshilov, V. N. Loginov Moscow Institute of Physics and Technology,
9 Institute lane, Moscow, 141701, Russia
Аннотация:
В данной статье рассматривается проблема централизованного планирования маршрутов передачи данных в сетях, устойчивых к задержкам и разрывам. Исходная проблема расширяется дополнительными требованиями к хранению узлов и процессу связи. Во-первых, предполагается, что связь между узлами графа устанавливается с помощью антенн. Во-вторых, предполагается, что каждый узел имеет хранилище конечной емкости. Существующие работы не рассматривают и не решают задачу с этими ограничениями. Предполагается, что заранее известны информация о сообщениях, подлежащих обработке, информация о конфигурации сети в указанные моменты времени, взятые с определенными периодами, информация о временных задержках для ориентации антенн для передачи данных и ограничения на объем хранения данных на каждом спутнике группировки. Два хорошо известных алгоритма — CGR и Earliest Delivery withAll Queues — модифицированы для удовлетворения расширенных требований. Полученные алгоритмы решают задачу поиска оптимального маршрута в сети, устойчивой к разрывам, отдельно для каждого сообщения. Также рассматривается проблема валидации алгоритмов в условиях отсутствия тестовых данных. Предложены и апробированы возможные подходы к валидации, основанные на качественных предположениях, описаны результаты экспериментов. Проведен сравнительный анализ производительности двух алгоритмов решения задачи маршрутизации. Два алгоритма, названные RDTNAS-CG и RDTNAS-AQ, были разработаны на основе алгоритмов CGR и Earliest Delivery with All Queues соответственно. Оригинальные алгоритмы были значительно расширены и была разработана дополненная реализация. Валидационные эксперименты были проведены для проверки минимальных требований «качества» к правильности алгоритмов. Сравнительный анализ производительности двух алгоритмов показал, что алгоритм RDTNAS-AQ на несколько порядков быстрее, чем RDTNAS-CG.
Ключевые слова:
DTN, алгоритмы на графах, комбинаторные алгоритмы, количественная валидация.
Поступила в редакцию: 25.12.2021 Исправленный вариант: 31.01.2022 Принята в печать: 02.02.2022
Образец цитирования:
A. A. Fedorov, I. V. Soshilov, V. N. Loginov, “Augmented data routing algorithms for satellite delay-tolerant networks. Development and validation”, Компьютерные исследования и моделирование, 14:4 (2022), 983–993
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/crm1011 https://www.mathnet.ru/rus/crm/v14/i4/p983
|
Статистика просмотров: |
Страница аннотации: | 67 | PDF полного текста: | 15 | Список литературы: | 27 |
|