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

Введение.

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

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

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

1.3. Оценивание длительности мертвого времени и параметров альтернирующего потока событий методом моментов.

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

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

1.4.2. Асимптотическая эффективность оценок.

1.4.2.1. Потенциальная точность для оценок параметров \zx,z2,4 ,Т}

1.4.2.2. Асимптотические дисперсии оценок параметров к, и, (), '/'} и величин {г. г,, у}.

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

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

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

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

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

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

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

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

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

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

3.1.3.1. Доверительные интервалы для оценок параметров

3.1.3.2. Оценки асимптотических дисперсий оценок параметров у,'/'}.

3.1.3.3. Потенциальная точность и эффективность оценок параметров {zj,z2,y,r}.

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

3.2.1. Алгоритм построения доверительных интервалов для оценок параметров {А,,а,Р,Г}.

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

3.2.2.1. Доверительные интервалы для оценок параметров {X.а.(},'/'}.

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

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

Основоположником теории массового обслуживания считается известный датский ученый А.К. Эрланг. Являясь сотрудником Копенгагенской телефонной компании, он опубликовал в 1909 г. работу "Теория вероятностей и телефонные переговоры", в которой решил ряд задач по теории систем массового обслуживания с отказами. Значительный вклад в создании и разработку общей теории массового обслуживания внес выдающийся математик А.Я. Хинчин, им и был предложен термин теория массового обслуживания. В зарубежной литературе чаще используется название теория очередей. Основы математической теории массового обслуживания заложены в монографиях и учебных руководствах А.Я. Хинчина [84], Б.В. Гнеденко, И.Н. Коваленко [15], Г.П. Климова [41], Т.Л. Саати [73], Бодино А., Брамбилла [87], А. Кофмана, Р. Крюона [48], Д. Риордана [69], Р. Сиски [106], Л. Клейнрока [40]. Дальнейшее развитие теории массового обслуживания связано с изучением различного рода приоритетных систем, которым посвящены монографии Б.В. Гнеденко, Э.А. Даниэляна, Б.Н. Димитрова, Г.П. Климова, В.Ф. Матвеева [17], О.И. Бронштейна, И.М. Духовного [7], В.В. Мовы, Л.А. Пономаренко, А. М. Калиновского [53], Г.П. Климова, Г.К. Мишкоя [42], М.И. Волковинского, А.Н. Кабалевского [12], Н. Джейсуола [28].

Методы теории массового обслуживания в достаточно сжатой форме изложены в монографии Д. Кенига, Д. Штояна [39]. Основные элементы тенденций развития теории массового обслуживания даны в работе Г.И. Ивченко, В.А. Каштанова, И Н. Коваленко [35]. Обширная библиография по различным аспектам теории массового обслуживания и ее приложениям, а также направлениям исследований приведены в целом ряде обзорных статей (В.В. Рыков [71], Б.В. Гнеденко, И.Н. Коваленко [16], И.Н. Коваленко [43, 44], Ю.К. Беляев, Б.В. Гнеденко, И.А. Ушаков [5], Ю. Бхат [10], Д. Кениг, В В. Рыков. Ф. Шмидт [38], М.А. Файнберг, Е.А. Файнберг [81]).

Одним из важных направлений в теории массового обслуживания и ее приложениях, является направление, связанное с управляемыми системами массового обслуживания (СМО). Первые работы по управляемым СМО появились в середине шестидесятых годов [8, 9, 11, 13, 70, 72, 91, 99, 109, 110]. Затем последовали многочисленные публикации, связанные с различными оптимизационными постановками задач [27, 29, 34, 54, 67, 75, 100, 108]. В публикациях [21, 56, 71, 81] имеются достаточно полные обзоры работ по управляемым СМО.

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

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

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

Примером исследований задач, связанных с оценкой интенсивности такого рода потоков, являются работы [14, 60]. Ко второму классу можно отнести потоки, для которых интенсивность \(t) есть кусочно-постоянный процесс с конечным числом состояний (Х, Д2,.,ХП). Переход процесса л(/) из состояния в состояние происходит в случайные моменты времени, при этом на интервалах времени, когда процесс \(j) находится в состоянии А,,, поток событий ведет себя как стационарный пуассоновский поток интенсивности . Такие потоки являются наиболее характерными для реальных вычислительных сетей и систем. По-видимому, впервые потоки второго типа применительно к системам массового обслуживания были рассмотрены в работах М. Ньютса [97] и Г.П. Башарина [1]. В последней работе был рассмотрен поток событий, для которого переход из состояния в состояние управлялся марковской цепью (отсюда название "МС (Markov с1шп)-потоки событий"). Развитие исследований СМО с кусочно-стационарными марковскими потоками событий (публикации [57, 89, 94, 95]) привели к созданию модели ВМАР (Batch Markovian Arrival Process) - потоков. Монография А.Н. Дудина и В.И. Клименок [30] посвящена исследованию различных систем массового обслуживания с входящими ВМАР-потоками. В целом такого рода кусочно-стационарные потоки событий могут быть разделены на 3 класса:

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

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

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

В научной литературе описанные потоки исследуются с двух точек зрения: построения оценок состояний (задачи фильтрации) и параметров ненаблюдаемой интенсивности потока (задачи оценивания) (работы [4, 14 19, 20, 22, 23, 24 26, 36, 45, 47, 77, 79, 85, 107]) и анализа процессов функционирования СМО с такого рода входящими потоками [30, 31, 46, 52, 64, 65, 87, 92].

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

Подобные задачи решены для простейшего потока событий при наличии непродлевающегося мертвого времени [19] методом максимального правдоподобия, для простейшего потока событий в схеме с продлевающимся мертвым временем -методом моментов [20].

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

Цель работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации.

По материалам данных исследований опубликовано 7 работ:

1. Завгородняя М.Е. Оценка параметров альтернирующего потока событий при условии его частичной наблюдаемости // Третья международная научно-техническая конференция "Актуальные проблемы электронного приборостроения", 1996 г., Новосибирск. Тезисы докладов. Т.6. Часть 1. Моделирование и вычислительная техника. -Новосибирск: Изд-во НГТУ, 1996. - С.98-99.

2. Горцев A.M., Завгородняя М.Е. Оценка параметров альтернирующего потока событий при условии его частичной наблюдаемости // Оптика атмосферы и океана. - 1997.-N3.-C. 273-280.

3. Паршина М.Е. Асимптотические дисперсии оценок параметров альтернирующего потока событий при условии его частичной наблюдаемости //Международная конференция "Всесибирские чтения по математике и механике при Томском государственном университете ": 17-20 июня 1997 г. Тезисы докладов. Т.1. Математика. -Томск: Изд-во ТГУ, 1997. - С. 137-138.

4. Горцев A.M., Паршина М.Е. Об оценивание периода ненаблюдаемости и параметров альтернирующего потока событий // Массовое обслуживание: потоки, системы, сети. Сборник материалов 14 Белорусской школы-семинара по теории массового обслуживания. - Минск: Изд-во БГУ, 1998 г. - С. 12-16.

5. Паршина М.Е. Исследование свойств оценок параметров альтернирующего потока событий в условиях "мертвого" времени// Сборник материалов конференции СФТИ при Томском госуниверситете, посвященной 70-летию образования института: 28сентября-2 октября 1998г. Тезисы докладов. - Томск: Изд-во СФТИ, 1998.-С. 8-9.

6. Горцев A.M., Паршина М.Е. Оценивание параметров альтернирующего потока событий в условиях "мертвого" времени //Известия вузов. Физика. -1999.-N4.-С.8-13.

7. Паршина М.Е. Численное решение уравнений метода моментов для альтернирующего потока событий в схеме с продлевающимся "мертвым" временем //Массовое обслуживание. Потоки, системы, сети: Материалы международной конференции "Современные математические методы исследования информационно-вычислительных сетей", 23-25 января 2001 г., Минск. Выпуск 16,-Минск: БГУ, 2001. - С. 166-171.

Апробация работы. Внедрение результатов работы.

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

- на третьей международной научно-технической конференции "Актуальные проблемы электронного приборостроения" (Новосибирск, 1996 г.);

- на международной конференции "Всесибирские чтения по математике и механике при Томском государственном университете " (Томск, 17-20 июня 1997 г.);

-на 14-ой Белорусской школе-семинаре по теории массового обслуживания (Минск, 1998 г.);

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

-на Международной конференции "Современные математические методы исследования информационно-вычислительных сетей" (Минск, 23-25 января 2001 г.).

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

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

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

1. Степанова Н. В., Терпугов А. Ф. Оценка интенсивности нестационарных эрланговых потоков. //Труды 1 Белорусской школы-семинара по массовому обслуживанию. Минск, 1985. - С. 142-143.

2. Терпугов А. Ф. Математическая статистика. — Томск: Изд-во ТГУ, 1974. -С. .

3. Тривоженко Б. Е. Выделение трендов интенсивности нестационарного пуассоновского потока событий сплайнами второго порядка. //Труды 5 Белорусской школы-семинара по массовому обслуживанию. Минск, 1989. -С. 121-122.

4. Ушаков И. А., Чернышев В. П. Оптимальное управление в многоканальной система массового обслуживания с несколькими потоками требований. //Изв. АН СССР. Техническая кибернетика. — 1976. — № 5. — С. 95-100.

5. Файнберг М. А., Файнберг Е. А. Управление в системах массового обслуживания. //Зарубежнаярадиоэлектроника. 1975. -№ 3. - С. 3-34.

6. Феллер В. Введение в теорию вероятностей и ее приложения. М.: Мир, 1984. - Т. 1 -528 с.

7. Харин Ю. С., Степанова М. Д. Практикум на ЭВМ по математической статистике. -Мн.: Изд-во "Университетское", 1987. 304 с.

8. Хинчин А. Я. Работы по математической теории массового обслуживания. -М.: Физматгиз, 1963.-235 с.

9. Шмырин И. С. Оптимальная оценка параметров потока событий с переключениями //Вестник ТГУ. 2000. - № 271. - С. 63-66.

10. Эльсгольц Л.Э. Дифферетщалъные уравнения и вариационное исчисление. -М.: Наука, 1969,- 424с.

11. Baba Yutaka A unified analysis to the queue length distribution in hf (k)/G/l/N and GI/M7(k)/G/l/N queues. //Sci. Repts Yokohama Nat. Univ. Sec. 1. 1996. - № 43. - P. 43-54.

12. Bodino G.A., Brambilla F. Teoria delle code. Milano, 1959. -219 p.

13. Combe M. Queueing models with dependence structures. Amsterdam: CWI, 1994.- 165 p.

14. Fisher R.A. On the mathematical foundations of theoretical statistics. II Proceedings of the Cambridge Philosophical Society, V.222, 1921. P.309.

15. Yandin M., Naor P. Queueing systems with a removable service station. //Oper. Res. Quart. 1963. - V.14. -№4. - P. 393-405.

16. Yandin M., Naor P. On queueing systems with variable service capacities. //Naval. Res. Logist. Quart. 1967. - V.14. -№ 1. - P. 43-53.