Содержание к диссертации
Введение
Глава 1. Оптимальная оценка состояний альтернирующего потока с инициированием лишних событий 16
1.1. Постановка задачи 17
1.2. Плотность вероятностей длительности интервала между соседними событиями 19
1.2.1. Плотность вероятностей р(т) для первого типа потока 22
1.2.2. Плотность вероятностей р(т) для второго типа потока 25
1.2.3. Плотность вероятностей р(т) для третьего типа потока 28
1.3. Апостериорные вероятности состояний 31
1.3.1. Апостериорные вероятности состояний для первого типа потока . 34
1.3.2. Апостериорные вероятности состояний для второго типа потока . 39
1.3.3. Апостериорные вероятности состояний для третьего типа потока . 43
1.4. Алгоритм оптимального оценивания состояний потока 46
1.5. Вероятность ошибочного вынесения решения о состоянии потока 47
1.5.1. Вероятность ошибки для потока первого типа 50
1.5.2. Вероятность ошибки для потока второго типа 54
1.5.3. Вероятность ошибки для потока третьего типа 60
1.6. Результаты и выводы к первой главе 62
Глава 2. Оценка параметров альтернирующего потока с непродлевающимся мертвым временем 64
2.1. Постановка задачи 65
2.2. Построение плотности вероятностей длительности интервала между соседними событиями в потоке с непродлевающимся мертвым временем 67
2.2.1. Построение плотности вероятностей длительности интервала между соседними событиями для потока первого типа 69
2.2.2. Построение плотности вероятностей длительности интервала между соседними событиями для потока второго типа 72
2.2.3. Построение плотности вероятностей длительности интервала между соседними событиями для потока третьего типа 78
2.3. Выражения для совместной плотности вероятностей длительностей смежных интервалов между событиями 83
2.4. Оценивание длительности мертвого времени методом максимального правдоподобия 87
2.5. Оценивание параметров потока и длительности мертвого времени методом моментов 90
2.5.1. Оценка параметров для первого и второго типа потоков 90
2.5.2. Оценка параметров для потока третьего типа 96
2.6. Результаты и выводы ко второй главе 99
Глава 3. Оценка параметров альтернирующего потока с продлевающимся мертвым временем 101
3.1. Постановка задачи 101
3.2. Преобразование Лапласа плотности вероятностей длительности интервала между соседними событиями в наблюдаемом потоке 103
3.2.1. Преобразование Лапласа для потока первого типа 104
3.2.2. Преобразование Лапласа для потока второго типа 110
3.2.3. Преобразование Лапласа для потока третьего типа 111
3.3. Оценивание длительности мертвого времени методом моментов 115
3.3.1. Оценивание длительности мертвого времени для потоков первого и второго типов 116
3.3.2. Оценивание длительности мертвого времени для потока третьего типа 117
3.4. Результаты и выводы к третьей главе 119
Глава 4. Численные результаты статистических экспериментов на имитационной модели 120
4.1. Результаты численных расчетов апостериорных вероятностей состояний и оценок состояний 121
4.2. Результаты численного расчета оценок параметров в условиях непродлевающегося мертвого времени 125
4.3. Результаты численного расчета оценки длительности мертвого времени в условиях продлевающегося мертвого времени 130
4.4. Результаты и выводы к четвертой главе 133
Заключение 135
Литература 137
- Плотность вероятностей длительности интервала между соседними событиями
- Построение плотности вероятностей длительности интервала между соседними событиями для потока первого типа
- Преобразование Лапласа для потока первого типа
- Результаты численного расчета оценок параметров в условиях непродлевающегося мертвого времени
Введение к работе
Актуальность работы. Развитие теории массового обслуживания насчитывает почти 100 лет. Первые работы в этой области были опубликованы датским ученым А.К. Эрлангом в 1908-1922 годах. Направленные на решение задач оптимизации обслуживания заявок, поступающих на телефонную станцию, эти работы уже тогда определили основную область применения новой теории - обслуживание телетрафика. Математический аппарат, примененный Эрлангом - теория вероятностей и математическая статистика, математическое моделирование, теория случайных процесов - до сих пор является основным инструментарием теории массового обслуживания (ТМО). Уже в первой половине XX века обнаружилось, что задачи, подобные тем, что были рассмотрены Эрлангом, возникают во многих других областях науки и техники: в системах связи, транспортных системах, системах управления запасами, в управлении производственными процессами и т.д. Первые публикации по ТМО в нашей стране принадлежат, по-видимому, академику М.Ю. Юрьеву [143] и инженерам К.В. Базилевичу и В.А. Говоркову [3]. Указанные работы были изданы в 20-х гг и посвящены решению задач оптимизации телетрафика (трафика в телефонной сети).
Весомый вклад в развитие ТМО внесли такие ученые как В. Феллер, Д. Кенделл, А.Я. Хинчин и др. В частности, один из основных методов теории - метод вложенных цепей Маркова - был разработан А.Я. Хинчиным в начале 30-х гг.
Основы теории массового обслуживания, ее основные методы можно найти в монографиях А.Я. Хинчина [139], Б.В. Гнеденко и И.Н. Коваленко [34], Г.П. Климова [80], Т.Л. Саати [124], А. Кофмана и Р. Крюона [88], Д. Риордана [120], Л. Клейнорка [79]. Входящие потоки событий в системах массового обслуживания (СМО), рассмотренных в тот период времени, аппроксимировались одной из трех моделей: регулярный поток (системы с таким потоком относятся к детерминированным и рассматриваются в теории
оптимизации как системы конвейерного типа), простейший (пуассоновский) поток и эрланговский (поток, полученный из пуассоновского путем разрежения) поток событий. При этом особое внимание уделяется системам с простейшим входящим потоком, тем более что СМО со входящим потоком Эрланга можно моделировать системой со входящим пуассоновским потоком.
Дальнейшее развитие ТМО шло в направлении приоритетных систем. Литературу по приоритетным системам можно найти в [16, 29, 33, 65, 81, 96]. Значительные научные исследования с использованием метода статистического моделирования на ЭВМ были выполнены Г.П. Башариным [6, 7], Б.С. Лифшицем, А.Д. Харкевичем, М.А. Шнепсом и др. [5, 93, 94, 142]. Методы ТМО изложены в [78].
В шестидесятые годы появились первые работы в области так называемых управляемых СМО [17, 18, 26, 30, 44, 121, 122, 153, 171, 179, 180]. Исключительная актуальность оптимизационных задач, приведших к возникновению таких систем, объясняет дальнейшее бурное развитие этой тематики. Достаточно полные обзоры по управляемым СМО можно найти в [44, 98, 123, 134]. Широта области применения управляемых систем и разнообразие задач, которые оказалось возможным решить с их помощью, повлекли более тщательную разработку этого направления. Ставились и решались все более частные задачи. В целом, все исследования в области управляемых систем можно разделить на пять основных направлений: 1) приоритетные системы с динамическими приоритетами [61, 97, 122, 153, 172]; 2) системы с управляемыми длительностями обслуживания [66, 126, 152, 173, 176, 180]; 3) системы с управляемым входящим потоком заявок [74, 82, 169]; 4) системы с формированием очередей [99, 100, 133, 159]; 5) системы с управляемой (динамической) структурой [2, 73, 91, 146, 164, 166, 167, 168, 174, 175].
Несмотря на довольно широкую область применения ТМО, главными потребителями результатов теории являются такие области как автоматизированные системы управления (АСУ) и сети связи, в том числе компьютерные сети. Наиболее сложные модели систем массового обслуживания
создаются и исследуются именно для этих двух областей.
До середины 80-х годов относительная простота систем связи, изолированность разных видов связи друг от друга, низкая пропускная способность каналов, их дороговизна и, следовательно, высокая их загруженность приводили к тому, что для входящих потоков заявок использовались все те же относительно простые модели, что и во времена К.А. Эрлаига - простейший поток и, реже, регулярный и эрланговский потоки. Усложнение структуры информационных систем, интеграция различных систем связи, разнообразие программного и аппаратного обеспечения, протоколов передачи информации приводят к тому, что теория, существовавшая до 80-х гг, во многом становится непригодной для анализа случайных процессов, существующих в современных сетях связи. В то же время, ТМО предлагает надежные, хорошо изученные общие математические методы теории вероятностей для детального анализа таких систем.
Основная литература по системам массового ослуживания посвящена нахождению различных стационарных характеристик системы обслуживания в условиях известных параметров входящих потоков и обслуживающих приборов. В реальных ситуациях часто эти параметры полностью или частично неизвестны. Например, загрузка сетей связи может изменяться как циклически в течение суток (недели, года), так и в зависимости от того, какие компьютерные приложения в данный момент использует сеть. С одной стороны, локальная сеть организации загружена больше днем, чем ночью, с другой стороны, сеть используется по-разному различными пользователями. В частности, можно различить сетевую активность делопроизводителя, который работает с элекронными документами и пользуется сетью только для их отсылки/получения, и системного администратора, на чей компьютер постоянно поступают данные о состоянии компьютеров и сетевых устройств офиса. Трафик первого пользователя представляет собой чередование долгих периодов "молчания" и кратковременных периодов, когда пакеты информации следуют один за другим. Трафик второго пользователя более равномерен. Однако, и в том и в другом случае имеется дело с потоками переменной
интенсивности, причем изменения интенсивности таких потоков, как правило, носят стохастический характер. В литературе подобные входящие потоки событий принято называть дважды стохастическими. Слово "дважды" имеет следующий смысл: в таком типе потоков имеют место два случайных механизма. Во-первых, случайными являются моменты наступления событий в потоке, во-вторых, случайным процессом является интенсивность потока. Впервые дважды стохастические потоки событий, по-видимому, были упомянуты в работе Кингмена [161] в 1964 году.
Такая случайная зависимость интенсивности входящих потоков от времени встречается чаще, чем постоянная интенсивность, поэтому представляет определенный интерес с точки зрения практических приложений. В последние годы появилось значительное количество исследований по данной проблеме. Статистические эксперименты, проведенные рядом исследователей, показали достаточно точную аппроксимацию реальных потоков в информацонных сетях моделями дважды стохастических потоков событий [10, 36, 140]. В работах [92, 157, 160] модели дважды стохастических потоков применены к описанию экономических процессов. В работе [150] - к описанию процесса обучения нейронной сети.
Интенсивность в дважды стохастических потоках является случайным процессом. В зависимости от характера этого процесса выделяют два больших класса таких потоков: 1) потоки, интенсивность которых является непрерывным (диффузионным) процессом; 2) потоки, интенсивность которых является кусочно-постоянным процессом. Модели различных потоков с диффузионной интенсивностью построены в работах [31, 118, 127, 130, 135], исследования СМО с входящим потоком, интенсивность которого есть диффузионный случайный процесс, приведены в [35, 115].
Потоки, интенсивность которых есть кусочно-постоянный процесс, в свою очередь, подразделяются на потоки с конечным числом состояний (с конечным числом значений, которое может принять процесс) и потоки со счетным числом состояний. Смена состояний происходит в случайные моменты времени, а на интервалах постоянства интенсивности поток ведет себя как простейший. Такие
потоки наиболее пригодны для описания реальных потоков в сетях связи и цифровых сетях интегрального обслуживания. Первыми работами, в которых потоки с кусочно-постоянной интенсивностью были использованы для описания функционирования СМО, были работы М. Ньютса [170] и Г.П. Башарина, В.А. Кокотушкина, В.А. Наумова [6, 7]. В [6] введены в рассмотрение так называемые МС (Markov сЬаіп)-потоки, то есть потоки с интенсивностью, управляемой цепью Маркова, в [170] — MVP (Markov versalite processes)-noTOKii, то есть потоки, управляемые марковским процессом. В монографии [70] и статьях [15, 67, 71,162] проведено исследование систем массового обслуживания с входящим ВМАР (Batch Markovian Arrival Process)-потоком событий, то есть потоком с кусочно-постоянной интенсивностью, в котором в момент изменения интенсивности может наступить не одно, а несколько событий (batch-пачка). Очевидно, ВМАР-потоки не являются ординарными.
Проводя наиболее общую классификацию потоков с кусочно-постоянной интенсивностью, выделяют следующие основные типы потоков: 1) синхронные дважды стохастические потоки, то есть потоки, в которых смена интенсивности происходит в моменты времени, являющиеся моментами наступления событий; 2) асинхронные потоки событий, то есть потоки, изменение интенсивности которых происходит в случайные моменты времени, не связанные с моментами наступления событий; 3) полусинхронные потоки событий, то есть потоки, у которых для одних состояний переход происходит в моменты наступления событий, а для других - независимо от моментов наступления событий.
Выделяют три основные задачи, возникающие при исследовании дважды стохастических потоков с кусочно-постоянной интенсивностью и конечным числом состояний: 1) исследование характеристик СМО с дважды стохастическим входящим потоком событий (средние длины очередей, среднее время ожидания обслуживания и т.п.) [8, 12-14, 32, 37-41, 58-60, 68, 69, 83, 85, 95, 111-114, 128, 129, 131, 137, 144, 145, 147, 148, 151, 154-156, 178, 181]; 2) оценка состояния потока в определенный момент времени при известном множестве значений интенсивности, основанная на информации о событиях, наблюденных до данного момента [57, 84, 86, 101, 116, 118, 141, 158, 177];
3) оценка параметров потока по наблюдениям за моментами наступления событий, возможно при неизвестном числе состояний [9, 25, 48-50, 56, 77, 110].
Среди потоков с конечным числом состояний особое значение имеют дважды стохастические потоки с двумя состояниями, в одном из которых имеет место нулевая интенсивность. Такие потоки, синхронные, асинхронные и полусинхронные, могут являться моделями потоков, поступающих в общую сеть с одного источника. Например, источник может отправлять информацию на обслуживающий прибор порциями по мере ее накопления, что сформирует синхронный поток с двумя состояниями от источника (либо информация пересылается с максимальной интенсивностью, либо не пересылается вовсе, при этом начало и конец окон передачи информации совпадают с моментами пересылки первого и последнего пакетов в "порции"). Если же интервалы времени, когда источник может проводить передачу, определяет обслуживающее или иное устройство, исходя из загруженности сети или сервера, то имеем асинхронный поток с двумя состояниями. Если окно передачи открывается обслуживающим или контролирующим прибором, а закрывается источником, или наоборот, то имеем полусинхронный поток с двумя состояниями. В цифровых сетях интегрального обслуживания (Integrated Service Digital Networks - ISDN), в частности, в компьютерных сетях, такими моделями может быть аппроксимирован трафик, исходящий от определенного порта компьютера (браузерный интернет-трафик, трафик почтового сервиса, файловый трафик и т.п.). Для таких моделей были решены задачи оценивания состояний и параметров. Для асинхронного потока с двумя состояниями - в работах [25, 32, 42, 51, 56, 72], для синхронного - в работах [46, 47, 49, 50], для полусинхронного - в работах [47, 48].
Следует отметить, что характеристики потока, исходящего от одного источника, являются важными в свете некоторых практических задач. Например, поток исходящих информационных пакетов по какому-либо виду трафика в компьютерной сети характеризуется набором параметров потока, а значит, оценив эти параметры, можно составить определенный "портрет" источника, который, в свою очередь, может быть использован при
анализе безопасности трафика на предмет выявления аномальной активности (вызванной, например, деятельностью сетевого вируса).
В то же время, не только в научной, но и в учебной и популярной литературе по информационным сетям, например [76, 109, 119, 132], все чаще упоминаются вопросы разработки теоретических положений и необходимость научно обоснованных технических решении, обеспечивающих эффективность и повышение качества администрирования информационных сетей на основе исследования циркулирующих в них потоков.
Наиболее простой случай оценивания параметров и состояний потока подразумевает, что вес события потока доступны наблюдению. На практике это далеко не всегда возможно. В частности, регистрирующий прибор может обладать так называемым мертвым временем, то есть временем, наступающим после регистрирования события, в течение которого другие события потока недоступны наблюдению. Это время может быть фиксированным (постоянным) или переменным (случайным). Кроме того, мертвое время может быть непродлевающимся (события, наступившие в течение мертвого времени, не вызывают продления его периода) и продлевающимся (события, наступившие в течение мертвого времени не регистрируются, но вызывают продление периода ненаблюдаемости на величину мертвого времени). Задачи оценивания параметров дважды стохастических потоков в условиях непродлевающегося мертвого времени фиксированной длительности приведены в работах [24, 42, 43, 48, 49], продлевающегося мертвого времени фиксированной длительности
в работах [25, 56], в условиях мертвого времени случайной длительности
в работе [23]. В работе [57] решается задача оптимального оценивания состояний асинхронного дважды стохастического потока с двумя состояниями при наличии ошибок в измерениях моментов времени.
Таким образом, проведено достаточно большое количество исследований дважды стохастических потоков событий с точки зрения задач определения характеристик СМО, оценивания параметров и состояний потока. В большинстве указанных работ задача оценки параметров решается методом моментов, реже - методом наименьших квадратов или методом максимального
правдоподобия. Методы максимального правдоподобия и наименьших квадратов имеют асимптотическую эффективность, равную единице [89], но, к сожалению, не всегда удается получить эффективно вычислимые оценки этими методами. Оценка, полученная методом моментов, не является эффективной, но на практике часто приводит к сравнительно простым вычислениям. Также часто в литературе [19, 20, 57] решается задача оптимального оценивания состояний дважды стохастического потока событий.
Для проверки полученных алгоритмов оценивания удобно использовать имитационую модель дважды стохастических потоков событий: получение доверительных интервалов для характеристик на основе многократного моделирования работы СМО. Задача создания такой имитационной модели представляется достаточно важной. Например, в работе [125] создан пакет программ, позволяющий моделировать реализации точечных процессов, интенсивность которых является случайным процессом.
Таким образом, развитие телекоммуникационных сетей, информационных технологий, интегрирование различных видов связи, вычислительных систем и сетей породило множество задач по моделированию и анализу обслуживания информационных потоков, циркулирующих в сетях. В частности, такие информационные потоки достаточно адекватно описываются моделями дважды стохастических потоков событий. Анализ литературных источников, приведенный выше, показывает, что имеется большое колличество работ, посвященных исследованию этих моделей. В последние годы появляются работы, посвященные применению таких моделей для решения задач, возникающих на практике. Это и работы, рассматривающие частные случаи двух состояний, и работы, в которых рассматриваются более общие задачи -конечного и счетного числа состояний.
Тем не менее, нельзя сказать, что построенными моделями исчерпываются все потоки с двумя состояниями, аппроксимирующие реальные потоки событий. Протоколы ISDN-сетях таковы, что при определении окна передачи информации сервером (то есть в случае асинхронного потока), в канал могут поступать так называемые лишние события, представляющие собой
пакеты-уведомления на открытие и/или закрытие окна. Такие события названы лишними, поскольку они не являются событиями пуассоновского потока, а вызываются переходом случайного процесса - интенсивности потока - из состояния в состояние. Эти лишние события могут значительно изменить картину потока и исказить результаты оценивания параметров и состояний. Поэтому очевидна необходимость построения и исследования моделей асинхронных дважды стохастических потоков с двумя состояниями и наличием лишних событий при переходе из состояния в состояние.
Необходимо также учесть возможность наличия мертвого времени у регистрирующего прибора, которая может исказить картину наблюдений за потоком. В силу этого, актуальной задачей является аналитическое и численное исследование моделей дважды стохастических потоков событий с инициированием лишних событий при переходе из состояния в состояние с учетом наличия продлевающегося или непродлевающегося мертвого времени. 1 В настоящей диссертационной работе решается задача оценки состояний асинхронного альтернирующего дважды стохастического потока событий с двумя состояниями (далее альтернирующего потока) с инициированием лишних событий при переходе из состояния в состояние (рассмотрено три схемы инициирования), а также задача оценивания параметров альтернирующего потока с инициированием лишних событий и мертвым (продлевающимся, непродлевающимся) временем фиксированой длительности.
Цель работы. Целью данной работы является:
построение математических моделей альтернирующего потока событий с инициированием лишних событий в условиях: а) отсутствия мертвого времени; б) наличия непродлевающегося мертвого времени фиксированной длительности; в) наличия продлевающегося мертвого времени;
построение оценок неизвестных параметров и состояний альтернирующего потока с инициированием лишних событий и разработка соответствующих алгоритмов оценивания;
программная реализация алгоритмов оценивания параметров и состояний альтернирующего потока событий с инициированием лишних событий;
4) проведение статистических экспериментов на основе имитационной модели альтернирующего потока с инициированием лишних событий с целью установления качества получаемых оценок параметров и состояний.
Методы исследований. Для построения моделей потоков и их аналитического исследования применялся аппарат теории вероятностей, теории дифференциальных уравнений, теории марковских процессов. Для построения алгоритмов оценивания параметров и состояний потоков -методы математической статистики, теории массового обслуживания, линейной алгебры, численные методы. Проведение статистических экспериментов с целью определения качества построенных оценок выполнено на основе имитационной модели альтернирующего потока событий с инициированием лишних событий и различными типами мертвого времени.
Научная новизна работы. Результаты, выносимые на защиту. Научная новизна работы состоит в рассмотрении задачи оценивания параметров альтернирующего потока с двумя состояниями и инициированием лишних событий при переходе из состояния в состояние, наблюдение за которым осложнено наличием мертвого времени, а также построении оптимальных оценок состояний такого потока в условиях отсутствия мертвого времени.
Результаты, выносимые на защиту:
математические модели альтернирующих потоков с двумя состояниями и инициированием лишних событий в условиях: а) отсутствия мертвого времени; б) наличия непродлевающегося мертвого времени фиксированной длительности; в) наличия продлевающегося мертвого времени фиксированой длительности;
алгоритмы оценивания параметров альтернирующего потока с двумя состояниями и инициированием лишних событий в случае присутствия мертвого времени (продлевающегося и непродлевающегося), полученные методом максимального правдоподобия и методом моментов;
алгоритмы оптимального оценивания состояний альтернирующего потока с двумя состояниями и инициированием лишних событий при отсутствии мертвого времени;
4) результаты статистического исследования предложенных оценок, полученные с помощью имитационной модели альтернирующего потока с двумя состояниями и инициированием лишних событий.
Теоретическая ценность работы состоит в аналитическом решении задач оценивания параметров альтернирующего потока с инициированием лишних событий, его состояний, а также длительности мертвого времени на основе выборки наблюдений за моментами наступления событий этого потока.
Практическая ценность работы состоит в возможности использования полученных алгоритмов оценивания параметров и состояний альтернирующего потока с инициированием лишних событий в задачах анализа и проектирования систем массового обслуживания, в частности, систем и сетей связи, спутниковых систем передачи данных, информационно-вычислительных сетей, дисциплины обслуживания которых зависят от параметров входящих потоков, а также для обработки результатов физического эксперимента по изучению потоков элементарных частиц, осложненного мертвым временем регистрирующей аппаратуры.
Работа выполнена в рамках научно-исследовательской работы Томского государственного университета "Исследование и разработка моделей высокопроизводительных многопроцессорных систем и методов обеспечения компьютерной безопасности" в период с 2002 по 2006 гг. и научно-исследовательской работы Томского государственного университета "Исследование вероятностных, статистических и логических моделей информационных потоков в технических, экономических системах и компьютерных системах обработки информации" (2006-2008 гг.).
Публикации. Основные результаты настоящей работы приведены в следующих научных публикациях. Всего опубликовано 11 работ:
1. Горцев A.M., Ниссенбаум О.В. Оценивание длительности мертвого времени и параметров асинхронного альтернирующего потока событий с инициированием лишнего события // Вестн. Томск, гос. ун-та. — 2004.—№284.—С. 139-145.
Горцев A.M., Ниссенбаум О.В. Оценивание длительности мертвого времени и параметров асинхронного альтернирующего потока событий при непродлевающемся мертвом времени /J Изв. вузов. Физика. —2005,—№10.—С.35-49.
Ниссенбаум О.В. Нерекуррентность асинхронного альтернирующего дважды стохастического потока событий с инициированием лишних событий при переходе из состояния в состояние II Вестн. Тюм. гос. ун-та. — 2007.— №5 — С.17-21.
Горцев A.M., Ниссенбаум О.В. Оптимальная оценка состояний асинхронного альтернирующего потока с инициированием лишних событий І/ Вестн. Тюм. гос. ун-та.—2008.—№ 6.—С. 107-119.
Ниссенбаум О.В. Сравнение методов моментов и максимального правдоподобия при оценивании длительности мертвого времени в асинхронном альтернирующем потоке // Вестн. Томск, гос. ун-та. — 2006.-Ш8. - Прил.-С.279-284.
Ниссенбаум О.В. Построение плотности вероятностей интервала между соседними событиями асинхронного альтернирующего потока событий при непродлевающемся мертвом времени //Матем. и информац. моделирование: сб. научн. трудов. — Тюмень: Вектор-Бук. — 2006. — Вып.8. - С.137-148.
Ниссенбаум О.В. Оценивание длительности мертвого времени при продлении его периода в асинхронном дважды стохастическом потоке событий //Вестн. Томск, гос. ун-та. — 2007. — №23. — Прил. — С.291-294.
Ниссенбаум О.В. Построение оценок параметров асинхронного дважды стохастического потока событий с инициированием лишнего события и продлевающимся мертвым временем //Вестн. Томск, гос. ун-та. Серия УВТИ. - 2008. - №3(4). - С.77-85.
Ниссенбаум О.В. Оценивание параліетров и состояний асинхронного дважды стохастического потока с инициированием лишних событий
//Совр. проблемы матем. и информац. моделир. Перспективы разработки и внедрения инновац. ГГ-решений: сб. научн. трудов. — Тюмень. — 2008. — С. 80-87.
Горцев A.M., Ниссенбаум О.В. Оптимальная оценка состояний асинхронного альтернирующего потока с инициированием лишних событий //Новые информац. технологии в исслед. сложи, структур: Тез. докл. Седьмой Росс. конф. с межд. участ. — Томск: Изд-во НТЛ. — 2008. — С.80.
Ниссенбаум О.В. Построение оценок неизвестных параметров коррелированного дважды стохастического потока событий в условиях продлевающегося мертвого времени // Новые информац. технологии в исслед. сложи, структур: Тез. докл. Седьмой Росс. конф. с межд. участ. — Томск: Изд-во НТЛ. - 2008. - С.86.
Апробация работы. Основные положения диссертации докладывались и обсуждались:
на научном семинаре НИИ ИИС ТюмГУ, г. Тюмень, сентябрь 2005 г.;
на VI Всероссийской конференции с межд. участием "Новые информационные технологии в исследовании сложных структур", г. Шушенское, сентябрь 2006 г.;
на VI Всероссийской школе-семинаре "Проблемы компьютерной безопасности и криптографии" - SIBECRYPT'07, г. Горно-Алтайск, ТГУ, ГАГУ, сентябрь 2007 г.;
на межрегиональной научно-практической конференции института МиКН ТюмГУ "Современные математические методы и информационные технологии", г. Тюмень, май 2008 г.;
- на VII Всероссийской конференции с межд. участием "Новые информаци
онные технологии в исследовании сложных структур", г. Томск, сентябрь 2008 г.
Плотность вероятностей длительности интервала между соседними событиями
Рассматривается асинхронный альтернирующий поток событий, интенсивность которого есть кусочно-постоянный стационарный случайный процесс \(t) с двумя состояниями Лі = А и Аг = 0. Будем говорить, что имеет место первое состояние процесса (потока), если А() = Л, и второе состояние процесса (потока), если X(t) — 0. В течение временного интервала, когда процесс X(t) находится в первом состоянии, поток событий представляет собой пуассоповский поток с интенсивностью Л. Во втором состоянии процесса поток событий отсутствует.
Моменты перехода процесса из состояния в состояния не связаны с моментами наступления событий в пуассоновском потоке, поэтому, во-первых, поток называется асинхронным потоком событий и, во-вторых, так как Л2 = 0 — альтернирующим. Длительность нахождения процесса в г-м состоянии является случайной величиной, распределенной по экспоненциальному закону с параметром аг: Fi(t) = 1 — ехр(—att), і = 1, 2.
Стохастический граф переходов случайного процесса А() представлен на рис. 1.1.1. Граф имеет две вершины. Вершина 1 соответствует первому состоянию, вершина 2 - второму состоянию процесса. Каждая дуга имеет вес, равный интенсивности перехода из одного состояния в другое. Петли в вершинах опущены.
Далее введем три модификации рассматриваемого потока: 1) поток с инициированием лишнего события в первом состоянии в момент перехода процесса Л() из второго состояния в первое; 2) поток с инициированием лишнего события во втором состоянии в момент перехода процесса X(t) из первого состояния во второе; 3) поток с инициированием лишнего события во втором состоянии в момент перехода процесса А() из первого состояния во второе и в первом состоянии в момент перехода процесса X(t) из второго состояния в первое. Каждую из этих модификаций будем рассматривать в отдельности. Далее, для краткости, будем говорить "первый тип", "второй тип" и "третий тип". Отметим, что события пуассоновского потока и лишние события неразличимы для наблюдателя. ja, Пример реализации альтернирующего потока с инициированием лишних событий приведен на рис. 1.1.2. Рисунок под буквой а) соответствует первому варианту инициирования лишних событий в первом состоянии при переходе процесса X(t) из второго состояния в первое, под буквой б) — второму варианту инициирования - при переходе процесса X(t) из первого состояния во второе, под буквой в) — третьему варианту инициирования — при переходе процесса X(t) из СОСТ05ШИЯ в состояние. На временной оси белыми кружками показаны моменты наступления событий пуассоновского потока; черными кружками — лишние события. Жирной линией показана реализация случайного процесса А(), стрелками на ней показаны направления изменения случайного процесса. Случайный процесс X(t), а также тип события (пуассоновское или лишнее) являются ненаблюдаемыми. Параметры потока ori, «2, А полагаются извест 19 ными. Наблюдаются только временные моменты іі, 2,... наступления событий в потоке. Требуется по наблюдениям за потоком на некотором временном интервале оценить состояние потока в момент окончания наблюдений. Рассматривается установившийся (стационарный) режим функционирования наблюдаемого потока событий, поэтому переходными процессами на интервале наблюдения (to,t), где to - начало наблюдений, t - окончание наблюдений, пренебрегаем. Тогда без потери общности можно положить to — 0. Решение о состоянии потока выносится по критерию максимума апостериорной вероятности, представляющей наиболее полную характеристику состояния потока, которую можно получить, располагая только выборкой наблюдений, и обеспечивающей минимум полной вероятности ошибки вынесения решения [11]. Таким образом, для вынесения решения о состоянии ненаблюдаемого процесса A(t) в момент t необходимо определить апостериорные вероятности w(Xi\ti,... , t,n), і = 1,2, того, что в момент времени t процесс A(t) = Х{ (т — количество наблюденных событий за время t). При этом w(Xi\ti,... , tTO) -f w(X2\ti1... , tm) = 1, Ai = A, A2 = 0. Решение о состоянии процесса A(t) выносится путем сравнения апостериорных вероятностей: 1) если u (Aii,..., tm) iy(A2ti,..., tm), то оценка состояния процесса есть X(t) = Ai; 2)если w(Xo\ti,... ,tm) w(Xi\ti,... ,tm), то оценка состояния процесса есть X(t) = А2. В следующем разделе определим плотность вероятностей длительности интервала между соседними событиями р(т) (далее плотность р(т)) в наблюдаемом потоке, которая понадобится для того, чтобы получить аналитические выражения для ошибок вынесения решения при оптимальном оценивании состояний потока, а также определим некоторые важные свойства альтернирующего потока. Следующая лемма устанавливает характер случайного процесса X(t). Лемма 1.2.1. Случайный кусочно-постоянный процесс A(t) является марковским процессом. Доказательство. Докажем, что после некоторого момента времени to поведение процесса X(t) не зависит от предыстории, т.е. не зависит от того, как протекал процесс A(t) до момента времени to. Поведение процесса A(t) после момента времени to зависит только от схемы изменения состояний после момента to, и не зависит от наступления событий альтернирующего потока. Пусть A(t) в момент to находится в г-м состоянии (г = 1,2). Поскольку длительность нахождения процесса в г-м состоянии есть случайная величина, распределенная по экспоненциальному закону, то она обладает свойством отсутствия последействия, а значит оставшаяся часть длительности нахождения процесса X(t) в г-м состоянии не зависит от того, как долго до момента to процесс A(t) находился в г-м состоянии. Переход же из г -го состояния в j-e ({i,j} = {1,2}) полностью определяется моментом окончания пребывания процесса в г-м состоянии. Таким образом, поведение процесса A(t) не зависит от предыстории, а зависит только от состояния процесса в момент to- Следовательно, A(t) — марковский процесс. Лемма доказана. Определим теперь априорные стационарные вероятности состояний процесса X(t). Обозначим щ - вероятность того, что процесс A(t) находится в г-м состоянии в любой момент времени, г = 1, 2.
Построение плотности вероятностей длительности интервала между соседними событиями для потока первого типа
Рассматривается асинхронный альтернирующий поток событий с двумя состояниями, описанный в разделе 1.1. Напомним конструкцию потока. Интенсивность рассматриваемого потока является ненаблюдаемой и представляет собой кусочно-постоянный стационарный случайный процесс \(t) с двумя состояниями Аі = АиА2 = 0.В первом состоянии процесса поток событий представляет собой пуассоиовский поток с интенсивностью А. Во втором состоянии процесса поток событий отсутствует. Длительность нахождения процесса в і-м состоянии является случайной величиной, распределенной по экспоненциальному закону с параметром af. Fi(t) = 1 — ехр(—а$), (г = 1,2). Как и в первой главе, рассматриваются три типа потоков.
После каждого зарегистрированного в момент времени г- события, независимо от того, было ли это событие пуассоновкого потока или лишнее событие, наступает время фиксированной длительности Т (мертвое время), в течение которого другие события исходного потока недоступны наблюдению. События, наступившие в течение мертвого времени, не вызывают продления его периода. По окончании мертвого времени первое наступившее событие снова создает период мертвого времени длительности Т и т. д.
Пример реализации альтернирующего потока с иницированием лишних событий приведен на рис. 2.1.1. Рисунок под буквой а) соответствует потоку первого типа, под буквой б) - потоку второго типа, под буквой в) - потоку третьего типа. На каждой из схем рис. 2.1.1 имеется две проекции оси абсцисс. На первой из них кружками показаны моменты наступления событий в потоке. При этом белыми кружками обозначены наблюдаемые события, черными кружками обозначены события, которые недоступны наблюдению, так как произошли в периоды мертвого времени. Периоды мертвого времени обозначены черными прямоугольниками. На второй проекции белыми кружками обозначены моменты наступления событий наблюдаемого потока. Жирной линией над первой проекцией оси абсцисс показана реализация случайного процесса Л (t), стрелками на ней показаны направления изменения случайного процесса. Случайный процесс А(), а также тип событий ("пуассоновское" или "лишнее") являются ненаблюдаемыми; наблюдаются только временные моменты і,І2? наступления событий в наблюдаемом потоке. Необходимо по этим наблюдениям оценить (в момент окончания наблюдений) параметры А, а\, а 2 и длительность мертвого времени Т. Рассматривается установившийся (стационарный) режим функционирования наблюдаемого потока событий, поэтому переходными процессами на интервале наблюдения (to,t), где to - начало наблюдений, t - окончание наблюдений, пренебрегаем. Тогда без потери общности можно положить Q=0. Для получения оценок параметров потока необходимо построить математическую модель наблюдаемого потока, то есть определить плотность вероятностей длительности интервала между соседними событиями в наблюдаемом потоке р(т), которая, очевидно, будет зависеть от параметров потока и длительности мертвого времени Т, и воспользоваться статистическими методами оценивания — такими, как метод моментов и метод максимального правдоподобия [11]. 2.2. Построение плотности вероятностей длительности интервала между соседними событиями в потоке с непродлевающимся мертвым временем Потоки первого, второго и третьего типов, рассматриваемые в данной главе, отличаются от потоков, рассмотренных в первой главе, только наличием мертвого времени, привязанного к моменту наступления события в наблюдаемом потоке. Процесс X(t) остается марковским, априорные вероятности состояний 7Гі и 7Г2 процесса X(t), по-прежнему, определяются формулой (1.2.1), так как эволюция процесса X(t) не зависит от событий потока и мертвого времени. Определим последовательность действий для нахождения плотности вероятностей р(т). Сначала для каждого из трех типов потоков найдем вероятности щ(Т) -условная стационарная апостериорная вероятность того, что процесс Х(і) в момент времени t находится в г-м состоянии при условии, что в этот момент времени наступило событие наблюдаемого потока. Вероятности щ(Т) зависят не только от процесса А(), но и от схемы наступления событий потока. Затем положим, что в наблюдаемом потоке регистрируется событие. Не нарушая общности, припишем этому событию момент времени t — 0. Обозначим через 7Tj(t\T) - условную вероятность того, что в момент времени t процесс X(t) будет находиться в состоянии j (j = 1, 2) при условии, что в момент времени t = 0 наступило событие наблюдаемого потока и начался период мертвого времени длительности Т (7Гі(Т) + 7T2(tT) = 1). Эти вероятности будем находить путем составления и решения системы дифференциальных уравнений с начальными условиями 7Г;(0Т) = itj(T), j — 1,2. Заметим, что %j(t = Т\Т) суть вероятности состояний процесса А() в момент окончания мертвого времени.
Рассмотрим после этого временной интервал длительности г = T+t, состоящий из двух смежных интервалов: первый - длительности Т, второй - длительности t. Началом первого интервала является момент наступления события в наблюдаемом потоке, началом второго - момент окончания мертвого времени. Обозначим Pi(t) - вероятность того, что в момент времени T+t процесс Х(и) будет находиться в г-м состоянии (і — 1, 2) и на полуинтервале [T,T + t) событий наблюдаемого потока не произойдет (t 0).
Преобразование Лапласа для потока первого типа
Коротко сформулируем результаты четвертой главы. 1. Разработан и реализован в виде программы на ЭВМ алгоритм имитационного моделирования альтернирующего потока трех типов с продлевающимся и иепродлсвающимся мертвым временем фиксированной длительности. 2. Разработан и реализован в виде программы на ЭВМ алгоритм оптимального оценивания состояний альтернирущего потока первого, второго и третьего типов. 3. Разработан и реализован в виде программы на ЭВМ алгоритм оценивания длительности мертвого времени и параметров альтернирующего потока трех типов с непродлевающимся мертвым временем. 4. Разработан и реализован в виде программы на ЭВМ алгоритм оценивания длительности мертвого времени в условиях его продления для альтернирующего потока первого, второго и третьего типов. 5. Приведен расчет величин, характеризующих качество оценивания для каждого из алгоритмов (для оценки состояний — безусловная вероятность ошибочного решения (первый и второй тип потока) и частоты ошибочного решения (третий тип потока); для оценки параметров - статистические характеристики оценок, полученные в численном эксперименте, такие как выборочное среднее, выборочная дисперсия, выборочная вариация). На основе полученных результатов оценивания состояний и параметров альтернирующего потока с инициированием лишних событий можно сделать вывод о достаточно качественных оценках в смысле введенных критериев: минимума полной (безусловной) вероятности ошибочного решения (первый и второй тип потоков) или частот вынесения ошибочного решения (третий тип потока) о состоянии потока и выборочной вариации оценок параметров. Подчеркнем, что оценки состояний потока являются оптимальными и обеспечить меньшую вероятность ошибочного решения невозможно. Основной вывод настоящей главы заключается в том, что на основе сформулированных алгоритмов пунктов 1.4, 2.5 разработаны программы на ЭВМ, готовые для использования в задачах проектирования систем массового обслуживания, таких как цифровые сети интегрального обслуживания, телекоммуникационные сети, измерительные системы и т.д. В диссертационной работе рассмотрены вопросы, связанные с оценкой состояний и параметров асинхронного альтернирующего дважды стохастического потока событий с инициированием лишних событий при переходе процесса X(t) из состояния в состояние (три типа потока) в условиях присутствия мертвого времени (продлевающегося и непродлевающегося). Основные теоретические и практические результаты диссертационной работы состоят в следующем: 1. Получены явные аналитические формулы для плотности вероятностей интервала между соседними событиями в альтернирующем потоке с инициированием лишних событий в случаях: отсутствия мертвого времени, наличия непродлевающегося мертвого времени фиксированной длительности, а также получено преобразование Лапласа плотности вероятностей интервала между соседними событиями в альтернирующем потоке с инициированием лишних событий и продлевающимся мертвым временем. 2. Получены явные аналитические формулы для апостериорных вероятностей состояний альтернирующего потока с инициированием лишних событий (первый, второй и третий тип потока) в любой момент времени наблюдения за потоком. На основе критерия максимума апостериорной вероятности находятся оценки состояний альтернирующего потока с инициированием лишних событий. Данный критерий обеспечивает минимум вероятности ошибочного решения. Получены явные формулы для полной (безусловной) вероятности ошибочного решения (первый и второй тип потока), а также алгоритм расчета условной вероятности ошибочного решения для третьего типа потока. 3. На основе полученных плотностей вероятностей в явном виде получена оценка максимального правдоподобия (первый и второй тип потока) и эвристическая оценка (третий тип потока) длительности мертвого времени для альтернирующего потока с инициированием лишних событий и непродлевающимся мертвым временем.
Результаты численного расчета оценок параметров в условиях непродлевающегося мертвого времени
В Приложении 2 приведено описание (в виде блок-схемы) алгоритма расчета апостериорной вероятности первого состояния w(X\t) и алгоритм оценки состояний процесса X(t). В качестве иллюстрации результатов работы программы представлены следующие примеры на рис. 4.1.1 - 4.1.6.
На рис. 4.1.1 и 4.1.2 приведены результаты для потока первого типа при значениях параметров: Л = 1, a?i = 0,1, «2 — 0,2 и общем времени моделирования tcom = 100. При этом на рис. 4.1.1 представлен график поведения апостериорной вероятности первого состояния w(X\t); на рис. 4.1.2 — траектории случайного процесса X(t) (внизу) и оценки X(t) (вверху). На рис. 4.1.2 штриховкой на оси времени обозначены промежутки, на которых оценка состояния не совпадает с истинным значением процесса. На рис. 4.1.5 и 4.1.6 приведены аналогичные результаты для потока третьего типа при значениях параметров: А = 1, а\ = 0,1, «2 = 0,1. В разделе 1.5 получены выражения для вероятности вынесения ошибочного решения при оценивании состояния процесса X(t) по наблюдениям за моментами наступления событий. Аналитические выражения для вероятностей ошибок оценивания получены только для потоков первого и второго типов. Для потока третьего типа таких выражений получить не удалось по причине его коррелированное. Для установления частоты ошибочных решений о состоянии случайного процесса \(t) по наблюдениям за потоком третьего типа проведен статистический эксперимент, состоящий из следующих этапов: 1) для определенного набора параметров A, ai, а.2 осуществляется моделирование потока третьего типа на заданном отрезке времени [0,сотп]; 2) расчет апостериорных вероятностей ги(А) первого состояния процесса X(t) на заданном отрезке; 3) оценивание траектории процесса X(t) (оценивание на отрезке [0, tcom] интервалов, когда оценка X(t) принимает то или иное значение); 4) определение di — суммарной протяженности интервалов, на которых значение процесса X(t) не совпадает с его оценкой Л(); 5) вычисление доли ошибочных решений pi = di/tcom, і — 1, JV; 6) повторение TV" раз шагов 1-5 для расчета оценки безусловной ошибки оценивания состояний на отрезке [0,сош]. .і Результатом выполнения описанного алгоритма явлется выборка pi,p%, IPN долей ошибочных решений в N экспериментах. По этому набору рассчитывается выборочное среднее (частота или оценка) ошибочного решения Числовые значения Ро я D представлены в таблице 4.1.1 для а\ = 0,1, «2 = 0, 1 и Л = 1 при N=100 и времени моделирования tcom = 200, 400, ..., 1800. Анализ результатов, приведенных в табл. 4.1.1, показывает, что получаемые оценки вероятностей ошибочного решения о состоянии потока достаточно стабильны. Дисперсия, начиная с общего времени моделирования tcom = 1000, не превышает величины 0,0001, что говорит о достаточно высоком качестве оценивания. 124 На рис. 4.1.7 представлены графики частоты ошибок PQ, вычисленные в результате работы описанного алгоритма, при а\ — О,1, когда осі изменяется по оси абсцисс от 0,001 до 2 с шагом 0,001 для различных значений Л =0,1; 0,5; 1; 2; 5 (каждому значению Л соответствует отдельная кривая на графике); N = 100, tcom = 1000 ед.вр. На рис. 4.1.8 и 4.1.9 для сравнения приведены графики безусловных вероятностей ошибок PQ для потоков первого и второго типов при тех же значениях параметров, рассчитанные по формулам (1.5.8), (1.5.9), (1.5.11), (1.5.12) для первого типа потока и (1.5.16), (1.5.18), (1.5.20)-(1.5.22), (1.5.24), (1.5.25), (1.5.27) для второго типа потока. Интегралы, входящие в выражения для PQ, найдены численно методом прямоугольников с точностью є = 0,001. Отметим, что изменение параметров Л и с 2 в указанных пределах обеспечивает охват всех приведенных формул для вычисления PQ. Анализ результатов показывает, что наибольшая вероятность ошибки для любого из типов потока наблюдается при малой интенсивности Л, что является естественным, так как в этом случае альтернирующий поток событий приближается к пуассоновскому и различение состояний становится затруднительным. Малая по величине вероятность ошибки оценивания наблюдается при большом (относительно а\ и 0) параметре Л, что также естественно, поскольку в этом случае на каждом интервале, когда \{t) = Л, наблюдается большое количество событий, а значит, такие интервалы достаточно легко выделить. Однако, в любом случае, вероятность ошибки при оценивании не превышает 0,5 в силу того, что оценка состояний производится согласно критерию максимума апостериорной вероятности. Отметим, что оценки состояний являются оптимальными, поэтому обеспечить меньшую вероятность ошибочного решения при равной информированности невозможно.
