22-30

УДК 621.396.49
DOI: 10.25686/2306-2819.2019.2.22

СНИЖЕНИЕ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ
КОНСТРУИРОВАНИЯ ДОПУСТИМЫХ МНОГОМЕРНЫХ
МАРШРУТОВ МЕТОДА СОВМЕСТНОЙ ДИНАМИЧЕСКОЙ МАРШРУТИЗАЦИИ

Ю. С. Винтенкова, С. В. Козлов
Казанский национальный исследовательский технический университет им. А.Н. Туполева (КНИТУ-КАИ),
Российская Федерация, 420111, Казань, ул. К. Маркса, 10
E-mail: vintenkova.yulia@gmail.com

АННОТАЦИЯ

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

КЛЮЧЕВЫЕ СЛОВА

метод совместной динамической маршрутизации; множество допустимых маршрутов; многомерные маршруты; теория графов.

ПОЛНЫЙ ТЕКСТ (pdf)

СПИСОК ЛИТЕРАТУРЫ

1. Спирина Е.А. Оптимизация распределения информации в фиксированных сетях широкополосного радиодоступа с учетом внутрисистемных помех // Журнал радиоэлектроники [электронный журнал]. 2015. № 9. Доступно по ссылке: http://jre.cplire.ru/jre/sep15/5/text.pdf.
2. Спирина Е.А., Козлов С.В. Метод маршрутизации, обеспечивающий повышение пропускной способности IP сетей в условиях внутрисистемных помех // Журнал радиоэлектроники [электронный журнал]. 2015. № 12. Доступно по ссылке: http://jre.cplire.ru/jre/dec15/3/text.pdf.
3. Пат. 2608678 Российская Федерация, МПК С1 H04L 12/64. Способ многомерной динамической маршрутизации в сети связи c пакетной передачей сообщений / Винтенкова Ю.С., Козлов С.В., Спирина Е.А.; заявитель и патентообладатель ФГБОУ ВО «Казанский нац. исслед. техн. ун-т им. А. Н. Туполева-КАИ». – № 2015149360; заявл. 17.11.2015.; опубл. 23.01.2017. Бюл. №3.
4. Цимбал В.А., Шабанов А.К. Концептуальная модель высокоскоростной сети связи на основе динамических многомерных маршрутов передачи // Труды Международного симпозиума «Надежность и качество». Пенза: Пензенский государственный университет. 2006. Т. 1. С. 191-192.
5. Luby Michael. A Simple Parallel Algorithm for the Maximal Independent Set Problem // SIAM Journal on Computing. 1986. Vol. 15, Iss. 4. Pp. 1036-1055.
6. Blelloch Guy, Fineman Jeremy, Shun Julian. Greedy Sequential Maximal Independent Set and Matching Are Parallel on Average // Proceedings of the 24th ACM symposium on Parallelism in algorithms and architectures, 2012. Pp. 308-317.
7. Олемской Игорь Владимирович, Фирюлина Оксана Сергеевна. Алгоритм поиска наибольшего независимого множества // Вестник СпбГу. Серия 10. Прикладная математика. Информатика. Процессы управления. 2014. № 1. С.78-89.
8. Bron Coen, Kerbosch Joep. Algorithm 457: finding all cliques of an undirected graph // Communications of the ACM. 1973. Vol. 16. Iss. 9. Pp. 575-577.
9. Tsukiyama S., Ide M., Ariyoshi H. and Shirakawa I. A new algorithm for generating all maximal independent sets // SIAM Journal on Computing. 1977. No 6. Pp. 505-517.
10. David S. Johnson, Mihalis Yannakakis, Christos H. Papadimitriou. On generating all maximal independent sets // Information Processing Letters. 1988. Vol. 27. Iss. 3. Pp. 119-123.
11. Makino K., Uno T. New Algorithms for Enumerating All Maximal Cliques. SWAT 2004. Lecture Notes in Computer Science, 2004. Vol. 3111. Springer, Berlin, Heidelberg, P. 260-272.

Для цитирования: Винтенкова Ю. С., Козлов С. В. Снижение вычислительной сложности конструирования допустимых многомерных маршрутов метода совместной динамической маршрутизации // Вестник Поволжского государственного технологического университета. Сер.: Радиотехнические и инфокоммуникационные системы. 2019. № 2 (42). С. 22-30. DOI: 10.25686/2306-2819.2019.2.22