Введение к работе
Актуальность темы. Возникновение и последующее бурное
развитие информатики как самостоятельного фундаментального
научного направления было вызвано в последние десятилетия
практической деятельностью человека, связанной с применением
средств вычислительной техники. По мере усложнения и
совершенствования этих средств все более актуальным становится
глубокое аналитическое и численное исследование тех моделей,
которые составляют теоретическую основу информатики. При этом
широко используются математические методы, разработанные в
теории управления, теории вероятностей, математической статистике,
теории массового обслуживания, теории управляемых случайных
процессов и др. Очень часто практика управления сложными
вычислительными комплексами ставит перед необходимостью
решения задач, относящихся к компетенции теории массового
обслуживания и, в частности, задач, решаемых в рамках теории
управляемых систем массового обслуживания. Начиная с 70-х годов
нашего столетия получило интенсивное развитие совершенно новое
направление исследований, связанных с применением систем с
нетрадиционными дисциплинами обслуживания, обусловленными
особенностями алгоритмов управления в современных
вычислительных комплексах, например, в узлах сетей передачи данных и вычислительных систем ( см. список конференций и семинаров, на которых проводилась апробация данной работы ). Особый класс среди подобных систем обслуживания составляют системы, в которых входные потоки заявок являются конфликтными. На содержательном уровне конфликтность потоков означает, во-первых, невозможность объединения некоторых потоков, то есть снижения размерности модели, во-вторых, обслуживание заявок конфликтных потоков осуществляется в непересекающиеся интервалы времени, в-третьих (как правило), существование интервалов недоступности, в течение которых потоки не обслуживаются. Можно указать достаточно большое число приложений в различных областях практической деятельности, которые требуют использования систем алгоритмического управления конфликтными потоками. К ним относятся системы управления движением транспорта на перекрестках со сложной геометрией переезда, системы диспетчерского управления работой крупных аэропортов, системы управления сложными роботизированными технологическими процессами, системы обработки данных в вычислительных сетях, системы управления обработкой информации о поступающих пациентах в больших медицинских клинических центрах и т.п. В подобных системах можно указать на следующие их общие отличительные особенности:
а) все протекающие в них процессы имеют существенно
дискретный характер и могут рассматриваться либо на интервалах
времени, либо в моменты, порожденные некоторым точечным
случайным процессом;
б) обслуживающее устройство может иметь несколько
изменяющихся режимов работы, причем помимо функций по
обслуживанию заявок оно может исполнять также функции
переналадок, переключения режимов и управления поступающими
потоками;
в) структура некоторых элементов системы может изменяться в
процессе ее функционирования.
Значительный вклад в развитие теории управляемых систем массового обслуживания внесли работы Бронштейна О.И., Гнеденко Б.В., Башарина Г.П., Боровкова А.А., Климова Г.П., Коваленко И.Н., Королюка B.C., Рыкова В.В., Ушакова В.Г. и ряда зарубежных ученых, например, Джейсуола Н., Данна М., Клейнрока Л., Неутса М.Ф., Поттса Р. и других. Однако классические способы описания систем алгоритмического управления потоками приводят к весьма сложным математическим моделям, трудно поддающимся аналитическому исследованию ( см., например, Климов Г.П. Системы обслуживания с разделением времени I. // Теория вероятностей и ее применения.-1974.-Т. 19.-Вып.3.-стр. 558-576. ). Поэтому проблема разработки методов описания и анализа подобных систем является актуальной. Среди систем алгоритмического управления потоками заявок можно выделить класс систем, функционирующих в случайной среде, которая оказывает влияние на вероятностную структуру входных потоков. При этом в зависимости от состояния среды входные потоки могут представлять собой или потоки отдельных заявок или так называемые неординарные потоки (потоки пачек). Построение и анализ моделей таких систем также представляются весьма важными.
Цель работы. В данной работе изучаются два типа систем
управления конфликтными потоками заявок, формирующимися в
случайной среде, определяющей в динамике изменение их
вероятностной структуры. Цель исследования состояла в построении
математических моделей таких систем для двух классов алгоритмов
управления: циклического алгоритма и алгоритма с упреждением, а
также в установлении в терминах важнейших параметров входных
потоков и системы необходимых и достаточных условий
существования стационарного режима функционирования.
Аналитическое исследование при этом основывалось на
разработанных в нижегородской школе теории массового
обслуживания методах нелокального описания составляющих элементов системы, например, входных потоков и потоков насыщения. Кроме того, на имитационных моделях систем управления
конфликтными потоками проводилось экспериментальное исследование переходных процессов. Также путем имитационного моделирования изучалась проблема сходимости оценок среднего времени пребывания произвольной заявки в системе с увеличением времени наблюдения в зависимости от загрузки системы, наряду с этим определялся разброс значений указанных оценок при различных загрузках, и тем самым выявлялись некоторые общие закономерности в поведении оценок важнейших характеристик системы с изменением загрузки и параметров, определяющих поведение случайной среды.
Научная новизна. Впервые построены вероятностные модели систем управления конфликтными потоками заявок в условиях динамического изменения вероятностной структуры входных потоков. Для двух классов алгоритмов управления математические модели представлены в виде точечных случайных процессов с выделенной дискретной компонентой (меткой). Для дискретной компоненты доказано свойство марковости; для каждого алгоритма управления определена структура цепи Маркова; найдены рекуррентные соотношения для одномерных распределений, позволяющие найти все конечномерные распределения дискретной компоненты; получены необходимые и достаточные условия существования стационарного распределения. Экспериментально на имитационных моделях такого рода систем выявлены характерные особенности поведения оценок важнейших характеристик системы при изменении загрузки и вероятностной структуры поступающих потоков заявок. Предложены методы оценивания продолжительности переходного процесса в системе для разных загрузок и параметров случайной среды. Показано, что разброс оценок основных характеристик системы существенно зависит от ее загрузки и выбора параметров системы управления.
Практическая ценность. Исследование систем алгоритмического управления конфликтными потоками требований в случайной среде проводилось в рамках НИР "Изучение функционалов от случайных процессов в задачах построения статистических решающих правил, вероятностного представления решений дифференциальных и интегральных уравнений и массового обслуживания" ( № гос. регистрации 0191.10054234 ), "Построение и анализ нетрадиционных вероятностных моделей процессов обслуживания и адаптивного управления" (№ гос. регистрации 0191.0041837 ), "Анализ однородных алгоритмов управления конфликтными потоками в случайной среде" (№ гос. регистрации 0196.60012274), выполненных на кафедре прикладной теории вероятностей ННГУ и в лаборатории теории вероятностей и математической статистики НИИ прикладной математики и кибернетики при ННГУ. Результаты исследований использованы при выполнении хоздоговорной работы "Разработка
вероятностно-статистических методов построения, анализа и синтеза моделей конфликтных управляемых систем обслуживания" по программе "Университеты России" (номер темы 1.3.26, направление "Фундаментальные проблемы математики и механики", раздел "Вероятностно-статистический анализ").
Полученные в диссертационной работе результаты использованы в учебном процессе при чтении специальных курсов для студентов 3-5 курсов факультета ВМК ННГУ, специализирующихся на кафедре прикладной теории вероятностей. Эти результаты могут быть также полезны при проектировании и эксплуатации вычислительных систем и систем автоматического управления конфликтными потоками заявок, например, потоками транспорта на перекрестках улиц.
Апробация полученных результатов. Результаты
диссертационной работы включены в сборники тезисов докладов и трудов следующих конференций и семинаров:
1. Республиканская научная конференция "Математическое и
программное обеспечение анализа данных" (БГУ, Минск, 1990).
2. VII Белорусская зимняя школа-семинар "Сети связи и сети
ЭВМ как модели массового обслуживания" (Гродно, 1991).
3. IV Всесоюзное совещание "Распределенные
автоматизированные системы массового обслуживания" (Душанбе,
1991).
4. Всесоюзная конференция "Математическое и машинное
моделирование" (ВТИ, Воронеж, 1991).
-
Международная конференция "Компьютерный анализ данных и моделирование" (БГУ, Минск, 1995).
-
XI Белорусская Межгосударственная зимняя школа-семинар "Исследование сетей связи и компьютерных сетей методами теории массового обслуживания" (БГУ, Минск, 1995).
По теме диссертации опубликовано 10 работ, список которых приводится в конце автореферата.
Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы и приложения. Объем основного текста работы 150 машинописных страниц.
