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

ЛЕКЦИИ 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, кроме диагонального.