Двух кольцевая» топологическая структура

Заданы: места расположения центров коммутации и матрица расстояний [R].

Требуется определить: оптимальную двух кольцевую структуру сети (рис2) по критерию , где m=число ребер Гамильтонова цикла, структуры и размещения одного ребра образующее ее двух кольцевую суть.

Оценить: структурную живучесть сети в виде минимального суммарного числа возможных маршрутов между двумя произвольными центрами коммутации.

Критерий оптимальности: +L_kj

Рис.36. Проект «двух кольцевой» структуры сети.

      

 

 

На рисунке 36 представлен макет «двух» топологической структуры с минимальной суммарной длиной кабеля H_min = 95 у.е.

    Следует отметить, что «двух кольцевая» структура всегда будет иметь большую суммарную длину кабеля, чем «одно кольцевая».

    Алгоритм расчета «двух кольцевой» топологической структуры.

Рис.37. Алгоритм расчета «двух кольцевой» топологической структуры

Алгоритм решения включает:

1. Разложение исходной сети на две подсети.

2. В первой подсети с помощью алгоритма «Коммивояжер» определяется минимальное значение Гамильтонова цикла ( =min).

3. Длина ребра делящего сеть на две подсети определяется путем перебора ребра разделяющего сеть на подсети с заданным числом узлов. Если n – четное, то число переборов равно n/2,, если n – нечетное, то число переборов равно (n-1)+4, где n – число узлов сети.

4. Минимальное значение суммы всех длин ребер сети, будет равно (  + L_kj=min).

3.3 «Трех кольцевая» топологическая структура

Заданы: места расположения центров коммутации (абонентов) рис 1.; измерены расстояния между центрами и составлена матрица расстояний [R](см. задачу №1).

Требуется определить: оптимальную трех кольцевую структуру сети (рис3) по критерию  где j-число ребер данной структуры сети.

Оценить: структурную живучесть сети в виде минимального числа возможных маршрутов между двумя любыми узлами (центрами коммутации сети).

Критерий оптимальности:[Г(s) + L_sj +L_sk + L_sm +L_km]= min

Рис.38. «трех кольцевая» структура сети.

        

 

 

На рисунке 38 представлен макет «трех кольцевой» топологической структуры с минимальной суммарной длиной кабеля H_min = 112 у.е.

    Следует отметить, что «трех кольцевая» структура всегда будет иметь большую суммарную длину кабеля, чем «двух кольцевая».

 

Алгоритм расчета «трех кольцевой» топологической структуры.

Рис.39. Алгоритм расчета «трех кольцевой» топологической структуры.

 

Алгоритм решения включает:

1. Разложение исходной сети на две подсети. Условием разложения является включение I-го узла исходной сети (i=1,n) во вторую подсеть. При этом задача «Коммивояжер» решается с меньшим числом узлов (узел I отсутствует).

2. Для сети, не содержащей узел решается задача «Коммивояжер». Находится минимальный Гамильтонов цикл.

3. Во второй подсети определяется суммарная длина четырех ребер [L_sj +L_sk + L_sm +L_km]= min.

4. Минимальное решение находится переборным методом. Если I изменяется от 1 до N и n² переборов для определения минимального значения суммарной длины ребер второй подсети.

Общее минимальное решение определяется, когда выполняется условие [Г(s) + L_sj +L_sk + L_sm +L_km]= min