Maxumum likelihood estimator of dead time duration in modulated synchronous twice stochastic flow of events.pdf Настоящая работа является непосредственным продолжением исследований модулированного синхронного потока событий, начатых в статьях [1-4]. Математические модели систем массового обслуживания широко применяются при описании реальных физических, технических и других процессов и систем. В связи с бурным развитием компьютерной техники и информационных технологий появилась важная сфера приложений теории массового обслуживания - проектирование и создание информационно-вычислительных сетей, компьютерных сетей связи, спутниковых сетей, телекоммуникационных сетей, объединенных термином «цифровые сети интегрального обслуживания» (ЦСИО) [5, 6]. На практике параметры, определяющие входящий поток событий, изменяются со временем, при этом изменения часто носят случайный характер, последнее приводит к рассмотрению дважды стохастических потоков событий. По-видимому, одной из первых работ в этом направлении явилась статья [7], в которой дважды стохастический поток определяется как поток, интенсивность которого есть случайный процесс. Дважды стохастические потоки можно разделить на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму классу относятся потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным числом состояний. Подчеркнем, что потоки второго класса впервые введены в рассмотрение практически одновременно в 1979 г. в [8, 9]. В [8] введенные потоки названы MC (Markov сЬат)-потоками; в [9] - MVP (Markov versatile processes)-потоками. Отечественные и зарубежные авторы в своих работах, начиная с начала 1990-х гг. [10-15], называют введенные в [8, 9] потоки событий либо дважды стохастическими потоками событий, либо MAP-потоками, либо MC-потоками. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, MC-потоки можно разделить на три типа: 1) синхронные потоки событий [16-21]; 2) асинхронные и обобщенные асинхронные потоки событий [22-27]; 3) полусинхронные и обобщенные полусинхронные потоки событий [28-33]. В [34] введены в рассмотрение MAP-потоки событий первого порядка (собственно MAP-потоки, введенные в [9]) и MAP-потоки событий второго порядка (суперпозиция двух синхронизированных MAP-потоков первого порядка, отличающихся друг от друга исходными параметрами). В [34] показывается, что синхронный MC-поток является частным случаем MAP-потока первого порядка, асинхронный и полусинхронный MC-потоки являются частными случаями MAP-потока второго порядка. В реальных ситуациях параметры, задающие входящий поток событий, известны либо частично, либо вообще неизвестны, либо (что еще более ухудшает ситуацию) изменяются со временем. Вследствие этого возникают задачи: 1) оценки состояний потока (задача фильтрации интенсивности потока) по наблюдениям за моментами наступления событий [24, 27, 29, 33, 35-38]; 2) оценка параметров потока по наблюдениям за моментами наступления событий [16-22, 26, 28, 30-32]. Одним из искажающих факторов при оценке состояний и параметров потока событий выступает мертвое время регистрирующих приборов [39-46], которое порождается зарегистрированным событием. Другие же события, наступившие в течение периода мертвого времени, недоступны наблюдению (теряются). Можно считать, что этот период продолжается некоторое фиксированное время (непродле-вающееся мертвое время). В качестве примера приведем протокол CSMA/CD - протокол случайного множественного доступа с обнаружением конфликта, широко используемый в компьютерных сетях. В момент регистрации (обнаружения) конфликта на входе некоторого узла сети по сети рассылается сигнал «заглушки» («пробки»); в течение времени рассылки сигнала «заглушки» заявки, поступившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторных вызовов. Здесь время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактовать как мертвое время прибора, регистрирующего конфликт в узле сети. Для того чтобы оценить потери заявок в узле сети, необходимо оценить длительность мертвого времени, которым выступает в данном случае длительность сигнала «заглушки». В работах [1-4] введен в рассмотрение модулированный синхронный поток событий, являющийся обобщением синхронного потока и относящийся к классу MAP-потоков второго порядка. Синхронный поток событий систематически исследовался в работах [16-21, 47-52]. В настоящей статье, являющейся непосредственным развитием работ [1-4], для решения задачи оценивания длительности мертвого времени применяется метод максимального правдоподобия [53-59], так как оценки, построенные при использовании данного метода, как правило, обладают привлекательными свойствами. 1. Постановка задачи Рассматривается модулированный синхронный поток событий (далее поток), интенсивность которого есть кусочно-постоянный стационарный случайный процесс A(t) с двумя состояниями: Ax, A2 (A > A2 > 0). Длительность пребывания процесса A(t) (потока) в i-м состоянии распределена по экспоненциальному закону с параметром ai, i = 1,2 . Если процесс A(t) в момент времени t находится в i-м состоянии, то на полуинтервале [t, t + At), где At - достаточно малая величина, с вероятностью a iAt + o(At) пребывание процесса A(t) в i-м состоянии закончится и процесс A(t) с вероятностью, равной единице, перейдет из i-го состояния в j-е (i, j = 1,2, i Ф j). В течение временного интервала случайной длительности, когда A(t) = A i, имеет место пуассоновский поток событий с интенсивностью ai, i = 1,2. Кроме того, переход из первого состояния процесса A(t) во второе возможен в момент наступления события пуассоновского потока интенсивности A1; переход осуществляется с вероятностью p (0 T, (1) Y(T) =---(z2 - A 1П1(Т) - A 2 П 2(T)), Z 2 z1 z1 = (a1 + A1 + a2 + A2 (a1 + A1 - a2 - A2)2 + 4a1a2, z2 = (aj + A,1 +a2 + А2) + (aj +Л,1 -a2 -А2)2 + 4^а2, z1 < z2, %l(T) = ^ - (я1 - я1(0| T))е-(а1+а2+pX1+qX2)T, %2(Т) = л2 - (я2 - я2(0| Т))е-(а1+а2++qX2)T, a 2 + qA 2 a1 + pA1 _ _ь2 ' 4^2_ _ п1 =-, п2 = 12 a1 + pA1 + a 2 + qA 2 a1 + pA1 + a 2 + qA 2 Пусть Tj = t2 - t1, т2 = t3 -t2,..., Tk = tk+1 - tk, k = 1,2,..., - последовательность измеренных в результате наблюдения за потоком на интервале наблюдения (0,t) значений длительностей интервалов между соседними событиями наблюдаемого потока. Упорядочим величины т1, т2,...,тk по возрастанию: тmin = т(1) < т(2) < ... < т(k). Тогда функция правдоподобия, с учетом (1), примет вид L(y,А,а;,p,q,T|T(1),.,т(k}) = 0 < Vm 0, где С определена в (4); в1, в2, Р1, Р2, Р определены в (3); z1, z2 определены в (1). Нетрудно показать, что X(т m) > 0 для т m > 0 . Последнее означает, что знак производной p '(т m) определяется множителем (в1 Р1 - в 2Р2) . Рассмотрим p'(тm) как функцию тm (тm > 0). Имеем p '(тm = 0) = (С / A2 > 0; p '(тm = м) = lim p'(тm ) = С /(в1 + в 2) > 0 . Знак разности p '(т m = 0) - p'(т m = м) = С (A 1 - A 2)(в1 Р1 - в 2 Р2)/( A 2(в1 + в 2)) определяется знаком множителя (в1 Р1 - в 2Р2) : если (в1 Р1 - в 2 Р2) > 0, то p '(т m = 0) > p'(т m = м); если (в1 Р1 - в 2 Р2) < 0, то p '(тm = 0) < p'(тm = м) ; если (в1 Pj - в 2Р2) = 0, то p '(тm = 0) = p'(тm = м) . Из вида производной p '(т m) следует, что в случае, когда (в1 Р1 - в 2Р2) > 0, функция p '(т m) > 0, т.е. функция pT (тm) есть возрастающая функция переменной Т в точке Т = тm (тm > 0). Случай (в1 Р1 - в2Р2) < 0 требует отдельного рассмотрения. Для этого исследуем вторую производную p''(тm) функции p^m). Производная p''(тm), с учетом (8), примет вид е-(р1 + р2) t„ p ''(Tm ) = -(А - А 2)(PjPj -Р2 Р2) zjz2 Y (т.), F (Tm ) (9) Y(т. ) = {c + (zj + z2)P - (zj + z2 +P1 +P2)Pe"(p1+p2)tm }, т. > 0, где С определена в (4); в1, в2, Р1, Р2, Р, F(Т = тm) определены в (3); z1, z2 определены в (1). Так как рассматривается случай (в1 Р1 - в 2 Р2) < 0, то множитель в (9) - (A1 - A2)(в1 Р1 - в2Р2)z1 z2е-(в+в2)т" / F3(тm) > 0; тогда знак производной p''(тm) определяется знаком выражения Y(т.). Исследуем функцию Y(т.). Имеем Y(м) = С + (z1 + z2)Р > 0, Y(0) = С - Р(в1 + в2), при этом Y(0) > 0, либо Y(0) < 0 , либо Y(0) = 0 . Производная Y'(т m) примет вид Y'(тm ) = (в1 + в 2 )(zj + z2 + в1 + в 2)Ре-(в1 +в2)т" , тm > 0. Знак производной Y'(тm) зависит от множителя Р: 1) если Р < 0, то Y'(тm) < 0 (тm > 0) и тогда p''(тm) > 0 (тm > 0); 2) если Р = 0, то Y^.) = С > 0 (т. > 0) и тогда p''(т.) > 0 (т. > 0); 3) если Р > 0, то Y '(т m ) > 0 ( т m > 0) и тогда p"(T„ ) > 0, либо p''^ m ) < 0, либо p''^ m ) = 0 ( т . > 0 ). Для первых двух случаев производная p' (т.) > 0 (т. > 0). Если реализуется третий случай, то возможны варианты поведения функции p'(T.) (т. > 0): а) если Y(0) = С -Р(в1 + в2) > 0, то p''^ m) > 0 (т m > 0); тогда p '(т.) > 0 (т. > 0); б) если Y (0) = С - Р(в j + в 2) = 0, то p''^.) = 0 (т. = 0), p''^ m) > 0( т m > 0); тогда p' (т.) > 0 (т. > 0); в) если Y (0) = С - Р^ + в 2) < 0, то поведение p''^.) определяется тремя ситуациями: 1) 0 < тm < т., тогда p'' (тm) < 0; 2) тm = т. , тогда p'' (тm) = 0; 3) тm < тm , тогда p"(тm ) > 0. Таким образом, при реализации варианта Y(0) = С - Р(в1 + в2) < 0 производная p' (тm) (тm > 0) достигает своего глобального минимума в точке т m = т. . При этом точка т. определяется выражением т. =--^ln z1 z2(z1 + z2 -Pj -P2) , Р > 0. (10) . Pj +P2 (zj + z2 +Pj + P2) Р Подставляя (10) в (8), находим выражение для производной p' (т m) в точке минимума т m = т. : ^ ) ^РТ^ iC + ^ " ^ 2)(Р1^1 -Р2 ^2)( 21 ^^ } P > 0 (11) Можно показать, что производная, определяемая в (11), строго больше нуля (р'(т*т) > О, P > 0). Отсюда следует, что при реализации варианта Y(0) = C - P(P1 + Р2) < 0 выполняется р'(тт) > 0 (тт > 0) . Лемма 2 доказана. Далее изучим поведение производной pT (т m) как функции переменной T на интервале (0, т m ) . Рассмотрим на предмет существования корней уравнение pT (тm) = 0, которое, с учетом (3), преобразуется в выражение Ч(Т) = e-(z2"z1)(xm\Ч(Т) = , 0 0. Обозначим h = 1 - p - q, тогда P = X2h . Величину (X1 - X 2)(Р1 P1 - Р 2P2) представим в виде (А -AjXM -P2P2) = -(^1^2)2 h2 + V2 [2^2 - (Р1 +P2)(z1 + z2)] h - (13) -z1 z2 (z1 -P1 -P2 )(z2 -P1 -P2) = x(h), - 1 < h < 1. Функция (13) достигает нуля в точках h = h1 и h = h2; h1 = z 2( z1 - P1 - P 2)/ X1X 2, h2 = z1(z2 - P1 - P2)/X1X2 , h1 < h2 . Исследуем функцию F1 (T), T > 0 , из (12) и определенную в (3). Лемма 3. Функция F1 (T) > 0 при T > 0 . Доказательство. Имеем F1 (0) = z1 (P1 +P 2)(z2 A - C)C / A 2 > 0, F1(m) = lim F1(T) = z1(z2 A - C) > 0, T ^да так как(z2A - C) > 0 (лемма 1). Тогда (z2 A - C) = X1X 2 z1 (h - h1) > 0 . Отсюда следует, что всегда h > h1. Для дальнейшего исследования F1 (T) на знак представим ее как функцию, зависящую от параметра h (F1(T) = F1(T, h)): F1(T, h) = z1 [(P1 +P2) z1z2 - zf(T, h) - f '(T, h)], T > 0, -1 < h < 1, (14) e-(p1+p2 )T e-(p1+p2)T f (T,h) = A + x(h) , f '(T,h) = -z1 z2(P1 + P2)x(h)- , F (T ,h) F (T , h) где x(h) определена в (13); A - в (4); Р1, P2; F(T, h) - в (3); z1, z2 - в (1). Знак функции F1 (T, h) зависит от знака функции x(h). Рассмотрим все возможные варианты. Пусть x(h) = 0 . Это возможно, как следует из (13), если h = h1 либо h = h2. Так как всегда h > h1, то случай h = h1 исключается. Тогда для случая h = h2 имеем F1(T, h = h2) = z12(z2 - z1)(P1 + P2) > 0, T > 0 . Пусть x(h) > 0. Последнее возможно, если реализуется один из следующих вариантов: 0 < h1 < h < h2 ; 0 = h1 < h < h2 ; h1 < 0 < h < h2 ; h1 < h = 0 < h2 ; h1 < h < 0 < h2 ; h1 < h < h2 = 0 ; h1 < h < h2 < 0 . Рассмотрим вариант 0 < h1 < h < h2. Имеем ^ = z2z2(P1 +X(he^ | z2(«1 -P1 -P2)-А1А2(,1 +P1 +P2)he-T J (15) Т > 0,0 < h < h < h2. Знак производной (15) определяется знаком функции: y,(T,h) = z1z2(z1 -р1 -р2) -A1X2(z1 +Р1 +P2)he"(p1+р2)Т, Т > 0, 0 0, функция (15) - возрастающая функция переменной Т (возрастает от y1(T = 0, h) = z1 z2(z1 -Р1 -Р 2) - X,X 2(z1 +Р1 +Р 2)h до y1(T = м) = z1 z2(z1 - в, - в 2) > 0). Тогда y, (Т = 0, h) < 0 для 0 < h1 < h < h2. Отсюда следует, что функция (16) проходит через ноль в точке T1(h) =--1-ln ziz2(zi-Р1 -Р2) , 0 F1(T = м, h), 0 < h1 < h < h2 . Покажем, что в точке Т = T1(h) функция F1 (Т, h) строго больше нуля (F1(T = Т1,h) > 0, 0 < h1 < h < h2 ). Имеем Fi(T =Ti(h),h) = zi {(Xi^2)2(zi +Р1 +Р2)2h2 -X^zi -Р1 -Р2)[zi(zi -Р1 -Р2)(z2 -Р1 -Р2) + (17) +z2(zi +Р1 +Р2)2] h + ziz2(zi -Р1 - Р2)3(z2 -Р1 - Р2)}, 0 0, Т > 0, для оставшихся вариантов, реализующихся для x(h) > 0 . Пусть x(h) < 0 . Это возможно, если реализуется один из следующих вариантов: 0 < h1 < h2 < h < 1; 0 = h1 < h2 < h < 1; h1 < 0 < h2 < h < 1; h1 < h2 = 0 < h < 1; h1 < h2 < 0 < h < 1; h1 < h2 < h = 0; h1 < h2 < h < 0. Используя формулы (15)-(17), показывается, что для всех приведенных вариантов функция F1 (Т, h) > 0, Т > 0, h > h2 . Лемма 3 доказана. Перейдем к рассмотрению функции F2 (Т), Т > 0 , из (12) и определенной в (3). Лемма 4. 1) Функция F2(T) = 0 (Т > 0 ), если x(h) = 0 ; 2) функция F2(T) < 0 (Т > 0 ), если x(h) > 0 . Доказательство. Имеем F2(0) = X,X 2 z22(Р1 + Р 2)(h - h2)C / Л 2, F2(м) = lim F2(T) = X, X 2 z22(h - h2). Т -^м Для дальнейшего исследования функции F2 (Т) на знак представим ее как функцию, зависящую от параметра h (F2 (Т) = F2 (Т, h)): F2 (Т, h) = z2 [(Pi + в2)zi z2 - z2 f (T, h) - f' (T, h)], T > 0, -1 < h < 1, (18) где f (T,h), f '(T,h) определены в (14). Знак функции F2(T, h) зависит от знака функции x(h), определенной в (13). Пусть x(h) = 0 . Это возможно, как следует из (13), если h = h1 либо h = h2. Так как всегда h > h1 (лемма 3), то случай h = h1 исключается. Тогда для случая h = h2, подставляя h2 в (18), имеем F2(T, h = h2) = 0, Т > 0 . Пусть x(h) > 0. Неравенство выполняется, если реализуется один из вариантов, приведенных в лемме 3 для x(h) > 0 . Рассмотрим вариант 0 < h1 < h < h2. Имеем ™ = - ^ -ф1+Р2)Т { z 2( z 2 - Р' -Р 2) - XiX 2( z 2 + Р' + Р 2* -(Р'+Р2)Т },(',) Т > 0, 0 Г, T > 0, 0 0, функция (23) - возрастающая функция переменной T (возрастает от y(T = 0, h) = ztz2(zt + z2 - Pt - P2) - 2(zt + z2 + Pt + P2)h до y(T = m, h) = ztz2(zt + z2 - Pt - P2) >0). Здесь возможны три ситуации: а) y(T = 0, h) > 0 , 0 < h, < h < h2; б) y(T = 0, h = h2) = 0 ; в) y(T = 0, h) > 0 , 0 < h, < h *; y(T = 0, h) = 0, h = h *; y(T = 0, h) < 0, h* < h < h2 , где h* = z^z, + z2-Р,-Р2)х x[[(z, + z2 +Р, + Р2)]'. Рассмотрим ситуацию а). Тогда функция (23) - положительная функция переменной Т (y(T, h) > 0 , Т > 0 ). В силу этого производная (22) - отрицательная функция переменной Т (Т > 0 ). Все это означает, что функция (21) убывает от Ф(Т = 0, h) > 0 до Ф(Т = м, h) > 0 . Отсюда следует, что для ситуации а) функция Ф(Т, h) > 0, Т > 0. Аналогично доказывается, что для ситуаций б), в) функция Ф(Т, h) > 0, Т > 0 . Используя формулы (22), (23), показывается, что для оставшихся вариантов, приведенных в лемме 3 для x(h) > 0, функция Ф(Т, h) > 0, Т > 0 . Лемма 6 доказана. Для случая x(h) < 0 имеет место лемма. Лемма 7. Функция Ф(Т, h) > 0, Т > 0 , если x(h) < 0 . Доказательство осуществляется применением формул (22), (23) (аналогично применению этих формул в лемме 6) для вариантов изменения параметра h, приведенных в лемме 3 для случая x(h) < 0 . Лемма 7 доказана. Лемма 8. Функции F,(T, h), F2(T, h) подчиняются неравенству: F,(T, h) > F2(T, h), T > 0, -1 < h < 1. Доказательство осуществляется объединением результатов лемм 6, 7. Лемма 8 доказана. Лемма 9. Уравнение (12) решения не имеет. Доказательство вытекает из последовательного применения лемм 3-5 и леммы 8. Лемма 9 доказана. Лемма 10. Производная p' (тm), определяемая формулой (3), является положительной функцией переменной Т (p'(--m) > 0, 0 < Т

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