Лекции 5-6. Расчет иерархической древовидной конфигурации сети (1153084)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ЛЕКЦИИ 5-6РАСЧЕТ ИЕРАРХИЧЕСКОЙ ДРЕВОВИДНОЙ КОНФИГУРАЦИИ СЕТИ.4.1 Постановка задачиСтруктура иерархически организованной информационной системы,обеспечивающей сбор, обработку и вывод информации, может бытьпредставлена в виде дерева, корнем которого является, например,информационно-вычислительныйцентр,промежуточнымивершинамиявляются местные вычислительные центры, висячими вершинами - абонентыподразделения (рис.4.1 ).Г3L3Г4L2Г1L 1Г2а)Г1Г5б)Рис.4.1. Топологическая (а) ииерархической структуры.функциональная (б) организация связейПринимаем условие, что вновь создаваемые информационные центрытерриториально размещаются при одном из существующих абонентовподразделений, тогда рассчитываемая сеть представляет собой граф,обеспечивающий покрытие всех узлов-абонентов.Поставленная задача может быть сформулирована следующим образом:заданы множество исходных узлов ∈ A мощностью N (i=̅̅̅̅̅̅1, ) и взвешенныерасстояния между каждой парой узлов , .

Каждый узел характеризуется собственной оценкой , трактуемой как количествоинформации, передаваемое узлом за единицу времени. Требуется построитьсеть S минимальной длины, обеспечивающую многоуровневое покрытиеисходных узлов множества А и называемую иерархическим деревом.Покрытие уровня h есть совокупность непересекающихся групп{Гр } мощностью {Г }ℎ . Каждая из групп Гр имеет единый центр Цℎ ,ℎразмещающийся при одном из узлов группы и соединяющийся с узлами,принадлежащими группе, при этом заданное множество исходных узлов ицентров при них составляет нижний уровень покрытия h = 1.Математическаяформулировказадачиотысканиякратчайшейиерархической древовидной сети предусматривает (в качестве критерияэффективности) использовать -расстояния, взвешенные, например, одним изсоотношений (2.4) - (2.6).Для получения строгой записи целевой функции необходимо определитьискомые неизвестные.

Структура S будет считаться известной, если будетустановлено: 1) при каких исходных узлах множества А располагаются центрыгрупп каждого уровня; 2) с каким центром Цℎ h-го уровня связан каждый узел h-го уровня; 3) сколько уровней иерархии имеет структура S.В качестве неизвестных первой группы будем рассматривать булевыпеременные, которые определяют местоположение центров Ц :1, если Ц ∈ = {}0, если Ц ∉ (4.1)Набор матриц {‖ ‖}ℎ для всех уровней структуры полностью определяетместоположение всех центров Ц , располагаемых на уровнях h.В качестве неизвестных второй группы принимаем также булевыпеременные, которые определяют, с каким центром Цℎ группы Гℎ связанисходный узел :1, если ∈ Гℎ = {}0, если ∉ Гℎ(4.2)Набор матриц {‖ ‖}ℎ для всех уровней h структуры S полностьюопределяет состав элементов в каждой группе Гℎ .Неизвестное число уровней иерархии обозначим H, промежуточные уровниструктуры обозначим h, т.е.

ℎ = ̅̅̅̅̅1, . Кроме того, для записи математическоймодели введем следующие обозначения:̅̅̅̅̅М = ‖ ‖, , = 1,– исходная матрица взвешенных расстояний междукаждой парой узлов , ; { } – оценка каждого узла структуры, которыемогут трактоваться как объем информации, поступающий в узел за единицувремени;Гℎ , p = ̅̅̅̅̅̅1, Г – сформированная p-я группа, центры которых {Цℎ }составляют уровень h структуры S;Цℎ , p = ̅̅̅̅̅̅1, Г - центральный узел Гℎ уровня h ;Пℎ - оценочные коэффициенты Цℎ , которые могут трактоваться какспособность узла обрабатывать объем информации, равный Пℎвремени.в единицуВ сформулированной таким образом задаче наилучшей считается таструктура S, у которой величина суммарных взвешенных длин являетсянаименьшей. Таким образом, целевая функция модели может быть записана вследующем виде: = min,,ℎ ∑ℎ=1 ∑Гℎ∈ℎ ∑=1 ∑=1( )ℎ ( )ℎ ( )ℎ(4.3)В (4.3) часть функционала ∑ ∑( )ℎ ( )ℎ ( )ℎ позволяет вычислитьсуммарную длину взвешенных связей для одной группы Гℎ уровня h.Переменная Выделяет из М столбец { }, для которого Ц ∈ .Переменные выделяют из столбца { },соответствуют узлам, входящим в группу Гℎ .теэлементы,которыеИерархическая древовидная структура требует выполнения следующихфункциональных ограничений, определяющих конфигурацию.Каждый центр Ц может располагаться только при одном узле т.е.∑=1( )ℎ = 1(4.4)Каждый узел может входить только в одну группу уровня h , т.е.∑=1( )ℎ = 1(4.5)Центры групп уровня h рассматриваются как совокупность исходных узловдля уровня (h+1), т.

е.{Цр } = ℎ+1(4.6)ℎОграничения на пропускную способность узлов, выражающиенеобходимость согласования оценочных характеристик исходных узлов { } ицентров Ц записывают в следующем виде:0 ≤ Пℎ − ∑=1 ℎ ℎ < {ℎ }где ∞ >Пℎ >0; ∈ Гℎ ; ∉ Гℎ(4.7)Физический смысл ограничения (4.7) состоит в том, что производительность Пℎ центра Цℎ должна быть не меньше, чем суммарные объемы ℎузлов ,обслуживаемыхцентром.Однако,недогруженностьпроизводительности Пℎ центра Цℎ не должна превышать наименьшейпотребности узла ℎ , не обслуживаемого центром Цℎ .Соотношения (4.1) - (4.7) представляют собой математическую постановкузадачи определения иерархической древовидной структуры, решение которойпозволит определить структуру S, отвечающую заданным требованиям.Сформулированная задача принадлежит к классу нелинейных задач сбулевыми переменными.Реальные объекты, для которых требуется определять структуры, имеютразмерности узлов N = 100 - 400.

Мощность ℎ множества состояний уровня hможно определить как число сочетаний из N по В элементов в группе, при этомцентры групп могут размешаться при каждом из N узлов, т.е.ℎ ≈ !⁄[( − 1)! ( − )!]для N=100 и В=10 ℎ = 5,2 *10154.2 Алгоритм расчета иерархической древовидной ВСИз изложенного видно, что общий алгоритм решения рассматриваемойнелинейной целочисленной задачи должен исключать необходимость явногоперебора всех допустимых вариантов.Требуются методы, обеспечивающие частичный перебор ограниченногочисла допустимых вариантов и неявный перебор всех остальных вариантов, изкоторых формируются допустимые варианты,В целях сокращения множества вариантов объединения в группыиспользуется эвристический алгоритм, сущность которого заключается в том,что для исходного уровня h = 1 на каждом шаге из не сгруппированных ранееэлементов определяется группа Гℎ , имеющая минимальную суммарную длинувзвешенных расстоянии и отвечающая ограничениям на конфигурацию ипропускные способности узлов.

С одной стороны, алгоритм позволяет снизитьразмерность задачи, так как это дает возможность использовать понятиеупорядоченного перебора при формировании группы, но, с другой стороны,поиск глобального оптимума заменяется поиском суммы локальныхоптимумов, т.е. вместо сформулированной в (3.8) целевой функцииэвристический алгоритм осуществляет поиск решения по целевой функциивида: = ∑ℎ=1 ∑Гℎ∈ℎ min ∑=1 ∑=1 ∑=1( )ℎ ( )ℎ ( )ℎИзложенное обусловливает наличие в эвристическом алгоритме расчетаиерархической древовидной структуры двух этапов: целенаправленногогруппирования и улучшения краевых точек.На каждом шаге этапа целенаправленного группирования определяетсяоптимальная группа Гℎ . Этап улучшения краевых точек обеспечиваетперераспределение сгруппированных элементов таким образом, чтобы, ненарушая ограничений по конфигурации, получить более компактные группы.Этот этап вступает в действие после определения второй и всех последующихгрупп каждого уровня.Для получения групп уровня h+1 производится корректировка оценочныххарактеристик элементов на основании соотношения:( )ℎ+1 = ∑=1 ∑=1 а также следует корректировать матрицу расстояний таким образом, чтобы вматрицу Мℎ+1 вошли только те столбцы и строки Мℎ , которые соответствуютномерам узлов, при которых размещены центры групп.Этап целенаправленного группирования.

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

4.2): упорядочение (1) , определения группы (2) ,вычеркивание (3) .группированияцеленаправленногонетнетКоличествогрупп>1?ЭтапВычеркиваниеОпределениеблизлежащейгруппыточекОпределениегруппыОпределениенаименееудаленногоцентраулучшения краевыхУпорядочениедаВсе группыуровняОпределениезаменяющегоэлементадаВыполняется условие пропускнойспособности узла?нетЭтапНачалодаКорректировкаМ⁰ ,{Iᵢ}нетВ уровнеодна группа?даКонецРис. 4.2 Укрупненная блок-схема алгоритма определения иерархическойдревовидной структурыВ результате вычислительных операций блока упорядочениями исходной̅ = ‖матрицы M получаем три матрицы: упорядоченную М̅̅̅̅̅‖,номеров МК =‖‖ и суммарную МС = ‖‖.Для получения каждого j-го столбца упорядоченной матрицы необходиморасположить по возрастанию значения всех элементов j-го столбца исходнойматрицы M, кроме диагонального.

Характеристики

Тип файла PDF

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

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций