Удосконалений метод Дейкстри для визначення найкоротших маршрутів між вузлами зв’язку у системі військового зв’язку

Вадим Слюсар; Катерина Громлюк

doi:10.33099/2311-7249/2023-46-1-5-12

Автор(и)

Вадим Слюсар Центральний науково-дослідний інститут ОВТ Збройних Сил України, Україна https://orcid.org/0000-0002-2912-3149
Катерина Громлюк Військовий інститут телекомунікацій та інформатизації, Україна https://orcid.org/0000-0002-0617-7849

DOI:

https://doi.org/10.33099/2311-7249/2023-46-1-5-12

Ключові слова:

метод Дейкстри, багатошаровий граф, блокова матриця, блоковий торцевий добуток матриць, матриця інцидентності

Анотація

У статті удосконалено метод Дейкстри для системи військового зв’язку завдяки використанню матриці інцидентності вузлів і ліній зв’язку замість матриці інцидентності вузлів. Удосконалений метод адаптовано до моделі системи військового зв’язку, що формалізується блоковою матрицею інцидентності вузлів і ліній зв’язку з поділом блоків матриці за родами і складовими системи військового зв’язку. Суть удосконалення полягає у введені додаткових блоків до стандартного алгоритму Дейкстри з метою попереднього, точнішого обчислення вагових коефіцієнтів ліній зв’язку. Водночас, на основі використання блокової матриці вторинної інцидентності, а також квадратичної форми матриці інцидентності, запропоновано низку нових аналітичних виразів. Математичне моделювання, на основі спрощеної моделі системи військового зв’язку, підтвердило ефективність удосконаленого методу. Синтезований удосконалений метод точніше відповідає реальним умовам управління системою військового зв’язку і може бути використаний для потреб автоматизації процесу управління системою як основи для розробки інформаційно-аналітичних завдань.

Посилання

Снарський А. О., Ланде Д. В. Моделювання складних мереж : навчальний посібник. Київ : НТУУ «КПІ», 2015. 212 с.

Harary F. Graph theory. 3rd ed Reading, Massachusetts: Addison-Wesley, 1972. 274 p.

Агеев Д. В. Методика описания структуры современных телекоммуникационных систем с использованием многослойных графов. Восточно-Европейский журнал передовых технологий. 2010. № 6. С. 56–59. URL: http://journals.uran.ua/eejet/article/ view/3295/3096 (дата звернення: 03.03.2023).

Агеєв Д. В. Моделирование современных телекоммуникационных систем многослойными графами Проблеми телекомунікацій. 2010. №1. С.23 34. URL: http://openarchive.nure.ua/handle/document/2722 (дата звернення: 03.03.2023).

Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik. 1959. Vol.1. № 1. P. 269–271. URL: https://doi.org/10.1007/bf01386390 (date of access: 03.03.2023).

Cormen T., Leiserson Ch., Rivest R. and Stein C. Introduction to algorithms, fourth edition. [S. l.] : MIT Press, 2022 – 1332 p. 1312 р.

Levitin A. Introduction to the design & analysis of algorithms. 3rd ed. [S. l.]: Pearson 2011. 565 p.

Black P. E. Greedy algorithm. Dictionary of Algorithms and Data Structures. 2005. URL: https://www.nist.gov/dads/HTML/ greedyalgo.html (date of access: 03.03.2023).

Bellman R. On a routing problem. Quarterly of applied mathematics. 1958. Vol. 16. № 1. P. 87–90. URL: https://doi.org/10.1090/qam/102435 (date of access: 03.03.2023).

Ford L. R., Fulkerson D. R. Flows in networks (rand corporation research studies series) [S.l.] : Princeton Univ Pr, 1962. 198 p.

Слюсар В. І., Перепеліцин С. О. Аналіз топології багаторангових мереж на основі торцевого добутку матриць. Радіотехнічні поля, сигнали, апарати та системи : зб. наук. пр. ІХ Міжнар. наук.-техн. конф. 16–22 листопада 2020. Київ : НТУУ КПІ. С. 114–116. DOI:10.13140/RG.2.2.26965.04329.

Слюсар В. И., Перепелицын С. А. Применение торцевого произведения матриц в задачах анализа топологий маршрутизации многоранговых сетей. Озброєння та військова техніка. 2021. №1(29). C. 56–63.

Слюсар В. И. Торцевые произведения матриц в радиолокационных приложениях. Изв. ВУЗов. Радиоэлектроника. 1998. Т.41. № 3. С. 71–75.

Slyusar V. I. A family of face products of matrices and its properties. Cybernetics and systems analysis. 1999. Vol. 35. № 3. P. 379–384. URL: https://doi.org/10.1007/bf02733426 (date of access: 03.03. 2023).

Міночкін А. І., Рудаков В. І., Слюсар В. І. Основи воєнно-технічних досліджень. теорія та приклади : монографія / ред. А. П. Ковтуненко. Київ : Гранмна, 2011. Т.2 «Синтез засобів інформаційного забезпечення озброєння і військової техніки». С. 7–98, 354–521.

Зінченко К. А. Метод формалізації аналітичного опису системи військового зв’язку на основі тензорно-матричної теорії у поєднанні з теорією графів. Труди університету : збірник наукових праць Національного університету оборони України імені Івана Черняховського. 2022. №6(175). С. 232–248.

Військовий стандарт «Словник НАТО зі зв’язку. Частина 1 (AComP 01 (Edition 3) NATO COMMUNICATIONS GLOSSARY (Chapter 716–722), MOD)». Вид. офіц. Київ : ВІТІ, 2019. 212 с.

Ланде Д. В., Снарський А. О., Безсуднов І. В. Интернетика: навигация в сложных сетях: модели и алгоритмы. Ліброком, 2006. 264 с.

Головач Ю., Олемский О., Фербер К. фон та ін. Складні мережі. Журнал фізичних досліджень. 2006. Т. 10. №4. С. 247 289.