Optimal estimate of the states of a generalized asynchronous event flow with an arbitrary number of states under conditi.pdf Системы и сети массового обслуживания (СМО и СеМО) широко применяются в качестве математических моделей различных технических, физических, экономических и других систем. Случайные потоки событий, являющиеся основными элементами СМО и СеМО, в свою очередь, применяются в качестве математических моделей различных реальных процессов, протекающих в таких системах. В частности, случайные потоки событий служат математическими моделями информационных потоков сообщений, функционирующих в телекоммуникационных сетях [1-3]. Современными математическими моделями информационных потоков в телекоммуникационных сетях являются дважды стохастические потоки событий. Одними из первых работ, положивших начало систематическому исследованию дважды стохастических потоков, были работы [4-9]. Большинством авторов исследования СМО и СеМО осуществляются в условиях, когда все события входящего потока доступны наблюдению. В реальности же зарегистрированное событие может создать период мертвого времени для регистрирующего прибора [10], в течение которого другие события потока становятся ненаблюдаемыми для регистрирующего прибора (теряются). В этой связи можно считать, что мертвое время выступает искажающим фактором при решении задачи оценивания, так как эффект мертвого времени влечет за собой потери событий потока, что отрицательно сказывается на оценивании как состояний, так и параметров потока. Все устройства регистрации делятся на две группы. Первую группу составляют устройства с непродлевающемся мертвым временем [11-13], вторую - устройства с продлевающемся мертвым временем [14]. Период ненаблю-даемости событий потока может продолжаться некоторое фиксированное время, а также может быть случайным. Здесь рассматривается случай неродлевающегося мертвого времени фиксированной длительности. В работе [15] введен обобщенный асинхронный поток событий с двумя состояниями (обобщенный MMPP-поток), функционирующий при отсутствии мертвого времени. Обобщение результатов этой работы получено в статье [16], где решена задача оптимального оценивания состояний обобщенного асинхронного потока событий с произвольным числом состояний в отсутствии мертвого 35 А.М. Горцев, Л.А. Нежельская времени. В настоящей статье, являющейся непосредственным развитием работы [16], решается задача об оптимальной оценке состояний обобщенного асинхронного дважды стохастического потока событий с произвольным (конечным) числом состояний при непродлевающемся мертвом времени. Предлагается алгоритм оптимальной оценки состояний, когда решение о состоянии потока выносится по критерию максимума апостериорной вероятности [17]. Данный критерий обеспечивает минимум полной (безусловной) вероятности ошибки вынесения решения [18]. 1. Постановка задачи Рассматривается обобщенный асинхронный поток событий (далее - поток), сопровождающий процесс (интенсивность) λ(t) которого есть кусочно-постоянный случайный процесс с n состояниями: λ(t) принимает значения из дискретного множества значений {λ ,...,λ }, λ1 > λ2 >...> λn ≥ 0. Будем говорить, что имеет место і-е состояние процесса λ(t), если λ(t) = λi, i = 1,n , n = 2,3,... Если имеет место і-е состояние процесса λ(t), то в течение временного интервала, когда λ(t) = λ^, имеет место пуассоновский поток событий с параметром (интенсивностью) λ , i =1,n . Длительность пребывания процесса λ(t) (потока) в і-м состоянии распределена по экспоненциальному закону с параметром , i = 1, n . Рассматривается стационарный режим функционирования потока, поэтому переходными процессами на полуинтервале наблюдения [t0,t), где t0 - начало наблюдения, t - окончание наблюдения, пренебрегаем. Тогда без потери общности можно положить t = 0 . В этих предпосылках λ(t) - сопровождающий стационарный кусочно-постоянный скрытый (принципиально ненаблюдаемый) транзитивный марковский процесс с произвольным числом состояний n (n = 2,3,...). Обобщенный асинхронный поток является обобщением асинхронного потока [11]. Обобщение состоит в следующем: в момент перехода процесса λ(t) из і-го состояния в і-е инициируется с вероятностью pij дополнительное событие (с вероятностью (1- pij) дополнительное событие не инициируется), i, j = 1, n, j ≠ i; переход происходит в произвольный момент времени, не связанный с моментом наступления события пуассоновского потока с параметром \\, при этом инициирование дополнительного события осуществляется в j-м состоянии (сначала осуществляется переход из /-го состояния в j-е (переход первичен), затем - инициирование дополнительного события в j-м состоянии), i, j = 1,n, j ≠ i; переход и инициирование дополнительного события происходят мгновенно. Матрицы инфинитезимальных характеристик процесса λ(t) примут вид: где αi = -αii -(λ 1 +«1) (1- p12)«12 ... (1- p1n)«1n λ1 p12«12 . .. p1n«1n D0= (1 - p 21)а21 -(λ 2 +“2) ... (1- p2n)«2n ,D1= p21«21 λ2 . .. p2n«2n (1- pn1 )«n1 (1- pn2 )«n2 ... -(λn +«n) pn1«n1 pn2«n2 . .. λn n = - Σ « i ,i =1, n; « >0, 0≤ pij ≤1, i, j = 1, n, j ≠i. (1) j=1, j ≠i Положив в (1) pjj = 0, i, j = 1, n, j ≠ i, получаем матрицы инфинитезимальных характеристик процесса λ(t) для асинхронного потока событий с произвольным числом состояний. После каждого зарегистрированного в момент времени tk события (как события пуассоновского потока с параметром λi, так и дополнительного события) наступает время фиксированной длительности T (мертвое время), в течение которого другие события исходного обобщенного асинхронного потока недоступны наблюдению (теряются). События, наступившие в течение мертвого времени, не вызывают продления его периода (непродлевающееся мертвое время). По окончании мертвого времени первое наступившее событие снова создает период мертвого времени длительности T и т.д. 36 Оптимальная оценка состояний обобщенного асинхронного потока событий Таким образом, наличие мертвого времени приводит к тому, что в исходном обобщенном асинхронном потоке происходит частичная потеря событий. В силу этого на полуинтервале [t , t ) наблюдается «прореженный» исходный поток, будем называть его наблюдаемым потоком. Требуется на основании последовательности временных моментов (от момента t0 до момента t) наступления событий наблюдаемого потока оценить состояние процесса λ(t) (потока) в момент времени t. Обозначим λ (t) оценку состояния процесса λ(t) в момент времени t. Для вынесения решения о состоянии процесса λ(t) в момент времени t необходимо определить апостериорные вероятности w(λ |t) = w(λ |t ,...,t ,t) = =P(λ(t)=λ |t ,..., t ,t), i=1,n, того, что в момент времени t значение процесса λ(t)=λi (m - количество событий, наступивших в моменты времени t ,...,t на интервале наблюдения (t , t)), при этом ∑w(λi |t)=1. Решение о состоянии процесса λ(t) (потока) выносится по критерию максимума апо-i=1 стериорной вероятности [17], согласно которому λ(t) = λi, если w(λi 11) ≥ w(λJ 11) , j = 1, n. 2. Явный вид апостериорных вероятностей Рассмотрим полуинтервал [⅛,∣), k = 1, 2, ..., между двумя соседними событиями наблюдаемого потока. Так как моменты времени наступления событий в наблюдаемом потоке случайны, то длительность полуинтервала [t,t ) - случайная величина. Длительность начального полуинтервала [t,t) - также случайная величина. Таким образом, значение длительности полуинтервала 1) есть τk = tk+j - tk, к = 0, 1, ... С другой стороны, так как наступившее в момент времени tk событие наблюдаемого потока порождает период мертвого времени длительности T, то τk = T + ¾, где - значение длительности интервала между моментом окончания периода мертвого времени и моментом tk+1 . Таким образом, временной полуинтервал [t ,t ) разбивается на два смежных полуинтервала: первый - [tk,tk+T), второй - [tk+T,tk+1). Условия нахождения апостериорных вероятностей w(λi |t), i=1,n, на полуинтервале [tk,tk+T) длительности T и на полуинтервале [tk+T,tk+1) , значение длительности которого есть , принципиально разные. Кроме того, для нахождения вероятностей w(λ |t), i=1,n, необходимо точно знать длительность T мертвого времени. В противном случае отсутствие информации о длительности T мертвого времени делает попытку строгого нахождения вероятностей w(λ |t), i=1,n, невозможной. В [16] сформулирован алгоритм расчета апостериорных вероятностей w(λJ |t), J =1,n, для случая отсутствия мертвого времени (T =0). При этом поведение w(λJ |t), J =1,n, на полуинтервале [t ,t ), k =1, 2, ..., между соседними событиями исходного обобщенного асинхронного потока, ,а также на полуинтервале [t0,t1) между началом наблюдения и наблюдением первого события определяется выражением (k) ∑ cs(k)γJs e s=1_ nn ∑∑ Ilc. , w(λn 11) = 1 _∑w(λj 11), j=1 --------= α + ∑ (а (6) dt nn p tk ≤ t < tk + T, j = 1,n _ 1, k = 1,2,... 38 Оптимальная оценка состояний обобщенного асинхронного потока событий Доказательство. Матрицы инфинитезимальных характеристик (1) процесса λ(t) для рассматриваемого полуинтервала мертвого времени [tk,tk ÷T), k = 1,2,..., примут вид D0 =∣∣αij^ , D = ∣∣0∣∣j^ ; ^ > 0, i, J = 1,n , i ≠ J ; ^ = - ∑^j, i = 1,n ; так как наступление событий как пуассоновского по-j=1,j ^i тока, так и дополнительных событий не оказывает влияния на поведение процесса λ(t ) (процесс λ(t ) «живет своей жизнью» и в течение периода мертвого времени). Рассмотрим полуинтервал [t,t ÷ Δt) , где Δt - достаточно малая величина, и t^ < t ÷Δt < tk ÷ T, т.е. полуинтервал [t, t ÷Δt) расположен внутри полуинтервала [t ,t ÷T), k =1,2,... Найдем апостериорную вероятность w(λ |t ÷Δt) того, что в момент времени t ÷ Δt процесс λ(t) находится в у-м состоянии, J = 1, п . Зафиксируем j-е состояние (J = 1, п ). Пусть в момент времени t процесс λ(t) находится в j-м состоянии и на полуинтервале [t, t ÷ Δt) процесс λ(t) не перешел в і-є состояние (i = 1, п , i ≠ J ), т.е. остался в j-м состоянии. Вероятность этого события есть w(λJ | t)(1 ÷ (XjjΔt) ÷ o(Δt) . Пусть в момент времени t процесс λ(t) находится в і-м состоянии (i = 1, п) и на полуинтервале [t, t ÷ Δt) процесс λ(t) перешел в у-е состояние (i ≠ J ). п Вероятность этого события есть ∑X Δtw(λ |t) ÷ o(Δt). Другие возможности имеют вероятность i =1,i ≠ J o(Δt) . Тогда имеем w(λ' 11 ÷ Δt) = (1 ÷ (^ jjΔt)w(λJ 11) ÷ Δt ∑ (^Jw(λ 11) ÷ o(Δt), J = 1, п . (7) i=1,i ≠J Производя в (7) необходимые преобразования, после чего переходя к пределу при Δt → 0 , приходим к линейной однородной системе дифференциальных уравнений [20] для вероятностей w(λ | t): dw(λ j 11) " - (8) .j =∑x jW(λ ,|1) (1, ≤ 1 < 1, ÷ T, J = 1, п , k = 1,2,...), dt i =1 с начальными условиями w(λ |t =t ) = w(λ |t ÷ 0), k =1,2,... Начальные условия для системы (8) формируются следующим образом. На полуинтервале [t ÷T,t ), k = 2,3,..., смежном полуинтервалу ÷ T), вероятности w(λj 11) рассчитываются по формуле (2), где w(λj | 1, ÷ 0) заменяются на w(λj 11^-1 ÷ T), k = 2,3,..., J = 1,п; затем в момент времени t = tk , k = 2,3,..., происходит пересчет вероятностей w(λj 11) по формуле (3), так что их значения в точке t = tk есть w(λj | 1, ÷ 0), J = 1, п , k = 2,3,... , которые являются начальными условиями для системы (8). Для граничного интервала [⅛, ) расчет вероятности w(λj 11), J = 1, п, производится по формуле (2) с их последующим пересчетом по формуле (3) в момент времени t = t . Апостериорные вероятности w(λJ | t) для любого t п-1 удовлетворяют условию нормировки. Тогда выражая, например, w(λ^ 11) = 1 - ∑ w(λj 11) и подстав- J=1 ляя данное представление в (8) приходим к (6). Теорема 1 доказана. Замечание 1. Поскольку λ(t) - транзитивный марковский процесс, то при 1 → ∞ апостериорные вероятности стремятся к пределам w(λJ), J = 1, п, не зависящим от начальных условий [19]. Тогда система (6) при t → ∞ приобретает вид: п-1 _ (9) ∑ (xnJ -ХУ )w(λ, ) =XnJ , j = 1, п - 1 , w(λ п ) = 1 - ∑ w(λJ ). i=1 J =1 39 А.М. Горцев, Л.А. Нежельская Полученная система линейных неоднородных алгебраических уравнений (9) идентична системе (5), так что w(λj ) = πj∙, j = 1, n. Система (6) с начальными условиями (3) определяет поведение вероятностей w(λ j | t) , j=1,n, на полуинтервале [tk,tk+T) , k =1, 2,... , ее решение устанавливает следующая теорема. Теорема 2. Апостериорные вероятности состояний обобщенного асинхронного потока событий w(λ j | t) , j=1,n, на полуинтервале времени [t ,t +T) , k =1, 2,... , определяются формулой nn-1 (1q) w(λ j 11) = πj + ∑ Ajib,ke^ •, w(λ n 11) = 1 - ∑ w(λ j 11), I=1 j=1 j = 1,n -1, t^ ≤ t < t^ + T, k = 1,2,..., где π (j = 1,n) - решение системы (5); A- элементы матрицы A =|Aji^ , составленной из соб- _ Il Il n -1 ~ ственных векторов матрицы α = ∣∣α(Uji =aij -^nj) так, что і-й столбец матрицы A соответствует собственному числу а(i), i = 1, n -1; коэффициенты b^(^k) являются решением системы линейных неоднородных алгебраических уравнений n-1 (.) _ ∑A^b(k)ea *k = w(λj 11, + 0)-πj (j = 1,n-1, k = 1,2,...), i=1 в которой w(λ j | tk + 0) определяются формулой (3). Замечание 2. Из (9) вытекает, что πj∙ = w(λj) = limw(λj 11) при t → ∞, тогда из (10) следует, что все собственные числа а(), i = 1, n -1, отрицательны. Замечание 3. Из (10) следует, что ^'(k+t^, w(λn 11^ + T) = 1 -∑w(λ^. 11^ + T), j=1 n-^ /Z4 ( (11) w(λ j 11, + T) = π j + ∑ Ajbike" i=1 j=1,n-1, k = 1, 2,... Полученные формулы позволяют сформулировать алгоритм расчета апостериорных вероятностей w(λ j | t) , j =1,n , и алгоритм принятия решения о состоянии процесса λ(t) в любой момент времени t . 3. Алгоритм принятия решения о состоянии процесса λ(t ) Алгоритм расчета апостериорных вероятностей w(λ j | t) в любой момент времени t : 1) в момент времени находятся w(λj 110^ + 0) = w(λ j 110^ = 0) = πj (j = 1, n) как решение системы (5); 2) по формуле (2) для k = 0 рассчитываются вероятности w(λ j | t) ( j=1,n) в любой момент времени t (0 ≤ t < t1), где t1 - момент наблюдения первого события наблюдаемого потока; 3) по формуле (2) для k = 0 рассчитываются вероятности w(λ j | t) , j=1,n, в момент времени t1 : w(λ j|t1) = w(λ j| t1-0) ; 4) k увеличивается на единицу, и по формуле (3) для k = 1 производится пересчет вероятностей w(λ j | t) в момент времени t = t1, при этом w(λj | t1 +0) ( j=1,n) являются начальными значениями для расчета w(λ j | t) по формуле (10); 4q Оптимальная оценка состояний обобщенного асинхронного потока событий 5) по формуле (10) для k =1 рассчитываются вероятности w(λj |t) ( j=1,n) в любой момент времени t ( t1< t < t1 +T); 6) по формуле (11) для k =1 рассчитываются вероятности w(λj |t) ( j=1,n) в момент времени t =t1 +T , т.е. вероятности w(λj |t1 +T) ; при этом w(λj |t1 +T) ( j=1,n) являются начальными значениями для вычисления вероятностей w(λ j |t) на следующем шаге алгоритма; 7) для k =1 по формуле (2), в которой w(λj |t1 +0) заменяются на w(λj |t1 +T), рассчитываются вероятности w(λj |t) ( j=1,n) в любой момент времени t (t1+T

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