Автоматика и телемеханика, № 2, 2015
Стохастические системы, системы массового обслуживания
© 2015 г. А.В. БОРИСОВ, д-р физ.-мат. наук (ABorisov@ipiran.ru) (Институт проблем информатики РАН, Москва), Б.М. МИЛЛЕР, д-р физ.-мат. наук (BMiller@iitp.ru) (Институт проблем передачи информации им. А.А. Харкевича РАН, Москва), К.В. СЕМЕНИХИН, д-р физ.-мат. наук (SiemenKV@rambler.ru) (Московский авиационный институт)
ФИЛЬТРАЦИЯ МАРКОВСКОГО СКАЧКООБРАЗНОГО ПРОЦЕССА ПО НАБЛЮДЕНИЯМ МУЛЬТИВАРИАНТНОГО ТОЧЕЧНОГО ПРОЦЕССА1
Сформулирована и решена задача оптимальной фильтрации марковского процесса с конечным числом состояний по дискретным наблюдениям, поступающим в случайные моменты времени. Установлено, что искомая оценка описывается конечномерной дифференциально-разностной системой, которая допускает явное решение. Полученные теоретические результаты применены к решению задачи мониторинга состояния телекоммуникационного соединения.
1. Введение
Непрерывное совершенствование современных систем автоматического управления биржевой торговлей и телекоммуникационными системами стимулирует развитие теории оптимального оценивания для класса стохастических систем, в которых смена состояния и поступление новых наблюдений происходит дискретно в случайные моменты времени [1—6]. Эти системы наблюдения удобно описывать с использованием семимартингалов — специального класса случайных процессов, представляющих собой естественное обобщение диффузионных и скачкообразных моделей. В [7] методами стохастического анализа были получены уравнения оптимальной оценки одного семимартингала по наблюдениям другого. Однако для применения этих уравнений необходимо знать характеристики совместного распределения, определяющие структуру наблюдаемого процесса и его зависимость от состояния системы. Поэтому так же, как в теории оптимальной фильтрации диффузионных процессов, в случае скачкообразных наблюдений не существует универсального алгоритма оптимального оценивания, эффективного с точки зрения численной реализации. Таким образом, выявление новых классов систем наблюдения, для которых искомая оценка определяется конечномерной системой уравнений, является востребованной задачей.
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проекты № 13-01-00406 и № 13-07-00408).
За последние 30 лет в этой области оценивания достигнут определенный прогресс. В [8] получены необходимые и достаточные условия существования конечномерного представления оптимальной оценки для стохастической дифференциальной системы, в которой пара «состояние—наблюдения» обладает марковским свойством. В [5] для синтеза оптимального управления частично наблюдаемой системой массового обслуживания найдено решение задачи фильтрации по наблюдениям, которые совместно с оцениваемым процессом допускают мартингальное разложение. В [1] исследована задача оценивания диффузионного марковского процесса по наблюдениям, поступающим в случайные моменты времени. При этом формально искомая оценка удовлетворяет некоторой конечномерной непрерывно-дискретной системе, но фактически зависит от условных моментных характеристик, которые не имеют явного представления и могут быть вычислены лишь приближенно, например с помощью метода Монте-Карло.
Предмет изучения данной работы — специальный класс систем, в которых состояние и наблюдения описываются процессами с непрерывным временем и конечным множеством значений, но лишь оцениваемый процесс X предполагается марковским. Рассматриваемый процесс наблюдений в стохастическом анализе принято называть мультивариантным точечным процессом [7]. Он однозначно определяется случайной последовательностью пар {т(к),У(к)}, где т (к) —момент измерения, а У (к) —результат измерения. Связь между оцениваемым и наблюдаемым процессами задается с помощью условных распределений величин т (к + 1), У (к + 1) относительно их предыдущих значений и состояния ХТ(£), взятого в последний момент измерений.
Основной результат статьи состоит в том, что оптимальная оценка фильтрации является решением некоторой конечномерной дифференциально-разностной системы. Структура этой системы такова, что при поступлении новых наблюдений производится пересчет предыдущего значения оценки, а затем вплоть до следующего момента измерений оценка удовлетворяет дифференциальному уравнению с разрывной правой частью, которая также была пересчитана на предыдущем шаге. Примечательно, что это уравнение допускает явное решение. В работе синтезирован рекуррентный алгоритм оптимальной нелинейной фильтрации марковского скачкообразного процесса по мультивариантному точечному процессу.
Полученные теоретические результаты применены к решению прикладной задачи мониторинга состояния телекоммуникационного соединения. В результате проведения численных экспериментов, выполненных на основе реальных и модельных данных, обоснована адекватность предложенной математической модели и продемонстрирована эффективность разработанного алгоритма оценивания.
2. Постановка задачи
Начнем с неформального описания рассматриваемой проблемы.
Пусть стохастическая система, скажем телекоммуникационное соединение, описывается марковским процессом {Х^, £ ^ 0}, который может находиться в одном из нескольких состояний (например, «свободно», «загружено», «нет
2* 35
связи»). Хотя состояние системы не доступно прямому наблюдению, имеется последовательность дискретных измерений Y (k), поступающих в случайные моменты времени т(k), k € N. Эти наблюдения могут быть получены в результате отправки сервисных сообщений с целью проверки качества соединения. Пусть т (k) —момент отклика системы на k-е сообщение, тогда Y (k) — результат этого отклика: «получено подтверждение» или «подтверждения нет».
Предположим, что если состояние системы XT(k) в момент последнего отклика известно, то известно и распределение времени ожидания следующего отклика т(k + 1). Если же этот момент уже наступил, то определено, с какой вероятностью было «получено подтверждение». Таким образом, априорная информация о рассматриваемой системе наблюдения исчерпывается двумя условными распределениями:
(1) Law{T(k + 1) | т(k),XT(k)} и Law{Y(k + 1) | т(k + 1),Xt(k)}.
Изучаемая задача оценивания состоит в нахождении условного распределения вероятностей текущего состояния Xt по всем имеющимся к моменту t наблюдениям:
(2) Law{Xt | (Y(k)^(k)): т(k) < t},
где {(Y(k)^(k))}kgN — мультивариантный точечный процесс [7], который также может быть представлен парой процессов «процесс значений — считающий процесс скачков»:
(3) Yt = Y (k), Nt = k при t € [т (k),т (k + 1)), k ^ 0, где т (0) = 0.
Одного процесса значений Yt для описания мультивариантного точечного процесса недостаточно, так как с положительной вероятностью значения Y (k) в соседние моменты т (k) могут совпадать, т.е. Y (k) = Y (k + 1). В этом случае использование только значений Y привело бы к потере информации о факте прихода измерений Y (k + 1) в момент времени т (k + 1).
Наблюдения {Yt,Nt, t^ 0} принципиально не могут обладать марковским свойством, поскольку вероятность получения подтверждения об успешной доставке посланного сообщения зависит от того, как давно не было подтверждения. Этот факт — следствие того, что в современных телекоммуникационных системах время отклика ограничено известной величиной — тайм-аутом (retransmission timeout), являющимся настраиваемым параметром сетевого протокола. Однако даже если эта верхняя граница достаточна велика, а система находится в стационарном режиме, истинное распределение времени отклика все равно будет сильно отличаться от экспоненциального.
Отметим, что при описании состояния телекоммуникационного соединения указанных проблем обычно не возникает. Поэтому модель марковского скачкообразного процесса {Xt, t ^ 0} оказывается вполне адекватной.
Теперь перейдем к описанию дополнительных предположений, которые необходимо сделать о рассматриваемой системе наблюдений.
Пусть марковский процесс Xt и процесс наблюдений (Yt, Nt) заданы на вероятностном пространстве (Q, F, P), имеют непрерывные справа траектории
и принимают значения в множествах Sn и Sm , составленных из единичных векторов, т.е.
Xt е Sn 4 (eb.. .,eN} с RN, Y e Sm = {/1,... ,/m } с Rm . Допустим, что для оцениваемого процесса:
A) заданы начальное распределение E(Xo} = po и матрица интенсивно-стей переходов Л^), элементы которой — ограниченные кусочно-непрерывные функции;
Б) процесс Xt представим в виде решения стохастической дифференциальной системы
t
(4) Xt = Xo + У Лт(з)Х5_ ds + MtX,
o
где MtX — мартингал, согласованный с расширенным потоком ст-алгебр Ft =
4 (Xs, (Ys,Ns), s ^ t}, причем Ft является непрерывным справа. Относительно процесса наблюдений предположим следующее:
B) моменты поступления наблюдений удовлетворяют условиям
0 < т(1) < т(2) < ... и lim т(k) = P-п.н.
(где п.н. — почти наверное);
Г) условное распределение момента поступления очередного наблюдения
(5) Gk(В) 4 р {т(k + 1) е В | S(k) v FXX}, в е B(R+), k ^ 0, относительно ст-алгебр
(6) S(k) 4 ct(Y(0), т(1), Y(1),..., т(k), Y(k)}, JX 4 CT(Xt, t > 0}
может быть представлено в виде
(7) Gk(B) = y 0T(t)Xr(k) Фк(dt),
в
где фк(t) 4 col [фк (t),..., (t)] — случайная вектор-функция, а Фк — неотрицательная ст-конечная случайная мера, такие что величины фк(t) и Фк(В)
5 (^-измеримы;
Д) условное распределение результата очередного наблюдения
(8) Цк 4 E{Y(k + 1) | ст(т(k + 1)}v S(k) V JX } , k ^ 0,
относительно момента его поступления и ст-алгебр (6) допускает представление
(9) Цк = ЯТ(т (k + 1))Xr (к),
где т —транспонирование, а Qk(t) —матрица с 3(к)-измеримыми элементами Qk (t) â P{Y (к + 1) = f | Xr (k) = ei, т (к + 1) = t, Y (к), т (к), ... ..., F(l), r(l), F(0)}, ¿ = Щ j TU. 0;
Е) условное распределение начального наблюдения зависит лишь от начального состояния оцениваемого процесса, т.е.
(10) r â E{Y(0) | FxX} = RTXo,
где R — соответствующая детерминированная N x M-матрица. Задача оптимального оценивания заключается в нахождении
(11) Xt â E{Xt | Gt} , где Gt = ^{(Ys,Ns), 0 < s < t}.
Условие А), накладыва
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.