close

Вход

Забыли?

вход по аккаунту

?

Случайные колебания длины приоритетной очереди при обслуживании конфликтных потоков по алгоритму с продлением в случайной среде.

код для вставкиСкачать
Математическое моделирование. Оптимальное управление
Вестник Нижегородского университета
Н.И. Лобачевского, 2009, № 1, с. 112–118
А.В.им.
Зорин
112
УДК 519.21
СЛУЧАЙНЫЕ КОЛЕБАНИЯ ДЛИНЫ ПРИОРИТЕТНОЙ ОЧЕРЕДИ
ПРИ ОБСЛУЖИВАНИИ КОНФЛИКТНЫХ ПОТОКОВ
ПО АЛГОРИТМУ С ПРОДЛЕНИЕМ В СЛУЧАЙНОЙ СРЕДЕ
 2009 г.
А.В. Зорин
Нижегородский госуниверситет им. Н.И. Лобачевского
zoav1@uic.nnov.ru
Поступила в редакцию 22.11.2008
Изучается система обслуживания формируемых в случайной среде конфликтных транспортных потоков автоматом-светофором с обратной связью. Требования одного из потоков имеют приоритет над
остальными. Алгоритм обслуживания циклический, допускает продление обслуживания неприоритетного потока при отсутствии требований по приоритетному потоку. Устанавливаются условия существования стационарных колебаний длины приоритетной очереди.
Ключевые слова: случайная среда, обслуживание конфликтных потоков, стационарный режим, итеративно-мажорантный метод.
Математическая модель
системы обслуживания
конфликтных транспортных
потоков по алгоритму с продлением
ного объема. Обслуживающее устройство имеет
2 состояния: Γ (1) и Γ ( 2 ) . В состоянии Γ ( j ) обслуживается максимально возможное число требований из очереди O j , а требования другой оче-
Пусть на перекрёсток поступают два конфликтных транспортных потока Π1 , Π 2 . Изменение во
времени вероятностной структуры входных потоков определяется внешней случайной средой. Моделью случайной среды будет служить неразложимая марковская цепь с состояниями e (1) , e ( 2 ) ,
реди не обслуживаются. Время пребывания светофора-автомата в состоянии Γ ( j ) неслучайно и
равно T j . Требования первого потока имеют при-
…, e (d ) , d < ∞ . Вероятность смены состояния
среды с e (l ) , l = 1 , 2 , …, d , на состояние e (k ) ,
k = 1 , 2 , …, d , равна al ,k . Смена состояния
среды может происходить только в моменты
времени, совпадающие с моментами смены состояния обслуживающего устройства (автоматасветофора). Если среда находится в состоянии
e (k ) , то требования по потоку Π j , j = 1 , 2 ,
поступают группами так, что поток групп есть
пуассоновский с параметром λ(kj ) , размеры
групп суть независимые случайные величины и
произвольная группа содержит c требований,
c = 1 , 2 , …, с вероятностью pc( j ,k ) . Такое предположение о структуре согласуется с наблюдениями: при хорошей погоде потоки машин на
магистрали, как правило, являются пуассоновскими, а при плохой погоде превращаются в
потоки пачек Бартлетта [1]. Требования потока
Π j поступают в накопитель O j неограничен-
оритет над требованиями второго потока в следующем смысле. Если по окончании времени,
отведённого для обслуживания требований из
очереди O2 , очередь O1 пуста, то снова включается режим обслуживания требований из очереди
O2 , в противном случае включается режим обслуживания требований из очереди O1 . После
окончания времени, отведённого для обслуживания очереди O1 , всегда начинается обслуживание
очереди O2 . Таким образом, обслуживающее
устройство выполняет не только традиционные
функции по обслуживанию неоднородных требований, но и функции по управлению входными
потоками для разрешения их конфликтности, по
формированию очередей в накопителях, а также
функцию изменения режимов своей работы. Процесс обслуживания удобно характеризовать не
длительностями обслуживания произвольного
требования, как принято в теории массового обслуживания, а потоками насыщения Π′1 , Π′2 –
выходными потоками системы обслуживания при
максимально возможной загруженности её накопителей и эксплуатации. Если обслуживающее
113
Случайные колебания длины приоритетной очереди при обслуживании конфликтных потоков
устройство находится в состоянии Γ ( j ) , то поток
насыщения Π ′j содержит l j требований.
Все рассматриваемые далее объекты задаются либо конструируются на некотором вероятностном пространстве (Ω, F, P) , где Ω —
множество описаний ω элементарных исходов,
F – σ -алгебра событий A ⊂ Ω , P — вероятность на F . Обозначим Γ = {Γ (1) , Γ ( 2 ) } ,
X = {0, 1, K} × {0, 1, K} . Введём отображения
v : Γ × X → {T1 , T2 } , и: Γ × X → Γ следующим
образом. Для Γ ( j ) ∈ Γ и x = ( x1 , x2 ) ∈ X пусть
v(Γ( j ) , x)
принимает
T1 ,
значение
если
Γ ( j ) = Γ ( 2 ) и x1 > 0 , в противном случае принимает значение T2 ; u ( Γ ( j ) , x ) принимает значение Γ (1) , если Γ ( j ) = Γ ( 2 ) и x1 > 0 , в противном случае принимает значение Γ . Пусть
τ0 = 0 , Γ0 ∈ Γ – состояние обслуживающего
(2)
устройства в момент τ0 , κ j ,0 – число требований
в
Oj
накопителе
в
момент
τ0 ,
κ 0 = ( κ1,0 , κ 2,0 ) , χ −1 – состояние случайной
среды в момент τ0 . Определим рекуррентные
i , i = 0 , 1 , … соотношения: τi +1 =
= τi + v ( Γi , κ i ) , Γi +1 = u( Γi , κ i ) — состояние
обслуживающего устройства на промежутке
( τi , τi +1 ] , κ j ,i +1 — число требований в очереди
по
в момент τi +1 , κ i +1 = ( κ1,i +1 , κ 2,i +1 ) . Промежуток
( τi −1 , τi ] будем называть i -м тактом. Чтобы
формализовать функциональные связи между
состояниями случайной среды, длинами очередей и состоянием обслуживающего устройства
в смежные моменты наблюдения, введём следующие величины и отображения. Пусть α0 ,
α1 , … – независимые случайные величины с
равномерным распределением на интервале
(0, 1) , отображение Ξ :
{e(1) , e( 2 ) , K, e ( d ) } ×
× (0, 1) → {e , e , K, e }
(1)
(2)
(d )
принимает в точке ( e( l ) , a ) значение e (1) при
0 < a < al ,1 , значение e (k ) при al ,1 + al ,2 + K +
+ al ,k −1 ≤ a < al ,1 + al , 2 + K + al ,k ,
k ≥ 2 . Тогда
последовательность χ −1 , χ 0 , … χ i , …, образо-
χi +1 =
= Ξ (χi , αi ) , будет марковской цепью, отображающей смену состояний случайной среды.
ванная рекуррентным соотношением
Именно χi задаёт состояние среды на промежутке ( τi , τi +1 ] . Обозначим ξ j ,i максимально
возможное число требований очереди O j , обслуженных на промежутке ( τi , τi +1 ] , ξ j,i число
фактически обслуженных требований очереди
O j на промежутке ( τi , τi +1 ] , η j,i число требований потока Π j , поступивших на промежутке
( τi , τi +1 ] . Легко видеть справедливость соотношений
ξ j ,i = min{κ j ,i + η j ,i , ξ j ,i } ,
= max{0, κ j ,i + η j ,i − ξ j ,i } .
κ j ,i +1 =
ξi =
Положим
= ( ξ1,i , ξ2,i ) , ξi = (ξ1,i , ξ2 ,i ) . Итак, получено рекуррентное соотношение
( Γi +1 , κ i +1 , χi +1 ) = (u( Γi , κ i ),
max{0, κ i + ηi − ξi }, Ξ(χi , αi )) ,
позволяющее изучить управляемую случайную
последовательность
{( Γi , κ i , χi ); i = 0, 1, K} .
Отметим, что аналогично дальнейшему
можно изучить более громоздкий процесс
{( Γi , κ i , χi , ξi ); i = 0, 1, K} .
Для задания нелокального описания [1]
входных потоков и потоков насыщения перечислим свойства условных распределений маркированных точечных процессов {( τi , ηi , νi );
i = 0, 1, K} с меткой νi = ( Γi , κ i ) требований на
промежутке ( τi , τi +1 ] и {( τi , ξi , ν′i ); i = 0, 1, K}
с меткой ν′i = Γi требований на промежутке
( τi , τi +1 ] . Положим
∞
f j( k ) ( z ) = ∑c =1 z c pc( j ,k )
определим величины ϕ(b; T , j , k ) ,
b = 0 , 1 , …, из разложения
exp{λ( kj )T ( f j( k ) ( z ) − 1)} =
и
T > 0,
∞
∑ z bϕ(b; T ,
j, k ) .
b=0
Так определённая величина ϕ(b; T , j, k ) есть
вероятность поступления b вызовов потока Π j
за время T при состоянии среды e (k ) . Например,
=
для
потока
Пуассона
(λ( kj )T )b (b! ) −1 exp{−λ( kj )T } ,
ϕ(b; T , j, k ) =
для потока Барт-
летта выражение приведено в [2]. Заметим, что
в перечисленных частных случаях ряд f j( k ) ( z )
сходится как минимум в некотором круге
| x |≤ 1 + ε , ε > 0 . В дальнейшем будем предполагать именно такой вид области сходимости.
Тогда для b = (b1 , b2 ) ∈ X , y = ( y1 , y2 ) ∈ {(0,0),
114
А.В. Зорин
~
( j~ )
( l1 , 0), (0, l 2 )} , r ∈ {1, 2} , 0 ≤ i ≤ i , Γ i ∈ Γ ,
x
( j~i )
∈X , e
( k ~i )
∈ {e (1) , e ( 2 ) , K, e( d ) } имеем
d
 w1 l 2
Qi +1 ( w1 , 0; 2, k ) = ∑ al ,k  ∑ ∑ Qi ( x1 , x2 ; 1, l ) ×
l =1
 x1 =0 x2 =0
× ϕ( w1 − x1 ; T2 , 1, l )
( j~i )
P({ηi = b, ξi = y} | {Γ~i = Γ ,
~
~
( k~ )
κ ~i = x ( i ) , χ ~i = e i , 0 ≤ i ≤ i}) =
= P({η1,i = b1} | {Γi = Γ ( ji ) , κ i = x (i ) , χi = e ( ki ) }) ×
+
l2
l 2 − x2

x2 = 0
b =0

Qi +1 ( w1 , w2 ; 2, k ) =
P({ηr ,i = br } | {Γi = Γ , κ i = x, χi = e }) =
= ϕ(br ; v ( Γ , x ), u( Γ , x ), k ) ,
( j)
P({ξr ,i = l r } | {Γi = Γ , κ i = x, χi = e }) = 1
( j)
(k )
при u ( Γ ( j ) , x ) = Γ ( r ) ,
P({ξr ,i = 0} | {Γi = Γ , κ i = x, χi = e }) = 1
( j)
(k )
при u ( Γ ( j ) , x ) ≠ Γ ( r ) .
Для управляемой случайной последовательности {( Γi , κ i , χi ); i = 0, 1, K} справедливы следующие утверждения.
Теорема 1. Последовательности {( Γi , κ1,i ,
χi ); i = 0, 1, K} , {( Γi , κ i , χi ); i =0, 1, K} при заданном распределении вектора ( Γ0 , κ 0 , χ0 ) являются марковскими цепями.
Обозначим
w2 + l 2
l =1
x2 = 0
∑
+
w1
∑ Qi ( x1 , x2 ; 1, l )ϕ( w1 − x1; T2 , 1, l ))
x1 =0
для w1 = 0 , 1 , … и w2 = 1 , 2 , ….
Введём производящие функции
Ψi (v1 , v2 , j, k ) =
Φ i (v1 , v2 , j, k ) =
d
Qi +1 (0, w2 ; 1, k ) = ∑ al ,k
l =1
∑ ∑ Qi ( x1 , x2 ; 2, l ) ×
× ϕ( w2 − x2 ; T1 , 2, l )
d
= ∑ al ,k ( v1
Qi +1 ( w1 , w2 ; 1, k ) = ∑ al ,k
l =1
∑ ∑ Qi ( x1 , x2 ; 2, l ) ×
x1 =1 x2 = 0
x1 =1x2 =0
−l1
l =1
x
v2 2 Qi ( x1 , x2 ; 2, k )
exp{λ(1l )T1 ( f1( l ) (v1 ) − 1) +
l 1 −1 ∞
+ exp{λ(2l )T1 ( f 2( l ) (v2 ) − 1)} ∑
∑ v2
x2
x1 =1x2 = 0
×
l1 − x1
∑
b =0
Qi ( x1 , x2 ; 2, l ) ×
b − l1 + x1
ϕ(b; T1 , 1, l )(1 − v1
d
Ψi +1 ( v1 , v2 , 2, k ) = ∑ al ,k ( v2
−l 2
)) ,
exp{λ(1l )T2 ( f1( l ) ( v1 ) − 1) +
l =1
+ λ(2l )T2 ( f 2( l ) ( v2 ) − 1)} ×
× ( Ψi ( v1 , v2 , 1, l ) + Ψi (0, v2 , 2, l )) +
l 2 l 2 − x2
+ exp{λ(1l )T2 ( f1( l ) ( v1 ) − 1)} ∑
∑ ϕ(b; T2 , 2, l ) ×
x2 = 0 b =0
× ϕ( w1 + l1 − x1 ; T1 , 1, l )ϕ( w2 − x2 ; T1 , 2, l )
для w1 = 1 , 2 , … и w2 = 0 , 1 , … и
x1
+ λ(2l )T1 ( f 2( l ) ( v2 ) − 1)}Φ i ( v1 , v2 , l ) +
∑ ϕ(b; T1 , 1, l ) ,
w1 + l1 w2
∞
∑ ∑ v1
Ψi +1 ( v1 , v2 , 1, k ) =
d
l1 − x1
b =0
x1 = 0 x2 = 0
∞
x
v2 2 Qi ( x1 , x2 ; j, k ) ,
Теорема 3. Имеют место рекуррентные по
i = 0 , 1 , … соотношения
w2
x1 =1x2 = 0
x1
Учитывая рекуррентные соотношения из
теоремы 2, получим следующее утверждение.
κ1,i = x1 , χi = e( k ) }) .
l1
∞
{( v1 , v2 ) : max{| v1 |, | v2 |} ≤ 1} .
Q1,i ( x1 ; j, k ) = P({Γi = Γ ( j ) ,
Теорема 2. Имеют место рекуррентные по
i = 0 , 1 , … соотношения:
∞
∑ ∑ v1
соответствующих распределений, сходящиеся,
по крайней мере, в области
Qi ( x1 , x2 ; j, k ) = P({Γi = Γ ( j ) ,
κ1,i = x1 , κ 2,i = x2 , χi = e ( k ) }) ,
ϕ( w2 + l 2 − x2 ; T2 , 2, l ) ×
× (Qi (0, x2 ; 2, l )ϕ( w1 ; T2 , 1, l ) +
(k )
( j)
d
= ∑ al ,k
× P({ξ2,i = y2 } | {Γi = Γ ( ji ) , κ i = x ( i ) , χi = e ( ki ) }) ,
( j)
∑ ϕ(b; T2 , 2, l ) +
b=0
∑ Qi (0, x2 ; 2, l )ϕ( w1; T2 , 1, l ) ∑ ϕ(b; T2 , 2, l )  ,
× P({η2,i = b2 } | {Γi = Γ ( ji ) , κ i = x ( i ) , χi = e ( ki ) }) ×
× P({ξ1,i = y1} | {Γi = Γ ( ji ) , κ i = x (i ) , χi = e ( ki ) }) ×
l 2 − x2
× (1 − v2
b − l 2 + x2
)(Qi (0, x2 ; 2, l ) +
∞
∑ Qi ( x1 , x2 ; 1, l )v1
x1 =0
x1
).
Случайные колебания длины приоритетной очереди при обслуживании конфликтных потоков
Можно получить рекуррентные соотношения
для вероятностей Q1,i ( x1 ; j, k ) и их производящих функций
∞
∑ v1
x1
x1 =0
∞
∑ v1
Q1,i ( x1 ; j , k ) ,
x1
x1 =1
Q1,i ( x1; 2, k )
из теорем 2, 3. Для этого достаточно заметить,
что в силу счётной аддитивности вероятности
Q1,i ( x1 ; j, k ) =
∞
∑ Qi ( x1 , x2 ;
j, k )
x2 =1
и, следовательно,
∞
∑ v1
x1
x1 =0
∞
∑ v1
x1 =1
115
от начального распределения имеет место соотношение
lim Q1,i +1 ( x1 ; j, k ) = 0 .
(5)
i →∞
Предположим, что изменение состояния
случайной среды описывается неразложимой
непериодической марковской цепью. Случай
периодической цепи изучается аналогично. Тогда существует единственное стационарное
распределение вероятностей этой цепи. Обозначим a k стационарную вероятность состоя∞
ния e (k ) . Обозначим µ (jk ) = ∑c =1 cpc( j ,k ) средний
Q1,i ( x1; j, k ) = Ψi ( v1 , 1, j, k ) ,
размер группы по потоку Π j при состоянии
x1
Q1,i ( x1 ; 2, k ) = Φ i ( v1 , 1, k ) .
среды e (k ) .
Условия существования
стационарного режима
случайных колебаний приоритетной очереди
Теорема 4. Для существования стационарного распределения марковской цепи (1) достаточно выполнения неравенства
(a1λ(11)µ1(1) + a 2 λ(12 )µ1( 2 ) + K +
В оставшейся части работы мы будем изучать свойства последовательности
{( Γi , κ1,i , χi ); i = 0, 1, K} ,
(1)
описывающей динамику изменения состояния
обслуживающего устройства, флуктуацию длины приоритетной очереди и изменение состояния внешней случайной среды. Суммируя соотношения теоремы 2 w2 = 0 , 1 , …, находим:
Q1,i +1 (0; 1, k ) =
d
= ∑ al ,k
l =1
l1
l 1 − x1
x1 =1
b=0
∑ Q1,i ( x1; 2, l ) ∑ ϕ(b; T1 , 1, l ) ,
(2)
Q1,i +1 ( w1 ; 1, k ) =
d
= ∑ a l ,k
l1 + w1
l =1
∑ Q1,i ( x1; 2, l )ϕ( w1 + l1 − x1; T1 , 1, l ) ,
+ a d λ(1d )µ1( d ) )(T1 + T2 ) − l1 < 0 .
Доказательство. Допустим, что выполнены
неравенства из формулировки теоремы, а стационарного распределения цепи (1) не существует. Тогда для всякого состояния должно
иметь место соотношение (5). Из соотношения (5) легко вывести, что последовательность
{E κ1,i ; i = 0, 1, K} неограниченно возрастает.
Покажем, что на самом деле эта последовательность ограничена.
Положим v2 = 1 в рекуррентных соотношениях теоремы 3. Получим:
Ψi +1 ( v1 , 1, 1, k ) =
(3)
d
= ∑ al ,k ( v1
x1 =1
l =1
d
Q1,i +1 ( w1 ; 2, k ) = ∑ al ,k ×
+
l =1

×  ∑ Q1,i ( x1 ; 1, l )ϕ( w1 − x1; T2 , 1, l ) +
 x1 =1
w1

В соотношениях (2)–(4) фактически вычислены одношаговые переходные вероятности
марковской цепи (1). Из их вида можно заключить, что все состояния этой цепи являются существенными и сообщающимися. Следовательно (см. [3]), либо существует единственное стационарное распределение цепи (1), либо для
всякого состояния ( Γ ( j ) , x1 , e ( k ) ) и независимо
exp{λ(1l )T1 ( f1( l ) ( v1 ) − 1)}Φ i ( v1 , 1, l ) +
l 1 −1
l1 − x1
x1 =1
b =0
∑ Q1,i ( x1; 2, l ) ∑
(4)

+ Q1,i (0; 2, l )ϕ( w1; T2 , 1, l )  .
−l1
b − l1 + x1
ϕ(b; T1 , 1, l )(1 − v1
)) , (6)
Ψi +1 ( v1 , 1, 2, k ) =
d
= ∑ al ,k exp{λ(1l )T2 ( f1( l ) (v1 ) − 1)} ×
l =1
× ( Ψi ( v1 , 1, 1, l ) + Ψi (0, 1, 2, l )) .
(7)
Выберем начальное распределение цепи (1)
так, чтобы производящие функции Ψ0 (v1 , 1, j , k ) ,
Φ 0 (v1 , 1, k ) , j = 1 , 2 , k = 1 , 2 , …, d , сходились в области | v1 |≤ 1 + ε1 , 0 < ε1 < ε . Суммируя соотношение (7) по k = 1 , 2 , …, d , и применяя затем соотношение (6), получим:
116
А.В. Зорин
d
d
∑ Ψi + 2 g ( v1 , 1, 2, k ) =
∑ Ψi +2 g ( v1 , 1, 2, k ) ≤
k =1
k =1
d
∑ exp{λ(1θ )T2 ( f1( θ ) ( v1 ) − 1)} ×
=
1
≤
1
θ1 =1
d
∑ ∑ aθ ,θ (v1
=
2
θ2 =1 θ1 =1
− l1
1
θ2 ) +
(θ
b=0
+
b − l1 + x1
хода за n шагов случайной среды из состояния
)) +
e (l ) в состояние e (k ) , al(,1k) = al ,k , al(,0k) = δl ,k ,
1
θ1 =1
Заметим, что при 1 < v1 < 1 + ε1 правая часть
не больше, чем
d
∑ ∑ aθ ,θ v1
2
θ2 =1 θ1 =1
−l1
1
exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1) +
+ λ(1θ2 )T1 ( f1( θ2 ) ( v1 ) − 1)}Ψi + 2 g −2 (v1 , 1,
δl ,k – символ Кронекера. Производная в точке
v1 = 1 от выражения, стоящего сомножителем
при Ψi ( v1 , 1, 2, θ2 g ) , равна
d
d
d d
− gl
L ∑ aθ2 g ,θ2 g −1 aθ2 g −1 ,θ2 g − 2 L aθ2 ,θ1 v1 1 ×
∑
∑
dv1 θ2 g −1 =1 θ2 g − 2 =1 θ1 =1
× exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1) +
2, θ2 ) + C1 ,
+ λ(1θ2 )T1 ( f1( θ2 ) ( v1 ) − 1)} ×
где
C1 =
d
× exp{λ(1θ3 )T2 ( f1( θ3 ) (v1 ) − 1) +
d
∑ ∑ a θ ,θ
θ2 =1 θ1 =1
l1 −1l 1 − x1
×∑
∑
x1 =1 b = 0
+
2
1
+ λ(1θ4 )T1 ( f1( θ4 ) ( v1 ) − 1)} × K ×
exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1)} ×
(θ
b − l 1 + x1
ϕ(b; T1 , 1, θ2 )(1 − v1
)+
(θ
d
d
≤
v1 =1
=
d
−l1
1
d
d
d
∑ ∑ ∑ ∑ aθ ,θ aθ ,θ aθ ,θ v1
θ4 =1 θ3 =1θ2 =1 θ1 =1
4
3
3
2
2
1
−2 l1
θ=1
g →∞
× exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1) + λ(1θ2 )T1 ( f1( θ2 ) (v1 ) − 1)} ×
+ λ(1θ4 )T1 ( f1( θ4 ) ( v1 ) − 1)}Ψi + 2 g − 4 ( v1 , 1, 2, θ4 ) + C2 ,
+ T1 ∑ λ(1θ)µ1( θ) (aθ( 22 gg,−θ2 ) + aθ( 22 gg,−θ4 ) + K + aθ( 02 g) ,θ ) − gl 1 .
lim (aθ( 22 gg,−θ1) + aθ( 22 gg,−θ3) + K + aθ(12)g ,θ ) g −1 = aθ ,
×
× exp{λ(1θ3 )T2 ( f1( θ3 ) (v1 ) − 1) +
d
Поскольку состояния среды образуют, по
предположению, единственный непериодический класс, имеют место предельные соотношения
exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1) +
+ λ(1θ2 )T1 ( f1( θ2 ) ( v1 ) − 1)}Ψi + 2 g − 2 ( v1 , 1, 2, θ2 ) ≤
d
(v1 ) − 1)}
θ=1
∑ ∑ aθ ,θ v1
2
(v1 ) − 1) +
= T2 ∑ λ(1θ )µ1( θ) (aθ( 22 gg,−θ1) + aθ( 22 gg,−θ3) + K + aθ(12)g ,θ ) +
1
Снова применяя соотношения (6), (7), найдём:
θ2 =1 θ1 =1
( θ2 g )
)
+ λ1 2 g T1 ( f1
∑ exp{λ(1θ )T2 ( f1( θ ) (v1 ) − 1)} > 0 .
1
( θ2 g −1 )
)
× exp{λ1 2 g −1 T2 ( f1
θ1 =1
d
2, θ2 g ) + C ,
где C > 0 . Обозначим al(,nk) вероятность пере-
d
d
( v1 ) − 1) +
(θ )
(θ )
+ λ1 2 g T1 ( f1 2 g (v1 ) − 1)}Ψi ( v1 , 1,
∑ exp{λ(1θ )T2 ( f1( θ ) (v1 ) − 1)}Ψi +2 g −1 (0, 1, 2, θ1 ) .
1
( θ 2 g −1 )
)
× exp{λ1 2 g −1 T2 ( f1
∑ Qi +2 g −2 ( x1 , x2 ; 2, θ2 ) ×
ϕ(b; T1 , 1, θ2 )(1 − v1
×
θ1 =1
+ λ(1θ4 )T1 ( f1( θ4 ) ( v1 ) − 1)} × K ×
x1 =1x2 =0
∑
− gl1
× exp{λ(1θ3 )T2 ( f1( θ3 ) (v1 ) − 1) +
l1 −1 ∞
l1 − x1
d
L ∑ aθ2 g ,θ2 g −1 aθ2 g −1 ,θ2 g − 2 Laθ2 ,θ1 v1
× exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1) + λ(1θ2 )T1 ( f1( θ2 ) (v1 ) − 1)} ×
+ exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1)} ×
×
∑ ∑
exp{λ(1θ1 )T2 ( f1( θ1 ) (v1 ) − 1) +
+ λ(1θ2 )T1 ( f1( θ2 ) ( v1 ) − 1)}Φ i + 2 g −2 (v1 , 1,
×∑
d
θ2 g =1 θ2 g −1 =1
× ( Ψi + 2 g −1 ( v1 , 1, 1, θ1 ) + Ψi + 2 g −1 (0, 1, 2, θ1 )) =
d
d
,
где C2 > 0 . Повторяя эту процедуру достаточное число раз, установим неравенство:
lim (aθ( 22 gg,−θ2 ) + aθ( 22 gg,−θ4 ) + K + aθ( 02 g) ,θ ) g −1 = a θ .
g →∞
Поэтому, выбирая g достаточно большим,
добьёмся того, чтобы знак производной совпал
со знаком выражения
d
(T1 + T2 ) ∑ λ(1θ )µ1( θ )a θ − l1 < 0 .
θ=1
Обозначим
117
Случайные колебания длины приоритетной очереди при обслуживании конфликтных потоков
R+ = max
d
{
1≤ θ2 g ≤ d
d
∑
∑
d
L ∑ aθ2 g ,θ2 g −1 ×
θ2 g −1 =1 θ2 g − 2 =1
θ1 =1
× aθ2 g −1 ,θ2 g − 2 Laθ2 ,θ1 v1
− gl 1
×
× exp{λ(1θ1 )T2 ( f1( θ1 ) ( v1 ) − 1) +
+ λ(1θ2 )T1 ( f1( θ2 ) ( v1 ) − 1)} ×
× exp{λ(1θ3 )T2 ( f1( θ3 ) (v1 ) − 1) +
+ λ(1θ4 )T1 ( f1( θ4 ) ( v1 ) − 1)} × K ×
Тогда
= 0, 1, K} ограничена.
Теорема 5 доказывается аналогично теореме 4.
Теорема 6. Для существования стационарного распределения марковской цепи (1) необходимо выполнение хотя бы одного из неравенств
λ(1l )µ1( l )T1 + al ,l λ(1l )µ1( l )T2 − l 1 < 0 ,
l = 1 , 2 , …, d .
(θ
)
(θ
)
× exp{λ1 2 g −1 T2 ( f1 2 g −1 (v1 ) − 1) +
(θ
( θ2 g )
)
+ λ1 2 g T1 ( f1
(v1 ) − 1)}
}.
Заметим, что R+ < 1 в некоторой правой окрестности точки v1 = 1 . Числовая последовательность
d
M 0 = ∑ Ψ0 (v1 , 1, 2, k ) ,
k =1
Доказательство. Предположим, что стационарное распределение марковской цепи (1) существует. Выбрав его в качестве начального
распределения, мы гарантируем существование
пределов
lim Q1,i +1 ( x1; j, k ) = Q1 ( x1 ; j, k ) ,
i →∞
d
M 1 = ∑ Ψ1 ( v1 , 1, 2, k ) , …,
k =1
d
M 2 g −1 = ∑ Ψ2 g −1 ( v1 , 1, 2, k ) ,
равных стационарным вероятностям соответствующих состояний. Функциональные соотношения для производящих функций
∞
∑ v1
Ψ (v1 , j, k ) =
k =1
M i + 2 g = R+ M i + C ,
{E κ 2,i ; i =
последовательность
x1 = 0
i = 0, 1, …
сходится, следовательно, она ограничена. В то
же время в той же окрестности точки v1 = 1
имеем
d
0 ≤ ∑ Ψi (v1 , 1, 2, k ) ≤ M i
k =1
Φ ( v1 , 1, k ) =
∞
∑ v1
x1 =1
 d
∑ ( Ψi ( v1 , 1, 1, k ) +

 dv1 k =1
d

= E κ1,i ; i = 0, 1, K

v1 =1
будет ограничена в силу интегральной формулы
Коши. Итак, соотношение (5) не может иметь
места, следовательно, существует единственное
стационарное распределение марковской цепи (1). Теорема доказана.
Приведём здесь без доказательства условие,
при выполнении которого ограниченным оказывается среднее число требований во второй
очереди.
+ Ψi ( v1 , 1, 2, k ))
Теорема 5. Пусть
λ(2l )µ (2l )T1 + λ(2k )µ (2k )T2 − l 2 < 0 для всех l ,
k = 1 , 2 , …, d .
Q1 ( x1; j, k ) ,
x1
Q1 ( x1 ; 2, k )
стационарных вероятностей можно получить из
равенств (6), (7). Имеем:
d
− l1
Ψ (v1 , 1, k ) = ∑ al ,k (v1
l =1
для i = 0 , 1 , …. Нетрудно видеть, что и последовательность
x1
exp{λ(1l )T1 ( f1( l ) ( v1 ) − 1)} ×
× Φ ( v1 , 1, l ) +
+
l 1 −1
l1 − x1
x1 =1
b =0
∑ Q1 ( x1; 2, l ) ∑
b − l 1 + x1
ϕ(b; T1 , 1, l )(1 − v1
)) , (8)
d
Ψ (v1 , 2, k ) = ∑ exp{λ(1l )T2 ( f1( l ) ( v1 ) − 1)} ×
l =1
(9)
× ( Ψ ( v1 , 1, l ) + Ψ (0, 2, l )) .
Подставим в равенства (8), (9) разложения
v1
− l1
exp{λ(1l )T1 ( f1( l ) (v1 ) − 1)} =
= 1 + (λ(1l )µ1( l )T1 − l 1 )( v1 − 1) + O (( v1 − 1) 2 ) ,
exp{λ(1l )T2 ( f1( l ) (v1 ) − 1)} =
= 1 + λ(1l )µ1( l )T2 (v1 − 1) + O (( v1 − 1) 2 ) ,
b − l 1 + x1
1 − v1
=
= ( l 1 − x1 − b)( v1 − 1) + O (( v1 − 1) 2 ) ,
справедливые в левой окрестности точки v1 = 1 ,
сложим полученные соотношения и приведем
подобные. Суммируя результат по l = 1 , 2 , …,
d и устремляя v1 к 1 слева, получим:
118
А.В. Зорин
ния второй очереди, то есть промежуток времени длиной (T1 + T2 ) , можем так сформулироl =1
вать условие стационарных колебаний длины
+ λ(1l )µ1( l )T2 Ψ (0, 2, l ) +
(10)
первой очереди: среднее число требований, поl 1 −1
l1 − x1
ступающих по первому потоку за «типичный
+ ∑ Q1 ( x1 ; 2, l ) ∑ ϕ(b; T1 , 1, l )( l 1 − x1 − b)) = 0 .
такт», меньше максимально возможного числа
x1 =1
b =0
обслуживаемых требований по этому потоку.
Положив v1 = 1 в равенстве (8), найдём, что
При этом среднее число поступивших требоваd
Ψ (1, 1, k ) = ∑ al ,k Φ (1, 1, l ) . Подстановка в ра- ний берётся и как среднее по возможным состояниям случайной среды, с учётом их стациоl =1
нарных вероятностей. Интересно, что на возвенство (10) даёт
можность стационарных колебаний длины приd
(l ) (l )
(l ) (l )
l
(
Φ
(
1
,
1
,
l
)(
λ
µ
T
+
a
λ
µ
T
−
)
+
оритетной очереди не влияют характеристики
∑
1 1 1
1
l ,l 1 1 2
l =1
другого потока. Таким образом, в системе воз+ λ(1l )µ1(l )T2 ∑ aθ,l Φ(1, 1, θ) + λ(1l )µ1( l )T2 Ψ(0, 2, l ) + можно существование стационарного режима
θ=1, 2,...,d
только по одному из потоков. Отметим, что неθ≠l
равенство
из теоремы 6 фактически является
l 1 −1
l1 − x1
необходимым
для существования стационарно+ ∑ Q1 ( x1 ; 2, l ) ∑ ϕ(b; T1 , 1, l )( l 1 − x1 − b)) = 0 .
x1 =1
b =0
го распределения цепи {( Γi , κ i , χi ); i = 0, 1, K} .
Предположение, что для всех l = 1 , 2 , …, d
Список литературы
имеет место неравенство
d
∑ (Φ(1, 1, l )(λ(1l )µ1( l )T1 − l1 ) + λ(1l )µ1( l )T2 Ψ(1, 1, l ) +
λ(1l )µ1( l )T1 + al ,l λ(1l )µ1( l )T2 − l 1 ≥ 0 ,
приводит к невозможному выводу Q1 (0; 2, l ) =
= 0. Теорема доказана.
Итак, считая «типичным тактом» работы
системы последовательное обслуживание первой очереди, а затем обслуживание без продле-
1. Федоткин М.А. Процессы обслуживания и
управляющие системы // Математические вопросы
кибернетики. Вып. 6. М.: Наука, 1996. С. 51–70.
2. Ляпунов А.А., Яблонский С.В. Теоретические
проблемы кибернетики // Проблемы кибернетики.
Вып. 9. М.: Физматгиз, 1963. С. 5–22.
3. Ширяев А.Н. Вероятность. В 2-х кн. Кн. 2. М.:
МЦНМО, 2004. 408 с.
STOCHASTIC OSCILLATIONS OF PRIORITY QUEUE LENGTH WHEN SERVICING CONFLICT
FLOWS BY A PROLONGATION ALGORITHM IN A RANDOM ENVIRONMENT
A.V. Zorine
A queueing system of conflict traffic flows formed in a random environment by automatic traffic lights with
feed-back is studied. Demands from one flow have priority over other demands. The servicing algorithm is cyclic, it
allows service prolongation of non-priority traffic in the absence of priority flow demands. Existence conditions of
priority queue length stationary oscillations are established.
1/--страниц
Пожаловаться на содержимое документа