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

Рисунок 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») показан процент всех оставшихся задач, для которых результаты работы обоих алгоритмов совпали.

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