Содержание к диссертации
Введение
Глава 1. Асимптотический анализ RQ-систем в условии большой загрузки 29
1.1 Исследование RQ-системы ММ 1 29
1.2. Исследование RQ-системы MGI1 марковизированием непрерывной компонентой 37
1.3. Исследование RQ-системы ММРРМ1 марковизированием дискретной компонентой 47
1.4. Исследование RQ-системы MMPPGI1 марковизированием двумя дополнительными компонентами 56
Резюме 68
Глава 2. Асимптотический анализ второго порядка RQ-систем в условии большой загрузки 70
2.1 Исследование RQ-системы ММ 1 70
2.2 Исследование RQ-системы MGI1 78
2.3 Исследование RQ-системы ММРРМ1 90
2.4 Исследование RQ-системы MMPPGI1 100
Резюме 114
Глава 3. Квазигеометрическая и гамма аппроксимации распределения вероятностей числа заявок в ИПВ в RQ-системах 116
3.1 Метод моментов для RQ-систем 116
3.1.1 Метод моментов для RQ-системы ММ 1 117
3.1.2 Метод моментов для RQ-системы ММРРМ1 122
3.2 Гамма аппроксимация распределения вероятностей числа заявок в ИПВ в RQ-системах 129
3.3 Квазигеометрическая аппроксимация распределения вероятностей числа заявок в ИПВ в RQ-системах 133
3.4 Сравнение квазигеометрической и гамма аппроксимаций 136
Резюме 138
Глава 4. Численные методы и комплекс проблемно-ориентированных программ 139
4.1 Численные методы и комплекс программ вычисления допредельных характеристик RQ-систем 139
4.1.1 Алгоритм вычисления распределения вероятностей числа заявок в ИПВ BRQ-CHCTeMaxMMlnMGIl 139
4.1.2 Численные методы вычисления распределения вероятностей числа заявок в ИПВ в RQ-системе ММРРМ 1 141
Рекуррентный алгоритм 142
Мегаматричный метод 145
4.2 Численная реализация метода асимптотического анализа первого порядка 147
4.3 Численная реализация метода асимптотического анализа второго порядка 149
4.4 Численная реализация квазигеометрической и гамма аппроксимаций 150
Резюме 153
Заключение 154
Список использованной литературы
- Исследование RQ-системы MGI1 марковизированием непрерывной компонентой
- Исследование RQ-системы MGI1
- Гамма аппроксимация распределения вероятностей числа заявок в ИПВ в RQ-системах
- Алгоритм вычисления распределения вероятностей числа заявок в ИПВ BRQ-CHCTeMaxMMlnMGIl
Исследование RQ-системы MGI1 марковизированием непрерывной компонентой
Рассмотрим (рисунок 1.3) однолинейную систему с ИПВ, на вход которой поступает простейший поток заявок с параметром X, а время обслуживания каждой заявки имеет произвольную функцию распределения В(х). Если поступившая заявка застает прибор свободным, то оно занимает его для обслуживания. Если прибор занят, то заявка переходит в ИПВ, где осуществляет случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром а. Из ИПВ после случайной задержки заявка вновь обращается обслуживающему прибору с повторной попыткой его захвата. Если прибор свободен, то заявка из ИПВ занимает его для обслуживания, в противном случае заявка мгновенно возвращается в источник повторных вызовов для реализации следующей задержки. 1, если прибор занят. Обозначим P{k{t)=0, i(t)=i}=P(0,i,i) - вероятность того, что прибор свободен в момент времени t и в источнике повторных вызовов находится / заявок; а P{k(t)=l, i(t)=i, z(t) z}=P(l,i,z,i) - вероятность того, что в момент времени t прибор занят, в источнике повторных вызовов находится / заявок и оставшееся время обслуживания меньше z.
Причем процесс \k\t\i\t),z(f)} изменения состояний данной системы во времени является марковским с переменным числом компонент. Тогда ставится задача нахождения распределения вероятностей числа заявок в источнике повторных вызовов такой системы. Для распределения вероятностей P(l,i,z,t), P(0,i,t) состояний рассматриваемой RQ-системы составим систему дифференциальных уравнений Колмогорова. dP(0,i,t) dP(l,i,0,t)
Решим полученную систему методом асимптотического анализа в условиях большой загрузки, то есть при ХЬ = рї 1 или при s -і- 0, где s = l-p 0 - бесконечно малая величина.
Введем обозначения u = w, H(0,U)=EG(W,), H(I,U,Z) = F(W,Z,E) . Тогда система (1.18) перепишется в виде:
Доказательство Доказательство теоремы состоит из последовательного вывода асимптотических уравнений и дальнейшего исследования системы полученных уравнений.
Из системы (1.19) выведем асимптотические уравнения следующим образом. Совершив предельный переход в (119) при s 0 и обозначив F(w,z) = \imF(w,z,s) и G(w) = HmG(w,s), получим:
Как уже говорилось, для получения вида асимптотической характеристической функции достаточно найти из системы (1.29) лишь функцию F(w). Процедуру ее нахождения реализуем в три этапа.
Таким образом, получили, что асимптотическая характеристическая функция h{u) в условиях большой загрузки для RQ-системы MGI1 имеет вид (1.22) характеристической функции гамма-распределения с параметрами вида (1.23).
Найденная характеристическая функция распределения числа заявок в ИПВ совпадает с результатом предельного перехода в формуле для допредельной характеристической функции, полученной Фалиным Г.И. [105], которая имеет вид: где к{и) = s(X - XeJU), a s(u) характеристическая функция закона обслуживания заявок на приборе. Для получения области применимости предлагаемого асимптотического метода проведем численное сравнение полученного асимптотического и допредельного распределений вероятностей числа заявок в ИПВ для различных значений параметров системы.
Критерием приемлемости результатов, как и в параграфе 1.1, будем считать условие А 0.05, где А - расстояние Колмогорова между распределениями, которое вычисляется по формуле [29]: A = max YD(v)-YP(v). Подробное описание алгоритмов вычисления асимптотического и допредельного распределений вероятностей, а также результатов их численного сравнения представлено в главе 4. В качестве примера рассмотрим случай, когда характеристическая функция закона обслуживания имеет вид гамма-распределения с параметрами аобс =Робс и робс =2. Тогда А = 1, Ь2=\.5.
Анализируя полученные результаты, можно утверждать, что предлагаемый в работе метод асимптотического анализа в условии большой загрузки дает хоро 47 шиє результаты аппроксимации допредельных распределений при загрузке р 0.95, если коэффициент вариации закона обслуживания не превышает 1.
Следовательно, метод может быть применен для исследования более сложных систем, для которых формула для допредельной характеристической функции не известна (например, система ММРРМ1 (п. 1.3) или система MMPPGI1 (п. 1.4)).
Рассмотрим (рисунок 1.5) однолинейную RQ-систему, на вход которой поступает ММРР-поток заявок (Markov Modulated Poisson Process), который является частным МАР-потока (Markovian Arrival Process) и описывается матрицами D0 иБь [121]
Обозначим n(t) - цепь Маркова, управляющая ММРР-потоком. Матрица ин-финитезимальных характеристик управляющего процесса n(t) равна Q = Dj + D0.
Матрица Т \ - диагональная матрица с элементами рХп, где Хп - условные интенсивности ММРР-потока, р - параметр, характеризующий загрузку системы (определен ниже), п = 1,2,...,N. Таким образом можно ввести матрицу . = diag{kn}, для которой выполняется: Dj = рХ. Вектор-строка R описывает стационарное распределение вероятностей состояний управляющего процесса n(t). Очевидно, что тогда интенсивность входящего потока будет равна X = R рХ Е, где Е - единичный вектор столбец.
Время обслуживания каждой заявки распределено по экспоненциальному закону с параметром ц, Если поступившая заявка застает прибор свободным, то оно занимает его для обслуживания. Если прибор занят, то заявка переходит в ИПВ, где осуществляет случайную задержку, продолжительность которой имеет экспоненциальное распределение с параметром а. Из ИПВ после случайной задержки заявка вновь обращается обслуживающему прибору с повторной попыткой его захвата. Если прибор свободен, то заявка из ИПВ занимает его для обслуживания, в противном случае заявка мгновенно возвращается в источник повторных вызовов для реализации следующей задержки.
Исследование RQ-системы MGI1
Предлагаемым асимптотическим методом исследованы следующие RQ-системы: с входящим простейшим потоком и экспоненциальным законом обслуживания заявок; с входящим простейшим потоком и произвольным законом обслуживания заявок; с входящим ММРР-потоком и экспоненциальным законом обслуживания заявок; с входящим ММРР-потоком и произвольным законом обслуживания заявок.
Доказано, что для всех рассмотренных RQ-систем асимптотическая характеристическая функция числа заявок в источнике повторных вызовов имеет вид характеристической функции гамма-распределения с параметрами, представленными в следующей таблице.
Кроме того, был проведен численный анализ влияния коэффициента вариации закона распределения вероятности длительности обслуживания заявок на приборе на расстояние Колмогорова между асимптотическим и точными распределениями.
Часть исследований, представленных в данной главе, проведена в рамках научных проектов: аналитической ведомственной целевой программы (АВЦП) «Развитие научного потенциала высшей школы (2009 - 2011 годы)» № 4761: «Разработка методов исследования немарковских систем массового обслуживания и их применение к сложным экономическим системам и компьютерным сетям связи» [60]. тематического плана государственного задания Министерства образования и науки РФ №8.4055.2011 «Разработка и исследование вероятностных, статистических и логических моделей компонентов интегрированных информационно-телекоммуникационных систем обработки, хранения, передачи и защиты информации» [61].
В предыдущей главе для исследования RQ-систем был предложен метод асимптотического анализа в условии большой загрузки. Однако, было показано, что этот метод имеет достаточно узкую область применимости: при загрузке р 0.95 расстояние Колмогорова А 0.05. В связи с этим в данной главе решается задача увеличения точности аппроксимации в виде получения асимптотики более высокого порядка.
Рассмотрим RQ-систему ММ1 (рисунок 1.1), описание которой приведено в главе 1.1. Для распределения вероятностей P(k,i,t) состояний рассматриваемой RQ-системы в главе 1.1 была составлена система дифференциальных уравнений Колмогорова (1.1), которая была записана в стационарном режиме (1.2). Далее был совершен переход к частичным характеристическим функциям и введены обозначения u = sw, Н(0,и) = sG(w,s), H(l,u) = F(w,s). Откуда была получена следующая система дифференциальных уравнений: Нетрудно показать, что полученный результат (2.4) совпадает с начальными членами разложения указанной функции в ряд Тейлора.
Асимптотическое распределение Р2(ї) вычисляется по формуле обратного преобразования Фурье. Подробное описание алгоритмов вычисления асимптотического (второго) распределения, а также сравнения этого распределения с допредельным и асимптотическим распределением первого порядка представлено в главе 4. Критерием приемлемости результатов, по прежнему, считаем условие А 0.05, где А - расстояние Колмогорова между распределениями, которое вычисляется по известной формуле [29]: В качестве примера рассмотрим случай, когда р = 0.8, a = l, Х = р, JLL = 1. На рисунке 2.1 изображены полученные распределения вероятностей D(i), P(i) и P2{i) числа заявок / в ИПВ. 0.15 Сравнение асимптотических (первого и второго порядков) и допредельного распределений при р = 0.8 Представим для наглядности результаты сравнения распределений для различных значений параметров системы в виде таблицы. Таблица 2.1- Расстояние Колмогорова между асимптотическими и точным распределениями в RQ-системе ММ Значения параметров системы Асимптотика первого порядка Асимптотика второго порядка
Таким образом, из таблицы 2.1 можно сделать вывод, что область применения метода асимптотического анализа (в виде получения асимптотики второго порядка) увеличивается в 4 раза: при загрузке р 0.8 расстояние Колмогорова А 0.05. Следовательно, целесообразно увеличить точность метода асимптотического анализа в условии большой загрузки для более сложных систем (MGI1, ММРРМ1, MMPPGI1), которые мы рассмотрим в следующих разделах. 2.2 Исследование RQ-системы MGI1
Рассмотрим RQ-системы MGI1 (рисунок 1.3). Для распределения вероятностей P(k,i,z,i) состояний рассматриваемой RQ-системы в главе 1.2 была составлена система дифференциальных уравнений Колмогорова (1.16), которая была записана в стационарном режиме (1.17). Далее был совершен переход к частичным характеристическим функциям и введены обозначения u = .w, H(0,U) = EG(W,E), H(l,u,z) = F(w,z,e) . Откуда была получена следующая система дифференциальных уравнений:
Гамма аппроксимация распределения вероятностей числа заявок в ИПВ в RQ-системах
В данной главе методом асимптотического анализа второго порядка в условии большой загрузки исследованы следующие системы массового обслуживания с повторными вызовами (RQ-системы): с входящим простейшим потоком и экс 115 поненциальным законом обслуживания заявок; с входящим простейшим потоком и произвольным законом обслуживания заявок; с входящим ММРР-потоком и экспоненциальным законом обслуживания заявок; с входящим ММРР-потоком и произвольным законом обслуживания заявок.
Проведен численный анализ показал, что область применения метода асимптотического анализа второго порядка в условии большой загрузки расширяется в 4 раза, по сравнению с методом асимптотического анализа первого порядка, то есть метод применим для значений загрузки р 0.8.
Часть исследований, представленных в данной главе, проведена в рамках научно-исследовательской работы в рамках проектной части государственного задания в сфере научной деятельности Министерства образования и науки РФ № 1.511.2014/К «Исследование математических моделей информационных потоков, компьютерных сетей, алгоритмов обработки и передачи данных» [62].
В главе 2 видно, что асимптотика второго порядка позволила расширить область применимости в 4 раза. В связи с этим встает вопрос об исследовании систем методом асимптотического анализа третьего (и выше) порядков. Однако, с помощью численного анализа было показано, что асимптотика третьего порядка существенно не расширяет области применимости метода.
Таким образом, возникает необходимость разработки других подходов, позволяющих применять результаты исследования для более широкого спектра значений загрузки системы. В качестве таких подходов в главе 3 предлагаются квазигеометрическая и гамма аппроксимации.
В главе 1 было показано, что асимптотическая в условии большой загрузки характеристическая функция иммет параметр формы а = 1 ч (3 больше едиицы. Так как параметр формы равен отношению квадрата первого момента к дисперсии, то вычисляя допредельные моменты, было показано, что величина а может принимать значения меньше единицы при некоторых знчаениях параметров RQ-системы. Таким образом, это позволяет надеятся на более высокую точность гамма аппроксимации при найденных допредельных значениях моментов.
Для построения аппроксимирующих распределений необходимо, чтобы были известны моменты искомых распределений. В связи с этим, в данном разделе предлагается провести исследование RQ-систем методом моментов с целью нахождения начальных моментов первого и второго порядков распределения вероятностей числа заявок в ИПВ.
Рассмотрим однолинейную RQ-систему ММ1 (рисунок 1.1). Для такой системы в разделе 1.1 была составлена следующая система дифференциальных уравнений для частичных характеристических функций:
В данном параграфе будем исследовать систему (3.1) с помощью метода моментов [49] для нахождения начальных моментов 1-го и 2-го порядков распределения вероятностей числа заявок в ИПВ. Метод моментов заключается в последовательном дифференцировании системы (3.1), записи уравнений при и = 0 и дальнейшем нахождении моментов нужного порядка.
Обозначим тк - среднее число заявок в ИПВ, когда прибор находится в состоянии к, тогда математическое ожидание числа заявок в ИПВ вычисляется как т0 + тх = т. При этом тк можно вычислить с помощью характеристической
Таким образом, мы получили формулы (3.26), (3.36), (3.37) и (3.43) для вычисления компонент математического ожидания и второго начального момента распределения числа заявок в ИПВ. Квазиточные моменты Для вычисления моментов распределения вероятностей числа заявок в ИПВ по формулам (3.26), (3.36), (3.37) и (3.43) необходимо знать вектора Ro и Ri в явном виде. В ходе вычислений же мы получили лишь соотношение (3.31):
Очевидно, что при дальнейшем использовании метода моментов к системе (3.23), то есть получении формул для моментов высших порядков, дополнительной информации о векторах Ro и Ri получить невозможно. А с помощью описанных выше уравнений однозначно вектора Ro и Ri определить нельзя. В связи вектора Ro и R\ найдем в виде следующего приближения:
Для определения точности описанного выше приближения для Ro и Rb проведем численное сравнение полученных моментов с точными (вычисленных с помощью численного алгоритма).
В следующих таблицах 3.1-3.2 представим значений математического ожидания и дисперсии для различных значений параметров системы (сверху - значение, вычисленное с помощью описанных выше формул, снизу - точное, полученное с помощью численного алгоритма).
Замечание. Численный алгоритм имеет существенный недостаток - невозможность вычислений характеристик системы при достаточно большой размерности системы линейных уравнений (1.36) (в частности, для числа заявок в ИПВ z 150). В таких случаях провести сравнение не представляется возможным, поэтому в таблице присутствуют пустые ячейки.
Алгоритм вычисления распределения вероятностей числа заявок в ИПВ BRQ-CHCTeMaxMMlnMGIl
В результате сравнения аппроксимирующих распределений с допредельными была составлена таблица 3.11 о выборе метода аппроксимации в зависимости от параметров системы, которая показала, что область применения предложенных методов квазигеометрической и гамма аппроксимации распределения вероятностей числа заявок в источнике повторных вызовов в RQ-системах покрывает почти весь спектр изменений значений параметров системы.
В данной главе предложены численные алгоритмы исследования систем с повторными вызовами (RQ-систем), а также программы реализующие методы, описанные в главах 1-3.
В разделе 4.1 предложены алгоритмы, вычисляющие допредельные распределения рассмотренных систем с повторными вызовами. В п. 4.1.1 представлен алгоритм вычисления распределения вероятностей числа заявок в ИПВ RQ-систем ММ1 и MGI1 с помощью известных допредельных распределений. В п. 4.1.2 предложены численные методы исследования RQ-системы ММРРМ1, а именно рекуррентный алгоритм и «мегаматричный метод». В разделе 4.2 описаны способы вычисления асимптотического распределения первого порядка и представлены результаты численной реализации алгоритмов. В разделе 4.3 описан алгоритм вычисления асимптотического распределения второго порядка и представлены результаты его численной реализации. В разделе 4.4 представлены алгоритмы численной реализации методов квазигеометрической и гамма аппроксимаций. Результаты этой главы представлены в публикациях [35, 36, 39, 42, 71].
В настоящей диссертации было проведено исследование однолинейных RQ-систем различной сложности: с входящими простейшим и ММРР-потоком заявок, с экспоненциальным и произвольным законами обслуживания заявок на приборе (т.е. RQ-системы ММ1, MGI1, ММРРМ1 и MMPPGI1).
Развит метод асимптотического анализа для исследования RQ-систем в условии большой загрузки. Кроме того, предложено его расширение в виде получения асимптотической характеристической функции второго порядка.
Предложены оригинальные подходы исследования RQ-систем, а именно: квазигеометрическая аппроксимации и гамма аппроксимации.
Получены формулы для стационарных характеристик исследуемых процессов, необходимые для анализа производительности и показателей производительности технических и эффективности экономических систем.
Полученные в диссертации результаты обобщают ранее известные, что существенно развивает теорию случайных процессов и теорию массового обслуживания. В первой главе рассматриваемые RQ-системы исследуются методом асим птотического анализа в условии большой загрузки. Доказано, что для всех рас сматриваемых RQ-систем асимптотическая характеристическая функция распре деления вероятностей числа заявок в источнике повторных вызовов имеет вид ха рактеристической функции гамма-распределения, параметры которой связаны со отношением а = 1 ч (3, где Ъ - среднее время обслуживания заявок. Сделаны зЬ выводы об области применимости метода на основе численного сравнения асимптотических и допредельных распределений. Во второй главе предлагается увеличение точности метода асимптотического анализа в условии большой загрузки в виде получения асимптотики более высокого порядка. Для каждой системы сформулированы и доказаны теоремы о виде асимптотической характеристической функции распределения вероятностей числа заявок в источнике повторных вызовов. Сделаны выводы об области применимости метода на основе численного сравнения асимптотических (второго порядка) и допредельных распределений.
В третьей главе предложены квазигеометрическая и гамма аппроксимации для исследования систем с повторными вызовами. В п. 3.1 методом моментов найдены первый и второй начальные моменты RQ-систем ММ1 и ММРРМ1. С помощью найденных моментов построены аппроксимирующие распределения и на основе численного сравнения с допредельными распределениями сделаны выводы об области применимости предлагаемых методов.
В четвертой главе предложены численные алгоритмы исследования RQ-систем в допредельной ситуации, а также алгоритмы и комплексы программ, реализующие метод асимптотического анализа в условии большой загрузки (первого и второго порядков) и квазигеометрическую и гамма аппроксимации.
