Алгоритм синтеза многосвязной сети

Алгоритм синтеза многосвязной сети — алгоритм для нахождения соединений между объектами проектируемой сети в соответствии с заданными критериями.

Исходные данные

В качестве исходных данных есть матрица расстояний (L) между конечными объектами сети (на практике в качестве них могут выступать например маршрутизаторы). Матрица квадратная, где каждый элемент (Lij=Lji) равен расстоянию (метры, километры) между i-м и j-м узлом. Lii=Ljj=0 — расстояние от текущего узла до самого себя. На основание данной матрицы и выбрав среду передачи информации (пусть это будут кабельные линии связи) можем построить матрицу стоимости (С) умножив расстояния на условную или реальную единицу стоимости метра или километра кабеля.

Построение матрицы базовой топологии

Строим матрицу базовой топологии (Cb). В качестве базовых топологий предлагается использовать один из таких вариантов — оптимальное кольцо, минимальное остовное дерево, звезда. Принцип построения данных топологий одинаков — минимальное расстояние между узлами в пределах заданной топологии отличающейся каждая по своим основным свойствам. Для оптимального кольца такими свойством является существование двух различных путей между узлами, что обеспечивает дублирование, для звезды — это наличие центрального узла, через который проходят все информационные потоки, для минимального остовного дерева — отсутствие в топологии замкнутых путей (петель).

Построение многосвязной сети

Построение многосвязной сети путем введения в матрицу базовой топологии дополнительных ветвей в соответствии с какими-либо ограничивающими критериями, при достижении которых многосвязная сеть считается построенной. В качестве таких критериев выбираются количество промежуточных узлов (Kij) на пути между двумя выбранными узлами i и j (по-другому критерий можно назвать — «количество переприёмов») и стоимость ввода ветви в сеть. Таким образом, задав некоторое ограничение на параметр К, и путем выбора из матрицы (С) минимальных элементов на каждом шаге данного алгоритма, мы постепенно получаем многосвязную сеть занимающую промежуточное, но не оптимальное место сравнительно с полносвязной сетью и сетью базовой топологии по стоимости и количеству переприёмов информации между двумя узлами. Когда заданное ограничение по критерию (К) будет достигнуто для всех узлов сети, многосвязная сеть считается готовой.

Усовершенствование алгоритма

Во втором пункте описанного выше метода предлагается выбирать из матрицы (С) на каждом шаге алгоритма не минимальное значение (Свводимое=Сijmin), а вводить в многосвязную сеть узел соответствующий критерию minimum((Сij/Cmin)+(Wmax/Wij)), где Сij — проверяемый на соответствие критерию элемент матрицы (С), Сmin — минимальный на данном шаге алгоритма элемент матрицы стоимости (С), Wij — величина показывающая изменение количество переприёмов (параметра К) по сравнению с состоянием сети до ввода ветви Сij, Wmax — максимально возможное изменение параметра W для текущего состояния сети. Для реализации данного усовершенствования на каждом шаге алгоритма происходит пересчёт текущего состояния сети, для построения матрицы W, отражающей изменение параметра К для всех элементов сети, при введении в неё элемента Сij, из которой собственно затем и берутся элементы Wij и Wmax. Шаги алгоритма разбиваются на подшаги, количество которых будет зависеть от величины сети.

Литература

• Рогинский В. Н., Харкевич А. Д., Шнепс М. А. и др.; Под ред. В. Н. Рогинского. Теория сетей связи: Учебник для вузов связи. — Радио и связь, 1981. — С. 192.
• Величко В.В., Субботин Е.А., Шувалов В.П., Ярославцев А.Ф. Телекоммуникационные системы и сети: Учебное пособие. В 3 томах. — Горячая линия–Телеком, 2005. — С. 592. — ISBN 5-93517-257-7
• Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. — Мир, 1984.
• В.П. Шувалов, Г.П. Катунин, Б.И. Крук и др.; Под ред. В.П. Шувалова. Системы электросвязи: Учебник для вузов. — М.: Радио и связь, 1987. — С. 512.
• Я.С. Дымарский. Задачи и методы оптимизации сетей связи. — Санкт-Петербург:СПбГУТ, 2005.
• Я.С. Дымарский. Методы и алгоритмы оптимизации сетей связи. — Санкт-Петербург:СПбГУТ, 2005.
• Зайченко Е.Ю. Анализ и синтез структуры глобальных вычислительных сетей. — Киев: ЗАО “Укрспецмонтаж”, 1998. — С. 108.