--PAGE_BREAK--Цель работы
Ознакомление с методами анализа и синтеза централизованных информационных сетей.
Исходные данные и задание к работе
Заданы места расположения источников информации, интенсивности запросов к центру обработки информации. Каждый узел-концентратор обслуживает сообщения терминалов, связанных с ним (в кружке каждого города выводится число терминалов). Будем полагать, что все терминалы генерируют одинаковый поток сообщений. Интенсивность и средняя длина сообщений одного терминала выводится в окне "Terminal params".
Необходимо оптимизировать структуру сети (выбрать местоположение центрального узла и пропускные способности линий связи). При выборе центрального узла сети использовать алгоритм «центр масс». Критерий оптимизации задается преподавателем.
Исходные данные генерируются ПЛК NET_LAB индивидуально для каждого студента (либо бригады) и выводятся на экран.
Теоретическое введение к работе
Рассмотрим алгоритм построения информационной сети звездообразной структуры — «центр масс». Исходными данными являются:
— множество мест расположения на заданной территории абонентских пунктов А{i}, где i=1,...,N;
— матрица пропускных способностей каналов связи С=7220с4ij7220;
— матрица стоимости линий связи S=7220s4ij7220.
При построении сети абонентские пункты подключаются к концентраторам, либо непосредственно к единственному центру сети. На первом этапе задача упрощается путем группирования абонентских пунктов и замены каждой группы терминалов эквивалентным узлом, расположенным в центре масс и имеющим вес, пропорциональный количеству абонентских пунктов в группе. При этом вес нового центра масс W=W4i0+W4j0, где W4i0 и W4j0 - соответственно веса узлов A4i0 и A4j0. В качестве веса любого узла может использоваться количество терминалов или суммарный поток сообщений, генерируемый этим узлом ко всем остальным узлам сети. Координаты нового центра масс вычисляются как
где X4i0, X4i0, X4j0, Y4j0 — декартовые или географические координаты узлов сети A4i0 и A4j0 соответственно.
Процесс группирования начинается с выбора ближайшей пары абонентских пунктов, которая затем заменяется одним пунктом с весом, пропорциональным двум абонентским пунктам, и расположенном в «центре масс» исходных двух узлов, далее выбирается ближайший к данному «центру масс» абонентский пункт и определяется новый «центр масс» с учетом весов абонентских пунктов и т.д. Размер группы ограничен пропускной способностью концентратора. Определенный таким образом «центр масс» является местом расположения концентратора, либо концентратор размещается в ближайшем к «центру масс» допустимом месте расположения.
На втором этапе работа осуществляется на множестве узлов, являющихся «центрами масс» групп, с весами, пропорциональными количеству объединенных в группы абонентских пунктов. Полученный таким образом «центр масс» является пунктом, в котором целесообразно разместить обрабатывающий центр информационной сети.
В лабораторной работе процесс построения сети начинается со второго этапа. При этом число абонентских пунктов, присоединенных к узлу-концентратору, указано в кружке каждого города. Интенсивность и средняя длина сообщений одного терминала выводится в окне "Terminal params".
В качестве модели канала информационной сети принята система массового обслуживания М/М/1. Среднее время задержки сообщения в канале с номером i вычисляется как: где: 1/7m4i0 — средняя длина сообщения (бит/сообщение), c4i0 — пропускная способность этого канала (бит/сек.),
7l4i0 — интенсивность потока сообщений (сообщений/сек.)
в этом канале.
Очевидно, что нагрузка на канал должна быть меньше его пропускной способности.
Среднее время задержки для всей сети вычисляется как:
где 7l4ij0 — интенсивность обмена между i-м и j-м узлом сети,
n — число узлов в сети.
Стоимость канала зависит от пропускной способности и длины, и может быть представлена как
S4j0 = V(c4j0) + S(c4j0)770l4j0 ,
где l4j0 — длина канала,
V(c4j0) — постоянная составляющая,
S(c4j0) — переменная составляющая.
Стоимость сети определяется как сумма всех S4j0.
продолжение
--PAGE_BREAK--Порядок выполнения работы
Путем выбора центра радиальной сети и подбором пропускных способностей каналов студент должен найти оптимальную конфигурацию.
На первом этапе на основе алгоритма «центр масс» с учетом числа терминалов в каждом пункте проектируемой сети (указано в кружке, соответствующем пункту (городу) сети) и расстояний между пунктами определяется местоположение центра сети. Центр сети выбирается в окне меню "Set net center". На экране центр сети помечен квадратом.
Расчет требуемых пропускных способностей каналов связи производится с учетом передаваемых по каналам потоков информации (исходя из интенсивности потока от одного терминала, числа терминалов, средней длины сообщений). Пропускная способность канала задается в окне меню "Channel params". Перебор каналов осуществляется опцией меню "Select channel". Выбранный канал помечен темным квадратом, параметры канала отображаются в окне Channel status.
Для сравнения на экран (окно Network status) выводятся значения стоимости и задержки текущего варианта сети и подоптимального машинного. В окне "Optimum" отображается степень близости текущего варианта сети машинному. Пример синтеза централизованной информационной сети приведен на рис. 4.
Контрольные вопросы к работе
1. Дать возможные математические постановки задачи синтеза централизованной информационной сети.
2. Какая модель канала связи использована при расчете задержки?
3. Пояснить работу алгоритма «центр масс».
4. Какие параметры влияют на стоимость линии связи?
5. Какие упрощения и ограничения использованы при синтезе структуры сети?
Содержание отчета
Математическая постановка задачи. Краткое описание методики и алгоритмов используемых при синтезе структуры информационной сети. Исходные данные. Полученная в результате синтеза структура сети. Таблицы пропускных способностей и загрузки каналов связи. Стоимость сети, задержки в сети.
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.
продолжение
--PAGE_BREAK--