The optimal state estimation of modulated synchronous twice stochastic flow of events.pdf Математические модели теории массового обслуживания широко применяются при описании реальных физических, технических и других процессов и систем. В связи с бурным развитием компьютерной техники и информационных технологий появилась важная сфера приложений теории массового обслуживания - проектирование и создание информационно-вычислительных сетей, компьютерных сетей связи, спутниковых сетей, телекоммуникационных сетей, объединенных термином - ЦСИО. На практике параметры, определяющие входной поток событий, изменяются со временем, при этом изменения часто носят случайный характер, последнее приводит к рассмотрению дважды стохастических потоков событий. По-видимому, одной из первых работ в этом направлении явилась статья [1], в которой дважды стохастический поток определяется как поток, интенсивность которого есть случайный процесс. Дважды стохастические потоки можно разделить на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму классу - потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным числом состояний. Подчеркнем, что потоки второго класса впервые введены в рассмотрение практически одновременно в \979 г. в [2-4]. В [2, 3] введенные потоки названы MC (Markov chami-потоками; в [4] - MVP (Markov versatile processes)-потоками. Последние начиная с конца 80-х годов прошлого века носят название MAP (Markov Arrival Process)-потоков событий. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, MC-потоки можно разделить на три типа: \) синхронные потоки событий [5, 6]; 2) асинхронные потоки событий [7, 8]; 3) полусинхронные потоки событий [9]. Здесь указаны ссылки, в которых авторы впервые рассматривают MC-потоки событий в соответствии с приведенной классификацией. Наиболее обширная литература по рассматриваемым типам MC-потоков событий приведена в [Ш]. В [П] введены в рассмот- \ Работа выполнена в рамках государственного задания Минобрнауки РФ на проведение научных исследований в Томском государственном университете на МП—20\4 годы, задание 8.4055.20П. рение MAP-потоки событий первого порядка (собственно MAP-потоки, введенные в [4]) и MAP-потоки событий второго порядка (суперпозиция (простая сумма) двух MAP-потоков первого порядка, отличающихся друг от друга исходными параметрами). В [11] показывается, что синхронный MAP-поток является частным случаем MAP-потока первого порядка, асинхронный и полусинхронный MC-потоки являются частными случаями MAP-потока второго порядка. В реальных ситуациях параметры, задающие входящий поток событий, известны либо частично, либо вообще неизвестны, либо (что еще более ухудшает ситуацию) изменяются со временем. Вследствие этого возникают задачи: 1) оценки состояний потока (задача фильтрации интенсивности потока) по наблюдениям за моментами наступления событий [12]; 2) оценка параметров потока по наблюдениям за моментами наступления событий [13]. В работе [14] введен в рассмотрение модулированный синхронный поток событий, являющийся обобщением синхронного потока и относящийся к классу MAP-потоков второго порядка. В настоящей статье, являющейся непосредственным развитием работы [14], решается задача об оптимальной оценке состояний модулированного синхронного потока. Предлагается алгоритм оптимальной оценки состояний, когда решение о состоянии потока выносится по критерию максимума апостериорной вероятности, представляющей наиболее полную характеристику состояний потока, которую можно получить, располагая только выборкой наблюдений. Сам критерий минимизирует полную вероятность ошибки вынесения решения [15]. 1. Постановка задачи Рассматривается модулированный синхронный поток событий (далее поток), интенсивность которого есть кусочно-постоянный стационарный случайный процесс X(t) с двумя состояниями: Х^Х2 (Xj > X2). Длительность пребывания процесса X(t) (потока) в i-м состоянии распределена по экспоненциальному закону с параметром аг-, i = 1,2 . Если процесс X(t) в момент времени t находится в i-м состоянии, то на полуинтервале [t, t + At), где At — достаточно малая величина, с вероятностью ai At + o(At) пребывание процесса X(t) в i-м состоянии закончится, и процесс X(t) с вероятностью равной единице перейдет из i-го состояния в j-е (i, j=1,2, ij). В течение временного интервала случайной длительности, когда X(t) = Xi, имеет место пуассоновский поток событий с интенсивностью Xi, i = 1,2 . Кроме того, переход из первого состояния процесса X(t) во второе возможен в момент наступления события пуассоновского потока интенсивности X1; переход осуществляется с вероятностью p (0 < p < 1); с вероятностью 1—p процесс X(t) 1-p 1-p W)t Х2 1-P a1 a2 q 1-q 1-q 1-q остается в первом состоянии. Переход из второго состояния процесса X(t) в первое возможен также в момент наступления события пуассоновского потока интенсивности X2; переход осуществляется с вероятностью q (0 = (X(0), X(1),...,X(0)) - последовательность неизвестных (ненаблюдаемых) значений процесса X(nAt) в моменты nAt(n = 0, m); X(0) = X(0) = Xi, i = 1,2. Обозначим rm = (r0,r1,...,rm) - последовательность числа событий за время от 0 до mAt на интервалах ((n - 1)At);nAt) длительности At, n = 0, m (значение r0 можно задавать произвольно, так как промежуток (-At,0) находится за пределами интервала наблюдения (0, mAt), и положить его, например, равным 0). Обозначим через w(X(m) \Гт) условную вероятность значения X(m) при условии, что наблюдалась реализация Гт . Аналогично w(X(m) \Гт+1). Для марковского случайного процесса (X(n), rn) в [8] получена рекуррентная формула, связывающая апостериорные вероятности w(X(m) \Гт) и w(X(m+1) \Гт+1): ( 1) Z X2m)X ) p(X(m+1), rm+1|X( m), rm ) w(X( -1 | rm+1) = —-b—^-, (1) m+1 Z X(2m+1) =X Z X2m) =X w(X( m) \ rm ) p(X(m+1), rm+1 |X(m), rm ) где p(X(m+1), rm+1 | X(m), rm) - вероятность перехода процесса (X(n), rn) за один шаг At из состояния (X(m), rm) в состояние (X(m+1), rm+1). В рассматриваемом случае модулированного синхронного дважды потока процесс (X(n), rn) будет марковским, при этом переходная вероятностьp(X(m+1),rm+1 | X(m),rm) в (1) примет вид p(X( m+1), rm+1 | X(m), rm ) = p(X( m+1) | X( m)) p(rm+1 | X(m), X( ^ . Принимая во внимание, что если w(X(т) \Гт) = w(X(т) \Гт (t)) = w(X(m+1) 11), (X(m+1:i \rm+1) = w(X(m+1:i \rm+l (t + At)) = w(X(m+1) 11 + At), то (1) запишется в виде w( ZX2m) =X w(X(m) 11)p(X(m+1) | X(m))p(rm+1 | X(m), X(m+1)) w(X(m+1) 11 + At) = ^X(m)=X '-—-:-——-:-:-.(2) Z X2m +1) =X Z X2m) =X w(X( m) |t) p(X( m+1) |X(m)) p(rm+1 |X( m), X( m+1)) Лемма 1. В течение времени между наступлениями соседних событий модулированного синхронного потока tk и tk+1,к = 0,1,..., апостериорная вероятность w(X\ 11) удовлетворяет дифференциальному уравнению dw(X\ 11) ■ = (X\ - X2) (w(X\ 11) - w\ )(w(X\ |t) - W2), (3) dt а\ + а2 + X\ -X2 + (X\ -X2 + а\ -а2)2 + 4а\а2 /2(X\ - X2). W\ 2 = Доказательство. Для определенности положим в (2) X(m+\) = X\. В силу определения потока величина rm+\ в (2) может принимать два значения: rm+\ = 0,rm+\ = \. Здесь рассматривается поведение вероятности w(X\ 11) на полуинтервале [tk, tk+\) между соседними событиями потока, то есть tk < t < tk+\, tk < t + At < tk+\. Тогда в (2) rm+\ = 0 и с учетом матрицы D0 , на полуинтервале [t, t + At) = [mAt, (m + \)At) переходные вероятности в (2) запишутся в виде p(X(m+\) = Xi | X(m) = X\)p(rm+\ = 01 X(m+\) = Xi, X(m) = X\) = = \ - а,- At - Xi At + o(At), i = \ 2, p(X(m+\) = X, | X(m) = X2)p(rm+\ = 01 X(m+\) = X,, X(m) = X2) = = а,At + o(At), i = 2. Подставляя эти выражения в (2), находим W(X 11 + At) = w(X\ 11)(\ - а\At - X\At) + w(X2 | flc^At + o(At) W( \ | ) w(X\ 11)Д - X\At) + w(X2 11)Д - X2At) + o(At). Учитывая, что w(X2 11) = \ - w(X\ 11) и при достаточно малых At величина A- = \ + X2At + + w(X\ 11)(X\ - X2)At + o(At), то деля обе части равенства на At и устремив At к 0, получаем dw(X\ 11) = а2 - w(X\ 11)(а\ + а2 + X\ -X2) + w2(X\ | t)(X\ -X2). dt Находя корни w\ и w2 характеристического уравнения а2 - w(X\ 11)(а\ + а2 + X\ - X2) + w2 (X\ 11)(X\ - X2) = 0, подставляя их в полученное дифференциальное уравнение, приходим к (3). Лемма 1 доказана. Замечание 1. Уравнение (3) определяет поведение вероятности w(X\ 11) на полуинтервале [tk,tk+\),k = 0Д,..., то есть между моментами наступления событий, причем на правом конце полуинтервала имеет место значение w(X\ | tk+ - 0), на основе которого, как будет показано в лемме 2, находится вероятность w(X\ | tk+\ + 0), являющаяся начальной для следующего полуинтервала [tk+\, tk+2). Лемма 2. Апостериорная вероятность w(X\ 11) в момент наступления события модулированного синхронного потока tk,k = 0Д,..., определяется формулой пересчета w(X\ | tk+\ + 0) = qX2 + ((\- p)X\ -qX2)w(X\|tk -0), k = \2,... . (4) n k+\ X2 + (X\ - X2)w(X\ | tk - 0) Доказательство. Пусть на интервале (t, t + At) в момент времени tk (t < tk < t + At) наступает событие потока (rm+\ = 1). Имеем два смежных интервала (t, tk) и (tk, t + At). Длительность первого tk -1 = At', длительность второго t + At-tk = At". Тогда в (2) w(X(m) 11) = w(X(m) | tk -At'), w(X(m+\) 11 + At) = = w(X\ | tk + At"), и (2) примет вид Х-?-)=. w(-(m)|tk-At')p(-\|-(m))p(rm+\|X(m),X(m+\)) w(X\ |tk +At") =—--. (5) \ k Z-U =^2»)=- w(-(m)|tk-At') p(-(m+\)|-(m))p(rm+\|-(m),-(m+\)) С учетом матрицы D\ на интервале (t, t + At ) = ( mAt,(m + 1)At) переходные вероятности в (5) запишутся в виде p(X(m+1) = X\ | X(m) = X\)p(rm+1 = 1| X(m+1) = X\,X(m) = X\) = (1 - p)X\At + o(At), p(X( m+1) = X2|X(m) = X 2) p(rm+1 = 1| X(m+1) = X 2,X(m) = X 2) = (1 - q) X2 At + о (At), p(X(m+1) = X\|X(m) = X2)p(rm+1 = 1| X(m+1) = X\,X(m) = X2) = pX\At + o(At), p(X(m+1) = X2 |X(m) = X\)p(rm+1 = 11 X(m+1) = X2 ,X(m) = X\) = qX2At + o(At). Подставляя данные переходные вероятности в (5), получаем числитель B\ и знаменатель B2 в (5): B\ = w(X\ | tk -1')(1 - p)X\ At + w(X2 | tk - At')qX2At + o(At), B2 = w(X\ | tk - At')(1 - p)X\At + w(X2 | tk - At')qX2At + w(X\ | tk - At')pX\At + + w(X2 | tk - At')(1 - q)X2At + o(At). Подставляя B\ и B2 в (5) , деля числитель и знаменатель на At и устремляя At к 0 (At' и At" стремятся к 0 одновременно), учитывая, что w(X21 tk - At') = = 1 - w(X\ | tk - At'), приходим к (4). Лемма 2 доказана. Замечание 2. В точке tk вероятность w(X\ 11) претерпевает разрыв (имеет место конечный скачок). Тогда решение уравнения (3) будет зависеть от начального условия в момент времени tk, т.е. от w(X\ | tk + 0), k = 1,2,.... В свою очередь, w(X\ | tk + 0) зависит от значения w(X\ | tk - 0) - значение вероятности w(X\ 11) в момент времени tk, когда w(X\ 11), определяемая в (3), изменяется на полуинтервале [tk-1,tk), соседнем с полуинтервалом [tk,tk+1),k = 1,2,.... Таким образом, в значении w(X\ | tk + 0) «сосредоточена» вся предыстория наблюдений за потоком начиная от момента времени t0 = 0 до момента tk . В качестве начального условия w(X\|t0 + 0) = w(X\ 110 = 0) в (3) выбирается априорная финальная вероятность первого состояния процесса X(t): П\ = (а\ + pX\ )/(а\ + а2 + pX\ + qX2). (6) Замечание 3. Рассмотрим случай, когда p+q=1. Тогда выражение (4) приобретает вид w(X\ | tk + 0) = q,k = 1,2,.... Последнее говорит о том, что для этого частного случая вероятность w(X1 11) не зависит от предыстории, а зависит только от ее значения в момент tk, т.е. от w(X1 | tk + 0) = q для любых k (k = 1,2,...). Леммы 1 и 2 позволяют сформулировать следующую теорему. Теорема. Поведение апостериорной вероятности w(X1 11) на временных полуинтервалах [tk,tk+1), k = 1,2,..., определяется явной формулой: |t) = w1( w(X1 |tk + 0) - w2) - w2( w(X1 |tk + 0) - w1)g( w1 - w2)( X -X2))(-k) (7) 1 w(X1 | tk + 0) - w2 - (w(X1 | tk + 0) - w1)e(w1 -w2)(X1 -X2)(t-tk) ' где tk < t < tk+1 (k = 0,1,...); w(X1 | tk + 0) определена формулой (4), k = 1,2,...; w(X1 110 + 0) = w(X1 110 = 0) = , где определяется в (6); w1, w2 определены в (3). Доказательство. Уравнение (3) в лемме 1 представимо в виде 1 d(w(X1 11) - w1) d(w(X2 11) - w2) = (X1 - X 2)dt, (8) w1 - w2 \ w(X1 11) - w1 w(X2 11) - w2 _ где w1 и w2 определены в (3). Интегрируя (8) в пределах от tk + 0 до t получаем (7). Теорема доказана. Полученные формулы позволяют сформулировать алгоритм расчета вероятности w(X1 11) и алгоритм принятия решения о состоянии процесса X(t) в любой момент времени t (алгоритм оптимальной оценки состояния модулированного синхронного потока): 1) в момент времени t0 = 0 по формуле (6) задается w(X1 110 + 0) = w(X1 110 = 0) = П1; 2) по формуле (7) для k=0 вычисляется вероятность w(X1 11) в любой момент времени t (0 < t < t1), где t1 - момент наступления первого события потока; 3) по формуле (7) для k=0 рассчитывается вероятность w(X1 111) = w(X1 111 - 0); 4) k увеличивается на единицу, и по формуле (4) для k=1 вычисляется значение w(X1 111 + 0), являющееся начальным значением для w(X1 11) в формуле (7); 5) по формуле (7) для k=1 рассчитывается вероятность w(X1 11) в любой момент времени t (t1 < t < t2); 6) по формуле (7) для k=1 вычисляется вероятность w(X1 112) = w(X1 112 - 0); 7) алгоритм переходит на шаг 4, после чего шаги 4 - 6 повторяются для k = 2 и т. д. По ходу вычисления w(X1 11) в любой момент времени t выносится решение о состоянии процесса X(t): если w(X1 11) > 0,5, то оценка X(t) = X1, в противном случае X(t) = X2. Особый случай. Если p+q=1, то каждый раз, когда алгоритм возвращается на шаг 4, вероятность w(X1 | tk + 0), k = 1,2,..., полагается равной q. 3. Результаты статистического эксперимента Для получения численных результатов разработан алгоритм вычисления апостериорной вероятности w(k1 11) по формулам (4) - (7). Программа расчета реализована на языке программирования Visual C++, Microsoft Visual Studio 2008. Первый этап расчета предполагает имитационное моделирование модулированного синхронного потока. Описание алгоритма моделирования здесь не приводится, так как никаких принципиальных трудностей он не содержит. Второй этап расчета - вычисление вероятностей w(k1 11), t0 < t < t1; w(k1 | tk + 0); w(k1 11), tk < t < tk+1, £=1,2,..., по формулам (4), (6), (7) и построение оценки X(t). Пример поведения процесса X(t) и его оценки изображен на рис. 2. Данные результаты получены для следующих значений параметров: = 1, X2 = 0,5, p = 0,4, q = 0,5, а = 2, а2 = 1, время моделирования T = 100 ед. времени. В верхней части рисунка изображено истинное поведение процесса X(t), полученное путем имитационного моделирования, где X и 12 - состояния процесса X(t). В нижней части рисунка изображено поведение оценки X(t) процесса X(t). Вынесение решения о состоянии процесса X(t) производилось с шагом At = 0,01. На рис. 2 штриховкой на оси времени обозначены промежутки, на которых оценка состояния не совпадает с истинным значением процесса X(t) (область ошибочных решений). На рис. 3 приведена траектория поведения апостериорной w(k1 11), соответствующая полученной при имитационном моделировании последовательности событий t1,t2,.... h(t). А.1 0 h(t) 0 -Л- -ё- Лt t Рис. 2. Траектория процесса X(t) и оценки X(t) t) 1 0,5 -е- -е- -е- -е- 0 t Рис. 3. Траектория поведения апостериорной вероятности w(X111) Для установления частоты ошибочных решений о состоянии процесса X(t) по наблюдениям за потоком проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров X1, X2, p, q, а1 , а2, Tm ед. времени осуществляется моделирование потока событий на заданном отрезке времени [0, Tm ] (отдельный j-й эксперимент); 2) рассчитывается вероятность w(X1 11) на отрезке [0, Tm ] по формулам (4), (6), (7); 3) оценивается траектория процесса X(t) на отрезке [0, Tm ]; 4) осуществляется определение (для j-го эксперимента) dj - суммарной протяженности интервалов, на которых значение процесса X(t) не совпадает с его оценкой X(t); 5) вычисляется доля ошибочных решений p j = dj / Tm ; 6) производится повторение N раз (j = 1, N) шагов 1 - 5 для расчета оценки безусловной (полной) вероятности принятия решения о состояниях процесса X(t) на отрезке [0, Tm ]. Результатом выполнения описанного алгоритма является выборка (pj, p2,... pN) долей ошибочных решений в N экспериментах. По этому набору вычисляются выборочное среднее безусловной вероятности принятия ошибочно- NN го решения P = (1 / N)£ pи выборочная дисперсия D = (1 /(1 - N))£ (p- P')2. j=i j=1 Результаты статистического эксперимента приведены в табл. 1 - 6. В первой строке таблиц указаны значения изменяющегося параметра при остальных фиксированных. Во второй и третьей строках таблиц для каждого значения изменяющегося параметра приведены численные значения P и D . Результаты в табл. 1,2 получены при следующих фиксированных параметрах, p=0,6, q=0,6, а1 = 1, а2 = 0,2. При этом в табл. 1 параметр меняет значения от 1 до 10 при X2 = 0,5, в табл. 2 X2 принимает значения от 0,5 до 9 при = 10. Результаты в табл. 3,4 получены при p=0,6, q=0,6, X1 = 10, X 2 = 0,5, причем в табл. 3 а1 принимает значения от 1 до 10 при а2 = 0, 2 , в табл. 4 а2 принимает значения от 0,2 до 9 при а1 = 10 . Результаты в табл. 5 и 6 приведены, когда X1 = 5 , X2 = 0, 5 , а1 = 5 , а2 = 0, 2 , при этом в табл. 5 p меняет свое значение от 0,05 до 0,9 при q=0,6, а в табл. 6 параметр q варьируется от 0,05 до 0,9 приp = 0,6. Таблица 1 X! 1 2 3 4 5 6 7 8 9 10 P 0,2525 0,2003 0,1602 0,1326 0,1171 0,1085 0,0897 0,0826 0,0763 0,0718 D 0,0017 0,0009 0,0006 0,0005 0,0005 0,0003 0,0003 0,0002 0,0002 0,0001 Таблица 2 %2 0,5 1 2 3 4 5 6 7 8 9 P 0,0683 0,1046 0,1683 0,2271 0,2795 0,3066 0,3516 0,3889 0,4122 0,4430 D 0,0002 0,0003 0,0004 0,0003 0,0002 0,0007 0,0004 0,0003 0,0004 0,0005 Таблица 3 а1 1 2 3 4 5 6 7 8 9 10 P 0,0683 0,0610 0,0574 0,0527 0,0468 0,0423 0,0405 0,0394 0,0347 0,0332 D 0,0002 0,0001 0,00004 0,00006 0,00009 0,00005 0,00006 0,00005 0,00002 0,00002 Таблица 4 а2 0,2 1 2 3 4 5 6 7 8 9 P 0,0337 0,0748 0,1248 0,1648 0,2135 0,2460 0,2788 0,3089 0,3397 0,3628 D 0,00002 0,00008 0,00009 0,0001 0,0002 0,0001 0,0001 0,0002 0,0001 0,0001 Таблица 5 Р 0,05 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 P 0,0820 0,0800 0,0780 0,0741 0,0741 0,0700 0,0641 0,0613 0,0575 0,0532 D 0,0002 0,0001 0,0001 0,00009 0,0001 0,00009 0,0001 0,0001 0,0001 0,00007 Таблица 6 q 0,05 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 P 0,0305 0,0318 0,0382 0,0415 0,0492 0,0539 0,0629 0,0708 0,0712 0,0747 D 0,00005 0,00005 0,00007 0,00009 0,00009 0,0001 0,0001 0,0001 0,0002 0,0002 Заключение Анализ результатов, приведенных в табл. 1, 2, говорит о том, что имеется тенденция роста оценки P при уменьшении разности Х1-Х2 и, наоборот, тенденция уменьшения оценки P при увеличении разности Х1-Х2. Последнее вполне естественно, так как при увеличении разности Х1-Х2 условия различимости двух состояний Х1 и Х2 улучшаются. Аналогичная тенденция роста оценки P наблюдается в табл. 3, 4 при уменьшении разности а1-а2, что объясняется лучшей различимостью состояний Х1 и Х2 процесса X(t) при увеличении разности а1-а2 и соответственно приводит к уменьшению вероятности принятия ошибочного решения. Уменьшение вероятности P хорошо прослеживается в табл. 5 и может быть объяснено тем, что при среднем значении вероятности перехода q, высокой частоте наступления событий в первом состоянии (Х1 = 5) и низкой частоте наступления событий во втором состоянии (Х2 = 0,5) время, проведенное процессом X(t) во втором состоянии, увеличивается с ростом вероятности p, что дает возможность большей различимости состояний и, следовательно, ведет к уменьшению вероятности ошибки. Обратная тенденция наблюдается в табл. 6. Здесь при среднем значении вероятности перехода p, низкой частоте наступления событий во втором состоянии и, наоборот, высокой частоте наступления событий в первом состоянии вероятность принятия ошибочного решения увеличивается с ростом q вследствие уравнивания длительности пребывания процесса h(t) в каждом из состояний, что приводит к ухудшению условий их различимости.

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