Автореферат
диссертации на соискание ученой степени кандидата физико-математических наук
Многолинейные системы с широковещательным обслуживанием
Общая характеристика работы
Связь работы с крупными научными программами, темами
Результаты, представленные в данной работе, были получены в рамках выполнения следующих научных проектов:
? НИР «Разработка аналитических средств моделирования и оптимизации процессов передачи информации в сетях с технологией IP и мобильных сотовых сетях связи» в рамках государственной комплексной программы научных исследований «Научные основы информационных технологий и систем» («Инфотех») на 2006-2008 годы, номер госрегистрации 20061225.
? НИР «Разработка вероятностно-аналитического аппарата для моделирования и оптимизации процессов передачи и обработки информации в современных информационно-телекаммуникационных сетях» в рамках государственной комплексной программы научных исследований «Научные основы информационных технологий и систем» («Инфотех») на 2009-2010 годы, номер госрегистрации 20090555.
Цель и задачи исследования
Целью данной работы является разработка алгоритмов нахождения стационарного распределения вероятностей числа запросов и времени пребывания, а также получение характеристик производительности ряда СМО с широковещательным обслуживанием и коррелированными потоками и иллюстрация преимуществ широковещательного обслуживания.
Сформулированная цель достигается решением следующих задач:
1. Формализация в терминах цепи Маркова (ЦМ) процесса функционирования системы MAP/PH/N с широковещательным обслуживанием и ошибками в обслуживании, расчет стационарного распределения вероятностей состояний системы и времени пребывания в ней и алгоритмы для вычисления характеристик ее производительности, включая вероятность успешного обслуживания.
2. Формализация в терминах ЦМ процесса функционирования системы MAP/PH/N с управляемым широковещательным обслуживанием, расчет стационарного распределения вероятностей состояний системы и времени ожидания и пребывания в ней и алгоритмы для вычисления характеристик ее производительности, включая вероятность успешного обслуживания.
3. Формализация в терминах ЦМ процесса функционирования системы MAP/PH/N с широковещательным обслуживанием и поломками приборов, расчет стационарного распределения вероятностей состояний системы и времени ожидания в ней и алгоритмы для вычисления характеристик ее производительности, включая вероятность успешного обслуживания.
4. Формализация в терминах ЦМ процесса функционирования системы MAP/PH/N с широковещательным обслуживанием и разогревом приборов, расчет стационарного распределения вероятностей состояний системы и времени пребывания в ней и алгоритмы для вычисления характеристик ее производительности.
Объектом исследования являются СМО с широковещательным обслуживанием и коррелированными потоками и их аналоги с классической дисциплиной обслуживания. Предмет исследования - стационарные распределения вероятностей состояний и времени ожидания и пребывания и характеристики производительности исследуемых СМО.
Положения, выносимые на защиту
1. Условия эргодичности и алгоритмы для расчета стационарного распределения вероятностей состояний и времени пребывания, а также характеристик производительности системы MAP/PH/N с широковещательным обслуживанием и ошибками в обслуживании.
2. Условия эргодичности и алгоритмы для расчета стационарного распределения вероятностей состояний и времени ожидания и пребывания, а также характеристик производительности системы MAP/PH/N с управляемым широковещательным обслуживанием.
3. Условия эргодичности и алгоритмы для расчета стационарного распределения вероятностей состояний и времени ожидания, а также характеристик производительности системы MAP/PH/N с широковещательным обслуживанием и поломками приборов.
4. Условия эргодичности и алгоритмы для расчета стационарного распределения вероятностей состояний и времени пребывания, а также характеристик производительности системы MAP/PH/N с широковещательным обслуживанием и разогревом приборов.
Личный вклад соискателя
Диссертационная работа подготовлена самостоятельно автором и содержит его личный вклад в проведенных исследованиях. Роль научного руководителя доктора физико-математических наук профессора А.Н. Дудина состояла в постановке рассмотренных в диссертации проблем и анализе полученных результатов.
Апробация результатов диссертации
Основные результаты, вошедшие в диссертационную работу, прошли апробацию на следующих научных конференциях: 66-я, 67-я конференция студентов и аспирантов БГУ (Минск, май 2009, май 2010), 11-я, 12-я, 13-я международная научная конференция «Обработка и передача мультимедийной информации» (Джёнджу, Южная Корея, декабрь 2008, сентябрь 2009, февраль 2010), 20-я международная научная конференция «Очереди: потоки, системы, сети» (Минск, январь 2009), международная научная конференция-форум «Информационные Системы и Технологии» (Минск, ноябрь 2009), 3-я Мадридская международная конференция по теории массового обслуживания (Толедо, июнь 2010), 8-й международный семинар «EUROPT - 2010» по проблемам оптимизации (Авейро, Португалия, июль 2010).
Опубликованность результатов
Основные результаты диссертации опубликованы в 12 научных работах, из них 4 статьи в научных журналах, соответствующих п. 18 Положения о присуждении ученых степеней и присвоения ученых званий в Республике Беларусь (общим объемом 2.95 авторского листа), 6 статей в сборниках научных трудов и материалов конференций и 2 тезисов.
Структура и объем диссертации
Диссертационная работа состоит из введения, перечня условных обозначений, общей характеристики работы, 5 глав, заключения, библиографического списка. Полный объем диссертационной работы составляет 114 страниц, из них 20 рисунков занимают 14 страниц, 4 таблицы занимают 3 страницы, количество использованных библиографических источников составляет 78 наименований, включая собственные публикации автора (но 7 страницах).
Основное содержание работы
алгоритм марков производительность широковещательный
В первой главе приведен краткий обзор литературы по ТМО. Указаны основные направления и исследования и приведено описание процессов поступления и обслуживания запросов рассматриваемых в диссертации.
Во второй главе рассматривается модель, в которой приборы системы не являются абсолютно надежными и обслуживание запроса может осуществляться с ошибками. Прибор не выходит из строя. Просто с определенной вероятностью произвольный запрос будет обслужен в нем с ошибкой.
В пункте 2.1 рассматривается математическая модель и распределение числа запросов в системе с дисциплиной BC. На вход системы поступает MAP (Markov Arrival Process) поток запросов. Предполагаем, что время обслуживиния запроса прибором имеет распределение фазового типа, заданное ЦМ , с неприводимым представлением . В процессе обслуживания запроса может произойти ошибка. Время от момента начала обслуживания запроса до возникновения ошибки имеет распределение фазового типа с неприводимым представлением . Наступление ошибки не влечет прерывания обслуживания запроса. Только результат обслуживания будет неудовлетворительным.
Пусть , - число запросов в системе; , - состояние управляющего процесса MAP-потока поступления запросов; , - состояние управляющего процесса обслуживания в j-ом приборе, , в момент времени .
Рассматриваем ЦМ . Перенумеровываем состояния ЦМ в лексикографическом порядке.
Лемма 2.1 [6, с. 6, 7, с. 47] Инфинитезимальный генератор (ИГ) ЦМ , , имеет вид
. (1)
Ненулевые блоки ИГ определяются следующим образом:
, ,
, ,
где ,
.
Обозначим стационарные вероятности ЦМ как
(2)
, , .
Соответственно лексикографическому упорядочиванию, формируем векторы-строки из вероятностей состояний ЦМ, имеющих значение компоненты , .
Теорема 2.1 [6, с. 6, 7, с. 47] Стационарное распределение вероятностей , ЦМ , , существует тогда и только тогда, когда выполняется неравенство
(3)
где - средняя интенсивность входного потока, а - среднее время обслуживания. Векторы , вычисляются следующим образом:
, ,
где , ,
,
матрица является минимальным неотрицательным решением уравнения
, (4)
а вектор является единственным решением системы линейных алгебраических уравнений
, .
В пункте 2.2 рассматривается распределение времени пребывания запроса в системе с дисциплиной BC. Пусть - функция распределения (ФР) времени пребывания запроса в рассматриваемой системе и - её преобразование Лапласа-Стилтьеса (ПЛС): .
Теорема 2.2 [6, с. 7, 7, с. 48] ПЛС распределения времени пребывания запроса в рассматриваемой системе имеет вид
,
где
,
Лемма 2.3 [6, c. 7, 7, с. 49] Вероятность того, что ошибка не случится за время обслуживания запроса в приборе, вычисляется как
.
Теорема 2.3 [6, c. 7, 7, с. 49] Вероятность того, что произвольный запрос будет обслужен без ошибки, вычисляется по формуле
В пункте 2.3 рассматривается система с классической дисциплиной с целью последующего сравнения её с дисциплиной BC.
Обозначим ИГ ЦМ , , описывающей поведение системы при классической дисциплине. Её компоненты имеют тот же смысл, что и компоненты ЦМ , рассмотренной в пункте 2.1.
Утверждение 2.1 [6, с. 7] Генератор имеет трёхдиагональную блочную структуру: диагональными блоками генератора являются матрицы , поддиагональными блоками генератора являются матрицы , наддиагональными блоками генератора являются матрицы заданные формулами
.
В пункте 2.4 в графической форме приведены результаты численных экспериментов, подтверждающие эффективность дисциплины BC и её преимущества перед классической дисциплиной: возможность меньшего среднего времени пребывания и большей вероятности успешного обслуживания запроса.
В частности, даны рисунок 1 и рисунок 2, приведенные ниже.
дисциплина: 1 - BC; 2 - классическая
Рисунок 1. Зависимость среднего времени пребывания от средней интенсивности обслуживания при различных дисциплинах обслуживания
дисциплина: 1 - BC; 2 - классическая
Рисунок 2. Зависимость вероятности успешного обслуживания произвольного запроса от средней интенсивности обслуживания при различных дисциплинах обслуживания
В третьей главе рассматриваются две модификации дисциплины ВС. Обе они представляют собой гибрид дисциплины ВС и классической дисциплины обслуживания. Дисциплина, которую будем называть BCS (Broadcasting with Copying when the number of free servers is Small) состоит в следующем. Пусть i ? число занятых приборов в момент поступления запроса; j ? пороговое значение, . Если , то все свободные приборы будут обслуживать поступивший запрос (как при дисциплине BC), а если , то запрос обслуживается только одним прибором.
Дисциплина, которую будем называть BCL (Broadcasting with Copying when the number of free servers is Large) состоит в следующем. Если , то все свободные приборы будут обслуживать поступивший запрос, а если , то запрос обслуживается только одним прибором.
В пункте 3.1 рассматривается распределение числа запросов в системе с дисциплиной BCS.
Лемма 3.1 [1, с. 35] задает структуру ИГ ЦМ , , блоки которого выражаются через матрицы , , , , описанные выше и матрицы , .
Теорема 3.1 [1, с. 36] Стационарное распределение вероятностей , ЦМ , , существует тогда и только тогда, когда выполняется неравенство (3). Векторы , вычисляются следующим образом:
,
,,
где , ,
,
,,
,
,
матрица является минимальным неотрицательным решением уравнения вида (4), а вектор является единственным решением системы линейных алгебраических уравнений
, .
В пункте 3.2 рассматривается распределение времени ожидания, вероятность успешного обслуживания запроса в системе с дисциплиной BCS.
Теорема 3.2 [1, с. 39] ПЛС распределения времени ожидания запроса в рассматриваемой системе имеет вид