Авторефераты по всем темам >> Авторефераты по техническим специальностям

На правах рукописи

Зуевич Владимир Леонидович

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

05.13.01 - Системный анализ, управление и обработка информации (в отраслях информатики, вычислительной техники и автоматизации)

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Томск - 2012

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования Национальный исследовательский Томский государственный университет на кафедре исследования операций

Научный консультант: доктор технических наук, профессор Горцев Александр Михайлович

Официальные оппоненты: Медведев Геннадий Алексеевич, доктор физико-математических наук, профессор, Белорусский государственный университет, профессор кафедры теории вероятностей и математической статистики Кошкин Геннадий Михайлович, доктор физико-математических наук, профессор, ФГБОУ ВПО Национальный исследовательский Томский государственный университет, профессор кафедры теоретической кибернетики

Ведущая организация: ФГБОУ ВПО Национальный исследовательский Томский политехнический университет

Защита состоится 21 июня 2012 г. в 14.30 час. на заседании диссертационного совета Д 212.267.12 при Томском государственном университете по адресу:

634050, г. Томск, пр. Ленина, 36, корп. 2, ауд. 212б.

Отзывы на автореферат (в двух экземплярах), заверенные гербовой печатью организации, просим направлять по адресу: 634050, г. Томск, пр. Ленина, 36.

С диссертацией можно ознакомиться в Научной библиотеке Томского государственного университета.

Автореферат разослан 18 мая 2012 г.

Ученый секретарь Тарасенко диссертационного совета Петр Феликсович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы. Усложнение структуры информационно-телекоммуникационных систем, интеграция различных систем связи, разнообразие программного и аппаратного обеспечения, протоколов передачи данных привели в начале 90-х годов XX века к созданию цифровых сетей интегрального обслуживания (Integrated Services Digital Networks - ISDN). Данные сети характеризуются тем, что по единым аппаратным средствам совместно передаются самые разнообразные виды информации - большие массивы данных, речь и видео в цифровой форме, факсимиле и т.д. Тогда же была предпринята успешная попытка создания адекватных математических моделей реальных информационных потоков, функционирующих в цифровых сетях интегрального обслуживания - так называемых дважды стохастических потоков. Одними из первых работ в этом направлении были работы М. Ньютса, Г.П. Башарина, В.А. Кокотушкина, В.А. Наумова.

Дважды стохастическим потоком называется такой поток событий, интенсивность которого является случайным процессом. Проведенные эксперименты показывают возможность аппроксимации реальных потоков событий дважды стохастическими потоками. Большое количество исследований дважды стохастических потоков и систем массового обслуживания с входящими дважды стохастическими потоками было проведено такими учеными как А.Ф. Терпугов, А.М. Горцев, А.А. Назаров, - в Томском государственном университете;

Г.А. Медведев, А.Н. Дудин, В.И. Клименок, Г.В. Царенков - в Белорусском государственном университете; Ю.В. Малинковский - в Гомельском университете; М.А. Маталыцкий - в Гродненском университете; Г.П. Башарин, П.П. Бочаров, А.В. Печинкин - в Российском университете Дружбы народов; Н.И Головко, В.В. Катрахов, Н.А. Филинова - в Дальневосточном отделении РАН;

M.F. Neuts, A.D. Banik, U.C. Gupta, D.M. Lucantoni - в США; F.A. Machihara - в Японии; и другими учеными. Для реальных телекоммуникационных сетей наиболее характерны дважды стохастические потоки, интенсивность которых является кусочно-постоянным случайным процессом (MC-потоки). В большинстве случаев в работах рассматривались потоки с двумя состояниями интенсивности (состояниями потока). Однако, реальные информационные потоки могут аппроксимироваться дважды стохастическими потоками с числом состояний, большим двух, поэтому имеет большое значение исследование дважды стохастических потоков с произвольным числом состояний.

На практике параметры, определяющие поток событий, как правило, известны только частично, либо вообще неизвестны. Состояние дважды стохастического потока, как правило, принципиально не наблюдаемо. Функционирование системы массового обслуживания непосредственно зависит от параметров входящего потока и его состояний, поэтому возникают два класса задач:

1) оценивание состояния дважды стохастического потока по наблюдениям за моментами наступления его событий; 2) оценивание параметров дважды стохастического потока по наблюдениям за моментами наступления его событий.

При наблюдении за реальными потоками событий часть моментов наступления событий может теряться для наблюдателя. Одна из причин - так называемое мертвое время прибора, регистрирующего события. Каждое зарегистрированное событие порождает промежуток ненаблюдаемости потока, в течение которого события потока не фиксируются (мертвое время). Можно считать, что мертвое время имеет фиксированную длительность и не продлевается (промежуток ненаблюдаемости не увеличивается) при наступлении событий в течение мертвого времени.

Целью работы является аналитическое исследование асинхронного дважды стохастического потока событий с произвольным конечным числом состояний в условиях полной наблюдаемости и при наличии фиксированного непродлевающегося мертвого времени для получения оптимальных оценок состояний и параметров потока; формулировка алгоритмов для оценивания состояний и параметров потока в режиме реального времени; разработка программной реализации алгоритмов оценивания и проведение статистических экспериментов с целью установления качества получаемых оценок состояний и параметров потока.

В рамках указанной цели были поставлены и решены следующие задачи:

1. Нахождение аналитического решения задачи оптимальной оценки состояний асинхронного потока с произвольным конечным числом состояний по наблюдениям за моментами наступления событий потока.

2. Нахождение аналитического решения задачи оптимальной оценки параметров асинхронного потока с произвольным конечным числом состояний по наблюдениям за моментами наступления событий потока.

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

4. Создание алгоритмов оптимальной оценки состояний и параметров асинхронного потока с произвольным конечным числом состояний в условиях полной наблюдаемости моментов наступления событий потока.

5. Создание алгоритма оптимальной оценки состояний асинхронного потока с произвольным конечным числом состояний при наличии фиксированного непродлевающегося мертвого времени.

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

Научная новизна результатов проведенных исследований.

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

Положения, выносимые на защиту:

1. Аналитическое решение задачи оптимальной оценки состояний асинхронного потока с произвольным конечным числом состояний по наблюдениям за моментами наступления событий потока.

2. Аналитическое решение задачи оптимальной оценки параметров асинхронного потока с произвольным конечным числом состояний по наблюдениям за моментами наступления событий потока.

3. Аналитическое решение задачи оптимальной оценки состояний асинхронного потока с произвольным конечным числом состояний по наблюдениям за моментами наступления событий потока при наличии фиксированного непродлевающегося мертвого времени.

4. Алгоритмы оптимальной оценки состояний и параметров асинхронного потока с произвольным конечным числом состояний в условиях полной наблюдаемости моментов наступления событий потока.

5. Алгоритм оптимальной оценки состояний асинхронного потока с произвольным конечным числом состояний при наличии фиксированного непродлевающегося мертвого времени.

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

Методы исследования. Для проведения исследований применялся аппарат теории вероятностей, теории массового обслуживания, теории дифференциальных уравнений, математического анализа, математической статистики и численные методы. Проведение статистических экспериментов по оценке состояний и параметров потока выполнено на основе созданной имитационной модели асинхронного дважды стохастического потока событий с произвольным конечным числом состояний.

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

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

Достоверность и обоснованность всех полученных в диссертации результатов подтверждается строгим математическим исследованием с использованием аппарата теории вероятностей, теории массового обслуживания, теории дифференциальных уравнений, математического анализа, математической статистики, численных методов.

ичное участие автора в получении результатов, изложенных в диссертации. Основные научные результаты, выносимые на защиту и составляющие основное содержание диссертационной работы, получены автором самостоятельно. Постановка изложенных в диссертации задач была сделана совместно с научным руководителем автора, д.т.н., проф. А.М. Горцевым. В совместных публикациях научному руководителю А.М. Горцеву принадлежат постановки задач и указания основных направлений исследований, а основные результаты, выкладки и численные расчеты выполнены автором. Численные расчеты выполнялись автором самостоятельно, программа имитационного моделирования выполнена автором единолично.

Апробация работы. Основные результаты диссертационного исследования докладывались и обсуждались на следующих научных конференциях:

1. XLVII Международная научная конференция Студент и научнотехнический прогресс, г. Новосибирск, апрель 2009 г.

2. Международная конференция Теория вероятностей, математическая статистика и их приложения, посвященная 75-летию профессора, доктора физико-математических наук Г.А. Медведева, г. Минск, февраль 2010 г.

3. VI Всероссийская открытая научно-практическая конференция Актуальные задачи математического моделирования и информационных технологий, г. Сочи, май 2010 г.

4. IV Международная научно-техническая конференция молодых специалистов, аспирантов и студентов Математическое и компьютерное моделирование естественнонаучных и социальных проблем, г. Пенза, май 2010 г.

5. Восьмая Российская конференция с международным участием Новые информационные технологии в исследовании сложных структур, г. Томск, октябрь 2010 г.

6. Международная научная конференция Современные вероятностные методы анализа и оптимизации информационно-телекоммуникационных сетей, г. Минск, январь-февраль 2011 г.

7. 50-я Международная научная конференция Студент и научнотехнический прогресс, г. Новосибирск, апрель 2012 г.

Публикации. По результатам проведенных исследований автором опубликовано 10 печатных работ, в том числе три статьи, все три статьи в издании, рекомендованном ВАК.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения, списка литературы, трех приложений. Общий объем работы составляет 114 страниц. Работа содержит 91 страницу основного текста, в том числе 19 рисунков и 10 таблиц. Список литературы включает 114 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, приведен обзор работ других авторов, сформулирована цель и задачи диссертационного исследования, изложена его научная новизна, обоснованы теоретическое значение и практическая ценность полученных результатов.

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

Рассматривается асинхронный дважды стохастический поток событий с n состояниями (далее асинхронный поток либо просто поток). Интенсивность потока является кусочно-постоянным случайным процессом (t) с n состояниями: 1, 2, Е, n (1 > 2 > Е > n > 0). Будем говорить, что процесс (поток) находится в i-м состоянии, если (t) = i (i = 1, n ). В течение времени пребывания в i-м состоянии поток ведет себя как пуассоновский с интенсивностью (t) = i (i = 1, n ). Переходы процесса (t) (потока) из состояния в состояние характериn зуются матрицей интенсивностей переходов между состояниями ij 1, где ij > 0 (i, j = 1,n, i j ) - интенсивность перехода из состояния i в состояние j.

Пусть здесь и далее t - достаточно малая величина, тогда элементы матрицы интенсивностей переходов определяются следующим образом:

P((t + t) = | (t) = i ) j ij = lim (i, j =1,n, i j ), где P((t + t) = | (t) = i) j tt - вероятность того, что в момент времени t + t процесс (t) находится в j-м состоянии при условии, что в момент времени t он находился в i-м состоянии;

P((t + t) = i | (t) = i ) -ii = lim (i =1,n), где P((t + t) = i | (t) = i) - tt вероятность того, что в момент времени t + t процесс (t) находится в i-м состоянии при условии, что в момент времени t он находился в этом же состоянии. Очевидно, для интенсивностей переходов справедливо равенство n ii = (i =1,n). Длительность пребывания процесса (t) (потока) в i-м соij j=1, ji стоянии является экспоненциально распределенной случайной величиной с ii функцией распределения Fi() = 1- e. Процесс (t) является принципиально ненаблюдаемым, то есть состояние потока в любой момент времени является неизвестным. Наблюдению доступны только временные моменты наступления событий потока.

Рассматривается стационарный режим функционирования потока, поэтому переходными процессами на интервале наблюдения (t0,t ), где t0 - начало наблюдений, t - окончание наблюдений, пренебрегаем.

Поскольку процесс (t) является принципиально ненаблюдаемым, то говорить о состоянии потока можно только в вероятностном смысле. Иными словами, состояние потока в любой момент времени t является случайной величиной, которую можно оценить, основываясь на информации о потоке, доступной к моменту времени t. Вся доступная информация о потоке - это моменты наступления собы тий с начала наблюдения за потоком до момента t. Обозначим (t) - оценка состояния потока в момент времени t. Обозначим (i | t1,t2,Е,tm) (i =1,n) - апостериорная вероятность того, что (t) = i (в момент времени t поток находится в i-м состоянии) при условии, что за время наблюдения за потоком наступило n m событий в моменты t1,t2,...,tm. При этом (i | t1, t2,..., tm) = 1. Оценку со i= стояния потока (t) предлагается получать согласно критерию максимума апостериорной вероятности, который обеспечивает минимум полной (безусловной) вероятности ошибки. Согласно данному критерию (t) =i, где i удовлетворяет следующему условию: (i | t1,t2,...,tm) ( | t1,t2,...,tm) ( j =1,n ).

j Основные аналитические результаты, полученные для случайного процесса (t) и апостериорных вероятностей, сформулированы в следующих леммах и теоремах.

емма 1.2.1. Процесс (t) является транзитивным марковским.

Для формулировки следующих лемм введем следующие обозначения.

Пусть наблюдения за потоком начинаются в момент времени t = 0, и время t изменяется дискретно с конечным шагом t : t = kt ( k = 0,1,...). Рассмотрим двумерный случайный процесс ((k), rk), где (k) = (kt) - значение процесса (t) в момент времени kt ((k) = i, i = 1, n, k = 0,1,Е); rk - число событий, наблюденных на интервале времени ((k - 1)t, kt), (rk = 0,1,Е, k = 0,1,Е). Так как на интервале (Цt, 0) наблюдений не проводится, то r0 можем положить произr вольным, например положим r0 = 0. Обозначим (m) = ((0),(1),...,(m)) - последовательность ненаблюдаемых значений процесса (t) в моменты времени r kt ( k = 0,m). Обозначим rm = (r0, r1,..., rm) - последовательность значений количества наблюденных событий на интервалах ((k - 1)t, kt) ( k = 0, m ).

r Обозначим ((m+1) | rm+1) - апостериорная вероятность того, что в момент времени (m + 1)t имеет место ((m + 1)t) = (m+1) ((m+1) = i,i = 1, n) при условии, что на полуинтервалах времени [(k - 1)t, kt) (k = 0,m +1) наблюдалось rk r событий потока соответственно; ((m) | rm) - апостериорная вероятность того, что (mt) = (m) ((m) = i,i = 1, n) при условии, что на полуинтервалах времени [(k - 1)t, kt) ( k = 0, m ) наблюдалось rk событий потока соответственно.

емма 1.2.2. Случайный процесс ((k), rk) является марковским.

В следующей лемме получена рекуррентная формула для апостериорной вероятности.

r Лемма 1.2.3. Апостериорная вероятность ((m+1) | rm+1) определяется рекуррентной формулой:

n r ((m) | rm) p((m+1), rm+1 | (m), rm) r (m) =((m+1) | rm+1) = n n r ((m) | rm) p((m+1), rm+1 | (m), rm) (m+1) =1 (m) =От дискретного времени перейдем теперь к непрерывному времени, устремив величину t к нулю. Поведение апостериорных вероятностей на временной оси определяется следующими леммами 1.2.4 - 1.2.6 и теоремой 1.2.1.

емма 1.2.4. В течение времени между моментами наступления соседних событий асинхронного потока апостериорные вероятности состояний потока (j | t) ( j = 1, n ) удовлетворяют системе дифференциальных уравнений:

n n d( | t) j = ( - ij )(i | t) + ( | t) (i | t), ij j j i dt (1) i=1 i=tk < t < tk +1, i, j = 1, n, k = 0,1,..., где ij - символ Кронекера.

В лемме 1.2.5. получена формула для пересчета апостериорных вероятностей состояний потока в моменты времени наступления событий.

емма 1.2.5. Апостериорные вероятности состояний асинхронного потока (j | t) ( j =1,n ) в момент наступления события потока определяются формулой пересчета:

( | tk - 0) j j ( | tk + 0) = ( j = 1,n, k = 1,2,...).

j n (2) i(i | tk - 0) i=Рассмотрим (j | t0) ( j =1,n ) - апостериорные вероятности состояния потока в момент начала наблюдений за потоком t0. (j | t0) ( j =1,n ) являются начальными условиями для решения системы (1) на полуинтервале [t0, t1), то есть на интервале времени от момента начала наблюдений за потоком до момента наступления первого события потока. Поскольку поток рассматривается в стационарном режиме, можно в качестве (j | t0) ( j =1,n ) выбрать априорные финальные вероятности состояний процесса (t).

емма 1.2.6. Априорные финальные вероятности j ( j = 1,n ) состояний процесса (t) удовлетворяют системе линейных алгебраических уравнений n n iij = 0 ( j = 1,n ), = 1, (3) j i=1 j=где ij (i, j = 1, n ) - элементы матрицы интенсивностей переходов.

еммы 1.2.4 - 1.2.6 позволяют сформулировать теорему 1.2.1.

Теорема 1.2.1. Поведение апостериорных вероятностей (j | t) ( j = 1,n ) на временной оси определяется системой дифференциальных уравнений (1), формулами пересчета вероятностей (2) и решением системы (3), содержащей n уравнений; где tk t < tk+1, вероятности (j | tk) = (j | tk + 0), (j | tk+1) = (j | tk+1 - 0) ( k = 0,1,...); для k = 0 имеет место равенство (j | t0) = (j | t0 + 0) = j ( j = 1, n ).

Теорема 1.2.1 определяет, в частности, поведение апостериорных вероятностей на полуинтервале [tk, tk+1), т.е. между моментами наступления соседних событий, причем на правом конце полуинтервала имеет место значение (j | tk+1) = (j | tk+1 - 0), на основе которого по формулам (2) находится апостериорная вероятность (j | tk+1 + 0) ( j = 1,n ), являющаяся начальной для следующего полуинтервала времени [tk+1, tk+2). Таким образом, апостериорные вероятности (j | t) в моменты наступления событий t1,t2,Е претерпевают разрывы первого рода.

Получим апостериорные вероятности (j | t) в явном виде. Для этого необходимо решить систему (1), которая является системой нелинейных дифференциальных уравнений. Ее удается решить с помощью ряда замен и введения дополнительных обозначений.

n Введем матрицу D = dil 1, dil = li (i l), dll = ll - l (i, l = 1, n ). Обозначим n 1, 2, Е, n - собственные числа матрицы D. Введем матрицу S = sil 1, составленную из собственных векторов матрицы D таким образом, что l-й столбец S является собственным вектором, соответствующим собственному числу -1 l (l = 1, n ). Элементы матрицы S обозначим sli1. Введем матрицу n = l il 1 (il - символ Кронекера). На главной диагонали расположены собственные числа матрицы D, прочие элементы - нулевые.

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

Теорема 1.3.1. Апостериорные вероятности состояний асинхронного потока (j | t) ( j = 1,n ) на полуинтервале времени [tk, tk+1) (k = 0,1,Е) определяются следующей формулой:

n (t-tk ) s zl (tk )el jl l=( | t) =, tk t < tk +1, j = 1, n, k = 0,1,..., (4) j n n (t-tk ) s zl (tk )el il i=1l=n n где ( | tk ) = ( | tk + 0) = s zl (tk ), zl (tk ) = sli-1(i | tk + 0).

j j jl l=1 i=В разделе 1.4 диссертации рассмотрен случай асинхронного потока с двумя состояниями.

Полученные формулы (2), (3), (4) позволяют создать алгоритм расчета апостериорных вероятностей (j | t), j = 1, n, для любого момента времени t. Алгоритм приведен в диссертации. Согласно алгоритму, параллельно вычислению апостериорных вероятностей (j | t), j = 1, n, в любой момент времени t по критерию максимума апостериорной вероятности выносится оптимальное решение о состоянии асинхронного потока: если (j | t) (i | t), i, j = 1,n, i j, $ то оценка (t) = .

j В разделе 1.6 диссертации решается задача оценки состояний потока при наличии мертвого времени.

После каждого зарегистрированного в момент времени tk события наступает время фиксированной длительности Т (мертвое время), в течение которого другие события исходного асинхронного потока недоступны наблюдению. События, наступившие в течение мертвого времени, не вызывают продления его периода (непродлевающееся мертвое время). По окончании мертвого времени первое наступившее событие снова создает период мертвого времени длительности Т и т.д. При этом, очевидно, необходимо разделять исходный (истинный) асинхронный поток, и наблюдаемый асинхронный поток, в котором часть событий исходного потока отсутствует. Так как первое наступившее после окончания периода мертвого времени событие асинхронного потока снова порождает период мертвого времени фиксированной длительности Т, в течение которого последующие события асинхронного потока недоступны наблюдению (поток отсутствует), то условия нахождения апостериорных вероятностей (j | t) ( j = 1, n ) на полуинтервале времени (tk, tk + Т] и на интервале времени (tk + Т, tk+1) принципиально разные. В настоящей работе предполагается, что значение длительности мертвого времени Т известно точно.

n-Обозначим a = a (aji = ij - nj); 1,Е, n - 1 - собственные числа матji n-рицы а; A = Aji 1 - матрица, составленная из собственных векторов матрицы а так, что i-й столбец матрицы А соответствует собственному числу i (i =1,n -1). Обозначим det a - определитель матрицы a; det aj - определитель, полученный из det a заменой j-го столбца столбцом (n1, n2,Е, n n-1)T.

На отрезке мертвого времени [tk, tk + Т] (k = 1, 2, Е) поведение апостериорных вероятностей (j | t) определяется выражениями:

n-det a j | t) = + Ajizi(tk )eit ( j =1,n -1), ( j det a i=n-n | t) =1- | t), ( ( (5) j j=где tk t tk + T, k = 1, 2, Е ; значения констант zi (tk) (i =1,n -1) находятся как решение системы линейных неоднородных алгебраических уравнений:

n-det a j Ajizi(tk )eitk =( | tk + 0) - ( j =1,n -1, k = 1, 2, Е).

j det a i=Полученные выражения (2), (3), (4), (5) определяют поведение апостериорных вероятностей на всей временной оси, в том числе на отрезках мертвого времени, и позволяют создать алгоритм расчета апостериорных вероятностей (j | t), j = 1, n, для любого момента времени t. Алгоритм приведен в диссертации. Согласно алгоритму, параллельно вычислению апостериорных вероятностей (j | t), j = 1, n, в любой момент времени t по критерию максимума апостериорной вероятности выносится оптимальное решение о состоянии асин$ хронного потока: если (j | t) (i | t), i, j = 1, n, i j, то оценка (t) = .

j Во второй главе решается задача оптимальной оценки параметров асинхронного дважды стохастического потока событий с произвольным числом состояний.

Значения параметров потока i, ij (i, j = 1, n, i j) неизвестны. Интенсивность потока (t) является принципиально ненаблюдаемым случайным процессом. Предполагается, что о потоке известно только число состояний n и наблюдению доступны все моменты наступления событий потока t1, t2, Е. Необходимо по наблюдениям t1, t2, Е оценить параметры потока i, ij (i, j = 1, n, i j) в момент окончания наблюдения за потоком.

r Обозначим = (1,...,n,ij;i, j =1,n,i j) - вектор неизвестных параметr $ ров потока, (t) - вектор соответствующих оценок параметров в момент вре$ мени t. k и (t) - k-е компоненты вектора параметров и вектора оценок соотk r r $ ветственно. Обозначим N - размерность векторов и (t), N = n2. Обозначим r r p( | t) = p( | t1, t2, Е, tm, t) - апостериорная плотность распределения вероятноr стей вектора параметров в момент времени t при условии, что в моменты времени t1, t2, Е, tm (0 < t1 < t2 < Е < tm < t) наблюдались события потока. Обозначим = {1 > 2 > Е > n > 0, ij > 0; i, j = 1, n, i j} - область значений векr r $ тора параметров . В диссертации предлагается использовать оценку (t), оптимальную в смысле минимума среднеквадратического отклонения от истинноr го значения вектора :

r r $ (t) = k p( | t)d ( k = 1, N ), k r где d = d1d2 Е dN, или в векторной форме rr r r $ (t) = p( | t)d.

(6) Выражение (6) дает оптимальную оценку параметров потока в виде апостериорного среднего. Для того, чтобы воспользоваться формулой (6), необхоr димо найти выражение для апостериорной плотности p( | t).

Пусть наблюдения за потоком начинаются в момент t0 = 0, и время t изменяется дискретно с конечным шагом t: t = kt (k = 0,1,Е). Обозначим r(kt) - число событий, наблюденных на полуинтервале времени [(k - 1)t, kt) (r(kt) = 0,1,Е, k = 0,1,Е). На полуинтервале [Цt, 0) наблюдений не производится, поэтому r(0) можно положить произвольным, например, положим r(0) = 0. Обоr значим r(mt) = (r(0),r(t),...,r(mt)) - последовательность значений количества наблюденных на временных полуинтервалах [(k - 1)t, kt) ( k = 0,m) событий. Рассмотрим момент времени t такой, что t = mt, а t + t = (m + 1)t.

r r Тогда имеем r(mt) = r(t), r((m + 1)t) = r(t + t), r (mt) = r (t), r r r ((m +1)t) = r (t + t).

r r r r r Обозначим p( | r (mt) ) = p( | r (t) ) = p( | t) - апостериорная плотность r вероятностей вектора параметров потока в момент времени t при условии, что на временных полуинтервалах [(k - 1)t, kt) ( k = 0,m) наблюдалось r(kt) r событий потока соответственно. Обозначим p( r| t + t) - апостериорная плотность вероятностей в момент времени t + t, p( | t) - апостериорная плотность в момент времени t. Теорема 2.2.1 определяет связь апостериорных плотностей r r вероятностей p( | t) и p( | t + t).

r Теорема 2.2.1. Апостериорная плотность p( | t + t) определяется следующей рекуррентной формулой:

От дискретного времени перейдем к непрерывному времени, устремив веn r личину t к нулю. Введем обозначение s(t,) = ( | t). Поведение апо j j j=стериорных вероятностей на временной оси определяется леммами 2.2.1, 2.2.2 и теоремой 2.2.2.

r Лемма 2.2.1. Апостериорная плотность p( | t) между моментами наступления событий удовлетворяет интегро-дифференциальному уравнению r rr r r r dp( | t) =- p( | t)s(t,) - s(t,) p( | t)d (tk < t < tk+1, k = 0, 1, Е).

(8) dt r Лемма 2.2.2. Апостериорная плотность p( | t) в момент tk наблюдения события потока пересчитывается по формуле r r r p( | tk - 0)s(tk - 0,) r r r p( | tk + 0) = (k = 1, 2, Е).

(9) p( | tk - 0)s(tk - 0,)d r Теорема 2.2.2. Поведение апостериорной плотности p( | t) на временной оси определяется интегро-дифференциальным уравнением (8) и формулой переr r счета вероятностей (9), в которых tk t < tk+1, p( | tk) = p( | tk + 0) (k = 0,1,Е).

В момент времени t0 начала наблюдений за потоком апостериорная плотr ность p( | t0) задается, исходя из априорных данных о параметрах асинхронноr го потока. Если таких данных нет, можно задать плотность p( | t0) как произведение N плотностей равномерно распределенных случайных величин, каждая из которых распределена в некотором интервале допустимых значений для соответствующего параметра потока.

Следующая теорема 2.2.3 определяет явный вид апостериорной плотности вероятностей в моменты времени между наступления событий потока.

r Теорема r2.2.3. Апостериорная плотность вероятностей p( | t) вектора параметров на полуинтервале времени [tk, tk+1) (k = 0, 1, Е) определяется формулой:

r $ При расчете оценок параметров (t) по формулам (6), (9), (10) возникают существенные сложности при реализации алгоритма расчета на ЭВМ. Вопервых, интегрирование в указанных формулах ведется по N-мерной области , которая в общем случае может быть не ограничена. Во-вторых, формулы содержат N-кратные интегралы. Поэтому в диссертации предлагается приблиr $ женный (упрощенный) алгоритм расчета оценок (t), который не содержит указанных сложностей. Идея приближенного алгоритма опирается на предпоr $ ложение о достаточной близости значений вектора оценок (t) к истинному r значению вектора параметров . Данное предположение позволяет воспользоваться разложениями в ряд Тейлора и значительно упростить формулы для вычислений. Приближенный алгоритм оценки параметров приведен в диссертации.

В третьей главе приведены результаты статистических экспериментов по нахождению оптимальных оценок параметров и состояний асинхронного потока с использованием алгоритмов оценки, полученных в главах 1 и 2. Сложность полученных в главах 1 и 2 аналитических формул оценок состояний и параметров потока не позволяет провести аналитическое исследование качества оценок. Статистические эксперименты проведены на ЭВМ с помощью имитационной модели асинхронного потока.

Статистические эксперименты по оценке состояний потока заключаются в вычислении выборочного среднего безусловной вероятности принятия ошибочного решения и выборочной дисперсии. Результаты численных экспериментов приведены в таблицах и на графиках. Здесь в качестве примера приведены результаты экспериментов для следующих параметров потока: число состояний потока n = 3; время моделирования Tm = 500 ед. времени; интервал дискретизации времени t = 0,01; размер выборки (число имитаций потока) N = 100; первая строка матрицы интенсивностей переходов случайного процесса (t) из состояния в состояние ij 1 есть (1) = ( - 0,03; 0,02; 0,01), вторая строка - (2) = (0,025; - 0,04; 0,015), третья строка матрицы - (3) = (0,02; 0,04; - 0,06).

Первый эксперимент (таблица 1) проводился для параметров 1 = 4; 2 = 2,5;

3 = 1 (при этом 2 = (1 + 3)/2). В каждом из последующих экспериментов (таблицы 2 и 3) интервал между значениями интенсивностей (1, 3) увеличивался по сравнению с предыдущим экспериментом, значение 2 всякий раз выбиралось как середина интервала (1, 3), т.е. в каждом эксперименте 2 = (1 + 3)/2. В первой строке каждой таблицы указаны значения мертвого времени T, при которых проводилось моделирование асинхронного потока событий (T = 0; 0,2; 0,4; 0,6; 0,8; 1 ед. времени). Во второй и третьей строках таблиц для каждого значения мертвого времени T приведены численные значения выборочного среднего безусловной вероятности ошибочного решения P0 и вы борочной дисперсии D соответственно.

Таблица Результаты эксперимента (1 = 4; 2 = 2,5; 3 = 1) T 0 0,2 0,4 0,6 0,8 P0 0,20200 0,23500 0,27800 0,29900 0,32100 0,325 0,00258 0,00233 0,00279 0,00377 0,00378 0,003D Таблица Результаты эксперимента (1 = 6,76; 2 = 3,625; 3 = 0,49) T 0 0,2 0,4 0,6 0,8 P0 0,10200 0,15100 0,17900 0,19900 0,21900 0,232 0,00047 0,00121 0,00161 0,00224 0,00227 0,002D Таблица Результаты эксперимента (1 = 11,424; 2 = 5,832; 3 = 0,24) T 0 0,2 0,4 0,6 0,8 P0 0,06300 0,1100 0,14300 0,16600 0,18400 0,202 0,00028 0,00091 0,00159 0,00138 0,00185 0,002D Анализ приведенных и других многочисленных экспериментов по оценке состояний потока показывает, что, во-первых, при росте значения мертвого времени Т качество оценки состояния ухудшается ( P0 и D растут); во-вторых, при фиксированном значении мертвого времени Т с увеличением величины интервала (1, 3) качество оценки состояния улучшается, т.к. чем сильнее интенсивности отличаются друг от друга, тем сильнее различается поведение потока при разных значениях интенсивностей, и отследить изменение состояния ста новится проще; в-третьих, величина оценки P0 полной вероятности принятия ошибочного решения и выборочная дисперсия оценки D достаточно малы;

в-четвертых, оценка безусловной вероятности ошибочного решения P0 уменьшается при увеличении времени моделирования Tm и является достаточно стабильной для времени моделирования Tm 200 ед. времени.

Ниже в качестве иллюстрации приведены результаты статистического эксперимента по расчету оценок параметров асинхронного потока для следующих истинных значений параметров: n = 2 (поток имеет два состояния); 1 = 0,5;

2 = 0,05; первая строка матрицы интенсивностей переходов процесса (t) из состояния в состояние ij 1 есть (1) = ( - 0,08; 0,08), вторая строка матрицы - (2) = (0,04; - 0,04). Начальная плотность распределения параметров выбрана равномерной: параметр 1 равномерно распределен в интервале [0,337;0,836], параметр 2 - в интервале [0,021;0,073], параметр 1 = 12 - в интервале [0,04;0,091], параметр 2 = 21 - в интервале [0,031;0,048]; N = 4 (число параметров потока). Время моделирования Tm изменяется от 0 до 100 ед. времени. В качестве показателя близости оценки параметра k (t) ( k =1, N ) к истинному значению параметра k выбрана величина (k,t) ( k =1, N ):

(k,t) =| k (t) - k | / mx(k (t),k ); в качестве общей характеристики точности N оценивания параметров потока выбрана величина (t) = (,t). На рис. N k k=представлен график оценки параметра 1 в зависимости от времени; на рис. представлен график величины (t).

(t) T m Рис. 1. Траектория оценки параметра (t) (t) Tm Рис. 2. Траектория общего показателя качества оценок (t) В приведенном эксперименте общий показатель качества оценок параметров потока (t) изменяется в диапазоне от 0,09475 до 0,14913, уменьшаясь с течением времени, что говорит о достаточном качестве получаемых оценок. В целом, анализ приведенного здесь, а также многочисленных других экспериментов, показывает, что оценки параметров потока имеют достаточно хорошую стабильность.

В заключении диссертации приведены основные результаты, которые изложены в пунктах научной новизны, теоретической значимости и практической ценности.

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

2. Горцев А.М. Оптимальная оценка состояний асинхронного потока событий с конечным числом состояний в условиях непродлевающегося мертвого времени. / А.М. Горцев, В.Л. Зуевич // Вестник Томского государственного университета. Управление, вычислительная техника и информатика. - 2010. - № 3 (12). - С. 41 - 53.

3. Горцев А.М. Оптимальная оценка параметров асинхронного дважды стохастического потока событий с произвольным числом состояний.

/ А.М. Горцев, В.Л. Зуевич // Вестник Томского государственного университета. Управление, вычислительная техника и информатика.

- 2011. - № 4 (17). - С. 25 - 40.

4. Зуевич В.Л. Оптимальная оценка состояний асинхронного дважды стохастического потока событий / В.Л. Зуевич // Студент и научнотехнический прогресс : Математика : материалы XLVII Международной научной студенческой конференции / Новосиб. гос. ун-т. - Новосибирск, 2009. - С. 164 - 165.

5. Горцев А.М. Оптимальная оценка состояний асинхронного потока событий с конечным числом состояний. / А.М. Горцев, В.Л. Зуевич // Теория вероятностей, математическая статистика и их приложения : материалы Международной конференции. - Минск : Изд-во РИВШ, 2010. - С. 60 - 67.

6. Зуевич В.Л. Вынесение оптимального решения о состоянии асинхронного потока событий с конечным числом состояний при наличии интервалов ненаблюдаемости потока / В.Л. Зуевич // Актуальные задачи математического моделирования и информационных технологий : материалы VI Всероссийской открытой научно-практической конференции, Сочи, 22 - 27 мая 2010 г. / СГУТиКД. - Сочи, 2010. - С. 65 - 67.

7. Зуевич В.Л. Оценивание интенсивности асинхронного потока событий при наличии мертвого времени / В.Л. Зуевич // Математическое и компьютерное моделирование естественнонаучных и социальных проблем :

сборник статей IV Международной научно-технической конференции молодых специалистов, аспирантов и студентов. - Пенза : Приволжский Дом знаний, 2010. - С. 90 - 92.

8. Зуевич В.Л. Оптимальная оценка состояний асинхронного потока событий с конечным числом состояний при его неполной наблюдаемости / В.Л. Зуевич // Новые информационные технологии в исследовании сложных структур : тезисы докладов Восьмой Российской конференции с международным участием. - Томск : Изд-во НТЛ, 2010. - С. 32.

9. Горцев А.М. Алгоритм оценки параметров асинхронного потока событий с конечным числом состояний / А.М. Горцев, В.Л. Зуевич // Современные вероятностные методы анализа и оптимизации информационнотелекоммуникационных сетей : материалы международной научной конференции, Минск, 31 января - 3 февраля 2011 г. - Минск : Изд-во РИВШ, 2011. - С. 88 - 95.

10. Зуевич В.Л. Приближенные формулы для оценки параметров асинхронного потока событий / В.Л. Зуевич // Студент и научно-технический прогресс : Математика : материалы Юбилейной 50-й Международной научной студенческой конференции / Новосиб. гос. ун-т. - Новосибирск, 2012.

- С. 151.

Подписано в печать 16.05.2012 г.

Формат А4/2. Ризография Печ. л. 0,9. Тираж 130 экз. Заказ № 07/05-Отпечатано в ООО Позитив-НБ 634050 г. Томск, пр. Ленина 34а Авторефераты по всем темам >> Авторефераты по техническим специальностям

Blog

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