Research of non-Markovianmodel of the computer communication network directed by dynamic protocol of access..pdf Построение адекватных математических моделей телекоммуникационных, вы-числительных, производственных систем может быть осуществлено в рамках тео-рии массового обслуживания [1-3]. Сети связи обеспечивают возможность опера-тивно получать, обрабатывать и передавать необходимую информацию. Поэтомуактуальной является задача построения адекватных моделей сетей связи случай-ного доступа и методов их исследования. Исследованию сетей связи в виде сис-тем массового обслуживания (СМО) с источником повторных вызовов посвяще-ны работы А.А. Назарова [4, 5], Г.И. Фалина [6, 7], В.И. Клименок [8], И.И. Хо-мичкова [9−11] и др. Методы теории массового обслуживания [1−3] являютсянаиболее действенными в проведении исследований компьютерных сетей связи,адекватными математическими моделями которых являются RQ-системы (RetrialQueueing systems) [6, 12, 13]. В монографии J. R. Artalejo, A. Gomez-Corral [12]приведено большое количество ссылок на работы, опубликованные за последниедвадцать лет, по этой тематике.Представляет интерес рассмотрение моделей, учитывающих интервалы недос-тупности прибора (моноканала), когда реализуется этап оповещения о конфликте[14], а также исследование сетей связи, управляемых статическими [15], динами-ческими [16, 17], адаптивными [18] протоколами случайного множественногодоступа.В статье рассмотрим немарковскую модель компьютерной сети связи, управ-ляемую динамическим протоколом доступа.1. Постановка задачиЛюбая абонентская станция, сформировав свое сообщение, отправляет его наобщий ресурс. Если ресурс свободен, то начинает осуществляться немедленнаяпередача сообщения, которая заканчивается успешно, если другие сообщения непоступали. А если во время передачи некоторого сообщения поступает другое,происходит наложение сигналов, сообщения считаются искаженными, то естьвозникает конфликт. От момента возникновения конфликта рассылается сигналоповещения о конфликте. Сообщения, попавшие в конфликт, а также поступив-шие на этапе оповещения о конфликте, считаются искаженными и переходят в ис-точник повторных вызовов (ИПВ), откуда вновь обращаются к ресурсу после слу-чайного времени задержки. Задачей данной работы является нахождение распре-деления вероятностей состояний системы.2. Математическая модельМатематическую модель сети связи рассмотрим в виде немарковской одноли-нейной RQ-системы, управляемой динамической дисциплиной обслуживания, навход которой поступает простейший поток заявок с интенсивностью ƒ (рис. 1).Требование, заставшее прибор свободным, занимает 5 1 его для обслуживания в те3. Исследование немарковской модели компьютерной сети связи,управляемой динамическим протоколом случайного доступаПусть i(t) - число заявок в ИПВ, k(t) - определяет состояние прибора сле-дующим образом:0, если прибор свободен,( ) 1, если прибор занят,2, если идет этап оповещения о конфликте,k t⎧⎪=⎨⎪⎩z(t) - длина интервала от момента t до момента окончания текущего режимафункционирования прибора при k(t) = 1 и k(t) = 2 в момент времени t.Компонента z(t) определяется только в те моменты, когда k(t)  0 , еслиk(t) = 0 , то компонента z(t) не определяется. ОбозначимP{k(t)=0,i(t)=i}=P0 (i,t) ,P{k(t)=k,i(t)=i,z(t) 0 , следовательно, lim zzeƒ=  , а это означает, что для второго со-множителя выполняется предельное равенство1 ( ) ( )0 00(0,0)ex 0B(x) 1 B(x)dx 0z−ƒ⎧⎨⎩ƒ  − ƒ ƒ − ƒ ƒ ⎫⎬⎭ =  .Тогда 1 ( ) * ( ) *0 0(0,0)0 B() 1 B() 0zƒ− ƒ ƒ ƒ − ƒ ƒ ƒ =, (6)где *0B( ) exdB(x)ƒ =  −ƒ .Из первого уравнения системы (2) следует, что10(0,0)(0)zƒ= ƒ ƒ, (7)поэтому уравнение (6) примет вид( ) ( * ) ( ) *ƒ00ƒ1−B(ƒ) −ƒ01ƒB(ƒ)=0,следовательно,*0 0 *(1) (0)1 ( ).( )BB− ƒƒ ƒ=ƒƒƒ(8)Тогда, с учётом равенств (7) и (8) уравнение (5) перепишем в виде*1 0 *0(0, ) (0,0) ( ) 1 ( ) ( )( )zz ez e x B x B B x dxBƒ −ƒ⎧ − ƒ ⎫ƒ = ƒ ⎨ƒ − ƒ − ƒ ⎬ =⎩ ƒ ⎭ 0 *0(0) 1 ( ) .( )zez e x B x dxBƒ −ƒ ⎧ ⎫= ƒ ƒ⎨ − ⎬⎩ ƒ ⎭ Так как 1(0) lim 1(0, )zzƒ = ƒ , то( )* *1 0 0 * 0 *1 10 (0) ( ) (0) 1 1 (0)1 ( )( ) ( )B BB Bƒ =ƒ ƒ⎝⎛⎜ −−ƒ ƒ ⎠⎞⎟=ƒ ⎜⎛⎝ ƒ − ⎟⎞⎠=ƒ − ƒƒ.Для системы (4) можно записать( )}( ) }( ) ( ) 11 001 0(1 ) (1 ) 22021 1( ,0)( , ) ( ) ( )(0, ) (0) ( ) ,( ,0)( , )( ) ( ) (0) ( ) ,ju juzz x jujuze z e xju ju juH uH u z e e H u e B xzx e B x dxH uH u z e ezH u e e A x e A x dxƒ+ƒ − ƒ+ƒ −−ƒ − −ƒ −⎧  ⎧ = − ƒ + ƒ − ⎪ ⎨  ⎩ ⎪⎪ƒ ƒ+ƒ ƒ ⎪⎪⎨ ⎧ ⎪ = − ⎨ ⎪  ⎩ ⎪⎪ƒ +ƒ +ƒ ƒ ⎪⎩(10)тогда получим следующую систему уравнений:( )( )( ) ( ( )) ( ( ))( )1 * * *0 1 011 0 1 02 2 * *1 12 22 1( ,0)( ) ( ) (0, ) (0) ( ) 0,( ,0)( ) ( )( ) (0) (0) 0,( ,0)( ) 1 (0) 1 0,( ,0)( ) 1 ( )ju jujuju ju ju ju jujuH uH u e B e BzH uH u H u ezH uH u e e A e e A ezH uH u e H u ez− −−− ƒ+ ƒ ƒ+ƒ −ƒ ƒ+ƒƒ+ƒ ƒ ƒ+ƒ =+ ƒ + ƒ − ƒ + ƒ − ƒ ƒ + ƒ ƒ =− ƒ + ƒ ƒ − + ƒ ƒ ƒ − =+ ƒ − − ƒ ( )( )11 20 0(0) 0,( ,0) ( ,0)( ) (0) 0,ju eju ejuH u H uH uz z⎧⎪⎪⎪⎪⎪⎪⎨⎪⎪+ ƒ + ƒ ƒ = ⎪⎪⎪ + − ƒ + ƒ + ƒ ƒ =⎪⎩  (11)где ( )*1 0 *0 (0)1 ( )( )BB− ƒƒ =ƒƒ,* **1 0 *(0, ) (0) ( ) ( )( )B BBƒ ƒ − ƒ + ƒƒ ƒ+ƒ = ƒƒ ƒ.Система (11) является системой пяти уравнений относительно трёх основных0( ) H u , 1( ) H u , 2( ) H u и двух вспомогательных неизвестных 1( ,0),H uzH2(u,0)z.В эту систему также входит величина ƒ0 (0) , значение которой будет определенониже из условия нормировки.И с к л ю ч е н и е в с п о м о г а т е л ь н ы х н е и з в е с т н ы хДомножим второе уравнение системы (11) на e ju , сложим с четвертым и, вы-читая из полученного равенства пятое уравнение, запишем1 ( ) ( ) ( ) ( )0 1 2( ,0)H u ju 1 () ju 1 () ju ju 1 () ju 1 0e Hu e Hue e Hu ez− − ƒ − − ƒ − − ƒ − =,откуда получим равенство10 1 2( ,0)H u ( ) ( ) ju ( )H u H u e H uz= ƒ+ ƒ + ƒ. (12)Домножая четвертое уравнение системы (11) на A*(ƒ(1−eju)) и вычитая изтретьего уравнения, запишем2 { *( ( ))} ( )*( ( ))2( ,0)H u 1 1 ju () 1 ju 1 ju 0,A e Hu e A ez− ƒ − − ƒ − ƒ − =откуда получим равенство( ) ( ( ))( ( ))*22 *( ,0) 1( ) 1 01 1jujujuH u A eH u ez A e ƒ −= ƒ − = − ƒ −. (13)Применяя полученные равенства (12) и (13) к первому, второму и четвертомууравнениям системы (11), получим{ ( ) }{ ( ) }{ } ( )( ( ))*0 1 2* **0 **0 1 2 0 **21 2 * 0( ) ( ) ( ) ( )(0) ( ) ( ) ( ) ,( )( ) ( ) 1 ( ) (0) 1 ( ) ,( )( ) ( ) 1 (0) 1 (1 1ju jujuju ju jujuju jujuH u e B H u e H uB B e BBH u e H u e H u B eBH u e e H u e BA e−−− −ƒ − ƒ + ƒ ƒ + ƒ + ƒ + ƒ =⎧ ƒ − ƒ + ƒ ⎫= ƒ ⎨ƒ − ƒ ƒ + ƒ⎬⎩ ƒ ⎭⎧ − ƒ ⎫− ƒ+ ƒ + + ƒ + ƒ = ƒ ⎨ƒ − ƒ ⎬⎩ ƒ ⎭ƒ − − ƒ− ƒ +ƒ + =ƒ −ƒ− ƒ − *) .( )e juB⎧⎪⎪⎪⎪⎪⎨⎪⎪⎪⎧ ⎫⎪ ⎨ ⎬⎪⎩ ⎩ ƒ ⎭(14)Система (14) является системой трёх линейных однородных алгебраическихуравнений относительно трёх неизвестных функций Hk(u) и одной неизвестнойпостоянной ƒ0 (0) .Н а х о ж д е н и е н е и з в е с т н ы х ф у н к ц и й Hk(u)и п о с т о я н н о й ƒ0 (0)Для того чтобы найти значение величины ƒ0 (0) в системе (14), положимu = 0 . При этом в третьем уравнении получаем неопределенность вида 00. Длятого чтобы ее раскрыть воспользуемся правилом Лопиталя, то есть( )1 *( ( )) 1 *( ( ))( ) 1 *( ( )) *lim 1 lim lim 1 1x1 1 x 1 x 1 (0)x A x  A x  A x Aƒ − −ƒ= = = −− ƒ − − ƒ − −ƒ − ƒ − ,где x = e ju . Так как *( ( )) (1 )0A 1x e x ydA(y)ƒ − =  −ƒ − , то* 00 0A (0) ey ( y)dA(y) ydA(y) a  = − =− =− .где а - математическое ожидание продолжительности этапа оповещения о кон-фликте. Тогда( )1 *( ( ))lim 1 1x 1 1x A x aƒ −=− ƒ −.Следовательно, с учётом этих преобразований получаем следующую системутрёх уравнений при u = 0 :{ ( ) }{ }( )*0 1 2* **0 **0 1 2 0 **1 2 0 *(0) ( ) (0) (0)(0) ( ) ( ) ( ) ,( )(0) (0) 2 (0) (0) 1 ( ) ,( )(0) 1 (0) (0) 1 ( ) ,( )H B H HB B BBH H H BBH H Ba B⎧ ƒ − ƒ + ƒ ƒ + ƒ + ƒ + ƒ =⎪⎪ ⎧ ƒ − ƒ + ƒ ⎫= ƒ ƒ − ƒ ƒ + ƒ ⎨ ⎬ ⎪ ƒ ⎩ ⎭ ⎪⎪⎨⎧ − ƒ ⎫⎪− ƒ+ ƒ+ƒ + ƒ=ƒ ⎨ƒ −ƒ⎬ƒ ⎩ ⎭ ⎪⎪⎧ − ƒ ⎫⎪ ƒ + ƒ − = ƒ ⎨ƒ ⎬⎪⎩ ⎩ ƒ ⎭(15)Система (15) является системой трёх алгебраических уравнений относительно ве-личин Hk (0) , значения которых определяются в виде1 00 *(0)(0) ,( ) ( )bHBƒ − ƒ=ƒ + ƒ ƒ + ƒ* [ ]1 0 2 01 *(0) ( ) (0)(0)( ) ( )b B bHBƒ − ƒ − ƒ + ƒ ƒ − ƒ=ƒ + ƒ ƒ + ƒ, (16)* * [ ]3 0 1 0 2 02 *( ) (0) (0) ( ) (0)(0) ( )( ) ( )B b b B bH aB− ƒ + ƒ ƒ + ƒ ƒ − ƒ + ƒ ƒ − ƒ= ƒ+ƒƒ + ƒ ƒ + ƒ,где* **1 *( ) ( ) ( )( )b B B BBƒ − ƒ + ƒ= ƒ − ƒ ƒ + ƒƒ,*2 *1 ( )( )b BB− ƒ= ƒ − ƒƒ,*3 *1 ( )( )b BB− ƒ= ƒƒ.Значение ƒ0 (0) найдём из условия нормировки20k (0) 1kH=ƒ = ,тогда, принимая во внимание (16), получим[ ] { [ ] }[ ] { [ ] }**0 * *2 ( ) ( ) 2 ( )(0) ( )2 ( ) ( ) ( ) 2 ( )a B aBa B B aƒ + ƒ + ƒ − ƒ + ƒ ƒ + ƒ + ƒ + ƒƒ = ƒƒ + ƒ + ƒ ƒ − ƒ + ƒ ƒ + ƒ + ƒ + ƒ. (17)Таким образом, значение величины ƒ0 (0) определяется равенством (17), а изсистемы (14) однозначно определяются значения функций Hk(u). Неоднороднуюсистему линейных алгебраических уравнений (14) перепишем в матричном видеН(u)Q(u) = ƒ0(0)G(u), (18)обозначив Н(u) ={H0(u),H1(u),H2(u)},( ) ( )( )( )( ( ))*2*0( ) 111 1G u B B e B B e B eB B B− −=⎪⎨⎧ƒ ƒ − ƒ+ƒ −ƒ ƒ + ƒ ƒ − ƒ − ƒ ƒ − ƒ⎪⎬⎫⎪⎩ ƒ ƒ ƒ ⎪⎭где ƒ0 (0) определяется равенством (17), тогда решение Н(u) системы (18)1Н(u) = ƒ0(0)G(u)Q− (u).Так как характеристическая функция h(u) =Mejui(t) имеет вид20( ) k( ) ( )kh u H u H u E==ƒ = ,где Е - единичный вектор, тогда распределение вероятностей ƒ(i) числа заявок висточнике повторных вызовов можно записать как( ) 1 ( ) .2i ejuihuduƒ−−ƒƒ =ƒ  (19)Численное интегрирование в (17) при заданных значениях параметров ƒ , ƒ ипреобразованиях Лапласа - Стилтьеса B*(ƒ) и B*(ƒ + ƒ) не представляет трудадля широкого спектра значений i .4. Исследование условия существования стационарного режимаВ силу свойств вероятности должны выполняться неравенства 0< ƒ0(0) ƒ+ƒ ƒ + ƒ+ƒ +ƒТаким образом, из вида этой системы следует, что при выполнении второго нера-венстваƒ[2+a(ƒ+ƒ)]>B*(ƒ+ƒ){ƒ[2+a(ƒ+ƒ)]+ƒ} (20)выполняются также и два остальных.Полученное неравенство (20) является условием существования стационарно-го режима в немарковской модели компьютерной сети связи, управляемой дина-мическим протоколом доступа.5. Численные результатыРассмотрим гамма-распеделения времени обслуживания заявок и продолжи-тельности этапа оповещения о конфликтах заявок. Для гамма-распределения вре-мени обслуживания заявок с параметрами ƒ и ƒ преобразования Лапласа -Стилтьеса B*(ƒ) и B*(ƒ + ƒ) имеют следующий вид:B*( )ƒ ƒ =⎛⎜⎝ƒ +ƒ ƒ⎞⎟⎠,B*( )ƒ ƒ + ƒ =⎛⎜⎝ƒ + ƒƒ + ƒ⎞⎟⎠. (21)Для гамма-распределения продолжительности этапа оповещения о конфликтахзаявок с параметрами ƒ и ƒ преобразование Лапласа - Стилтьесса A*(ƒ(1−eju))запишется как( ( )) ( )* 11juju A eeƒ ƒ − =⎛⎜ ƒ ⎞⎟⎜⎝ƒ + ƒ − ⎟⎠.Значение пропускной способности для данной сети связи будет определятьсяусловием (20), в котором B*(ƒ + ƒ) имеет соответствующий вид (21).Определение. Пропускной способностью сети связи называется точная верх-няя граница S тех значений загрузки ƒ = ƒb , где b - среднее значение времениобслуживания, для которых в математической модели сети существует стацио-нарный режим.Для заданных значений параметров ƒ = 1,5 , ƒ = ƒ = 0,5 , ƒ = ƒ = 0,5 пропуск-ная способность данной системы составляет S = 0,3365 , поэтому значение пара-метра ƒ примем равным, например, ƒ = 0, 25 . Распределение вероятностей ƒ (i)числа заявок в источнике повторных вызовов определяется обратным преобразо-ванием Фурье (19) и приведено в таблице, где также указаны значения величинƒ(i) =ƒ(i+1)/ƒ(i) .Распределение вероятностей ƒ (i) числа заявок в ИПВпри гамма-распределении времени обслуживанияi 0 1 2 3 4 5 6 7 8ƒ(i) 0,5515 0,0358 0,0939 0,0706 0,0550 0,0428 0,0333 0,0259 0,0202ƒ(i) 0,0649 2,6245 0,7517 0,7793 0,7781 0,7784 0,7784 0,7785 0,7785i 9 10 11 12 13 14 15 16 …ƒ(i) 0,0157 0,0122 0,0095 0,0074 0,0058 0,0045 0,0035 0,0027 …ƒ(i) 0,7785 0,7785 0,7785 0,7785 0,7785 0,7785 0,7785 0,7785 …Данное распределение вероятностей ƒ (i) обладает свойством стабилизациипоследовательности отношений ƒ(i) =ƒ(i+1)/ƒ(i) , которое заключается в том,что элементы этой последовательности принимают постоянное значение при i > 2с точностью до двух знаков после запятой. Аналогичные результаты имеют местои для других значений параметров ƒ , ƒ , ƒ и ƒ , ƒ и ƒ .Для аппроксимации распределений вероятностей, обладающих указаннымсвойством стабилизации последовательности ƒ(i) , целесообразно предложитьквазигеометрическое распределение ƒ (i) дефекта n , впервые рассмотренное вработе [16]. Полученное распределение вероятностей дефекта 2 является квази-геометрическим.ЗаключениеТаким образом, в данной статье проведено исследование немарковской моделикомпьютерной сети связи, управляемой динамическим протоколом доступа, в ви-де немарковской динамической RQ-системы с конфликтами заявок и оповещени-ем о конфликте. В результате исследования получена характеристическая функ-ция h(u) числа заявок в источнике повторных вызовов. Равенством (19) опреде-лено распределение вероятностей ƒ (i). В виде (20) найдено условие существова-ния стационарного режима данной RQ-системы.Далее для гамма-распределения времени обслуживания заявок и продолжи-тельности оповещения о конфликтах заявок найдено распределение вероятностейƒ (i) числа заявок в ИПВ. Показано, что распределение вероятностей обладаетсвойством стабилизации последовательности отношений ƒ(i) =ƒ(i+1)/ƒ(i) .Для аппроксимации полученного распределения вероятностей предложеноквазигеометрическое распределение дефекта 2.

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