Построение маршрута при групповой рассылке сетевых пакетов данных

из таких способов. Запишем веса узлов в виде

vt= a(bci0 + (l — b)ci2),

где ci0, ci2 — стоимости соединения терминала i с центральным узлом и с его ближайшим соседним терминалом соответственно; а и b — некоторые константы, причем а ≥ 0, 0 ≤ b ≤ 1. При а = 0 получаем алгоритм Краскала; при а = b = 1 — алгоритм Исау — Вильямса; при а = 1, b = 0 — алгоритм Фогеля. Наконец, придавая а и b некоторые промежуточные значения, можем получить одновременно свойства всех вышеперечисленных алгоритмов.

На практике обычно параметрам а и b придают некоторые начальные значения и затем, варьируя их по очереди и оценивая получаемые результаты, последовательно приближаются к наилучшему. Такой способ позволяет получить результаты на 1—5 % лучше, чем при использовании алгоритмов Исау— Вильямса и Фогеля. Указанный способ параметризации можно применять для одновременного решения задач группирования и размещения терминалов, если в выражении для vi под сi0 понимать стоимость соединения терминала i с ближайшим центральным узлом. При этом никакого предварительного разбиения терминалов на группы не производится, а оно выполняется автоматически в процессе работы алгоритма.

Рассмотрим эффективность реализации унифицированного алгоритма синтеза КСД. Сложность алгоритма — время вычислений и необходимый объем памяти — зависит от размерности графа N. В общем случае граф должен быть полным, что требует просмотра всех пар узлов. Однако при большом количестве терминалов можно без значительного снижения точности результатов решать задачу с помощью разреженного графа, в котором каждый терминал связан лишь с некоторым ограниченным числом соседних терминалов. Например, в сети с 40 узлами достаточно рассматривать соединения каждого терминала с пятью соседними. Дальнейшее увеличение числа терминалов К лишь незначительно улучшает результаты. Для сети терминалов, однородно распределенных вокруг центрального узла, можно игнорировать около 75 % возможных соединений. Для быстрой оценки приближенного значения К всю область, содержащую терминалы, разбивают на прямоугольники, в пределах каждого из которых находят К ближайших соседей заданного терминала. Благодаря такому правилу число операций для повторного вычисления Eij при включении новой ветви в дерево можно снизить с N (N — 1)/2 до N х К. Кроме того, учитывая, что Еij =vi-cij, где cij — константа, пересчет Еij можно свести к пересчету vi, т. е. вместо N х К повторных вычислений Eij достаточно пересчитать N раз значение vi.

В общем случае сложность алгоритма оценивается выражением: AN2 + BKN + CKN log2K, где А ,В и С — константы. При этом предполагается, что программа обеспечивает возможность реализации любого правила v. Однако, если правило v таково, что не требуется пересчет vi для каждого терминала, то членом AN2 можно пренебречь. Для многих практических целей сложность алгоритма имеет вид BKN + CKN log2К. Время работы ЭВМ и требуемый объем оперативной памяти при реализации алгоритма экспериментально оценены в сетях, содержащих 20, 40, 60, 80, 120, 200 узлов при учете только пяти соседних терминалов, использовании правила изменения v по алгоритму Исау — Вильямса и суммарном графике в ветви, ограниченном значением Н ≤ N/4.

Результаты экспериментов показали, что зависимость логарифма времени работы ЭВМ от логарифма числа терминалов имеет линейный характер с наклоном кривой, который свидетельствует о квадратичной зависимости вычислительной сложности унифицированного алгоритма от размерности задачи 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*:

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

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

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

Принимаем Сij = 0; Сij = (li*j1).

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

s=s+1.

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

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

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

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

Определяем Cij = Cij + (Hi).

Вычисляем = (li*js+i, Hi).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 2.2 – Структура СДО, синтезированная по алгоритму:

а – Прима; б – метод ветвей и границ

На рисунке 2.3, а построена структура СДО, синтезированная по алгоритму Исау — Вильямса, на рисунке 2.3, б — по алгоритму Шарма, на рисунке 2.3, в — по алгоритму Фогеля при L = =447 км, W = 13 400 руб. и на рисунке 2.3, г — по алгоритму Краскала. Для данной задачи из всех эвристических алгоритмов наилучшие результаты дает решение по алгоритмам Исау — Вильямса и Шарма (L = 440 км, W = 13 200 руб.), а наихудшим оказался алгоритм Краскала (L — 456 км, W = 13 680 руб.). Далее эта задача решена методом D-струк-тур для случая, когда имеются каналы двух типов d1 = 25 бит/с, c1 = 30 руб. /(кан.- км) и d2 = 40 бит/с, с2 = = 50 руб./(кан.- км). Она характеризуется показателями L = = 387 км, W = 12 330 руб. Синтезированная структура показана на рисунке 2.4.

Рисунок 2.3 – Структура СДО, синтезированная по алгоритму:

а – Исау-Вильямса; б – Шарма; в – Фогеля; г – Краскала.

Рисунок 2.4 – Структура СДО, синтезированная по алгоритму D-структур

2.3 Разработка структуры для поставленной задачи

В предыдущих разделах были описаны достоинства и недостатки различных способов разработки и оптимизации структур сетей. Приводились доводы за и против использования какой-либо структуры для поставленной задачи синтеза сети дистанционного обучения.

В результате предлагается остановиться на варианте D-структуры как наиболее универсальной. Она объединяет в себе преимущества радиальной и древовидной структур, и в то же время учитывает специфику сети передачи данных.

В рамках поставленной задачи не следует забывать о том, что составляющие элементы сети уже будут заданы конкретной ситуацией. От разработчиков не зависит расположение абонентов, существующие связи между ними, а зачастую и расположение промежуточных узлов.

Таким образом, сама по себе сеть будет задана внешними условиями, а задача синтеза сводится к оптимизации распределения абонентов между региональными центрами.

В конце работы первого этапа алгоритма построения маршрута синтезированная сеть будет приблизительно иметь вид, представленный на рисунке 2.5.

Р
исунок 2.5 – Схематичное представление синтезированной СДО

Обозначения:

– ВУЗ

– региональные центры

– абоненты

3 МЕТОДЫ ПОСТРОЕНИЯ ДЕРЕВЬЕВ
3.1 Задача Штейнера для построения сети

Задача Штейнера относится к классу так называемых NP-полных задач, поэтому алгоритмы, дающие точные решения, как правило, не могут быть использованы в САПР из-за неприемлемой временной сложности. Это обстоятельство послужило стимулом для разработки многочисленных эвристических алгоритмов. Наибольший практический интерес представляет алгоритм последовательного введения дополнительных вершин в дерево Прима-Краскала. Использование предложенного алгоритма позволяет строить деревья Штейнера, длина которых в среднем не превышает длину оптимального дерева Штейнера более чем на 0.5 процента. Временные характеристики модификаций алгоритма позволяют успешно использовать его на данном этапе построения маршрута.

Математическая модель задачи синтеза структуры сети по критерию стоимости приведена ниже.

Пусть имеется множество Х={xj} абонентов сети – источников информации с объемом трафика абонента h; {gj, wj} – географические координаты пункта, а также места размещения сервера {yi*} и привязки абонентов к серверу Xyi,i=1..m. Известны приведенные затраты на передачу информации от пункта i к пункту j: . Требуется синтезировать структуру сети в классе древовидных структур минимальной стоимости при ограничениях на суммарный поток fij в каждой ветви (i,j): , где dmax – пропускная способность линии связи; fij определяется как сумма информационных потоков от всех узлов, предшествующих узлу i на путях от концевых вершин к корню дерева и потока hi, определяемого абонентом xi.

Для ДШ постановка задачи выглядит следующим образом.

Дано:

– сеть, представленная в виде ненаправленного графа G=(V, E), где V – набор узлов, а Е – набор связей;

– матрица стоимости W, где Wij показывает стоимость использования связи (i,j) Е;

– узел-центр s V и набор узлов-участников D V;

– каждый узел vi имеет координаты xi и yi на экране, название и тип (центр, участник, вершина Штейнера, незадействованный узел).

Нужно найти такое дерево Т сети G с корнем в s, стягивающее всех членов набора D так, что полная стоимость ребер дерева Т будет минимальна. В стоимость обычно включается время передачи единицы данных по каналу, расстояние или денежный эквивалент данного соединения, пропускная способность канала или комбинация критериев.

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

Основная идея алгоритма заключается в следующем. Достаточно хорошим приближением дерева Штейнера является дерево Прима-Краскала, длина которого не может превышать длину соответствующего дерева Штейнера более чем в полтора раза. Также для случая ортогональной метрики доказано, что если через каждую точку из исходного множества точек провести горизонтальные и вертикальные линии, то решение задачи Штейнера можно получить рассматривая в качестве возможных дополнительных вершин только точки пересечения полученной сетки линий. Данный алгоритм последовательно вводит в текущее дерево Прима-Краскала каждую из дополнительных вершин решеточного графа, строит новое дерево Прима и запоминает полученный выигрыш в длине. После оценки всех дополнительных точек в текущее дерево включается точка с максимальным выигрышем. При этом, чтобы избежать в процессе преобразования появления избыточных точек, необходимо учитывать, что дополнительные точки в дереве Штейнера могут иметь только степень 3 и 4.

Предложен ряд процедур, позволяющих кардинальным образом сократить время работы за счет предварительной «отбраковки» тех вершин, чья вероятность оказаться штейнеровской точкой равна нулю или крайне мала. Данная процедура в несколько раз уменьшает временную сложность исходного алгоритма и, что не менее важно, в среднем качество получаемых решений не ухудшается.

В данной работе под средними показателями алгоритма (качественными, временными или какими либо другими) следует понимать средний результат для 10.000 задач. Тестовый набор для каждого значения размерности состоит из 10.000 различных задач, полученных случайным образом. Все результаты, приведенные в работе, получены на этих тестовых наборах.

Можно отметить, что для модифицированного варианта алгоритма процент улучшения дерева Прима-Краскала немного, всего лишь на несколько сотых долей, но все-таки больше, чем тот же самый показатель исходного алгоритма. Это обусловлено сокращением числа локальных неоптимальных минимумов эвристики за счет сокращения числа возможных дополнительных точек.

Однако можно сделать интересное наблюдение, если сравнивать не средние результаты достаточно большого тестового набора, а результаты, полученные двумя различными способами для каждой конкретной задачи. В строке G («good») приведен процент от общего числа тех задач, в которых вышеописанный модифицированный алгоритм дает выигрыш в суммарной длине всех ребер дерева по сравнению с исходным алгоритмом. В строке B («bad») приведен процент тех задач, в которых модифицированный алгоритм уступает исходному. И, наконец, в строке U («unchanged») показан процент всех оставшихся задач, для которых результаты работы обоих алгоритмов совпали.

Можно отметить две тенденции. Во-первых, с ростом числа точек уменьшается число задач, в которых оба алгоритма получают один и тот же результат. Во-вторых, число более удачных решений модифицированного алгоритма по отношению к исходному приблизительно равно числу менее удачных решений. Данное соотношение справедливо как для задач малой размерности, так и для больших задач. Объяснение этому достаточно простое. Как и большинство всех известных эвристических алгоритмов (и не только применительно к задаче Штейнера), данная эвристика не всегда сходится к оптимальному решению, а, как раз наоборот, чаще сходится к некоторому решению - локальному минимуму, отличному от оптимального решения. С ростом числа точек растет количество таких локальных неоптимальных минимумов, и, соответственно, уменьшается вероятность схождения алгоритма к решению с наилучшим результатом. Также на окончательный результат сильно влияет первая итерация алгоритма, очень часто именно она задает практически окончательную конфигурацию дерева, которая уже очень мало изменяется на последующих итерациях.

Данные рассуждения не являются каким-то таким уж невероятным открытием. Однако, тот факт, что средние результаты двух алгоритмов отличаются всего лишь во втором, третьем, а то и большем знаке, ловко маскирует другую тенденцию. А именно, практически абсолютная идентичность средних результатов достигается не за счет сходимости двух разных алгоритмов к одному и тому же решению, а за счет, так сказать, статистической схожести этих двух эвристик. Эта интересная тенденция, по-видимому, до сих пор выпадала из поля зрения исследователей, работающих с этим алгоритмом. Сравнивая различные методы улучшения качественных показателей, коллеги ориентировались только на средний результат и стремились получить максимальный выигрыш сразу, за один проход. Яркий пример этого подхода iterated 2-Steiner algorithm, где предлагается оценивать выигрыш от введения сразу двух возможных точек Штейнера в дерево Прима-Краскала. Временная сложность алгоритма в этом случае вырастает невероятно, что уже не позволяет использовать его на данном этапе.

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

3.2 Локальное перестроение дерева Штейнера

Для улучшения начальной конфигурации дерева предлагается для каждой глобальной точки исходной задачи провести процедуру локального перестроения дерева Штейнера. Эту процедуру следует проводить на множестве точек, включающем саму эту точку и инцидентные ей вершины (рисунок 3.1). Поскольку степень точки в дереве Штейнера не может быть выше 4-х, то максимальная размерность локальной задачи Штейнера, соответственно, не может быть больше 5-ти. Для задач же с размерностью до 5-ти точек включительно, как известно, существуют быстрые алгоритмы определения оптимальной конфигурации дерева Штейнера.

Рисунок 3.1 – Процесс локального перестроения дерева для глобальной вершины

Для данного метода перестроения дерева характерно некоторое число положительных исходов данной процедуры (стратегия A).

Аналогичную процедуру можно провести и для дополнительных точек, локально перестраивая дерево Штейнера на том же множестве точек инцидентных данной точке, но, в отличие от той же процедуры для глобальной точки, не включая в данное множество рассматриваемую точку (рисунок 3.2). Данный подход также позволяет получить некоторое небольшое число положительных исходов (стратегия B).

Рисунок 3.2 – Процесс локального перестроения дерева для дополнительной вершины

Факт наличия выигрыша от использования описываемых алгоритмов и сам факт незначительности этого выигрыша объясняются особенностями первого этапа модифицированного алгоритма. На этапе предварительной выборки дополнительных точек существует очень маленькая, но все-таки ненулевая вероятность пропустить точку, которая могла бы дать выигрыш при включении ее в дерево Штейнера.

К достоинствам вышеописанных процедур можно отнести линейную от размерности задачи временную сложность. Недостаток же очевиден – это малое число положительных исходов.

Использование совокупности только этих двух алгоритмов в качестве процедуры перестройки дерева Штейнера неэффективно. Большая часть времени будет затрачена на такие подготовительные процедуры, как выделение памяти и инициализация переменных, а затем, после отработки алгоритмов, на освобождение занятой памяти (стратегия 0). Однако использование этих процедур в качестве отдельного этапа (первого среди нескольких) – вполне разумно, тем более, что максимальный эффект от их использования достигается в совместном использовании с другими подходами, что и будет показано немного ниже.

Стоит добавить, что можно не ограничиваться рассмотрением только лишь инцидентных вершин каждой рассматриваемой точки. Если в построение локального дерева Штейнера включить инцидентные вершины второго уровня (рисунок 3.3) и использовать для определения конфигурации дерева модифицированный алгоритм, то количество положительных исходов вырастает во много раз за счет, конечно, увеличения временных показателей (стратегии D, E, F).

Рисунок 3.3 – Локальное перестроение дерева Штейнера для вершины 0 и инцидентных вершин первого и второго уровней

3.3 Процедура объединения свободных ребер

Введем понятие свободного ребра. Свободное ребро – это ребро, соединяющее две несовпадающие вершины, причем X и Y