Научная работа: Построение маршрута при групповой рассылке сетевых пакетов данных
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 | <