On relationship ofMC- flows and MAP- flows of events..pdf Математические модели теории массового обслуживания широко применяют-ся при описании реальных физических, технических и других процессов и систем.В связи с бурным развитием компьютерной техники и информационных техноло-гий появилась еще одна важная сфера приложений теории массового обслужива-ния - проектирование и создание информационно-вычислительных сетей, компь-ютерных, спутниковых сетей связи, телекоммуникационных сетей и т.п. Услож-нение структуры информационно-телекоммуникационных систем, интеграцияразличных систем связи, разнообразие программного и аппаратного обеспечения,протоколов передачи данных привели в конце 80-х - начале 90-х годов прошлоговека к созданию цифровых сетей интегрального обслуживания (Integrated ServicesDigital Networks - ISDN). Данные сети характеризуются тем, что по единым аппа-ратным средствам совместно передаются самые разнообразные виды информации- большие массивы данных, речь и видео в цифровой форме, факсимиле и т.д.При этом теория построения математических моделей функционирования инфор-мационно-телекоммуникационных систем, существовавшая до середины 80-х го-дов прошлого века, во многом становится непригодной для анализа информаци-онных процессов, протекающих в ISDN. В связи с этим в это же время была пред-принята успешная попытка создания адекватных математических моделей ин-формационных потоков в телекоммуникационных системах, так называемых два-жды стохастических потоков событий.На практике параметры, определяющие входящий поток событий, известнылибо частично, либо вообще неизвестны, либо (что ещё больше ухудшает ситуа-цию) они изменяются со временем, при этом изменения часто носят случайныйхарактер, последнее и приводит к рассмотрению дважды стохастических потоковсобытий. По-видимому, одной из первых работ в этом направлении явилась ста-тья [1], в которой дважды стохастический поток определяется как поток, интен-сивность которого есть случайный процесс. Дважды стохастические потоки собы-тий можно разделить на два класса: к первому классу относятся потоки, интен-сивность которых есть непрерывный случайный процесс; ко второму классу отно-сятся потоки, интенсивность которых есть кусочно-постоянный случайный про-цесс с конечным числом состояний. Подчеркнем, что потоки второго класса впер-вые введены в рассмотрение практически одновременно в 1979 г. в статьях [2-4].В [2, 3] введённые потоки названы МС (Markov chain)-потоками; в [4] - MVP(Markov versatile processes)-потоками. Отметим, что МС-потоки событий наиболеехарактерны для реальных телекоммуникационных сетей. В свою очередь, в зави-симости от того, каким образом происходит переход из состояния в состояние,МС-потоки можно разделить на три типа:1) синхронные потоки событий - потоки с интенсивностью, для которой пере-ход из состояния в состояние происходит в случайные моменты времени, являю-щиеся моментами наступления событий [5, 6];2) асинхронные потоки событий - потоки с интенсивностью, для которой пе-реход из состояния в состояние происходит в случайные моменты времени и независит от моментов наступления событий [7, 8];3) полусинхронные потоки событий - потоки, у которых для одного множест-ва состояний справедливо определение первого типа, а для остальных состоянийсправедливо определение второго типа [9].Здесь указаны ссылки, в которых авторы впервые рассматривали МС-потокисобытий в соответствии с приведенной классификацией. Наиболее обширная ли-тература по рассматриваемым типам МС-потоков событий приведена в [10-12].Режимы функционирования системы массового обслуживания непосредствен-но зависят от параметров МС-потока и состояний, в которых находится поток.Если система обслуживания функционирует в условиях полной (все параметрыпотока априорно неизвестны) либо частичной (часть параметров потока априорнонеизвестна) неопределенности, то возникает задача оценки параметров потока понаблюдениям за потоком (по наблюдениям за моментами наступления событий)[6, 13, 14]. Что касается состояний МС-потока событий, то даже тогда, когда по-ток функционирует в условиях отсутствия априорной неопределенности (пара-метры потока полностью известны), сказать о том, в каком состоянии находитсяпоток в тот или иной момент времени без наблюдений за потоком, возможнотолько на основании априорных данных. В этом случае возникает задача оценкисостояний потока событий (задача фильтрации интенсивности МС-потока) по на-блюдениям за моментами наступления событий [5, 7-12, 15, 16].Одними из первых работ по оценке состояний МС-потоков событий, по-видимому, являются [7, 8, 17], в которых рассматриваются асинхронные МС-потоки с двумя и произвольным числом состояний, по оценке параметров - рабо-та [18]. Практически все задачи, связанные с оценкой состояний и параметровМС-потоков событий, докладывались на Белорусских школах-семинарах начинаяс 1985 г.Предыдущее изложение связано с МС-потоками событий, которые, как ужеуказывалось, введены в рассмотрение в [2, 3]. Параллельно, начиная с моментавыхода статьи [4] велась интенсивная работа по созданию математических моде-лей так называемых ВМАР (Batch Markovian Arrival Process)-потоков. Централь-ной работой в этом направлении явилась статья [19]. В монографии [20] сконцен-трированы исследования белорусских авторов по системам массового обслужива-ния с BMAP-потоками.В настоящей статье делается попытка установления связи МС-потоков (син-хронных, асинхронных и полусинхронных) с МАР-потоками событий, являющих-ся частным случаем ВМАР-потоков.1. Связь синхронного МС-потока событийс МАР-потоком первого порядкаЧисло состояний МС-потока и МАР-потока событий в дальнейшем изложенииберется равным двум. В соответствии с [20] определение МАР-потока событийвыглядит следующим образом. Имеется поток событий с интенсивностью, пред-ставляющей собой кусочно-постоянный случайный процесс ƒ(t) с двумя состоя-ниями ƒ(t)= ƒ1 либо ƒ(t)=ƒ2 (ƒ1> ƒ2). Процесс ƒ(t) принципиально не наблюдаем.Время пребывания процесса ƒ(t) в i-ом состоянии есть случайная величина с экс-поненциальной функцией распределения ( ) 1 , it 1,2Fi t = −e−ƒ i = . В момент окон-чания i-го состояния процесса ƒ(t) возможны следующие ситуации, каждая из ко-торых происходит мгновенно: 1) процесс ƒ(t) переходит из i-го состояния в i-е, инаступает событие потока в i-м состоянии; совместная вероятность этой ситуации- P (ƒi ƒi, 1) = P1 (ƒi | ƒi), i=1,2; 2) процесс ƒ(t) переходит из i-го состояния в j-е, инаступает событие потока; совместная вероятность этой ситуации - P (ƒi  ƒj, 1) == P1 (ƒj | ƒi) (i, j=1, 2; i≠j); 3)процесс ƒ(t) переходит из i-го состояния в j-е и собы-тие потока не наступает; совместная вероятность этой ситуации - P (ƒi  ƒj, 0) == P0 (ƒj | ƒi) (i, j=1, 2; i≠j). При этом P1 (ƒi | ƒi) + P1 (ƒj | ƒi) + P0 (ƒj | ƒi) = 1; i, j=1, 2;i≠j. Матрица инфинитезимальных коэффициентов имеет блочный вид:1 10 2 1 1 1 1 1 1 1 2 10 12 0 1 2 2 2 1 1 2 2 1 2 2( | ) ( | ) (( || )) (( || )) ,DP P PP PP DD−ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ= =ƒ ƒ ƒ −ƒ ƒ ƒ ƒ ƒ ƒ ƒ (1)матрица D0 описывает ситуацию, когда на полуинтервале [ t, t+ƒt ), где ƒt - доста-точно малая величина, событие потока отсутствует; матрица D1- когда на полуин-тервале [ t, t+ƒt ) наступило событие потока.Сделаем важное замечание. В приведенном определении МАР-потока в явномвиде не оговаривается, в каком состоянии процесса ƒ(t) наступает событие потокапри переходе процесса ƒ(t) из первого (второго) состояния во второе (в первое),так как P1 (ƒj | ƒi) (i, j=1, 2; i≠j) - совместная вероятность перехода процесса ƒ(t) изсостояния i в состояние j и наступления события потока при этом переходе. Дру-гими словами, не оговаривается, что первично: наступление события потока илипереход процесса из состояния i в состояние j.В связи со сделанным замечанием, во-первых, отметим, что в реальных пото-ках событий, моделями которых являются МАР-потоки, событие потока (в мо-мент окончания того или иного состояния процесса ƒ(t)) наступает с полной опре-деленностью в первом либо во втором состояниях процесса ƒ(t), т.е. установленапричинно-следственная связь: первично наступление события потока, вториченпереход процесса ƒ(t) из состояния в состояние либо наоборот. Во-вторых, в зада-чах расчета характеристик потока, например среднего числа событий, наступив-ших в единицу времени в том или ином состоянии процесса ƒ(t), в задачах оценкипараметров МАР-потока событий данное обстоятельство необходимо учитывать,иначе расчеты во многих случаях будут некорректными.Вследствие этого можно выделить четыре вида МАР-потоков событий, кото-рые в дальнейшем будем называть МАР-потоками событий первого порядка иобозначать МАР-1-потоки:1) МАР-поток, в котором в момент окончания того или иного состояния про-цесса ƒ(t) первично наступление события (Event) как в первом, так и во второмсостояниях, вторичен переход из состояния в состояние (обозначение: МАР-1Е);2) МАР-поток, в котором в момент окончания того или иного состояния пер-вичен переход (Tranzition) из состояния в состояние, вторично наступление собы-тия (обозначение: МАР-1Т);3) МАР-поток, в котором в момент окончания первого состояния процесса ƒ(t)первично наступление события, вторичен переход из первого состояния во вто-рое; в момент окончания второго состояния процесса ƒ(t) первичен переход извторого состояния в первое, вторично наступление события (обозначение: МАР-1ЕТ);4) МАР-поток, в котором в момент окончания первого состояния процесса ƒ(t)первичен переход из первого состояния во второе, вторично наступление собы-тия; в момент окончания второго состояния процесса ƒ(t) первично наступлениесобытия, вторичен переход из второго состояния в первое (обозначение: МАР-1ТЕ).Таким оборазом, для МАР-потока первого порядка имеем следующую таблицуклассификации:МАР-1 (МАР-поток событий первого порядка)МАР-1Е МАР-1Т МАР-1ЕТ МАР-1ТЕПодчеркнем, что все четыре вида МАР-потока первого порядка на полуинтер-вале [ t, t+ƒt ) описываются матрицей инфинитезимальных коэффициентов (1).Сделаем еще одно змечание. Можно представитьDs qp pq Ds Ds−ƒ − ƒ ƒ= =−ƒ ƒ − ƒописывающую синхронный поток событий [5, 6, 14, 16]. Так как в синхронномпотоке в момент окончания того или иного состояния процесса ƒ(t) первично на-ступление события потока, а вторичен переход из состояния в состояние, то син-хронный поток есть частный случай потока МАР-1Е.2. Связь асинхронного и полусинхронного потоков событийс МАР-потоком второго порядкаВведем в рассмотрение два МАР-потока первого порядка: МАР(1)-1, МАР(2)-1.Поток МАР(1)-1 описан в разделе 1 и для всех его видов, включая модель МАР(1)-1R, имеет место блочная матрица инфинитезимальных коэффициентов:0 1 10 10 1 1(1) (1) (1)(1) 1 1 2 1 1 1 1 1 2 1 (1) (1)(1) (1) (1)2 1 2 2 2 1 2 2 2 2( | ) ( | ) ( | ),( | ) ( | ) ( | )P P PD DDP P P−ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ= =ƒ ƒ ƒ −ƒ ƒ ƒ ƒ ƒ ƒ ƒ(2)где (1) (1) (1)P1 (ƒi | ƒi) +P1 (ƒj | ƒi) + P0 (ƒj | ƒi) =1; i, j =1, 2; i  j.Поток МАР(2)-1 отличается от потока МАР(1)-1 только тем, что длительностьпребывания процесса ƒ(t) в i-м состоянии есть случайная величина с экспоненци-альной функцией распределения (2)( ) 1 i , 1,2.iF t = −e−ƒ t i= Блочная матрица инфи-нитезимальных коэффициентов для всех вариантов потока МАР(2)-1, аналогичныхвариантам потока МАР(1)-1, при этом имеет вид0 1 10 10 1 1(2) (2) (2)(2) 1 1 2 1 1 1 1 1 2 1 (2) (2)(2) (2) (2)2 1 2 2 2 1 2 2 2 2( | ) ( | ) ( | ),( | ) ( | ) ( | )P P PD DDP P P−ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ ƒ= =ƒ ƒ ƒ −ƒ ƒ ƒ ƒ ƒ ƒ ƒ(3)где (2) (2) (2)P1 (ƒi | ƒi) +P1 (ƒj | ƒi) + P0 (ƒj | ƒi) =1; i, j =1, 2; i  j.Определим МАР-поток второго порядка как суперпозицию (простую сумму)двух МАР-потоков первого порядка: МАР(1)-1 и МАР(2)-1. Так как каждый изуказанных МАР-потоков первого порядка имеет четыре вида, то МАР-потоквторого порядка будет иметь 16 видов. Обозначим поток МАР(k)-1Е черезМАР1(k); поток МАР(k)-1Т через МАР2(k); поток МАР(k)-1ЕТ через МАР3(k); потокМАР(k)-1ТЕ через МАР4(k); k = 1, 2. Каждый вид МАР-потока второго порядкаобозначим парой МАР-потоков первого порядка: (MAPi(1) ,MAP(j2)), i,j =1,4.Тогда все виды МАР-потока второго порядка представимы в виде матрицыМАР-2= ( (1) (2)) 4MAPi ,MAPj 1 . Элемент матрицы МАР-2 соответствуетМАР-потоку второго порядка МАР(i,j)-2=(MAPi(1) ,MAP(j2)), i,j =1,4. Обозначимчерез МАР(1)-1R рандомизированную модель потока МАР(1)-1, в которой рандо-мизированное правило выбора, описанное в разделе 1, определяется вероятно-стями (1)p1 , (1)p2 и (2)p1 , (2)p2 ; через МАР(2)-1R обозначим рандомизированнуюмодель потока МАР(2)-1, в которой рандомизированное правило определяетсяаналогичными вероятностями (1) (1)q1 ,q2 ( (1) (1)q1 +q2 =1 ); (2) (2)q1 ,q2 ( (2) (2)q1 +q2 =1).Тогда рандомизированная модель МАР-потока второго порядка естьсуперпозиция рандомизированных моделей МАР-потоков первого порядка:МАР--2R=(MAP(1)−1R,MAP(2)−1R). Для всех видов МАР-потока второго по-рядка, включая модель МАP-2R, имеет место блочная матрица инфинитези-мальных коэффициентов D(1,2), являющаяся суммой матриц инфинитезимальныхкоэффициентов (2) и (3):0 00 0(1) (2)(1,2) 1 1 1 2 1 1 2 1(1) (2)2 1 2 2 1 2 2 2( ) ( | ) ( | )( | ) ( | ) ( )P PDP P− ƒ + ƒ ƒ ƒ ƒ + ƒ ƒ ƒ=ƒ ƒ ƒ +ƒ ƒ ƒ −ƒ +ƒ1 1 10 11 1 1 1(1) (2) (1) (2)1 1 1 1 1 1 11 2 1 1 2 1 (1,2) (1,2)(1) (2) (1) (2)2 1 2 2 1 2 2 2 2 2 2 2( | ) ( | ) ( | ) ( | ).( | ) ( | ) ( | ) ( | )P P P PD DP P P Pƒ ƒ ƒ +ƒ ƒ ƒ ƒ ƒ ƒ +ƒ ƒ ƒ=ƒ ƒ ƒ +ƒ ƒ ƒ ƒ ƒ ƒ +ƒ ƒ ƒ(4)Положим в матрице (4)(1) (1) (1) (1)P0 (ƒ2 | ƒ1) =P0 (ƒ1 | ƒ2) =P1 (ƒ2 | ƒ1) = P1 (ƒ1 | ƒ2) = 0 ;(1) (1)P1 (ƒ1 | ƒ1) =P1 (ƒ2 | ƒ2) =1;(2) (2) (2) (2)P1 (ƒ1 | ƒ1) =P1 (ƒ2 | ƒ1) = P1 (ƒ1 | ƒ2) = P1 (ƒ2 | ƒ2) = 0 ;(2) (2)P0 (ƒ2 | ƒ1) =P0 (ƒ1 | ƒ2) =1,тогда имеем матрицу( ) 1 1 1 1 ( ) ( )0 12 2 2 2( ) ( )0 0 ,Das Das D as− ƒ + ƒ ƒ ƒ= =ƒ −ƒ +ƒ ƒописывающую асинхронный (asynchronous) поток событий [7, 8, 11, 13, 17, 18],который также носит название ММР (Markov Modulated Poisson) - поток [21]. Дляасинхронного потока в момент окончания первого (второго) состояния процессаƒ(t) возможны следующие варианты дальнейшего поведения процесса ƒ(t): 1) на-ступает событие потока и процесс ƒ(t) с вероятностью единица переходит в пер-вое (второе) состояние; 2) событие потока не наступает и процесс ƒ(t) с вероятно-стью единица переходит во второе (в первое) состояние. Вследствие этого асин-хронный поток есть частный случай потока МАР(1,1)-2 либо потока МАР(1,2)-2.Положим в матрице (4)(1) (1) (1) (1)P0 (ƒ2 | ƒ1) =P0 (ƒ1 | ƒ2) =P1 (ƒ2 | ƒ1) = P1 (ƒ1 | ƒ2) = 0 ;(1) (1)P1 (ƒ1 | ƒ1) =P1 (ƒ2 | ƒ2) =1; (2) (2)P1 (ƒ1 | ƒ1) =P1 (ƒ2 | ƒ2) = 0 ;(2)P0 (ƒ2 | ƒ1) =1−p; (2)P0 (ƒ1 | ƒ2) =1−q; (2)P1 (ƒ2 | ƒ1) =p; (2)P1 (ƒ1 | ƒ2) =q,тогда имеем матрицу( ) 1 1 1 1 1 ( ) ( )0 12 2 2 2 2(1( ) ) ((1 ) ) ,Dgas q p q p Dgas D gas− ƒ + ƒ − ƒ ƒ ƒ= =− ƒ − ƒ +ƒ ƒ ƒописывающую обобщенный (generalized) асинхронный поток событий [10]. Дляобобщенного асинхронного потока в момент окончания первого (второго) состоя-ния процесса ƒ(t) возможны следующие варианты дальнейшего поведения про-цесса ƒ(t): 1) наступает событие потока и процесс ƒ(t) с вероятностью единица пе-реходит в первое (второе) состояние; 2) событие потока не наступает и процессƒ(t) с вероятностью единица переходит во второе (в первое) состояние и с вероят-ностью p во втором состоянии (с вероятностью q в первом состоянии) наступаетсобытие потока; 3) событие потока не наступает и процесс ƒ(t) с вероятностьюединица переходит во второе (в первое) состояние и с вероятностью 1-p событиепотока во втором состоянии (с вероятностью 1-q событие потока в первом со-стоянии) не наступает. Вследствие этого обобщенный асинхронный поток естьчастный случай потока МАР(1,2)-2.Положим в матрице (4)ƒ1= 0, ƒ2= ƒ ; (1) (1) (1)P0 (ƒ2 | ƒ1) =P0 (ƒ1 | ƒ2) = P1 (ƒ1 | ƒ2) = 0 ;(1)P1 (ƒ1 | ƒ1) =1−p, (1)P1 (ƒ2 | ƒ1)=p; (1)P1 (ƒ2 | ƒ2) =1;(2)P0 (ƒ1 | ƒ2) =1, (2)P0 (ƒ2 | ƒ1) =0.Все остальные вероятности (2)P1 () =0. Тогда имеем матрицу( ) 1 1 1 ( ) ( )0 12 2( 0 )(10) ,Dss p p Dss D ss−ƒ − ƒ ƒ= =ƒ − ƒ +ƒ ƒописывающую полусинхронный (semi-synchronous) поток событий [9]. Для полу-синхронного потока в момент окончания первого состояния процесса ƒ(t) воз-можны следующие варианты дальнейшего поведения процесса ƒ(t): 1) наступаетсобытие потока и процесс ƒ(t) с вероятностью 1-p переходит в первое состояние;2) наступает событие потока и процесс ƒ(t) с вероятностью p переходит во второесостояние; в момент окончания второго состояния: 1) наступает событие потока ипроцесс ƒ(t) с вероятностью единица переходит во второе состояние; 2) событиепотока не наступает и процесс ƒ(t) с вероятностью единица переходит в первоесостояние. Вследствие этого полусинхронный поток есть частный случай потокаМАР(1,1)-2 либо потока МАР(1,2)-2.Положим в матрице (4)ƒ1= 0, ƒ2= ƒ ; (1) (1) (1)P0 (ƒ2 | ƒ1) =P0 (ƒ1 | ƒ2) = P1 (ƒ1 | ƒ2) = 0 ;(1)P1 (ƒ1 | ƒ1) =1−p; (1)P1 (ƒ2 | ƒ1)=p; (1)P1 (ƒ2 | ƒ2) =1;(2)P0 (ƒ1 | ƒ2) =1−ƒ; (2)P0 (ƒ2 | ƒ1) =0; (2)P1 (ƒ1 | ƒ2) = ƒ.Все остальные вероятности (2)P1 () =0. Тогда имеем матрицу( ) 1 1 1 ( ) ( )0 12 2(1 ) ( 0 )(1 ) ,Dgss p p Dgss D gss−ƒ − ƒ ƒ= =− ƒ ƒ − ƒ + ƒ ƒƒ ƒописывающую обобщенный полусинхронный поток событий [12]. Для обобщен-ного полусинхронного потока в момент окончания первого состояния процессаƒ(t) дальнейшее поведение последнего аналогично поведению процесса ƒ(t) дляполусинхронного потока. В момент окончания второго состояния процесса ƒ(t)возможны следующие варианты: 1) наступает событие потока и процесс ƒ(t) с ве-роятностью единица переходит во второе состояние; 2) событие потока не насту-пает и процесс ƒ(t) с вероятностью единица переходит в первое состояние, в кото-ром с вероятностью ƒ наступает (с вероятностью 1-ƒ не наступает) событие пото-ка. Вследствие этого обобщенный полусинхронный поток есть частный случайпотока МАР(1,2)-2.ЗаключениеПолученные результаты устанавливают связь асинхронного, полусинхронногои синхронного МС-потоков событий с МАР-потоками событий первого и второгопорядков.Задавая в блочной матрице (1) соответствующим образом вероятности P0() иP1(), получаем блочную матрицу D(s) , определяющую синхронный МС-потоксобытий, т.е. последний является частным случаем МАР-потока первого порядка.Введение в рассмотрение МАР-потоков второго порядка позволяет простымобразом связать асинхронный, обобщенный асинхронный, полусинхронный иобобщенный полусинхронный МС-потоки событий с МАР-потоками второго по-рядка. Задавая в блочной матрице (4) соответствующим образом вероятности( ) ( )P0i() ,P1i(),i=1,2, получаем блочные матрицы D(as), D(gas), D(ss) и D(gss), опре-деляющие отмеченные типы МС-потоков событий, которые вследствие этого яв-ляются частными случаями МАР-потоков событий второго порядка.Наконец, отметим, что рандомизированные модели МАР-потоков первого ивторого порядков охватывают все возможные виды этих потоков.

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