Оптимальная оценка состояний обобщенного полусинхронного потока событий

ВЕСТНИК ТОМСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА

2010 Управление, вычислительная техника и информатика № 2

УДК 519.21

А.М. Горцев, А. А. Калягин, Л. А. Нежельская

ОПТИМАЛЬНАЯ ОЦЕНКА СОСТОЯНИЙ ОБОБЩЕННОГО ПОЛУСИНХРОННОГО ПОТОКА СОБЫТИЙ

Рассматривается задача оптимальной оценки состояний дважды стохастического полусинхронного потока с инициированием дополнительных событий (обобщенный полусинхронный поток), являющегося математической моделью информационных потоков, функционирующих в телекоммуникационных сетях. Находится явный вид апостериорных вероятностей состояний потока. Решение о состоянии потока выносится по критерию максимума апостериорной вероятности. Приведены численные результаты, полученные с использованием расчетных формул и имитационного моделирования.

Ключевые слова: обобщенный полусинхронный поток событий, состояние потока, апостериорная вероятность состояния, оценка состояния.

Системы и сети массового обслуживания (CMO, CeMO) являются широко распространенной математической моделью реальных физических, технических, экономических, информационных систем и сетей. В свою очередь, случайные потоки событий как основные элементы CMO и CeMO широко применяются в качестве математических моделей информационных потоков заявок, функционирующих в таких системах и сетях. В последние два десятилетия в связи с бурным развитием компьютерной техники и информационных технологий возникла важная сфера приложений теории массового обслуживания - проектирование и создание информационно-вычислительных сетей, спутниковых сетей связи, телекоммуникационных сетей и т.п. Все это можно объединить термином - цифровые сети интегрального обслуживания (Integrated Service Digital Networks - ISDN). Особенностью ISDN является передача по единым аппаратным средствам разнообразных видов информации (речевых сигналов в цифровом формате, интерактивных данных, видеосигналов и т.п.). Оказалось, что классические математические модели входящих потоков событий являются в той или иной степени непригодными для описания информационных потоков в ISDN. Все это дало толчок к построению новых математических моделей входящих потоков событий, достаточно адекватно описывающих реальные информационные потоки, функционирующие в ISDN. На практике параметры, определяющие входящий поток событий, известны либо частично, либо вообще неизвестны, либо (что еще больше ухудшает ситуацию) они изменяются со временем, при этом изменения часто носят случайный характер, что приводит к рассмотрению дважды стохастических потоков событий. Отметим, что одними из первых работ в этом направлении были статьи [1 - 3]. В [1,

2] введены в рассмотрение так называемые MC (Markov сИаш)-потоки, в [3] -MVP (Markov versatile processes)-потоки. Потоки событий с зависящей от времени интенсивностью, являющейся случайным процессом, можно разделить на два класса. К первому классу относятся потоки с интенсивностью, изменения которой являются непрерывным случайным процессом. Ко второму классу относятся потоки, у которых изменения интенсивности есть кусочно-постоянный случайный

процесс с конечным числом состояний. Последние (потоки с переключениями, или MC-потоки событий [1, 2]) - наиболее характерны для реальных телекоммуникационных сетей. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, MC-потоки можно разделить на три типа:

1) синхронные потоки событий - потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени, являющиеся моментами наступления событий [4 - 17];

2) асинхронные потоки событий - потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени и не зависит от моментов наступления событий [18 - 37];

3) полусинхронные потоки событий - потоки, у которых для одного множества состояний справедливо определение первого типа, а для остальных состояний справедливо определение второго типа [38 - 44].

Отметим, что синхронные, асинхронные и полусинхронные дважды стохастические потоки возможно представить в виде моделей MAP (Markovian Arrival Pro-cess)-потоков событий [45 - 47].

Режимы функционирования системы массового обслуживания непосредственно зависят от параметров дважды стохастического потока и состояний, в которых находится поток. Если система обслуживания функционирует в условиях полной (все параметры потока априорно неизвестны) либо частичной (часть параметров потока априорно неизвестна) неопределенности, то возникает задача оценки параметров потока по наблюдениям за потоком (по наблюдениям за моментами наступления событий) [7, 8, 10, 11, 13, 15 - 17, 25, 26, 29 - 35, 40 - 44]. Что касается состояний дважды стохастического потока событий, то даже тогда, когда поток функционирует в условиях отсутствия априорной неопределенности (параметры потока полностью известны), сказать о том, в каком состоянии находится поток в тот или иной момент времени без наблюдений за потоком, возможно только на основании априорных данных. В этом случае возникает задача оценки состояний потока событий (задача фильтрации интенсивности дважды стохастического потока) по наблюдениям за моментами наступления событий [4 - 6, 9, 12, 14, 18 -

24, 27, 28, 36 - 39].

В настоящей статье рассматривается дважды стохастический поток событий третьего типа - полусинхронный поток событий. Подчеркнем, что в [38, 39] решены задачи фильтрации, в [40 - 44] - задачи оценки параметров полусинхронно-го дважды стохастического потока событий в различных условиях, когда число состояний потока равно двум.

В данной статье решается задача об оптимальной оценке состояний полусин-хронного дважды стохастического потока с двумя состояниями и инициированием дополнительных (лишних) событий (далее обобщенный полусинхронный поток либо просто поток), т.е. результаты [38, 39] обобщаются на случай присутствия в полусинхронном потоке дополнительных (лишних) событий. Находятся выражения для апостериорных вероятностей состояний обобщенного полусинхрон-ного потока. Решение о состоянии потока выносится по критерию максимума апостериорной вероятности, представляющей наиболее полную характеристику состояния потока, которую можно получить, располагая только выборкой наблюдений, и обеспечивающей минимум полной вероятности ошибки вынесения решения [48].

1. Постановка задачи

Рассматривается обобщенный полусинхронный поток событий, интенсивность которого есть кусочно-постоянный случайный процесс Х(^ с двумя состояниями и Х2 (^1 > Х2). В течение временного интервала, когда Х(^ = Х, , имеет место пу-ассоновский поток событий с интенсивностью Х, , , = 1,2. Переход из первого состояния процесса Х(/) во второе возможен только в момент наступления события, при этом переход осуществляется с вероятностью р (0 < р < 1); с вероятностью 1 -р процесс Х(0 остается в первом состоянии. Тогда длительность пребывания процесса Х(0 в первом состоянии есть случайная величина с экспоненциальной функцией распределения ^ (т) = 1 - е-рХ‘т. Переход из второго состояния процесса Х(0 в первое состояние может осуществляться в произвольный момент времени. При этом длительность пребывания процесса Х(0 во втором состоянии распределена по экспоненциальному закону: ^2(т) = 1 -е~ат. При переходе процесса Х(/) из второго состояния в первое инициируется с вероятностью 5 (0 < 5 < 1) дополнительное событие в первом состоянии (т.е. сначала осуществляется переход, а затем инициируется дополнительное событие). Очевидно, что в сделанных предпосылках Х(0 - марковский процесс. Вариант возникающей ситуации приведен на рис. 1, где 1,2 - состояния случайного процесса Х(0; ^ , /2 ,... - моменты наступления событий; t4,... - моменты инициирования дополнительных событий с вероятностью 5.

/Г

ж-

N1.

t2 1-3 t4 1-5 1-6 Ь t8 t9 ^0 t11 t

Рис. 1. Формирование обобщенного полусинхронного потока

а

а

X

2

Если 5 = 0, то имеет место обычный полусинхронный поток событий [39-44]. Так как процесс Х(/) и типы событий (события пуассоновских потоков и дополнительные события) являются ненаблюдаемыми, а наблюдаемыми являются только временные моменты наступления событий ^ , /2 ,. , то необходимо по этим наблюдениям оценить состояние процесса (потока) Х(/) в момент окончания наблюдений.

Рассматривается установившийся (стационарный) режим функционирования потока событий, поэтому переходными процессами на интервале наблюдения (/0 , /), где /0 - начало наблюдений, t - окончание наблюдений (момент вынесения решения), пренебрегаем. Для вынесения решения о состоянии ненаблюдаемого процесса Х(^ в момент времени t необходимо определить апостериорные вероятности V (Х, | ^ ,..., т), , = 1,2, того, что в момент времени t значение процесса Х(^ = Х,

2

(т - количество наблюденных событий за время (), при этом 2^(Х, |^,...,tm) = 1.

,=1

Решение о состоянии процесса Х(^ выносится путем сравнения апостериорных вероятностей: если w(kj | ^ ,..., т) > ^(Х,- | tl ,..., т), , = 1,2, , Фу, то оценка состояния процесса есть Х (^ = Ху.

2. Вывод апостериорных вероятностей состояний потока

Вывод уравнений для апостериорных вероятностей осуществим при использовании известной методики [48]: сначала рассмотрим дискретные наблюдения через равные достаточно малые промежутки времени Л^ а затем совершим предельный переход при стремлении Лt к нулю. Пусть время меняется дискретно с конечным шагом Л^ t = kЛt, к = 0,1,. . Введем двумерный случайный процесс (Х(к), Гк), где Х(к) = Х(кЛ() - значение процесса Х(^ в момент времени t = кЛt (Х(к) = Х,- , , = 1,2), гк = Гк(Л^ = r[kЛt] - г[(к-1)Л/| - число событий обобщенного полусинхронного потока, наблюденных на временном интервале ((к-1)Л^ кЛ^ длины Лt, гк = 0,1,. .

Обозначим Гт = (г0,г1,...,гт) - последовательность наблюденных событий за

время от 0 до mЛt на интервалах ((к-1)Л^ кЛ^ длительности Лt, к = 0,т (г0 - число наблюденных событий на интервале (-Л^ 0); так как на этом интервале наблюдений не производится, то г0 можно задать произвольным, например г0 = 0);

Х т = (Х(0), Х(1),..., Х(т) ) - последовательность неизвестных (ненаблюдаемых) значений процесса Х(кЛ!) в моменты времени кЛ^ к = 0, т (Х(0) = Х(0) = Х,, = 1,2).

Обозначим через V (Хт, Гт) совместную вероятность значений Хт, Гт . Процесс (Х(к) , гк) - марковский, что вытекает из сделанных предпосылок и его конструкции. Действительно, обозначим: р(Х(к), гк |Х( ), Гк-1) - переходная вероятность

того, что Х(кЛ)= Х(к) и на полуинтервале [(к-1)Л^ kЛt) произошло гк событий потока при условии, что Х(/Л/)= Х(у) (у = 1,к -1) и на полуинтервалах [(/'-1)Л/, у Л),

(у = 1, к -1) наблюдалось Гу событий потока соответственно. Процесс Х(^ - марковский, т.е. его поведение после момента времени t = (к-1^ не зависит от предыстории до момента времени t = (к-1^ (длительность каждого состояния потока имеет экспоненциальное распределение). В каждом состоянии обобщенный полусинхронный поток ведет себя как простейший и дополнительные события инициируются в первом состоянии только в момент перехода процесса Х(^ из второго состояния в первое с постоянной вероятностью 5. Таким образом, поведение компоненты Гк также не зависит от предыстории до момента времени (к-1)Л^ В силу этого переходная вероятность

р(Х(к\ Гк|Х(к 1), Гк-1 ) = р(Х(к), Гк|Х(к^ Гк-1) .

Тогда совместная вероятность ^(Хт, Гт) представляется как произведение переходных вероятностей:

^ ^ т

М>(Х т , Гт ) = ^(Х(0) ,Г0 )П р(Х(к ), Гк |Х(к-1), Гк - ) ,

к=1

где р(Х(к), Гк | Х(к-1) ,гк-1) - вероятность перехода процесса (Х(Ш),Гк(А/)) за один шаг Лt из состояния (Х(к-1),Гк-1) в состояние (Х(к),Гк).

Рассмотрим переходную вероятность

р

Первый сомножитель в (1) запишется в виде р(Х(к) | Х(к-1),Гк-1) = р(Х(к) | Х(к-1)), так как на значение процесса Х(кА.) в момент времени . = кА. число наступивших на полуинтервале [(к-2)А., (к-1)А.), предшествующем полуинтервалу [(к-1)А., кА.), событий гк-1 не влияет в силу марковости процесса (Х(к),Гк). Второй сомножитель в (1) примет вид р(гк | Х(к-1),Гк-1, Х(к))= р(гк | Х(к-1), Х(к)), так как число событий гк, наблюденных на полуинтервале [(к-1)А., кА.) не зависит от числа событий гк-1, наблюденных на полуинтервале [(к-2)А., (к-1)А.), в силу того, что потоки событий в обоих состояниях процесса Х(.) пуассоновские, дополнительные же события инициируются с постоянной вероятностью 5. Таким образом, переходная вероятность (1) запишется в виде

р

Обозначим м(Х(к) | Гк) - апостериорная вероятность того, что в момент времени . = кА. состояние процесса Х(.) есть Х(к) (к = т,т+1; Х(к) = Х,, , = 1,2). Тогда, используя результаты, приведенные в [14], и выражение (2) для переходной вероятности, получаем рекуррентную формулу для апостериорной вероятности

Гт+1):

X м

м

X X м(х(т) | ;и)р(х(т+1) | Х(т))р(ги+11 Х(т),Х(т+

Х(т)=Х1 Х(т+1) =Х1

Совершим теперь предельный переход при А..—>0 в рекуррентном соотношении (3). Имеем м(Х(т+1) | Гт+1) = м(Х(т+1) | Гт+1 (. + А.)) = м(Х(”+1) | . + А.), м(Х(т) | Гт) = = м(Х(т) | Гт (.)) = м(Х(т) |.). Положим для конкретности в (3) Х(т+1) = Х1. Тогда (3) примет вид

X м

ХХМ

1 =1 5=1

Сначала рассмотрим случай, когда на интервале (., .+А.) нет событий (Гт+1 = 0) наблюдаемого потока (т.е рассмотрим поведение апостериорной вероятности м(Х1 | .) на интервале между моментами времени .,-1 и .). Подчеркнем, что этот случай означает, что на интервале (., .+А.) нет как событий пуассоновских потоков, так и дополнительных событий.

Рассмотрим произведение р(Х/ | Х5) р(Гт+1 = 0 | Х5, X,), 1,5 = 1,2, входящее в (4) (здесь и далее Х5 привязано к моменту времени . = тА1, Х, - к моменту времени (т+1) А.). В силу определения обобщенного полусинхронного потока событий вероятности перехода процесса Х(.) из состояния в состояние р(Х, | Х5) выпишутся в виде р(Х1 | Х1) = 1- рХ1А.+о(А.); р(Х2 | Х1) = рХ1А.+о(А.);

р(Х1 | Х2) = аА.+о(А.); р(Х2 | Х2) = 1-аА.+о(А.).

Рассмотрим вероятности р(Гт+1 = 0 | Х5, Х,) (1,5 = 1,2).

Имеем

/• ЛП 1 Ч р

р(Гт+1 = 0| Х5 , Х1 ) =---

Р

Р

I Х.)

р

Из (5) вытекает, что

р

Из определения обобщенного полусинхронного потока событий следуют формулы для вероятностей р(Х/ | Гт+1 = 0, Х5), 1,5 = 1,2:

р

Вероятность р(Гт+1 = 0 | Х1), входящая в (6), для ] = 1,2 описывает ситуацию, когда на полуинтервале [., .+А.) нет событий пуассоновского потока с параметром

Х1, так как дополнительное событие инициируется с вероятностью 5 только при переходе процесса Х(.) из второго состояния в первое, поэтому р(Гт+1 = 0 | Х1) = 1 -

- Х1А.+о(А.). Вероятность р(Гт+1 = 0 | Х2), входящая в (6), для ] = 1 описывает ситуацию, когда на полуинтервале [., .+А.) нет событий пуассоновского потока с параметром Х2 и нет дополнительного события, поэтому р(Гт+1 = 0 | Х2) = (1 - 5)(1 -

- Х2А.) + о(А.). Для ] = 2 вероятность р(Гт+1 = 0 | Х2) описывает ситуацию, когда на полуинтервале [., .+А.) нет событий пуассоновского потока с параметром Х2, поэтому в этом случае р(Гт+1 = 0 | Х2) = 1- Х2А.+о(А.). Подставляя эти формулы и формулы (7) для соответствующих 1 и 5 в (6), находим

р(Х1 | Х1) р(гт+1 = 0 | Х1, Х1) = 1-Х1А.+о(А.);

р

Подставляя выражения (8) в (4), производя при этом необходимые преобразования, получаем числитель А0 и знаменатель В0 в (4):

А0 =

В0 = 1-А.[Х1 м

Подставляя (9), (10) в (4), учитывая при этом, что

В01 = 1+А.[Х1 м(Х1 | .)+(а5+Х2) м(Х2 | .)]+о(А.), получаем (с точностью до членов о(А.)):

М(Х1 | .+А.) - М(Х1 | .) =

= -Х1 А. м(Х1 | .)+а(1-5)А. м(Х2 | .)+А. м(Х1 | .)[Х1 м(Х1 | .)+(а5+Х2) м(Х2 | .)] +о(А.). Деля левую и правую части последнего равенства на А., учитывая при этом, что м(Х2 | .) = 1 - м(Х1 | .), и переходя к пределу при А.—0, находим

^М

&

Полученное дифференциальное уравнение (11) определяет поведение апостериорной вероятности м(Х1 | .) на полуинтервале [.,-1 , .,), т.е. между моментами на-

ступления событий, причем на правом конце полуинтервала имеет место значение w(X1 | /,-0), на основе которого, как будет видно ниже, находится апостериорная вероятность w(X1 | .+0), являющаяся начальной для следующего полуинтервала

[. , А+1).

Рассмотрим случай наблюдения одного события (скажем, в момент времени ?,) на полуинтервале (., /+А/). В силу ординарности наблюдаемого потока варианты Гт+1 = 2,3,. имеют вероятность о(А.). Рассмотрим два смежных интервала (., .,), (. , . + А.). Длительность первого интервала: ^. = Д.', длительность второго:

. + А. - . = Д.". Тогда имеем ^(Х5 | () = ^(Х5 | . - Д.'), 5 = 1, 2; ^(Х1 | . + А.) = = w(X1 | и+ Д.") и (4) примет вид

X М,

w

XX ^

1=1 5=1

По-прежнему, рассмотрим произведение р(Х_;- | Х5) р(Гт+1 = 1 | Х5, ХД 1,5 = 1,2, входящее в (12). Тогда из (5), где нужно заменить Гт+1 = 0 на Гт+1 = 1, вытекает соотношение, аналогичное (6):

р

Из определения обобщенного полусинхронного потока событий следуют формулы для вероятностей р(Х_;- | Гт+1 = 1, Х5), 1,5 = 1,2:

р

Вероятность р(Гт+1 = 1 | Х1), входящая в (13), для ] = 1,2 описывает ситуацию, когда на полуинтервале [, /+А/) произошло событие пуассоновского потока с параметром Х1, так как дополнительное событие инициируется с вероятностью 5 только при переходе процесса Х(.) из второго состояния в первое, поэтому

р(Гт+1 = 1 | Х1) = = Х^+о^). Вероятность р(Гт+1 = 1 | Х2), входящая в (13), для 1 = 1

описывает ситуацию, когда на полуинтервале [., .+А.) произошло событие пуассо-новского потока с параметром Х2, а дополнительное событие не произошло, или обратную ситуацию, поэтому р(Гт+1 = 1 | Х2) = (1-5)X2А/+5(1-X2А/)+о(А/). Для 1 = 2 вероятность р(Гт+1 = 1 | Х2) описывает ситуацию, когда на полуинтервале [., .+А.) произошло событие пуассоновского потока с параметром Х2, поэтому в этом случае р(Гт+1 = 1 | Х2) = Х2А.+о(А.). Подставляя эти формулы и формулы (14) для соответствующих 1 и 5 в (13), находим

р(Х1 | Х1)р(Гт+1 = 1 | Х1, Х1) = (1-p)XlЛ/+о(Л/);

р(Х2 | Х1) р(Гт+1 = 1 | Х1, Х2) = pXlА/+о(А/);

р(Х1 | Х2) р(Гт+1 = 1 | Х2, Х1) = a5А/+о(А/);

р

Отметим, что для выражений (8),(15), с точностью до членов о^), выполняется условие нормировки

X X р(Х 1 | Х1)р(Гт+1 | X1, Х1 ) =

Гт+1 =0 1 =1

X X р(Х 1 | Х2)р(Гт+1 | Х2 , Х1 ) = 1+о(А.).

Гт+1 =0 1 =1

Подставляя выражения (15) в (12) и производя при этом необходимые преобразования, получаем числитель А1 и знаменатель В1 в (12):

А1 = А?[

В1 = А.[Х1 ^

Подставляя (16), (17) в (12), деля числитель и знаменатель на А, учитывая при этом, что ^(Х2 | Д. ')=1-^(Х1 | Д.'), и переходя к пределу при А^-0 (Д ’ и Д." одновременно стремятся к нулю), получаем

»<>,К +0) = -г+К1-р)Х. - а0]^

Х2 +а5 +

Таким образом, в точке . (момент наступления события) апостериорная вероятность ^(Х1 | .) претерпевает разрыв (имеет место конечный скачок). В качестве начального значения ^(Х1 | .0+0) = ^(Х1 | .0 = 0) можно выбрать априорную финальную вероятность первого состояния процесса Х(.): п1 = Иш п1(?) при .^да, для которой справедлива система алгебраических уравнений: рХ1п1-ап2 = 0, п1+п2 = 1. Откуда получаем п1 = а/(а+рХ1).

Решение дифференциального уравнения (11) на полуинтервале [ti , таким образом, будет зависеть от начального условия в момент времени , т.е. от ^(Х1 | .,+0), , = 0,1,. . Так как Х(.) марковский процесс, то существует предел ^(Х1 | .) при .^-да, не зависящий от . и начального условия: Иш ^(Х1 | .) = м> при .^-да. Тогда дифференциальное уравнение (11) при примет вид

Корни квадратного уравнения (19) определяются в виде

а

wl =--------------, w2 = 1,

1

в (20) предполагается, что а = Х1 - Х2 - а5 Ф 0. В зависимости от соотношения параметров X, , . = 1,2, а, 5 вероятность w(X1 | .) при .^-да будет стремиться либо к w1 , либо к w2 . Тогда дифференциальное уравнение (11) примет вид

1------------------1----- сЫ>0Л |.) = -ЬЖ ,

w(X1 | .) - w1 w(X1 | .) - w2 _

где Ь = ^2-^) а = Х1-Х2-а. Интегрируя (21) в пределах от и до ., находим явный

вид апостериорной вероятности w(X1 | .):

«О, |<) = » I1 - wСХ1 |.. + 0)] - 1“’ - >'^

1 - w

где Ь определено в (21); w(X1 | ..+0), w = w1 определены в (18), (20) соответственно; . .< . < .м, .=0,1,.; w(X1 | .0+0) = w(X1 | .0 = 0) = п1. В (22) имеют место следующие ситуации:

1) если Х1 - Х2 - а > 0, Х1 - Х2 - а5 > 0, 0 < 5 < 1, то 0 < w < 1 и Иш w(X1 | .) = w при .^да;

2) если Х1 - Х2 - а < 0, Х1 - Х2 - а5 > 0, 0 < 5 < 5* (5* = (Х1-Х2)/а < 1), то w > 1 и Иш w(X1 | .) = 1 при .^да;

3) если Х1 - Х2 - а < 0, Х1 - Х2 - а5 < 0, 5* < 5 < 1, то w < 0 и Иш w(X1 | .) = 1 при .^да.

Формулы (18), (22) позволяют сформулировать алгоритм расчета апостериорной вероятности w(k1 | і) и алгоритм принятия решения о состоянии процесса 1(і) в любой момент времени і:

1) в момент времени і0 = 0 задается w(k1 | і0+0) = ж (1-і | і0 = 0) = п1;

2) по формуле (22) рассчитывается вероятность ж(11 | і) в любой момент времени і (0 < і < і1), где і1 - момент наблюдения первого события потока;

3) по формуле (22) рассчитывается ж(11 | і) в момент времени і1 (Щ | і1) = = ж(11 | і1-0)), затем по формуле (18) производится пересчет апостериорной вероятности в момент времени і = і1, при этом ж(11 | і1+0) является начальным условием для ж(11 | і) на следующем шаге алгоритма;

4) по формуле (22) рассчитывается апостериорная вероятность ж(11 | і) для любого і (і1 < і < і2), где і2 - момент времени наступления второго события потока и т.д.

Параллельно, по ходу вычисления апостериорной вероятности ж

(ж(11 | і) > 1/2), то оценка X(і) = 11, в противном случае X(і) = 12 и т.д.

3. Частные и особые случаи

Представляет интерес рассмотреть частные случаи соотношения параметров

X. , . = 1, 2, р, а, 5 при а Ф 0.

1. Х1 - Х2 - а = 0, 0 < 5 < 1. Тогда а = а(1-5) > 0, w = 1. Дифференциальное урав-

нение (11) при этом примет вид

=аа-ад-л | «]=,

ш

его решение есть

w

(1|) 1 + а(1 - 5)[1 - w(X1 | ^ + 0)](. - ^) , (

где ^ . < .т,, = 0,1,. . Формула пересчета (18) примет вид

М1, |!, + 0) = “8+1<1 - р)Х1 - a51wСXl|t- - 0) , , - 1,2.

и< X - а(1 - 5)[1 - ч-О^и, - 0)]

Здесь формула (23) не вытекает из формулы (22) для общего случая.

2. р = 1, 5 = 0. Тогда а = Х1 - Х2 > 0, w = а/(Х1-Х2). При этом из формулы пересчета (18) следует, что w(X1 | .,+0) = 0, , = 1,2,. . Формула (22) поэтому выпишется в виде

w - we-ыt-.‘)

w

1 -we у

В (24) имеют место следующие ситуации:

1) если Х1 - Х2 - а > 0, то 0 < w < 1 и Иш w(X1 | .) = w при .^да;

2) если Х1 - Х2- а < 0, то w > 1 и Иш w(X1 | .) = 1 при .^да.

Для начального интервала изменения .: .0 < . < .1, справедлива формула (22), в которой w(X1 | .0+0) = п1 (п1 = а/(а+Х1)).

Таким образом, в данном частном случае апостериорная вероятность w(X1 | .) не зависит от предыстории, её поведение для любых , (,=1,2,.) определяется начальным значением, равным нулю.

3. Х1 - Х2 - а = 0, р = 1, 5 = 0. Тогда а = Х1-Х2, w = а/(Х1-Х2). Из формулы пересчета (18) следует, что w(X1 | ti+0) = 0, = 1,2,. . Для этого случая справедлива

формула (23), которая приобретает вид

w(Xl |.) = —aaС^—*1^ , . < /м, = 1,2,. , Иш w(X1 | .) = 1 при .^да.

1 + а

Для начального интервала (.0 < . < .) справедлива формула (23), в которой w(X1 | .0+0) = п1 (п1 = а/(а+Х1)).

Здесь так же, как и в частном случае 2, отсутствует зависимость апостериорной вероятности w(X1 | .) от предыстории.

4. Х1 - Х2 - а = (1-5) рХ1 , 0 < 5 < 1. Тогда а = (1-5)(а+рХ1), w = п1 = а/(а+рХ1). Формула (22) при этом примет вид

м,а |Л = п1[1 - w

1 1 - w(Xl | + 0) - [п - w(Xl | + 0)]е~(1-5)р%1(/-/‘) .

Так как w(X1 | .0 = 0) = п1 , то из (25) следует, что w(X1 | .) = п1 для .0 < . < . . Таким образом, и для . = .1 получаем w(X1 | .1 - 0) = п1 . Подставляя последнее в (18), находим w(X1 | .1 + 0) = п1 и т.д. Тогда w(X1 | .) = п1 для . > .0 . Это говорит о том, что при данном соотношении параметров информация о моментах наступления событий .1 ,., т не оказывает влияния на апостериорную вероятность w(X1 | .), т.е. в конечном итоге не влияет на качество оценивания состояний процесса Х(.). Решение о том или ином состоянии обобщенного полусинхронного потока выносится на основании априорных данных.

Рассмотрим частные случаи, когда а = 0.

1. Х1 - Х2 - а5 = 0. Отсюда следует, что равенство нулю достигается для 5* = (Х1 - Х2)/а, при этом Х1 - Х2 - а < 0. Дифференциальное уравнение (11) примет вид

dw

dt

. = - (Хі - Х2 - a)[1 - w^i | t)],

его решение есть

w(X1 | t) = 1 - [1 - w(X1 | t+0)] e(X-a)(t-ti) , ti < t < ti+1, i = 0,1,. ; lim w(X1 | t) = 1 при t^-да. Формула пересчета (18) запишется в виде

w(X1 | tt + 0) = — [Х1 - X2 + (X2 - pX1)w(X1 | tt - 0)], i = 1,2,. .

X1

2. X1 - X2 - a = 0, 5 = 1. Тогда дифференциальное уравнение (11) примет вид dw(X1 | t)/dt = 0, ti< t < ti+1, i = 0,1,. . Отсюда следует, что w(X1 | t) = const,-, ti < t < ti+1, i = 0,1,. . Формула пересчета (18) при этом запишется в виде

w

X1

Так как w(X1 | t0 = 0) = n1 (n1 = a/(a+pX1)), то w(X1 | t) = п1 для t0 < t < t1 . Таким

образом, и для t = t1 получаем w(X1 | t1-0) = п1. Подставляя последнее в (26), находим w(X1 | t1+0) = п1 и т.д. Тогда w(X1 | t) = п1 для t > t0. Здесь также, как и в частном случае 4 для а Ф 0, отсутствует зависимость от моментов наступления событий t1 ,., tm, и решение о том или ином состоянии потока выносится на основании априорных данных.

В заключение отметим, что при p = 0 обобщенный полусинхронный поток вырождается в простейший, так как переходы во второе состояние процесса X(t) отсутствуют. В этом случае п = 1 и из формул (22), (18) следует, что w(Xj | t) = 1 для

t > to.

4. Результаты численных расчетов

Для получения численных результатов разработан алгоритм вычисления апостериорной вероятности w(k1 | t) по формулам (18), (22). Программа расчета реализована на языке программирования Borland C++, Builder 6. Первый этап расчета предполагает имитационное моделирование обобщенного полусинхронного потока событий. Описание алгоритма имитационного моделирования здесь не приводится, так как никаких принципиальных трудностей алгоритм не содержит. Второй этап - непосредственное вычисление вероятностей w(Xj | t,+0), w(Xj | t) по

формулам (18), (22) и определение оценки X(t). Расчеты произведены для следующих значений параметров: X = 4, Х2 = 2, p = 0,025, а = 0,02, 5 = 0,2 и времени моделирования T = 100 ед. времени. В качестве иллюстрации на рис. 2 приведена траектория (нижняя часть рис. 2) случайного процесса X(t), полученная путем имитационного моделирования, где 1,2 - состояния процесса X(t), и траектория

(верхняя часть рис. 2) оценки X(t), где 1,2 - состояния оценки X(t). Вынесение решения о состоянии процесса X(t) производилось с шагом At = 0,001. На рис. 2 штриховкой на оси времени обозначены временные промежутки, на которых оценка состояния не совпадает с истинным значением процесса X(t) (области ошибочных решений). На рис. 3 приведена траектория поведения апостериорной вероятности w(Xj | t), соответствующая полученной при имитационном моделировании последовательности моментов наступления событий tb t2... .

МЧi I i i I i i i I I t

1 I I I I I

2 i    i I i

0 10 20 30 40 50 60 70 80 90 t

Рис. 2. Траектории процесса X

Рис. 3. Траектория апостериорной вероятности w

Для установления частоты ошибочных решений о состоянии случайного процесса X(t) по наблюдениям за обобщенным полусинхронным потоком событий проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров Xb X2, Р, а, 5 осуществляется моделирование обобщенного полусинхронного потока на заданном отрезке времени [0, T] (отдельный i-й эксперимент); 2) осуществляется расчет апостериорной вероятности w(X1 | t) первого состояния процесса X(t) на заданном отрезке [0, T] по формулам (18), (22); 3)осуществляется оценивание траектории процесса X(t) (оценивание на

отрезке [0, T] интервалов, когда оценка X(t) принимает то или иное значение);

4) осуществляется определение (для отдельного г-го эксперимента) dг - суммарной протяженности интервалов, на которых значение процесса X(t) не совпадает с

его оценкой X(t); 5) осуществляется вычисление доли ошибочных решений pг = d/T; 6) осуществляется повторение N раз (i = 1,N) шагов 1 - 5 для расчета

оценки безусловной (полной) вероятности ошибки оценивания состояний процесса X(t) на отрезке [0,7].

Результатом выполнения описанного алгоритма является выборка

pj,p2,...,pN долей ошибочных решений в N экспериментах. По этому набору вычисляются выборочное среднее безусловной вероятности ошибочного решения

NN

Pо = (1/ N)X Рi и выборочная дисперсия D = (1/(N -1))X (Рг - Pо )2.

г=1 i =1

Результаты статистического эксперимента приведены в табл. 1 - 5. В первой строке таблиц указано время моделирования обобщенного полусинхронного потока событий T (T = 100, 300,., 1700 ед. времени). Во второй и третей строках таблиц для каждого времени моделирования T приведены численные значения

для Pо и D соответственно.

Результаты получены при следующих значениях параметров, общих для всех таблиц: Х2 = 2, p = 0,025, а = 0,02, 5 = 0,2, N = 100. При этом результаты в табл. 1 получены для Xi = 4, в табл. 2 - для Xj = 5, в табл. 3 - для Xj = 6, в табл. 4 - для Xj = 7, в табл. 5 - для X1 = 8.

Т аблица 1

Результаты статистического эксперимента

T 100 300 300 700 900 1100 1300 1300 1700

P О 0,1833 0,130б 0,1347 0,1378 0,1б37 0,1б40 0,1б42 0,1б43 0,1бб9

D 0,0173 0,00б1 0,0032 0,0028 0,0024 0,0017 0,0017 0,0017 0,0013

Т аблица 2

Результаты статистического эксперимента

T 100 300 300 700 900 1100 1300 1300 1700

P О 0,1390 0,1224 0,1144 0,1112 0,1134 0,1118 0,1137 0,1130 0,1131

D 0,0104 0,0023 0,0014 0,0012 0,0009 0,000б 0,0003 0,0003 0,0003

Т аблица 3

Результаты статистического эксперимента

T 100 300 500 700 900 1100 1300 1500 1700

P о 0,0811 0,0834 0,0782 0,0806 0,0795 0,0801 0,0814 0,0807 0,0812

D 0,0026 0,0011 0,0007 0,0005 0,0004 0,0003 0,0002 0,0002 0,0002

Т аблица 4

Результаты статистического эксперимента

T 100 300 500 700 900 1100 1300 1500 1700

P о 0,0656 0,0619 0,0616 0,0618 0,0606 0,0625 0,0612 0,0606 0,0612

D 0,0019 0,0005 0,0003 0,0002 0,0002 0,0001 0,0001 0,0001 0,0001

Т аблица 5

Результаты статистического эксперимента

T 100 300 500 700 900 1100 1300 1500 1700

P о 0,0531 0,0510 0,0485 0,0493 0,0492 0,0504 0,0488 0,0482 0,0490

D 0,0012 0,0004 0,0003 0,0001 0,0001 0,0001 0,0001 0,0001 0,0001

Анализ численных результатов, приведенных в табл. 1 - 5, показывает:

1) для всех вариантов расчета оценка безусловной вероятности ошибочного

решения Pо является достаточно стабильной для T > 100 ед. времени;

2) при фиксированном T оценка Po уменьшается в зависимости от X1 (X1 = 4, 5, 6, 7, 8 ), что является естественным, так как состояния процесса X(t) при этом становятся лучше различимыми;

3) при данных значениях параметров алгоритм оптимальной оценки состояний обощенного полусинхронного потока обеспечивает приемлемую оценку безусловной вероятности ошибочного решения, при этом выборочная дисперсия оценки достаточно мала.

Заключение

Полученные результаты показывают возможность оценивания состояний обобщенного полусинхронного потока событий по результатам текущих наблюдений в течение некоторого временного интервала за потоком.

Выражения (18), (22) для оценки состояний обобщенного полусинхронного потока получены в явном виде, что позволяет производить вычисления без привлечения численных методов. Сам же алгоритм оценки состояний потока обеспечивает минимум полной вероятности ошибки вынесения решения.

Наконец, отметим, что рассмотренный обобщенный полусинхронный поток событий охватывает ранее изученные модели потоков, вытекающие из него как частные случаи: 1) полусинхронный дважды стохастический поток событий [38 -

41, 43, 44], для которого 5 = 0; 2) синхронно-альтернирующий дважды стохастический поток событий [8,11,13], для которого X1 = X, X2 = 0, 5 = 0.

ЛИТЕРАТУРА

1. Башарин Г.П., Кокотушкин В.А, Наумов В.А. О методе эквивалентных замен расчета фрагментов сетей связи // Изв. АН СССР. Техническая кибернетика. 1979. № б. С. 92 -99.

2. Башарин Г.П., Кокотушкин В.А, Наумов В.А. О методе эквивалентных замен расчета фрагментов сетей связи // Изв. АН СССР. Техническая кибернетика. 1980. № 1. С. 33 - б1.

3. Neuts M.F. A versatile Markov point process // J. Applied Probability. 1979. V. 1б. P. 7б4 -779.

4. Нежельская Л.А. Нелинейная оптимальная фильтрация дважды стохастического потока с инициативными событиями // Тез. докл. Всес. науч.-технич. конф. «Микросистема -91», 8 - 12 октября 1991, Суздаль. М.: Всесоюзное общество информатики и вычислительной техники, 1991. С. 2б - 28.

3. Нежельская Л.А. Рекуррентные формулы для апостериорных вероятностей при оценке состояний синхронного MC-потока событий // Распределенные микропроцессорные управляющие системы и локальные вычислительные сети: материалы Всес. науч-технич. конф., июнь 1991, Томск. Томск: Изд-во ТГУ, 1991. С. 181 - 182.

6. Нежельская Л.А. Моделирование биотехнологических процессов дважды стохастическими потоками с инициативными событиями // Тез. докл. Междунар. конф. по проблемам моделирования в бионике «Биомод-92», 21 - 2б июня 1992, Санкт-Петербург. М.: Российское общество информатики и вычислительной техники, 1992. С. 83 - 8б.

7. Горцев А.М., Нежельская Л.А. Оценка параметров синхронного MC-потока событий // Сети связи и сети ЭВМ (анализ и применение): тез. докл. Восьмой Белорусской зимней школы-семинара по теории массового обслуживания. Минск: Изд-во БГУ, 1992. С. 33.

8. Горцев А.М., Нежельская Л.А. Оценка параметров синхронно-альтернирующего пуас-соновского потока событий методом моментов // Радиотехника. 1993. № 7 - 8. С. б - 10.

9. Нежельская Л.А. Оптимальная оценка состояний синхронного MC-потока событий // Избр. докл. Междунар. конф. «Всесибирские чтения по математике и механике». Т. 1. Томск: Изд-во ТГУ, 1997. С. 97 - 102.

10. Горцев А.М., Нежельская Л.А. Оценивание параметров синхронного дважды стохастического потока событий методом моментов // Вестник ТГУ. Приложение. 2002. № 1(1). С. 24 - 29.

11. Горцев А.М., Нежельская Л.А. Оценивание длительности мертвого времени и параметров синхронного альтернирующего потока событий // Вестник ТГУ. Приложение. 2003. № б. С. 232 - 239.

12. Бушланов И.В., Горцев А.М. Алгоритм оптимальной оценки состояний синхронного дважды стохастического потока событий // Вестник ТГУ. Приложение. 2003. № б. С.220 - 224.

13. Василевская Т.П., Горцев А.М., Нежельская Л.А. Оценивание длительности мертвого времени и параметров синхронного альтернирующего потока с проявлением либо не-проявлением событий // Вестник ТГУ. Приложение. 2004. № 9(II). С. 129 - 138.

14. Бушланов И.В., Горцев А.М. Оптимальная оценка состояний синхронного дважды стохастического потока событий // Автоматика и телемеханика. 2004. № 9. С. 40 - 31.

13. Горцев А.М., Нежельская Л.А. Оценивание длительности «мертвого» времени и интенсивностей синхронного дважды стохастического потока событий // Радиотехника. 2004. № 10. С. 8 - 1б.

16. Горцев А.М., Нежельская Л.А. Синхронный дважды стохастический поток событий при продлевающемся мертвом времени // Теория вероятностей, случайные процессы, математическая статистика и приложения: материалы Междунар. конф. Минск: Изд-во БГУ, 2003. С. б0 - б9.

17. Бушланов И.В., Горцев А.М., Нежельская Л.А. Оценка параметров синхронного дважды стохастического потока событий // Автоматика и телемеханика. 2008. № 9. С. 7б - 93.

18. Горцев А.М., Нежельская Л.А. Оптимизация параметров адаптора при наблюдениях за MC-потоком // Стохастические и детерминированные модели сложных систем. Новосибирск: Изд-во ВЦ СО АН СССР, 1988. С. 20 - 32.

19. Горцев А.М., Нежельская Л.А. Статистическое оценивание состояний дважды стохастического пуассоновского процесса // Перспективные методы планирования и анализа экспериментов при исследовании случайных полей и процессов: тез. докл. III Всес. конф., 27 - 29 сентября 1988, Гродно. М.: Изд-во МЭИ, 1988. С. 124 - 125.

20. Горцев А.М., Нежельская Л.А. Алгоритм оценивания состояний МС-потока // Сетемет-рия, анализ и моделирование информационно-вычислительных сетей. Куйбышев: Изд-во Куйбышевского ун-та, 1988. С. 28 - 38.

21. Горцев А.М., Нежельская Л.А. Оптимальная нелинейная фильтрация марковского потока событий с переключениями // Техника средств связи. Сер.: Системы связи. 1989. Вып. 7. С. 46 - 54.

22. Горцев А.М., Шевченко Т.И. Оценка состояний МС-потока событий при наличии ошибок измерений // Сети связи и сети ЭВМ как модели массового обслуживания: тезисы докладов Седьмой белорусской зимней школы-семинара по теории массового обслуживания. Минск: Изд-во БГУ, 1991. С. 48 - 49.

23. Горцев А.М., Шевченко Т.И. Аналитическое решение интегрального уравнения в задаче оценивания состояний МС-потока событий // Материалы Всес. науч.-технич. конф. «Микросистема-22», сентябрь 1992, Калининград. Томск: Изд-во ТГУ, 1992. С. 63 - 66.

24. Горцев А.М., Нежельская Л.А., Шевченко Т.И. Оценивание состояний МС-потока событий при наличии ошибок измерений // Изв. вузов. Физика. 1993. № 12. С. 67 - 85.

25. Горцев А.М., Завгородняя М.Е. Оценка параметров альтернирующего потока событий при условии его частичной наблюдаемости // Тез. докл. VII Белорусской математической конференции. Ч. 3, 18 - 22 ноября 1996, Минск. Минск: Изд-во БГУ, 1996. С. 3, 4.

26. Горцев А.М., Завгородняя М.Е. Оценка параметров альтернирующего потока событий при условии его частичной наблюдаемости // Оптика атмосферы и океана. 1997. Т. 10. № 3. С. 273 - 280.

27. Горцев А.М., Шмырин И.С. Оптимальный алгоритм оценки состояний МС-потока событий при наличии ошибок в измерениях моментов времени // Оптика атмосферы и океана. 1998. Т. 11. № 4. С. 419 - 429.

28. Горцев А.М., Шмырин И.С. Оптимальная оценка состояний дважды стохастического потока событий при наличии ошибок в измерениях моментов времени // Автоматика и телемеханика. 1999. № 1. С. 52 - 66.

29. Горцев А.М., Паршина М.Е. Оценивание параметров альтернирующего потока событий в условиях «мертвого времени» // Изв. вузов. Физика. 1999. № 4. С. 8 - 13.

30. Горцев А.М., Шмырин И.С. Оптимальная оценка параметров дважды стохастического пуассоновского потока событий при наличии ошибок в измерениях моментов наступления событий // Изв. вузов. Физика. 1999. № 4. С.19 - 27.

31. Васильева Л.А., Горцев А.М. Оценивание параметров дважды стохастического потока событий в условиях его частичной наблюдаемости // Автоматика и телемеханика. 2002. № 3. С. 179 - 184.

32. Васильева Л.А., Горцев А.М. Оценивание длительности мертвого времени асинхронного дважды стохастического потока событий в условиях его неполной наблюдаемости // Автоматика и телемеханика. 2003. № 12. С. 69 - 79.

33. Горцев А.М., Ниссенбаум О.В. Оценивание длительности мертвого времени и параметров асинхронного альтернирующего потока событий с инициированием лишнего события // Вестник ТГУ. 2004. № 284. С. 137 - 145.

34. Горцев А.М., Ниссенбаум О.В. Оценивание длительности мертвого времени и параметров асинхронного альтернирующего потока событий при непродлевающемся мертвом времени // Изв. вузов. Физика. 2005. № 10. С. 35 - 49.

35. Горцев А.М., Нежельская Л.А. Оценивание параметров асинхронного потока с инициированием лишнего события методом моментов // Вестник ТГУ. Приложение. 2006. № 18. С. 267 - 273.

36. Горцев А.М., Ниссенбаум О.В. Оптимальная оценка состояний асинхронного альтернирующего потока с инициированием лишних событий // Вестник Тюмен. гос. ун-та. 2008. № 6. С. 107 - 119.

37. Горцев А.М., ЛеоноваМ.А., Нежельская Л.А. Оптимальная оценка состояний асинхронного дважды стохастического потока с инициированием лишних событий // Массовое обслуживание: потоки, системы, сети: материалы Междунар. науч. конф. «Современные математические методы анализа и оптимизации информационно-телекоммуникационных сетей», 2б - 29 января 2009. Минск: РИВШ, 2009. С. 90 - 9б.

38. Нежельская Л.А. Алгоритм оценивания состояний полусинхронного потока событий с учетом мертвого времени // Массовое обслуживание: потоки, системы, сети: материалы Четырнадцатой Белорусской зимней школы-семинара по теории массового обслуживания. Минск: Изд-во бГу, 1998. С. 18 - 21.

39. Нежельская Л.А. Оптимальное оценивание состояний полусинхронного потока событий в условиях его частичной наблюдаемости // Вестник ТГУ. 2000. № 2б9. С. 93 - 98.

40. Горцев А.М., Нежельская Л.А. Оценивание параметров полусинхронного дважды стохастического потока событий методом моментов // Вестник ТГУ. Приложение. 2002. № 1(I). С. 18 - 23.

41. Горцев А.М., Нежельская Л.А. Оценивание периода мертвого времени и параметров полусинхронного дважды стохастического потока событий // Измерительная техника. 2003. № б. С. 7 - 13.

42. Горцев А.М., Нежельская Л.А. О рекуррентности дважды стохастических потоков событий // Вестник ТГУ. Приложение. 2003. № 14. С.2З8 - 2бб.

43. Горцев А.М., Нежельская Л.А. Полусинхронный дважды стохастический поток событий при продлевающемся мертвом времени // Массовое обслуживание: потоки, системы, сети: материалы Междунар. науч. конф. «Математические методы повышения эффективности информационно-телекоммуникационных сетей», 29 января - 1 февраля 2007, Гродно. Минск: РИВШ, 2007. С. б8 - 78.

44. Горцев А.М., Нежельская Л.А. Полусинхронный дважды стохастический поток событий при продлевающемся мертвом времени // Вычислительные технологии. 2008. Т. 13. № 1. С. 31 - 41.

43. Lucantoni D.M. New result on the single server queue with a batch markovian arrival process // Communications in Statistics Stochastic Models. 1991. V. 7. P. 1 - 4б.

46. Lucantoni D.M., Neuts M.F. Same steady - state distributions for the MAP/SM/1 queue // Communications in Statistics Stochastic Models. 1994. V. 10. P. 373 - 398.

47. Дудин А.Н., Клименок В.И. Системы массового обслуживания с коррелированными потоками. Минск: Изд-во БГУ, 2000. 173 с.

48. Хазен Э.М. Методы оптимальных статистических решений и задачи оптимального управления. М.: Сов. радио, 19б8. 23б с.

Горцев Александр Михайлович

Калягин Алексей Андреевич

Нежельская Людмила Алексеевна

Томский государственный университет

E-mail: gam@fpmk.tsu.ru; redall@inbox.ru Поступила в редакцию 13 февраля 2010 г.