The method of the asymptotic semiinvariants of the system MMP|M|1 withretrial queue.pdf Исследованию информационных технологий в целом и сетевых технологий в частности посвящено большое количество работ. Так, вопросам анализа сетей связи и протоколов случайного множественного доступа посвящены работы А.А. Назарова [1 - 5], И.И. Хомичкова [6], А.Н. Дудина [7], В.К. Щербо [8].Однако многие задачи все еще остаются нерешенными и интересными для ис-следования. Так, одной из наиболее важных характеристик сети передачи данных является величина задержки, необходимая для доставки сообщения от источника к месту назначения, которая в сетях случайного доступа является нерегулярной.В реальных системах часто наблюдаются эффекты повторных обращений зая-вок к обслуживающему прибору, конфликты заявок требуют рассмотрения моде-лей, выходящих за рамки классических систем массового обслуживания. Поэтому интерес к рассмотрению таких, более реальных систем возрастает. В связи с этим появилось большое количество работ, посвященных рассмотрению систем с по-вторными заявками, такие, как [9 - 13], в которых развиваются численные методы исследования.Альтернативным подходом является применение метода асимптотического анализа для исследования таких систем.Методом асимптотического анализа в теории массового обслуживания будем называть решение уравнений, определяющих какие-либо характеристики системы при выполнении некоторого предельного условия, вид которого будет конкрети-зирован для различных моделей и поставленных задач исследования.В данной статье мы рассмотрим систему с повторными вызовами и конфлик-том заявок и входящим MMP-потоком.МMP-потоком называется модулированный пуассоновский поток, если управ-ляющий процесс k(t) является цепью Маркова с непрерывным временемДля исследования рассматриваемой системы предлагается метод асимптотиче-ских семиинвариантов до третьего порядка.1 Работа выполнена при поддержке АВЦП «Развитие научного потенциала высшей школы (2009 -2010 гг.)» Федерального агенства по образованию по проекту «Разработка методов исследования не-марковских СМО и их применение к сложным экономическим системам и компьютерным сетям связи».80Е.А. Судыко1. Постановка задачиВ данной работе рассмотрим RQ-систему (Retrial queue) с конфликтами заявок и входящим MMP-потоком. Заявка, поступившая в систему, отправляется на обслуживание. И если прибор свободен, то начинает осуществляться немедленная передача сообщения, которая заканчивается успешно, если за это время другие сообщения не поступали. Если же во время передачи одного сообщения поступает другое, то в этом случае говорят о ситуации конфликта. Сообщения, попавшие в конфликт, считаются искаженными, переходят в так называемый источник повторных вызовов (ИПВ), откуда вновь подаются на обслуживание после случайной задержки.2. Математическая модельВ качестве математической модели RQ-системы рассмотрим однолинейную марковскую систему массового обслуживания с источником повторных вызовов, на вход которой поступает MMP-поток заявок, управляемый цепью Маркова, заданной матрицей Q инфинитезимальных характеристик qkν и набором неотрицательных величин λk ≥ 0. Требование, заставшее прибор свободным, занимаетего для обслуживания в течение случайного времени, распределенного по экспоненциальному закону с параметром μ. Если прибор занят, то поступившая и обслуживаемая заявки вступают в конфликт и переходят в источник повторных вызовов (ИПВ), где осуществляют случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром σ . Из ИПВ после случайной задержки заявка вновь обращается к прибору с повторной попыткой его захвата. Если прибор свободен, то заявка из ИПВ занимает его на случайное время обслуживания.Пусть i(t)- число заявок в ИПВ, а l(t)- определяет состояние прибора следующим образом:() = {0, если прибор свободен, 1, если прибор занят.ОбозначимP{l(t) = l, k(t) = k,i(t) = i} = P(l,k,i,t)вероятность того, что прибор в момент времени t находится в состоянии l, управляющая цепь Маркова приняла состояние k и в источнике повторных вызовов находится i заявок.Процесс {l(t),k(t),i(t)} изменения во времени состояний описанной системы является марковским.Для распределения вероятностей P(l,k,i,t) состояний {l,k,i} рассматриваемой RQ-системы составим систему дифференциальных уравнений Колмогорова∂P(0,k,i,t) =-(λk+iσ)P(0,k,i,t) + μP(1,k,i,t) + λkP(1,k,i-2,t) +∂t+(i - 1)σ P(1, k, i -1,t ) + ∑ P (0, ν, i, t)qνk ,дР(\ к i t )(1 )v' ' , = -(λk +μ + iσ)P(1,k,i,t) + λkP(0,k,i,t) + σ(i + 1)P(0,k,i+1,t) + ∂tνАсимптотический анализ системы ММР \ М \ 1 с источником повторных вызовов81В стационарном режиме система (1) примет вид-(Хk+iа)P(0, k,i)+цP(1, k,i)+ЧP(1, k,i-2)+(i-1)аP(1, k,i-1)+^P(0,у,i)q=0,v(2)- (Xk +\i+ia) P ( ,k,i ) +"KkP ( 0,k,i ) +a( i+1 ) P ( 0,k,i+1 ) +Y P(1,v,i)qvk = 0.VПерепишем систему (2) для функции H(l,k,u) = ^ejuiP(l,k,i) следующимiобразом:Л H (0, k )H (1 k )2ju, H (1 k ) j 6H(0,k,u) je ju дH (1,k ,u)dudu+^(0,v,u ) q k=0,v(3)(л)H (1 k ) л H (0 k ) j oH(1,k,u) . -ju oH(0,k,u)udu+YH(1,v,u)qvk=0.VОбозначив вектор-строку H(l,u) = {H(l,1,u), H(l,2,u),}, эту систему перепишем в видедuдuдuдuгде I - единичная матрица.Обозначив вектор-строку H (u) = {H(0,u), H(1,u)}, эту систему перепишем в матричном видеjv^^A(ju)=H(u)B(ju), дuгде матрицы A(ju), B(ju) являются блочными матрицами и имеют вид -I e-juЛ B ju ( Q-ЛЛ, () = \Ke ju I -IA( ju)B( ju )=\I.(5)yyI + e2juA Q-K-yI Матрицы допускают следующие разложения:v=0 v!v=0 v!Вид матриц Av, Bv очевидно определяется из (5):A 0=[- I - I I A=(0 (-1 0 )VI1;B0 = Q I, BV = IПолученное равенство (4) будем называть основным для составленной математической модели.82Е.А. СудыкоРешение H (u) уравнений (4) найдем при помощи предлагаемого в данной работе метода асимптотических семиинвариантов в условии растущего времени задержки в источнике повторных вызовов.3. Асимптотика первого порядкаДля нахождения асимптотики первого порядка в основном уравнении (4) выполним следующие замены:ст = в, u = ew, H(u) = F1 (w, e).Тогда уравнение (4) примет видjdF1( w ,) A(jsw) = F(w,e)B(jzw).OwТеорема 1. Предельное при е^-0 значение F1(w) решения F 1(w ,е) уравнения (7) имеет видF1 (w) = RejeK1, где вектор R является решением системыR(B0+k1A0) = 0,удовлетворяющим условию нормировкиRE = 1, а величина к1 является решением нелинейного скалярного уравненияR(B1+K1A1)E = 0, где вектор R = R(к1) зависит от к1 и является решением системы (9), (10). Доказательство. При е-»0, обозначив limF1(w,e) = F1(w), перепишемуравнение (7) следующим образом:dF(w) j 1 A0=F1(w)B0,owрешение F1 (w) которого запишем в виде произведенияF1 (w) = R Ф1 (w),(13)где неизвестный вектор R будет определен ниже. Вектор R имеет смысл распределения вероятностей значений процесса l(t) при е ->■ 0, а скалярная функцияФ1 (w) определяется следующим образом. Для этого сложим все уравнения системы (7), умножив это равенство на единичный вектор E. Затем, раскладывая матрицы A(jew), B(jew) по малому параметру и подставляя в полученное равенство произведение (13), получим нелинейное уравнениедФ()jw RA1E = 1(w)RB1E,(14)dwрешение Ф1 (w) которого, удовлетворяющее начальному условию Ф1 (0) = 1, имеет вид01(w) = exp{jwK1},где величина к1 будет определена ниже.Асимптотический анализ системы ММР \ М \ 1 с источником повторных вызовов83Подставляя (15) в (13), а затем в (12), получим однородную систему уравнений.R(B0+k1A0) = 0,определяющую вектор R = R(к1), удовлетворяющий условию нормировки RE = 1.Подставляя равенство (15) в уравнение (14), получим нелинейное скалярное уравнение относительно неизвестной величины к1:R(K1)(B1+K1A1)E = 0,Теорема доказана.В силу замен (6), равенств H(l,u) = ^ejuiP(l,i) и (15), можно записать асим-iптотическое равенствоMejui(t) = H(u)E = ^ejui^P(l,i) = F1(w,&)E « F1(w)E = eju 'a .ilФункцию h1 (u) = eju 1 будем называть асимптотикой первого порядка. Величину K1 /a, которая определяет асимптотическое среднее значение числа заявок в источнике повторных вызовов, будем называть асимптотическим семиинвариантом первого порядка.4. Асимптотика второго порядкаДля нахождения асимптотики второго порядка в уравнении (4) выполним заменуH(u) = H2(u)exp { j uк1 } ,для неизвестной вектор-функции H2 (u) получим уравнениеjаШ^A( ju) = H 2( u ){ B ( ju ) + к1 A ( ju )} ,дuдH2(u дu в котором выполним заменыu = ew, H2(u) = F2(w,e).(20)Уравнение (19) примет видjedF2(w,s) A(jew) = F2(w ,E){B(jew) + K1 A(jEw)}.(21owТеорема 2. Предельное при е^-0 значение F2(w) решения F2(w,e) уравнения (21) имеет видF2(w)=Rexp|2K2L где вектор R определен в теореме 1, а величина к2 определяется равенствомg1(B1+K1A1)E + 1R(B2+K1A2)Eк2 =,RA1E + g(B1+K1A1)E84Е.А. Судыков котором векторы g1иg являются решениями следующих систем уравнений:g1(B0+K1A0) + R(B1+K1A1) = 0,g(B0+к1A 0)+RA0=0. Доказательство. Этап 1: В этом уравнении сделаем предельный переход при е ->■ 0 , обозначив limF2(w,e) = F2(w), получим уравнениее->0F2(w)(B0+k1A0) = 0.(24)Тогда его решение F2 (w) запишем в виде произведенияМjw )F2(w) = R2(w) = Rexpl±^K2\,где R - вектор, определенный системой (9) и условием нормировки RE = 1, а скалярная функция Ф2 (w) определена равенством (25), где значение к2 будет определено ниже.Этап 2: Раскладывая матрицы A(jew), B(jew) в ряды по параметру е, систему (21) перепишем с точностью до бесконечно малых слагаемых порядка е2 следующим образом:jedF2( w,e) A 0 =F2(w,E){ B 0 +К1 A 0 +jEw(B 1 +к1 A1)} + O(е2 ).(26)OwРешение F2(w,e) этой системы будем искать в видеF2 (w, 6) = exp 2 к2 \{R + jewf1 (w)} + O(е2 ).(27Подставляя разложение (27) в предыдущее равенство, получим неоднородную систему уравненийf1 (w)(B0 + к1 A0 ) + R(B1+K1A1+ к2A0) = 0относительно вектор-функции f1 (w), из которой вектор-функцию f1 (w) можно записать в виде разложенияf 1 (w) = G1 (w)R + h1,(28)где G1 (w) - произвольная скалярная функция, а вектор h 1 является решением системыh1(B0+K1A0) + R(B1 +K1 A 1 +k2A 0) = 0, Представим h 1 в виде разложенияh 1 = g1+K2g,гдеg1(B0+-K1A0)+R(B1+-K1A1) = 0, g(B0+K1A0) + RA0 =0.(29)Этап 3: Для нахождения скалярной величины к2 просуммируем все уравнения системы (21), умножив ее на единичный вектор E, получимje 2A(jew)E = F2(w,e){B(jew) + K1A(jew)}E.(30)dwАсимптотический анализ системы ММР \ М \ 1 с источником повторных вызовов85Раскладывая матрицы A(jew), B(jew) в ряды по параметру е и учитывая равенство R(B1 + К1 A 1 )E = 0, перепишем (30) в видеk2RA1E + -R(B2 +K1A2)E + f1(w)(B1 + к1A1)E = 0 .K2RA1E + 1R(B2+K1A2)E + (g1+K2g)(B1+K1A1)E = 0Имея в виду (29), получаем k2RA1E + 1R(B2 Следовательно, решение к2 будет выглядеть следующим образом:g1(B1+K1A1)E + 1R(B2+K1A2)Eк2=2.RA1 E + g(B 1+yl1A1)EНесмотря на то, что общие решения g1 и g систем (29) имеют види g = C2R + gчастное соответственно, равенство (31) для к2 не будет зависеть от слагаемых C1R и C2R в силу равенства R(B1 + к1 A 1 )E = 0 . Следовательно, искать значение констант C 1 и C2 не имеет смысла.Следствие. Выражение для определения скалярной величины к2 (31) не зависит от слагаемого G1(w)R в разложении для f1(w) (28). Вследствие этого вектор f 1 (w) в разложении (27) можно рассматривать не зависящим от переменной w , то есть (27) записать в виде11частное2CR +F2 (w, 6) = exp 2 к Л {R + jewf1} + O(s2). В силу замен (18), равенств H(l,u) = ^ejuiP(l,i) и (21), можно записать асимп-iтотическое равенствоMejui ( t ) = H( u)E = ejuфH2(u)E = eju4/c!1F2(w,e)E « ejm/C1F2(w)E == expЬuк1/ст + 2к2/ст1.Функцию/ (ju) i h2 (u) = exp ■ 0 , получим равенствоF3(w)(B0+k1A0) = 0.Тогда его решение будем искать в видеF3(w) = R03(w) = Rexp\ jw к3 >.(38)Этап 2: Систему (35) перепишем с точностью до бесконечно малых слагаемых порядка б3 следующим образом:Асимптотический анализ системы ММР \ М \ 1 с источником повторных вызовов87jе2 F 3( w,£) A0 = F3 (w, 6) \B 0 + к1 A 0 + jew (B 1 + к1 A 1) + ( j w ) (B2 + к1 A2) +ow2+ jswK2A 0 + (jew)2K2 A 1 +O(б3). Решение F3(w,e) этой системы будем искать в видеF3(w,s) = exp|6К3 NR + jEwf 1(w) + 2 f2(w)^ + O(E3 ).(39)Подставляя разложение (39) в предыдущее равенство, получим22 (jw)2Л( j8w)jsк3RA 0 =Ryj6w(B 1 +К1 A 1 + к2A 0) +- (B2+к1A2 +2к2A 1) + л2 +jwf1 (w) {B0 + K1 A 0 + jsw(B 1 + K1 A 1 + к2A 0)} + ( j 2 f2 (w) {B0 + к1 A0 } + O(е3 ).Приравнивая коэффициенты при одинаковых степенях е, получим следующие уравнения:е: R{к2A 0 +B 1 + к1 A 1} + f1(w){B0 +K1 A0} = 0,е2: 2 f2 (w)(B0 +к1 A 0)+ 2ЧВ2 +*1 A 2 +2к2A 1}+f 1 (w ){к2 A 0 +B 1 +k1A1}+1k3RA0 =0 .(40) Решение f1 (w) первой системы (40) запишем в видеf1(w) = h 1+G1(w)R,где G1 (w) - произвольная скалярная функция, а вектор h 1 определяется системойh 1 {B0 +к1A 0}+R{к2A 0 +B 1 +К1A 1} = 0 .Решение f2 (w) второй системы (40) запишем в видеf2 (w) = G2 (w)R + h2 + 2G1 (w)h 1,где G2(w)- произвольная скалярная функция, а вектор h2 определяется системойh2{B0 +K1A0} + R{2K2A1 +B2 + к1 A 2 +к3A 0} + 2h1 {B 1 +к1 A 1 +к2A 0} = .Представим h2 в виде разложенияh2=g2+ к3g ,гдеg2 (B0 + K1 A 0) + R (B2 + K1 A 2 + 2к2A 1) + 2h 1 (B 1 + к1 A 1 + к2A 0) = 0,g(B0+K1A0)+RA0=0. Этап 3: Для нахождения к3 просуммируем все уравнения системы (35), умножив ее на единичный вектор E, получимje23A(jew)E = F3 (w, е) {B(jew) + K1 A ( jew) + jewK2A(jew)} E. (43)

Скачать электронную версию публикации