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

Дальневосточная Государственная Академия Экономики и Управления

На правах рукописи

Писаренко Татьяна Алексеевна

ПОСТРОЕНИЕ И АНАЛИЗ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ДИФФУЗИОННОЙ ИНТЕНСИВНОСТЬЮ ВХОДНОГО ПОТОКА

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

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научные руководители:

Катрахов В.В. - доктор физико-математических наук, профессор

Головко Н.И. - кандидат технических наук, доцент

Владивосток -1999

Содержание

Введение..................................................................................5

Глава 1. Вывод уравнений для плотности диффузионного процесса и уравнений для характеристик СМО типа М / М/\/< Ыц < со, с диффузионной

интенсивностью входного потока ..................................15

§1. Уравнения для плотности диффузионного процесса

и СМО с нулевым коэффициентом сноса.................................15

п.1.1. Уравнения для плотности диффузионного процесса...........15

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

СМО типа М/М/1/#0 ..................................................20

п. 1.3. Уравнения для характеристик числа заявок СМО

типа М!М! 1/...........................................................25

п.1.4. Уравнения для СМО типа М/М/1 ...........................30

п.1.5. Уравнения для СМО типа М/М/1/0...........................30

§2. Уравнения для плотности диффузионного процесса и характеристик СМО типа МIМ11 / Ыд,

0 < Ы0 < оо, с диффузионной интенсивностью

входного потока с ненулевым коэффициентом сноса..................31

п.2.1. Уравнения для плотности диффузионного

процесса..........................................................................31

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

СМОтипаМ/М! 1/ЛГ0, 0 < <00..................................37

п.2.3. Уравнения для характеристик числа заявок СМО

типа М/М/1/7У0, 0 < 7У0 <оо.........................................45

п.2.4. Уравнения для СМО типа М/М/1...............................52

п.2.5. Уравнения для СМО типа М/М /1/0...........................52

Глава 2. СМО типа М/М /1/0 с диффузионной

интенсивностью входного потока ...................................54

§1. СМО типа М/М/1/0 с диффузионной интенсивностью входного потока с нулевым

коэффициентом сноса .................................................54

§2. СМО типа М/М/1/0 с диффузионной интенсивностью входного потока с ненулевым

коэффициентом сноса...........................................................62

§3. Численный анализ...........................................................70

Глава 3. Анализ СМО с конечным накопителем типа М/М /1 / Л^ с диффузионной интенсивностью

входного потока .........................................................77

§1. Матричный анализ СМО типа М/М /1 / с

нулевым коэффициентом сноса..............................................77

п.1.1. Теоремы существования и единственности решения краевой задачи относительно стационарных

характеристик ^^ (х), 0 < к < N..........................................77

п.1.2. Решение краевой задачи относительно

стационарных характеристик (х), 0 < к < N..................90

§2. Матричный анализ СМО типа М / М Ш N0 с

ненулевым коэффициентом сноса..........................................99

п.2.1. Функция и оператор Грина............................................99

п.2.2. Оценки оператора Грина в некоторых

функциональных пространствах .........................................103

п.2.3. Краевая задача для СМО с конечным

накопителем...................................................................105

п.2.4. О положительности характеристик числа заявок..............107

§3. Численный анализ СМО с конечным накопителем...............110

Заключение ...............................................................120

Библиографический список использованной литературы.....129

Введение

Актуальность проблемы. Развитие вычислительной техники и средств передачи информации привело к возникновению сетей ЭВМ, сетей передачи информации. В настоящее время активно проводятся исследования по проектированию и анализу функционирования таких сетей [11, 13, 32, 33, 34, 82]. Аналитическими моделями сети в целом и отдельных её элементов являются, соответственно, сети и системы массового обслуживания (СМО) [64, 68, 75]. При рассмотрении СМО задается ее структура, т.е. входной поток, обслуживание, комплекс обслуживающих приборов, емкость накопителя, и дисциплина обслуживания. Входной поток описывается совместной функцией распределения интервалов времени между соседними появлениями заявок , / > 1, а для ординарных рекуррентных потоков, когда интервалы гг- независимы и одинаково распределены, - функцией распределения А(т) = Р{т1 < Т, 1} . Таким образом, чтобы указать о какой именно СМО

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

А/В/т/М,

где А, В обозначают типы функций распределения для входного потока и обслуживания, т - количество обслуживающих приборов, N - емкость накопителя. А, В принимают значения из набора {М, (7, Н% и др.], где М -экспоненциальное распределение, G - распределение общего вида, Нк — гиперпоказательное распределение порядка Я.

Большинство авторов изучает системы массового обслуживания в предположении, что параметры СМО не изменяются со временем [31, 36, 48,

57, 62, 64, 68, 69, 89, 92]. Однако для реальных моделей (элементы сетей ЭВМ, вычислительных комплексов, сетей связи) это предположение не всегда выполняется. Параметры потоков сообщений в таких системах претерпевают с течением времени случайные или детерминированные изменения по следующим причинам:

- нестационарность входных потоков сети [16, 20, 33, 50, 59, 73, 108];

- изменение маршрутов сообщений, в силу чего на элементе сети возникают и исчезают потоки сообщений;

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

сети.

Кроме того, функционирование узлов локальных вычислительных сетей [32, 45], а также узлов глобальных вычислительных сетей типа ИНТЕРНЕТ (провайдерские узлы связи, шеЬ-серверы, передающие станции и т.д.) описывается СМО с параметрами, изменяющимися в случайные моменты времени [110].

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

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

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

тервале времени, не зависит от количества заявок, поступивших за другой временной интервал.

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

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

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

Анализ СМО с изменяющимися во времени параметрами является сложной математической задачей. Однако достаточно универсальных методов (как приближённых, так и численных), применяемых к расчёту характеристик СМО, пока не существует, поэтому есть необходимость в разработке таких методов хотя бы для определённых классов систем. В последнее время большое внимание уделяется изучению дважды стохастических (ДС) потоков. В работах [60, 61, 67] исследуются ДС потоки, интенсивность которых является процессом с независимыми приращениями или гауссовским про-

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

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

Для этого необходимо решить следующие задачи:

1. Построить модели указанных СМО, описываемые уравнениями относительно характеристик числа заявок в системах типа М/М/Х/Ыо , 0 < < 00, с конечным накопителем, М/М/1 с

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

2. Аналитически и численно изучить стационарные характеристики числа заявок в системе М / М1X1О с отказами с диффузионной интенсивностью входного потока.

3. Разработать матричный метод анализа СМО типа М / М/X/Ы0

с конечным накопителем с диффузионной интенсивностью входного потока.

Состояние проблемы. В настоящее время достаточно хорошо изучены СМО с пуассоновским простейшим входным потоком заявок, экспоненциальным обслуживанием с постоянными параметрами в стационарном режиме [47, 50, 57, 69, 89]. Основная сложность анализа СМО в нестационарном режиме, в особенности, если параметры СМО являются зависящими от времени детерминированными функциями, заключается в решении, как правило, большой или бесконечной системы дифференциальных уравнений с переменными коэффициентами.

Изучение СМО с зависящими от времени детерминированными интен-сивностями входящих потоков и обслуживающих приборов началось в середине 50-х годов работой Кларка [72]. В этой работе нестационарное распределение вероятностей состояния в СМО M(t)/M(t)/1/ со было выражено в явном виде через неизвестную функцию, которая находится численным решением интегрального уравнения. Впоследствии такая задача для этой же СМО была решена несколько другим методом Гешевым [14]. В дальнейшем появилось множество работ, посвященных анализу и расчёту нестационарных характеристик СМО с постоянными интенсивностями входного потока и обслуживания, в частности, исследовались СМО M / M /1 [21, 57, 92, 109, 108], M/M/1/N0 [33, 43, 50]. Далее анализ СМО с детерминированно изменяющимися параметрами шел в основном по двум направлениям: теоретическое исследование случайных процессов в СМО и разработка численных методов расчёта характеристик СМО. Довольно хорошо как с теоретической, так и с практической точки зрения исследованы СМО с пуассоновским входящим потоком, интенсивность которого есть периодическая функция времени [58, 93, 99, 100, 103]. Приближенные методы анализа СМО с детерминированно изменяющимися во времени параметрами, использующие зачастую эвристические предположения, рассматривались в работах [39, 40, 44]. Так, например, в работе [25] временной интервал изменения параметров СМО M(t) / M(î) /1 разбивался на подынтервалы с различной загрузкой и в каждом подынтервале проводился анализ характеристик СМО в предположении, что параметры в этом подынтервале изменяются медленно. В работе [59] автор приводит приближенное выражение для средней длины очереди в системе M{t) / M /1. В теоретическом плане исследованы системы M(t)l G(t)/\ [85]. Численные методы анализа СМО разработаны для систем Mit)/Mit)/1, Mit)/MH/N [91], Mit)/Mit)/s!N [95].

Многими авторами исследовались СМО с параметрами, изменяющимися во времени случайным образом. Для таких СМО в литературе принято название «СМО, функционирующие в случайной среде» [44, 53, 86, 110]. Как правило, рассматривались СМО, параметры которых постоянны в течение некоторого случайного времени, а затем мгновенно изменяются [58, 99, 101]. Набор значений параметров конечен, а процесс их переключения есть либо марковский [37, 43, 62], либо полумарковский [3, 9, 10, 36, 95, 98]. В работах [99, 101] исследовались СМО в предположении, что интенсивность потока и обслуживания могут принимать два значения, выбор которых осуществляется вероятностным образом на основе цепей Маркова. В [99] для системы с бесконечной очередью получено необходимое и достаточное условие эргодичности процесса, а для СМО с конечным накопителем получены выражения для некоторых показателей производительности СМО. В работе [87] расчет характеристик СМО сводится к решению матричных уравнений. Система, функционирующая в полумарковской среде, исследуется в работе [80], в предположении, что среда изменяется редко, т.е. длительность пребывания

среды в каждом состоянии имеет порядок , где £ - малый параметр. Получены формулы для коэффициента разложения распределения числа заявок в системе в ряд по параметру £. Анализ СМО со случайно изменяющейся интенсивностью входного потока проводился также в работах [18, 19, 20, 24]. Работы [29, 33, 38, 54, 56, 83] посвящены изучению скачкообразных процессов и СМО со скачкообразной интенсивностью входного потока. Росс высказал предположения о нижней границе вероятности потери требования в системе с ДС пуассоновским входным потоком [67].

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

для анализа стационарного режима приводится в работах [4, 16, 17, 52, 70, 73, 79, 99] при исследовании виртуального времени ожидания, времени до первого переполнения системы. Исследование диффузионной аппроксимации в нестационарном режиме для расчета характеристик числа заявок и времени ожидания заявками начала обслуживания в различных СМО приводится в работах [4, 90]. Изучение диффузионных процессов проводится в работах [8, 46, 55, 63]. Работы [2, 65, 66, 113] посвящены анализу уравнений Фоккера-Планка для плотности диффузионного процесса при различных типах граничных условий.

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

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

Вторая глава содержит анализ СМО типа МIМ! 1/0 с отказами с диффузионной интенсивностью входного потока. В первом параграфе доказаны теоремы существования и единственности решения краевой задачи относительно стационарных характеристик числа заявок и найдены стационарные характеристики числа заявок в системе с нулевым коэффициентом сноса. Второй параграф содержит решение краевой задачи относительно стационарных характеристик числа заявок в системе с отказами с ненулевым коэффициентом сноса. В третьем параграфе проведен численный анализ СМО с отказами.

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