Модернизация транспортных сетей связи методом наложения с использованием минимальных связывающих деревьев Штейнера

Зюзин А. Н., Репин Б. Г., Ясинский С. А.

Читать статью полностью

  Модернизация транспортных сетей связи методом наложения с использованием минимальных связывающих деревьев Штейнера(754,37 KB)

Аннотация

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

Ключевые слова:

телекоммуникационная система – telecommunications system; транспортная сеть связи – communication transport network; метод наложения – overlay method; взвешенное покрытие – weighted coverage; дерево Штейнера – Steiner tree; библиотека NetworkX – NetworkX library.

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

1. Грязев, А. Н. Методы развития транспортных сетей связи для цифровой экономики РФ / А.Н. Грязев, С.А. Ясинский, А.Н. Зюзин // Вестник связи. – 2018. – № 2. – С. 19 – 22.

2. Грязев, А. Н. Многослойная графовая модель для модернизации и развития транспортных сетей связи / А.Н. Грязев, А.Н. Зюзин, С.А. Ясинский // Вестник связи. – 2018. – № 5. – С. 13 – 16.

3. Рунеев, А. Ю. Концепция ТСС. Первичные сети связи. Концепция создания и развития первичной сети территориальной системы связи / А.Ю. Рунеев, Н.А. Зюзин // Телекоммуникационные технологии. – 2001. – Вып. 1. – С. 3–13.

4. Сторожук, Н. Л. Формализованный подход к применению метода наложения для принятия решения на модернизацию и развитие транспортных сетей связи / Н.Л. Сторожук, А.Н. Зюзин, С.А. Ясинский // Информация и Космос. – 2018. – № 4. – С. 15–19.

5. Иванов, А. О. Задача Штейнера на плоскости или плоские минимальные сети / А.О. Иванов, А.А. Тужилин // Математический сборник. – 1991. – Т. 182, № 12. – C. 1813–1844.

6. Минимальное остовное дерево – Minimum spanning tree [Электронный ресурс] : Википедия. Свободная энциклопедия. – Режим доступа: https://ru.abcdef.wiki/wiki/Minimum_spanning_tree [дата обращения 30.05.22], свободный. – Загл. с экрана.

7. NetworkX is a Python package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks [Электронный ресурс] : библиотека Python. – Режим доступа: https://networkx.org/ [дата обращения 30.05.22], свободный. – Загл. с экрана.

8. Source code for networkx.algorithms.approximation. steinertree [Электронный ресурс] : библиотека Python. – Режим доступа: https://networkx.org/documentation/stable/_ modules/networkx/algorithms/approximation/steinertree. html#steiner_tree [дата обращения 30.05.22], свободный. – Загл. с экрана.

9. Свидетельство об официальной регистрации программы для ЭВМ № 21021 Российская Федерация. Расчет оптимального покрытия линий сети связи для нескольких направлений связи / Зюзин А.Н., Зюзин Д.Н., Малюков К.А.; Военная академия связи. – 06.04.2021.