The optimal state estimator of modulated synchronous twice stochastic flow of events in the conditions of fixed dead time.pdf Настоящая статья является продолжением работ [1-4]. Математические модели теории массового обслуживания широко применяются при описании реальных физических, технических и других процессов и систем. В связи с бурным развитием компьютерной техники и информационных технологий появилась важная сфера приложений теории массового обслуживания - проектирование и создание информационно-вычислительных сетей, компьютерных сетей связи, спутниковых сетей, телекоммуникационных сетей, объединенных термином «цифровые сети интегрального обслуживания» (ЦСИО) [5]. На практике параметры, определяющие входной поток событий, изменяются со временем, при этом изменения часто носят случайный характер, последнее приводит к рассмотрению дважды стохастических потоков событий. По-видимому, одной из первых работ в этом направлении явилась статья [6], в которой дважды стохастический поток определяется как поток, интенсивность которого есть случайный процесс. Дважды стохастические потоки можно разделить на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму классу относятся потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным числом состояний. Подчеркнем, что потоки второго класса впервые введены в рассмотрение практически одновременно в 1979 г. в [7-9]. В [7, 8] эти потоки названы MC (Markov chain)-потоками, в [9] - MVP (Markov versatile processes)-потоками. Отечественные и зарубежные авторы с начала 1990-х гг. [10-15] называют введенные в [7-9] потоки событий либо дважды стохастическими потоками событий, либо MAP-потоками, либо MC-потоками. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, MC-потоки можно разделить на три типа: 1) синхронные потоки событий [16, 17]; 2) асинхронные потоки событий [18, 19]; 3) полусинхронные потоки событий [20]. Здесь указаны ссылки на работы, в которых авторы впервые рассматривают MC-потоки событий в соответствии с приведенной классификацией. Наиболее обширная литература по рассматриваемым типам MC-потоков событий приведена в [21]. В [22] введены в рассмотрение MAP-потоки событий первого порядка (собственно MAP-потоки, введенные в [9]) и MAP-потоки событий второго порядка (суперпозиция двух синхронизированных MAP-потоков первого порядка, отличающихся друг от друга исходными параметрами). В [22] показывается, что синхронный MC-поток является частным случаем MAP-потока первого порядка, асинхронный и полусинхронный MC-потоки являются частными случаями MAP-потока второго порядка. В реальных ситуациях параметры, задающие входящий поток событий, известны либо частично, либо вообще не известны, либо (что еще более ухудшает ситуацию) изменяются со временем. Вследствие этого возникают задачи: 1) оценки состояний потока (задача фильтрации интенсивности потока) по наблюдениям за моментами наступления событий [23]; 2) оценки параметров потока по наблюдениям за моментами наступления событий [24]. Одним из искажающих факторов при оценке состояний и параметров потока событий выступает мертвое время регистрирующих приборов [25], которое порождается зарегистрированным событием. Другие же события, наступившие в течение периода мертвого времени, недоступны наблюдению (теряются). Можно считать, что этот период продолжается некоторое фиксированное время (непро-длевающееся мертвое время). В качестве примера приведем протокол CSMA/CD - протокол случайного множественного доступа с обнаружением конфликта, широко используемого в компьютерных сетях. В момент регистрации (обнаружения) конфликта на входе некоторого узла сети по сети рассылается сигнал «заглушки» («пробки»); в течение времени рассылки сигнала «заглушки» заявки, поступившие в данный узел сети, получают отказ в обслуживании и направляются в источник повторных вызовов. Здесь время, в течение которого узел сети закрыт для обслуживания заявок, поступающих в него после обнаружения конфликта, можно трактовать как мертвое время прибора, регистрирующего конфликт в узле сети. В работах [1-4] введен в рассмотрение модулированный синхронный поток событий, являющийся обобщением синхронного потока и относящийся к классу MAP-потоков второго порядка. Синхронный поток событий систематически исследовался в работах [16, 17, 24, 26-30]. В настоящей статье решается задача об оптимальной оценке состояний модулированного синхронного потока, функционирующего в условиях непродлевающегося мертвого времени. Предлагается алгоритм оптимальной оценки состояний, когда решение о состоянии потока выносится по критерию максимума апостериорной вероятности, представляющей наиболее полную характеристику состояний потока, которую можно получить, располагая только выборкой наблюдений. Сам критерий минимизирует полную вероятность ошибки вынесения решения [31]. 1. Постановка задачи Рассматривается модулированный синхронный поток событий (далее поток), интенсивность которого есть кусочно-постоянный стационарный случайный процесс X(t) с двумя состояниями: X^X2(Х1 > X2). Длительность пребывания процесса X(t) (потока) в i-м состоянии распределена по экспоненциальному закону с параметром а,, i = 1,2 . Если процесс X(t) в момент времени t находится в i-м состоянии, то на полуинтервале [t, t + At) , где At - достаточно малая величина, с вероятностью а,At + o(At) пребывание процесса X(t) в i-м состоянии закончится, и процесс X(t) с вероятностью, равной единице, перейдет из i-го состояния в j-е (i, j = 1,2, i Ф j). В течение временного интервала случайной длительности, когда X(t) = X,, имеет место пуассоновский поток событий с интенсивностью X,, i = 1,2. Кроме того, переход из первого состояния процесса X(t) во второе возможен в момент наступления события пуассоновского потока интенсивности X1; переход осуществляется с вероятностью p (0 < p < 1); с вероятностью 1-p процесс X(t) остается в первом состоянии. Переход из второго состояния процесса X(t) в первое возможен также в момент наступления события пуассоновского потока интенсивности X2; переход осуществляется с вероятностью q (0 < q < 1); с вероятностью 1-q процесс X(t) остается во втором состоянии. В сделанных предпосылках X(t) - марковский процесс. После каждого зарегистрированного в момент tk события наступает время фиксированной длительности Т (далее мертвое время), в течение которого другие события потока недоступны наблюдению. Рассматривается непродлевающееся мертвое время, т.е. события, наступившие в течение интервала мертвого времени, не вызывают его продления. По окончании длительности периода мертвого времени первое наступившее событие вновь генерирует период мертвого времени длительности Т и т.д. Вариант возникающей ситуации приведен на рис. 1, где Х1, X2 - состояния процесса X(t), t1, t2,... - моменты наступления наблюдаемых событий потока, штриховка - периоды мертвого времени длительности Т, ось под номером 1 отображает исходный модулированный поток событий, под номером 2 - схему создания мертвого времени, под номером 3 - наблюдаемые события модулированного синхронного потока. X(t)+ 1-р 1-р 1-р q а2 Р а! Т 1-q 1-q X2 1-q 1 t -tylffjtttlj 2 тншщ уЦШЫЩ -ушишц t T T T -Ьh h h U Рис. 1. Формирование наблюдаемого потока событий Блочная матрица инфинитезимальных коэффициентов примет вид 3 t -(X1 + а1) а1 а2 -(X 2 + а2) (1 - Р) X1 PX1 qX 2 (1 - q) X2 = D0 DJ D = Элементами матрицы Dl являются интенсивности переходов процесса X(t) из состояния в состояние с наступлением события. Недиагональные элементы матрицы D0 - интенсивности переходов из состояния в состояние без наступления события. Диагональные элементы матрицы D0 - интенсивности выхода процесса X(t) из своих состояний, взятые с противоположным знаком. Отметим, что если а; = 0, i = 1,2 , то имеет место обычный синхронный поток событий [24]. Подчеркнем, что в постановке задачи принимается первичность наступления события, затем -переход процесса X(t) из состояния в состояние. Данное обстоятельство при получении аналитических результатов является несущественным, так как наступление события и переход процесса X(t) из состояния в состояние происходят мгновенно. При получении же численных результатов путем имитационного моделирования необходима определенность, что первично - наступление события, затем смена состояния либо наоборот. Так как процесс X(t) и типы событий (события пуассоновских потоков с интенсивностями X1 либо X2) принципиально ненаблюдаемые, а наблюдаемыми являются только временные моменты наступления наблюдаемых событий на временной оси t1,t2,..., то необходимо по этим наблюдениям оценить состояние процесса X(t) (потока) в момент окончания наблюдений. Рассматривается стационарный режим функционирования потока событий, поэтому переходными процессами на интервале наблюдения (t0, t) , где t0 - начало наблюдений, t - окончание наблюдений (момент вынесения решения), пренебрегаем. Тогда без потери общности можно положить t0 = 0. Для вынесения решения о состоянии процесса X(t) в момент времени t необходимо определить апостериорные вероятности w(X; 11) = w(X; 111,... tm,t), i = 1,2, того, что в момент времени t значение процесса X(t) = X, (m - количество наблюденных событий за время t), при этом w(X1 11) + w(X211) = 1, тогда, если w(X . 11) > w(Xi 11), i, j = 1,2, i Ф j, то оценка состояния процесса есть X(t) = X .. 2. Алгоритм оптимальной оценки состояний модулированного синхронного потока в условиях непродлевающегося мертвого времени Момент вынесения решения t будет принадлежать интервалу (tk,tk+1), k = 1,2,..., между соседними событиями наблюдаемого потока. Для начального интервала (t0, t1) момент t будет лежать между началом наблюдения t0 и моментом t1. Рассмотрим интервал (tk, tk+1) , значение длительности которого есть Tk = tk+1 - tk (k = 0,1,...). Так как поток функционирует в условиях непродлевающегося мертвого времени фиксированной длительности Т, то данный интервал будет разбит на два смежных: первый полуинтервал (tk, tk + T ], второй интервал (tk + T, tk+1), условия вычисления апостериорной вероятности на которых принципиально разные. В статье [4] сформулирован алгоритм расчета апостериорной вероятности w(X1 11) для случая отсутствия мертвого времени (T = 0). При этом поведение w(X1 11) на интервале (tk,tk+1),k = 1,2,..., между соседними событиями модулированного синхронного потока, а также на интервале (t0, t1) между началом наблюдений и первым событием потока определяется выражением w1 [w(X | tk + 0) - w2]- w2 [(w(X | tk + 0) -w1 ]e(w -w2)(X -X2)(t-tk) w(XJtk + 0) - w2-[w(X,|tk + 0) - w ]e w(X1|t) = 1 ..2 r.l ^ ,,. i _(w-w2)(X.)-, (1) x1 + а2 + X1 - X2 + y](X1 - X2 + а1 - а2)2 + 4а1а2 / 2(X1 - X2); где tk < t < tk+1(k = 0,1,...); w1,2 = w(X1110 + 0), w(X1 | tk + 0) (k = 1,2,...), определены ниже. В момент наступления события модулированного синхронного потока tk, k = 1,2,..., апостериорная вероятность претерпевает разрыв (имеет место скачок), поэтому w(X1 11) определяется формулой пересчета (X 11 + 0) qX2 + [(1 - p)X1- qX2 ]w(X1| tk- 0) k (2) w(X1|tk + 0)=-r^-7.-^ „ ,,-Г7-,k^Д... (2) X2 + (X - X2)w(X11 tk - 0) где w(X11 tk - 0) вычисляется по формуле (1) в момент t = tk, когда t изменяется в полуинтервале [tk-1, tk), соседнем с полуинтервалом [tk, tk+1). В качестве начального условия w(X1|t0 + 0) = w(X1 110 = 0) в (1) выбирается априорная финальная вероятность первого состояния процесса X(t) [1]: п1=(а2 + qX2)/ (а1 + а2 + pX1 + qX2), (3) которая находится из уравнений п1 + п2 = 1, п1 (а1 + pX1) = п2 (а2 + qX2). Таким образом, вычисление апостериорных вероятностей w(X1 11) по формуле (1) в условиях, когда длительность мертвого времени T ф 0, справедливо на интервале (tk + T, tk+1) . При этом начальное условие для w(X1 11) привязывается к моменту окончания длительности мертвого времени tk + T , т.е. в формуле (1), во-первых, w(X11 tk + 0) заменяется на w(X1 | tk + T), во-вторых, tk + T < t < tk+1 (k = 1,2,...). Формула пересчета (2) при этом остается без изменений, так как она предназначена для вычисления апостериорных вероятностей в момент наступления наблюдаемого события потока tk. Отметим, что для потока, функционирующего в условиях мертвого времени, наблюдаемыми событиями являются события, не попавшие в интервалы мертвого времени (события, инициирующие его наступление), для потока же, функционирующего в условиях отсутствия мертвого времени, все события являются наблюдаемыми. Рассмотрим полуинтервал (tk,tk + T], k = 1,2,.... Так как на этом полуинтервале длительности Т событие наблюдаемого потока имеет место в граничной точке tk , а на самом отрезке события отсутствуют, то необходимо определить поведение апостериорной вероятности w(X1 11) на полуинтервале (tk, tk + T]. В момент времени tk, когда наступают наблюдаемое событие потока и период мертвого времени длительности Т, события потока перестают наблюдаться. Эта ситуация аналогична той, когда в начальный момент времени t0 0 событие потока также не наблюдается, имеются лишь априорные данные о потоке, поэтому вывод дифференциального уравнения для нахождения вероятности w(X1 1t) на временном полуинтервале (tk, tk + T ] аналогичен выводу дифференциального уравнения для априорной вероятности п1 [1]. Найдем дифференциальные уравнения относительно неизвестных w(X1 11) и w(X211). Определим апостериорную вероятность w(X1 11 + At) того, что в момент времени t + At (tk < t + At < tk + T), где At - достаточно малая величина, процесс X(t) находится в первом состоянии, и на полуинтервале [t, t + At) процесс X(t) не перейдет во второе состояние. Вероятность такого события есть w(X111)(1 - а1 At - pX1At) + o(At) . Пусть в момент времени t процесс X(t) находится во втором состоянии и на полуинтервале [t,t + At) процесс X(t) перейдет в первое состояние. Вероятность такого события есть w(X21 t)(qX2At + а2At) + o(At) . Другие возможности имеют вероятность o(At) . Тогда w(X111 + At) = w(X111)(1 - а1 At - pX1 At) + w(X2 11)(qX2At + а2At) + o(At). (4) Аналогично находится w(X211 + At): w(X211 + At) = w(X211)(1 - а2 At - qX2At) + w(X1 11)(pX1At + a1At) + o(At). (5) Производя в (4), (5) необходимые преобразования и перейдя к пределу при At ^ 0, получаем систему дифференциальных уравнений для апостериорных вероятностей w(X1 11) и w(X2 11) dw(Xl *t) = -К + pX1)w(X1 11) + (а2 + qX2)w(X211), dt (6) dw(X2|t) = -(а2 + qX2)w(X211) + (а1 + qX1 )w(X1 11) dt с граничными условиями w(X111 = tk) = w(X11 tk + 0), w(X211 = tk) = w(X2 | tk + 0), k = 1,2,... . Последнее вытекает из того, что на полуинтервале (tk-1 + T, tk ], k = 2,3,..., смежном с полуинтервалом (tk, tk + T], апостериорная вероятность рассчитывается по формуле (1), где вместо w(X1 | tk + 0) стоит w(X1 | tk + T); в точке t = tk происходит пересчет апостериорной вероятности по формуле (2), так что ее значение в этой точке есть w(X1 | tk + 0). Для граничного полуинтервала [t0, t1) расчет апостериорной вероятности w(X111) производится по формуле (1) с ее последующим пересчетом по формуле (2) в точке t = t1. Решая систему (6), находим w(X1 11) = я1 + (w(X1 | tk +0) - %1)e-(a1+ 0,5, то оценка X(t) = X1, в противном случае X(t) = X2. 3. Результаты статистического эксперимента Для получения численных результатов разработан алгоритм вычисления апостериорной вероятности w(X1 11) по формулам (1)-(3), (7)-(9). Программа расчета реализована на языке программирования Visual C++, Microsoft Visual Studio 2008. Первый этап расчета предполагает имитационное моделирование модулированного синхронного потока. Описание алгоритма моделирования здесь не приводится, так как никаких принципиальных трудностей он не содержит. Второй этап расчета - вычисление вероятностей w(X1 11), t0 < t < t1; w(X1 | tk + 0); w(X1 11), tk < t < tk + T; w(X1 11), tk + T < < t < tk+1, к = 1,2,..., и построение оценки X(t) . Пример поведения процесса X(t) и его оценки X(t) изображен на рис. 2. Данные результаты получены для следующих значений параметров: = 3, X2 = 0,3, p = 0,6, q = 0,4, а1 = 4 , а2 = 0,4 , T = 1, время моделирования Tm = 100 ед. времени. В верхней части рисунка изображено истинное поведение процесса X(t), полученное путем имитационного моделирования, где Xx и X2 - состояния процесса X(t). В нижней части изображено поведение оценки X(t) процесса X(t). t Рис. 2. Траектория поведения процесса X(t) и его оценки X(t) Вынесение решения о состоянии процесса X(t) производилось с шагом At = 0,01. На рис. 2 штриховкой на оси времени обозначены промежутки, на которых оценка состояния не совпадает с истинным значением процесса X(t) (область ошибочных решений). На рис. 3 приведена траектория поведения апостериорной w(X111), соответствующая полученной при имитационном моделировании последовательности событий tj, t2,... наблюдаемого потока. Для установления частоты ошибочных решений о состоянии процесса X(t) по наблюдениям за потоком проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров Xj, X2, p, q, oq, а2, T , Tm ед. времени осуществляется моделирование потока событий на заданном отрезке времени [0, Tm ] (отдельный j-й эксперимент); 2) рассчитывается вероятность w(Xj 11) на отрезке [0,Tm ] по формулам (1)-(3), (7)-(9); 3) оценивается траектория процесса X(t) на отрезке [0, Tm ]; 4) осуществляется определение (для J-го эксперимента) dJ - суммарной протяженности интервалов, на которых значение процесса X(t) не совпадает с его оценкой X(t); 5) вычисляется доля ошибочных решений pj = dj / Tm ; 6) производится повторение N раз (J = 1, N ) шагов 1-5 для расчета оценки безусловной (полной) вероятности принятия решения о состояниях процесса X(t) на отрезке [0, Tm ]. Результатом выполнения описанного алгоритма является выборка (p1, p2,... p N) долей ошибочных решений в N экспериментах. По этому набору вычисляются выборочное среднее безусловной N вероятности принятия ошибочного решения P = (1 / N) ^ pj и выборочная дисперсия J=1 D = (1/(1 - N)) J (pj - P)2. j=1 Рис. 3. Траектория поведения апостериорной вероятности w(kx 11) Результаты статистического эксперимента для Tm = 100 ед. времени и N = 100 приведены в табл. 1-4. В первой строке таблиц указаны значения изменяющегося параметра (длительности мертвого времени T) при остальных фиксированных. Во второй и третьей строках таблиц для каждого значения изменяющегося параметра приведены численные значения P и D. Т а б л и ц а 1 Результаты эксперимента при 10 , X2 =0,5, p = 0,6, q = 0,6, a1 = 1, a2 = 0,2 T 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 P 0,0865 0,1283 0,1892 0,2431 0,2805 0,3172 0,3489 0,375 0,4005 0,428 0,4481 D 0,0001 0,0002 0,0004 0,0008 0,0008 0,001 0,0016 0,0016 0,0014 0,0019 0,0019 Т а б л и ц а 2 Результаты эксперимента при X1= 3 , X2 = 0,3, p = 0,6, q = 0,4, a1 = 4, a2 = 0,4 T 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 P 0,1183 0,1272 0,1541 0,1905 0,2218 0,2476 0,2691 0,2939 0,3064 0,3349 0,3509 D 0,0002 0,0003 0.0005 0.0005 0,0006 0,0007 0,001 0,0011 0,0013 0,0014 0,0018 Результаты эксперимента при X1= 5 , X2 =0,5, p = 0,4, q=0,6, a1 = 7, a2 = 0,8 Т а б л и ц а 3 T 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 P 0,1560 0,1743 0,2187 0,2648 0,3034 0,3296 0,3627 0,3926 0,4190 0,4385 0,4579 D 0,0003 0,0002 0,0004 0,0005 0,0006 0,0010 0,0009 0,0011 0,0011 0,0012 0,0010 Результаты эксперимента при X1= 2 , X2 =0,6, p = 0,3, q=0,4, a1 = 5, a2 = 1 Т а б л и ц а 4 T 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 P 0,2869 0,3025 0,3062 0,3422 0,3618 0,3915 0,4171 0,4306 0,4562 0,4694 0,4854 D 0,0005 0,0006 0,0007 0,0007 0,0009 0,0010 0,0008 0,0012 0,0010 0,0011 0,0012 Анализ результатов, приведенных в таблицах, говорит о том, что имеется тенденция роста оценки P при увеличении длительности мертвого времени T, что вполне естественно, так как чем больше мертвое время, тем больше теряется информации о потоке. С ростом T темп ухудшения оценки падает, поскольку увеличение потерь информации становится относительно малым по сравнению с уже имеющимися потерями. Многочисленные эксперименты, проведенные для тех же параметров, что и эксперименты, представленные в табл. 1-4, показывают, что при изменении T в диапазоне от 18 до 20 ед. времени значения P и D стабилизируются, т.е. потери информации о потоке столь велики, что дальнейшее увеличение мертвого времени не оказывает существенного влияния на качество оценок. При фиксированном значении Т с увеличением X1 - X 2 качество оценки состояния улучшается, так как чем сильнее интенсивности X1 и X 2 отличаются друг от друга, тем сильнее различается поведение потока в первом и втором состояниях. В целом анализ результатов экспериментов показывает, что предложенный в статье алгоритм обеспечивает приемлемую величину оценки полной вероятности принятия ошибочного решения, выборочная дисперсия оценки при этом достаточно мала. Заключение Полученные результаты показывают возможность оценивания состояний модулированного синхронного дважды стохастического потока событий, функционирующего в условиях непродлевающе-гося мертвого времени, по результатам наблюдений (в течение некоторого временного интервала) за потоком. Последнее позволяет системе массового обслуживания оперативно адаптироваться (варьировать дисциплину обслуживания, режимы обслуживания и свою структуру) к изменяющимся состояниям потока. Выражения (2), (8), (9) для оценки состояний модулированного синхронного дважды стохастического потока событий получены в явном виде, что позволяет производить вычисления без привлечения численных методов. Сам же алгоритм оценки состояний потока обеспечивает минимум полной вероятности ошибки вынесения решения.

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