The joint probability density of duration of the intervals in a generalized semisynchronous flow of events with unprolonging dead time.pdf В настоящей статье проводится дальнейшее исследование обобщенного полусинхронного потока событий, функционирующего в условиях непродлевающегося мёртвого времени, начатое в работах [1-5]. Обобщенный полусинхронный поток событий (далее поток) относится к классу дважды стохастических потоков и является одной из адекватных математических моделей информационных потоков заявок, функционирующих в цифровых сетях интегрального обслуживания (ЦСИО) [6]. В реальных ситуациях параметры, задающие входящий поток событий, известны либо частично, либо вообще не известны, либо (что ещё более ухудшает ситуацию) изменяются со временем. Вследствие этого возникают задачи: 1) оценки состояний потока (задача фильтрации интенсивности потока) по наблюдениям за моментами наступления событий [7]; 2) оценки параметров потока по наблюдениям за моментами наступления событий [8]. Одним из искажающих факторов при оценке состояний и параметров потока событий выступает мертвое время регистрирующих приборов [9], которое порождается зарегистрированным событием. Другие же события, наступившие в течение периода мертвого времени, недоступны наблюдению (теряются). Можно считать, что этот период продолжается некоторое фиксированное время (непродлевающееся мёртвое). В качестве примера приведем CSMA/CD - протокол случайного множественного доступа с обнаружением конфликта, широко используемого в компьютерных сетях. В момент регистрации (обнаружения) конфликта на входе некоторого узла сети рассылается сигнал «заглушки» («пробки»); в течение времени рассылки сигнала «заглушки» заявки, поступившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторных вызовов. Здесь время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактовать как мёртвое время прибора, регистрирующего конфликт в узле сети. Для решения задачи оценивания (тем или иным статистическим методом) параметров потока в первую очередь необходимо знание вероятностных свойств потока. В настоящей работе находятся явные виды плотности вероятностей значений длительности интервала между моментами наступления соседних событий потока и совместной плотности вероятностей значений длительности двух соседних интервалов, учитывающие эффект непродлевающегося мертвого времени. 1. Постановка задачи Рассматривается обобщенный полусинхронный поток событий, интенсивность которого есть кусочно-постоянный случайный процесс X(t) с двумя состояниями X1 и X2 > X2). В течение временного интервала, когда X(t) = X,, имеет место пуассоновский поток событий с интенсивностью X,, i = 1,2. Переход из первого состояния процесса X(t) во второе возможен только в момент наступления события, при этом переход осуществляется с вероятностью p (0 < p < 1); с вероятностью 1 - p процесс X(t) остается в первом состоянии. Тогда длительность пребывания процесса X(t) в первом состоянии есть случайная величина с экспоненциальной функцией распределения F1(t) = 1 - е-pXlT. Переход из второго состояния процесса X(t) в первое состояние может осуществляться в произвольный момент времени. При этом длительность пребывания процесса X(t) во втором состоянии распределена по экспоненциальному закону F2 (т) = 1 - е-ат. При переходе процесса X(t) из второго состояния в первое инициируется с вероятностью 5 (0 < 5 < 1) дополнительное событие. При этом блочная матрица инфини-тезимальных коэффициентов примет вид -Х1 0 (1 -5) а -(Х2 +а) (1 - Р)^1 Р^1 5а Х2 N А||. D = Элементами матрицы D1 являются интенсивности переходов процесса X(t) из состояния в состояние с наступлением события. Недиагональные элементы матрицы D0 - интенсивности переходов из состояния в состояние без наступления события. Диагональные элементы матрицы D0 - интенсивности выхода процесса X(t) из своих состояний, взятые с противоположенным знаком. В сделанных предпосылках X(t) - скрытый марковский процесс. После каждого зарегистрированного в момент времени tk события наступает время фиксированной длительности Т (мертвое время), в течение которого другие события исходного потока недоступны наблюдению. События, наступившие в течение мертвого времени, не вызывают продления его периода (непродлевающееся мертвое время). По окончании мертвого времени первое наступившее событие снова создает период мертвого времени Т и т.д. Вариант возникающей ситуации показан на рис. 1, где 1, 2 - состояния случайного процесса X(t); дополнительные события, которые могут наступать в момент перехода процесса X(t) из второго состояния в первое, помечены буквой 5; штриховка - периоды мертвого времени длительности Т; t1, t2,... - моменты наступления событий в наблюдаемом потоке. 1 Л а а а V v 2 Процесс X(t) 5 5 -о-о Обобщенный полусинхронный поток ! T I T I T \ Схема создания непродлевающегося мертвого времени -Оt3 t4 Наблюдаемый поток событий ... t T t t Рис. 1. Формирование наблюдаемого потока событий Подчеркнем, что если 5 = 0, то имеет место обычный полусинхнонный поток событий [10]. Отметим также, что в соответствии с классификацией MAP-потоков событий, приведенной в [11], обобщенный полусинхронный поток относится к классу MAP-потоков событий второго порядка. Заметим, что в определении обобщенного полусинхронного потока событий в явном виде не оговаривается, в каком состоянии процесса X(t) наступает дополнительное событие потока при переходе процесса X(t) из второго состояния в первое. Данное обстоятельство при последующем выводе плотности вероятностей значений длительности интервала между моментами наступления соседних событий потока и совместной плотности вероятностей значений длительности двух соседних интервалов является несущественным, так как наступление дополнительного события и переход процесса X(t) из второго состояния в первое происходят мгновенно. В реальных ситуациях возможны два варианта, связанных с наступлением события и переходом процесса X(t) из второго состояния в первое: 1) первично наступление события во втором состоянии процесса ^(t), затем его переход из второго состояния в первое; 2) первичен переход процесса X(t) из второго состояния в первое, затем наступление события в первом состоянии. В силу этого при получении численных результатов путем имитационного моделирования наблюдаемого потока необходимо учитывать реальную ситуацию. Процесс X(t) и типы событий (события пуассоновских потоков и дополнительные события) являются принципиально ненаблюдаемыми, а наблюдаемыми являются только моменты наступления событий ti, t2,... наблюдаемого потока. Рассматривается установившийся (стационарный) режим функционирования наблюдаемого потока событий. В силу предпосылок последовательность моментов наступления событий t1, t2,... 4,... образует вложенную цепь Маркова, т.е. наблюдаемый поток обладает марковским свойством, если его эволюцию рассматривать с момента tk (момента наступления события), k = 1,2,. . Обозначим тк = tk+1 - tk , k = 1,2,., - значение длительности k-го интервала между соседними событиями наблюдаемого потока. Так как рассматривается стационарный режим, то плотность вероятностей значений длительности k-го интервала pT (тк) = pT (т), т > 0, для любого k (индекс T подчеркивает, что плотность вероятностей зависит от длительности мертвого времени). В силу этого момент tk без потери общности можно положить равным нулю, или, что то же самое, момент наступления события наблюдаемого потока есть т = 0. Пусть теперь (tk, tk+1), (tk+1, tk+2) - два смежных интервала с соответствующими значениями длительностей Tk = tk+1 - tk , Tk+1= tk+2 - tk+1; их расположение на временной оси, в силу стационарности потока, произвольно. Тогда можно положить k = 1 и рассматривать соседние интервалы (t1, t2), (t2, t3) с соответствующими значениями длительностей: т1 = t2 - t1, т2= t3 - t2; т1 > 0, т2 > 0. При этом т1 = 0 соответствует моменту t1 наступления события наблюдаемого потока; т2 = 0 - моменту t2 наступления следующего события наблюдаемого потока. Соответствующая совместная плотность вероятностей при этом есть pT (т1, т2), т1 > 0, т2 > 0. Задача заключается в нахождении явного вида pT (т) и явного вида pT (т1, т2), а также в установлении условий рекуррентности наблюдаемого потока событий и при T = 0 условий рекуррентности обобщенного полусинхронного потока событий. 2. Вывод плотности вероятностей pT (т) Рассмотрим интервал времени (0, т) между соседними событиями в наблюдаемом потоке. С другой стороны, значение длительности этого интервала есть т = T + t, где t - значение длительности интервала между моментом окончания мертвого времени и следующим событием наблюдаемого потока (t > 0). Пусть pjk(t) - условная вероятность того, что на интервале (0, t) нет событий наблюдаемого потока и X(t) = Xk при условии, что в момент t = 0 имеет место Ц0) = lj , j, k = 1,2. Отметим, что переход из первого состояния процесса X(t) во второе возможен только при наступлении события наблюдаемого потока, тогда p12(t) = 0, t > 0. Аналогично обозначим p(t) - условная плотность вероятностей значений длительности интервала (0, t) при условии, что Ц0) = %j , X(t) = Xk , j,k = 1,2. Введем переходную вероятность qij(T) - вероятность того, что за мертвое время длительности T процесс X(t) перейдет из состояния i (момент времени т = 0) в состояние j (момент времени т = T), i, j = 1,2, и вероятность лг(0|Т) - условная (финальная) вероятность того, что процесс Цт) в момент времени т = 0 находится в состоянии i (i = 1, 2) при условии, что в этот момент времени наступило событие наблюдаемого потока и наступило мертвое время длительности T. Тогда искомую плотность вероятностей pT (т) можно записать в виде Г0, 0 0. Тогда условные плотности вероятностей pjk (t) того, что без наступления событий наблюдаемого потока на интервале (0, t) и наступления события наблюдаемого потока в момент времени t процесс k(t) перейдет на этом интервале из состояния j в состояние k (j,k = 1,2), запишутся для разных j и k в виде Pn(t) = (1 - p)k pn(t); P12 (t) = pkPn(t); p 21 (t) = Sap22 (t) + (1 - p )k P21 (t); p22 (t) = k2P22 (t) + PV21(t), t > Для вероятностей pjk(t) справедлива следующая система дифференциальных уравнений: Pn(t) = - Vh(t); P22(t) = -(a + k>)P22 (t); p21(t) = -^1^21(t) + (1 - S)ap22 (t), t > 0, с граничными условиями p11(0) = p22(0) = 1; p21(0) = 0, решая которые находим P11 (t) = ; P22 (t) = a+X2)t; P21 (t) = k (1"5)a Геa+X2)t - 1, t > 0, (3) k - k 2 - a L J где - ^2 - a Ф 0. Подставляя (3) в (2), получаем явный вид плотностей вероятностей pjk(t), j,k = 1,2. Для вероятностей qjr), 0 < т < T, справедливы следующие системы дифференциальных уравнений: quOO = -pkqnOO + aq12(T); ^(т) = pkqnOO -aq12( т); q21 (т) = -Pkq21 (т) + aq22 (т); q'^2 (т) = Pkq21 (т) - aq22 (т), с граничными условиями q11(0) = q22(0) = 1, q12(0) = q21(0) = 0, решая которые, находим (для т = T): qn(T) = щ + a+pk1)T; q12(T) = Щ - ^2e_(a+pk1)T; q21 (T) = щ - щеa+pk1)T; q22 (T) = щ + Щa+Л)Т, (4) q11 (T) + q12(T) = 1, q21 (T) + q22(T) = 1; «1 =a/(a + pk), «2 = Pk /(a + pk). Перейдем к нахождению вероятностей лг(0|7), i =1, 2. Так как моменты наступления событий наблюдаемого потока образуют вложенную цепь Маркова, то для вероятностей лг(0|7) справедливы следующие уравнения: (0| T) = (01T )яп +^2(0| T )Я21; ^2(0 | T) = Я1 (0 | T )Я12 + ^ (0 | T )П22, Я1(0|Г) + ^2(0| T) = 1, (5) где щ- - переходная вероятность того, что за время, которое пройдет от момента времени т = 0 до наступления следующего события наблюдаемого потока, процесс Х(т) перейдет из i-го состояния в j-е (i,j = 1,2). Введем в рассмотрение вероятность p- - переходная вероятность того, что за время, которое пройдет от момента времени t = 0 (момента окончания мертвого времени) до момента наступления следующего события наблюдаемого потока, процесс X(t) перейдет из i-го состояния в j-е (i,j = 1,2). Так как t - произвольный момент времени, то вероятности переходаpij определятся в виде да да да да Р11 = I Pn(t)dt = (1 - p)X J pn(t)dt, P12 = J P12 (t)dt = pX J pn(t)dt, (6) (8) P21 = J p 21 (t )dt = (1 - p)XJ p21 (t )dt + 5a J p22 (t )dt, p22 = J P22 (t)dt = p\ J p21 (t)dt + X2 J p22 (t)dt, где pjk (t) определены в (2),Pjk(t) - в (3). Подставляя (3) в (6), находим a(1 - p + p5) X2 + pa(1 -5) p11 =1- P, p12 = P, p21 =-:-, P22 = --:-; a + X2 a + X2 (7) P11 + P12 = I P21 + P22 =1. В силу марковости процесса X(t) полученные переходные вероятности qij(T) и pij , i,j = 1,2, позволяют выписать выражения для переходных вероятностей п- : = qn(T) P11 + q12(T) P21, ^12 = qn(T) P12+fe(T) P22, Л21 = q21(T) P11 + q22(T) P21, Л22 = q21(T) P12 + q22(T) P22. Подставляя в (8) сначала (4), затем (7), получаем -[X2 - p(X2 +5a)] -(a+pX1)T =1 - p - 1 - e a + X -(a+pX1)T 1 - e Л12 = P +-T"[X2 - P(X2 + 5a)] a + X2 (9) a(1 - p + p5) л1 Л21 = a + X -(a+p-1)T 1 - e Л22 = + [X2 - p(X2 +5a)] 1 - e-(a+pX1)T a + X2 '2 ^ ^ /v,2 X2 + pa(1 - 5) л1 [-2 - p(-2 +5a)] a + X2 a + X2 ^2(01T) = a(1 - p + p5) + л1 [X2 - p(X2 + 5a) 1 - e"(a+Px1)T a + p(X2 + 5a) + [X2 - p(X2 + 5a)] p(a + X2) + тс2 [X2 -p(X2 +5a)] _1 -e"(a+Px1)T ~ 1 -e"(a+px1)T ~ a + p(X2 + 5a) + [X2 - p(X2 + 5a)] 1 -e"(a+px1)T Наконец, подставляя (9) в (5), находим *1(0|T) = (10) где Л1 , п2 определены в (4). Подставляя в (1) сначала (2), затем (3), (4) и (10), проделывая при этом достаточно трудоемкие преобразования и учитывая, что t = т - Т, получаем [0, 0 T, у (T) = 1 - *2 (T) X "XX2 "5а, ^2 (T) = " [ " ^2(01T )]e-( а+pX1)T, \ - X 2 - а * 0, Aj - X 2 - а где п2 определена в (4), п2(0|Т) - в (10). В частности, положив в (11) T =0, получаем формулу для pT (т), приведенную в [3]. 3. Вывод совместной плотности вероятностей pT(ti, т2) Пусть т = T + t(1), т2 = T + t(2) - значения длительностей двух смежных интервалов между моментами наступления последовательных событий наблюдаемого потока. т = 0 - момент наступления первого события, т2 = 0 - момент наступления второго события. В силу того что последовательность моментов наступления событий наблюдаемого потока образует вложенную цепь Маркова, в обозначениях раздела 2 совместная плотность вероятностейpT(ti, т2) примет вид 0, 0 T, Х2 > T, и pT (т) = A,1e"Xl(т~т), т > T, i = 1, 2, т.е. рт (т) = X1e~x1(T~T>, T > T. Для второго условия факторизации Х1(1 - р + р5) - Х1(1 - р) = 0, р Ф 1, вытекающего из (18), плотность вероятностей рт (т) определяется формулой (17), в которой n2(0|T) = р. Для р = 1 из второго условия факторизации вытекает, что 5 = 0. Тогда рт (т) определяется формулой (17), в которой 5 = 0, n2(T) = Х1 +ae_(a+^1)T /(a + A,2). Отметим, что условия факторизации для ситуации T = 0 [3] и ситуации T Ф 0 идентичны. Связав изложенные в особом случае результаты для рекуррентных обобщенных полусинхронных потоков событий, функционирующих в условиях мертвого времени, с результатами для апостериорных вероятностей состояний процесса X(t), приведенных в [2] для особого случая, получим точно такие же выводы относительно близости наблюдаемого рекуррентного потока к пуассоновскому потоку, что и в [3]. Заключение Приведенные результаты делают возможным решение задачи оценки неизвестных параметров, задающих обобщенный полусинхронный поток событий, функционирующий в условиях мертвого времени, по наблюдениям за моментами наступления событий. Рабочими методами оценки параметров при этом могут быть либо метод максимального правдоподобия, либо метод моментов [12]. Полученные явные формулы для плотностей вероятностей рт (т) и рт (т1, т2) позволяют выписать в явном виде либо функцию правдоподобия, либо уравнения моментов.

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