Вопросы построенияархитектуры распределенных систем на основепередвижных пунктов управления
Территориально-распределенные системы, включающие не только стационарные, но и передвижные объекты, получают все большее распространение. На примере представления иерархической структуры системы в виде графовой модели и условий баланса выделяемых и потребляемых коммуникационных ресурсов предложено два алгоритма для проектирования архитектуры разрабатываемых систем. Предложенные методы и реализующие их алгоритмы эффективно работают с размерностями реальных задач и учитывают плотность расположения объектов разного типа на топологическом поле.
On Design of the Architectureof Space-Distributed Systems with Traveling Managed Objects.pdf Развитие беспроводных сетей и миниатюризация аппаратуры созда-ли новые технические и технологические возможности для построениянавигационно-телекоммуникационных комплексов (НТК) нового поколе-ния (НП). Составной частью НТК НП могут быть, например, аппаратно-программные средства мониторинга и управления мобильными ком-плексами (МК), передвижные пункты управления (ППУ) и беспилотныелетательные аппараты (БПЛА). Особым спросом НТК пользуются в орга-низациях и системах быстрого реагирования на природные, техногенныеи иные критические ситуации.Для повышения функциональных возможностей по управлению и ко-ординации действий нескольких ППУ и МК, находящихся в одном райо-не, а также применения БПЛА для мониторинга территории с воздухацелесообразно создание соответствующей архитектуры НТК НП.Обеспечение эффективности управления в рамках НТК НП можетбыть достигнуто путем использования комбинированного способа взаи-модействия: сочетания стратифицированного управления с горизонталь-ным взаимодействием между уровнями (стратами). На рис. 1 приведенпример обобщенной структуры НТК НП с комбинированным способомуправления. В соответствии с этим необходимо обеспечить: синхронизацию режимов приема-передачи и обработки навигацион-ной, фото- и видео- информации в режиме реального времени на уровненаземной станции управления БПЛА, управляющей станции мобильногокомплекса, диспетчерского центра; передачу управления БПЛА от одного диспетчерского центра дру-гому; интеграцию каналов связи различного типа.Совершенно очевидно, что система, приведенная на рис. 1, относит-ся к классу территориально-распределенных систем (ТРС), а в качествеее отличительных свойств можно выделить принципы иерархичности,централизма и многосвязности. Данные свойства во многом предопреде-ляют концептуальную основу построения архитектуры рассматриваемо-Рис. 1. Пример обобщенной структуры НТК НП с комбинированным способомуправленияго класса ТРС. Вместе с тем свойства иерархичности и многосвязностипредполагают наличие альтернативного выбора многих архитектурныхрешений при построении конкретной системы.При построении и оптимизации архитектуры ТРС важное место за-нимает задача разбиения множества объектов нижнего уровня иерархии(терминальных объектов - МК) на подмножества с целью подключенияобъектов этих подмножеств к объектам более высокого уровня (центрам- ППУ). Последовательно решая эту задачу относительно объектов наболее высоком уровне, мы получим новые центры и, в конечном итоге,- иерархическую структуру системы. Центр и подключенное к нему под-множество объектов более низкого уровня в последующем будем имено-вать локальным узлом иерархической структуры. Определение соста-ва локальных узлов в иерархической структуре в общем случае связано сзадачей декомпозиции множества объектов на подмножества. На первомэтапе множество объектов составляют терминальные объекты, а на после-дующих этапах декомпозиции в качестве множества объектов выступаютцентры.В терминах теории графов как объекты (вершины графа), так и от-ношения между ними (ребра графа) при описании структуры системы со-провождаются указанием ряда атрибутов. Такие атрибуты отражают кон-кретные свойства соответствующих объектов и связей между ними. Графыс приписанным набором атрибутов будем именовать графовой моделью.Графовые модели позволяют учесть параметры, характеризующиеобъекты системы и отношения между ними, и с нужной подробностьюописывают архитектуру системы. Если при этом атрибуты, как в нашемслучае, будут отражать параметры объектов и каналов связи между ними,то мы вправе проводить параллель между графовой моделью и архитек-турой системы.Описание и анализ объектов и связей между ними будем вести относи-тельно примера визуального представления графовой модели иерархиче-ской структуры системы, изображенной на рис. 2.Объекты структуры ТРС ассоциируются с действиями в системе и, поаналогии с сетями Петри, на рис. 2. изображаются планками. Для удоб-ства объекты (планки) в последующем будем именовать модулями, имеяв виду аппаратно-программные средства объекта, которые осуществляютсбор, обработку, анализ, формирование сообщений и другие операции.Предполагается также, что модули являются сложными и могут быть раз-вернуты в графовые модели, которые более детально и функционально-ориентированно описывают работу объекта.Кружками на рис. 2, также по аналогии с сетями Петри, данные, фор-мируемые терминальным объектом для передачи в центр, представленыРис. 2. Пример визуального представления графовой моделиодним кружком (позицией). В случае развернутого представления графо-вой модели все многообразие данных будет представлено в явном видеотдельными позициями. Модули центров, как показано на рис. 2, фор-мируют несколько данных для передачи вверх и вниз по иерархическойструктуре, в том числе и для модулей, расположенных на одном уровне.Передача данных между модулями одного уровня, как правило, можетосуществляться внутри одного локального узла иерархической структу-ры.Для примера приведем параметры, с которыми придется оперироватьпри построении архитектуры системы. Допустим, это параметры имею-щихся ресурсов: процессорное время τj, которое выделяется для выполнения модуляmj ; объём памяти ρj запоминающего устройства j-го объекта; канальный ресурс Kjr определяет предельный объем данных, кото-рый можно передать по r-му каналу из j-го объекта.Параметры ресурсов устанавливаются как предельные значения дляопределенного отрезка времени, который будем именовать интерваломанализа τ. Величина τ подбирается так, чтобы циклически повторяющи-еся процессы в системе укладывались в интервал анализа целое числораз.Выполнение каждого модуля инициируется (запускается) по опреде-ленным правилам, в соответствии с технологическим регламентом работысистемы. Будем различать запуски циклические, вероятностные, детерми-нированные и условные. Циклические запуски модулей mj осуществляют-ся через интервалы времени Δτj. Для вероятностных запусков указываютсявероятности наступления определенных событий, диктующих необходи-мость выполнения модуля. Детерминированные запуски также являютсявероятностными, но отличаются наличием дополнительных правил много-кратного запуска модуля в определенные моменты времени. Условные за-пуски могут быть отнесены к вероятностным, но они наступают не подвоздействием внешних по отношению к системе факторов, а под влияниемвнутренних, условия наступления которых контролирует сама система.Для разных модулей mj интервалы циклов запуска Δτj могут разли-чаться. Например, если цикл запуска одних модулей составляет 10 еди-ниц, а других - 20, то интервал анализа τ может быть принят равным 100единицам. Исходя из этого для каждого модуля mj, суммируя все видызапусков, можно подсчитать частоту ρj, с которой он будет выполняться водном интервале анализа. Так, для интервала анализа τ = 100, частота ρjсрабатывания модуля mj с Δτj = 10 будет складываться из десяти цикли-ческих и. например, в среднем двух запусков по другим основаниям, т.е.ρj = 10+2=12.Каждый запуск модуля mj будем сопоставлять с формированием со-стояния, данного по одной из выходных позиций. Поэтому число состоя-ний данного ρi, формируемого в позиции di за один интервал τ, не превы-сит значение ρj. Если модуль mj формирует состояния для Vj, то можнозаписать, что .Значения величин ρi и ρj дают возможность оценить объемы потре-бления ресурсов в системе. Для этого введём следующие параметры по-требления ресурсов:τji - процессорное время j-го объекта, затрачиваемое для формирова-ния одного состояния в позиции di;ρji - память, необходимая для хранения одного состояния позиции di вj-том объекте;Kjir - потребление канального ресурса Kjr при передаче по r-каналуодного состояния позиции di, сформированного модулем mj .Перечисленные параметры позволяют сопоставить наличие балансамежду имеющимися ресурсами и их потреблением. Выражения для про-верки баланса имеют следующий вид:(1)(2)(3)Здесь αj , βj , γ j - коэффициенты резервирования ресурсов по параме-трам τ j, Pj , Kjr ;ci - коэффициент селекции, определяющий снижение числа сформи-рованных в позиции di состояний при передаче их потребителю;R - число типов каналов, используемых в системе.Каждый j-тый объект, помимо канального ресурса Kjr по передаче дан-ных, должен обладать канальным ресурсом K΄jr по приему данных, посту-пающих от совокупности Vj΄ входных позиций i j d ∈V′ и потребляющихресурс K΄jr в объеме K΄ir . Условие проверки баланса запишется аналогич-но (3) в виде(4)В условии баланса (1) предполагается, что процессорное время в раз-мере τji затрачивается для формирования состояния в каждой выходнойпозиции i j d ∈V . Если для разных позиций di формируется одно состоя-ние, то в этом случае экономится ресурс τj, и при необходимости такаяситуация может быть учтена. При разработке конкретной ТРС возможныи другие особенности потребления ресурсов, которые могут учитыватьсяпри составлении уравнений баланса.Проверку условий (1) - (4) можно проводить для объектов существую-щей системы при ее модернизации или для анализа очередного вариантаиерархической структуры проектируемой ТРС. Анализ существующейсистемы, в том числе и при ее модернизации, позволяет оценить «узкиеместа» и найти решения по их преодолению. Но если будут разработа-ны методы принятия решений при проектировании ТРС, то, несомненно,они могут быть применены и для модернизации.Для реализации сопоставления выделяемого и потребляемого ресур-са важно найти эффективные методы, которые на стадии формированияварианта иерархической структуры учитывали бы условия баланса ре-сурсов. При разработке таких методов будем исходить из того, что ТРСстроится на базе априорно заданного числа терминальных объектов. Та-кие объекты (например, метеостанции) являются интеллектуальнымитерминалами и осуществляют сбор и обработку первичных данных дляпередачи в центр. Терминальные объекты также могут принимать дан-ные из центра в виде инструкций, сообщений, запросов и т.п.В общем случае будем считать, что заданное множество объектов Mне является однородным и разбивается на непересекающиеся подмно-жества Ms , s=1,2,…,S по типам. Основанием для деления терминальныхобъектов по типам могут быть различия в функциональных возможно-стях, различия в доступе к определенным видам каналов для передачи иприема данных и другие различия.Для рассматриваемой задачи важно различать объекты по ресурснымпараметрам. Например, функциональные признаки влияют на ресурсы τи τ΄, P и P΄, а возможности доступа к каналам - на ресурсы К и К΄. Поэто-му в последующем будем считать, что все различия объектов сведены копределенным значениям ресурсных параметров. При этом если объектыразличаются по какому-либо признаку, который не влияет на такие пара-метры, то это различие не учитывается.Сведения о потреблении ресурсов терминальными объектами, состав-ляющими множество М, удобно представить в виде таблицы. Для нагляд-ности таблица приведена в качестве примера описания ресурсных пара-метров для |M|=50 объектов, разбитых на 5 видов подмножеств Мs. Числообъектов в каждом подмножестве Мs обозначено величиной ms, котораяприведена в отдельной колонке в правой части таблицы. Здесь же в пра-вой колонке приведена величина , которая равна суммарнойчастоте выполнения модулей mj, входящих в подмножество объектов Мs,за один интервал анализа.Обозначения параметров в таблице записаны, исходя из предположе-ния, что каждый терминальный объект имеет одну выходную позицию сномером d1 и одну входную с номером d2 (см. рис. 2). При обозначениивеличины τji вместо j указано s-е подмножество, к которому принадлежитj-й объект. Передачу и прием данных объекты могут вести по четыремтипам каналов, R=4. Наличие в таблице нулевых значений параметровканальных ресурсов означает, что соответствующий тип канала не ис-пользуется объектами подмножества.Подводя итог описанию и анализу терминальных объектов, можно от-метить, что исходные сведения о выделяемых и потребляемых ими ре-сурсах определены, и для всех объектов множества М выполняются усло-вия (1) - (4). Согласно иерархической структуре, изображенной на рис. 2,терминальные объекты подключаются к нескольким центрам. Предпола-гается, что каждый центр способен подключать определенное число тер-минальных объектов, порождая при этом локальный узел иерархическойструктуры.Определение рациональной совокупности локальных узлов, охваты-ТаблицаПотребление ресурсов терминальными объектамиS τs1 τ΄s2 Ps1 P΄s2 К1,1 К1,2 К1,3 К1,4 К΄2,1 К΄2,2 К΄2,3 К΄2,4 ms ρs1 8 5 15 3 0 3 2 0 0 1 1 0 9 452 10 5 12 7 2 0 1 1 1 0 2 1 7 643 2 4 23 4 0 1 0 3 0 1 0 2 15 384 8 6 14 5 1 2 0 0 2 2 0 0 9 965 7 9 18 8 3 0 2 0 1 0 1 0 10 80вающих все терминальные объекты множества М, по существу являетсяосновной целью первой задачи, сформированной в начале главы. Реше-ние такой сложной задачи предполагается разбить на два этапа. На пер-вом этапе определяется минимальное число центров, необходимых дляподключения всех объектов множества М. При этом предполагается, чтокаждый центр имеет ограниченное число объектов. Второй этап связан сразбиением множества М на подмножества, каждое из которых подклю-чено к одному из центров. Решение задач второго этапа рассматриваетсяс учетом территориального расположения объектов множества М и будетизложено позже.Рассмотрим задачи первого этапа, связанные с определением числацентров. Поиск решения предлагается вести на основе сопоставления ре-сурсов терминальных объектов и ресурсов центров. Значения ресурсныхпараметров терминальных объектов известны. Если установить значенияресурсных параметров центров, то нетрудно определить ориентировоч-ное число необходимых центров. Поэтому основное внимание следуетсосредоточить на установлении значений ресурсных параметров цен-тров. Заметим, что по составу ресурсные параметры центров ничем неотличаются от терминальных объектов. На основе характеристик произ-водительности аппаратуры, принятой для комплектации центра, частотысрабатывания модуля при формировании состояний данных выходныхпозиций и обработки входных позиций, объёмов передаваемой и по-ступающей информации, загружающей канальные ресурсы, можно дляпринятого интервала анализа рассчитать значения параметров ресурсов,которыми располагает обобщенный центр. Эти параметры обозначим ве-личинами τ*, P*, Кr*, К΄r*.Общий объем ресурсов, потребляемых всеми центрами (одним вир-туальным центром), вычисляется аналогично тому, как это делалось длятерминальных объектов. Тогда число центров, получаемое для каждоговида ресурса, определяется отношением общего объема потребляемогоресурса и имеющегося в обобщенном центре:(5)(6)(7)(8)Здесь V,V΄ - множества входных и выходных позиций по отношениюк объектам множества М;G(τ), G(P), G(К), G(К΄) - число обобщенных центров, необходимоедля обслуживания терминальных объектов множества М ресурсом τ, P,К, К΄ соответственно;α, β, γ, γ΄ - коэффициенты резервирования ресурсов, которые в дан-ном случае должны учитывать возможные выходы и входы в центры,расположенные на этом же уровне иерархии, и в вышестоящие центры,относительно которых рассматриваемые обобщенные центры выступаютв роли терминальных объектов.Значения параметров τi, Pi, Кir, Кir΄ определяются с использованиемпараметров входных и выходных позиций терминальных объектов. Так,если значения τs определяют затраты процессорного времени для форми-рования одного состояния позиции d2 для всех объектов множества Мs , товыражение (5) запишется в видеДля τ1= τ5=0,1; τ2=0,4; τ3=0,3; τ4=0,5 при τ*=25, α=1,4 и ρs из табли-цы имеем 1,4(0,1*45+0,4*64+0,3*38+0,5*96+0,1*80)/25=5,46. ЗначениеG(τ)=5,46 означает, что 6 центров с ресурсом процессорного времени 25единиц в одном интервале анализа своевременно справятся с формирова-нием состояний выходных позиций d2 (входных для объектов множестваМ). Аналогично по выражениям (6) - (8) определяется число центров от-носительно других ресурсов. Сопоставляя значения величин G(τ), G(P),G(К), G(К΄), принимается решение о величине G, которая определяет чис-ло центров.Рассмотрим ситуацию, когда терминальные объекты настолько отли-чаются друг от друга, что могут быть подключены только к тому центру,который оснащен соответствующими возможностями. Например, еслинекоторый объект формирует и передает в центр видеоданные, то нетнеобходимости все центры оснащать эффективными средствами их об-работки. Получается, что центры обладают различными возможностямидля подключения объектов. Способность центра g-го вида подключатьопределенное количество терминальных объектов разного типа предста-вим вектором подключения Ag={ags}; g=1,2,…,G*; s=1,2,…,S. Элемент agsвектора Ag равен числу объектов s-го вида, которые могут быть подклю-чены к центру g-го вида.В этом случае для определения числа центров более перспективнымпредставляется другой подход. В его основе лежит предположение о на-личии заранее сформированного множества G* видов центров. Форми-рование множества G* может осуществляться на этапе разработки ТРСвиртуально, на основе анализа различия объектов в множестве М. Приэтом номенклатура виртуальных видов центров может существенно пре-вышать реальную потребность в центрах, которая ассоциируется с чис-лом G. Для генерации множества G* могут использоваться различныеэвристические правила, которые здесь не рассматриваются.Для ряда предметных областей, в которых проектируется ТРС, мно-жество G* формируется на промышленной основе, то есть возможныедля применения виды центров известны разработчику проекта заранее.В этой ситуации из множества G* следует выбрать минимальное числоцентров, способных подключить все объекты множества М.Введем переменную xg, g=1,2,…, G*, которая определяет число цен-тров g-го вида, выбранных для подключения объектов множества М. Тог-да задачу выбора минимального числа центров, необходимых для под-ключения объектов множества М, можно записать в виде(9)(10)xg - целое положительное для всех s=1,2,…,S (11)Задача (9)-(11) относится к классу задач целочисленного линейно-го программирования. В результате решения задачи получим векторX*={xgs*}, g=1,2,…,G*, компоненты которого xg* определяют минималь-ное число центров g-го вида, необходимых для подключения объектовмножества М.Критерий (9) записан при условии, что все центры равнозначны поцене, либо такие различия несущественны. Если это не так, то вводитсяцена Cg центра g-го вида, и критерий (9) в этом случае запишется в видеОграничение (10) допускает некоторую функциональную избыточ-ность центров, когда сумма s-тых компонентов ags векторов подключенияAg превышает число объектов ms в множестве Мs. Такая избыточностьможет рассматриваться в качестве резерва, либо по возможности исклю-чаться при комплектации центров.Полученная в результате решения задачи (9)-(11) совокупность цен-тровпри необходимости может рассматриваться в каче-стве терминальных объектов для получения центров на более вы-соком уровне иерархической структуры, как это показано на рис. 2.Аналогично в качестве терминальных объектов рассматриваются цен-тры, которые были получены ранее в количестве G штук на основе со-поставления ресурсов. Изложенные выше методы используются ипри определении числа центров на более высоком уровне иерархии.В предыдущем параграфе было определено число центров, способ-ных подключить терминальные объекты проектируемой ТРС. Предпо-лагается также, что каждый центр способен подключить определенноеколичество объектов. Если все объекты одного типа, каждый центрподключает примерно равное число объектов. В условиях, когда объ-екты различаются по типам, состав объектов, подключаемых к центру,определяется его вектором подключения. В общих случаях терминаль-ные объекты должны быть разбиты на подмножества, каждое из кото-рых подключается к центру и образует локальный узел иерархическойструктуры.Таким образом, задача построения локальных узлов сводится к раз-биению объектов на подмножества. Основным фактором, определяю-щим критерий разбиения, является размещение объектов на определен-ной территории. Территорию, на которой расположены терминальныеобъекты, будем именовать топологическим полем. Очевидно, что пред-почтительным является такое разбиение объектов на подмножества, прикотором центры и подключаемые к ним подмножества располагаютсяна топологическом поле в компактных областях.На содержательном уровне задача размещения центров на топологиче-ском поле и подключения к ним объектов формулируется просто. На топо-логическом поле расположено множество Q={qir}, i=1,2,…,n, r=1,2,…,R,состоящее из подмножеств Qr объектов r-го типа. Для объектов ов ∈Q ir qизвестны координаты (xi,yi) их расположения на топологическом поле.Расстояние dij между объектами qir и qjr вычисляется по выражениюРазмещаемая совокупность центров представлена множеством С={сs},s=1,2,…,S с векторами подключения As={asr}. Здесь S - общее число цен-тров, необходимое для подключения множества объектов Q. Требуетсядля каждого центра Cs найти такие координаты (xs,ys), чтобы сумма егорасстояний до подключаемых объектов была минимальной.В предлагаемой стратегии поиска решения будем исходить из того,что первичным является размещение центров Cs, т.е. определение для нихкоординат (xs,ys), а после этого решается задача подключения объектов кэтим центрам. Начнем рассмотрение с более простой задачи, когда всеобъекты в множестве Q одного типа, т.е. R=1. Центры Cs в этом случаемогут различаться только числом подключаемых объектов.На начальной стадии поиска варианта размещения центров прини-мается, что они располагаются в местах размещения объектов, т.е. ко-ординаты центров совмещаются с координатами объектов, выбранныхдля размещения центров. Объекты, в которых располагаются центры,будем именовать полюсами. Число полюсов совпадает с числом цен-тров.В общем случае любой объект может быть объявлен полюсом. Всвою очередь, каждый полюс рассматривается в качестве места для раз-мещения центра и подключения к нему объектов. Поэтому после под-ключения объектов к полюсам, каждый из них окажется в отдельномподмножестве. Если с этой позиции рассматривать любые два объекта,то чем дальше они удалены друг от друга, тем с большей вероятностьюони попадут в разные подмножества, т.е. будут подключены к разнымцентрам. Это же можно сказать и относительно полюсов: чем дальшеони расположены друг от друга, тем более обоснованным оказываетсяих присутствие в разных подмножествах.Это соображение хорошо поясняется на подмножествах, представ-ленных на рис. 3. Например, объекты q1 и q14 имеют больше основанийпопасть в разные подмножества, чем близко расположенные объектыq21, q22 или q8, q9. Аналогично, если в качестве полюсов выбраны объектыq1, q5, q18, q24, q22, то они «естественным путем» попадают в разные под-множества, выделенные на рис. 3 пунктирными линиями, а не толькопотому, что эти объекты являются полюсами. Например, относительнообъектов q1, q2, q6, q11, q17, назначенных полюсами произвольным обра-зом, говорить о том, что они «естественным путем» попадут в разныеподмножества с хорошими оценками компактности, не приходится.Исходя из этого, алго-ритм формирования полю-сов, реализующий данноеэвристическое правило,устроен так, что выбираетнеобходимую совокупностьполюсов, в которой они какможно дальше отстоят другот друга. Алгоритм реали-зован программой «Полюс»и получил обозначение П1.Формирование множества Рис. 3. Пример визуального разбиения объектовна подмножестваполюсов Qp={qip}, p=1,2,…, P с помощью алгоритма α1 осуществляет-ся последовательно и включает выполнение следующих операций:Первым полюсом qi1 принимается объект т ∈Q i q , который макси-мально удален от всех других объектов множества Q. Объект qi1 выбира-ется согласно выражениюq [ max] ( .) 1\ir i iq Q qij Q d q qj i− ⇒ = ∈ ∀ Σ∈. (12)Здесь dij - расстояние между объектами qi и qj. Объект qi1 заносится вмножество полюсов Qp.Для каждого объекта p q Q \Q i ∈определяются расстояния di,ip отобъекта qi до полюсов p ∈Q ip q . Среди этих расстояний выбираетсяминимальное d*i,ip и запоминается. Таким образом, каждому объектуp q Q \Q i ∈соответствует величина d*i,ip.Cреди множества величин {d*i,ip} выбирается максимальное значение,а соответствующий объект p q Q \Q i ∈принимается в качестве очеред-ного p-го полюса qip и включается в множество Qp.Операции 2 и 3 повторяются до тех пор, пока число полюсов в мно-жестве Qp не достигнет величины p=| Qp|, то есть станет равным числуразмещаемых центров.Заметим, что при выборе 2-го полюса в множестве Qp присутствуеттолько один элемент qi1. Поэтому в данном случае «выбор» минимально-го расстояния d*i,ip (см. п.2 алгоритма) для объекта p q Q \Q i ∈ сводитсяк одной величине di,i1. На следующей иерархии алгоритма, при определе-нии 3-го полюса, выбор будет производиться из двух величин di,i1 и di,ip2 ,и так далее.Равномерность расположения полюсов по площади поля являетсяосновным свойством алгоритма П1. Это свойство можно отнести к досто-инству по отношению к полям с регулярной плотностью расположенияобъектов и к недостатку по отношению к нерегулярному расположениюобъектов. Алгоритм П1 оказался «нечувствительным» к неравномернойплотности расположения объектов на поле. Поэтому при существеннонеравномерной плотности расположения объектов как альтернатива ал-горитму П1 разработан алгоритм П2.Отличие алгоритма П2 от П1 заключается в том, что после выбора повыражению (12) первого полюса выполняется подключение к нему бли-жайших объектов согласно числу объектов, подключаемых к соответству-ющему центру С1, и полученное подмножество объектов исключается издальнейшего рассмотрения. Для выбора второго полюса на оставшемсямножестве объектов повторно выполняется операция выбора первого по-люса по выражению (12), определяется подмножество ближайших объек-тов для центра С2 и исключается из рассмотрения. Выбор последующихполюсов и исключение подмножеств объектов производится аналогич-но.Для повышения эффективности работы алгоритма необходимо ре-шить задачу подключения объектов к полюсам (центрам) так, чтобы со-кратить общую протяженность линий связи на подключение.Считаем, что на топологическом поле с помощью алгоритма П1 илиП2 определено множество полюсов Qp={qip}, p=1,2,…,P. Число полюсовР равно числу центров S. Для каждого центра cs, s=1,2,…,S известно чис-ло ms объектов ∈Q i q , i=1,2,…n, которое он может подключить. В част-ности, число ms для всех центров может быть одинаковым. Определенытакже расстояния dsi между центрами, закрепленными за полюсами qip, иобъектами qi.Введем переменную xsi, xsi=1, если объект qi подключен к центру сs,xsi=0, в противном случае. Задача подключения объектов к центрам с уче-том принятых обозначений формулируется как задача математическогопрограммирования:(13)(14)(15)Критерий (13) минимизирует суммарные расстояния от центров доподключаемых к ним объектов. Уравнение (14) обеспечивает подключе-ние к каждому центру cs ровно as объектов. Уравнение (15) обеспечиваетподключение каждого объекта qi только к одному центру.Задача в постановке (13) - (15) относится к классу легко решаемых за-дач транспортного типа, например, с помощью венгерского алгоритма. Вэтой задаче число объектов as, подключаемых к центрам, ассоциируетсяс объемами производства, а объекты соответствуют единичным объемампотребления. Объемы перевозок xsi в нашей задаче могут составлять неболее одного объекта. Соответственно, переменные xsi являются булев-скими.В тех случаях, когда число объектов на топологическом поле изме-ряется сотнями или даже тысячами, возникает потребность уменьше-ния размерности задачи без заметного ухудшения качества ее решения.С этой целью на топологическое поле наносится сетка с определеннымразмером шага так, чтобы число ячеек, содержащих объекты, было су-щественно меньше общего числа объектов. Таким образом, изменяя шагячейки, можно подобрать приемлемую размерность задачи. Каждая непу-стая ячейка объявляется новым объединенным объектом с координатамицентральной точки ячейки.Задача (13) - (15) решается относительно новых пунктов потребле-ния, представленных объединенными объектами (непустыми ячейками).Переменная xsi в этом случае определяет число объектов, взятых из i-йячейки для подключения к центру cs. В правой части уравнения (15) вме-сто единицы указывается число объектов в ячейке. Задача (13) - (15) втакой постановке полностью соответствует классической задаче матема-тического программирования транспортного типа.Разбиение объектов Q на подмножества Qs, полученное в результатерешения задачи (13) - (15), зависит от расположения полюсов. Как пра-вило, полюса в подмножествах Qs относительно критерия (13) располага-ются не лучшим образом. Это хорошо видно на рис. 2, где подмножествасформированы на основе полюсов (q1,1, q5,2, q18,3, q24,4, q22,5). Например, вподмножестве Q2 для размещения центра вместо объекта q5 лучше вы-брать объект q9. Если имеется возможность отказаться от размещенияцентра cs в одном из объектов подмножества Qs, то для этого подмноже-ства определяется центральная точка qs, как это показано на рис. 3. Ко-ординаты (xs,ys) точки qs вычисляются для каждого подмножества Qs какцентры при условии, что масса объектов ов ∈Qs i q принимается равнойединице, т.е.Σ∈=i s q Qs s i x 1/ m x ;; / 1 Σ∈=qi Qss s i y m y| | . s s m = Q (16)Заметим, что координаты (xs,ys), полученные по (16), не соответствуютстрого центральной точке qs* для объектов множества Qs. В отличие отточки qs* для точки qs величина Σ∈qi Qssi d не является минимальной. Здесьdsi - расстояние между объектом s ∈Q i q и точкой qs.Анализируя приведенные выше рассуждения относительно подмно-жеств Qs, как локальных узлов иерархической структуры, напрашиваетсяследующий вывод. Возможна и другая стратегия поиска решений даннойзадачи. В этой стратегии первичным является определение компактныхподмножеств Qs, а размещение в каждом из них центров легко осущест-вляется путем выбора одного из объектов подмножества или на основевыражения (16).Таким образом, согласно стратегии, рассматриваемая задача заключа-ется в следующем. Множество объектов Q необходимо разбить на сово-купность подмножеств {Qs}, s=1,2,…,S, таких, что:min;1 ,Σ Σ= ∈⇒qi q j QsijSsd (17)Uss s t Q = Q, Q ∩Q = 0, s,t = 1,2,..., S; (18)| | , , | | . |1Q m m n n QSss s s = = = Σ=(19)Критерий (17) суммирует расстояния dij между объектами во всех па-рах i j s (q , q ) ∈Q . Условия (18), (19) задают на множестве Q множествоW допустимых вариантов разбиения {Qs}. Совокупность множеств {Qs}w,удовлетворяющих условиям (18), (19), соответствует некоторому w-муварианту разбиения Q W s w { } ∈ .Разбиение {Qs*}w назовем компактным разбиением (К-разбиением)множества объектов Q, если данное разбиение удовлетворяет критерию(17). Cумму расстояний dij между объектами qi и qj в множестве Qs обо-значим величиной Ls, т.е. Σ∈=qi q j Qss ij L d,, а суммарную оценку компактностидля разбиения {Qs}w обозначим величиной .1 Σ==Ssw s L L тогда К-разбиению{Qs*}w будет соответствовать оценка компактности * min .w w W w L L∈=Применительно к задаче размещения центров, множество Qs рассма-тривается как совокупность объектов, подключаемых к центру cs, кото-рый размещен в некоторой точке qs с координатами (xs,ys). Будем считать,что координаты точки qs для множества Qs определяются по выражению(16). Для множества Qs введем другую оценку компактности Rs, котораяопределяется относительно точки qs как сумма расстояний dsi от объектовq ∈Q до точки qs, т.е. . Σ∈=qi Qss is R dАналогично оценкам Lw и Lw*, вводится оценка Σ==Ssw s R R1для разби-ения {Qs}w и оценка w w W w R R∈* = min для К-разбиения {Qs*}w. При использо-вании оценок Rw критерий решения задачи разбиения запишется в виде(20)Относительно использования оценок L и R следует заметить, что онине противоречат друг другу, т.е. минимизация оценки L соответствуетминимизации оценки R и наоборот. Также соответствие подтверждаетсяэкспериментально. В последующем будем рассматривать задачу разбие-ния в постановке (20), (18), (19) с вычислением координат центральныхточек qs по выражению (16).Рассмотрим одно из возможных разбиений {Qs}w. В множествах Qs,согласно (16), определены координаты точек qs для размещения цен-тров cs. Решим задачу (13) - (15) подключения объектов q Q i ∈ к центрамв точках qs так, чтобы на каждый центр cs было распределено ms объ-ектов, а сумма расстояний, связывающих центры с распределенными наних объектами, была бы минимальной. Задачу (13) - (15) в последующембудем именовать задачей TN, обозначая тем самым то обстоятельство,что она наполовину является транспортной (Т) и наполовину задачей на-значения (N).Решение задачи TN относительно разбиения {Qs}w приводит к одно-му из двух принципиально отличающихся результатов. В одном из нихраспределение объектов по центрам полностью соответствует разбиению{Qs}w. В этом случае на каждый центр cs распределились объекты множе-ства Qs. Такое решение соответствует ситуации, когда в разбиении {Qs}wобъекты множества Q относительно центров cs, s=1,2,…,S распреде-лились наилучшим образом, и при этом разбиение {Qs}w оказалось наи-лучшим относительно принятого расположения центров cs на топологи-ческом поле. Такое расположение центров будем именовать устойчивым.Устойчивое расположение совокупности центров {cs} всегда связываетсяс совокупностью значений {ms}.Другой результат решения задачи TN соответствует ситуации, когдапроисходит изменение некоторых или всех множеств Qs, т.е. имеет ме-сто перераспределение объектов между множествами. Новые множества,обозначим их Q΄s, очевидно, образуют разбиение с более высокой оценкойкомпактности, т.е. . w w R′ ≤ R ′ Действительно, оценка w R ′ ′ , полученная врезультате решения задачи TN, не может быть больше оценки w R , таккак это означало бы, что решение задачи TN не является оптимальным,т.е. хуже исходного разбиения {Qs}w. Следовательно, между оценкамикомпактности s w Q ′ { ′} и {Qs}w должно выполняться одно из соотношений,w w R′ < R ′ или . w w R′ = R ′ Соотношение . w w R′ = R ′ соответствует рас-смотренной выше ситуации, при которой перераспределение объектовмежду множествами не произошло либо имеют место два разных раз-биения, {Qs}w, и {Qs}w с равными оценками компактности. Соотношениеw w R′ < R ′ однозначно указывает на то, что объекты между множествамиQs перераспределились, и это привело к улучшению оценки компактно-сти нового разбиения.В множествах s Q′ нового разбиения остались точки qs, установлен-ные для множеств Qs исходного разбиения. Эти точки не соответствуютреальным центральным точкам множеств s Q′ . Поэтому появляется воз-можность вычислить новые точки расположения центров сs и улучшитьоценку компактности w R ′ ′ . Учитывая перенос точек на новые места, раз-биение s w Q ′ { ′} рассматривается как исходное, а задача TN решается от-носительно нового расположения центров сs в надежде получить разбие-ние s w Q ′′ { ′′} с оценкой компактности w w R′′ < R ′′ .Перенос центров сs и решение задачи TN следует повторять до тех пор,пока вновь полученное разбиение не совпадет с предыдущим, принятымв качестве исходного. Это будет означать, что получено устойчивое рас-положение, которое соответствует устойчивому разбиению, названномулокальным компактным разбиением (ЛК-разбиением). Найденное устой-чивое разбиение названо локальным, так как нет оснований полагать, чтосреди множества разбиений W оно имеет наилучшую оценку компактно-сти *w R , т.е. является К-разбиением.Алгоритм решения задачи (20), (18), (19) сводится к получению ЛК-разбиения, и для этой цели используется изложенный выше метод после-довательного улучшения разбиений. Для применения метода необходимосформировать исходное разбиение и определить центральные точки в егомножествах. Исходное разбиение получается путем решения задачи TNотносительно принятой совокупности полюсов. При этом в условии (14)значение ms уменьшается на 1, так как полюса входят в соответствующиемножества Qs. Алгоритм получения ЛК-разбиения включает следующиеоперации.Задается топологическое поле с множеством объектов Q. Координатыобъектов формируются автоматически по месту фиксации объектов наполе. Нумерация объектов производится в соответствии с последователь-ностью их на поле. Вычисляются расстояния Qij между объектами qi и qj, иформируется матрица расстояний Д.В множестве Q по алгоритму П1 и П2 выделяется совокупность по-люсов, и относительно них на основе матрицы Д формируется матрицарасстояний для решения задачи TN. Относительно полюсов решается за-дача TN и определяются множества Qs исходного разбиения.Для каждого множества Qs по выражению (12) определяются коор-динаты (xs,ys) центральных точек qs , и относительно них формируетсяновая матрица расстояний для решения задачи TN. Решается задача TN, иопределяется новое разбиение.Анализируется результат решения задачи TN в п.3. Если новое разбие-ние отличается от исходного, то новое разбиение принимается в качествеисходного и выполняется п.3. Если новое и исходное разбиения совпада-ют, то это о
Скачать электронную версию публикации
Загружен, раз: 334
Ключевые слова
распределённые системы управления, проектирование архитектуры системы, оптимизация передачи данных, distributed control systems, design of the system architecture, optimization of data transmissionАвторы
ФИО | Организация | Дополнительно | |
Сонькин Михаил Аркадьевич. | Национальный исследовательский Томский политехнический университет | Д.т.н., профессор | sonkin@tpu.ru |
Погребной Владимир Константинович. | Национальный исследовательский Томский политехнический университет | Д.т.н., профессор | sonkin@tpu.ru |
Ссылки

Вопросы построенияархитектуры распределенных систем на основепередвижных пунктов управления | ПУСС. 2012. № Том 4. Выпуск 7.
Скачать полнотекстовую версию
Полнотекстовая версия
Загружен, раз: 857