Асимптотический анализ системы MMP|m|1 с источником повторных вызовов

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2010 Управление, вычислительная техника и информатика № 4

УДК 519.872

Е.А. Судыко

АСИМПТОТИЧЕСКИЙ АНАЛИЗ СИСТЕМЫ MMP|M|1 С ИСТОЧНИКОМ ПОВТОРНЫХ ВЫЗОВОВ1

Для исследования математической модели RQ-системы (Retrial queue) с конфликтами заявок и входящим MMP-потоком (Markov-modulated Process) предложен метод асимптотических семиинвариантов в условии растущего времени задержки в источнике повторных вызовов. Приведены графики распределения вероятностей состояний системы.

Ключевые слова: RQ-система, источник повторных вызовов, конфликты заявок, метод асимптотических семиинвариантов.

Исследованию информационных технологий в целом и сетевых технологий в частности посвящено большое количество работ. Так, вопросам анализа сетей связи и протоколов случайного множественного доступа посвящены работы А.А. Назарова [1 - 5], И.И. Хомичкова [6], А.Н. Дудина [7], В.К. Щербо [8].

Однако многие задачи все еще остаются нерешенными и интересными для исследования. Так, одной из наиболее важных характеристик сети передачи данных является величина задержки, необходимая для доставки сообщения от источника к месту назначения, которая в сетях случайного доступа является нерегулярной.

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

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

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

В данной статье мы рассмотрим систему с повторными вызовами и конфликтом заявок и входящим MMP-потоком.

MMP-потоком называется модулированный пуассоновский поток, если управляющий процесс k(t) является цепью Маркова с непрерывным временем

Для исследования рассматриваемой системы предлагается метод асимптотических семиинвариантов до третьего порядка.

1 Работа выполнена при поддержке АВЦП «Развитие научного потенциала высшей школы (2009 -2010 гг.)» Федерального агенства по образованию по проекту «Разработка методов исследования немарковских СМО и их применение к сложным экономическим системам и компьютерным сетям связи».

1. Постановка задачи

В данной работе рассмотрим RQ-систему (Retrial queue) с конфликтами заявок и входящим MMP-потоком. Заявка, поступившая в систему, отправляется на обслуживание. И если прибор свободен, то начинает осуществляться немедленная передача сообщения, которая заканчивается успешно, если за это время другие сообщения не поступали. Если же во время передачи одного сообщения поступает другое, то в этом случае говорят о ситуации конфликта. Сообщения, попавшие в конфликт, считаются искаженными, переходят в так называемый источник повторных вызовов (ИПВ), откуда вновь подаются на обслуживание после случайной задержки.

В качестве математической модели Яр-системы рассмотрим однолинейную марковскую систему массового обслуживания с источником повторных вызовов, на вход которой поступает ММР-поток заявок, управляемый цепью Маркова, заданной матрицей Q инфинитезимальных характеристик дку и набором неотрицательных величин Xк > 0 . Требование, заставшее прибор свободным, занимает

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

Пусть і (ґ) - число заявок в ИПВ, а І (ґ) - определяет состояние прибора следующим образом:

вероятность того, что прибор в момент времени t находится в состоянии I, управляющая цепь Маркова приняла состояние к и в источнике повторных вызовов находится I заявок.

Процесс { {), к^), I ^)} изменения во времени состояний описанной системы является марковским.

Для распределения вероятностей Р (I, к,/, t) состояний {/, к, /} рассматриваемой Я^-системы составим систему дифференциальных уравнений Колмогорова

2. Математическая модель

0, если прибор свободен,

1, если прибор занят.

Обозначим Р {I {) = I, к ^) = к, I ^) = /'} = Р

dP (dk, 1,1 ^ =-( k + iG)P ( k,',1 ) + (1, k, i,1 ) + X kP(1, k, i - 2, t) +

+(i - 1)ctP(1, k, i -1, t) + £ P(0, v, i, t)qvk ,

др(Xk,i,t) _ -(k +^ + ia^P(,k,i,t) + XkP(0,k,i,t) + ст(і + 1)P(0,k,i +1,t) + dt +Z P(1, v i>t) qvk.

В стационарном режиме система (1) примет вид

-(Х к + іст)Р (0, к ,і)+цР (1, к ,і)+ХкР(1, к ,і - 2)+(і-1)стР(1, к ,і-1)+^ ?(0,у,і)?ї^0,

У

-(Хк +ц+іст)Р (1, к ,і)+ХкР (0, к ,і)+ст(і+1)Р (0, к ,і+1)+^ Р(1,у,і)дук =0.

V

Перепишем систему (2) для функции Н(І,к,и) = ^ е]ШР(1,к,і) следующим

І

образом:

-ХкН(0,к,и) + цН(1,к,и) + е2іиХкН(1,к,и) + устдН(0,к,и) -]еіистдН(1,к,и) +

ди ди

+Х Н (0, V и ^к = 0,

''

\тгґл , \ л гг/а ; \  дН

-(Хк + Ц)Н І1, к, и ) + Х кН ( к, и) + іст------------------------------1-Iе ст-г-+

ди ди

+Х Н (1, v, и) ^к =0.

V

Обозначив вектор-строку Н(І,и) = {Н(1,1,и), Н(1,2,и),............}, эту систему пере-

пишем в виде

Н(0,и)©-Л) + Н(1,и)(е2]иЛ + ц/) + уст дН(0,и) -]еіистдН(1,и) =0,

ди ди

Н (0, и )Л + Н (1, и )(Q-Л-ц/) - і"е~іи стдН (0, и) + устдН (1, и) = 0.

ди ди

где / - единичная матрица.

Обозначив вектор-строку Н(и) = {Н(0,и), Н(1,и)}, эту систему перепишем в матричном виде

іст дН

ди

где матрицы А(уи), В(уи) являются блочными матрицами и имеют вид

А( іи) =

( -/ е~1и/Л

е]и/ -/

, Q-л л

В

ц/ + е2 ;и Л Q-Л-ц/

Матрицы допускают следующие разложения:

ад / • XV ад / • XV

А(р)= Ха, ад= Х '-Щ-в,.

V=0 ,! ,=0 ,!

Вид матриц А,, В, очевидно определяется из (5):

Ас =

(7 -/), 40 (Т];

Q-л л ^ Г 00

В0 [ц/ + Л б-Л-ц/ , Bv [ 2,л 0

Полученное равенство (4) будем называть основным для составленной математической модели.

Решение H (и) уравнений (4) найдем при помощи предлагаемого в данной работе метода асимптотических семиинвариантов в условии растущего времени задержки в источнике повторных вызовов.

3. Асимптотика первого порядка

Для нахождения асимптотики первого порядка в основном уравнении (4) выполним следующие замены:

СТ = 6, и = Sw, H

Тогда уравнение (4) примет вид

j S) A

dw

Теорема 1. Предельное при е—0 значение F1(w)решения F1(w,е) уравнения (7) имеет вид

F

где вектор R является решением системы

R

удовлетворяющим условию нормировки

RE = 1,

а величина к1 является решением нелинейного скалярного уравнения

R

где вектор R = R(к1) зависит от к1 и является решением системы (9), (10).

Доказательство. При е —0, обозначив lim F1(w, е) = F1 (w), перепишем

е—>0 1 1

уравнение (7) следующим образом:

cF

j-^-A = F

dw

решение F (w) которого запишем в виде произведения

F1

где неизвестный вектор R будет определен ниже. Вектор R имеет смысл распределения вероятностей значений процесса l(t) при е —0, а скалярная функция

Ф1 (w) определяется следующим образом. Для этого сложим все уравнения системы (7), умножив это равенство на единичный вектор E. Затем, раскладывая

матрицы A( jew), B( jew) по малому параметру и подставляя в полученное равен-

ство произведение (13), получим нелинейное уравнение

^

j-У-RA, E = Ф1

dw

решение Ф1 (w) которого, удовлетворяющее начальному условию Ф1 (0) = 1, имеет вид

Ф1

где величина к1 будет определена ниже.

Подставляя (15) в (13), а затем в (12), получим однородную систему уравнений.

Я

определяющую вектор Я = Я( к1), удовлетворяющий условию нормировки ЯЕ = 1.

Подставляя равенство (15) в уравнение (14), получим нелинейное скалярное уравнение относительно неизвестной величины к1:

Я

Теорема доказана.

В силу замен (6), равенств Н(1,и) = £ е1ШР(1, г) и (15), можно записать асим-

г

птотическое равенство

К/

МеМ‘) = н(и)Е = £ г]ш £ Р(1,г) = Е^, е)Е и ^¡(м>)Е = е;“ /ст .

г I

Ш к/

Функцию А1(м) = е /ст будем называть асимптотикой первого порядка. Величину к^ ст, которая определяет асимптотическое среднее значение числа заявок в источнике повторных вызовов, будем называть асимптотическим семиинвариантом первого порядка.

4. Асимптотика второго порядка

Для нахождения асимптотики второго порядка в уравнении (4) выполним замену

Н

для неизвестной вектор-функции Н2(м) получим уравнение

ст дн2

дш

в котором выполним замены

ст = є2, м = ew, H2

Уравнение (19) примет вид

jedFd-w-)A

dw

Теорема 2. Предельное при є^-0 значение F2(w)решения F2(w,є) уравнения (21) имеет вид

F2{w) = R expjjLк2 J ,

где вектор R определен в теореме 1, а величина к2 определяется равенством

g1 (B1 + К1 Ai )E + ТR (B2 + К1A2 )e

к 2 =-----------------2---------------,

2 RA1E + g (B1 +к1 A1 )E

в котором векторы g1 и g являются решениями следующих систем уравнений:

gi(B0 +кИо) + R( +KjAj ) = 0,

g В +Kj Ao) +RAo =0.

Доказательство. Этап 1: В этом уравнении сделаем предельный переход при s —— 0 , обозначив lim F2 (w, s) = F2 (w), получим уравнение

s—0

F2

Тогда его решение F2 (w) запишем в виде произведения

F2

где R - вектор, определенный системой (9) и условием нормировки RE = 1, а скалярная функция Ф 2 (w) определена равенством (25), где значение к2 будет определено ниже.

Этап 2: Раскладывая матрицы A(jsw), В(jsw) в ряды по параметру s, систему (21) перепишем с точностью до бесконечно малых слагаемых порядка s2 следующим образом:

^s) A0 = F2

dw

Решение Fi(w, s) этой системы будем искать в виде

F2

Подставляя разложение (27) в предыдущее равенство, получим неоднородную систему уравнений

f1(w)(В0 +K1 A0) +R ( +K1A1 +K2A0 ) = 0 относительно вектор-функции f (w), из которой вектор-функцию f (w) можно записать в виде разложения

f1

где G1(w) - произвольная скалярная функция, а вектор h1 является решением системы

h (В0 + K1A0)+R (( +K A1 + K2 A0) = 0,

Представим h1 в виде разложения

h1 = g1 +K2g ,

где g1

Этап 3: Для нахождения скалярной величины к2 просуммируем все уравнения системы (21), умножив ее на единичный вектор E, получим

^s) A

dw

Раскладывая матрицы А(]єм>), В(]єм>) в ряды по параметру є и учитывая равенство Я(В1 + к1 А1)Е = 0 , перепишем (30) в виде

Несмотря на то, что общие решения и g систем (29) имеют вид

&1 = С1Я + glчaсmное и g = С2Я + gчастное соответственно, равенство (31) Для не будет зависеть от слагаемых С1Я и С2Я в силу равенства Я(В1 + к1 А1)Е = 0 . Следовательно, искать значение констант С1 и С2 не имеет смысла.

Следствие. Выражение для определения скалярной величины к2 (31) не зависит от слагаемого 01(м)Я в разложении для /¡(м) (28). Вследствие этого вектор Л (м) в разложении (27) можно рассматривать не зависящим от переменной м , то есть (27) записать в виде

будем называть асимптотикой второго порядка. Тогда величину к2/ст, которая определяет асимптотическую дисперсию, будем называть асимптотическим семиинвариантом второго порядка.

Из вида И2(и)следует, что число заявок в источнике повторных вызовов распределено асимптотически нормально.

Имея в виду (29), получаем

Следовательно, решение к2 будет выглядеть следующим образом:

&1 (В1 +К1А1 )Е + 1 К (В2 +К1А2 )Е

ЯА1Е + g (В 1 +к1 А1 )Е

В силу замен (18), равенств Н(1,и) = ^ е]тР(1, і) и (21), можно записать асимп-

і

тотическое равенство

Ме]иі(і) = Н(и)Е = е]ик/стН2 (и)Е = е1ик1/ст1 Е2 (м>, є)Е и е]ик/ст Е2 (м>)Е =

Функцию

5. Асимптотика третьего порядка

Для нахождения асимптотики третьего порядка в уравнении (19) выполним замену

H2

для неизвестной вектор-функции H3(u) получим уравнение

j^dH3

du

в котором выполним замены

ст = е3, u = ew, H3

Уравнение (33) примет вид

2 dF3(w, e) , .

je --- -----A

dw

Теорема 3. Предельное при e—0 значение F3(w)решения F3(w,e) уравнения (35) имеет вид

F,

где вектор R определен в теореме 1, а величина к3 определяется равенством

h1 {2 + K1A2 + -K2 A1 }} + g2

к3 =---------------------------------------------------------------------:-г3-,

3 RA1E + g ( +к1 A1 )E

в котором векторы h1, g и g2 являются решениями следующих систем уравнений:

h1 {0 + K1A0 } +R {K2A0 +Б1 + K1A1 } = 0 ,

g2 (Б() + KiA0) + R ((2 + KA2 + 2k2Ai ) + 2hi (( +KAi + K2A)) = 0,

g (Б0 +k A,)+RA) =0.

Доказательство. Этап 1: В уравнении (37) сделаем предельный переход при e —— 0 , получим равенство

Fs( w) ( +Ki A, ) = 0.

Тогда его решение будем искать в виде

F3

Этап 2: Систему (35) перепишем с точностью до бесконечно малых слагаемых порядка e3 следующим образом:

je2---3f , ) A0 = F3(w, e) j Б0 +K1A0 + jew (Б1 +K1A1 )+ (j , ) (Б2 +K1A2 ) +

dw j 2

+ jewK2 A) + (jew)2 K2 Ai | + O(e3).

Решение F3 (w, e) этой системы будем искать в виде

F3

Подставляя разложение (39) в предыдущее равенство, получим j2e2 (jw к3RAq = R j jew(Б +кA1 +k2Aq) + íj—)—(б2 + k1 A2 +2k221) | +

\2

2

+Іє^Л (м) {Во + к А + ;'є^( В1 +к А1 +к2 А))} + Л2( м) {Во + к Ао} + 0(є3).

Приравнивая коэффициенты при одинаковых степенях є, получим следующие уравнения:

Є: Я{А + В +кА1} + А(м>){Во +к1 А)} = 0,

є2 : 2Л2 (м)(0 +к1 А)+2К{В2 +к1 А2 + 2к2 А1} + Л1 (м){к24) + В1 +к1 А1}+2к3ЯА0 = 0 .(40) Решение Л (^) первой системы (40) запишем в виде

Л

где 01 (^) - произвольная скалярная функция, а вектор Их определяется системой

^1 {В0 + к1 А) } +Я {к2А) +В1 + к1 А1 } = 0 .

Решение Л2 (м) второй системы (40) запишем в виде

Л2

где 02 (м) - произвольная скалярная функция, а вектор к2 определяется системой ^2 {В0 + к1 А] } + Я {2к2 А1 + В2 + к1 А2 + кз А] } + 2^1 {В +к1 А1 + к2 А) } = 0. Представим к2 в виде разложения

к2 = ё2 + к3ё ,

где ё2 (В0 + к1 А0) + Я (2 +к1 А2 + 2к2А1) + 2И1 ( +к1 А1 + к2А) = 0,

ё В +к1 А) +ЯА =0.

Этап 3: Для нахождения к3 просуммируем все уравнения системы (35), умножив ее на единичный вектор Е , получим

2 дК(м, є) , .

jє —3-А

дм

Раскладывая матрицы по малому порядку и учитывая Я( В0 +к1 Ао) = 0, перепишем (43) в виде

к3RA1E+—R{B— +KjA— +3k2A2}E+f (w){B— +KjA2 +2k2AjE+f2(w)B +KjAx)E=0 . Имея в виду (41) и (42), получаем

К3 RAi E +— R {B + к A3 + ЗК2 A2 } E + (Gi (w)R + hi) {B— + Ki A2 + 2k2 Ai } E +

+(G— (w)R + h2 + G1 (w)h3) ( + k1 A1) E = 0,

где G1 (w)R {B2 +k1 A2 + 2k2A1} E + G1 (w)h3 (B1 + k1 A1) E = 0

в силу второй системы (40).

Следовательно, решение для к3 будет выглядеть следующим образом:

h1 {B2 + К1A2 + 2k2 A1} E + g2 (B1 + K1A1 )E +TR (B3 + K1A3 + —2 A2 )E

k3 =------------------------------------------------------------------------------3-.

3 RA1E + g (B1 +k1 A1 )E

Несмотря на то, что общие решения g2, h1 и g имеют вид g2 = C1R + g2частное,

h1 = С2R + hiчастное и g = C3R + gчастное соответственно, равенство (44) дЛЯ кз не

будет зависеть от слагаемых C1R , C2R и СзR в силу равенстваR(B1 + к1 A1)E = 0 . Следовательно, искать значение констант С1, С2 и Сз не имеет смысла.

Следствие. Выражения для определения скалярной величины кз (44) не зависят от слагаемых G1(w)R и G2(w)R в разложениях для f1(w) и f2(w) в (41) и (42). Вследствие этого векторы f1( w) и f2( w) в разложении (39) можно рассматривать не зависящими от переменной w , то есть (39) записать в виде

F3 (w, е) = exp Кз j |R + jzwf + (J'ew f— j + 0(ез).

В силу замен (32), (34) и равенства H(l,u) = ^ eJu’P(l, i), можно записать

i

асимптотическое равенство

(ju)—к /а (ju)2к /а

MeJui = H(u)E = eJuKi/ge 2! Hз(и)E = eJuKi/ge 2! F3(w,е)E и

(ju)2 к /„ Г t ( ;,. \3

e]uK^e 2! ^ F3(w)E и exp I ju ст+ (J,Е к2/ ст+ (jЕ кз/ ctJ. Функцию

h3(u) = exp J ju к^ g + Bj—)— k2/ g + Bj—)— кз/ g [•

I 2 6 J

будем называть асимптотикой третьего порядка. Величину к—/g будем называть асимптотическим семиинвариантом третьего порядка.

Аналогично асимптотикам первых трех порядков можно получить вид асимптотики произвольного порядка m:

К (и) = ехР |£ К^ст!

V!

где кт/ст будем называть асимптотическим семиинвариантом V -го порядка.

6. Распределение вероятностей состояний системы

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

ПО') = 2- I 1ШК 0') Ли, V = 2,3,

где

2-

\ (и) = ехр |£

а=1

(М К

I! СТ

величины к определяются из (17), (31) и (44).

Определим значения параметров. Пусть ст = 0,01, ц = 1,

0,1 0 0 " "-0,3 0,1 0,2 "

Л = 0 0,2 0 , Q = 0,2 -0,4 0,2

_ 0 0 0,3_ _ 0,2 0,3 1 0, -

I = 0...100.

Построим асимптотическое распределение вероятностей числа заявок в ИПВ для различных V следующим образом:

Рис. 1 Асимптотическое распределение вероятностей числа заявок в ИПВ для V = 2,3 .

На графиках (рис. 1) показаны распределения вероятностей числа заявок в ИПВ, полученных с помощью асимптотического анализа.

Заключение

В работе предложен метод асимптотических семиинвариантов для исследования математической модели Я^-системы с конфликтами заявок и входящим ММР-потоком. Применен метод асимптотических семиинвариантов в условии растущего времени задержки в источнике повторных вызовов. Построены графики распределения вероятностей состояний системы.

ЛИТЕРАТУРА

1. Назаров А.А., Пичугин С.Б. Исследование спутниковой сети связи методом математического моделирования // Изв. вузов. Физика. 1992. № 9. С. 120-129.

2. Назаров А.А., Одышев Ю.Д. Исследование сетей связи с протоколами «адаптивная Алоха» для конечного числа станций в условиях перегрузки // Проблемы передачи информации. 2000. № 3. С. 83-93.

3. Назаров А.А., Никитина М.А. Применение условий эргодичности цепей Маркова к исследованию существования стационарных режимов в сетях связи // Автоматика и вычислительная техника. 2003. № 1. С. 59 - 66.

4. Назаров А.А., Одышев Ю.Д. Исследование сети связи с динамическим протоколом «синхронная Алоха» в условиях большой загрузки // Автоматика и вычислительная техника. 2001. № 1. С. 77 - 84.

5. Назаров А.А., Цой С.А. Общий подход к исследованию марковских моделей сетей передачи данных, управляемых статистическими протоколами случайного множественного доступа // Автоматика и вычислительная техника. 2004. № 4. С. 73-85.

6. Хомичков И.И. Исследование моделей локальной сети с протоколом случайного множественного доступа // АиТ. 1993. № 12. С. 89 - 90.

7. Дудин А.Н., Клименок В.И. Системы массового обслуживания с коррелированными потоками. Минск: БГУ, 2000. С. 221.

8. Щербо В.К., Киреичев В.М., Самойленко С.И. Стандарты по локальным вычислительным сетям.: Справочник. М.: Радио и связь, 1990. С. 304.

9. КлейнрокЛ., Вычислительные системы с очередями. М.: Мир, 1979. С. 598.

10. D’Apice С., De Simone Т., Manzo R., Rizelian G. Priority service of primery customers in the M/G/1/r retrial queueing system with server searching for customers // J. Information Theory and Information Processing. 2004. V. 4. No. 1. P. 13-23.

11. Bocharov P., D’Apice C., D’Auria B., Salerno S., A queueing system of finite capacity with the server requiring a priority search for customers // Vestnik RUDN, Seria Prikladnaia Matematika I Informatika. 2000. No. 12. P. 50-61.

12. Bocharov P., D’Apice C., Phong N., Rizelian G., Retrial servicing of multivariate Poisson flow with customer-searching server with finite buffer // Ibid. 2002. No. 1. P. 98-106.

13. Artalejo J.R., Joshua V.C., Krashnamoorthy A., An M/G/1 retrial gueue witn orbital search by the server // Advances in Stochastic Modeling (J.R. Artalejo, A. Krishnamoopthy (Eds)). Notable publications, New Jersey, 2002. P. 41-54.

14. Колоусов Д.В., Назаров А.А., Цой С.А. Исследование вероятностно-временных характеристик бистабильных сетей случайного доступа // АиТ. 2006. № 2. С. 90-105.

15. Коцюруба П.И., Назаров А.А. Исследование асимптотических средних характеристик немарковских моделей неустойчивых сетей случайного доступа // Проблемы передачи информации. 2003. № 3. С. 77-88.

Судыко Елена Александровна Томский государственный университет E-mail: ESudyko@yandex.ru

Поступила в редакцию 19 мая 2010 г.