Оценивание длительности мертвого времени и параметров асинхронного дважды стохастического потока событий методом моментов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат физико-математических наук Васильева, Лариса Анатольевна

• Васильева, Лариса Анатольевна
• кандидат физико-математических наук
• 2005

Оглавление диссертации кандидат физико-математических наук Васильева, Лариса Анатольевна

Введение.

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

1.1. Постановка задачи.

1.2. Плотность распределения вероятностей интервала времени между соседними событиями наблюдаемого потока.

1.3. Оценивание длительности мертвого времени и параметров асинхронного дважды стохастического потока событий методом моментов.

1.4. Свойства оценок.

1.4.1. Состоятельность оценок.

1.5. Построение оценок асинхронного потока событий в случае, когда мертвое время — случайная величина.

1.5.1. Распределение вероятностей для наблюдаемого потока событий.

1.6. Выводы к главе 1.

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

2.1. Постановка задачи.

2.2. Преобразование Лапласа плотности распределения вероятностей интервала времени между соседними событиями наблюдаемого потока.

2.3. Оценивание длительности мертвого времени и параметров асинхронного потока событий методом моментов.

2.4. Выводы к главе 2.

3. Имитационное моделирование асинхронного дважды стохастического потока событий при условии его частичной наблюдаемости. Статистические эксперименты. Численные результаты.

3.1. Имитационное моделирование асинхронного дважды стохастического потока событий в схеме с непродлевающимся мертвым временем. Статистические эксперименты.

3.1.1. Алгоритм построения доверительных интервалов для математических ожиданий оценок параметров.

3.1.2. Численные результаты.

3.1.2.1 Доверительные интервалы для математических ожиданий оценок параметров.

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

3.2. Имитационное моделирование асинхронного альтернирующего дважды стохастического потока событий в схеме с непродлевающимся мертвым временем. Мертвое время -случайная величина. Статистические эксперименты.

3.2.1. Алгоритм построения доверительных интервалов для оценивания математических ожиданий оценок.

3.2.2. Численные результаты.

3.2.2.1. Доверительные интервалы для математических ожиданий оценок параметров.

3.3. Имитационное моделирование асинхронного дважды стохастического потока событий в схеме с продлевающимся мертвым временем. Статистические эксперименты.

3.3.1. Алгоритм построения доверительных интервалов для математического ожидания оценки периода мертвого времени.

3.3.2. Численные результаты. Доверительные интервалы для математического ожидания оценки периода мертвого времени.

3.4. Выводы к главе 3.

Введение диссертации (часть автореферата) на тему «Оценивание длительности мертвого времени и параметров асинхронного дважды стохастического потока событий методом моментов»

Актуальность работы

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

Основоположником теории массового обслуживания считается известный датский ученый А.К. Эрланг. Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909 г. работу "Теория вероятностей и телефонные переговоры", в которой решил ряд задач по теории систем массового обслуживания с отказами. Значительный вклад в создании и разработку общей теории массового обслуживания внес выдающийся математик А .Я. Хинчин, им и был предложен термин теория массового обслуживания. В зарубежной литературе чаще используется название теория очередей. Основы математической теории массового обслуживания заложены в монографиях и учебных руководствах А.Я. Хинчина [93], Б.В. Гнеденко, И.Н. Коваленко [24], Г.П. Климова [52], Т.Л. Саати [83], Бодино А., Брамбилла [97], А. Кофмана, Р. Крюона [59], Д. Риордана [79], Р. Сиски [115], Л. Клейнрока [51]. Дальнейшее развитие теории массового обслуживания связано с изучением различного рода приоритетных систем, которым посвящены монографии Б.В. Гнеденко, Э.А. Даниэляна, Б.Н. Димитрова, Г.П. Климова, В.Ф. Матвеева [26], О.И. Бронштейна, И.М. Духовного [15], В.В. Мовы, Л.А. Пономаренко, А. М. Калиновского [64], Г.П. Климова, Г.К. Мишкоя [53], М.И. Волковинского, А.Н. Кабалевского [20], Н. Джейсуола [39]. Методы теории массового обслуживания в достаточно сжатой форме изложены в монографии Д. Кенига, Д. Штояна [50]. Основные элементы тенденций развития теории массового обслуживания даны в работе Г.И. Ивченко, В.А. Каштанова, И.Н. Коваленко [46]. Обширная библиография по различным аспектам теории массового обслуживания и ее приложениям, а также направлениям исследований приведены в целом ряде обзорных статей (В.В. Рыков [81], Б.В. Гнеденко, И.Н. Коваленко [25], И.Н. Коваленко [54, 55], Ю.К. Беляев, Б.В. Гнеденко, И.А. Ушаков [12], Ю. Бхат [18], Д. Кениг, В.В. Рыков, Ф. Шмидт [49], М.А. Файнберг, Е.А. Файнберг [90]).

Одним из важных направлений в теории массового обслуживания и ее приложениях, является направление, связанное с управляемыми системами массового обслуживания (СМО). Первые работы по управляемым СМО появились в середине шестидесятых годов [16, 17, 19, 21, 80, 82, 100, 108, 118, 119]. Затем последовали многочисленные публикации, связанные с различными оптимизационными постановками задач [38, 40, 45, 65, 66, 67, 77, 85, 89, 109, 113, 114, 117]. В публикациях [32, 67, 81, 90] имеются достаточно полные обзоры работ по управляемым СМО.

Расширение поля приложений неизбежно привело к увеличению числа исследователей и к расширению того круга изданий, в которых появляются работы по теории массового обслуживания. Однако, несмотря на большое количество работ, остается еще много проблем, требующих дополнительного исследования. В частности, анализ литературных источников приводит к выводу, что в литературе по теории массового обслуживания и ее приложениям совсем незначительное количество работ посвящено адаптивным системам, т.е. системам, функционирующим в условиях полной или частичной неопределенности. Наряду с тем, что подавляющее число авторов рассматривает ситуации, когда все параметры, характеризующие СМО, точно известны, в реальности дело обстоит, как правило, иначе. Если в отношении параметров, характеризующих обслуживающие устройства, можно сказать, что они известны и с течением времени не меняются, то в отношении интенсивностей входящих потоков или других их параметров этого сказать во многих случаях нельзя. Интенсивность входящих потоков обычно меняется со временем, часто эти изменения носят случайный характер; последнее приводит к рассмотрению дважды стохастических потоков событий [102]. С другой стороны, очевидно, что функционирование СМО непосредственно зависит от интенсивностей входящих потоков заявок: чем больше интенсивности входящих потоков, тем напряженнее режим обслуживания, требующий, например, подключения дополнительных обслуживающих приборов. Вследствие этого важной задачей является задача оценки в произвольный момент времени параметров потока событий по наблюдениям за этим потоком.

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

СМО с подобными потоками, появились около 20 лет назад, однако до сих пор относительное число работ, посвященных вопросам оценивания параметров дважды стохастических потоков событий в различных условиях наблюдаемости достаточно мало, и исследования в этой области по-прежнему являются актуальными.

Потоки событий с интенсивностью, зависящей от времени и являющейся случайным процессом, можно разделить на два класса. К первому классу относятся потоки с интенсивностью Х(г), являющейся непрерывным случайным процессом. Примером исследований задач, связанных с оценкой интенсивности такого рода потоков, являются работы [22, 23, 78]. Ко второму классу можно отнести потоки, для которых интенсивность есть кусочно-постоянный процесс с конечным числом состояний (х.,Д2,.Д„). Переход процесса из состояния в состояние происходит в случайные моменты времени, при этом на интервалах времени, когда процесс А,(/) находится в состоянии поток событий ведет себя как стационарный пуассоновский поток интенсивности А,. Такие потоки являются наиболее характерными для реальных вычислительных сетей и систем. По-видимому, впервые потоки второго типа применительно к системам массового обслуживания были рассмотрены в работах М. Ньютса [106] и Г.П. Башарина [8, 9]. В последней работе был рассмотрен поток событий, для которого переход из состояния в состояние управлялся марковской цепью (отсюда название "МС (Markov chain)-n0t0kh событий"). Развитие исследований СМО с кусочно-стационарными марковскими потоками событий (публикации [68, 41, 42, 98, 103, 104, 105, 107]) привели к созданию модели ВМАР (Batch Markovian Arrival Process) - потоков. Монография А.Н. Дудина и В.И. Клименок [43] посвящена исследованию различных систем массового обслуживания с входящими ВМАР-потоками. В целом такого рода кусочно-стационарные потоки событий могут быть разделены на 3 класса:

1) синхронные дважды стохастические потоки событий — потоки с интенсивностью, для которой переход из состояния в состояние происходит в случайные моменты времени, являющиеся моментами наступления событий;

2) асинхронные дважды стохастические потоки событий — потоки с интенсивностью, для которой переход из состояния в состояние не зависит от моментов наступления событий;

3) полусинхронные дважды стохастические потоки событий — потоки, в которых для одного множества состояний справедливо 1, а для остальных состояний справедливо 2.

В научной литературе описанные потоки исследуются с двух точек зрения: построения оценок состояний (задачи фильтрации) и параметров ненаблюдаемой интенсивности потока (задачи оценивания) (работы [11, 22, 27, 28, 29, 30, 31, 33, 34, 35, 36, 37, 47, 56, 58, 69, 87, 94, 116]) и анализа процессов функционирования СМО с такого рода входящими потоками [40,41,57, 63,74, 75, 96, 101].

В данной работе рассматривается задача оценивания параметров асинхронного МС-потока событий с интенсивностью х((), являющейся кусочно-постоянным марковским процессом, принимающим два значения (А., Д2) события которого частично наблюдаемы. Частичная наблюдаемость связана с возникновением, так называемой, схемы мертвого времени, когда после наступления события в асинхронном потоке наступает некоторое время фиксированной длительности (период мертвого времени), в течение которого другие события недоступны наблюдению. Одним из основных искажающих факторов при определении характеристик случайных потоков выступает мертвое время устройств регистрации [7, 61, 62]. В течение мертвого времени обрабатывается зарегистрированное событие, а любое другое событие, поступившее на вход системы в этот период теряется. По этой причине счетчик событий показывает, как правило, не истинную картину, а несколько искаженный ход явлений. В связи с этим возникает задача оценивания параметров (характеристик) истинного потока событий, поступающего на вход системы. В конкретных устройствах величина и характер мертвого времени зависят от многих факторов. В первом приближении можно считать, что этот период продолжается некоторое определенное (фиксированное) время Г. Все устройства регистрации с достаточной степенью приближения можно разделить на две группы. Первую группу составляют устройства с непродлевающимся мертвым временем, которое не зависит от поступления других событий в пределах его действия. Непродлевающееся мертвое время иногда называют мертвым временем первого рода, а соответствующие устройства регистрации - счетчиками или регистраторами типа I. Ко второй группе относятся устройства с продлевающимся мертвым временем (регистраторы II типа). В этом случае мертвое время возникает после любого события, поступившего на вход системы, вне зависимости, от факта его регистрации. В первой главе диссертации решается задача оценивания параметров асинхронного потока событий и длительности мертвого времени в схеме с непродлевающимся мертвым временем методом моментов, во второй главе решается аналогичная задача, но в схеме с продлевающимся мертвым временем, в третьей главе представлены алгоритмы статистических экспериментов и численные результаты.

Подобные задачи решены для простейшего потока событий при наличии непродлевающегося мертвого времени [28] методом максимального правдоподобия, для простейшего потока событий в схеме с продлевающимся мертвым временем - методом моментов [30]. Для альтернирующего дважды стохастического потока событий эти задачи решены в [35, 36, 44, 71, 72, 73].

Остановимся теперь на методе моментов, с помощью которого и предлагается находить оценки для параметров распределения по выборочным значениям в данной работе. Считается, что метод моментов, введенный К. Пирсоном ([110, 111, 112]), является самым первым общим методом оценивания неизвестных параметров по выборочным значениям. Этот метод заключается в приравнивании определенного количества выборочных моментов к соответствующим моментам распределения, являющимися функциями от неизвестных параметров. Рассматривая количество моментов, равное числу подлежащих оценке параметров, и решая полученные уравнения относительно этих параметров, получаем искомые оценки. Известно, что оценки, получаемые таким способом, не являются "наилучшими" из возможных (имеют не наименьшую возможную дисперсию ) [48, 60] (свойства оценок метода моментов обсуждаются в параграфе 4 главы 1 ) . Тем не менее, метод моментов часто очень удобен для практических целей.

Цель работы.

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

Методы исследования.

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

Научная новизна. Результаты, выносимые на защиту.

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

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

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

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

Теоретическая ценность.

Теоретическая ценность заключается в том, что в работе:

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

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

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

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

Практическая ценность.

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

Работа выполнялось в рамках научно-исследовательской работы Томского государственного университета "Разработка алгоритмов оценки параметров и состояний дважды стохастических потоков заявок, циркулирующих в информационно-вычислительных, локально-вычислительных сетях и коммутационных системах" (код темы по ГРНТИ: 28.17.19.29.19.15) в период с 1996 по 2000г.г. и научно-исследовательской работы "Исследование и разработка моделей высокопроизводительных многопроцессорных систем и методов обеспечения компьютерной безопасности" (код темы по ГРНТИ: 50.07.05) в период с 2001 по 2004г.г.

Публикации.

По материалам данных исследований опубликовано 6 работ: 1. Васильева Л.А. Оценивание параметров дважды стохастического потока событий в условиях присутствия мертвого времени // Вестник Томского государственного университета. Материалы научных конференций, симпозиумов, школ, проводимых в ТГУ.- Томск: ТГУ, 2002.-№1. - С. 9-13.

2. Васильева JI.A., Горцев A.M. Оценивание параметров МС-потока при условии его частичной наблюдаемости//Математическое моделирование. Кибернетика. Информатика. — Томск: ТГУ, 1999.- С.34-41.

3. Васильева JI.A., Горцев A.M. Оценивание параметров дважды стохастического потока событий в условиях его неполной наблюдаемости//Материалы Всероссийской научно-практической конференции "Новые технологии и комплексные решения: наука, образование, производство". Часть II (математика). — Кемерово: изд-во Кемеровского университета, 2001.- С. 14-16.

4. Васшьева JI.A. Оценивание параметров МС-потока событий при условии его частичной ненаблюдаемости // Сборник материалов конференции СФТИ при Томском госуниверситете, посвященной 70-летию образования института: 29сентября-2 октября 1998г. Тезисы докладов. - Томск: Изд-во СФТИ, 1998.-С. 46-47.

5. Васильева JI.A., Горцев A.M. Оценивание параметров дважды стохастического потока событий в условиях его неполной наблюдаемости // Автоматика и телемеханика. - 2002. — №3. — С.179-184.

6. Васильева JI.A., Горцев A.M. Оценивание длительности мертвого времени асинхронного дважды стохастического потока событий в условиях его неполной наблюдаемости // Автоматика и телемеханика. -2003. - № 12. - С.69-79.

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

-на юбилейной конференции СФТИ при Томском госуниверситете, посвященной 70-летию образования института (Томск, 29 сентября - 2 октября 1998г.);

-на IV Всероссийской конференции с международным участием "Новые информационные технологии в исследовании сложных структур" и Сибирской научной школы-семинара "Проблемы компьютерной безопасности" (Томск, ТГУ, 10-13 сентября 2002г.).

-на Всероссийской научно-практической конференции "Новые технологии и комплексные решения: наука, образование, производство" (Анжеро-Судженск, 18-19 октября 2001г.)

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

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Васильева, Лариса Анатольевна

Результаты работы отражены в 6 публикациях.

ЗАКЛЮЧЕНИЕ

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

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

Основные научные и практические результаты состоят в следующем:

- получен вид плотности распределения вероятностей интервала между соседними событиями наблюдаемого потока в схеме с непродлевающимся мертвым временем;

- получен вид плотности распределения вероятностей интервала между соседними событиями наблюдаемого потока в схеме с непродлевающимся мертвым временем, когда мертвое время — случайная величина;

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

- получен вид преобразования Лапласа плотности распределения вероятностей интервала между соседними событиями наблюдаемого потока в схеме с продлевающимся мертвым временем;

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

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