Estimation of the unextendable dead time duration in semi-synchronous events flow of the second order by the method of m.pdf В настоящей работе рассматривается полусинхронный дважды стохастический поток событий второго порядка. Дважды стохастические потоки [1-9], в свою очередь, являются адекватными математическими моделями информационных потоков запросов, функционирующих в телекоммуникационных сетях. Модели дважды стохастических потоков можно классифицировать в зависимости от того, каким образом происходит смена их состояний: синхронные потоки [10]; асинхронные [11]; полусинхронные потоки [12]. Более того, в литературе выделяют два класса дважды стохастичсеких потоков в зависимости от интенсивности потока: 1) интенсивность является непрерывным случайным процессом [4, 5]; 2) интенсивность является кусочно-постоянным случайным процессом [1-3]. Множество состояний вышеприведенных потоков конечно и дискретно. В данной работе число состояний потока полагается равным двум. Поскольку в реальности любому регистрирующему устройству необходимо некоторое время на регистрацию заявки (сообщения), в течение которого устройство не способно регистрировать другие заявки, большую актуальность в настоящее время имеют модели потоков, функционирующих в условиях так называемого мертвого времени. Мертвое время [13, 14] является периодом ненаблюдаемости, вызванным наступлением события, в течение которого другие наступившие события потока недоступны для наблюдения. В этой связи возникает вопрос об оценке среднего числа потерянных событий в единицу времени, который сводится к задаче оценивания длительности мертвого времени. Наступившие в период ненаблюдаемости события могут продлевать или не вызывать продления длительности мертвого времени, поэтому различают модели с продлевающимся и непродлевающимся мертвым временем. В работах [15-19] рассматриваются подобные задачи для различных моделей дважды стохастических потоков событий. В данном исследовании, которое является непосредственным развитием [20, 21], методом моментов решается задача оценивания длительности непродлевающегося мертвого времени в рекуррентном полусинхронном потоке событий второго порядка, проводятся статистические эксперименты. 1. Постановка задачи Рассматривается стационарный режим функционирования полусинхронного потока событий второго порядка (поток), сопровождающий случайный процесс которого X(t) - кусочно-постоянный с двумя состояниями S1 и S2. 82 Оценка длительности непродлевающегося мертвого времени в рекуррентном полусинхронном потоке событий Длительность пребывания процесса Ці) в состоянии Si определяется случайной величиной ^ = min(£(1), £(2)), где £(1) имеет функцию распределения F1(1)(t) = 1 - e~Xlt, t > 0; ^(2) - функцию распределения F\\2\\t) = 1 - e~at, t > 0; £(1) и ^(2) - независимые случайные величины. В момент наступления события потока в зависимости от того, какая из случайных величин \\ (), i = 1, 2, приняла минимальное значение, процесс Ці) переходит из состояния Si в S2 с вероятностью P(г)(Ц I Ц), либо Ці) остается в состоянии Si с вероятностью P1(i)(^1 | Ц), i = 1,2. Здесь Pj(i)(X2 | Ц) + Pj(i)(^j | Ц) = 1, i = 1, 2. Длительность интервала между событиями потока в состоянии Si является случайной величиной с функцией распределения F1(t) = 1 - e~("+a1)t, t > 0 . Длительность пребывания процесса Ці) в состоянии S2 является случайной величиной с функцией распределения F2(t) = 1 - e~а2t, t > 0 . В течение времени пребывания процесса Ці) в состоянии S2 имеет место пуассоновский поток событий с параметром Ц. Далее полагается, что имеет место состояние Si (i -е состояние) процесса Ці), если X(t) = Ц , i = 1, 2; Ц > "2 > 0. Матрицы инфинитезимальных характеристик [22] процесса Ці) имеют вид: D0 = -("+а) с , D1 = Ѵ1(1)(Ц|Ц) + a1P/2)(m"1) Ѵ1(1)(Ц|Ц) + a1P1(2)("2 | "1) ^2 ("2 + ^2) 0 "2 После каждого зарегистрированного в момент времени tk события наступает период мертвого времени фиксированной длительности T, в течение которого следующие события исходного потока являются недоступными для наблюдения. После окончания данного периода первое наступившее событие снова создает период мертвого времени длительности T (непродлевающееся мертвое время) и т.д. Пример возникающей ситуации проиллюстрирован на рис. 1, где ti, І2, ... - моменты наступления событий в наблюдаемом потоке; штриховкой обозначены периоды мертвого времени длительности T; черными кружками обозначены недоступные наблюдению события потока. Рис. 1. Формирование наблюдаемого потока событий Fig. i. Formation of the observed event flow Процесс Ці) - принципиально ненаблюдаем, наблюдаются только моменты наступления событий ti, і2, ..., тогда Ці) является скрытым марковским процессом или ненаблюдаемым сопровождающим марковским процессом. Отметим, что в моменты ti, і2, ..., tk,... последовательность {"(tk)} представляет собой вложенную цепь Маркова. Обозначим %k = tk+1 - tk, k = 1, 2, ..., - значение длительности интервала между соседними событиями в наблюдаемом потоке, (тк) - плотность вероятности значений длительности интервала между соседними событиями наблюдаемого потока. Рассматривается стационарный режим функцио-83 Л.А. Нежельская, ДА. Тумашкина нирования потока, тогда рт(тк) = рт(х) для всех k = 1, 2, х> 0 . Как следствие, момент наступления события потока tk без ограничения общности можно положить равным нулю, т.е. момент наступления события есть х = 0. В силу стационарного режима функционирования потока расположение двух смежных интервалов (tk, tk+1) и (tk+1, tk+2) , к = 1, 2, ..., на временной оси произвольно. Тогда без ограничения общности х = 0 и х2 = 0 можно рассматривать как моменты наступления соседних событий в наблюдаемом потоке. При этом совместную плотность вероятности значений любых смежных интервалов обозначим рт (х1 , х2) , Хі > 0 , Х2 > 0 . Ставится задача оценивания длительности мертвого времени T в рекуррентном полусинхронном потоке событий второго порядка методом моментов. Для решения поставленной задачи необходимо найти явный вид совместной плотности вероятности рт (х1 , х2 ) , Хі > 0 , Х2 > 0 , получить условия рекуррентности потока, а также для каждого из выписанных условий найти явный вид плотности вероятности рг (х) , х> 0, в рекуррентном потоке. 2. Вывод совместной плотности вероятности pT (xj, х 2) Пусть х1 = T +1(1), х2 = T +1(2) - значения длительностей двух смежных интервалов между моментами наступления соседних событий в наблюдаемом потоке, где T - значение длительности мертвого времени, t - значение длительности интервала между моментом окончания периода мертвого времени и моментом наступления очередного события наблюдаемого потока, t(l) > 0, l = 1, 2. Рассмотрим один из двух смежных интервалов, значение длительности которого обозначим х = T +1, t > 0. Введем в рассмотрение переходную вероятность qij (T) того, что за мертвое время длительности T процесс X(t) перейдет из состояния Si в момент времени т = 0 в состояние Sj в момент т = T, i, j = 1,2 ; условную стационарную вероятность *i (01T) того, что процесс X(t) в момент времени т = 0 находится в состоянии Si, i = 1, 2, при условии, что в данный момент времени наступило событие наблюдаемого потока, породив период мертвого времени длительности T; условную вероятность рц (t) того, что на интервале (0, t) нет событий потока, и в момент времени t значение процесса X(t) = Xц при условии, что в момент времени t = 0 значение процесса X(0) = Х;-; рц (t) - соответствующая плотность вероятности, i, j = 1, 2 . В силу того, что последовательность моментов наступления событий ti, t2, ... образует вложенную цепь Маркова |X(tk)}, совместная плотность вероятности рт (хх, х 2) [23] определится в виде: 0, 0 < х1 < T, х2 > 0, (1) рт(Х1,Х2) = ^0, 0 0, Zi=i Щ (0| q,j (Шк=1 Pjk (ъ -7,)Zi=i?fa(7,)Z„=iPOT('t2 -'!')■ -Cl >Т, X 2>T. Явный вид * (01 т), qtj (т), Pjk (х - т), i, j, k = 1, 2, устанавливают следующие леммы [21]. Лемма 1. Переходные вероятности qij (т), i, j = 1, 2, в коррелированном полусинхронном потоке событий второго порядка определяются формулами qn (Г) = * + *2е-(“2+а)т , q12 (т) = *2 - %2е-“2+Я)т , q21 (т) = *1 - *^(“2+а)т , q22 (т) = *2 + а+а)т , (2) где а = XP(1) (Х2 | X) + aiP(2) (X2 I X) ; априорные финальные вероятности состояний Si и S2 равны *1 = а2 / (а2 + а), *2 = а / (а2 + а) соответственно. 84 Оценка длительности непродлевающегося мертвого времени в рекуррентном полусинхронном потоке событий Лемма 2. Плотности вероятностей рj (т), i, j = 1, 2, в коррелированном полусинхронном потоке событий второго порядка имеют вид: Pi j (т) = [k Pi(1)(k j !^i) + aiPi(2)(Xj |Хі)]е -(Xl+“1)т, j = 1,2, р / \\ a2[k1 P1( )(k1 I k0 + a1 P1( 4k1 I ki)]r„-(k2+a2)T -(k+a1)T-| p 21 ( ) /Л X /Л 4 [ ] , (k1 +ai) - (k2 +a2) [е^(k2+a2)т - e-(ki+ai)T] + k2e-(k2+a2)T, T> 0 , P22(t) = ■ (3) a2[k1P/ 4k2 1 ki) + aiP/ \\k2 1 ki)] (k1 +ai) - (k2 +a2) где (k+a) - (k2+a2) ^ 0 . Лемма 3. Условные стационарные вероятности яг- (0 \\ T), i = 1,2, в коррелированном полусинхронном потоке событий второго порядка определяются следующим образом «i(0 \\ T) = (zi - a)(a2 + k2^i(i-e_(“2+a)T))/(^2 - k2(zi -a)e"(a2+a)T), я2(0 \\ T) = 1 -^(0 \\ T), (4) Zi = ki +ai, z2 = k2 +a2 ; л1 и a определены в (2). Теорема 1. Плотность вероятности значений длительности интервала между соседними событиями в коррелированном полусинхронном потоке второго порядка в условиях наличия мертвого времени для случая (k + a) - (k2 + a2) ^ 0 имеет вид ІО, 0-(ki+ai)T, j = 1,2, (7) P21 (t) = a2[kiPi(1)(ki I ki) +aiPi(2)(ki |ki)]Te-(ki+ai)T , P22(t) = a 2[k1P1(1)(k 2 I k1) + a1P1(2) (k 2 I k1)]Te ~(ki+ai)T+k 2е ~(ki+ai)T , t> 0 . Теорема 3. Плотность вероятности значений длительности интервала между соседними событиями в коррелированном полусинхронном потоке второго порядка в условиях наличия мертвого времени для случая (k1 + a1) - (k2 + a2) = 0 определяется следующим образом: 85 Л.А. Нежельская, ДА. Тумашкина Рт (х) 0, 0 < х < T, [(К + аі) -а 2 п2(Т)(\\ - (К + аі)(х - T))] е-("1+“і)(х-т\\ х > T, (8) %2(т) = %2 1 + аа2 (Кі +аі)2 е(а2 + а)т - К2 (Кі +аі - a) j где % 2 и a определены в (2) [21]. На основании лемм 1, 4, теоремы 3 сформулируем следующую теорему. Теорема 4. Полусинхронный поток событий второго порядка является коррелированным и совместная плотность вероятности значений длительностей смежных интервалов для случая (Кі + аі) - (К2 + а2) = 0 имеет вид: Рт(Чх2) = p 0 т , где zi = Хі + ai, z2 = Х2 + a2; 2) K2 = 0, получим рт (х) = у(т)Zje^1*-х-т) + (і -у(т))г2е2(х-т),х > т, где zi = Xi + ai,, Z2 = a2; 3) у(т) = 0, получим плотность для простейшего потока рт (х) = z2e~z2(х-т),х > т , где Z2 = Х2 + a2; 4) і-у(т) = 0, получим плотность для простейшего потока рт (х) = ^(х-т),х > т, где zi = Хі + ai. В свою очередь, для особого случая Кі + аі = К2 + а2 задания параметров потока, анализируя (9), аналогичным образом находим, что совместная плотность факторизуется рт (хі, х2) = рт (хі) рт (х2), если: i') z - а = 0, получим рт (х) = [ z -а2 %2(т )(і - г(х- т ))]e_z (х-т), х> т , где z = К1+а1; 2') К2 = 0, получим рт(х) = z[1 -%2(т)(і-z(х-т))]e_z(х-т),х>т , где z = К1+а1; 3') %(т) = 0, получим плотность для простейшего потока рт (х) = ze~z(х-т),х > т, где z = К + а. Ставится задача оценивания длительности мертвого времени T для рекуррентного потока при выполнении условий 1 и 2 в общем случае задания параметров, а также для условий 1' и 2' в особом случае задания параметров потока. 4. Оценивание длительности мертвого времени в рекуррентном потоке методом моментов Пусть хк = tk+і - tk - значение длительности интервала между моментами tk и (к+і, к = і, 2, ..., п, наступления событий в наблюдаемом потоке. Введем статистику C = (і/n)^”_іх4: , 86 Оценка длительности непродлевающегося мертвого времени в рекуррентном полусинхронном потоке событий да MT (т) = J xpT (x)dх - начальный теоретический момент первого порядка. Тогда в соответствии с мето- T дом моментов [24] уравнение моментов для определения неизвестного параметра T запишется в виде: МТ (т) = C . (10) В общем случае задания параметров потока с учетом плотности, определенной для условий 1 и 2 рекурретности потока, уравнение (10) будет иметь вид: y(T)(1 / z -1/z2) + T +1/z2 = C, (11) где zi, Z2 принимают значения, соответствующие выписанным условиям 1 и 2. Утверждение 1. Уравнение моментов (11) для условий рекуррентности 1 и 2 имеет единственное решение. В свою очередь, уравнение (10) для особого случая задания параметров потока с учетом плотности, определенной для условий 1' и 2' рекурретности потока, запишется в виде: а2тс2 (T)/ z2 + T +1/z = C, (12) где %2(T) = л2(1 + а / (ze(a+а)T )) для условия 1'; %2(T) = л2(1 + а / (а2е(а2+a)T )) для условия 2'. Утверждение 2. Уравнение моментов (12) для условий рекуррентности 1' и 2' имеет единственное решение. Доказательство утверждений 1 и 2 проводится аналогичным путем, приведенным в работе [21]. Полученные уравнения моментов (11) и (12) относительно неизвестного параметра T решаются только с привлечением численных методов. 5. Вероятностные характеристики потока Поскольку теоремы 2 и 4 доказывают, что поток является коррелированным, рассмотрим следующие вероятностные характеристики. Для общего случая задания параметров потока при T = 0 ковариация и коэффициент корреляции имеют вид: cov(x1,Х2) = 7(1 -у)(1 - а/zx)(X2/Z2)(1/zl -1/Z2)2, X ,х2 =7(1 -7)(1 - а / z^(X 2/z2)(1/Z1 -1/z2)2 {-у 2(1/Z1 -1/z2)2 + 27(1/Z12 -1/^2))+1/z22 f1. В особом случае задания параметров потока ковариация и коэффициент корреляции при T = 0 определяются выражениями cov(xj, х 2) = -X 2 а 22(z - а)п 22(0)/z б, X ,х2 = -X 2а 22(z - а)^22(0)/z 6 {-а 2^(0)/z 4 + 2а 2^(0)/z3 +1/z 2 fl. При T Ф 0 ковариация и коэффициент корреляции для общего случая параметров имеют вид: COVT (хь Х2) = y(T)(1 -y(T))(1 - а / z)(X 2/z2)1 zr -1/Z2)2 e “(а2+^T, V2 T) = y(T )(1 -y(T))(1 - а / zt)(X 2/Z2)(1/Z! -1/Z2)2 e x x{- у(T)2 (1 / Z1 -1 / Z2)2 + 2y(T)(1 / Zj2 -1 /(Z1Z2))+1 / Z22 f1, и для особого случая задания параметров потока: 2 (Т\\ д-(а2+а)T / z 6 COvT (х1, х2) = -X2а22 (z - а)л22 (T)e X,хг(T) =-X2а22(z-а)%22(T)e~(ai+а)Т /z6{-а22^2(T)/z4 + 2а2^2(Г)/z3 +1/z2f1. Отметим, что для рекуррентного потока как в общем случае задания параметроа потока X + а ^ Х2 + а, так и в особом случае X + а = X + а при полной наблюдаемости потока имеем 87 Л.А. Нежельская, ДА. Тумашкина cov(Tj, т2) = 0, г = 0; при наличии непродлевающегося мертвого времени фиксированной длительности T имеем covr(xj, т2) = 0, г т (Т) = 0. 6. Результаты статистических экспериментов Оценка длительности мертвого времени T производится по следующему алгоритму. Обозначим f (Т) = Мт (Т). В качестве оценки параметра T выбирается решение (11) / (12) (в зависимости от задания параметров потока) на полуинтервале (0, тmin], где Tmin = min(Tk), к = 1, 2, ..., n;; если f (0) < C < f (Tmin), то Т numeric = Т; если f (0) < f (Tmin) ^ C, то Tnumeric =Tmin; f (0) ^ C, то Tnumeric = 0 где Т numeric - численное решение уравнения (11) / (12) методом Ньютона. Стоит отметить, что применение т mil дает улучшенную оценку параметра T. Для проверки качества оценивания длительности мертвого времени с использованием построенной имитационной модели полусинхронного потока событий второго порядка проведена серия статистических экспериментов [25]. По алгоритму, приведенному выше, находится выборка оценок Т1, Т2, ..., Т N для N реализаций потока и вычисляются выборочное среднее M(T) = (1/ N)^^ Т , выборочная вариация V(T) = 1 / Nj (Т - Т)2 и оценка смещения 5(Т) = |M(T) - т| для конкретного эксперимента. Цель первого статистического эскперимента - проверка установления стационарного режима в случае выполнения первого условия рекуррентности в общем случае задания параметров потока. В соответствии с условием рекуррентности положим Д(1)(Я2 ІМ = Д(2)(Я2 |Хі) = 1, Рі(1)(Хі|^) = д(2)(^1^1) = 0 . При параметрах потока ^ = 5, ^ = 2, аі = 3, а2 = 1, T = 1,5 и N = 300 рассмотрим следующие значения времени моделирования: Tm = 50, 100, ..., 1 000 ед. времени c шагом 50. В табл. 1 приведены численные результаты данного эксперимента. Таблица 1 Результаты первого статического эксперимента T 50 100 150 700 750 950 1 000 M (T) 1,2095 1,2748 1,3067 1,4905 1,4906 1,4904 1,4905 8(Т) 0,2905 0,2252 0,1933 0,0095 0,0094 0,0096 0,0095 V (T) х 10-5 24,4841 20,0012 18,1038 1,7731 1,5871 1,1742 1,8421 Целью второго статистического эксперимента является установление зависимости M (T), V (T) от количества реализаций N (N = 50, 100, ..., 500 c шагом 50) при заданных значениях параметра мертвого времени T (T = 0,2; 0,5; 1; 1,5; 2), а также проверка качества оценивания при увеличении периода ненаблюдаемости при выполнении второго условия рекуррентности для особого случая задания параметров потока. В соответствии с условием рекуррентности положим ^ = 0, Р(1) (\\ ) = Р(2) (Х2) = 0,4, р(1) (Х2) = р(2) (\\ |Xj) = 0,6, а также h = 7, ш = 1, а2 = 8. Т а блица 2 Результаты второго статического эксперимента N 50 100 150 200 250 300 350 400 450 500 T = 0,2 M (T) 0,1980 0,1986 0,1988 0,1988 0,1988 0,1989 0,1990 0,1989 0,1989 0,1988 V (T) х10-5 1,0179 0,3475 0,3815 0,2157 0,2874 0,2904 0,3111 0,3199 0,2894 0,2971 88 Оценка длительности непродлевающегося мертвого времени в рекуррентном полусинхронном потоке событий Окончание табл. 2 N 50 100 150 200 250 300 350 400 450 500 T = 0,5 Ml (T) 0,5033 0,5026 0,5024 0,5028 0,5021 0,5021 0,5024 0,5024 0,5022 0,5022 V ( Т) х10~5 1,5980 0,7159 0,6791 0,6105 0,6817 0,6587 0,6454 0,6971 0,6587 0,6621 T = 1 Mi ( t ) 0,9913 0,9928 0,9918 0,9920 0,9928 0,9930 0,9931 0,9932 0,9930 0,9931 V (Т) х 10~5 3,5483 2,1713 1,9971 1,6105 1,5157 0,9387 0,9689 0,9189 0,9541 0,8917 T = 1,5 M (Т) 1,4876 1,4880 1,4881 1,4887 1,4891 1,4897 1,4892 1,4896 1,4897 1,4896 V ( Т) х 10~5 5,7781 3,7421 3,1154 2,9715 2,4718 2,1741 2,2154 2,2089 2,2541 2,3517 T = 2 M (т) 1,9602 1,9612 1,9621 1,9618 1,9625 1,9629 1,9632 1,9630 1,9630 1,9631 V ( Т) х 10~5 7,4887 5,3872 5,0082 4,9700 4,8176 4,5813 4,1984 4,3489 4,1579 3,9947 Проводя анализ полученных в табл. 1 и 2 численных результатов, можно сделать следующие выводы: 1) найденная оценка является состоятельной [24] и смещенной, при этом наблюдения показывают достаточно приемлемую величину смещения; 2) оценка ухудшается (в смысле увеличения выборочной вариации) с увеличением T, что является естественным в силу большей потери событий (информации); 3) отмечается установление стационарного режима для Тт > 700 (табл. 1); 4) количество экспериментов коррелирует со значением мертвого времени T (табл. 2): для достаточно малого значения T результаты стабилизируются при N = 100, однако при увеличении T для получения более стабильных результатов необходимо увеличить количество реализаций и положить N = 300. Заключение В настоящей работе рассмотрен полусинхронный поток событий второго порядка в условиях наличия непродлевающегося мертвого времени фиксированной длительности T. В ходе исследования потока было выявлено два случая задания параметров потока: общий и особый. Для обоих случаев задания параметров потока путем вывода совместной плотности вероятности значений длительностей смежных интервалов доказано, что рассматриваемый поток является коррелированым. В этой связи найдены такие вероятностные характеристики потока, как ковариация и коэффициент корреляции, а также сформулированы условия, при которых поток является рекуррентым. Для рекуррентного потока решена задача оценивания длительности мертвого времени с применением численного метода для решения уравнения моментов относительно неизвестного параметра T. Алгоритм вычисления оценок длительности мертвого времени запрограммирован на языке С# в среде Visual Studio 2013. С целью проверки качества полученных оценок проведена серия статистических экспериментов с помощью имитационной модели потока; численные результаты реализованных экспериментов демонстрируют приемлемое качество оценивания.

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