Методы построения кольцевой структуры ЛВС

Математическая модель кольцевой структуры ЛВС

В кольцевой локальной сети все АС с помощью физической среды передачи данных объединяются в кольцо. В общем случае для получения математической модели задачи синтеза кольцевой структуры моноканала достаточно дополнить ограничения (2.5) в модели условием, требующим замкнуть гамильтоновую цепочку в исходной точке после однократного обхода всех АС. Тогда ограгичение (2.5) можно записать в следующем виде:

å Z_jk = 1 (j¹k, kÎM°, M°_k(1)Ì M°),

^jÎM°k(1)

å Z_jk = 1 (j¹k, kÎM°, M°_k(2)ÎM_k°), (2.7)

^jÎM°k(1)

где M°_k1 = M°_k-1ÇM°_k и M°_k(2) = M°_k (M°_k-1Ç M°_k) – подмножества АС, которые могут быть соеденены с j-й АС. Ограничения (2.7) обеспечивают объединение АС в кольцо при минимальных затратах на передачу информации (2.6).

Методы построения кольцевой структуры ЛВС.

3.2 Алгоритм модификации метода парных оценок без

изолированной вершины (МРОК1).

Сначала строится гамильтоновый цикл, начиная обход с первого столбца. Далее осуществляется вычисление D-оценок для каждого столбца. Для начала обхода матрицы затрат выбирается столбец с максимальным положительным значением D–оценки. Этот процесс продолжается до тех пор, пока не получим вариант структуры, где все D–оценки равны или меньше нуля (рис. 2.8).

Рис 2.8. Первая итерация алгоритма МРОК1

Алгоритм работает следующим образом:

Шаг 1. Определить F=¥, Д=Æ,Z=Æ, M={1,2,…,i,…,n}, N={1,2,…,j,…,n}.

Шаг 2. Выбрать столбец с номером j и найти C_kj=min{C_ij}.

^iÎM

Принять x_kj=1 и g=j k¹j.

Шаг 3. Определить М=М/к, N=N/j, Z=Z+C_kj и Д=Д+1. Если Д<n-1, то перейти к шагу 4, иначе- к шагу 5.

Шаг 4. Принять j=k и найти C_kj=min{C_ij}.

^iÎM/g

Определить x_kj=1 и перейти к шагу 3.

Шаг 5. Принять j=k, k=g, x_kj=1 и Z=Z+C_kj. Определить M={1,2,…,n} и N={1,2,…,n}. Положить N₁=N\k и N₁=N₁\g.

Шаг 6. Если Z<F, то принять F=Z и перейти к шагу 7. В противном случае- к шагу 8.

Шаг 7. Для всех столбцов jÎN₁ вычислить оценки Dj по (2.47) и

выбрать столбец с Dg= max Dg.

^jÎN1

Положить g=j и перейти к шагу 2.

Шаг 8. Проверить, все ли столбцы с Dj>0 просмотрены. Если нет, то выбрать следующий столбец с Dj>0 и перейти к шагу 2. В противном случае цепь со значением F является оптимальной гамильтоновой цепью. Конец алгоритма.

СПИСОК ЛИТЕРАТУРЫ

1. Ж.С. Сарыпбеков Модели и методы проектирования локальных вычислительных сетей. (Учебное пособие)