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

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

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

ОБРАБОТКА ИНФОРМАЦИИ

УДК 519.21

DOI: 10.17223/19988605/47/2

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

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

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

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

Дважды стохастические потоки событий можно разделить на два класса: первый класс составляют потоки, интенсивность которых есть непрерывный случайный процесс [1]; второй - потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным (произвольным) числом состояний. Впервые результаты исследований потоков второго класса опубликованы практически в одно и того же время, в 1979 г., в работах [2, 3]. В [2] указанные потоки получили название MC (Markov chain)-потоки; в [3] - MVP (Markov versatile processes)-™™^. В статьях [4, 5] описанные выше потоки называют также MAP (Markov Arrival Process)-потоками событий. С использованием моделей дважды стохастических потоков событий возможно исследование финансово-экономических процессов [6], биофизических процессов [7], процессов управления запасами [8] и др. Отметим, что MC-потоки событий (MAP-потоки) являются наиболее характерной и подходящей моделью потоков в реальных телекоммуникационных сетях, в частности в широкополосных сетях беспроводной связи вдоль протяженных транспортных магистралей [9-18]. Зарубежными и отечественными исследователями при описании подобных входящих потоков событий в СМО используются термины «дважды стохастические потоки событий», MAP-потоки, MC-потоки.

В статье [19] предложена классификация MAP-потоков на MAP-потоки первого порядка и MAP-потоки второго порядка в зависимости от возможных вариантов смены состояний интенсивно-

сти потока. Класс МАР-потоков первого порядка составляют потоки, у которых смену состояний интенсивности определяет одна случайная величина; вследствие этого смена состояний происходит в случайные моменты времени, в которые событие потока может наступить или не наступить: 1) синхронные потоки (потоки, у которых состояние интенсивности меняется в случайные моменты времени, являющиеся моментами наступления событий) [20]; 2) собственно МАР-потоки как обобщение синхронных потоков [21]. Класс МАР-потоков второго порядка составляют потоки, у которых смена состояний интенсивности определяется двумя независимыми случайными величинами так, что смена состояний происходит в случайные моменты времени, в которые событие потока может наступить или не наступить: 1) модулированные МАР-потоки [22]; 2) обобщенные асинхронные потоки [23], являющиеся обобщением асинхронных потоков, или, что то же самое, ММРР-потоков (потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени и не зависит от моментов наступления событий) [24]; 3) обобщенные полусинхронные потоки [25] как обобщение полусинхронных потоков (потоки, у которых одна часть состояний интенсивности меняется в моменты наступления событий потока (свойство синхронных потоков), другая часть состояний интенсивности меняется в произвольные моменты времени, не связанные с моментами наступления событий потока (свойство асинхронных потоков)).

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

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

Рассматривается обобщенный асинхронный поток, сопровождающий процесс (интенсивность) А,(/) которого есть кусочно-постоянный случайный процесс с п состояниями: принимает значения из дискретного множества значений {АЬ...,Ап}, А1 > А2 >...> Ап > 0. Будем говорить, что имеет место 7-е состояние процесса А^), если А(г) = А, г = 1,п , п = 2,3,.... Если имеет место 7-е состояние процесса А^), то в течение временного интервала, когда А(г) = А1, имеет место пуассоновский поток событий с параметром (интенсивностью) Аг, г = 1,п . Длительность пребывания процесса А(?) (потока) в 7-м состоянии распределена по экспоненциальному закону с параметром аг: ^ (т) = 1 - е , т > 0, г = 1, п . Процесс А^) является принципиально ненаблюдаемым (А^) - скрытый случайный процесс); наблюдаемыми являются моменты времени t1, t2,...,tk,... наступления событий потока. Рассматривается стационарный режим функционирования потока, поэтому переходными процессами на полуинтервале наблюдения |/0, ^, где 10 - начало наблюдения, t - окончание наблюдения, пренебрегаем. Тогда без потери общности можно положить ^ = 0 . В этих предпосылках А^) - сопровождающий стационарный кусочно-постоянный скрытый транзитивный марковский процесс с произвольным числом состояний п (п = 2,3,...).

Обобщ1;нный асинхронный поток является обобщением асинхронного потока. Обобщение состоит в следующем: в момент перехода процесса А^) из 7-го состояния в /-е инициируется с вероятностью ргу дополнительное событие, г,у = 1,п, у ф г; переход происходит в произвольный момент времени, не связанный с моментом наступления события пуассоновского потока с параметром Аг,

при этом инициирование дополнительного события осуществляется в у-м состоянии (сначала осуществляется переход из /-го состояния в у-е (переход первичен), затем - инициирование дополнительного события ву-м состоянии), г,у = 1,п, у ^ г ; переход и инициирование дополнительного события происходят мгновенно.

Матрицы инфинитезимальных характеристик [28] процесса Я(г) примут вид:

-(Я1 +а1) (1 - />12)«12 ... (1 - Р1п )а1п (1 - Р 21 )а21 -(Я 2 +а2) ... (1 - Р 2п )а2п

Я Р 21а21

Р12а12 Яо

Рп1ап1 Рп2ап2

Р1п а1п

Р 2п а2п

Я„

где аг = -агг, агг = - 2 агу , г = 1, п ; а у > 0 , 0 < Ру < 1, г, у = 1, п, у * г .

у=1, у

Элементами матрицы ^ являются интенсивности переходов процесса Я(г) из состояния в состояние с наступлением события. Недиагональные элементы матрицы Б0 - интенсивности переходов процесса Я(г) из состояния в состояние без наступления события. Диагональные элементы матрицы Б0 - интенсивности выхода процесса Я(г) из своих состояний, взятые с противоположным знаком.

Положив в (1) Ргу = 0, г,у = 1,п, у ^ г, получаем матрицы инфинитезимальных характеристик процесса Я(г) для асинхронного потока событий с произвольным числом состояний [26].

Наблюдения за потоком производятся на полуинтервале времени [г0, г) . Требуется на основании моментов наступления событий, наблюденных от момента г0 до момента г, оценить состояние

процесса Я(г) (потока) в момент времени г. Обозначим Я (г) оценку состояния процесса Я(г) в момент времени г. Для вынесения решения о состоянии процесса Я(г) в момент времени г необходимо

определить апостериорные вероятности w(Яг | г) = w(Яi 111,...,гт,г) = Р(Я(г) =Яг | г^..., гт,г) , I = 1,п , того, что в момент времени г значение процесса Я(г) = Яг- (т - количество событий, наступивших в

п

моменты г1,...,гт на полуинтервале наблюдения [г0, г)), при этом 2^(Яг- I г) = 1. Решение о состоя-

г=1

нии процесса Я(г) (потока) выносится по критерию максимума апостериорной вероятности [27], согласно которому Я (г) = Яг, если ^(Яг-1 г) > ^(Я у | г) , у = 1, п.

2. Рекуррентное соотношение для апостериорных вероятностей состояний потока

Согласно методике [29], рассмотрим дискретные наблюдения за потоком через достаточно малые промежутки времени длительности Дг. Пусть наблюдения за потоком начинаются в момент времени г = 0, и время г изменяется дискретно с шагом Дг: г(к^ = кДг, к = 0,1,.... Введем двумерный случайный процесс (Я(к), гк), где Я(к) = Я(кДг) - значение процесса Я(г) в момент времени г(к) = кДг (Я(к) = Яг, г = 1 , п ); Гк = Гк (Дг) = г(кДг) - г ((к -1) Дг) - число событий потока, наступивших на полуинтервале времени [(к- 1)Дг, кДг) длительности Дг, г^ = 0,1,..., к = 0,т . Поскольку на полуинтервале [-Дг, 0) наблюдение за потоком не производится, то г0 можем положить произвольным, например г0 = 0 . Обозначим Я(ш) = (Я(0), Я(1),..., Я(т)) - последовательность неизвестных (ненаблюдаемых) значений процесса Я(кДг) в момент времени кДг, к = 0, т (Я(0) = Я(0) = Я , г = 1,п ). Обозначим

гт = Оо, Г,..., гт ) - последовательность чисел наблюденных событий за время от 0 до mAt на полуинтервалах [(к -1)Д^ кА) длительности At, к = 0, т .

Нетрудно показать, что компоненты двумерного случайного процесса (А(к \ г к), к = 0, т, являются взаимно независимыми марковскими компонентами. Тогда для марковского процесса (А(к\ Гк),

к = 0, m +1, имеет место рекуррентная формула для апостериорных вероятностей [26]:

n Inn -

w

i=1 / г=1к=1

где p (Aj, rm+11 Ai, rm) - вероятность перехода процесса (А(к), гк) на полуинтервале [mAt, (т + 1)At) = [t, t + At) из состояния (A(m) = Ai, гт), i = 1,n , rm = 0,1,..., в состояние

(A(m+1) = Aj , Гт+1) , j = \n , Гт+1 = 0,1,....

Исследуем переходную вероятность в (2) для рассматриваемого случая обобщенного асинхронного потока. Имеем

P

Количество наблюденных событий на полуинтервале [mAt, (m + 1)At) состоит из событий пуас-

соновского потока интенсивности A(mAt) = At, i = 1, n , и дополнительных событий, инициируемых в моменты перехода процесса A(t) из /-го состояния в j-е (i, j = 1,n, j ф i). В силу этого инициирование дополнительных событий связано с переходной вероятностью p (A j | Ai, ^); наступление же событий пуассоновского потока связано с вероятностью p(г^ | Ai, ^, Aj), т.е. ^, Гm+1 - число событий пуассоновского потока, наблюденных на полуинтервалах [(m -1)At, mAt), [mAt, (m + 1)At) соответственно. Отметим, что в силу малости величины At число событий гт = 0;1 (гт = 2,3,...), имеет вероятность o(At)), аналогично для г^ . Количество переходов процесса A(t) на полуинтервале [mAt, (m +1)At) более одного также имеет вероятность o(At).

Замечание 1. Ситуация: одновременное наступление события пуассоновского потока и переход процесса A(t) на интервале длительности At из /-го состояния в j-е (с инициированием дополнительного события либо без его инициирования) имеет вероятность o(At), i, j = 1, n, j ф i.

Первый сомножитель в (3) запишется в виде p(Aj | Ai, ^) = p(Aj | Ai) , так как на значение процесса A((m + 1)At) = A j в момент времени (m + 1)At число наблюденных событий гш на полуинтервале [(m -1)At, mAt) не влияет (процесс A(t) «живет своей жизнью»); значение же A(mAt) = Ai процесса A(t) в момент времени t = mAt не зависит от предыстории в силу марковости процесса A(t) . Наконец, подчеркнем, что дополнительное событие на полуинтервале [mAt, (m + 1)At) наступает (либо не наступает) в j-м состоянии при переходе процесса A(t) из /-го состояния в j-е (i, j = 1, n, j ф i). Это обстоятельство нужно отразить в вероятности p (Aj | Ai): p (Aj | Ai) = pd (Aj | Ai), d = 0;1,

i, j = 1,n, j ф i; p (A | A ) = po (A | Aj), i = 1,n . Если d = 0, то дополнительное событие на полуинтервале [mAt, (m + 1)At) с вероятностью (1 - piJ-) не инициируется, i, j = 1, n; pü = 0 , i = 1, n . Если d = 1, то дополнительное событие на полуинтервале [mAt, (m +1)At) инициируется с вероятностью

pij , i,j = 1, n, j ф i.

Рассмотрим второй сомножитель в (3). Имеем, во-первых, p(гп+1 | Ai, гп, Aj) = p(гп+1 | Ai, Aj), так как число событий г^1, наблюденных на полуинтервале [mAt, (m +1)At), не зависит от числа со-

бытий гш, наблюденных на полуинтервале [(т — 1)А/, тА), в силу того, что потоки событий во всех состояниях процесса Я(^) пуассоновские. Во-вторых,

, Л ч Р ^ , Гт+1,

X,) Р (X, |Хг

, Гт+1 ) Р

Р

7 Р

Так как на значение процесса Х((т +1)А/) = X^ в момент времени (т +1)А число наблюденных событий гт+1 на полуинтервале [тА/, (т +1)А), так же как и число наблюденных событий гт на полуинтервале [(т — 1)Д/, тД/), не влияет, то Р (X^ | X,, гт+1) = Р (X^ | X,.) . Тогда из равенства (4) вытекает Р(гт+1 | Xi, Xу ) = Р(гт+1 | Xi) . В силу этого (3) приобретает вид:

Р

Подставляя (5) в (2), находим рекуррентное соотношение для апостериорных вероятностей состояний в случае обобщённого асинхронного потока событий:

п / п п

V

,=1 / /'=1^=1

й = О;1, Гт+1 = 0;1,7 = 1, п.

3. Система дифференциальных уравнений и формулы пересчета для апостериорных вероятностей

Пусть временной полуинтервал [/, / + А/) расположен на временной оси между моментами наступления соседних событий обобщенного асинхронного потока, скажем, между моментами и (события в моменты времени /к и могут быть событиями пуассоновского потока либо дополнительными событиями, либо и теми и другими). Тогда на полуинтервале [/, / + А/) нет событий потока. Последнее означает, что в (6) й = 0, гт+1 = 0 . Тогда учитывая (1), имеем

Ро

Ро

Р

Лемма 1. На интервале времени (/к, , к = 0,1,..., т.е. между моментами наступления соседних событий обобщенного асинхронного потока, апостериорные вероятности м(X^ | /), 1 = 1,п, удовлетворяют следующей системе нелинейных дифференциальных уравнений:

п п

-1- = 2[

й/ , = 1 , = 1 ^ = 1

где 1 = 1, п, /к < / < /к+1, к = 0,1,...; р^ = ри = 0; 5 у - символ Кронекера.

Доказательство. Обозначим в (6) 1) - числитель, В0 - знаменатель. Учитывая введенные обозначения, формулы (7)-(9) и проделывая необходимые преобразования, находим

Д 1 =2 м (X, | /)Р0 (X | X,)Р (Гт+1 = 01 X,) = (1 — XА)м X | /) + А/2(1 — Р1} (X, | /) + о(А),

¿=1 1=1

Рц =0,1=1,п;

п п п п

В = 22^ )Р0^ ^)р(Гт+1 = 0| X,) = 1 — А/2+ 2Р^] + о(А),

,=15=1 , =1 5=1

Р,, = 0, , = 1, п.

Подставляя (11), (12) в (6) и принимая во внимание, что (1 — х) 1 = 1 + х + о(х), получаем

w(Аj \Х + АХ) =

п п п _

= (1 — А] АХ^(А] \ Х) + АхX(1 — Р)«^(А, \ Х) + А^(А] \ хЩА, + Xр,а,МА, \ Х) + о(Ах), 7 = 1,п.

i=1 1=1 ,=1

Перенося w (X у \ Х) в левую часть последнего равенства, после чего деля левую и правую части равенства на АХ и устремляя АХ к нулю, приходим к (10). Лемма 1 доказана.

Систему (10) необходимо дополнить начальными условиями: значениями апостериорных вероятностей в моменты наступления событий и в момент начала наблюдения за потоком.

В силу замечания 1 рассмотрим ситуацию, когда на полуинтервале [Х, Х + Ах) наступает одно событие обобщенного асинхронного потока, скажем, в момент времени Х^, к = 1,2,.... Рассмотрим два смежных промежутка времени [Х, ХА ), [Хк, Х + АХ) . Длительность первого промежутка есть АХ' = Хк — Х, длительность второго промежутка есть Ах" = Х + АХ — Хк . Тогда в (6) м(А \ Х + АХ) = м(А ^\ Хк + Ах") , \ Х) = \ Хк — Ах'), и рекуррентная формула (6) приобретает вид:

X ъ

w

X X w(Аi \ Хк —Ах ') ра (А, \ А.) р (Гт+1 \ А.) =1 , =1

7 = 1П; (й = 0, гт+1 = 1), (й = 1, Гт+1 = 0); к = 1,2,... Начальные условия для системы (10) определяются в следующих леммах.

Лемма 2. Апостериорные вероятности состояний обобщённого асинхронного потока w (А 7 \ Х), 7 = 1,п, в момент Хк, к = 1,2,..., наступления события потока определяются формулой пересчета:

п / п п

w

1=1 / 1=1 ,=1

где 7 = 1,п; р п = 0, ри = 0 ; к = 1,2,...

Доказательство. Обозначим в (13) А1(7 - числитель, ^ - знаменатель. Учитывая (1), находим

р

рДА^А,) = 0, 7 = Щ;

р

Тогда, принимая во внимание введенные обозначения, формулы (7)-(9), (15)-(17), и с учетом замечания 1, проделывая необходимые преобразования, получаем

п

А/7) =X w (А I \ Хк — АХ ')[р0 (А7 \ А I)р(Гт+1 = 1 \ А .) + р (А7 \ А ..)р(гт+1 = 0 \ А ..)] =

= Ах[А^ (А7 \ Хк — АХ ') + X рг]а^ (А I \ Хк — Ах ')] + о(Ах), р= 0, 7 = 1,п;

п ( л п п -

= XА°) = АХXw

} =1 !=1 ,=1

Подставляя (18), (19) в (13), деля при этом числитель и знаменатель на Ах, после чего устремляя Ах к нулю (АХ ' и Ах" стремятся к нулю одновременно), приходим к (14). Лемма 2 доказана.

Замечание 2. При стремлении Ах к нулю величина Х = Хк — АХ ' стремится к Х4 слева, величина Х + АХ = Хк +АХ " стремится к Хк справа. В формуле (14) w(А7 \ Хк + 0) - предел функции w(А7 \ Х) в точке ^ (к = 1,2,...) справа, w(А7 \ Хк — 0) - предел w(А7 \ Х) в той же точке слева. То есть функция

!=1

wу | I) в точке ¡к претерпевает разрыв первого рода, к —1,2,... Вероятности w(Xу 11к + 0) являются начальными условиями для решения системы (10) на полуинтервале , , к —1,2,...

Рассмотрим w(Яу 110) — w(Яу 110 + 0) (у — 1,и) - апостериорные вероятности состояний потока в момент г0 — 0 . Вероятности w(X  | 10 + 0) являются начальными условиями для решения системы

(10) на полуинтервале [г0, г1) . Задавать w(Xу 110 + 0) (у — 1,п) можно, исходя из априорной информации о потоке. Поскольку поток рассматривается в стационарном режиме, то можно в качестве w(A,у | 10 + 0), у — 1, п, выбрать априорные финальные вероятности состояний процесса Я(^) . Пусть

я у (у — 1, п) - априорная финальная вероятность того, что процесс Х({) в произвольный момент времени I находится в у-м состоянии. Для вероятностей я у (у — 1, п) справедлива лемма 3.

Лемма 3. Априорные финальные вероятности я у (у — 1, п) состояний процесса Х(^) (I ^го) удовлетворяют неоднородной системе линейных алгебраических уравнений

£я,-агу = 0, j = 1,n -1, £яj = 1,

i=1 j=1

где а у (i, у = 1, n) определены в (1).

Доказательство. Процесс X(t) является транзитивным марковским, для которого существует финальное распределение вероятностей состояний [30], т.е. существует Яу = limЯу(t) при t ^да (у = 1,n), причем для Яу (у = 1, n) выполняется условие нормировки. На поведение процесса X(t) наступление

событий обобщенного асинхронного потока (как событий пуассоновского потока, так и дополнительных событий) не оказывает влияния. Вследствие этого дальнейшее доказательство формулы (20) аналогично доказательству, приведенному в [26]. Решение системы (20) можно осуществить по формулам Крамера [31]. Лемма 3 доказана.

Леммы 1-3 позволяют сформулировать теорему 1.

Теорема 1. Поведение апостериорных вероятностей w (^у 11), у = 1,n, на временной оси t > t0 = 0 определяется системой дифференциальных уравнений (10), формулами пересчета вероятностей (14) и решением системы (20), в которых tk < t < tk+1, w(^у | tk ) = w(^у | tk + 0), w('kj | tk+1) = w(kу | tk+1 -0) (k = 0,1,...); для k = 0 имеет место равенство w(Xу 110) =

= w(Xу 110 + 0) = пу (у = 1,n).

Доказательство следует из (10), (14), (20) путем их синхронизации. Теорема 1 доказана. Замечание 3. Теорема 2 определяет, в частности, поведение апостериорных вероятностей на полуинтервале [t^_j, t^), т.е. между моментами наступления соседних событий, причем на правом

конце полуинтервала имеет место значение w(kj | tk) = w(kj | tk - 0), на основе которого по формуле (14) находится вероятность w('kj | tk + 0) (у = 1,n), являющаяся начальной для следующего полуинтервала [tk, tk+1), k = 1,2,... Таким образом, апостериорные вероятности w(^у 11) в моменты наступления событий t1, t2,... претерпевают разрывы первого рода.

4. Явный вид апостериорных вероятностей в зависимости от времени

Рассмотрим [tk, tk+j) (k = 0,1,...) - полуинтервал времени между моментами наступления соседних k-го и k +1 -го событий, либо, если k = 0, между моментом начала наблюдения за потоком и

n

n

моментом наступления 1-го события. Следующая теорема определяет решение системы нелинейных дифференциальных уравнений (10) на временной оси в явном виде.

Теорема 2. Апостериорные вероятности состояний обобщ1;нного асинхронного потока событий w(A j 11), j = 1,n, на полуинтервале времени [tk, tk+1 ), k = 0,1,..., определяются формулой

n inn

w

s=1 / l=1s=1

w(Aj |t0) = w (Aj |t0 + 0) = %j ; w(Aj |tk ) = w(Aj |tk + 0), k = 1,2,...; - корни (собственные числа) характеристического уравнения det D = 0, D = Ц^Ц^ , dsl = asl ( s,l = 1,n, s Ф l ), dM = ass - ю ( s = 1,n ), asi = [(1 -Pis)als-AlSls], 5ls - символ Кронекера, s,l = 1,n ; y- компоненты собственного вектора Y(s) = (y1s,..., Уns)Г, j,s = 1,n (либо yls ; l,s = 1,n), определяемые из уравнения (A-rosE)y(s) = 0, s = 1, n, в котором yns = 1 ( s = 1, n ), A = ||asJ1" , E - единичная матрица; коэффициенты cs^) являют-

п , 7 ч -

ся решением системы линейных алгебраических уравнений: X с, у 7, = w (А 7\Хк + 0), 7 = 1, п,

к = 0,1,...; вероятность w(А7 \ Хк + 0), к = 1,2,..., определяется формулой пересч!та (14), в которой w^ \ Хк — 0), I = 1, п, вычисляется по формуле

n ! n n _

w

s

s=1 I l =1 s=1

Доказательство. Решим систему нелинейных дифференциальных уравнений (10) на полуинтервале [Хк, Хк+1), к = 0,1,..., с начальным условием w(А ^\Хк ) = w(А ^\Хк + 0), 7 = 1, п, пут!м сведения е! к системе линейных дифференциальных уравнений. Преобразуем систему (10). Обозначим

--п п

2 7 = (1 — р у )а7 -Зу ( i,7 = 1, п X ¥(Х) = X[Аi + X Рг,аг, М^ \ Х) . Тогда (10) примет вВД:

I=1 х=1

dw(Aj 11) n

dt =Z Z,]'^KA,|t ' ' ^ y"VA j

= Z zijw

I=1

7 = , Хк < Х <Хк+1, w(А7 \ Хк) = w(Ау \ Хк + 0), к = 0,1,... Произведем замену искомых функций w(А7 \ Х) в (23):

н<А ;.\Х) = у 7 (Х) ехр[/Т(х) йх], 7 = Щ , Хк < Х < Хк+1,

хк

w

Подставляя (24) в (23), находим

йу7 (Х) п -

-7- = X Zг7Уг

йХ I=1

Относительно у7 (Х), 7 = 1,п, получена система линейных дифференциальных уравнений с постоянными коэффициентами. Решение системы (25) выпишется в виде [32]:

У} (Х) = XX с,(k)Уj,eю,(х—Хк), 7 = , Хк < х < Хк+1, Уу (Хк) = У;(Хк + 0) = w(Ау \Хк + 0), к = 0,1,... (26) ,=1

п

Так как X w(А/ \ Х) = 1, хк < Х < Хк+1, к = 0,1,..., то из (24), учитывая (26), получаем

/=1

Х / п / п п П \

^ / /=1 / /=1,=1

Подставляя (26), (27) в (24), приходим к (21). Теорема 2 доказана.

Формулы (14), (20)-(22) позволяют сформулировать алгоритм расчета апостериорных вероятностей w(X j 11), j = 1,n, в любой момент времени t ( t > t0 = 0 ):

1) в момент времени t0 = 0 задаются вероятности w(X j 110 + 0) = n j , где n j - решение системы

(20), j = 1,n ;

2) по формуле (21) рассчитываются вероятности w (X j 11), j = 1, n, в любой момент времени t ( 0 < t < ^ ), где tj - момент наблюдения первого события потока;

3) по формуле (22) рассчитываются вероятности w (X j 11), j = 1,n, в момент времени Ц : w(Xj 111) = w(Xj 111 - 0) ; затем по формуле (14) производится пересчет апостериорных вероятностей в точке t = tj, при этом вероятности w (X j 111 + 0), j = 1, n, являются начальными условиями для w (X j 11) на следующем шаге алгоритма;

4) по формуле (21) рассчитываются апостериорные вероятности w (X j 11), j = 1, n, для любого t ( tj < t < t2 ), где t2 - момент времени наступления второго события потока, и т.д.

Параллельно по ходу вычисления апостериорных вероятностей w (X j 11), j = 1, n, в момент времени t выносится решение о состоянии процесса X(t) (потока) по критерию максимума апостериорной вероятности: XX(t) = Xt, если w(X; 11) = max w(Xj 11), j = 1,n.

Заключение

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

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

ЛИТЕРАТУРА

1. Cox D.R. The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables // Proc. of

the Cambridge Philosophical Society. 1955. V. 51, is. 3. P. 433-441.

2. Башарин Г.П., Кокотушкин В.А., Наумов В.А. О методе эквивалентных замен расчёта фрагментов сетей свя-

зи. Ч. 1 // Известия АН СССР. Техническая кибернетика. 1979. № 6. С. 92-99.

3. Neuts M.F. A versatile Markovian point process // Journal of Applied Probability. 1979. V. 16. P. 764-779.

4. Lucantoni D.M. New results on the single server queue with a batch markovian arrival process // Communications in

Statistics Stochastic Models. 1991. V. 7. P. 1-46.

5. Diamond J.E., Alfa A.S. The MAP/PH/1 retrial queue // Communications in Statistics Stochastic Models. 1998. V. 14.

P. 1151-1177.

6. Лившиц К.И., Сухотина Л.Ю., Шифердекер И.Ю. Математическая модель деятельности некоммерческого фон-

да при дважды стохастическом потоке платежей // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2007. № 1. С. 36-43.

7. Card H.C. Doubly stochastic Poisson processes in artificial neural learning // Neural Networks, IEEE Transactions.

1998. V. 9, is. 1. P. 229-231.

8. Лившиц К.И., Ульянова Е.С. Модель управления запасами однородной продукции с релейным управлением

темпом производства и MMP-потоком моментов продаж // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 44. С. 50-61.

9. Башарин Г.П., Самуйлов К.Е., Яркина Н.В., Гудкова И.А. Новый этап развития математической теории теле-

трафика // Автоматика и телемеханика. 2009. № 12. С. 16-28.

10. Basharin G.P., Gaidamaka Y.V., Samouylov K.E. Mathematical theory of teletraffic and its application to the analysis of multiservice communication of next generation networks // Automatic Control and Computer Science. 2013. V. 47, is. 2. P. 62-69.

11. Вишневский В.М., Ларионов А. А. Открытая сеть массового обслуживания с коррелированными входными потоками для оценки производительности широкополосных беспроводных сетей // Информационные технологии и математическое моделирование (ИТММ-2016) : материалы XV Междунар. конф. Катунь, 12-16 сентября 2016. Томск : Изд-во Том. ун-та, 2016. Ч. 1. С. 36-50.

12. Vishnevsky V.M., Larionov A.A., Smolnikov R.V. Optimization of topological structure of broadband wireless networks along the long traffic routes // Distributed Computer and Communication Networks: Control, Computation, Communications : proc. of the eighteenth Int. Scientific Conf. (DCCN-2015) (Moscow, October 19-22, 2015). Moscow : ICS RAS, 2015. P. 27-35.

13. Вишневский В.М., Ляхов А.И. Оценка пропускной способности локальной беспроводной сети при высокой нагрузке и помехах // Автоматика и телемеханика. 2001. № 8. С. 81-96.

14. Гайдамака Ю.В., Зарипова Э.Р., Самуйлов К.Е. Модели обслуживания вызовов в сети сотовой подвижной связи. М. : Изд-во РУДН, 2008. 72 с.

15. Дудин А.Н., Клименок В.И. Расчет необходимого числа каналов в современных телекоммуникационных сетях // Информатизация образования. 2005. № 4. С. 56-68.

16. Наумов В.А., Самуйлов К.Е., Яркина Н.В. Теория телетрафика мультисервисных сетей. М. : Изд-во РУДН, 2007. 191 с.

17. Ниссенбаум О.В., Пахомов И.П. Аппроксимация сетевого трафика моделью альтернирующего потока событий // Прикладная дискретная математика. 2009. № 1. С. 78-79.

18. Самуйлов К.Е., Яркина Н.В., Гудкова И.А. Математическая модель управления доступом в сетях Triple play // IV Междунар. конф. по проблемам управления : сб. трудов. М. : Изд-во ИПУ, 2009. С. 1722-1730.

19. Горцев А.М., Нежельская Л.А. О связи МС-потоков и МАР-потоков событий // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. № 1 (14). С. 13-21.

20. Bushlanov I.V., Gortsev A.M., Nezhel'skaya L.A. Estimation of the parameters of a synchronous doubly stochastic event stream // Automatika i telemekhanika. 2008. Is 9. P. 76-93.

21. Gortsev A.M., Solov'ev A.A. Joint probability density of interarrival interval of a flow of physical events with un-extendable dead time period // Russian Physics Journal. 2014. V. 57, is. 7. P. 973-983.

22. Bakholdina M., Gortsev A. Joint probability density of the intervals length of the modulated semi-synchronous integrated flow of events and its recurrence conditions // Communications in Computer and Information Science. 2014. V. 487. P. 18-25.

23. Gortsev A.M., Nezhelskaya L.A. An asynchronous double stochastic flow with initiation of superfluous events // Discrete Mathematics and Applications. 2011. V. 21, is. 3. P. 283-290.

24. Vasil'eva L.A., Gortsev A.M. Estimation of parameters of a double-stochastic flow of events under conditions of its incomplete observability // Automation and Remote Control. 2002. V. 63, is. 3. P. 511-515.

25. Горцев А.М., Калягин А.А., Нежельская Л.А. Оценка максимального правдоподобия длительности мертвого времени в обобщенном полусинхронном потоке // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2015. № 1 (30). С. 27-37.

26. Горцев А.М., Зуевич В.Л. Оптимальная оценка состояний асинхронного дважды стохастического потока событий с произвольным числом состояний // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2010. № 2 (11). С. 44-65.

27. Левин Б.Р. Теоретические основы статистической радиотехники. М. : Сов. радио, 1968. Кн. 2. 504 с.

28. Назаров А.А., Терпугов А.Ф. Теория вероятностей и случайных процессов. Томск : Изд-во НТЛ, 2006. 204 с.

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

30. Хинчин А.Я. Работы по математической теории массового обслуживания. М. : Физматгиз, 1963. 236 с.

31. Лившиц К.И. Линейная алгебра и аналитическая геометрия. Томск : Изд-во НТЛ, 2011. 252 с.

32. Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. М. : Наука, 1969. 424 с.

Поступила в редакцию 23 ноября 2018 г.

Gortsev A.M., Nezhel'skaya L.A. (2019) OPTIMAL ESTIMATE OF THE STATES OF A GENERALIZED ASYNCHRONOUS EVENT FLOW WITH AN ARBITRARY NUMBER OF STATES. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie vychislitelnaja tehnika i informatika [Tomsk State University Journal of Control and Computer Science]. 47. pp. 12-23

DOI: 10.17223/19988605/47/2

In this paper, we consider a generalized asynchronous flow of events (hereinafter called a flow). The flow accompanying process (intensity process) is a piecewise constant random process X(t) with n states: X(t) takes values from a discrete set of values

(Xj,...,Xn}, X1 > X2 > ... >Xn > 0 . Let's say that the i-th state of the process X(t) holds if X(t) = X,, i = 1,n , n = 2,3,.... If the i-th state takes place, then during the time interval when X(t) = Xi there is a Poisson flow of events with parameter (intensity) Xi, i = 1, n . The duration of the process X(t) (flow) in the i-th state is distributed according to the exponential law with the parameter at: F (t) = 1 - e~a,iT, t > 0 , i = 1, n . The process X(t) is a fundamentally unobservable process; we can only observe time moments of occurrence of flow events tj, t2,..., tk,...

We consider the stationary mode of the flow functioning. In these premises, X(t) is an accompanying stationary piecewise constant hidden transitive Markov process with an arbitrary number of states n (n = 2,3,...).

A generalized asynchronous flow (a generalized MMPP-flow) is a generalization of the asynchronous flow. The generalization is as follows: at the moment of transition of the process X(t) from the i-th state to the j-th, an additional event is triggered with probability pj ; the transition occurs at an arbitrary time moment, not related to the moment of occurrence of the Poisson flow event with

parameter Xi, while initiating an additional event occurs in the j-th state, i, j = 1, n , j ф i; transition and initiation of an additional event occur instantly.

It is required, on the basis of the moments of occurrence of events observed from moment t0 to moment t, to estimate the state of the process X(t) at the moment t . We denote the estimate of the state of the process X(t) at the time moment t as X(t). We found an explicit form for a posteriori probabilities w(X, 1t) = w(Xi 111,..., tm,t) = P(X(t) = X,-1 tx,..., tm,t), i = 1,n , that at the time moment t the value of the process X(t) = X,- (m is the number of events that occurred at the time moments t1v.., tm at the observan

tion interval (t0, t)), here Xw(X; 11) = 1. The decision on the state of the process X(t) obtained according to criterion of a posteriori

i=1

probability maximum.

The algorithm for calculating a posteriori probabilities w(Xj 11), j = 1, n , at any time moment t (t > t0 = 0 ) was formulated according to analytical formulas. In parallel, as we calculate a posteriori probabilities w(Xj 11), j = 1, n , we can make a decision on the state of the process X(t) at the time moment t : XX(t) = X;, if w(X,-11) = max w(X • 11) , j = 1, n .

Keywords: generalized asynchronous doubly stochastic flow of events; a posteriori probability; optimal states estimation.

GORTSEV Alexander Mikhailovich (Doctor of Technical Sciences, Professor, National Research Tomsk State University, Tomsk, Russian Federation). E-mail: a-gortsev@mail.ru

NEZHEL 'SKAYA Lyudmila Alekseevna (Doctor of Physical and Mathematical Sciences, Associate Professor, National Research Tomsk State University, Tomsk, Russian Federation). E-mail: ludne@mail.ru

REFERENCES

1. Cox, D.R. (1955) The analysis of non-Markovian stochastic processes by the inclusion of supplementary variables. Proc. of the

Cambridge Philosophical Society. 51(3). pp. 433-441. DOI: 10.1017/S0305004100030437

2. Basharin, G.P., Kokotushkin, V.A. & Naumov, V.A. (1979) O metode ekvivalentnykh zamen rascheta fragmentov setey svyazi.

CH. 1 [On the Equivalent Substitutions Method for Computing Fragments of Communication Networks]. Izvestiya AN SSSR. Tekhnicheskaya kibernetika. 6. pp. 92-99.

3. Neuts, M.F. (1979) A versatile Markovian point process. Journal of Applied Probability. 16. pp. 764-779. DOI: 10.2307/3213143

4. Lucantoni, D.M. (1991) New results on the single server queue with a batch Markovian arrival process. Communications in Statistics

Stochastic Models. 7. pp. 1-46. DOI: 10.1080/15326349108807174

5. Diamond, J.E. & Alfa, A.S. (1998) The MAP/PH/1 retrial queue. Communications in Statistics Stochastic Models. 14. pp. 1151-

1177. DOI: 10.1080/15326349808807518

6. Livshits, K.I., Sukhotina, L.Yu. & Shiferdeker, I.Yu. (2007) Mathematical model of incomercial fund functioning under the twice

stohastic payments flow. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika -Tomsk State University Journal of Control and Computer Science. 1. pp. 36-43. (In Russian).

7. Card, H.C. (1998) Doubly stochastic Poisson processes in artificial neural learning. Neural Networks, IEEE Transactions. 9(1).

pp. 229-231. DOI: 10.1109/72.655046

8. Livshits, K.I. & Ulyanova, E.S. (2018) Model of inventory control of homogeneous products with relay control of production rate

and MMP-flow of sales moments. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika - Tomsk State University Journal of Control and Computer Science. 44. pp. 50-61. (In Russian). DOI: 10.17223/19988605/44/6

9. Basharin, G.P., Samouylov, K.E., Yarkina, N.V. & Gudkova, I.A. (2009) A new stage in mathematical teletraffic theory. Automa-

tion and Remote Control. 70(12). pp. 1954-1964. DOI: 10.1134/S0005117909120030

10. Basharin, G.P., Gaidamaka, Y.V. & Samouylov, K.E. (2013) Mathematical theory of teletraffic and its application to the analysis of multiservice communication of next generation networks. Automatic Control and Computer Science. 47(2). pp. 62-69. DOI: 10.3103/S0146411613020028

11. Vishnevsky, V.M. & Larionov, A.A. (2016) [Open queueing network with correlated input flows for estimating the performance of broadband wireless networks]. Information Technologies and Mathematical Modelling (ITMM 2016). Proc. of the 15th International Conference. September 12-16, 2016. Tomsk. pp. 36-50. (In Russian).

12. Vishnevsky, V.M., Larionov, A.A. & Smolnikov, R.V. (2015) Optimization of topological structure of broadband wireless networks along the long traffic routes. Distributed Computer and Communication Networks: Control, Computation, Communications. Proc. of the 18th International Conference (DCCN-2015). Moscow. October 19-22, 2015. Moscow: ICS RAS. pp. 27-35.

13. Vishnevskii, V.M. & Lyakhov, A.I. (2001) A wireless LAN under high load and in noise: throughput evaluation. Automation and Remote Control. 62(8). pp. 1298-1311. DOI: 10.1023/A:1010257612786

14. Gaidamaka, Yu.V., Zaripova, E.R. & Samouylov, K.E. (2008) Modeli obsluzhivaniya vyzovov v seti sotovoy podvizhnoy svyazi [Call Service Models in Cellular Mobile Network]. Moscow: PFUR.

15. Dudin, A.N. & Klimenok, V.I. (2005) Raschet neobkhodimogo chisla kanalov v sovremennykh telekommunikatsionnykh setyakh [Calculation of the required number of channels in modern telecommunication networks]. Informatizatsiya obrazovaniya. 4. pp. 56-68.

16. Naumov, V.A., Samouylov, K.E. & Yarkina, N.V. (2007) Teoriya teletrafika mul'tiservisnykh setey [Teletraffic Theory of Multiservice Networks]. Moscow: PFUR.

17. Nissenbaum, O.V. & Pakhomov, I.P. (2009) Approximation of network traffic by the alternating event flow model. Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 1. pp. 78-79. (In Russian).

18. Samouylov, K.E., Yarkina, N.V. & Gudkova, I.A. (2009) [Mathematical model of access control in Triple play networks]. Proc. of the Fourth International Conference on Control Problems. Moscow: ICS RAS. pp. 1722-1730. (In Russian).

19. Gortsev, A.M. & Nezhelskaya, L.A. (2011) On relationship of MC-flows and MAP-flows of events. Vestnik Tomskogo gosudar-stvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika - Tomsk State University Journal of Control and Computer Science. 1(14). pp. 13-21. (In Russian).

20. Bushlanov, I.V., Gortsev, A.M. & Nezhelskaya, L.A. (2008) Estimation of the parameters of a synchronous doubly stochastic event stream. Automation and Remote Control. 9. pp. 76-93.

21. Gortsev, A.M. & Soloviev, A.A. (2014) Joint probability density of interarrival interval of a flow of physical events with unex-tendable dead time period. Russian Physics Journal. 57(7). pp. 973-983. DOI: 10.1007/s11182-014-0333-4

22. Bakholdina, M. & Gortsev, A. (2014) Joint probability density of the intervals length of the modulated semi-synchronous integrated flow of events and its recurrence conditions. Communications in Computer and Information Science. 487. pp. 18-25. DOI: 10.1007/978-3-319-13671-4_3

23. Gortsev, A.M. & Nezhelskaya, L.A. (2011) An asynchronous double stochastic flow with initiation of superfluous events. Discrete Mathematics and Applications. 21(3). pp. 283-290. DOI: 10.1515/dma.2011.017

24. Vasilieva, L.A. & Gortsev, A.M. (2002) Estimation of parameters of a double-stochastic flow of events under conditions of its incomplete observability. Automation and Remote Control. 63(3). pp. 511-515. DOI: 10.1023/A:1014718921138

25. Gortsev, A.M., Kalyagin, A.A. & Nezhelskaya, L.A. (2015) Maximum likelihood estimation of dead time at a generalized semy-synchronous flow of events. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika - Tomsk State University Journal of Control and Computer Science. 1(30). pp. 27-37. (In Russian).

26. Gortsev, A.M. & Zuevich, V.L. (2010) Optimal estimation of states of the asynchronous doubly stochastic flow of events with arbitrary number of the states. Vestnik Tomskogo gosudarstvennogo universiteta. Upravlenie, vychislitel'naya tekhnika i informatika - Tomsk State University Journal of Control and Computer Science. 2(11). pp. 44-65. (In Russian).

27. Levin, B.R. (1968) Teoreticheskie osnovy statisticheskoy radiotekhniki [Theoretical Foundations of Statistical Radio Engineering]. Moscow: Sovetskoe radio.

28. Nazarov, A.A. & Terpugov, A.F. (2006) Teoriya veroyatnostey i sluchaynykh protsessov [Theory of Probability and Random Processes]. Tomsk: NTL.

29. Khazen, E.M. (1968) Metody optimal'nykh statisticheskikh resheniy i zadachi optimal'nogo upravleniya [Methods of optimal statistical decisions and problems of optimal control]. Moscow: Sovetskoe radio.

30. Khinchin, A.Ya. (1963) Raboty po matematicheskoy teorii massovogo obsluzhivaniya [Works on the Mathematical Theory of Queuing]. Moscow: Fizmatgiz.

31. Livshits, K.I. (2011) Lineynaya algebra i analiticheskaya geometriya [Linear Algebra and Analytic Geometry]. Tomsk: NTL.

32. Elsgolts, L.E. (1969) Differentsial'nye uravneniya i variatsionnoe ischislenie [The Differential Equations and Calculus of Variations]. Moscow: Nauka.