litceysel.ru
добавить свой файл
1 2 3

ЛЕКЦИЯ 4 (4 часа). ЧАСТНЫЕ МОДЕЛИ КОМПОНЕНТОВ ПРОЕКТИРУЕМЫХСИСТЕМ

4.1. Модель топологии размещения компонентов МВС

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

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

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

Задача заключается в поиске мест расположения станций и плана подключения к ним терминальных точек так, чтобы сумма длин расстояний между точками и станциями была минимальной. Данная задача сформулирована как не линейная задача математического программирования с булевыми переменными и была изложена в разделе 2.3. В такой постановке совмещены задачи определения числа станций, их расположения на объекте и распределения терминальных точек по станциям. Основным недостатком такой постановки является большая размерность задачи. В работе [33] решение данной задачи предлагается осуществлять в два этапа. На первом из них определяются места расположения станций, а на втором непосредственно осуществляется распределение терминальных точек по станциям. Такой подход представляется более предпочтительным, так как упрощает задачу и позволяет более гибко изменять полученные решения, при согласовании их с решениями других задач проектирования СРВ.

Определение мест расположения станций
(1−й вариант задачи)


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

Введем следующие обозначения:

- множество точек, заданных координатами на топологическом поле;

- множество станций;

- число точек, которое может быть подключено к одной станции.

Для определения мест расположения станций на топологическом поле выделяется подмножество точек , . Точки именуются полюсами. Для выделения полюсов предлагается использовать эвристическое правило, согласно которому полюса на топологическом поле располагаются относительно равномерно.

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


В общем случае выбор очередного полюса можно записать следующим образом. Обозначим − расстояние от точки до точки . Тогда условие выбора очередного полюса имеет вид

. (4.1)

Здесь - расстояние от точки до ближайшего полюса в множестве , выбранной для размещения очередного полюса и соответствующей максимальному, в сравнении с другими точками множества , удалению от полюсов . Терминальная точка , выбранная по условию (3.1) включается в множество . Выбор точек для размещения полюсов продолжается до получения множества , мощность которого .

Задача распределения терминальных точек по станциям

Для решения задачи распределения терминальных точек по станциям (полюсам) множества введем матрицу , где − расстояние между полюсом и точкой ; − число полюсов, ; − число распределяемых точек, . Введем также переменную , если точка подключается к полюсу , в противном случае . В принятых обозначениях задача распределения точек по полюсам (станциям) по критерию минимальной суммы длин связей при подключении точек к станциям запишется в виде:


, (4.2)

, (4.3)

. (4.4)

Здесь − число мест для подключения точек к станции в − полюсе. То в выражении (4.3) величина для всех . Если все станции могут подключать одинаковое число терминальных точек.

Задача определения числа станций
(2−й вариант задачи)


Введем ряд обозначений. Пусть на топологическом поле размещена совокупность терминальных точек , где - терминальные точки -го типа, .

Для каждой станции -го типа введем вектор подключения точек , , где - общее число типов точек на топологическом поле. Тогда способность станций подключать точки согласно векторам представим матрицей


.

здесь − число точек −го вида, которые могут быть подключены к станции -го типа.

Введем переменную , которая определяет число станций -го типа, необходимых для подключения точек топологического поля. Тогда задача определения минимального числа станций разных типов, необходимых для подключения всех терминальных точек с учетом введенных обозначений заключается в следующем:

(4.5)

(4.6)

- целое для всех (4.7)

Здесь − число точек − го типа на топологическом поле, .

Задача (4.5) – (4.7) является целочисленной задачей линейного программирования. По своей специфике данная задача относится к ставшей широко известной задачей покрытия [34]. Для нее предложен достаточно эффективный метод решения [35].

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


.

Задача распределения терминальных точек по заданному числу станций


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

а) формирование совокупности полюсов

На этом этапе определяются места, в которых могут быть размещены станции. Для решения данной задачи используется алгоритм определения полюсов, который работает в условиях, когда терминальные точки одного вида [28]. Полюса выделяются на местах расположения точек и являются потенциальными местами для размещения станций.

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


b) формирование вариантов подключения точек к станциям

Далее для каждой станции с и вектором подключения формируется множество вариантов подключения , Алгоритм формирования вариантов заключается в следующем.

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


c) выбор вариантов подключения

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

Принадлежность точек вариантам представим в виде матрицы , . Строки матрицы соответствуют элементам множества , а столбцы - вариантам множества . Элемент , если точка принадлежит варианту , в противном случае . Здесь величина определяет мощность множества точек , вошедших в варианты .


Введем переменную ,



Тогда задачу выбора вариантов по критерию минимальной суммы их оценок можно записать в виде:

(4.8)

(4.9)

(4.10)

Задача (4.8) – (4.10) является линейной задачей математического программирования с булевыми переменными.

d) определение «центров» размещения станций

Варианты , выбранные в результате решения задачи (4.8) – (4.10), включают совокупности точек различных типов согласно векторам подключения . Обозначим совокупность точек варианта множеством . В одной из точек множества , являющейся полюсом, расположена станция -го типа. В общем случае расположение станции в множестве относительно критерия минимальной суммы расстояний от станции до точек не является наилучшим. Для определения «центра» в множестве и размещения в нем станции используется следующая процедура.


В множестве каждая точка представлена координатами . Координаты точки с минимальным суммарным удалением от точек определяются выражениями:



Точка с координатами принимается в качестве «центра» множества и в нее размещается станция. Данная процедура выполняется для всех вариантов .

При решении задачи (4.8) – (4.10) качество варианта оценивалось величиной , которая не зависит от места размещения станции в данном варианте. В действительности, после размещения станции в «центре» множества , вариант следует оценивать суммой расстояний от «центра» до всех точек . Обозначим эту величину и сформулируем следующее предположение. Если для двух вариантов и , , выполняется условие , то условие также должно выполняться. Данная гипотеза проверялась экспериментально. С этой целью на топологическом поле случайным образом генерировались два множества точек и одинаковой мощности. В каждом из множеств определялся «центр» и сопоставлялись условия и . На множестве проведенных экспериментов гипотеза всегда подтверждалась.


e) улучшение распределения точек по станциям

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

Представим множество точек , , совокупностью множеств, содержащих точки -го типа, и пронумеруем точки в множествах ,

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


Информацию о расстоянии между точками и центрами представим матрицей , где - расстояние от центра с местом подключения -го типа до точки -го типа. Введем переменную ,



В принятых обозначениях задача распределения точек по станциям запишется в виде:

, (4.11)

, (4.12)

4.13)

Ограничение (4.12) разрешает подключение точек к станции согласно ее вектору подключения. Ограничение (4.13) обеспечивает подключение каждой точки к одной из станций.

Задача (4.11) – (4.13) занимает промежуточное положение между задачей о назначении и транспортной задачей. Так, если вектор подключения точек к станции представить булевским и, соответственно, пронумеровать места подключения каждой точки, то задачу (4.11) – (4.13) можно записать в виде задачи назначения точек на доступные по типу места подключения. И, напротив, если топологическое поле представить совокупностью клеток координатной сетки и каждую клетку с расположенными в ней точками разных типов рассматривать в качестве пункта потребления, а места подключения станции – пунктами производства, то задача преобразуется в классическую задачу транспортного типа. Известно, что и транспортная задача и задача о назначениях имеют эффективные алгоритмы решения [32].

Постановка задачи распределения терминальных точек разного типа с учетом сокращения размерности топологического поля


Рассмотрим постановку данной задачи при условии, что точки различаются по видам, а каждой станции -го вида соответствует вектор подключения точек , . Здесь - число точек -го вида, которые могут быть подключены к станции -го вида, - число видов точек. Множество точек в этом случае является объединением непересекающихся подмножеств точек -го вида , .

Для сокращения размерности рассматриваемой задачи множество разобьем на подмножества, компактно расположенные на топологическом поле, , . Компактность подмножества можно оценить отношением суммарной длины связей (расстояний) между точками множества к мощности данного множества , .

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


Задача распределения терминальных точек по полюсам в данном случае имеет следующий вид:

(4.14)

(4.15)

(4.16)

Здесь − расстояние от центра ячейки сети, содержащей −ю станцию с возможностью подключения точек, до ячейки с компактным множеством ;

− число точек множества подключенных к −ой станции;

− число точек в множестве .

Задача (4.14) – (4.16) относится к классу задач транспортного типа, для которой выполняется условие .

Заметим также, что в выражении (4.14) величина , если компактное множество связывается со станцией, для которой . Для решения задачи (4.14) – (4.16) также как и для задачи (4.2) – (4.4), может быть использован один из методов решения задач транспортного типа, например, метод потенциалов.

Пример топологического поля


Пример решения задачи определения полюсов и распределения по ним точек приведен на рис. 4.1





Рис. 4.1. Пример топологического поля


Расположение полюсов на рисунке соответствует варианту, полученному после выполнения первого этапа алгоритма. Здесь предполагается также, что точки, на которых расположились полюса, подключаются к данным полюсам. После решения задачи распределения точек по полюсам места размещения станций уточняются. С этой целью среди точек, подключенных к конкретной станции, определяется точка с минимальным суммарным расстоянием от нее до всех остальных точек. В выбранной таким образом точке размещается соответствующая станция.

Предложенный метод решения задач определения мест размещения станций и распределения терминальных точек по станциям может использоваться как базовый при разработке методов решения данных задач с другими исходными условиями. Заметим также, что предложенный алгоритм определения мест размещения полюсов согласно выражению (4.1) разработан для условия . Для условия выбор мест расположения станций осуществляется на основе решения задачи (4.5) – (4.7), в которой определяется число станций, и далее решения задачи (4.8) – (4.10) и задачи (4.11) – (4.13) по выбору вариантов подключения точек, определения мест расположения станций и распределения точек по станциям.

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


следующая страница >>