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

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

Содержание

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

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

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

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

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

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

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

Во втором пункте описанного выше метода предлагается выбирать из матрицы (С) на каждом шаге алгоритма не минимальное значение (Cвводимое=С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.

Ссылки



Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Алгоритм синтеза многосвязной сети" в других словарях:

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
https://dic.academic.ru/dic.nsf/ruwiki/1722668 Нажмите правой клавишей мыши и выберите «Копировать ссылку»