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

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

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

УДК 519.21

А.М. Горцев, М. А. Леонова

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

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

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

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

ность есть кусочно-постоянный случайный процесс с конечным числом состояний. Последние (потоки с переключениями или МС-потоки событий [1,2]) являются наиболее характерными для реальных телекоммуникационных сетей. В свою очередь, в зависимости от того, каким образом происходит переход из состояния в состояние, МС-потоки можно разделить на три типа: 1) синхронные дважды стохастические потоки событий - потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени, являющиеся моментами наступления событий [4 - 6]; 2) асинхронные дважды стохастические потоки событий - потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени и не зависит от моментов наступления событий [7, 8]; 3) полусинхронные дважды стохастические потоки событий - потоки, у которых для одного множества состояний справедливо 1, а для остальных состояний справедливо 2 [9 - 11]. Наконец, подчеркнем, что отмеченные синхронные, асинхронные и полусинхронные потоки событий возможно представить в виде моделей МАР (Markovian Arrival Process) - потоков событий [12, 13] с определенными ограничениями на параметры последних [14]. При исследовании дважды стохастических потоков событий могут быть выделены два класса задач: 1) задача фильтрации интенсивности потока (или задача оценивания состояний потока событий) по наблюдениям за потоком (по наблюдениям за моментами наступления событий) [7, 15]; 2) задача оценивания параметров потока по наблюдениями за моментами наступления событий [4 - 6, 8 - 11].

Одними из первых работ по оценке состояний дважды стохастических потоков, по-видимому, являются [7, 16], в которых рассматривается асинхронный дважды стохастический поток событий с двумя состояниями.

В настоящей статье решается задача об оптимальной оценке состояний асинхронного дважды стохастического потока с инициированием дополнительных событий [17]. В данной статье находятся выражения для апостериорных вероятностей состояний обобщенного асинхронного потока событий. Решение о состоянии потока выносится по критерию максимума апостериорной вероятности, представляющей наиболее полную характеристику состояния потока, которую можно получить, располагая только выборкой наблюдений, и обеспечивающей минимум полной вероятности ошибки вынесения решения [18].

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

Рассматривается асинхронный дважды стохастический поток с инициированием лишних событий (далее обобщенный асинхронный поток), интенсивность которого есть кусочно-постоянный случайный процесс X(t) с двумя состояниями Xj и X2 (Xj> X2). В течение временного интервала, когда X(t) = X, , имеет место пуассо-новский поток событий с интенсивностью X, , i = 1, 2. Переход из первого состояния процесса X(t) во второе (из второго в первое) может осуществляться в произвольный момент времени. При этом длительность пребывания процесса X(t) в i-м состоянии распределена по экспоненцильному закону с параметром а, , i = 1,2. При переходе процесса X(t) из первого состояния во второе инициируется с вероятностью p (0 <p < 1) дополнительное событие во втором состоянии (т.е. сначала осуществляется переход, а затем инициируется дополнительное событие). Наоборот, при переходе процесса X(t) из второго состояния в первое инициируется с ве-

роятностью q (0 < q < 1) дополнительное событие в первом состоянии. Очевидно, что в сделанных предпосылках 1(0 - марковский процесс. Вариант возникающей ситуации показан на рис. 1, где 1, 2 - состояния случайного процесса 1(0; ^, 4,... - моменты наступления событий; /2, 4,... - моменты инициирования дополнительных событий; /2 - момент инициирования с вероятностью р дополнительного события во втором состоянии; /6 - момент инициирования с вероятностью q дополнительного события в первом состоянии.

1

^3 1:4 4 ^6 ^ . . .

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

2

Если р = q = 0, то имеет место обычный асинхронный поток [8]. Так как переходы процесса 1(0 из состояния в состояние не привязаны к моментам наступления событий пуассоновских потоков, то в названии потока присутствует слово «асинхронный». Так как процесс 1(0 и типы событий (события пуассоновских потоков и дополнительные события) являются ненаблюдаемыми, а наблюдаемыми являются только временные моменты наступления событий ^, 4,..., то необходимо по этим наблюдениям оценить состояние процесса (потока) 1(0 в момент окончания наблюдений.

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

2

событий за время 0, при этом ^ю(Х, |^,...,tm) = 1. Решение о состоянии процесса

,=1

1(0 выносится путем сравнения апостериорных вероятностей: если ю(1,| t,,..., т) >

> ю(1,| ti,..., т), ,=1,2, 1ф], то оценка состояния процесса есть ку) = X.

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

Вывод уравнений для апостериорных вероятностей осуществим, используя известную методику [18]: сначала рассмотрим дискретные наблюдения через равные достаточно малые промежутки времени At, а затем совершим предельный переход при стремлении Лt к нулю. Пусть время меняется дискретно с конечным

шагом М: t = kAt, к = 0, 1,. Рассмотрим двумерный процесс (1(к), гк), где

1(к) = 1(kAt) - значение процесса 1(0 в момент времени kЛt (1(к) = 1,, , = 1, 2), гк = rk(At) = r[kAt] - r[(k-1)At] - число событий, наблюденных на временном интервале ((к-1)Л^ МО длины Лt, гк = 0,1,. Обозначим гт = (г0, гь..., гт) - последовательность наблюденных событий за время от 0 до mЛt на интервалах ((к - 1)Л, kЛt) длительности Лt, k = 0,т (г0 - число наблюденных событий на интервале (-Л^ 0); так как на этом интервале наблюдений не производится, то его можно задать произвольно, например, г0 = 0); Х(т) = (1(0),1(1),..., 1(т)) - последовательность неизвестных (ненаблюдаемых) значений процесса 1(кЛ0 в моменты времени кЛ^ k = 0,т (1(0) = 1(0) = 1! , , = 1, 2). Обозначим через ю(Х(т), гт) совместную вероятность значений Х(т), тт. Процесс (1(k), гк) - марковский, что вытекает из сделанных предпосылок и его конструкции. Тогда совместная вероятность ю(Х(т), тт) представляется как произведение переходных вероятностей

т

( m), Тт ) = Ю(k(0), Г0)ПР (к( k ),Г! |Х(!-1),‘Гк-Д k=1

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

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

Р

Первый сомножитель в (1) запишется в виде р(к(к)|к(к-1),гк_1) = р(к(к)|к(к_),

так как на значение процесса 1(кД0 в момент времени kЛt число наблюденных событий гк-1 на полуинтервале [(к-2)Л^ (k-1)Лt) совершенно не влияет (процесс 1(кД0 «живет своей жизнью»), значение же 1(к - 1) процесса 1((к - 1)Д0 в момент времени (k-1)Лt не зависит от предыстории в силу марковости процесса 1(0. Рассмотрим второй сомножитель в (1). Имеем, во-первых, р(гк |к(к_1),гк_1,к(к)) = р(гк |к(к-1),к(к)), так как число событий гк , наблюденных на полуинтервале [(к-1)Д, kДt), не зависит от числа событий гк-1 , наблюденных на полуинтервале [(к-2)Д; (k-1)Дt), в силу того, что потоки событий в обоих состояниях процесса 1(0 пуассоновские. Пусть гк = 0. Тогда, для 1(к-1) = 11, 1(к)= 11 имеем

р(Гк = 0 |к(к-1) =%1, к(к) = ^) =

= р(гк = 0, к(к-1) =к1, к(к) =кх)1 р(к(к-1) =к1, к(к) =к1) =

= р(к(к) =к1 |гк =0, к(к-1) =к1)р(гк = 0 | к(к-1) =кг)/р(к(к) =к1 |к(к-1) =к1) =

= р(гк = 0 | к(к-1) = кД

Аналогично находятся

р(Гк = 0 |к(к-1) = к!, к(к) = к2) = р(Гк = 0 |к(к-1) = к!); р(гк = 0 |к(к-1) = к2, к(к) =к1) = р(гк = 0 |к(к-1) = к2); р(Гк = 0 |к(к-1) = к2, к(к) =к2) = р(гк = 0 |к(к-1) = к2).

Итак, получаем р(гк = 0 |Х(к !), Х(к)) = р(гк = 0 |Х(к !)). Подобным образом находятся р(гк = 1 |Х(к-1), Х(к)) = р(гк = 1 |Х(к-1)). Случаи гк = 2, 3,..., в силу ординарности наблюдаемого потока, имеют вероятность о(Д).

Окончательно имеем р(гк |Х(к-1),гкЧ,Х(к)) = р(гк |Х(к-1)). Таким образом, переходная вероятность (1) примет вид

р(Х(к), гк |Х(к-1), Гк_1) = р(Х(к) |Х(к-1))р(Гк |Х(к-1)).

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

ш(Х(т+1)| гт+1):

Х2

X ЦХ

х( т)=х

“

£ X2 ю

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

Совершим теперь предельный переход при Л/^-0 в рекуррентном соотношении (2). Имеем

ю(Х(т+1) | Гт+1) = ю(Х(т+1) | Гт+1 ( + А/)) =  (Х^ | + А/) ,

Ю(Х(т)|Гт ) = Ю(Х(т)|Гт (/)) = ю(Х(т)|/).

Положим для конкретности в (2) Х(т+1)= Хь Тогда (2) примет вид

2

Хга

ХХЮ

1=1 *=1

Сначала рассмотрим случай, когда на интервале (/, /+М) нет событий наблюдаемого потока (т.е. рассмотрим поведение апостериорной вероятности ю(Х1|/) на интервале между наблюденными событиями, скажем, между моментами времени /,-1 и /,).

В силу определения обобщенного асинхронного потока ситуация, когда осуществляется переход процесса Х(/) из первого состояния во второе и дополнительное событие при этом не инициируется, имеет вероятность р(Х2|Х1) = = (1-р)а1А/+о(А/). Аналогичная ситуация, когда осуществляется переход процесса Х(/) из второго состояния в первое и дополнительное событие также не инициируется, имеет вероятность р(Х1|Х2) = (1-д)а2Л/+о(Л/). Так как в первом и втором состояниях потоки пуассоновские, то р(гт+1=0|Х*) = 1 - Х*Л/ + о(Л/), * = 1, 2. Вероятности р(Х1|Х1) = 1 - а1Д/ + о(Л/), р(Х2|Х2) = 1 - а2Л/ + о(Л/). Подставляя все эти выражения в (3), находим числительА0 и знаменатель В0 в (3):

А =

В0 =1-Д/[(Х1 + />а1)со(Х1 \) + (X2 + да2)со(Х2 \)] + о(Д/).

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

В0-1 = 1 + А/[

ю(Х1 |/ + А/) _ю(Х1 |/) = _А/(Х1 + а1)ю(Х1 |/) + А/(1 _д)а2ю(Х2 |/) +

+А/ю(Х1 |/)[(Х1 + ра1)ю(Х1 |/) + (Х2 + да2)ю(Х2 |/)] + о(А/).

Деля левую и правую части последнего равенства на А/, учитывая при этом, что ю(Х2 |/) = 1 _ю(Х1 |/), и переходя к пределу при А/^-0, находим

аЮ(Х1 ^) = (1 _ д)а2 _ [Х! _Х2 + а1 + (1 _ 2д)а2]ю(Х1 |/) + а/

+

Полученное дифференциальное уравнение (6) определяет поведение апостериорной вероятности ю(Х1|/) на полуинтервале [/,-1 , /,), т.е. между моментами наступления событий, причем на правом конце полуинтервала имеет место значение ю(Х1|/,—0), на основе которого, как будет видно ниже, находится апостериорная вероятность ю(Х1|/,+0), являющаяся начальной для следующего полуинтервала [и , 4н).

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

^И

ХХ“

1=1 *=1

Рассмотрим числитель А1 выражения (7):

А1 = Ю(Х1 |/, _А/ ’) р(Х1 |Х1) р(гт+1 |Х1) + ю(Х2 |/, _А/ ’) р(Х1 |Х 2 ) р(гт+1 Р+

Здесь возможны следующие варианты: 1) процесс Х(/) на интервале (/, / + Д/) не перешел во второе состояние и на этом интервале произошло событие пуассоновского потока с параметром Х1 (вероятность этого варианта есть р(Х1|Х1) р(гт+1 = 1| Х1) = (1-а1А/+о(А/)) (Х1Д/+о(Д/))=Х1Д/+о(Д/)); 2) процесс Х(/) на интервале (/, /+Д/) перешел из второго состояния в первое, при этом сыницииро-валось дополнительное событие и событие пуассоновского потока с параметром Х2 не произошло (вероятность этого варианта есть р(Х1|Х2) р(гт+1=0| Х2) = = (да2А/ + о(А/)) (1 - Х2Д/ + о(Д/)) = да2Д/ + о(Д/)). Другие варианты имеют вероятность о(Д/). Тогда А1 будет иметь вид

А1 = А/[Х1ю

Аналогично находится выражение для знаменателя В1 выражения (7):

В1 = А/[

Подставляя (8), (9) в (7), учитывая при этом, что ю(Х2\ґ-Аґ')=1-ю(Х1\ґ-Аґ'), и переходя к пределу при Аґ^-0 (АҐ и А/" одновременно стремятся к нулю), получаем

»

Х2 + да2 +

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

Решение дифференциального уравнения (6) на полуинтервале [/,, ґі+1), таким образом, будет зависеть от начального условия в момент времени , т.е. от ю(Х1\/,+0), і = 0, 1,... . Так как Х(ґ) - марковский процесс, то существует предел ю(Х1\/) при ґ^-да, независящий от ґ и от начального условия: Ііш со(Х1\/) = ю1, при /^•да. Тогда уравнение (6) при ґ^-да примет вид:

Корни уравнения (11) определяются после необходимых преобразований в виде

[Х1 -Х2 +а1 + (1 - 2д)а2 ] -д/(Х1 -Х2 +а1 -а2)2 +4а1а2(1 - р(1 -д) ґл ,ч

ю1 =--------------------------------------------------------------------- ,

2

[-Х2 + а1 + (1 -2д)а2] + д/^ -Х2 + а1 -а2)2 + 4а^2(1 -р(1-д) ҐЛ^

ю2 =---------------------------------------------------------------------.

2

В (12), (13) предполагается, что а = Х1- Х2+ ра1 - да2 Ф 0, при этом 0 < о1 < 1,

о2 > 1 для а > 0; 0 < о1 < 1, о2 < 0 для а < 0. С учетом (12), (13) уравнение (6) выпишется в виде

1

ю1 -ю2

1 1

_ю(Х1 \/)-ю1 ю(Х1 \/)-ю2 _

ёю

Интегрируя (14) в пределах от до /, находим явный вид апостериорной вероятности ю(Х1\/):

. )= Ю1 [2 -ю

1 ю2 -ю(Х1 \ ґг + 0) -[ -ю(Х1 \ Ґг + 0)]а|>2-И1)(/-/і-) ,

где а определена в (12), (13), Ґі < ґ < /і+1 , і = 0,1,.

Формулы (10), (15) позволяют сформулировать алгоритм расчета апостериорной вероятности ю(Х1\ґ) и алгоритм принятия решения о состоянии процесса Х(ґ) в любой момент времени ґ:

1) в момент времени ґ0 = 0 задается ю(Х1\/0+0) = ю(Х1\/0=0) = п1;

2) по формуле (15) рассчитывается вероятность ю(Х1\ґ) в любой момент времени ґ (0 < ґ < ґ1), где ґ1 - момент наблюдения первого события потока;

3) по формуле (15) рассчитывается ю(Х1\ґ) в момент времени ґ1 (ю(Х1\/1) = = ю(Х1\ґ1-0)), затем по формуле (10) производится пересчет апостериорной вероятности в момент времени ґ = ґ1, при этом ю(Х1\ґ1+0) является начальным условием для ю(Х1\ґ) на следующем шаге алгоритма;

4) по формуле (15) рассчитывается апостериорная вероятность для лю-

бого t (^ < t < /2), где /2 - момент времени наступления второго события потока и т.д.

Параллельно по ходу вычисления апостериорной вероятности ю(Х1|/) в момент времени / выносится решение о состоянии процесса Х(/): если ю(Х1|/) >

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

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

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

1. Х1+да1 = Х2+ра2 , р Ф д. Тогда ю1 = п1 = а2/(а1+а2), ю2 = (1-д)/(р-д),

Так как ю(Х1\/0 +0) = п1 ,то из (16) следует, что ю(Х1\ґ) = п1 для ґ0 < ґ < ґ1 , т.е. ю(Х1\ґ1-0) = п1. Тогда из (17) вытекает, что ю(Х1\ґ1+0) = п1 и т.д.

Таким образом, имеем ю(Х1\ґ) = п1 для ґ > ґ0 . Последнее говорит о том, что при таком соотношении параметров информация о моментах наступления событий ґ1, ..., ґт не оказывает влияния на апостериорную вероятность ю(Х1\ґ), т.е. в конечном итоге не влияет на качество оценивания состояний процесса Х(ґ). Решение о том или ином состоянии обобщенного асинхронного потока выносится на основании априорных данных.

2. Х1+да1 = Х2+ра2 , р = д. Тогда дифференциальное уравнение (6) примет вид

Так как ю(Х1\ґ0+0) = п1, то из (18) следует, что ю(Х1 \ґ) = п1 (ґ0 < ґ < ґ1), т.е. ю(Х1\ґ1-0) = п1. Тогда из (19) вытекает, что ю(Х1\ґ1+0)=п1 и т.д. Таким образом, получаем ю(Х1 \ґ)=п1 для ґ > ґ0 (результат, аналогичный результату первого частного случая).

3. Подкоренное выражение в (12), (13) равно нулю. Данная ситуация возможна в двух случаях:

3.1. а >0, р = 1, 0 < д < 1, Х1 - Х2 = а2 - а1. Тогда дифференциальное уравнение (6) может быть представлено как

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

ю2 -ю(Х1 \ ґі + 0) -[ -ю(Х1 \ ґі + 0)]е ь(Ґ Ґі

где Ь = (1-д) а1+(1-р) а2 , Ґі < ґ < ґг+1 , і = 0,1,.

, і = 1,2,...

\Ґ) = (1- д)(а1 +а2) [П| -ю(Х1 |0],

аґ

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

ю(Х1 \ґ ) = п1 +[ю(Х1 \ґг + 0) -п1 ](1-д)( а1+а2

ґі < ґ < ґі+1 , і = 0,1,. Формула пересчета (10) примет вид

Х 2 + да 2

, і = 1,2,....

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

ю

11 1 + (1 -д)а2 [1 -ЦМ/. + 0)](/-/г) ,

и < / < /,+ , , = 0,1,. . Формула пересчета (10) выпишется в виде

«,(>, |. + 0)- д“2- +(Х' ~““2>Ю(Х1|/- ~0) , , = 1,2,...

х2 + да2 +

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

3.2 а < 0, д = 1, 0 <р < 1, X - Х2 = а2 - а1. Тогда дифференциальное уравнение (6) будет иметь следующий вид:

Л

—-— = -(1 -рН (Я,1 |/),

ш

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

---------а

1 +

и < / < /,+1 , , = 0,1,. . Формула пересчета (10) выпишется в виде

Ю(М, + 0)= а2 + ('Л -0) , , 1,2,...

Х2 +а2 -

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

4. Х1 - Х2 + а1 + (1 - 2д)а2 = 0, 0 < д < 1. Данное соотношение параметров имеет место только для а < 0. Тогда дифференциальное уравнение (6) примет вид

Лю(!"11/) = (1 - д)“2 -[(1 - р)“1 + (1 - д)“2 ]2(х11/),

Ш

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

,-\1‘с + ю

э(Х, \ґ) = V-------------------р-;=-----------^—-—-

Ыс +ю

где с = (1 - д)а2/[(1 - р)а1 + (1 - д)а2], Л = 2(1 - д)а2/>1с, < / < /,+1 , , = 0, 1,.

Формула пересчета (10) примет вид

<М, + 0) =----д“2 + 0-1 - да2 (^1 \1, - , 1,2,.

Х2 + да2 -[

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

5. Х1- Х2+а1 +(1-2д)а2 = 0, 0 <р < 1, д = 1. Данный частный случай полностью совпадает с частным случаем 3.2.

6. Х1Х2 = рда1а2 , 0 <р < 1, 0 < д < 1, Х2 Ф 0, Х1 Ф да1. Последнее ограничение вытекает из того, что отмеченная связь параметров влечет за собой равенство а = (1/Х1)(Х1-да2)(Х1+ра1). Тогда а Ф 0, если Х1 Ф да2. Для расчета апостериорной вероятности ю(Х1|/) справедлива формула (15). Формула пересчета (10) при этом приобретает вид

ю

Таким образом, в данном частном случае апостериорная вероятность ю(Х11/) не зависит от предыстории. Изучим смысл апостериорной вероятности (23). Обозна-

чим (А, Х(0) = Х1) - событие, заключающееся в том, что в момент времени т = 0 событие обобщенного асинхронного потока наступило и процесс Х(т) в момент т = 0 находится в первом состоянии. Обозначим (А, Х(0) = Х1, Х(-Дт) = Х5) - событие, заключающееся в том, что в момент времени т = 0 событие обобщенного асинхронного потока наступило, процесс Х(т) в момент т = 0 находится в первом состоянии, а в момент времени т = -Дт процесс Х(ґ) находился в 5-м состоянии (^ = 1, 2). Так как рассматривается стационарный режим функционирования потока, то вероятность события (А, Х(0) = Х1) запишется в виде

Р(А, Ц0) = Х1) = Р( Ц-Дт) = Х1) Р(А, Ц0) = Х1 \ Ц-Дт)= Х1) +

+ Р( Х(-Дт) = Х2) Р(А, Ц0) = Х1 \ Ц-Дт)= Х2).

Учитывая, что Р( Х(-Дт) = Х1) = п1, Р( Х(-Дт) = Х2) = п2 =1- п1, и принимая во внимание, что, с точностью до членов о(Дт), Р(А, Х(0) = Х1 \ Х(-Дт) = Х1) = = Х1Дт +о(Дт), Р(А, Х(0) = Х1 \ Х(-Дт)= Х2) = да2Дт+о(Дт), находим Р(А, Х(0) = Х1) = п1Х1 Дт + п2да2Дт + о(Дт).

Аналогично имеем

Р(А, Х(0) = Х2) = л2Х2Дт + п1ра1Дт + о(Дт).

Тогда, используя формулу Байеса, находим апостериорную вероятность того, что в момент времени т=0 процесс Х(т) находится в первом состоянии при условии, что в момент т=0 наступило событие обобщенного асинхронного потока, в виде

Р

а1

Подставляя в (24) Х2=рда1а2 / Х1, получаем (23). Таким образом, ю(Х1\ґі+0) в рассматриваемом случае - апостериорная вероятность того, что процесс Х(ґ) в момент времени ґ,+0 находится в первом состоянии при условии, что в момент времени Ґ, наступило событие обобщенного асинхронного потока, і=1 ,2,________ Для об-

щего случая ю(Х1\ґі+0) - апостериорная вероятность того, что процесс Х(ґ) в момент времени ґ,+0 находится в первом состоянии при условии, что в моменты времени ґ1,_, /г-1 наступили события обобщенного асинхронного потока. Отметим, что в рамках отмеченной связи имеют место и частные случаи 3.1, 3.2, 4, 5.

Рассмотрим особые случаи, когда а = 0 (в выражениях (12), (13) имеет место деление на ноль).

1. р Ф д, 0 < р < 1, 0 < д < 1. Тогда Х1+ра1 = Х2+да2 (вариант д = 0 при этом не реализуем, так как в этой ситуации имеем Х2 > Х1 , что противоречит постановке задачи). Тогда дифференциальное уравнение (6) примет вид

\Ґ) = (1 - д)а2 -[(1 - р)а1 + (1 - д)а2]со(Х1 \ґ),

аґ

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

ю

где Р = (1 -р)а1 +(1 -д)а2 , Ґ, < Ґ < Ґі+1 , і = 0,1,_ Формула пересчета (10) выпишется в виде

ю

Х 2 + да 2

2. p ф q, 0<p <1, 0< q <1, Х^а2 , Х2 = раь Для расчета апостериорной вероятности ю(Хі|0 справедлива формула (25). Формула пересчета (10) при этом приобретет вид

ю(Х1 |/г- + 0) = qa2/(ра1 + qa2) , і = 1,2,...

Таким образом, в данном особом случае получили результат, аналогичный результату частного случая 6: апостериорная вероятность ю(Х1|/) не зависит от предыстории.

3. p = q, 0< q <1. Тогда (25) примет вид

ю

и < і < ґі+1, і = 0, 1,. . Формула пересчета запишется в виде (26). Так как ю(Х1|/0+0) = п1, то из (27) следует, что ю(Х1|і) = п1 для і0 < і < і1 , т.е. ю(Х1|і 1-0) = п1. Тогда из (26) вытекает, что ю(Х1|/1+0) = п1 и т.д. Таким образом, имеем ю(Х1|і) = п1 для і > і0. Получили результат, аналогичный результату частного случая 1.

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

Для получения численных результатов разработан алгоритм вычисления апостериорной вероятности ra(Xi|0 по формулам (10), (15). Программа расчета реализована на языке программирования C++ в среде Builder 6. Первый этап расчета предполагает имитационное моделирование обобщенного асинхронного потока событий. Описание алгоритма имитационного моделирования здесь не приводится, так как никаких принципиальных трудностей алгоритм не содержит. Второй этап расчета - непосредственное вычисление вероятностей ю(Х1|/,+0), ю(Х1|/) по формулам (10), (15) и определение оценки X(t). Расчеты произведены для следующих значений параметров: Х1 = 3, Х2 = 0,5, а1 = 0,03, а2 = 0,04, p = 0,7, q = 0,9 и времени моделирования T = 100 ед. времени. В качестве иллюстрации на рис. 2 приведена траектория (нижняя часть рисунка) случайного процесса X(t), полученная путем имитационного моделирования, где 1, 2 - состояния процесса X(t), и траектория (верхняя часть рисунка) оценки X(t), где 1, 2 - состояния оценки X(t). Вынесение решения о состоянии процесса X(t) производилось с шагом At = 0,05. На рис. 2 штриховкой на оси времени обозначены временные промежутки, на которых оценка состояния не совпадает с истинным значением процесса X(t) (области ошибочных решений). На рис. 3 приведена траектория поведения апостериорной вероятности ш(Х1 |t), соответствующая полученной при имитационном моделировании последовательности моментов наступления событий t1, t2,...

X

i

2

X

i

t

0 i0 20 30 40 50 60 70 80 90 t

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

ю

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

Для установления частоты ошибочных решений о состоянии случайного процесса Х(/) по наблюдениям за обобщенным асинхронным потоком проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров Хь Х2, а1, а2, р, д осуществляется моделирование обобщенного асинхронного потока на заданном отрезке времени [0, Т ]; 2) рассчитываются апостериорные вероятности ю(Х1|/) первого состояния процесса Х(0 на заданном отрезке [0, Т ] по формулам (10), (15); 3) оцениваются траектории процесса Х(0 (оценивание на отрезке [0, Т ] интервалов, когда оценка Х(/) принимает то или иное значение); 4) определяется (для г-го эксперимента) - суммарная протяжен-

ность интервалов, на которых значение процесса Х(/) не совпадает с его оценкой Х(/); 5) вычисляется доля ошибочных решений рг = й^Т; 6) осуществляется повторение N раз (г = 1, N) шагов 1 - 5 для расчета оценки безусловной вероятности ошибки оценивания состояний процесса Х(/) на отрезке [0, Т ].

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

1 N 1 N

Р0 = — ^рг и выборочная дисперсия Г =---------^(Р0 - рг )2.

Ni =1 N - 1 г=1

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

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

Анализ численных результатов, приведенных в табл. 1 - 5, показывает: 1) для всех вариантов расчета оценка безусловной вероятности ошибочного решения Р0 является достаточно стабильной для Т > 100 ед. времени; 2) при фиксированном Т оценка Р0 уменьшается в зависимости от Х1 (Х1 = 4, 5, 6, 7, 8), что является естественным; 3) при заданных значениях параметров алгоритм оптимальной оценки состояний обобщенного асинхронного потока обеспечивает приемлемую оценку безусловной вероятности ошибочного решения, при этом выборочная дисперсия оценки достаточно мала.

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

т 100 300 500 700 900 1100 1300 1500 1700

Ро 0,1683 0,1575 0,1642 0,1563 0,1799 0,1635 0,1634 0,1878 0,1619

Ь 0,0146 0,0121 0,0142 0,0163 0,0151 0,0147 0,0109 0,0159 0,0133

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

т 100 300 500 700 900 1100 1300 1500 1700

Р0 0,0711 0,0756 0,0637 0,0691 0,0712 0,0872 0,0687 0,0786 0,0788

Ь 0,0029 0,0038 0,0027 0,0038 0,0038 0,0061 0,0026 0,0032 0,0038

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

т 100 300 500 700 900 1100 1300 1500 1700

Р0 0,0401 0,0428 0,0354 0,0441 0,0396 0,0446 0,0405 0,0428 0,0444

Ь 0,0011 0,0012 0,0010 0,0015 0,0016 0,0014 0,0013 0,0013 0,0014

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

т 100 300 500 700 900 1100 1300 1500 1700

Р0 0,0279 0,0284 0,0230 0,0274 0,0290 0,0240 0,0280 0,0273 0,0249

Ь 0,0005 0,0008 0,0004 0,0006 0,0007 0,0007 0,0005 0,0006 0,0005

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

т 100 300 500 700 900 1100 1300 1500 1700

Р0 0,0181 0,0192 0,0179 0,0171 0,0182 0,0197 0,0213 0,0177 0,0202

Ь 0,0002 0,0002 0,0002 0,0002 0,0004 0,0003 0,0003 0,0002 0,0003

Заключение

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

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

20], для которого p = q = 0; 2) асинхронный альтернирующий дважды стохастический поток событий [21, 22], для которого X1 = X, ^ = 0, p = 0, q = 0; З) асинхронный альтернирующий дважды стохастический поток с инициированием дополнительных событий [2З, 24], для которого X1 = X, X2 = 0, p = q = i (либо p = i, q = 0, либо p = 0, q = 1); 4) асинхронный дважды стохастический поток с инициированием дополнительных событий [23], для которого p = q = i.

ЛИТЕРАТУРА

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

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

3. NeutsM.F. A versatile Markov point process // J. Appl. Probab. 1979. V. 1б. P. 7б4 - 779.

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

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

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

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

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

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

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

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

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

13. Machihara F.A. A MAP/SM/1 queue with service times depending on the arrival process // Symposium on Perfomance Models for Information Communication Networks: Proc. Conf., Tokyo. 1997. P. 1S0 - 191.

14. Василевская Т.П., Завгородняя М.Е., Шмырин И.С. О соотношении моделей МАР-потока событий и асинхронного, полусинхронного и синхронного дважды стохастических потоков событий // Вестник ТГУ. Приложение. 2004. № 9(II). С. ^S - 144.

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

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

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

18. Хазен Э.М. Методы оптимальных статистических решений и задачи оптимального управления. М.: Сов. радио, 1986. 256с.

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

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

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

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

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

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

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

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

Леонова Мария Алексеевна

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

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