Лабораторная работа N 2

5.2. Лабораторная работа N 2.

Синтез глобальной сети древовидной структуры..........20

Цель работы

Изучение алгоритмов синтеза информационной сети древовидной структуры.

Исходные данные и задание к работе

Заданы места расположения источников информации, интенсивности запросов к центру обработки информации. Необходимо оптимизировать структуру сети (выбрать местоположение центрального узла и пропускные способности линий связи). Поиск осуществляется в классе древовидных структур.

Критерий оптимизации и алгоритм синтеза задается преподавателем.

Исходные данные генерируются ПЛК NET_LAB индивидуально для каждого студента (либо бригады) и выводятся на экран.

Теоретическое введение к работе

Алгоритмы определения оптимальной структуры при наличии ограничений для сети большой размерности требуют значительных затрат времени вычисления. Поэтому на практике применяются эвристические алгоритмы, которые позволяют найти решения близкие к оптимальным при значительном уменьшении объема вычислений.

Рассмотрим следующие эвристические алгоритмы построения информационных сетей древовидной структуры: алгоритм Прима, алгоритм Краскала, алгоритм Ежи-Вильямса.

В основе алгоритма Ежи-Вильямса лежит процедура поиска наиболее удаленных узлов (в смысле стоимости) и соединения их с соседними узлами с целью обеспечения наибольшего выигрыша по стоимости. При использовании алгоритма Прима производятся обратные действия, вначале выбираются узлы ближайшие к центру, затем к этим узлам подключаются ближайшие к ним и т.д. По алгоритму Краскала последовательно выбираются линии с наименьшей стоимостью.

Алгоритм Прима

Шаг 0. Каждому узлу приписывается вес W4i0. При этом W410=0 (центральный узел), все остальные W4i0 равны бесконечности, i>1. Затраты Т4ij0 определяются следующим образом: S4ij0-W4i0, где S4ij0-стоимость подключения пункта A4i0 к пункту A4j0. Первоначально все Т4ij0 равны бесконечности, кроме T41j0.

Шаг 1. Найти минимальное значение T4ij0 для узлов, которые еще не включены в сеть.

Шаг 2. Проверка ограничений по пропускной способности каналов связи. Если ограничения выполняются перейти к шагу 3, иначе вернуться к шагу 1.

Шаг 3. Добавить линию (i,j), установить W4j0=0, изменить исходные условия и заново вычислить все Т4ij0. Вернуться к шагу 1.

Алгоритм Краскала

Шаг 1. Выбирается линия (i,j) с наименьшей стоимостью.

Шаг 2. Проверка ограничений по пропускной способности и отсутствию циклов.

Шаг 3. Добавить линию (i,j).

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

Алгоритм Ежи-Вильямса

Шаг 0. Вычисление всех параметров затрат 7t4ij0=s4ij0-s4i10 для всех i,j >1, где s4ij0 соответствующий элемент матрицы стоимости.

Шаг 1. Выбрать минимальное 7t4ij0.

Шаг 2. Проверка ограничений. Если ограничения выполняются, то перейти к шагу 3. Если нет, то положить 7t4ij0 равным бесконечности и вернуться к шагу 1.

Шаг 3. Добавить линию (i,j), изменить исходные условия (учесть потоки), вернуться к шагу 1.

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

Использование эвристических алгоритмов является компромиссом между стремлением улучшить качество сети и объемом вычислений.

Порядок выполнения работы

Путем выбора местоположения центра обработки сети, выбором каналов и их пропускных способностей студент должен найти оптимальную структуру древовидной информационной сети.

Местоположение центра обработки сети определяется на основе алгоритма "Центр масс" (см. лабораторную работу N 1) либо задается преподавателем.

На основе одного из эвристических алгоритмов (задается преподавателем) студент, используя опцию меню "create/delete channel" создает желаемую конфигурацию сети, что достигается путем выбора действий "создать/удалить канал" и инцидентных каналу вершин.

Расчет требуемых пропускных способностей каналов связи производится с учетом передаваемых по каналам потоков информации. Пропускная способность канала задается в окне "Channel params". Перебор каналов осуществляется опцией меню "Select channel". Выбранный канал помечен темным квадратом, параметры канала отображаются в окне Channel status.

Для сравнения на экран (окно "Network status") выводятся значения стоимости и задержки текущего варианта сети и подоптимального. В окне "Optimum" отображается степень близости текущего рабочего варианта сети к оптимальному. Если сеть незамкнута и имеет петли, то выдается сообщение об ошибке.

Контрольные вопросы к работе

1. Дать математическую постановку задачи синтеза информационной сети древовидной структуры.

2. Как рассчитывается задержка в древовидной сети?

3. Пояснить работу используемых алгоритмов.

4. Какие модели и ограничения были использованы при проектировании сети древовидной структуры?

5. Какие параметры влияют на стоимость сети?

Содержание отчета

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