Построение маршрута при групповой рассылке сетевых пакетов данных (стр. 4 из 8)

Результаты экспериментов показали, что зависимость логарифма времени работы ЭВМ от логарифма числа терминалов имеет линейный характер с наклоном кривой, который свидетельствует о квадратичной зависимости вычислительной сложности унифицированного алгоритма от размерности задачи N. В результате исследований выявлено, что время решения задачи почти не изменяется при переходе от одного правила v к другому и при изменении ограничений, в то же время оно сильно зависит от числа соседних терминалов, подключаемых к данному (т. е. числа новых линий, подключаемых к дереву). Зависимость времени работы унифицированного алгоритма синтеза КСД от числа соседних терминалов для сети с 40 терминалами приведена в таблице 2.2.

Таблица 2.2 – Зависимость времени работы терминала

Число соседних терминалов, К	Время работы алгоритма, мин	Относительная стоимость связи
1	0,434	7,77
2	0,491	5,26
3	0,522	4,54
4	0,557	4,50
5	0,589	4,48
8	0,691	4,45
10	0,767	4,45
15	0.985	4,45
20	1,240	4,45
25	1,503	4,45
30	1,767	4,45
39	2,245	4,45

2.2.6 Алгоритм D-структур

В модели многопунктовой ЛС, используемой как в унифицированном алгоритме Кершенбаума — Чжоу, так и в алгоритмах Исау — Вильямса, Мартина, Краскала и других, учитывают следующее допущение: при подключении очередного АП к многопунктовой сети стоимость канала передачи данных между узлами iи j

не зависит от объема информации hi, при этом вводится лишь одно ограничение: fij≤ d, где fij— суммарный поток (трафик) в любой ветви (i, j). Такое допущение справедливо в случае, когда по всей длине многопунктовой связи ее пропускная способность dостается постоянной. Вместе с тем использование модемов, работающих с различными скоростями передачи данных, позволяет организовать многопунктовые связи, в которых пропускная способность постепенно изменяется по мере приближения линии к центру обработки данных.

Таким образом, для многопунктовых связей с изменяемой (регулируемой) пропускной способностью традиционно используемое допущение

(hi) = const оказывается неверным, что исключает возможность использования унифицированного алгоритма Кершенбаума—Чжоу.

Для решения задачи синтеза структуры древовидной сети при переменной скорости передачи данных предложен алгоритм D-структур. Важной особенностью алгоритма D-структур является то, что на шаге 1 определяются оптимальные места размещения РЦ и радиальная структура СДО, а затем она преобразуется в древовидную структуру. Рассмотрим описание алгоритма. Введем следующие обозначения: Хi, Xj— подграфы графа X, Xi = {xi*, xi2, ... , Xin}; xi* — направляющая вершина подграфа Хiт. е. его концевая вершина на данной итерации, куда сходятся информационные потоки из всех хЄХi. Будем предполагать, что подключить Xiк Xjможно введением ветви (i*, j), исходящей только из направляющей вершины xi*, причем хjЄХj, и на Xjограничения не накладываются; Hi— суммарный объем ИВР подграфа Xi,

,hij— суммарный поток в ветви (i, j); С(Хi)— стоимость передачи информации во всех ветвях подграфа Xi.

1.Применяем алгоритм синтеза R-структур, находим размещение РЦ Y* = {yi*} и привязки абонентов к РЦ Хyi.Далее предполагаем, что РЦ размещен в пункте 1.

2.Определяем начальные веса всех вершин vi=

(hi,li1) и выполняем переход на подпрограмму «Оценка» (шаги 3—20).

Подпрограмма «Оценка». В подпрограмме «Оценка» определяем стоимость передачи объема информации Hiот подграфа Xiк подграфу Xjпри наилучшем варианте подключения. Пусть к началу итерации построено К. подграфов X1, Х2 , … Хк.

3.Выбираем изолированный подграф Хi.

4.Проверяем возможность введения ветви (i, j)

Нi + Нj≤dmax

Если условие выполняется, то переходим к шагу 5, в противном случае полагаем, что экономия Еij = ∞, переходим к шагу 4 и выбираем другую пару подграфов Хr, Хlдля анализа.

5.Отыскиваем вершину xj1, (xj1 Є Хj), ближайшую к xi*:

6. Проверяем, является ли xj1направляющей в подграфе Xj. Если — да, то запоминаем дугу (i*, j*), вычисляем

= Ci*j*(Hi,li*j*), Н’j=Нj + Нiи переходим к шагу 21, иначе — к шагу 7. Шаги 7—20 предназначены для нахождения наилучшего варианта подключения Хiк Xj.

7. Определяем направленный маршрут из xi* в xj* через вершину xj1. Пусть им окажется πi*j*={xi* – xj1 – xj2 – … xjk}, xjk=xj*.

8. Вычисляем Сi*j1 =

(Hi,li*j1), находим ni*j1 = ]Hi/d[, где ni*j1 — число каналов в ветви (i*, j1); знаком] [ обозначено округление с избытком. Пусть nikjk — число каналов в ветви (ik, jк).

9. Принимаем Сij= 0; Сij =

(li*j1).

10.Полагаем s = 0, где s — номер итерации.

11.s=s+1.

12.Проверяем условие, все ли ветви маршрута πi*j* просмотрены. Если s<K, то переходим к шагу 13, иначе — к 21.

13.Вычисляем

(Hi) — приращение стоимости для передачи дополнительного объема информации Hi:

единичных каналов, которые необходимо установить в ветви (js, js+1); dТФ — ПС телефонного канала связи.

14.Вычисляем величины

15.Определяем Cij = Cij +

(Hi).

16.Вычисляем

= (li*js+i, Hi).

17.Сравниваем Cijс

. Если Cij< то переходим к шагу 11, иначе переходим к шагу 18.

18.Полагаем Cij=

, вводим дугу (i*, js+1) вместо (i*, j).

19.Восстанавливаем прежние значения трафиков hij на всех предыдущих ветвях маршрута πi*j*:

20. Переходим к шагу 11.

21. Вычисляем экономию Еijпри подключении Xi к Xj по сравнению с подключением Xi к РЦ напрямую: Eij= Сij — vi.

22. Находим минимальное значение Eiljl = min Eij, где минимум берется по всем подграфам Xi, Xj.

23. Проверяем условие Eiljl < 0. Если оно выполняется, то переходим к шагу 24, иначе подключаем все оставшиеся изолированные подграфы напрямую к РЦ, и конец работы алгоритма.

24. Вводим дугу (il, jl) и подключаем Хil к Хjl. Образуем новый подграф Х’jl =Хil⋃ Хjl с направляющей вершиной x’jl*= xjl*, H’jl=Hil+Hjl.

25. Проводим коррекцию весов для всех вершин нового подграфа Х’jl:

где

— стоимость передачи информации из направляющей вершины в РЦ у1.

26. Если подграф Хjl напрямую связан с ВЦy1, то

, и тогда v’jl = 0, v’il = 0. В этом случае подграфХjl из дальнейшего рассмотрения исключается.

27.Проверяем условие, все ли подграфы подключены к РЦ. Если условие выполняется, то переходим к шагу 28, иначе — к шагу 3.

28.Вычисляем критерий — суммарные приведенные затраты Wпр— для построенного варианта D-структуры: Wпр =

Итак, как следует из описания алгоритма D-структур, объединение изолированных подграфов проводится до тех пор, пока это экономически целесообразно и выполняется ограничение, в противном случае соответствующий подграф подключается напрямую к узлу 1 (РЦ). Завершается работа алгоритма построением дерева с корнем в узле, соответствующем месту размещения РЦ. Следует отметить, что алгоритм D-структур, как и другие алгоритмы синтеза СДО в классе древовидных структур, требует вычислительных затрат порядка N logN, где N — число узлов.

Работа различных алгоритмов синтеза КСД иллюстрируется на примере решения задачи синтеза структуры сети, имеющей N = 20 узлов. Прямоугольные координаты узлов (xj, yj) и объемы информации hj, генерируемые каждым из узлов, приведены в таблице 2.3. Стоимость единицы длины канала составляет 30 руб./(кан.- км), а ограничение по пропускной способности dmax = 25 бод (бит/c).

Таблица 2.3 – Исходные данные для задачи

і	*Гкм	у,; км	бит/с	/	км	щкм	бит/о	V	*/-км	у,; км	бит/с
2	—35	80	5	9	—16	— 12	5	15	20	50	4
3	—39	60	7	10	0	—23	11	16	53	25	2
4	—20	50	3	11	—10	—16	7	17	70	34	10
5	—4	30	4	12	22	7	5	18	42	62	8
6	-20	25	4 і	13	40	5	8	19	35	78	7
7	-12,	12	9	14	30	20	4	20	17,5	70'	4
8	—40	18	6

Территориальное размещение узлов (АП) и решение задачи по алгоритму Прима (КСД без ограничений) показано на рисунке 2.2, а. РЦ расположен в пункте 1. Общая протяженность сети L= 366 км, а стоимость W = 10 980 руб. Оптимальная структура с учетом ограничений, полученная по методу ветвей и границ при L= 426 км, W = 12 780 руб., изображена на рисунке 2.2, б. Цифры, указанные в кружках на ребрах графа, соответствуют суммарному трафику (бит/с), передаваемому по данной связи. Как следует из рисунка 2.2, а, для сети Прима нарушаются ограничения по пропускной способности для связей 1—12 и 1—7.