Анализ свойств раскрашенных сетей

Определение количественных характеристик сетей

Для определения количественных характеристик сетей можно использовать различные методы теории графов и классического сетевого анализа. Ранее для сетей Петри рассматривались два подхода: через построение дерева достижимости и матричные методы анализа (линейная алгебра).

Для временных сетей, когда с каждым переходом связано время , важной характеристикой является время перевода сети из состояния М₀в М. Для этого на дереве достижимости можно отыскать соответствующий путь с вектором запусков счёта срабатывания , переводящих сеть из состояния М₀в состояние М. Тогда время перевода сети из состояния М₀в состояние М определится суммой:

, где - компонента вектора S для перехода t_j (число срабатываний перехода t_j).

В случае параллелизма в срабатывании переходов оценка времени перехода от М₀к М усложняется.

Оценка времени на пути из М₀в М позволяет изучить свойства системы путём сравнения их с заданными, обеспечение которых необходимо, например, из условий режима реального времени. Общее решение задачи об эквивалентности сетей Петри и временных сетей неизвестно. Отношение эквивалентности выражает в некотором смысле тождество строения. Эквивалентные – это «одинаково устроенные» сети. Исключение из рассмотрения времени и переход к анализу невременных сетей имеют двоякие следствия.

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

Раскрашенная сеть характеризуется следующим множеством элементов:

CN = { N, C, F, C M₀ },

где: N = { T, P, I, O } – биграф;

C = { X, R }, X = { λ, с₁, с₂, …, с_L } = { с_r} – множество раскрашивающих цветов или других признаков, включающее элемент λ, обозначающий «отсутствие цвета»;

R - бинарное отношение на множестве цветов Х, (чаще всего это отношение эквивалентности или равенства цветов);

F: А à Х – отображение множества дуг биграфа N на множество цветов, дающее раскраску дуг: с_ij^S - цвет s-ой дуги a_ij^S биграфа, направленной из вершины i в вершину j;

С М₀– начальное цветное маркирование сети.

В сети также раскрашиваются метки. Если – множество цветных меток, то цветное маркирование сети характеризуется парой отображений:

CM: { P; Х },

первое из которых указывает на размещение меток по позициям, а второе - на цвет этих меток. Факт размещения метки m в позиции P_i обозначим ( mP_i ).

Условимся, что метка m, имеющая цвет c(m), может принять участие в возбуждении перехода t_j, если пара ( c(m),с_ij^S ) удовлетворяет заданному R-отношению на множестве цветов. Если R-отношение равенства, то метка (mP_i) может участвовать в возбуждении t_j при условии что c(m) = с_ij^S (т. е. когда цвет метки равен цвету дуги a_ij^S). Для возбуждения перехода t_j необходимо, чтобы по всем входящим дугам могли пройти метки соответствующего цвета из позиций P_i , являющиеся предшественниками перехода t_j .

Логическое уравнение, описывающее условие возбуждения перехода t_j, имеет следующий вид:

∀ P_i Pre(t_j) ∃ m P_i [ R(с(m), с_ij^S) = 1] u(t_j) = 1,

иначе u(t_j) = 0.

Итак, если переход t_j возбуждён (u(t_j) = 1), то происходит его срабатывание и возбуждавшие метки из позиций Pre(t_j) при этом изымаются, а позиции Post(t_j) пополняются метками, цвет которых принимается равным цвету дуг, проходящих из t_j в позиции Post(t_j).

Для отображения цветного маркирования условимся представлять его в следующем виде:

CM = | m₁ … m_i … m_n |*,

где: * - операция транспонирования;

m_i = | m_i¹ m_i² …… m_i^L |, причём m_i^r - число меток r-го цвета в позиции P_i.

Динамика меток в раскрашенной сети характеризуется матрицей инцидентности Д, элементы которой d_ij представим в виде векторов-строк длиною L:

d_ij = | d_ij¹ d_ij² … d_ij^L |, (5.16)

где L - число раскрашивающих цветов.

Значения d_ij^r задаются следующим образом. Если метка цвета r потребляется переходом t_j из позиции P_i при срабатывании t_j, то d_ij^r = -1; если метка цвета r поступает в P_i из t_j , то d_ij^r = 1, и, наконец, в отсутствии этих действий d_ij^r = 0.

Эти же условия можно сформировать по другому. Если позиция P_i имеет исходящие дуги цвета r в переход t_j, то d_ij^r = -1; если имеет входящие дуги цвета r, то d_ij^r = 1, и если не имеет инцидентных дуг цвета r, то d_ij^r = 0.

Динамику продвижения меток по раскрашенной сети можно описать уравнением состояния:

CM_k = CM_k_-1 + D*U_k , (5.17)

где CM_k - состояние, в которое переходит раскрашенная сеть из CM_k_-1 под действием управляющего вектора U_k = | u_jk |, компоненты которого

1, если в k-ый момент срабатывает переход t_j ;

u_jk=

0, иначе.

Р-инварианты.Введём в рассмотрение инварианты раскрашенной сети, подобно тому как это сделано в сети Петри. Р-инвариант найдём из решения линейной системы:

DV = 0 , (5.18)

где V = | V_i | - целочисленный вектор-столбец, компоненты которого имеют вид:

V_i* = | v_i¹ v_i² …. v_i^L | .

Учитывая уравнение (5.1), находим:

V*CM = V*CM₀. (5.19)

Итак, подобно уравнению (5.9) для сети Петри, уравнение (5.19) для раскрашенной сети описывает инвариантность в её маркированиях.

Фундаментальная система решений однородной системы линейных уравнений имеет n – rL решений, где n - число позиций сети; r - ранг матрицы Д; L - мощность множества цветов Х. Объединив их в матрицу СВ, получим уравнение, аналогичное уравнению (5.11):

CB CM = CB CM₀ = K₀ .

T-инварианты. Решение линейной системы:

D*W = 0 , (5.20)

даёт t-инварианты W, где W = | W_j | - целочисленный вектор-столбец, в котором

W_j = | W_j¹ W_j²… W_j^L |.

Условие существования тупиков в раскрашенной сети находится из анализа системы:

CB CM = CB CM₀ ;

CO*CM ≤ COE’ – E, (5.21)

подобно тому как это выполняется для сети Петри. Здесь CO* - матрица аналогичная O*, расширенная в пределах каждого элемента по принципу (5.16):

1, если существует дуга из t_j в P_i, раскрашенная цветом r;

CO_ij^r =

0, иначе,

CO_ij = | CO_ij¹, CO_ij², … , CO_ij^r ,…, CO_ij^L |,

Е’ – единичный клеточный вектор, компоненты которого e_j’ представлены наборами из L единиц.

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

Рассмотрим простой пример для уяснения методики расчёта динамических свойств раскрашенных сетей.

б)

Рис.5.23. Примеры раскрашенных сетей

В изображённой на рис. 5.23а сети, описывающей взаимодействие двух процессов, обозначенных метками (□,○), протокол взаимодействия предусматривает порождение нового процесса (●), а затем возврат к исходным.

Каждому цвету из множества Х = (□,○,●) сопоставим числа r = 1, 2, 3. Тогда элементы матрицы Д = || d_ij ||, где i = 1, 2, 3, 4, j = 1, 2, 3, 4, 5, равны:

d₁₁ = d₂₂ = | -1 0 0 |; d₂₃ = | 0 0 1 |;

d₁₂ = d₃₁ = | 1 0 0 |; d₃₃= | 0 0 -1|;

d₃₅ = d₄₄ = | 0 1 0 |; d₂₄ = d₄₅ = | 0 -1 0 |,

а другие d_ij = | 000 |.

Вектор начального маркирования СМ₀= | m₀_i | представлен компонентами:

m₀₁ = | 100 |; m₀₂ = m₀₃ = m₀₄ = | 000 |; m₀₅ = | 010 |.

Уравнение состояния (5.17) здесь имеет вид:

m₁		m₁		d₁₁	d₂₁	d₃₁	d₄₁		U₁
m₂		m₂		d₁₂	d₂₂	d₃₂	d₄₂		U₂
m₃	=	m₃	+	d₁₃	d₂₃	d₃₃	d₄₃	*	U₃
m₄		m₄		d₁₄	d₂₄	d₃₄	d₄₄		U₄
m₅	k	m₅	k-1	d₁₅	d₂₅	d₃₅	d₄₅			k

Рекуррентное решение данного уравнения позволяет моделировать динамику состояний сети.

Найдём Р-инвариант сети V* = | V₁V₂V₃V₄V₅ |, где V_i* = | v_i¹v_i² v_i³ |. Для этого нужно решить систему (5.18). Ранг матрицы Д равен 1, следовательно фундаментальная система имеет одно решение, так как n – rL = 1. Распишем систему уравнений (5.18) для данной сети:

v₁¹ = v₂¹; v₃³ = v₁¹+ v₅²;

v₃³ = v₂¹ + v₄²; v₄² = v₅².

В качестве инварианта можно взять клеточный вектор-столбец с компонентами V₁* = V₂* = |100|; V₃*= |003|; V₄* = V₅* = |020|, удовлетворяющий приведённой однородной системе линейных уравнений. Затем вычисляем произведение:

V*CM₀ = | V₁* V₂* V₃* V₄* V₅*|| m₁* m₂* m₃* m₄* m₅*|₀ = 3,

и условие инвариантности:

VCM = | V_i* || m_i* |* = ∑ V_i* m_i* = m₁¹+ m₂¹ +3m₃³ + 2m₄² + 2m₅² = 3.

i=1

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

m₁¹+ 2m₄² = 3; m₁¹+ 2m₅² = 3; m₂¹ + 2m₄² = 3;

m₂¹ +2m₅² = 3; 3m₃³ = 3.

Из условия инвариантности, содержащего в правой части константу 3, следует ограниченность сети.

Решив систему (5.20), можно установить, что данная сеть живая и устойчивая. Элементы матрицы СО равны:

CO₁₁ = CO₂₂ = | 100 | ; CO₄₂ = CO₅₄ = | 010 | ; CO₃₃ = | 001 |;

а другие CO_ij= | 000 |. Система (5.21) здесь имеет вид:

m₁¹+ m₂¹ +3m₃³ + 2m₄² + 2m₅² = 3;

m₁¹ ≤ 0; m₂¹ + m₄² ≤ 1; m₃³ ≤ 0; m₅² ≤ 0.

Данная система не совместна, а, следовательно, исследуемая раскрашенная сеть не имеет тупиков.

Изменим раскраску на дуге (t₃,p₅) и примем новое начальное маркирование как показано на рис. 5.23б.

На основе вычислений можно установить, что приведённая сеть – ограниченная, живая, однако тупиковая, поскольку система

m₁¹+ m₂¹ +3m₃³ + 2m₄² + 2m₅¹ + 2m₅² = 3;

m₁¹ ≤ 0; m₂¹ + m₄² ≤ 1; m₃³ ≤ 0; m₅² ≤ 0,

совместна. Тупиковое маркирование описывается вектором СМ = | (000) (100) (000) (100) (000) |.

«Обесцвечивание» сети, т. е. переход от раскрашенной сети к базовой сети Петри может привести к потере и искажению информации о протекании процессов в сетевой модели. Так, если выполнить «обесцвечивание» приведённой сети, то расчётами можно установить, что её инвариант станет равным m₁ + m₂ + 3m₃ + 2m₄ + 2 m₅ = 3, т. е. произошло как бы «обесцвечивание» инварианта сети, приведённой на (рис. а), а не на (рис. б). Но самое важное состоит в том, что «обесцвеченная» сеть – беступиковая, хотя исходная раскрашенная сеть имеет тупик. Искажение такого важного свойства при упрощении модели указывает, что для обеспечения достоверности проектного анализа при исследовании раскрашенных сетей недопустим переход к «обесцвеченной» сети.