The optimal states evaluation of modulated semisyncronous integrated flow of events.pdf В последнее время в связи с бурным развитием компьютерной техники и информационных технологий появилась важная сфера приложений теории массового обслуживания - проектирование и создание информационно-вычислительных сетей, телекоммуникационных сетей и т.п., объединенных термином ЦСИО. Математические методы теории массового обслуживания обеспечивают возможность решения многочисленных задач расчета характеристик качества функционирования различных компонент ЦСИО, включая оценку вероятностно-временных характеристик узлов коммутации и маршрутизации; анализ буферной памяти узлов и методов локального и глобального управления потоками и т.д. Стоит отметить, что условия функционирования реальных объектов и систем таковы, что если в отношении параметров обслуживающих устройств можно сказать, что они известны и с течением времени не меняются, то в отношении интен-сивностей входящих потоков этого сказать во многих случаях нельзя. Более того, интенсивности входящих потоков обычно меняются со временем, часто эти изменения носят случайный характер, что приводит к рассмотрению математических моделей дважды стохастических потоков событий. По-видимому, статья [1] является одной из первых работ в этом направлении, где дважды стохастический поток определяется как поток, интенсивность которого есть случайный процесс. С другой стороны, функционирование систем массового обслуживания зависит от параметров и состояний входящих потоков. В подобных ситуациях наиболее рациональным является применения адаптивных систем массового обслуживания, которые в процессе функционирования оценивают неизвестные параметры либо состояния входящих потоков и изменяют дисциплину обслуживания в соответствии с полученными оценками [2]. Дважды стохастические потоки событий можно разделить на два класса: к первому классу относятся потоки, интенсивность которых есть непрерывный случайный процесс; ко второму - потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным числом состояний. Потоки второго класса впервые и независимо введены в работах [3-5]. В [3, 4] введенные потоки названы MC (Markov Лв^-потоками; в [5] - MVP (Markov Versatile Processes)-потоками. Последние с начала 90-х годов получили название MAP (Markovian Arrival Process)-потоков событий. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, MC-потоки событий можно разделить на три типа: 1) синхронные потоки [6]; 2) асинхронные потоки [7]; 3) полусинхронные потоки [8]. Здесь указаны ссылки на статьи, в которых авторы впервые рассматривали MC-потоки событий в соответствии с приведенной классификацией. Наиболее полная литература по изучаемым типам MC-потоков событий приведена в [9]. Подчеркнем, что синхронные, асинхронные и полусинхронные потоки возможно представить в виде моделей MAP-потоков событий первого либо второго порядков [10]. В [10] показывается, что синхронный MC-поток является частным случаем MAP-потока первого порядка, асинхронный и полусинхронный MC-потоки - частными случаями MAP-потока второго порядка. Как было отмечено выше, в реальных ситуациях интенсивность входящего потока событий изменяется со временем случайным образом, поэтому для реализации адаптивного управления системой массового обслуживания требуется решение следующих задач: 1) оценка состояний потока по наблюдениям за моментами наступления событий [11, 12]; 2) оценка параметров потока по наблюдениям за моментами наступления событий [13]. В работе [14] введен в рассмотрение модулированный обобщенный полусинхронный поток событий, относящийся к классу MAP-потоков второго порядка. В настоящей статье, являющейся непосредственным развитием работы [14], решается в полной мере задача оптимальной оценки состояний модулированного обобщенного полусинхронного потока событий. Предлагается алгоритм оптимальной оценки состояний, когда решение о состоянии потока выносится по критерию максимума апостериорной вероятности, представляющей наиболее полную характеристику состояния потока, которую можно получить, располагая только выборкой наблюдений. Сам критерий минимизирует полную вероятность ошибки вынесения решения [15]. 1. Постановка задачи Рассматривается модулированный обобщенный полусинхронный поток событий (далее - поток), интенсивность которого есть кусочно-постоянный стационарный случайный процесс X(t) с двумя состояниями , X2 (Х1 > X2). Длительность пребывания процесса X(t) (потока) в первом состоянии распределена по экспоненциальному закону с параметром р , во втором - с параметром а . Если процесс X(t) в момент времени t находится в первом (во втором) состоянии, то на полуинтервале [t, t + At), где At (здесь и далее) - достаточно малая величина, с вероятностью pAt + o(At) (с вероятностью aAt + o(At)) пребывание процесса X(t) в первом (во втором) состоянии закончится, и процесс X(t) с вероятностью единица перейдет из первого (второго) состояния во второе (в первое). В течение временного интервала случайной длительности, когда X(t) = Xi, имеет место пуассоновский поток событий с интенсивностью Xi , i = 1,2 . Кроме того, переход из первого состояния процесса X(t) во второе возможен в момент наступления события пу-ассоновского потока интенсивности Х1; переход осуществляется с вероятностью р (0 < p < 1); с вероятностью 1 - р процесс X(t) остается в первом состоянии (т.е. сначала наступает событие потока, затем происходит переход процесса X(t) из первого состояния во второе). Переход из второго состояния процесса X(t) в первое в момент наступления события пуассоновского потока интенсивности X2 невозможен. В момент окончания второго состояния процесса X(t) при его переходе с вероятностью единица из второго состояния в первое инициируется с вероятностью 5 (0 w (Хг- 11), i, J = 1,2 , i Ф J, то оценка состояния процесса есть X (t) = Xj . 2. Вывод апостериорной вероятности состояний модулированного обобщенного полусинхронного потока событий Момент вынесения решения будет принадлежать интервалу (tk, tk+1), k = 1,2,..., между соседними событиями потока. Для начального интервала (t0, t1) момент t будет лежать между началом наблюдения t0 и первым наблюденным событием потока. Рассмотрим интервал (tk, tk+1), значение длительности которого есть Tk = tk+1 -tk,k = 0,1,.... Для вывода формул апостериорной вероятности w (X1 11) используем известную методику [14]: сначала рассмотрим дискретные наблюдения через равные достаточно малые промежутки времени At, а затем совершим предельный переход при стремлении At к нулю. Пусть время меняется дискретно с шагом At: t = nAt,n = 0,1,.... Введем двумерный процесс (X(n),rn), где X(n)=X(nAt) - значение процесса X(t) в момент времени nAt (X(n) = X;,i = 1,2); rn = rn (At) = r (nAt) - r ((n -1) At) - число событий потока, наблюдаемых на интервале ((n-1)At,nAt) длительности At, rn = 0,1,.... Обозначим через Rm =(r0,r1,...,rm) последовательность числа событий за время от нуля до mAt на интервалах ((n -1) At, nAt) длительности At (n = 0, m). Здесь r0 - число событий, наблюдаемых на интервале (-At,0). Это число не определено, так как на этом интервале наблюдений не производится, поэтому его можно задать произвольным, например r0 = 0. Обозначим через Л(,я)=(x(0),X(1),...,X(m)) последовательность неизвестных (ненаблюдаемых) значений процесса X(nAt) в моменты времени nAt (n = 0, m ); x(0) = X (0) = Хг-,i = 1,2. Обозначим через w (X(m) | Rm) условную вероятность значения X(m) при условии, что наблюдалась реализация Rm. Аналогично w (x(m+1) | Rm+1). Для марковского случайного процесса (X(n), rn) в [7] получена рекуррентная формула, связывающая апостериорные вероятности w (X(m) | Rm) и w (x(m+1) | Rm+1): Х2 X — ( >R )p (, rm+1 | X(m), ^ ) - ( | Rm+1 ) = -T-X(m)=XX-, (2) X XX - (X(m)|Rm )p (, rm+1|X(m), rm ) X(m)=Xj X(m+1)=Xj где p(x(m+1),rm+1 | X(m),rm) - вероятность перехода процесса (X(n),rn) за один шаг At из состояния (X(m), rm) в состояние (x(m+1), rm+1). В рассматриваемом случае потока случайный процесс (X(n), rn), в силу предпосылок и его конструкции, является марковским, так что формула (2) имеет место. Лемма 1. В течение времени между моментами наступления соседних событий потока tk и tk+1,k = 0,1,..., апостериорная вероятность —(Х1 11) удовлетворяет дифференциальному уравнению — '(Х1 11) =а(1 -5)-(Х1 -Х2 +а + в-2a5)w(X1 11) + (Х1 -Х2-a5)w2(X1 11), tk < t < tk+1,к = 0,1,.... (3) Доказательство. Переходная вероятность p (x(m+1), rm+1 | X(m), rm) для потока в (2) запишется в виде p (X(m+1), rm+1|X(m), rm ) = p (Х^ХМ). p (rm ^X^, X^) ; X(m), X(m+1)=X1, X 2. (4) Принимая во внимание, что — (X(m)|Rm ) = — (X(m)|Rm (t )) = — (X(m)|t) , — (X(m| Rm+1 ) = — (X(m| Rm+1 (t + At)) = — (X(m+1) | t + At) , учитывая (4) и полагая в (2) для определенности X(m+1) = Х1, получаем (2) в виде X — (X Jt )p (Х1 | X , )p (rm+1|X , , X1 ) — (X1 11 + At ) = -^-. (5) XX — (Xs\t)p(Xj |X,)p( rm+1 |X,, X j) j=1 s=1 В силу определения потока величина rm+1 принимает только два значения: rm+1 = 0, rm+1 = 1. Здесь рассматривается поведение вероятности — (Х1 11) на полуинтервале [tk,tk+1) между соседними событиями потока, т.е. tk < t < tk+1; tk < t + At < tk+1. Тогда в (5) rm+1 = 0 и с учетом матрицы D0 в (1) на полуинтервале [t, t + At ) = [mAt, (m + 1)At) переходные вероятности (4) примут вид p (Х1 | Х1) p (rm+1 = 0|Х1, Х1 ) = 1 -(Х1 +e)At + o (At), p(X2 | X2)p(rm+1 = 0 | X2,X2) = 1 -(X2 +a)At + o(At), p (Х1 |X2) p (rm+1 = 0 | X 2, ) = (1 -5)aAt + о (At), p (X2 | ) p (rm+1 = 01X1, X2 ) = pAt + о (At). (6) Подставляя (6) в (5), учитывая, что w (X2 11) = 1 - w (X1 11), находим числитель А0 и знаменатель B0 в (5): А =(1 -5)aAt + (1 -(X1 +p)At-(1 -5)aAt) w (X1 11) + о (At), B0 = 1 -At [aS + X 2 +(X1 -X 2 -aS)w (X1 11 )] + о (At). Подставляя А0 и B0 в (5) и учитывая при этом, что B0-1 = 1 + At -[aS + X 2 +(X1 -X 2 -aS)w (X1 11 )] + о (At) (так как (1 - x) 1 = 1 + x + о (x) для достаточно малых x > 0), получаем w(X1 11 + At) - w(X1 11) = = At {a(1 -8)-(X1 -X2 +a + p- 2aS)w(X1 11) + (X1 -X2 -aS)w2(X1 |/)} + о(Дt). Деля здесь левую и правую части на At и переходя к пределу при At ^ 0 , находим (3). Лемма 1 доказана. Замечание 1. Уравнение (3) определяет поведение вероятности w (X1 11) на полуинтервале [tk,tk+1),k = 0,1,..., т.е. между моментами наступления событий, причем на правом конце полуинтервала имеет место значение w (X1 | tk+1 - 0), на основе которого, как будет показано в лемме 2, находится вероятность w (X1 | tk+1 + 0), являющаяся начальной для следующего полуинтервала [tk+1, tk+2 ) . Лемма 2. Апостериорная вероятность w (X1 11) в момент наступления события потока tk, k = 0,1,..., определяется формулой пересчета w (X |t + 0 )= a5 + [X1 С - p )-aS] w (X1| tk - 0) = w(X1 |tk + 0) = т——Г777-:-яч I ,—, k = 1,2,.... (7) X2 + aS + (X1 - X2 - aS) w (X1 | tk - 0) Доказательство. Пусть на интервале (t, t + At) в момент времени tk (t < tk < t + At) наступает событие потока ( rm+1 =1). Имеем два смежных интервала (t, tk), (tk, t + At) с длительностями tk -1 = At ', t + At -tk = At ". Тогда w(X« 11) = w(X« | tk -At'), « = 1,2; w(X1 11 + At) = w(X1 | tk + At") и (5) примет вид Xw(XJtk -At')p(X11X,)p(rm+1|X«,X1) w (X11 tk +At>-f=|-. (8) XXw(XJtk-At')p(Xj |X,)p( |X«, X j) j=1 «=1 С учетом матрицы D1 в (1) на интервале (t, t + At ) = (mAt, (m + 1)At) вероятности (4) запишутся в виде p (X1 |X1) p (rm+1 = 1|X1, X1 ) = (1 - p)^At + о (At), p (X 2 | X2 ) p (rm+1 = 1| X 2 , X 2 )=X2At + о (At) , p (41 | X2 ) p (rm+1 = 1| X2 , X1 ) = a5At + o (At) , p (X2 | X1 ) p (rm+1 = 1| X1, X2 ) = pX1 At + o (At) . (9) Подставляя (9) в (8), получаем числитель А1 и знаменатель B1 в (8): А = At((1 -p)Х1—(Х1 |tk-At') + а5— (Х2 |tk-At')) + o(At), B1 = At(X1— (X1 | tk -At') + (X2 +а5) — (X2 | tk -At')) + o(At). Подставляя А1 и B1 в (8), деля числитель и знаменатель на At, учитывая, что — (X 21 tk - At') = 1 - — (Х1 | tk - At'), и переходя к пределу при At ^ 0 (At' и At" одновременно стремятся к нулю), получаем (7). Лемма 2 доказана. Замечание 2. В точке tk вероятность — (Х1 11) претерпевает разрыв (имеет место конечный скачок). Тогда решение уравнения (3) будет зависеть от начального условия в момент времени tk, т.е. от — (Х1 | tk + 0),k = 1,2,.... В свою очередь, — (Х1 | tk + 0) зависит от значения — (Х1 | tk - 0) - значения вероятности — (Х1 11) в момент времени tk, когда — (Х1 11), определяемая в (3), изменяется на полуинтервале [tk-1,tk), соседнем с полуинтервалом [tk,tk+1),k = 1,2,.... Таким образом, в значении — (Х1 | tk + 0) «сосредоточена» вся предыстория наблюдений за потоком начиная от момента времени t0 = 0 до момента tk. В качестве начального условия — (Х1 110 + 0) = — (Х1 110 = 0) на полуинтервале [t0, t1) в (3) выбирается априорная финальная вероятность первого состояния процесса X(t): П = а / (а + в + pX1). (10) Леммы 1 и 2 позволяют сформулировать следующую теорему. Теорема. Поведение апостериорной вероятности — (Х1 11) на временном полуинтервале [tk,tk+1), k = 1,2,..., определяется явной формулой -b(t-t, —1 [—2 - — (Х1 | tk + 0)]- — 2 [—1 - — (Х1 | tk + 0)] — (x1|t)= "v-n "П"1 ^-, (U) —2 - — (X1 | tk + 0) -[—1 - — (X1 | tk + 0)] e-b(-tk) Х1 -X 2 +а+в- 2а5- b Х1 -X 2 +а + в- 2а5 + b —1 =-7-\-, —2 =-7-\-, 2 (Х1 -X 2-а5) 2 (Х1 -X 2-а5) b = -X2 -а + в)2 +4ав(1 -5), где tk < t < tk+1,k = 0,1,...; — (X1 110 + 0) = — (X1 110 = 0) = п1, определена в (10), — (X1 | tk + 0) - в (7). Доказательство. Уравнение (3) в лемме 1 представимо в виде ((— (Х1 11)-—1 )-1 -(— (Х1 11)-—2)-1)d— (Х1 11) = (Х1 -Х2 -а5)dt, (12) где — 1 и — 2 определены в (11). Интегрируя (12) в пределах от tk + 0 до t, получаем (11). Теорема доказана. Особый случай. Х1 - X2 - а5 = 0 . Тогда формула (11) примет вид , ч а(1 -5) w (А-1 11 ) = \ + а + р-а5 где tk < t < tk+1,k = 0,1,... . Формула (7) остается без изменения. Если к ограничению X1 - X2 - а5 = 0 добавить еще одно ограничение: (1 - p)X1 -a5 = 0, то тогда (7) запишется в виде w(X1 | tk + 0) = a5/(X2 +a5), k = 1,2,..., т.е. в этом случае апостериорная вероятность w (X1 11) не зависит от предыстории, а зависит только от ее значения в момент tk . Частный случай. Если p = 1, 5 = 0, то тогда w(X1 |tk + 0) = 0,k = 1,2,..., т.е. в этом случае апостериорная вероятность w (X1 11) также не зависит от предыстории, а зависит только от ее значения в момент tk . 3. Результаты численных расчетов Для получения численных результатов разработан алгоритм вычисления апостериорной вероятности w (X1 11) по формулам (7), (10), (11). Программа расчета реализована на языке программирования С#, Microsoft Visual Studio 2012. Первый этап расчета предполагает имитационное моделирование потока и как результат получение истинной траектории интенсивности потока X(t) и временных моментов t1, t2,... наступления событий потока. Описание алгоритма имитационного моделирования здесь не приводится, так как никаких принципиальных трудностей алгоритм не содержит. Второй этап расчета - непосредственное вычисление вероятностей w(X1 11), t0 < t < t1; w(X1 | tk + 0), k = 1,2,...; w(X1 11), tk < t < tk+1, а(1 -5) ' а + р-а5 -(a+p-a5)(t-tk w (Wtk + 0 )k = 1,2,..., по формулам (7), (10), (11) и построение оценки X(t). Расчеты произведены для следующих значений параметров: X1 = 8, X2 = 1, p = 0,2, р = 0,8, а = 0,5 , 5 = 0,8, число событий входящего потока m = 1000. Данное число событий определяет время моделирования. В качестве иллюстрации на рис. 2 приведена траектория (верхняя часть рис. 2) процесса X(t) (истинная траектория), полученная путем имитационного моделирования, и траектория (нижняя часть рис. 2) оценки X (t). X2 X1 Реализация оценки процесса X(t) X 2 0,5 1,0 1,5 2,0 2,5 Рис. 2. Траектория процесса X(t) и его оценки X (t) t 0 Вынесение решения о состоянии процесса A(t) производилось с шагом At = 0,001. На рис. 2 штриховкой на оси времени обозначены промежутки, на которых оценка состояния не совпадает с истинным значением процесса A(t) (область ошибочных решений). На рис. 3 приведена траектория поведения вероятности w 11), соответствующей полученной при имитационном моделировании последовательности наступления событий t1,t2,.... wftjt) Рис. 3. Траектория апостериорной вероятности w (Х111) Для установления частоты ошибочных решений о состояниях процесса A(t) по наблюдениям за потоком проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров n, , A2, p, р, а, 5 осуществляется моделирование потока событий на протяжении времени моделирования [0, Tm- ] (отдельный j-й эксперимент); 2) рассчитывается вероятность w (Х1 11) на отрезке [0, Tm- ] по формулам (7), (10), (11); 3) оценивается траектория процесса A(t) на отрезке [0, Tm- ] ; 4) осуществляется определение (для j-го эксперимента) d■ - суммарной протяженности интервалов, на которых истинная траектория процесса A(t) не совпадает с траекторией его оценки A (t); 5) вычисляется доля ошибочных решений p- = d- / Tm-; 6) Производится повторение N раз (- = 1, N) шагов 1-5 для расчета оценки безусловной (полной) вероятности ошибки принятия решения о состояниях процесса A(t). Результатом выполнения описанного алгоритма является выборка (p1,p2,...pN) долей ошибочных решений в N экспериментах. По этому набору вычисляются выборочное среднее безусловной вероятности ошибочного решения N „ N 2 P0 = (1/ N) X p- и выборочная дисперсия D = (1/ (N -1)) - - А) . -=1 -=1 Результаты статистического эксперимента приведены в табл. 1-5. В первой строке таблиц указан параметр, значение которого изменяется от опыта к опыту. Во второй и третьей строках приведены для каждого опыта численные значения P0 и D . При этом результаты получены при следующих значениях параметров: в табл. 1 для m = 1000, X2 = 3,5, p = 0,8, Р = 0,4, а = 0,4, 5 = 0,9, N = 100, в табл. 2 - для m = 1000, X1 = 14, X2 = 3,5, Р = 0,4, а = 0,4, 5 = 0,9, N = 100, в табл. 3 - для m = 1000, X1 = 14, X2 = 3,5, p = 0,8, а = 0,4, 5 = 0,9, N = 100, в табл. 4 - для m = 1000, X1 = 14, X2 = 3,5, p = 0,8, Р = 0,4, 5 = 0,9, N = 100, в табл. 5 - для m = 1000, X1 = 14, X 2 = 3,5, p = 0,8, Р = 0,4, а = 0,4, N = 100. Таблица 1 X! 7 8 9 10 11 12 13 14 Р0 0,0634 0,0560 0,0508 0,0449 0,0427 0,0385 0,0364 0,0339 D 0,00006 0,00006 0,00004 0,00004 0,00002 0,00002 0,00002 0,00003 Таблица 2 p 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 Р0 0,1417 0,1081 0,0813 0,0613 0,0530 0,0430 0,0378 0,0339 0,0300 0,0271 D 0,0002 0,0002 0,0001 0,00009 0,00005 0,00003 0,00003 0,00001 0,00001 0,00001 Таблица 3 Р 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 Р0 0,0344 0,0337 0,0340 0,0333 0,0332 0,0336 0,0331 0,0321 0,0325 0,0322 D 0,00001 0,00001 0,00002 0,00003 0,00002 0,00002 0,00001 0,00002 0,00002 0,00001 Таблица 4 а 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 Р) 0,0085 0,0172 0,0251 0,0333 0,0417 0,0492 0,0589 0,0654 0,0727 0,0804 0,00001 0,00001 0,00001 0,00002 0,00002 0,00003 0,00004 0,00004 0,00004 0,00005 Таблица 5 5 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 Р0 0,0334 0,0335 0,0335 0,0334 0,0339 0,0337 0,0335 0,0336 0,0338 0,0335 D 0,00001 0,00002 0,00001 0,00002 0,00002 0,00002 0,00002 0,00002 0,00002 0,00002 Отметим, что анализ проведенных многочисленных вариантов расчетов по нахождению оценки Р0 показывает, что Р0 является достаточно стабильной для m = 1000 событий потока. Вследствие этого m для всех экспериментов выбрано равным 1000 событий. Анализ результатов, приведенных в табл. 1-5, показывает, что тренд значений оценки Р0 в зависимости от X1 убывающий, так как при увеличении разности X1 -X2 условия различимости состояний потока улучшаются, при этом оценка D для всех вариантов расчета достаточно мала. Анализ результатов табл. 2 показывает, что значение оценки P0 уменьшается при увеличении вероятности перехода р из первого во второе состояние процесса A(t). Это связано с тем, что при увеличении параметра р процесс A(t) преимущественно будет находиться во втором состоянии, что улучшает условия различимости состояний потока. В случае табл. 3 значение вероятности перехода р = 0,8 достаточно велико, поэтому с вероятностью 0,8 в момент наступления события пуассоновского потока процесс A(t) переходит из первого состояния во второе и изменение параметра р не приводит к изменению оценки P0. Анализируя табл. 4, можно прийти к выводу, что при увеличении а значение оценки P0 также увеличивается. Это связано с тем, что при увеличении параметра а число переходов процесса A(t) из состояния A2 в состояние увеличивается, и поэтому условия различимости состояний потока ухудшаются. Анализ результатов табл. 5 показывает, что изменение параметра 5 не сказывается на величине оценки P0, так как длительность нахождения процесса A(t) в состоянии A2 определяется только параметром а. Заключение Полученные результаты показывают возможность оценивания состояний потока по результатам текущих наблюдений за потоком. Это позволяет изменять режимы работы системы обслуживания в зависимости от того или иного состояния потока. Выражения апостериорных вероятностей получены в явном виде, что позволяет производить вычисления без привлечения численных методов. Сам же алгоритм оценки состояний потока обеспечивает минимум безусловной (полной) вероятности ошибки вынесения решения.

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