Анализ различных классов систем обслуживания с приоритетами тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Берговин Алексей Константинович

• Берговин Алексей Константинович
• кандидат наук
• 2024

Оглавление диссертации кандидат наук Берговин Алексей Константинович

Введение

Глава 1. Система АЯНМп,г|С|1|ж

1.1. Описание системы

1.2. Обозначения. Предварительные результаты

1.3. Основная теорема

1.4. Относительный приоритет

1.4.1. Система АШМп2|С|1|ж

1.4.2. Численный пример

1.5. Предельная теорема

1.5.1. Вспомогательные разложения

1.5.2. Основной результат

1.5.3. Численный пример

Глава 2. Система С1 |С|1|ж с профилактиками обслуживающего

прибора

2.1. Описание системы и обозначения

2.2. Математическая модель. Построение

2.3. Математическая модель. Решение

2.4. Распределение количества требований, поступивших во время профилактики

2.5. Основной результат

Глава 3. Система Мг|Сг|1|ж со смешанными приоритетами

3.1. Обозначения и определения

3.2. Распределение длины очереди. Модель №1

3.3. Распределение длины очереди. Модель №2

3.4. Предельная теорема для системы М^С^Щж

3.4.1. Описание системы

3.4.2. Вспомогательные разложения

3.4.3. Основной результат

Заключение

Список литературы

Введение

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

Актуальность темы.

Теория массового обслуживания (ТМО) посвящена построению и анализу вероятностных моделей как систем, так и сетей обслуживания. Работами, которые легли в основу данной теории считаются статьи Эрланга[13] и Йоханнсена [20], которые были опубликованы в начале ХХ века и посвящены построению математической модели станции телефонной связи. На протяжении всего этого времени ТМО непрерывно развивалась, появилось бесчисленное множество фундаментальных трудов [8, 19, 24, 27, 30, 39, 40, 42, 53-56, 58, 63], а области применения ее моделей достаточно быстро перестали ограничиваться только задачами телефонной связи. Приведем некоторые области применения моделей ТМО: коммуникационные и телекоммуникационные сети [12, 44], информационно-вычислительные сети [43], транспортные системы [29], страхование [52].

Образовалось много научных школ, как в России, так и за рубежом. В России значительно развили математическую ТМО работы таких ученых как: Л.Г. Афанасьева, Г.П. Башарин, А.А. Боровков, В.М. Вишневский, Б.В. Гне-денко, А.В. Зорин, И.Н. Коваленко, Г.П. Климов, А.Н. Моисеев, С.П. Моисеева, Е.В. Морозов, А.А. Назаров, Ю.В. Прохоров, Р.В. Разумчик, А.С. Румянцев, В.В. Рыков, А.Ф. Терпугов, В.Г. Ушаков, М.А. Федоткин, А.Я. Хинчин и многие другие. За рубежом известными специалистами в области ТМО являются: М.С. Бартлетт, А.Н. Дудин, Д. Кендалл, Л. Клейнрок, Д. Линди, М. Ньютс, К. Пальм, Л. Такач, Дж.Ф.С. Кингман, Т.Л. Саати и многие другие

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

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

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

Первостепенной особенностью телекоммуникационных сетей является коррелированный трафик, то есть интервалы между поступлениями пакетов данных (в терминах ТМО - заявок, требований) являются стохастически зависимыми, это было, например, показано в работах [14, 23]. Появилось множество работ [17, 18, 21, 24, 50, 51, 62], а также целые монографии [9, 44, 45], посвященные анализу таких входящих потоков. Одним из основных подходов к построению таких моделей является использование BMAP-потоков (Batch Markovian Arrival Process), которые, во-первых, содержат в себе, как частные случаи большинство классических потоков, а, во-вторых, позволяют конструировать входящие потоки сложной структуры (например, чтобы учесть все основные зависимости в реальном трафике). Но, к сожалению, нахождение вероятностных характеристик систем с BMAP-потоками осуществляется преимущественно с помощью численных методов. Поэтому, в данной диссертации в качестве модели коррелированного входящего потока будет использоваться модель авторегрессии первого порядка для выбора текущей интенсивности входящего потока, которая, как

показано, допускает аналитическое решение в классическом для ТМО виде.

Следующей особенностью телекоммуникационных и вычислительных сетей является то, что они функционируют непрерывно, в том смысле, что сервер (обслуживающее устройство в терминах ТМО) не отключают, в моменты кратковременного отсутствия трафика, тогда возникает вопрос о том, что происходит в сети в момент отсутствия трафика (нет заявок в системе в терминах ТМО). Ответ на этот вопрос зависит от особенностей использования данной сети, возможными решениями являются самодиагностика сети, передача некого второстепенного трафика. Одним из подходов к добавлению этой особенности в математическую модель является понятие профилактики (прогулок, каникул) обслуживающего прибора. Исследованию таких моделей посвящено немало статей и монографий, например, [4, 11, 26-28, 49, 61]. В данной диссертации будет рассматриваться приоритетная модель с профилактиками обслуживающего прибора с самыми общими предположениями на входящий поток и время обслуживания заявок.

Последней, но не по значимости, особенностью, которая будет рассмотрена в данной диссертации является наличие смешанных приоритетов в реальных сетях передачи информации. Прежде всего надо пояснить термин «смешанные приоритеты», так как он не является общепринятым, то исследователи в ТМО под ним могут понимать разные концепции. Вот некоторые из них: между приоритетными классами с близкими приоритетными индексами установлена дисциплина относительного приоритета, а для остальных дисциплина абсолютного приоритета [1]; а в [10] понимается, что при поступлении требования с некоторой заданной вероятностью выбирается дисциплина относительного приоритета, а, соответственно, с дополнительной вероятностью - абсолютного приоритета с обслуживанием заново. В данной же работе под этим термином будет пониматься возможность выбора приоритетной дисциплины между каждой парой классов. Будет рассмотрено две модели: 1) можно устанавливать дисциплины относительного приоритета и абсолютного с обслуживанием заново; 2) выби-

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

Кроме вышеперечисленного, нельзя не отметить, что в последние десятилетия имеет место стремительное распространение сетей связи и передачи информации, а также систем хранения и обработки больших массивов данных, поэтому объем передаваемого и обрабатываемого трафика вырос колоссально. По этой причине, такие системы являются высоконагруженными, что вызывает необходимость проводить дополнительный анализ таких систем, в так называемых условиях критической загрузки. В данной диссертационной работе для системы с коррелированным входящим потоком и для системы со смешанными приоритетами было исследовано поведение длины очереди в условиях критической загрузки. Характеристики системы с профилактиками обслуживающего прибора не исследовались при критической загрузке, в силу того, что в такой ситуации прибор не станет свободным, то есть не будет уходить на профилактики. Под критической загрузкой в данной работе понимается постановка предложенная в [57], когда одновременно время стремится к бесконечности, а загрузка системы к единичной. .

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

для прикладных специалистов.

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

Научная новизна. Все результаты полученные в данной диссертации являются новыми и состоят в следующем:

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

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

3. Найдены интегральные уравнения, которым удовлетворяют преобразования Лапласа совместной производящей функции количества требований в системе С1 |С|1|ж с профилактиками обслуживающего прибора в случае дисциплины относительного приоритета.

4. Найдены совместные распределение количества требований в системе

Мг|Сг|1|ж в случае смешанной приоритетной дисциплины для двух моделей. Модель №1: между каждой парой приоритетных классов можно выбрать одну из двух дисциплин - относительный приоритет или абсолютным с обслуживанием заново прерванного требования. Модель №2: между каждой парой приоритетных классов можно выбрать одну из двух

дисциплин - абсолютный приоритет с потерей или с обслуживанием заново прерванного требования.

5. Найдены предельные распределения количества требований наименее приоритетного класса в системе М^С^Щж для модели №1 описанной выше.

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

Основные положения, выносимые на защиту:

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

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

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

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

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

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

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

Апробация работы. Основные результаты работы докладывались автором на следующих конференциях [31-33, 35]:

1. Научная конференция «Тихоновские чтения 2022», МГУ имени М.В.Ломоносова, факультет ВМК, Москва, Россия, 24-29 октября 2022 г. Тема доклада: Приоритетная система С1 \С\1 с профилактиками обслуживающего прибора

2. Х-я международная молодежная научная конференция «Математическое и программное обеспечение информационных, технических и экономических систем». Секция: математическая теория телетрафика и теория массового обслуживания, Томск, Россия, 26-29 мая 2023 г.

Тема доклада: Приоритетная система обслуживания с гиперэкспоненциальным входящим потоком авторегрессионного типа

3. 26th International Conference on Distributed Computer and Communication Networks: Control, Computation, Communications, Москва, Россия, 25-29 сентября 2023 г.

Тема доклада: Приоритетная система обслуживания с профилактиками прибора в общих предположениях на управляющие последовательности

4. Научная конференция «Тихоновские чтения 2023», МГУ имени М.В.Ломоносова, факультет ВМК, Москва, Россия, 29 октября-3 ноября

2023 г.

Тема доклада: О двух моделях смешанных приоритетов в системах вида M\G\1

5. Информационные технологии и математическое моделирование (ИТММ-2023). Секция: математическая теория телетрафика и теория массового обслуживания. Томск, Россия, 4-9 декабря 2023 г.

Тема доклада: Предельное распределение длины очереди в системе с авторегрессионным входящим потоком в условиях критической загрузки

6. Научная конференция «Ломоносовские чтения 2024», МГУ имени М.В.Ломоносова, факультет ВМК, Москва, Россия, 20 марта - 3 апреля

2024 г.

Тема доклада: Асимптотическое распределение длины очереди в системе обслуживания со смешанной приоритетной дисциплиной

Также, автор неоднократно докладывал результаты научно-квалификационной работы на семинарах «Аналитические методы в теории массового обслуживания» (руководитель - доктор физико-математических наук, профессор Владимир Георгиевич Ушаков) и «Теория риска и смежные вопросы» (руководители - доктор физико-математических наук, профессор Виктор Юрьевич Королев,

доктор физико-математических наук, профессор Юрий Степанович Хохлов и доктор физико-математических наук, доцент Олег Владимирович Шестаков) кафедры математической статистики факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова.

Основой диссертации являются следующие статьи, входящие в перечень Web of Science, Scopus и RSCI [34, 36-38].

1. Берговин А.К., Ушаков В.Г. Система обслуживания с приоритетной дисциплиной без прерывания обслуживания // Вестн. Моск. уни-та. Сер. 15. Вычисл. матем. и киберн. 2018. № 3. С.24—29.

2. Берговин А.К. Приоритетная система с профилактиками обслуживающего прибора // Вестн. Моск. уни-та. Сер. 15. Вычисл. матем. и киберн. 2023. № 1. С.14—20.

3. Берговин А.К., Ушаков В.Г. Исследование систем обслуживания со смешанными приоритетами // Информатика и ее применения 2023. Т. 17 Вып. 2. С.57—61.

4. Берговин А.К. Длина очереди в системе с авторегрессионным гиперэкспоненциальным входящим потоком при критической загрузке // Вестн. Моск. уни-та. Сер. 15. Вычисл. матем. и киберн. 2023. № 4. С.9—16.

В статьях, написанных в соавторстве, вклад Ушакова В.Г. состоит в постановке задач. Все результаты, представленные в диссертации, получены автором лично.

Также, автор имеет публикации в сборниках трудов конференций:

1. Берговин А. К., Ушаков В. Г. Приоритетная система GI\G\1 с профилактиками обслуживающего прибора // Тезисы докладов научной конференции Тихоновские чтения (2022 г., МАКС Пресс, Москва, тезисы). — Москва: ООО МАКС Пресс, 2022. — С. 106-107.

2. Берговин А.К. Приоритетная система обслуживания с гиперэкспоненциальным входящим потоком авторегрессионного типа // Материалы X Международной молодежной научной конференции «Математическое и программное обеспечение информационных, технических и экономических систем». Т. 308 из Сер. Серия физико-математическая. — Томский государственный университет Томск: 2023. — С. 110-114.

3. Берговин А. К., Ушаков В. Г. О двух моделях смешанных приоритетов в системах вида М|С| 1// Тезисы докладов научной конференции Тихоновские чтения (2023 г., МАКС Пресс, Москва, тезисы). — Москва: ООО МАКС Пресс, 2023. — С. 94.

4. Берговин А. К., Ушаков В. Г. Предельное распределение длины очереди в системе с авторегрессионным входящим потоком в условиях критической загрузки // Информационные технологии и математическое моделирование (ИТММ-2023). — Т. 1 из Материалы XXII Международной конференции имени А. Ф. Терпугова 4-9 декабря 2023 г. — Издательство Томского государственного университета Томск: 2023. — С. 139-144.

5. Берговин А. К., Ушаков В. Г. Приоритетная система обслуживания с про-филактиками прибора в общих предположениях на управляющие последовательности // Распределенные компьютерные и телекоммуникационные сети: управление, вычисление, связи (ЭССК-2023). — материалы XXVI Междунар. научн. конфер, 25—29 сент. 2023 г., Москва. — ИПУ РАН Москва: 2023. — С. 56—62.

6. Берговин А. К., Ушаков В. Г. Асимптотическое распределение длины очереди в системе обслуживания со смешанной приоритетной дисциплиной // Тезисы докладов научной конференции Ломоносовские чтения (2024 г., МАКС Пресс, Москва, тезисы). — Москва: ООО МАКС Пресс, 2024. — С. 133-134.

Структура работы. Работа состоит из введения, основной части, состоящей из трех глав, заключения и списка литературы. Общий объем работы составляет 107 страниц.

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

Основная теорема: а) функции р{ъ,з) и р,^ {ъ,х,в),1 = 1,г, ] = 1,^, определяются по формулам:

^«) = + 7ГЗЙ £ £ {ъ, *) • 1 - - №^ ъ)))

{1 - P){P, ъ) ^ 1 мк{{p, ъ)){5 - мк{{p, ъ)))'

Л 7(к)1 рг]{ъ, X, в) = {1 - Вг{х)) —77-„ г ' -;-—е

к {г,в)_ -(8-^((р,ъ)))х

к=1 Цк {{P, ъ)) + % {1 - P{P, ъ))

где

7(те){ъ, 8) = ^Хр^ П[Мт{{р, ъ)) + а, {1 - р{р, ъ))]

N

am{{p, ъ)) .=

х у^ аеР(е{ъ, 0,5)

е=1 Мт{{P, ъ)) + ае{1 - p{p, ъ))

и 7г-т)(7, й), т = 1, N удовлетворяют соотношениям:

ЕГ (тЬ ч^г - Рг(8 - Цт((ф, %)))

Гг ЧМ--- =

г=1

(1 - P)(P, ъ) aт((p, ъ))

N

N

Y[[^т({p, ъ)) + ак(1 - p(p, г))]

сз аз 1з(ъ,5)

к=1

3=1

(Mт((P, ъ)) + а3 (1 - p(p, ъ)))

б) р0^ (й) определяются следующим образом:

1

N

РОЗ М =

1

1

X

X

■3 /=1 (1 - P)(P, 4)(5 - »1 (5)) из=п(аз - ап)

1 т-т ( м;(5)

ПО

+ % (1 - Р& =п \ 1 - Р& $) 1 - Р^ )

)

1

X

X

N

П

к=1

04(з) + аз(1 - р(р,^1))(^* (з) + ак(1 - р(р,*!))

1 - р(р,^*)

Предельная теорема: При т ^ ж существует предел:

т

Ит р (р1 • ь*{ й < *)=

е 2 (1у, а < 2,

Ч-е

3 у2 (1у--1

К

V 4-* 4

4— +'Шху1/ 4и

е у (1у, а = 2,

1 - е~тх, а > 2,

где

П) =

1 - а*Р*Ф*п

а*р*2У *

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

2

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

Основная теорема: функции pi(zi,х,y,s), г = 0,г, определяются следующими соотношениями:

рг(2г,х,у,8) = (1 - А(у))S),

где /¡(7,х,у, в), 1 = 0, г, — единственные решения уравнений:

]г(ъг,х,у, 8) = (р, z) J а(и - у)¡г(ъг,х,и, в)Си + (Сг(ъг,х,у, в), г = 0,г,

у

для = 1, :

х, у, в) = (1 - Вг(х))е-х ^кг(хг,у - х, в)-

с»

- ! а(у -у + х)Н{(г{,у, з)сСу ^ 1(у ^ х),

у-х

с»

с(0(ъ,х,у, в) = (1 -С (х)) к0(у -х, в) - (р,2) J а(у -у + х)к0(у, з)с(у ^х

- х

шт(х, у)

1 -С(х)^ -- ^ е- /(х - У) ч (V.

х 1(У ^ х) + 1 С(х) (1 - (р, 7)) / «1 ]

1 -С (х - г;)

В третьей главе была рассмотрена система с несколькими пуассонов-

скими входящими потоками и произвольным временем обслуживания требо-

ваний каждого потока. Заявки всех потоков обслуживаются одним прибором.

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

Основная теорема (модель №1): функция р(х, з) определяется по формуле:

г 1 - А I ^ + ^ - Е аз хз\

p{z, в) = ро(в) + V-7-^^--Pг{z, 0, s),

■ л 8 + V - У, аЗ ХЗ

г=1 -1

зФ Д

где

-1

Po(s) = ^S + а - Е а3Kjr(s)^

а Pi(z, 0, s) определяются из рекуррентных соотношений:

Е di (Kik (zk+\,... ,zr ,s),.. .,жкк (zk+i,... ,zr ,s),zk+i,.. .,zr ,s) pi(z, 0,s) =

i=k+l

/к r \

= 1 - l s + a аз ^зк (Zk+1, ...,zr ,s) - a3 z3 ) Po(s), k =1,r - 1.

V 3=1 3=k+l )

Основная теорема (модель №2): Функция p(z, s) определяется по фор-

муле:

в) = ро(в) + ^

(

1 - А| + а - XI

3=г

)

=1

й + а - ^ а^^

Рг(г,0, $),

=

где

Ро(5) = ( 5 + а - а3т]Г (з)

=1

а рг(ъ, 0, в) определяются из рекуррентных соотношений:

1

У^ Сг (т (^+1,..., , в),..., ткк (гк+1,..., гг, в), хк+1,..., гг, з) рг(г, 0, в) =

г=к+1

¡к г \

= 1 - I в + а а^к(¿к+1,..., , 5) - ^2 а323 I Ро(з), к = 1,г - 1.

\ 3=1 3=к+1 )

Предельная теорема: При т ^ с существует предел:

Нш Р ^ • Ьз — <х) =

т—>со

Я

;) < х)

V * 4=

Х

е 2 Су, а < 2,

1

у2(Су - -

е у с(у, а = 2,

V +и!*х\ 4

1 -е-гих, а > 2,

где

*

иГ =

1 - а*Д*1 - а£$1

а%и *

В заключении резюмируются полученные результаты и описываются возможные направления для дальнейших исследований

2

— 1Ю*х

Благодарности Автор диссертации выражает благодарность своему научному руководителю, доктору физико-математических наук, профессору Владимиру Георгиевичу Ушакову и всему коллективу кафедры математической статистики факультета вычислительной математики и кибернетики Московского государственного университета имени М.В. Ломоносова.

Глава 1

Система АКНМп^г|С|1

оо

1.1. Описание системы

Рассматривается однолинейная система массового обслуживания с ожиданием, в которую поступает поток требований следующей структуры. Интервал времени до поступления первого требования г1 и интервалы между поступлениями (п — 1) - го и п-го требований хп имеют показательное распределение со случайным параметром а(п\ п = 1, 2,.... Значение а(п выбирается непосредственно перед началом промежутка хп, причем Р(а(1) = а^) = с^, =

_ N

а3, I = ^ с3 > 0, ] = 1,^, Е сз = 1 и а(п) = £ • а(п—1) + (1 — 0 • Ь(п), где

3=1

Ь(п\п = 1, 2,... - последовательность независимых и независящих от последовательности а(п\п = 1, 2,... одинаково распределенных случайных величин, распределение которых такое же, как у а(1), а случайная величина £ не зависит от а(п и 6(п), п = 1, 2,... и имеет распределение Бернулли с вероятностью успеха .

Описанный входящий поток обладает следующими свойствами:

N

гп < ¿) = Е (1 —) =1

N N

гп < и, Хп+1 < ¿2) = (1 — р) ^ 9(1 — е—а^1) £ ск(1 — е—акЬ2) +

з=1 к=1

N

+ р^ Ск (1 — е—а^1 )(1 — е—а^2) =1

Е ^ = £ %' = £ I, согг(^, ^) = т (1— ^^пт2)

=1 =1

Следовательно, для любых д > 0,а > д существует рассматриваемый поток даже второго порядка ( N = 2), у которого математическое ожидание и дисперсия интервалов между поступлениями требований равны д и а2. Коэффициент корреляции двух соседних интервалов равен | - (^. А это означает, что при построении математических моделей появляется возможность не только «подогнать» первые два момента интервалов между поступлениями реального потока, но и учесть их зависимость.

В частности, при р = 0 входящий поток будет гиперэкспоненциальным. При р = 1 получается система, в которой в начальный момент времени случайно выбирается значение интенсивности из множества {а1,..., аN} с вероятностями с-[,..., сN ив дальнейшем система функционирует как система с пуассоновским входящим потоком с выбранной интенсивностью, такой случай далее рассматриваться не будем.

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

__г

рг, г = 1,г, рг > 0, рг = 1 независимо от остальных событий. Нали-

=1

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

Список литературы диссертационного исследования кандидат наук Берговин Алексей Константинович, 2024 год

Используя

N

Е

3=1

сзаз

Мк (р 1*1 + Р2^2 ) +а3 (1 - р(р 1*1 + Р2^2))

N

(1 - )( 1 1 + 2 2)

-(е(Х'2,

азР 0з(з)

=1

Мк (Р1^1 + Р2%2) + ^ (1 - р(р1%1 + р2^))

найдем, что

N

Е

сзаз1з (е_ир7,вРа)

1

_ Ма^г* + р2е-ир7) + ^(1 -р(р 12* + р2е-ир7)) (1 -р)^* + Р2е~ир7)

(вра - 1г* + р2е~ир1)) V —^-7. азР0](5) , ,-—

V г Рп^1 1 ;; ^ ^(ад* + Р2е~ир ) + а,(1 - р^г* + р2е~ир7))

N

1

1-

(V

2 и

- ■ V / I -

ар1рп - 1

*) Е

=1

Роз( ^ 1-

1-

N

1"(" - ^ *) (

)

N

Используя лемму 1.5 и тот факт, что Е пз = 1, получаем следующие разложе-

=1

ния:

при а < 2

при а = 2

при а > 2

1-

(

1 - - -

ар 2и

арфп - 1

1-

1

ар 2и

ар 1рп - 1

-фР

)

1 + + 4 зг/

25

1-

2 и 2- С 3- С

1 - 5 Р--Б-7 - фР

V арфц -1 у

из них следует утверждение леммы. Конец доказательства.

1

1

1

1

1

1

Лемма 1.8 Справедливо следующее асимптотическое разложение:

е-ир' - ß2(sра - т(р!Z* + р2е-ир')) = ( ß2lP2^

= <

apißn - 1 Р2

apißn - 1 р22

v apißii - 1

x

x

x

-s +

22

a2 22 2

2 -и2

и - ß2iS +

(apißii - 1)2

a2 22 ß21 2

(apißii - 1)2

+ o(p2), a < 2, + o(p2), a = 2,

и

a2p22ß2iv 2 и + --^-—и2

+ o(p2), a> 2.

(аргрг 1 - I)2 Доказательство:

Указанные соотношения непосредственно вытекают из результатов леммы 1.6

и того, что

е-ир' - ß2(sра - IH(Р!Z* + Р2в-ир)) =

2 2

1 у ,иР = 1 - ир' +—

- 1+ß2i

s р

2 и у

a ß 1 - 1

Конец доказательства. 1.5.2. Основной результат

фр2у

ß22 a 2 и у

2 _apißii - 1_

+о(р2у).

Вместо нахождения предела: lim Р р1 • L2[ — < х ) будем искать претите у \Ра J )

дел преобразование Лапласа по времени, затем сделаем обратное преобразование и найдем интересующее нас предельное распределение, значит, основной задачей становится поиск: lim рар(1, е-ирЛ, sра). В параграфе 1.4.1 было найдено преобразование Лапласа производящей функции числа требований второго

2

приоритетного класса, поэтому задача сводится к поиску следующего предела:

Ч^ •ЫЗра) + ^ •Й(е^ - 1} • рг(р 1 + *е^)(,р1 -Мр 1 + р2е^)) Х

X

l _ р—ир1

7^(1, е_ир7 ,spa )(1— е_ир 7 ß2(spa — ßl(Pl + р2 e_Ufß)) +

N

П [ßi(pi + Р2е_ир7) + ат(1 _p(pi + ^е_ир7))]

+ —-1-^-х

ai (рi + р2е_ир )

х (1, е_ир7,spa)

j=i ßi(Pi + Р2е_ир7) + а3(1 _p(pi + р2е_иР')) Учитывая, что lim pap0(spa) ^ 0 из леммы 1.5, ßi(pi+p2е_ир') = ар2ир1+о(р1).

Из леммы 1.1 для определения функций рк(р1г1 + р2г2), к = 1, N можно найти, что

N 1 N

а1(1) = П(-Рт(1)) = -гг—г П(ат(1 -р)),

2 а(1 _ р) i

т=2 х ' т= i

тогда

N N

п [ßi(pi + Р2е_ир1) +ат(1 _p(pi + Р2е_ир7))] П (ат(1 _р))

т i т i

lim--^-=-т-т-= а(1 _ р).

ai(p i + Р2е _ир7) ai(1) v F>

Таким образом, задача сводится к поиску следующего предела:

Ит I -£-гг (1,е-ир 7ра)+

\а2р2(1 -р)(р1 + р2е-иР7) /2 у Р 7

+пткка—р)] v_cjаjfj (1,е—ир 7,5 ра)_\

пт=2(_Мт(1)) а2Р2и ^ Hi(pi + Р2в_ир) + а^(1 _p(pi + ^е_ир7)) J '

Действуя аналогично лемме 1.7, получаем, что

lim ^V_^ fj(1^ ^_= 0 Va > 0.

а2р2и Hi(pi + Р2e_Ufl) + аj(1 _ р(рi + Р2е_ир1))

Тогда,

Ишрар(1, е"ир1 ,зра) — 11ш ^Ъ (1,е ^ ,3^)

а2р2 (1 - р)(р 1 + Р2е ~ир1)

= ИшПт=1(ат(1 - р)) ^ /9ар2е(е~ир'' , 0, й^) = Нш — V рар2е(е-^ , 0, 5 Л аЦ1)(1 -р)а2р2 ^ ар2 ^

и а 1

е .........

=1 2 =1

- Ит Ра^е~иР1 Ра)

р2а2 (1 - р)

Из определения функции (г1, г2, я) имеем

Ит Ра721}(6~иР1 ^Ра) -р2а2 (1 - р)

(р 121* + р2 е"ир1) е~ир1ра

— 1ХШ_-_1_-_X

р2а2а,1(р1х{ + р2е~ир 1 )[е-ир1 - А(зРа - Мр^! + р2е"ир1))]

N

х П Ме-ир1) +ат(1 - р(р12* + р2е-ир1 ))]х

т=1

— с3а3]3(е~ир/,вРа)

х£

■=1 н-1 (р 1^1 1 р-2^ • ) i аз

Р>1 (р 1^* + р2 е~ир1) + аj (1 - р(р 1^* + р2 е-ир1))

— Нш

(1 - ) Ра

х

р2а[е~ир1 - @2(зРа - (р\г* + р2е~ир1))]

N

X

Cjаjfj(г*, е-ир 1 ^Ра)

=1

№ (р1 2* + р2е"ир1) + а^ (1 - р(рх + р2 е-ир1))'

Отсюда, используя леммы 1.7 и 1.8, получаем, что

Нш Рар(1, е ир<, вРа) — <

5-1 +

5-1 +

а*р?2и

1 а

* * *

-1

, а < 2,

а*р2и

2у 1

1 - а*р*ф*11 1 + ут^

а*рХ 4 п-1 1 + --2 . и

1

, а

— 2,

1 - а*р \р\1

, а> 2.

Тогда, обращая преобразования Лапласа, получаем утверждение следующей теоремы.

Теорема 1.2: При т ^ то существует предел

т

11т Р рЛ •Ь2\ — <х) =

е 2 (у, а < 2,

1

*'<1у - -

Ж

V 4г;* 44

4г;* 44

е у (1у, а = 2,

1 - е~™х, а > 2,

где

П =

1 - а*р а 2 *

2

Следствие 1 из теоремы 1.2: Плотность распределения длины очереди при критической загрузке:

п • ехр

Г !*П2х2 "1

\ 4Г" Г

а < 2,

пе

Ж

_ 2 V*

е у (у + -— х

V 4«* 4

х ( ехр -(-/+ пх ^ | + ехр | + )

^ ехр -

2

а = 2,

п • ехр{-пх}, а > 2.

Следствие 2 из теоремы 1.2: Математическое ожидание длины очереди при критической загрузке:

V' V* Ж

2

— , при а < 2,

—, при а > 2.

Следствие 3 из теоремы 1.2: Дисперсия длины очереди при критической загрузке:

(2^ - 4)£

-г—, при а < 2

пу*и)2

, при а > 2.

иг

Замечание: математическое ожидание и дисперсия в случае а = 2 могут быть вычислены с использованием численных методов.

1.5.3. Численный пример

Для визуализации различий между предельными распределениями, полученных для разных а, рассмотрим поведение плотностей, математических ожиданий и дисперсий полученных предельных распределений при различных £. Рассмотрим систему АД^М2,2|С|1|то со следующими параметрами а1 = 1, а2 =

2, с\ = 0.35, С2 = 0.65, Ри = 0.5749, = 0.775,^2 = М22 = 1,Р = 0.5,р1 = 0.5,^2 = 0.5.

Рис. 1.4. 1 = 0.1

Рис. 1.5. 1 = 0.5

Рис. 1.6. 1 = 2.5

Из данных графиков видно, что при различных значениях £ расположение графиков плотностей предельных распределений относительно друг друга для раз-

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

Глава 2

Система а|С|1|с с профилактиками обслуживающего прибора

2.1. Описание системы и обозначения

Рассматривается однолинейная система обслуживания, в которую поступает рекуррентный поток требований с функцией распределения интервалов между поступлениями требований А(х). Поступающие требования разделяются на г приоритетных классов, р,1, ^ pi = 1 - вероятность того, что новое требо-

¡=1

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

Будем предполагать, что функции распределения А(х),Вг(х) и С(х) имеют плотности распределния а(х), Ь^х) и с(х) соответственно. Обозначим

с» с» с»

«(.) = / е-фУ* ДМ = / е-ШХ* Ф) = / е-•*,)*

0 0 0

с

а1 = J и • а(и)(и 0

Введем следующие случайные процессы: Ь(£) = (Ь1^),... ,ЬГ(£)), где Ьг(Ь) - число требований ¿-го класса в системе в

момент времени

г(£) = Е {0,1,..., г} - либо номер класса (1 ^ % ^ г), требование которого обслуживается в момент времени £ (если Ь(£) = 0), либо г(Ь) = 0, если в данный момент прибор находится на профилактике;

х(р) - время, прошедшее с начала обслуживания до момента £, если г(£) = 0, если ( ) = 0, то время, прошедшее с начала профилактики до момента ; у(£) - время, прошедшее с момента последнего поступления требования до момента .

Будем предполагать, что в момент начала наблюдения за системой (£ = 0) в ней нет требований, и с начала профилактики прибора прошло случайное время с плотностью /(х), а с последнего поступления требования случайное время с плотностью д(х) = . Также, положим, что требования ¿-го класса

имеют приоритет перед требованиями ^'-го класса при % < ]. Обозначим

с» с»

ф(8) = / е-и/(и)йи, ф^) = / е-ид(и)йи = —. ] ] «1 • 5

0 0

В сделанных предположениях случайный процесс (Ь(£), ъ(Ь), х(Ь), у{р)) является однородным марковским процессом. Положим

/ ч а(х) , ч ЬЛх) . ч с(х)

Ф) = л ч, т(х) = У ,, м(х) = ( )

1 -А(х)' /ну 1 -Вг(х) ^ 7 1 -С (х)'

п = (п1,... ,пг), данный вектор может быть нулевым только при г(£) = 0, в противном случае существует хотя бы одна положительная компонента.

д 2

рг(п,х,у,г) = дхдур(ь0) = п,х(г) < х,у(г) < у,ЭД = г),

оо

/с с

е-5* У • • • У г"1... ^рг(п, х, у, г)(И.

п П1=0 пг =0

2.2. Математическая модель. Построение.

Рассмотрим изменение состояний системы в интервале времени (р,1 + А): В случае если обслуживающее устройство находится на профилактике и не было поступлений требований в систему и текущий цикл профилактики не закончился уравнение имеет следующий вид:

Ро(п,х + А,у + А,£ + А) = Ро(и,х,у, Ь) • [1 - (и(у) + д(х))А] + о(А).

Если профилактика началась за время А, то она началась в следствии того, что не осталось требований в системе (1 слагаемое), либо до этого была профилактика и это новый цикл (2 слагаемое):

А

! Ро(п, и, у + А, г + А)(и = 0

= Щ0,..., 1,..., 0),х,у, ¿) ^(х)(хА + у Р0(0,х,у, ф(х)(хА + о(А). =1 0 0

Если во время профилактики за время А поступила заявка, то

А

J Р0(п, х + А,и,г + А)(и = Е^У Р0(п - 1 ,х,у, г)ы(у)((уА + о(А). 0 =1 0

Так как, мы условились считать, что наблюдение за системой начинается в момент профилактики и отсуствия заявок, то Р0(п,х,у, 0) = 5П,0/(х)д(у). В случае если обслуживающее устройство занято обслуживанием заявики -го приоритетного класса и за время А не было закончено обслуживание заявки и не было новых поступлений:

Рг(п, х + А,у + А, г + А) = Д(п, х, у, ¿)[1 - (и(у) + ^(х))А].

Если произошло обслуживание заявки какого-либо приоритетного класса или закончился цикл профилактики (а система оказалась не пустой):

А

J Е Рг(п,и,у + А, г + А) (и = 0 =1

Р0(п,х,у, £)д(х)(хА + / Р,;(п + 1i ,х,у, ¿) щ(х)(хА

0 =1 0

' гр 1 .Х- ,

-Е / Pi((0,..., 1,..., 0),х,у, ¿) г]г(х)((хА - Ро(0, х, у, ф(х)(хА + о(А).

=1 0

Если во время обслуживания заявки ¿-го приоритетного класса поступило требование какого-либо приоритетного класса в систему:

А

¡р,п,х + Л,и, « + Д)(и = £ I Pi(п - ^,х ,, (^Д + о(Д).

0 3=1 0

В силу того, что изначально в системе отсутствуют заявки, то р^п, х, у, 0) = 0. Устремляя А ^ 0, имеем

дpo(п,х,y, дpo(п,х,y, 0 дpo(п,х,y, ^ ( ( ( (

-^-+-дх-+-ду-= -(и(у) + х, У, ^

Ро(п, 0,у, ¿) = Е/ Pi((0,..., 1,..., 0),х,у, ¿) Г]г(х)(х + ^ Р0(0, х, у, ¿)д(х)(х, =1 0 0

Ро(п,х, 0, ¿) = Е Pi Ро (п - 1 ,х,у, г)у(у)(у, =1 0

p0(п,х,У, 0) = $и,о/(х)9(y),

для = 1, :

т + э/ + ( эу ' = + "'(х))д(п,х,у,

Г *

^Р8(п, 0,у, г)= Р0(п,х, у, г)ц(х)(1,х + У Рг(п + 1{,х,у, ¿)Т]г(х)йх~

г=1 0 г=1

t

У^ / Р^((0,..., 1,..., 0),х,у, ¿) Г){(х)йх — Р0(0,х,у, 1)ц(х)йх,

= 0

г 1

рг(n,х, 0, ^ = У / рг(п — 1 ,х,у, ^'=1 0

Рг(п,х,у, 0) = 0.

Переходя к производящим функциям и преобразованию Лапласа по времени, получим:

дР0 ^ в) + дРй{г^% $) = —(» + %) + ^(х))Р0(2,х,г/,6.) + /(х)5(г/), (2.1)

Г

р0(ъ, 0,у, в) = ^ е—81Рг((0,..., 1,..., 0),х,у, г) Г)г (х)(1х(И+

г= 0 0

+ е Р0(0,х,у, 1)ц(х)(1х(И.

00

Заметим, что из вида соотношения для р0(ъ, 0, у, в) следует, что оно не зависит от 7.

с

Po(z,х, 0, в) = (р,г) ^po(z,х,y, 8)и(у)с1 у.

0

Для 1 = 1, г:

дpг(z,х,y, в) дpг(z,х,y, в) ( ( ( ( -дх- + -ду- = —+ "(У) + 11г(х))Рг(7, х, у, в),

оо

Г 1

У Рг(7, 0,у, в) = I Р0(7,х,у, в)ц(х)(1х + ^ — [ рг(х,х,у, в) Т]г (х)(1х — ■ «У • «У

г=1 0 г=1 0

^ —О //П 1 П\ ™ _|Л._ I I ^ — &

Уу у е—^Рг((0,..., 1,..., 0),х, у, г) г]г(х)(1х<И—у у е—^Р0(0,х,у, г)ц(х)с1х<И, г=1 0 0 0 0

г

г

Pi(z,х, ° й) = Pi(z,х,y, з)р(у)(у.

0

Рассмотрим следующее интегральное преобразование:

д(х, х,п, з)= е

1 - (р,х) / ёшиа(и)(и -ыу-1 - щ)--P(z,х,У, в)((У.

(2.2)

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

д(1 (х, х, п, в) д х

1 - (р,х) / ешиа(и)(и

=

1 - А(У)

др(х, х, у, й) д х

( ,

тогда интегрируя данное выражение по частям, имеем:

1 - (р,х) Г еыиа(и)(и [ -ыу_0_ др(z,X,У, 5)

1 - А(У)

д

(у =

1 - (р,х) / ешиа(и)(и

= е~ыу-

1 - А(у)

P(z,X,У,

=0

оо

д_ дУ

1 - (р,х) / еыиа(и)(и

-ыу_0_

' 1 - А(у)

р(х, х, у, в)(1у.

оо

Учитывая, что

дУ

1 - (р,х) / ешиа(и)с(и -ыу_0_

' 1 - А(у)

р(х, х, у, в)(1у =

[ (р,х)а(у) ( ,

= -пд (г,х,п, й) -у ——^ ^ р( г ,х,у, з)ау+

00 1 - (р,х) / еыиа(и)(и

+ J и(у)е~ыу-1-0 л / ч- ■ р(х,х,у, з)(1у,

0

1 - А(у)

имеем

1 - (р,х) Г еыиа(и)(и /* _о_ дP(z,X,У, 'У

1 - А( )

д

(!у =

1 - (р,х) / ешаа(и)(и

=

1 - А(у)