Уравнения баланса. Теорема Джексона

Будем рассматривать сети типа [M|М|m]^N, т.е. сети, содер­жащие N узлов, причём в каждом 1-м узле имеется m обслуживающих приборов с показательным временем обслуживания с параметром m_i. В 1-й узел извне поступает простейший поток требований с интенсив­ностью γ_i≥0 (γ_i=0 означает отсутствие потока извне в i-й узел), причем вектор γ = ( γ_i, γ₂, … , γ_N) - не нулевой вектор.

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

рис 6.1. Структура узла сети 1

Для того чтобы вычислить полную интенсивность потока требо­ваний в заданный узел, нужно просуммировать простейшие потоки, поступающие извне, и потоки от других узлов сети. Обозначим через λ_i полную интенсивность потока, входящего в i-й узел. Эти интенсивности λ₁,λ₂,. . . , λ_N удовлетворяют системе линейных уравнений баланса (закон сохранения потока)

λ_i = γ_i + λ_j ρ_{i j} , i= 1, 2, . . . , N (8.3)

или в матричной форме

λ = γ + λР , (8.4)

где λ = ( λ₁,λ₂,. . . , λ_N) и γ = ( γ₁, γ₂,. . ., γ_N) – векторы – строки интенсивностей, Р – матрица маршрутизации.

Для того чтобы состояния узлов сети описывались эргодическими цепями Маркова, для всех i должны выполняться неравенства λ_i / (m_iμ_i)<1.

Джексон доказал, что каждый узел СеМО [[M|M|m]^N ведёт себя в сети так, как если бы он был независимой системой М|M|m с входящим пуассоновским простейшим потоком с параметром l_i. Обозначим Q_i (t), i=1,2,...,N , - число требований, находящихся в i-м узле в момент времени t;

Q(t)= (Q₁(t), Q₂(t), . . . , Q_N(t)); k = (k₁, k₂, . . . ,k_N),

k_i = 0,1, … - состояние процессора Q_i(t).

Пусть p(k₁,k₂,...,k_N) обозначает стационарное распределение процесса Q(t), р_i(к_i) стационарное распределение процесса Qi(t)

Стационарные вероятности состояний сети р(k)=р(k₁,k₂,...,k_N) являются решением системы уравнений глобального равновесия :

р(k₁,k₂,...,k_N) g_i + m_i min (k_i , m_i) =

m_i min (k_i+1,m_i) р(k₁,k₂,...,k_i+1,…,k_N) p_iN+1 +

+ g_i d_ki р(k₁,k₂, ... ,k_i-1,…,k_N) + (8.5)

m_i min (k_i+1,m_i) d_kj р(k₁,k₂,...,k_i+1, … ,k_j-1, … ,k_N) p_ji +

+ m_i min (k_i , m_i) р(k₁,k₂,...,k_N) p_ii , где d_k = min (k , 1).

Величина d_k, входящая в уравнения (8.5), учитывает тот факт, что при k_j =0 вероятность р(k₁,k₂,…,k_i+1,…,k_j-1,…,k_N) должна равняться нулю. Левая часть равенства (2.5) описывает вероятност­ный поток, исходящий из состояния k=(k₁,k₂,...,k_N), правая часть - вероятностный поток, входящий в это состояние из соседних сос­тояний (см. рис.2.4). Входящие потоки требований в узлы СеМО пуассоновские, время обслуживания на приборах в узлах СеМО имеет показательное распределение. Поэтому инфинитезимальные коэффици­енты (интенсивности переходов) из состояний k'= (k'₁,k'₂,…,k'_N), у которых | k'_i- k_i | > 1хотя бы для одного i, равны нулю и соответ­ствующие вероятностные потоки имеют нулевую интенсивность.

j=2

N p_kN+1 + p_N+1k

j=3 i=1

. . . . i¹1

. . . .

. . . .

N

j=3 i=1 N N p_k

. . . . i¹2 .

. . . . i=1 j=1 .

. . . . i¹j .

j=N

. . . .

. . . .

. . . .

j=1

N

j=2 i=1

. . . . i¹N

. . . .

. . . .

j=

N-1

j=1

N

j=2 i=1

. . . .

. . . .

. . . .

j=N

Рис. 6.2.

На рис.6.2

p_ij = m_i min (k_i +1, m_i) d_kj р(k₁, k₂,..., k_i+1,…, k_j -1, … , k_N) p_ij , i¹j

p_ii = m_i min (k_i, m_i) р(k₁, k₂,…, k_N) p_ii ;

p_kN+1= m_i min (k_i +1, m_i) р(k₁, k₂,..., k_i+1, … , k_N) p_iN+1;

p_k = р(k₁, k₂,…, k_N) .

Будем говорить, что узел j достижим из узла i: (i « j), если требования, выходящие из узла i, могут за конечное число шагов с положительной вероятностью поступить на обслуживание в узел j.

Узлы i и j называются сообщающимся: (i « j), если (i ® j) и (j ® i).

Будем говорить, что узел j сообщается с внешним источником, если:

1) этот узел достижим для требований, поступающих в сеть извне;

2) сток (выход из сети) достижим из этого узла.

Определим функцию b_i (k_i) следующим образом:

b_i (k_i) = min(l,m_i) = k_i!, k_i £ m_i

, k_i > m_i .

Теорема Джексона. Если в открытой сети [M|M|m]^N все узлы сообщающиеся, т.е (i ® j) для любых i,j = 1,2,...,N (матрица маршрутизации р - неприводимая матрица.) , так что нет узлов, не сообщающихся с внешним источником , то уравнения ба­ланса (8.3) имеют единственное решение. Если при этом для всех i=1,2,...,N выполнены условия эргодичности l_i / (m_im_i)<1, то ста­ционарное распределение марковского процесса Q(t) существует, не зависит от начального распределения и имеет вид

р(k₁,k₂,...,k_N) = р₁(k₁)p₂(k₂),...,p_N(k_N) = .

Здесь р_i(k_i) = р_i(0) r_i^ki/b( k_i) , k_i ³ 0, представляют собой стационарные вероятности состояний i – го узла как системы M|M|m_i ,

, i = 1,2,...,N

.

При доказательстве теоремы Джексона используется идея локального равновесия в сети. В условиях теоремы наряду с уравне­ниями глобального равновесия (8.5) имеет место система уравнений локального равновесия. Эта система представляет собой множество систем уравнений, на которые распадается система (8.5):

р(k₁,k₂,...,k_N) = = m_i min (k_i +1, m_i) р(k₁, k₂,..., k_i+1, … , k_N) p_iN+1;

р(k₁,k₂,...,k_N) m_i min (k_i , m_i) = р(k₁, k₂,..., k_i+1, … , k_N) +

+ m_j min (k_j+1 , m_j) р(k₁, k₂,..., k_j+1,…, k_i-1, … , k_N) p_ji +

+ m_i min (k_i , m_i) р(k₁,k₂,...,k_N) p_ii .

В системе локального равновесия приравнивается интенсивность потока из данного состояния СеМО за счет ухода требований из узла i к интенсивности потока в данное состояние сети из соседних состояний за счет поступления требований в узел i (см. рис. 2.5 и 2.6).

j=1

N

. . .

. . .

. . .

Рис.6.3. Равновесие потоков для внешнего источника

j=1

N

. . .

. . .

. . .

i-1

i+1

. . .

. . .

. . .

Рис. 6.3. Равновесие потоков для узла i

На рис 6.2:

p_iN+1 = m_i min (k_i+1, m_i) р(k₁, k₂,..., k_i+1,…, k_N) p_iN+1;

p_N+1k = р(k₁, k₂, ... , k_N) .

На рис 6.3:

p_ji = m_j min (k_j +1, m_j) d_ki р(k₁, k₂,..., k_j+1,…, k_j -1, … , k_N) p_ij ;

p_ii = m_i min (k_i, m_i) р(k₁, k₂,…, k_N) p_ii ;

p_N+1i = g_i d_ki р(k₁, k₂,…, k_j -1, … , k_N);

p_ki = р(k₁, k₂,…, k_N) m_i min (k_i, m_i) .

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

р(k)=1/G(N) r_i^ki / b( k_i) в уравнения локального равновесия, которые при этом

обращаются в тождества, если имеют место уравнения баланса (8.3).

Теорема Джексона позволяет в явном виде выписать формулы для определения стационарных вероятностей марковских СеМО.

Сеть [M|M|1]^N. Пусть l = ( λ₁, λ₂,. . . , λ_N) - решение системы уравнений баланса (2.3). Если для всех i=1,2,...,N загрузка узла r_i = l_i / m_i <1, то

р_i(k_i) = (1- r_i )r_i^ki

и по теореме Джексона

р(k₁,k₂,...,k_N) = (1- r_i )r_i^ki .

Сеть [М|М|1]^N. Пусть l = ( λ₁, λ₂,. . . , λ_N) - решение системы уравнений баланса (8.3). Положим m = (m₁, m₂, …, m_N), где m_i число приборов в i-м узле. Тогда, если для всех i = 1, 2,..., N выполняются неравенства r_i / m_i = l_i / (m_i m_i) <1, то существует стационарный режим работы СеМО, и по теореме Джексона

р(k₁,k₂,...,k_N) = p_1k1 p_2k2 … p_NkN ,

где pi_ki являются обычными решениями для систем М|М|m [4, гл.2]:

p_i0 r_i^k/k! , k £ m_i

p_ik =

p_{i 0} r_i^k/(m_i! m_i^k-mi ), k ³ m_i ;

p_i0 = [ r_i^k/k! + r_i^mi/(m!(1-r_i/m_i)