Оптимальная оценка состояний обобщённого асинхронного потока событий с произвольным числом состояний | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/2

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

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

Optimal estimate of the states of a generalized asynchronous event flow with an arbitrary number of states.pdf Распространенными математическими моделями физических явлений и процессов являются потоки событий. В подавляющем большинстве работ по исследованию систем массового обслуживания (СМО) в качестве входящих потоков событий рассматривались пуассоновские потоки событий. Однако в связи с бурным развитием вычислительной техники, спутниковых, компьютерных, беспроводных и мобильных сетей связи модель простейшего потока перестала быть адекватной реальным информационным потокам событий. При этом теория построения математических моделей функционирования информационно-телекоммуникационных систем, существовавшая до середины 1980-х гг., во многом становится непригодной для анализа информационных процессов, протекающих в современных телекоммуникационных системах. Поэтому в это же время была предпринята успешная попытка создания адекватных математических моделей информационных потоков в телекоммуникационных системах так называемых дважды стохастических потоков. Дважды стохастические потоки событий можно разделить на два класса: первый класс составляют потоки, интенсивность которых есть непрерывный случайный процесс [1]; второй - потоки, интенсивность которых есть кусочно-постоянный случайный процесс с конечным (произвольным) числом состояний. Впервые результаты исследований потоков второго класса опубликованы практически в одно и того же время, в 1979 г., в работах [2, 3]. В [2] указанные потоки получили название MC (Markov chai^-roTOm; в [3] - MVP (Markov versatile processes)-™™^. В статьях [4, 5] описанные выше потоки называют также MAP (Markov Arrival Process)-потоками событий. С использованием моделей дважды стохастических потоков событий возможно исследование финансово-экономических процессов [6], биофизических процессов [7], процессов управления запасами [8] и др. Отметим, что MC-потоки событий (MAP-потоки) являются наиболее характерной и подходящей моделью потоков в реальных телекоммуникационных сетях, в частности в широкополосных сетях беспроводной связи вдоль протяженных транспортных магистралей [9-18]. Зарубежными и отечественными исследователями при описании подобных входящих потоков событий в СМО используются термины «дважды стохастические потоки событий», MAP-потоки, MC-потоки. В статье [19] предложена классификация MAP-потоков на MAP-потоки первого порядка и MAP-потоки второго порядка в зависимости от возможных вариантов смены состояний интенсивности потока. Класс MAP-потоков первого порядка составляют потоки, у которых смену состояний интенсивности определяет одна случайная величина; вследствие этого смена состояний происходит в случайные моменты времени, в которые событие потока может наступить или не наступить: 1) синхронные потоки (потоки, у которых состояние интенсивности меняется в случайные моменты времени, являющиеся моментами наступления событий) [20]; 2) собственно MAP-потоки как обобщение синхронных потоков [21]. Класс MAP-потоков второго порядка составляют потоки, у которых смена состояний интенсивности определяется двумя независимыми случайными величинами так, что смена состояний происходит в случайные моменты времени, в которые событие потока может наступить или не наступить: 1) модулированные MAP-потоки [22]; 2) обобщенные асинхронные потоки [23], являющиеся обобщением асинхронных потоков, или, что то же самое, MMPP-потоков (потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени и не зависит от моментов наступления событий) [24]; 3) обобщенные полусинхронные потоки [25] как обобщение полусинхронных потоков (потоки, у которых одна часть состояний интенсивности меняется в моменты наступления событий потока (свойство синхронных потоков), другая часть состояний интенсивности меняется в произвольные моменты времени, не связанные с моментами наступления событий потока (свойство асинхронных потоков)). В настоящей статье рассматривается MAP-поток событий второго порядка с произвольным числом состояний, являющийся обобщением асинхронного потока событий с произвольным числом состояний [26]. Решается задача об оптимальной оценке состояний обобщенного асинхронного потока событий (далее - обобщенный асинхронный поток либо просто поток). Находятся явные выражения для апостериорных вероятностей состояний потока. Решение о состоянии потока выносится по критерию максимума апостериорной вероятности, представляющей наиболее полную характеристику состояний потока, которую можно получить, располагая только выборкой наблюдений; этот критерий обеспечивает минимум полной (безусловной) вероятности ошибки вынесения решения [27]. 1. Постановка задачи Рассматривается обобщенный асинхронный поток, сопровождающий процесс (интенсивность) A(t) которого есть кусочно-постоянный случайный процесс с n состояниями: A(t) принимает значения из дискретного множества значений {Aj,...,An}, А >А2 >... >An > 0. Будем говорить, что имеет место i-е состояние процесса A(t), если A(t) = At, i = 1,n , n = 2,3,.... Если имеет место i-е состояние процесса A(t), то в течение временного интервала, когда A(t) = А,-, имеет место пуассоновский поток событий с параметром (интенсивностью) , i = 1, n . Длительность пребывания процесса A(t) (потока) в i-м состоянии распределена по экспоненциальному закону с параметром аг: F{ (т) = 1 - e ~ai%, т> 0, i = 1, n . Процесс A(t) является принципиально ненаблюдаемым (A(t) - скрытый случайный процесс); наблюдаемыми являются моменты времени t1,t2,...,tk,... наступления событий потока. Рассматривается стационарный режим функционирования потока, поэтому переходными процессами на полуинтервале наблюдения [t0, t), где 10 - начало наблюдения, t - окончание наблюдения, пренебрегаем. Тогда без потери общности можно положить t0 = 0 . В этих предпосылках A(t) - сопровождающий стационарный кусочно-постоянный скрытый транзитивный марковский процесс с произвольным числом состояний n (n = 2,3,...). ОбобщШный асинхронный поток является обобщением асинхронного потока. Обобщение состоит в следующем: в момент перехода процесса A(t) из i-го состояния в j-е инициируется с вероятностью pij дополнительное событие, i, j = 1,n, j ф i; переход происходит в произвольный момент времени, не связанный с моментом наступления события пуассоновского потока с параметром , при этом инициирование дополнительного события осуществляется в j-м состоянии (сначала осуществляется переход из /-го состояния в j-е (переход первичен), затем - инициирование дополнительного события в j-м состоянии), i, j = 1, n, j ф i; переход и инициирование дополнительного события происходят мгновенно. Матрицы инфинитезимальных характеристик [28] процесса X(t) примут вид: -(X1 +«l) (1 " Л2)а12 ••• (1 - An)a1n (1 - p 21 )a21 -(X 2 +a2) ••• (1 - p 2n )a2n (1 - pn1)an1 (1 - pn2)an2 ••• -(X n +an ) X1 p 21a21 p12a12 Xo An a1n p 2n a2n X„ (1) Da D, pn1an1 pn2an2 где ai = -a;i, aii = - 2 ai/., i = 1, n ; a ij- > 0 , 0 < pj < 1, i, j = 1, n, j ф i . j =1, J *i Элементами матрицы Dj являются интенсивности переходов процесса X(t) из состояния в состояние с наступлением события. Недиагональные элементы матрицы D0 - интенсивности переходов процесса X(t) из состояния в состояние без наступления события. Диагональные элементы матрицы D0 - интенсивности выхода процесса X(t) из своих состояний, взятые с противоположным знаком. Положив в (1) pzy = 0, i, J = 1, n, j ф i, получаем матрицы инфинитезимальных характеристик процесса X(t) для асинхронного потока событий с произвольным числом состояний [26]. Наблюдения за потоком производятся на полуинтервале времени [t0, t) . Требуется на основании моментов наступления событий, наблюденных от момента t до момента t , оценить состояние процесса X(t) (потока) в момент времени t. Обозначим X (t) оценку состояния процесса X(t) в момент времени t. Для вынесения решения о состоянии процесса X(t) в момент времени t необходимо определить апостериорные вероятности w(Xi 11) = w(Xi 111,...,tm,t) = P(X(t) =Xi|t1,..., tm,t) , i = 1,n , того, что в момент времени t значение процесса X(t) = X,- (m - количество событий, наступивших в n моменты t1,...,tm на полуинтервале наблюдения [t0, t)), при этом 2w(X 11) = 1. Решение о состояi=1 нии процесса X(t) (потока) выносится по критерию максимума апостериорной вероятности [27], согласно которому X(t) = Xt, если w(X; 11) > w(Xj 11) , j = 1, n. 2. Рекуррентное соотношение для апостериорных вероятностей состояний потока Согласно методике [29], рассмотрим дискретные наблюдения за потоком через достаточно малые промежутки времени длительности At. Пусть наблюдения за потоком начинаются в момент времени t = 0, и время t изменяется дискретно с шагом At: t(k^ = kAt, k = 0,1,.... Введем двумерный случайный процесс (X(k), rk), где X(k) = X(kAt) - значение процесса X(t) в момент времени t(k) = kAt (X(k) =Xt, i = 1 , n ); rk = rk (At) = r(kAt) - r((k -1)At) - число событий потока, наступивших на полуинтервале времени [(k- 1)At, kAt) длительности At, r^ = 0,1,..., k = 0,m . Поскольку на полуинтервале [-At, 0) наблюдение за потоком не производится, то r0 можем положить произвольным, например r0 = 0 . Обозначим X(m) = (X(0), X(1),..., X(m)) - последовательность неизвестных (ненаблюдаемых) значений процесса X(kAt) в момент времени kAt, k = 0, m (X(0) = X(0) = X , i = 1,n ). Обозначим rm = (r0, r1,...,rm) - последовательность чисел наблюденных событий за время от 0 до mAt на полуинтервалах [(к -1)At, kAt) длительности At, к = 0, m . Нетрудно показать, что компоненты двумерного случайного процесса (X(lc), Гк), к = 0, m, являются взаимно независимыми марковскими компонентами. Тогда для марковского процесса (к(к), Гк), к = 0, m +1, имеет место рекуррентная формула для апостериорных вероятностей [26]: n Inn - W (X | t + At) = 2 w (X, | t)P (X , rm+i Xi , rm ) Ц W (X, | t)p (Xк , W X,, rm ), j = 1, n , (2) i=1 / г=1к=1 где p (кj, rm+1 Xi, rm) - вероятность перехода процесса (к(к), rk) на полуинтервале [mAt, (m + 1)At) = [t, t + At) из состояния (X(m) = Xi, rm), i = 1,n , rm = 0,1,..., в состояние (X(m+1) =к; , rm+1) , j = n , rm+1 = 0,1,.... Исследуем переходную вероятность в (2) для рассматриваемого случая обобщенного асинхронного потока. Имеем P (Xj, rm+1 Xi, rm) = P (Xj Xi, rm)P (rm+1 Xi, rm, Xj ) ; i, j = 1, n . (3) Количество наблюденных событий на полуинтервале [mAt, (m + 1)At) состоит из событий пуассоновского потока интенсивности X(mAt) = Xi, i = 1, n , и дополнительных событий, инициируемых в моменты перехода процесса X(t) из i-го состояния в j-е (i, j = 1,n, j ^ i). В силу этого инициирование дополнительных событий связано с переходной вероятностью p (к j кi, rm); наступление же событий пуассоновского потока связано с вероятностью p(rm+1 , rm, Xj), т.е. rm, rm+1 - число событий пуассоновского потока, наблюденных на полуинтервалах [(m - 1)At, mAt), [mAt, (m + 1)At) соответственно. Отметим, что в силу малости величины At число событий rm = 0;1 (rm = 2,3,...), имеет вероятность o(At)), аналогично для rm+1. Количество переходов процесса X(t) на полуинтервале [mAt, (m +1)At) более одного также имеет вероятность o(At). Замечание 1. Ситуация: одновременное наступление события пуассоновского потока и переход процесса X(t) на интервале длительности At из i-го состояния в j-е (с инициированием дополнительного события либо без его инициирования) имеет вероятность o(At), i, j = 1, n, j ^ i. Первый сомножитель в (3) запишется в виде p(Xj kt, rm) = p(kj kt) , так как на значение процесса X((m +1)At) = X j в момент времени (m + 1)At число наблюденных событий rm на полуинтервале [(m - 1)At, mAt) не влияет (процесс X(t) «живет своей жизнью»); значение же X(mAt) = Xi процесса X(t) в момент времени t = mAt не зависит от предыстории в силу марковости процесса X(t) . Наконец, подчеркнем, что дополнительное событие на полуинтервале [mAt, (m + 1)At) наступает (либо не наступает) в j-м состоянии при переходе процесса X(t) из i-го состояния в j-е (i, j = 1, n, j ^ i). Это обстоятельство нужно отразить в вероятности p (Xj Xi) : p (Xj Xi) = pd (Xj Xi), d = 0;1, i, j = 1, n, j ф i; p (X X ) = po (X X ), i = 1, n . Если d = 0, то дополнительное событие на полуинтервале [mAt, (m + 1)At) с вероятностью (1 - piJ-) не инициируется, i, j = 1, n; pu = 0 , i = 1, n . Если d = 1, то дополнительное событие на полуинтервале [mAt, (m +1)At) инициируется с вероятностью pij, i,j = 1, n, j ф i. Рассмотрим второй сомножитель в (3). Имеем, во-первых, p(rm+1 Xi, rm, Xj) = p(rm+1 Xi, Xj), так как число событий rm+1, наблюденных на полуинтервале [mAt, (m +1)At), не зависит от числа событий rm, наблюденных на полуинтервале [(m - 1)At, mAt), в силу того, что потоки событий во всех состояниях процесса X(t) пуассоновские. Во-вторых, , Л ч p (Ъ , Гш+1 , X j) p (X j | Xt , rm+ )p (Xi, rm+) P (rm+1 1 Xi, X j) =-n , , =-n n , (..-• (4) ' p (Xi, X j ) p (X j 1 Xi )p (Xi ) Так как на значение процесса X((m + 1)At) = Xj в момент времени (m +1)At число наблюденных событий rm+1 на полуинтервале [mAt, (m +1)At), так же как и число наблюденных событий rm на полуинтервале [(m - 1)At, mAt), не влияет, то p(Xj | Xi, rm+1) = p(Xj | Xt) . Тогда из равенства (4) вытекает p(rm+1 | X,, Xj ) = p(rm+1 | X,) . В силу этого (3) приобретает вид: p (Xj, rm+1 | Xi, rm ) = pd (Xj | Xi )p (rm+1 | Xi) ' i, j = 1 n . (5) Подставляя (5) в (2), находим рекуррентное соотношение для апостериорных вероятностей состояний в случае обобщённого асинхронного потока событий: n Inn w (X j^t + At) = 2 w (Xi 11) pd (X j ^) p (rm+1 V4) 2 2 w (X ^ t) pd (X ^X i) p (rm+11X i), (6) i=1 / i=1s=1 d = 0;1, rm+1 = 0;1, j = 1, n. 3. Система дифференциальных уравнений и формулы пересчета для апостериорных вероятностей Пусть временной полуинтервал [t, t + At) расположен на временной оси между моментами наступления соседних событий обобщенного асинхронного потока, скажем, между моментами tk и tk+^ (события в моменты времени tk и tk+^ могут быть событиями пуассоновского потока либо дополнительными событиями, либо и теми и другими). Тогда на полуинтервале [t, t + At) нет событий потока. Последнее означает, что в (6) d = 0, rm+1 = 0 . Тогда учитывая (1), имеем po(Xj |Xj) = p(Xj |Xj) = 1 + ^jjA + o(A), j = Tn; (7) p0 (Xj | Xi) = (1-py )ay At+o(At) , i, j = 1, n, i * j; (8) p (rm+1 = 0 | Xj) = 1 - Xi At + o(At) , i = 1n . (9) Лемма 1. На интервале времени (tk, tk+l) , k = 0,1,..., т.е. между моментами наступления соседних событий обобщенного асинхронного потока, апостериорные вероятности w(X j 11), j = 1,n, удовлетворяют следующей системе нелинейных дифференциальных уравнений: dw(X, 11) n -j- = 2[(1 - p,j)%■ -ЩMh 11) + w(Xj 11)Z[X, + ZpIsaIS]w(Xi 11), (10) dt i=1 i=1 s=1 n n где j = 1, n, tk < t < tk+1, k = 0,1,...; pjj = pu = 0; 5 ij - символ Кронекера. Доказательство. Обозначим в (6) A^j) - числитель, B0 - знаменатель. Учитывая введенные обозначения, формулы (7)-(9) и проделывая необходимые преобразования, находим (11) Aj = Z w (X 11) p0 (Xj | X) p (rm+1 = 0X) = (1 - Xj At )w (Xj 11) + At 2(1 - pj )ajw (X 11) + o(At), i=1 i=1 pjj. = j =1,n; n n n n B0 =22 w(X,U ) p0(Xs^l) p(rm+1 = ) = 1 - At 2 w(Xl|t)[Xl + 2 p^ls ] + o(At), i=1 s=1 i=1 s=1 pn = 0, i = 1, n. Подставляя (11), (12) в (6) и принимая во внимание, что (1 - x) 1 = 1 + x + o(x), получаем w(kj 11 + At) = n n n _ = (1 - XJ At)w(XJ 11) + AtX(1 - Pj)avw(X{ 11) + Atw(X] | + Xpisais]w(Xi 11) + o(At), J = 1, n. i=1 i=1 s=1 Перенося w (X j 11) в левую часть последнего равенства, после чего деля левую и правую части равенства на At и устремляя At к нулю, приходим к (10). Лемма 1 доказана. Систему (10) необходимо дополнить начальными условиями: значениями апостериорных вероятностей в моменты наступления событий и в момент начала наблюдения за потоком. В силу замечания 1 рассмотрим ситуацию, когда на полуинтервале [t, t + At) наступает одно событие обобщенного асинхронного потока, скажем, в момент времени tk, k = 1,2,.... Рассмотрим два смежных промежутка времени [t, tk ), [tk, t + At) . Длительность первого промежутка есть At' = tk - t, длительность второго промежутка есть At" = t + At - tk . Тогда в (6) w(Xj 11 + At) = w(Xj | tk + At") , w(X11) = w(Xi I tk - At'), и рекуррентная формула (6) приобретает вид: X w(X,tk -At")pd (X j | X{)p(rm+r | X{) w (X jtk + At") = -:-, (13) X X w(X { I tk -At") pd (X s I X {) p (rm+! X {) i=ls=l J = 1n; (d = 0, rm+x = 1), (d = 1, rm+1 = 0); k = 1,2,... Начальные условия для системы (10) определяются в следующих леммах. Лемма 2. Апостериорные вероятности состояний обобщённого асинхронного потока w (X j 11), J = 1,n, в момент tk, k = 1,2,..., наступления события потока определяются формулой пересчета: n In n w(Xj Itk + 0) = Xjw(Xj Itk - 0) + X plj^ljw(Xl Itk - 0) Xw(X{ I tk - 0)[Xi + X pls*ls(14) i=1 / i=1 s=1 где J = 1,n; pjj = 0, pu = 0 ; k = 1,2,... Доказательство. Обозначим в (13) A1 t0 - 0 определяется системой дифференциальных уравнений (10), формулами пересчета вероятностей (14) и решением системы (20), в которых tk < t < tk+1, w(Xj | tk ) - w(Xj | tk + 0), w(Xj | tk+1) - w(Xj | tk+1 -0) (k - 0,1,...); для k - 0 имеет место равенство w (Xj 110) - - w(Xj 110 + 0) - n j (j - 1,n). Доказательство следует из (10), (14), (20) путем их синхронизации. Теорема 1 доказана. Замечание 3. Теорема 2 определяет, в частности, поведение апостериорных вероятностей на полуинтервале tk_, tk), т.е. между моментами наступления соседних событий, причем на правом конце полуинтервала имеет место значение w(Xj | tk) - w(Xj | tk - 0), на основе которого по формуле (14) находится вероятность w(Xj | tk + 0) (j - 1,n), являющаяся начальной для следующего полуинтервала tk, tk+1), k -1,2,... Таким образом, апостериорные вероятности w(Xj 11) в моменты наступления событий t1,t2,... претерпевают разрывы первого рода. 4. Явный вид апостериорных вероятностей в зависимости от времени Рассмотрим tk, j) (k - 0,1,...) - полуинтервал времени между моментами наступления соседних k-го и k +1 -го событий, либо, если k - 0, между моментом начала наблюдения за потоком и моментом наступления 1-го события. Следующая теорема определяет решение системы нелинейных дифференциальных уравнений (10) на временной оси в явном виде. Теорема 2. Апостериорные вероятности состояний обобщ1;нного асинхронного потока событий w(X j 11), j = 1,n, на полуинтервале времени [tk, tk+j), k = 0,1,..., определяются формулой n inn w(Xj 11) = X cs(k)уjs еш(t-tk7 XX X c ^)yls еш(t-tk) , j = 1,n, tk < t < tk+,, k = 0,1,...; (21) s=1 / l=1s=1 w(Xj 110) = w(Xj 110 + 0) = %j; w(Xj | tk) = w(Xj | tk + 0), k = 1,2,...; - корни (собственные числа) характеристического уравнения det D = 0, D = ||ds^|1n , dsl = asl (s,l = 1,n, s Ф l), dM = ass - ш (s = 1,n ), asi = [(1 - pis )als -Xl5ls ], 5ls - символ Кронекера, s, l = 1, n ; у js - компоненты собственного вектора Y(s) = (y1s,..., Уns)T, j,s = 1,n (либо уls; l,s = 1,n), определяемые из уравнения (A-rosE)y(s) = 0, s = 1, n, в котором yns = 1 (s = 1, n), A = ||asJ1" , E - единичная матрица; коэффициенты cs^k) являютn (]f ся решением системы линейных алгебраических уравнений: X cs у js = w(X j | tk + 0), j = 1, n, s=1 k = 0,1,...; вероятность w(Xj | tk + 0), k = 1,2,..., определяется формулой пересч1та (14), в которой w(X, | tk - 0), i = 1, n, вычисляется по формуле n ! n n _ w(X, | tk -0) = XXcJ(k-1)увеш'(tk-tk-^XXcke-(tk-tk- , i = 1,n , k = 1,2,... (22) s s=1 I l =1 s=1 Доказательство. Решим систему нелинейных дифференциальных уравнений (10) на полуинтервале [tk, tk+j), k = 0,1,..., с начальным условием w(Xj | tk) = w(Xj | tk + 0), j = 1,n, пут!м сведения е! к системе линейных дифференциальных уравнений. Преобразуем систему (10). Обозначим --n n zij =(1- Pij -5ij (иj =1, n), W) = X[X, + X Pi&i, ]w(X! 11). Тогда (10) примет вид: i=1 s=1 dw(X j 11) n dt =X Z,]'^iX,|t ' ' y"VX j = X zMXiU) + Y(t)w(X j|t), (23) i=1 j = 7n, tk < t < tk+1, w(Xj | tk) = w(Xj | tk + 0), k = 0,1,... Произведем замену искомых функций w(X j 11) в (23): w(X j|t) = y} (t)exp[ JT(x)dx], j = Ш, tk < t < tk+1, tk w(Xj | tk) = w(Xj | tk + 0) = yj(tk + 0) , k = 0,1,... (24) Подставляя (24) в (23), находим dyf (t) n - -j- = X zij-yi (t), j = 1, n, tk < t < tk+1, yj (tk ) = yj (tk + 0) = w(X j | tk + 0), k = 0,1,... (25) dt ,=1 Относительно yj (t), j = 1,n, получена система линейных дифференциальных уравнений с постоянными коэффициентами. Решение системы (25) выпишется в виде [32]: yj (t) = XC (%еш (t-tk), j = й, tk < t < tk+1, yj (tk ) = yj (tk + 0) = w(Xj | tk + 0), k = 0,1,... (26) s=1 n Так как X w(Xl 11) = 1, tk < t < tk+j, k = 0,1,..., то из (24), учитывая (26), получаем l=1 t /n t n n П exp[№)dx] = 1/ Xyl(t) = 1 XX XX Cs )yls еш'(t-tk), tk < t < tk+1, k = 0,1,... (27) ^ / l=1 / l=1s=1 Подставляя (26), (27) в (24), приходим к (21). Теорема 2 доказана. Формулы (14), (20)-(22) позволяют сформулировать алгоритм расчета апостериорных вероятностей w(kj 11), j = 1,n, в любой момент времени t (t > t0 = 0): 1) в момент времени t0 = 0 задаются вероятности w(kj 110 + 0) = пj , где пj - решение системы (20), j = 1П ; 2) по формуле (21) рассчитываются вероятности w (k j 11), j = 1, n, в любой момент времени t (0 < t < tx), где ^ - момент наблюдения первого события потока; 3) по формуле (22) рассчитываются вероятности w (k j 11), j = 1,n, в момент времени tj: w(kj 111) = w(kj 111 - 0); затем по формуле (14) производится пересчет апостериорных вероятностей в точке t = tj, при этом вероятности w (k j 111 + 0), j = 1, n, являются начальными условиями для w (k j 11) на следующем шаге алгоритма; 4) по формуле (21) рассчитываются апостериорные вероятности w (k j 11), j = 1, n, для любого t (tj < t < t2), где t2 - момент времени наступления второго события потока, и т.д. Параллельно по ходу вычисления апостериорных вероятностей w (k j 11), j = 1, n, в момент времени t выносится решение о состоянии процесса k(t) (потока) по критерию максимума апостериорной вероятности: k(t) = ki, если w(ki 11) = max w(kj 11), j = 1,n. Заключение Результаты, полученные в статье, дают возможность производить оценку состояний обобщенного асинхронного потока событий с произвольным (конечным) числом состояний по результатам текущих наблюдений (в течение некоторого временного интервала) за потоком. Это позволяет системе массового обслуживания адаптироваться (оперативно варьировать дисциплину обслуживания, режимы обслуживания и свою структуру) к изменяющимся состояниям потока. Выражения (14), (20)-(22) для оценки состояний обобщенного асинхронного потока событий с произвольным числом состояний получены в явном виде, что позволяет производить вычисления без привлечения численных методов. Сам же алгоритм оценивания состояний потока обеспечивает минимум полной (безусловной) вероятности ошибки вынесения решения.

Ключевые слова

обобщенный асинхронный дважды стохастический поток событий, апостериорная вероятность, оптимальная оценка состояний, generalized asynchronous doubly stochastic flow of events, a posteriori probability, optimal states estimation

Авторы

ФИООрганизацияДополнительноE-mail
Горцев Александр МихайловичТомский государственный университетпрофессор, доктор технических наук, заведующий кафедрой прикладной математики Института прикладной математики и компьютерных наукa-gortsev@mail.ru
Нежельская Людмила АлексеевнаТомский государственный университетдоцент, доктор физико-математических наук, профессор кафедры прикладной математики Института прикладной математики и компьютерных наукludne@mail.ru
Всего: 2

Ссылки

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.
Башарин Г.П., Кокотушкин В.А., Наумов В.А. О методе эквивалентных замен расчёта фрагментов сетей свя зи. Ч. 1 // Известия АН СССР. Техническая кибернетика. 1979. № 6. С. 92-99.
Neuts M.F. A versatile Markovian point process // Journal of Applied Probability. 1979. V. 16. P. 764-779.
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.
Diamond J.E., Alfa A.S. The MAP/PH/1 retrial queue // Communications in Statistics Stochastic Models. 1998. V. 14. P. 1151-1177.
Лившиц К.И., Сухотина Л.Ю., Шифердекер И.Ю. Математическая модель деятельности некоммерческого фон да при дважды стохастическом потоке платежей // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2007. № 1. С. 36-43.
Card H.C. Doubly stochastic Poisson processes in artificial neural learning // Neural Networks, IEEE Transactions. 1998. V. 9, is. 1. P. 229-231.
Лившиц К.И., Ульянова Е.С. Модель управления запасами однородной продукции с релейным управлением темпом производства и MMP-потоком моментов продаж // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2018. № 44. С. 50-61.
Башарин Г.П., Самуйлов К.Е., Яркина Н.В., Гудкова И.А. Новый этап развития математической теории теле трафика // Автоматика и телемеханика. 2009. № 12. С. 16-28.
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.
Вишневский В.М., Ларионов А. А. Открытая сеть массового обслуживания с коррелированными входными потоками для оценки производительности широкополосных беспроводных сетей // Информационные технологии и математическое моделирование (ИТММ-2016) : материалы XV Междунар. конф. Катунь, 12-16 сентября 2016. Томск : Изд-во Том. ун-та, 2016. Ч. 1. С. 36-50.
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.
Вишневский В.М., Ляхов А.И. Оценка пропускной способности локальной беспроводной сети при высокой нагрузке и помехах // Автоматика и телемеханика. 2001. № 8. С. 81-96.
Гайдамака Ю.В., Зарипова Э.Р., Самуйлов К.Е. Модели обслуживания вызовов в сети сотовой подвижной связи. М. : Изд-во РУДН, 2008. 72 с.
Дудин А.Н., Клименок В.И. Расчет необходимого числа каналов в современных телекоммуникационных сетях // Информатизация образования. 2005. № 4. С. 56-68.
Наумов В.А., Самуйлов К.Е., Яркина Н.В. Теория телетрафика мультисервисных сетей. М. : Изд-во РУДН, 2007. 191 с.
Ниссенбаум О.В., Пахомов И.П. Аппроксимация сетевого трафика моделью альтернирующего потока событий // Прикладная дискретная математика. 2009. № 1. С. 78-79.
Самуйлов К.Е., Яркина Н.В., Гудкова И.А. Математическая модель управления доступом в сетях Triple play // IV Междунар. конф. по проблемам управления : сб. трудов. М. : Изд-во ИПУ, 2009. С. 1722-1730.
Горцев А.М., Нежельская Л.А. О связи МС-потоков и МАР-потоков событий // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2011. № 1 (14). С. 13-21.
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.
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.
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.
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.
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.
Горцев А.М., Калягин А.А., Нежельская Л.А. Оценка максимального правдоподобия длительности мертвого времени в обобщенном полусинхронном потоке // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2015. № 1 (30). С. 27-37.
Горцев А.М., Зуевич В.Л. Оптимальная оценка состояний асинхронного дважды стохастического потока событий с произвольным числом состояний // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. 2010. № 2 (11). С. 44-65.
Левин Б.Р. Теоретические основы статистической радиотехники. М. : Сов. радио, 1968. Кн. 2. 504 с.
Назаров А.А., Терпугов А.Ф. Теория вероятностей и случайных процессов. Томск : Изд-во НТЛ, 2006. 204 с.
Хазен Э.М. Методы оптимальных статистических решений и задачи оптимального управления. М. : Сов. радио, 1968. 256 с.
Хинчин А.Я. Работы по математической теории массового обслуживания. М. : Физматгиз, 1963. 236 с.
Лившиц К.И. Линейная алгебра и аналитическая геометрия. Томск : Изд-во НТЛ, 2011. 252 с.
Эльсгольц Л.Э. Дифференциальные уравнения и вариационное исчисление. М. : Наука, 1969. 424 с.
 Оптимальная оценка состояний обобщённого асинхронного потока событий с произвольным числом состояний | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/2

Оптимальная оценка состояний обобщённого асинхронного потока событий с произвольным числом состояний | Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика. 2019. № 47. DOI: 10.17223/19988605/47/2