Содержание к диссертации
Введение
Глава 1. Регенерирующие процессы 12
1.1. Сильно регенерирующие процессы 13
1.1.1. Основные определения 13
1.1.2. Сильно регенерирующие процессы с дискретным временем 15
1.2. Слабая регенерация 16
1.3. Метод обновляющих событий 16
1.4. k-зависимые случайные величины 18
1.5. Регенерирующие процессы с непрерывным временем 19
1.6. Марковские цепи, возвратные по Харрису 21
1.7. Искусственная регенерация 26
1.7.1. Распределения с тяжелыми хвостами 27
1.7.2. Метод экспоненциального расщепления 31
1.7.3. Процессы обслуживания, имеющие распределения с тяжелыми хвостами 32
1.7.4. Оценка Хилла индекса v тяжести хвоста 34
Глава 2. Регенерирующие сети обслуживания 37
2.1. Описание систем и сетей обслуживания 37
2.2. Регенеративная структура сетевых процессов 39
2.2.1. Система GI/GI/m 39
2.2.2. Тандем 44
2.2.3. Тандемная сеть GI/GI/mi GI/mN . 46
2.2.4. Сеть типа Джексона 50
2.3.Условия регенерации 58
Глава 3. Статистические свойства регенерирующих сетей 62
3.1. Доверительное оценивание характеристик сильно регенерирующего процесса . 63
3.2. Доверительное оценивание на основе слабой регенерации 65
3.3. Методы повышения эффективности оценок 72
3.3.1. Метод одинаковых случайных чисел 74
3.3.2. Метод противоположных случайных чисел . 76
3.4. Методы повышения эффективности оценки среднего времени ожидания в сетях обслуживания 77
Глава 4. Результаты моделирования некоторых сетей обслуживания 85
4.1. Время доверительного оценивания с заданной точностью 87
4.1.1. Тандем GI/GI/1 -> -/GI/1 88
4.1.2. Тандемная сеть 93
4.2. Применение методов уменьшения дисперсии оценки в до верительном оценивании 102
Заключение 105
Литература 107
Приложение
- Слабая регенерация
- Искусственная регенерация
- Регенеративная структура сетевых процессов
- Методы повышения эффективности оценки среднего времени ожидания в сетях обслуживания
Введение к работе
Цель работы - разработка методов моделирования сетей обслуживания на основе слабой регенерации.
Системы и сети массового обслуживания очень распространены в реальной жизни. Типичным примером системы массового обслуживания являются автоматические телефонные станции, а вся телефонная сеть - это сеть массового обслуживания.
Система массового обслуживания (узел) характеризуется потоком заявок (клиентов), нуждающихся в обслуживании и числом каналов (приборов) обслуживания. Сеть обслуживания представляет собой объединение взаимодействующих систем массового обслуживания. Для исследования стационарных характеристик систем (сетей) массового обслуживания, главной целью которого является выбор наиболее разумной конфигурации системы (сети), обычно изучаются математические модели систем (сетей) массового обслуживания. Изучением таких моделей занимается теория массового обслуживания [4, 8, 12]. В дальнейшем, для краткости, под системой (сетью) массового обслуживания мы будем понимать их математические модели, как это принято в теории массового обслуживания.
Поскольку аналитические модели недостаточно разработаны и, кроме того, корреляционная структура значений процессов, протекающих в коммуникационных сетях является очень сложной, то возникает необходимость в разработке новых методов анализа поведения сетей обслуживания. В этой связи основным методом был выбран метод имитационного моделирования, ориентированный на определенную структуру зависимости значений процессов, а именно, на свойства регенерации. Регенерация означает, что в определенный момент времени траектория процесса перестает зависеть от предыстории процесса.
В данной работе рассматриваются в основном процессы с дискретным временем.
Актуальность тематики обусловлена интенсивным развитием коммуникационных сетей. Несмотря на быстрое развитие теории массового обслуживания, широко изучены только так называемые Марков-
ские сети, обладающие свойством мультипликативности [4, 8, 12]. Это свойство заключено в теореме Джексона и ее обобщениях, которые содержат достаточные условия мультипликативности предельного распределения векторного процесса очереди в узлах сети. Другими словами, при этих условиях существует предельное распределение процесса, равное произведению маргинальных распределений, относящихся к отдельным узлам. Такие сети, допускающие мультипликативность, называются сетями Джексона. Достаточным условием мультипликативности является обратимость во времени марковского процесса, которая выражается в форме уравнений детального баланса, связывающих вероятности перехода и предельное распределение данного процесса. При этом предельное распределение числа заявок в каждом узле можно выписать в явном виде.
Однако, поведение многих реальных систем нельзя описать марковскими процессами (входной поток не является пуассоновским, а время обслуживания имеет закон распределения, отличный от экспоненциального), кроме того, если сеть и можно описать марковским процессом, то он может быть очень сложным (большой размерности), что приводит к невозможности использования хорошо разработанных методов классической статистики [9]. Для анализа поведения таких сетей можно использовать регенеративный подход [68]. При определенных (весьма слабых) условиях существует предельное распределение регенерирующего процесса, при этом значения процесса делятся на циклы регенерации, которые между собой независимы. Моменты начала нового цикла, называются моментами регенерации [6, 7]. Эти моменты образуют вложенный процесс восстановления. Такая регенерация называется сильной или регенерацией по Смиту [7, 68]. Класс сильно регенерирующих процессов является хорошо изученным. Примерами таких процессов являются процессы, описывающие поведение многоканальных систем типа GI/GI/m [51].
Однако, чем сложнее сеть (чем больше у нее узлов или переходов между узлами), тем менее вероятным становится появление моментов сильной регенерации, и частота появления этих моментов падает. Это очень существенно для доверительного оценивания, т.к. время доверительного оценивания сокращается с ростом частоты моментов регенерации.
Существует более общая конструкция - слабая регенерация. А
именно, допускается зависимость значений процесса на циклах регенерации. При этом длины циклов по-прежнему остаются независимыми. Такая ситуация возможна в общих цепях Маркова, возвратных по Харрису. Это цепи с общим пространством состояний, для которых существует некоторое подмножество состояний, в которое сеть попадает бесконечное число раз с вероятностью единица и при выходе из этого подмножества цепь имеет одно и тоже распределение, не зависящее от конкретной точки подмножества.
Метод слабой регенерации базируется на методе обновляющих событий Боровкова [3]. Кроме того, он использует метод расщепления (при анализе цепей Маркова, возвратных по Харрису). Класс слабо регенерирующих процессов гораздо шире и до настоящего времени исследован недостаточно подробно. В применении к процессам обслуживания известны результаты только для многоканальных систем типа GI/GI/m и тандемов [10, 49]. Вышеуказанные системы и сети являются частными случаями ациклических сетей типа Джексона. Сеть типа Джексона представляет из себя несколько узлов обслуживания с входным потоком восстановления, каждый узел имеет несколько каналов обслуживания, заявки в узел поступают из других узлов и внешнего входного потока [24]. В данной работе выявлен класс событий, которые являются обновляющими для тандемной сети GI/GI/mi —>...-> /GI/rriN и ациклической сети типа Джексона, что позволяют строить моменты слабой регенерации.
Параллельно с теоретическими исследованиями регенеративный метод был успешно применен к статистическому анализу сетей обслуживания. Здесь надо отметить работы [5, 9, 38, 63, 6], где для исследования многоканальных систем типа GI/GI/m и тандемов используется подход, основанный лишь на сильной регенерации. В этой связи методом имитационного моделирования было исследовано поведение тан-демных сетей GI/GI/mi —>...—> -/GI/rriN, на основе и сильной, и слабой регенерации.
Важнейшими характеристиками любой сети обслуживания в стационарном режиме являются время, проведенное заявкой в очередях узлов при прохождении сети (время ожидания) и время пребывания заявки в сети, которое включает времена обслуживания в узлах. Поэтому важно уметь надежно оценить среднее время ожидания и среднее время пребывания в сети. С этой целью в работе уделено большое вни-
мание их доверительному оцениванию. Известно, что для построения доверительных интервалов по моментам сильной регенерации можно использовать центральную предельную теорему (ЦПТ) для независимых случайных величин, а для построения по моментам слабой регенерации можно применять ЦПТ для к-зависимых случайных величин [35].
В доверительном интервале, построенном по моментам слабой регенерации присутствуют оценки ковариаций. С целью уменьшения длины доверительных интервалов в данной работе предлагается использовать методы уменьшения дисперсии оценок, которые позволяют изменить знак оценки ковариаций. К ним относится, например, метод одинаковых случайных чисел, который при дополнительном условии монотонности рассматриваемых функций (обе функции возрастают или обе функции убывают) [60] приводит к положительной ковариаций между ними. В работе доказана теорема о положительной ковариаций функций неодинакового числа аргументов, полученных методом одинаковых случайных чисел. Время ожидания заявки в сети является функцией, зависящей от интервалов между приходами заявок в сеть и времен их обслуживания, причем число аргументов этой функции не одинаково на разных циклах регенерации, в том числе на соседних. Поэтому данная теорема обосновывает применимость метода одинаковых случайных чисел с целью уменьшения дисперсии оценки времени ожидания заявки в сети (и других подобных характеристик). Заметим, что в той же конструкции метод противоположных случайных чисел дает отрицательную ковариацию, что также может быть использовано для уменьшения дисперсии оценки [60].
В данной работе доказана теорема о том, что доверительные интервалы, построенные по моментам сильной и слабой регенерации асимптотически эквивалентны. При большом числе моментов сильной и слабой регенерации лучше использовать сильную регенерацию, вследствие простоты идентификации моментов регенерации. Однако в сетях большой размерности (при большом числе узлов) моменты сильной регенерации отсутствуют или очень редки, что значительно увеличивает время, затрачиваемое на построение доверительного интервала с заданной точностью.
В данной работе найдено условие для сети типа Джексона, при котором моменты сильной регенерации могут отстутствовать. Кроме
того, с увеличением размерности сети частота моментов сильной регенерации падает, а, следовательно, доверительное оценивание с заданной точностью на основе слабой регенерации более эффективно по затратам процессорного времени. Мы будем называть это условие условием эффективности слабой регенерации.
Для того, чтобы выяснить как влияют изменения вероятности сильной регенерации и числа узлов сети при выполнении условия эффективности слабой регнерации на время доверительного оценивания с заданной точностью были проведены имитационные эксперименты по моделированию тандемных сетей GI/GI/m\ —>...—»> -/GI/rriN. Кроме того, для того, чтобы оценить как изменяется длина доверительного интервала в результате применения методов одинаковых и противоположных случайных чисел на основе слабой регенерации были проведены имитационные эксперименты и получены доверительные интервалы для оценки среднего времени ожидания.
Кроме моментов слабой регенерации существуют искусственные моменты слабой регенерации. Они строятся методом расщепления, который заключается в том, что исходный процесс заменяется на эквивалентный ему процесс, обладающий свойством слабой регенерации. Причем, если исходный процесс в сети имеет распределение с тяжелым хвостом, то метод искусственной регенерации всегда применим.
На защиту выносятся получены следующие основные результаты:
Для сетей типа Джексона выявлен класс событий, являющихся обновляющими;
Доказано, что доверительные интервалы, построенные по моментам сильной регенерации и по моментам слабой регенерации асимптотически эквивалентны;
Показано, что с увеличением числа узлов в сети типа Джексона вероятность сильной регенерации уменьшается;
Доказана теорема о знаке ковариации для монотонных случайных функций с разным числом аргументов;
Установлена линейная зависимость между временем доверительного оценивания с заданной точностью по моментам сильной ре-
генерации и числом узлов сети при имитационном моделировании тандемных сетей;
Апробация работы. Основные результаты диссертации докладывались на международных конференциях и семинарах: Developments in Distributed Systems and Data Communications, Петрозаводск, май 1998г.; The 3th St.Petersburg Workshop on Simulation, июнь-июль 1998г.; Developments in Distributed Systems and Data Communications, Петрозаводск, май 1999г.; Probabilistic Analysis of Rare Events: Theory and Problems of Safety, Insurance and Ruin, Рига, июль 1999г.; Second International Conference on Stochastic Analysis, Осло, август 1999г.; Finnish school on Theory of Probability, Лахти, июнь 2000г.; The 4th St.Petersburg Workshop on Simulation, июнь-июль 2001г.; Developments in Distributed Systems and Data Communications, Петрозаводск, май 2002г. ;Finnish school on Theory of Probability, Лахти, июнь 2002г.; Applied stochastic models and information processes, Петрозаводск, сентябрь 2002г.
Работа частично поддержана грантом РФФИ № 01-07-90259.
Публикации работ. По теме диссертации опубликовано 6 работ [11, 14, 25, 53, 54, 55].
Структура работы. Работа содержит введение, 4 главы, заключение и приложение. Краткое содержание состоит в следующем.
Первая глава носит вспомогательный характер, в ней даны основные определения теории регенерирующих процессов, в том числе сильно регенерирующего процесса, слабо регенерирующего процесса и их свойств, приведен метод обновляющих событий для идентификации моментов слабой регенерации в сетях обслуживания.
Во второй главе рассматриваются основные свойства регенеративной структуры некоторых систем и сетей обслуживания ( многоканальной системы типа GI/GI/m и тандема).
Для тандемной сети GI/GI/m\ —>...—» -jGl/mjv и сети типа Джексона показано, что некоторое событие является обновляющим (теорема 1) и дана рекурсивная процедура построения моментов слабой регенерации с использованием этого события.
Для сети типа Джексона найдено достаточное условие, при котором с увеличением размерности сети вероятность сильной регенерации убывает, а, следовательно, частота моментов сильной регенерации падает.
В третьей главе приведены процедуры построения доверительных интервалов для различных характеристик, описывающих поведение сетей обслуживания по моментам сильной и слабой регенерации. Доказана теорема 2 о том, что доверительные интервалы, построенные по моментам сильной регенерации и по моментам слабой регенерации асимптотически эквивалентны. Доказаны теорема 6 о знаке ковариации между монотонными функциями с разным числом аргументов и теорема 7 о положительной ковариации в доверительном интервале для оценки среднего времени ожидания, построенном по моментам слабой регенерации на основе метода одинаковых случайных чисел.
В главе 4 приведены численные результаты имитационного моделирования тандемной сети GI/GI/m\ —»...-> -/GI/rriN' процессорное время (в секундах), необходимое для построения доверительных интервалов с заданной точностью по моментам сильной и слабой регенерации; длины доверительных интервалов, построенных методами слабой регенерации, одинаковых случайных чисел и противоположных случайных чисел. Процессорное время, необходимое для построения доверительного интервала включает время, затраченное на генерацию с.ч., необходимых для вычисления всех характеристик, описывающих рассматриваемый процесс (например, для вычисления времен обслуживания, входного потока, вычисления незавершенного времени обслуживания и времени ожидания заявки в сети). Установлены линейная зависимость между временем доверительного оценивания по моментам сильной регенерации и числом узлов сети.
Слабая регенерация
Чтобы расширить класс регенерирующих процессов можно рассмотреть слабо регенерирующие процессы (или регенерирующие процессы в широком смысле), которые допускают зависимость между циклами регенерации. Определение 2 [42]. Случайный процесс Z называется слабо регенерирующим (регенерирующим процессом в широком смысле), если для него выполнены следующие условия: (1) Распределение случайной пары Qpk(Z,(3) не зависит от к; (2) Распределение случайной пары Qpk(Z,l3) не зависит от {/%,., ад-Другими словами, в отличие от сильной регенерации, слабая регенерация допускает зависимость между циклами регенерации, так что св. Yj - зависимы, но (5 = {(Зп, 0} по-прежнему процесс восстановления, то есть длины циклов ctj, - н.о.р. св., для всех j 0. Часто можно ограничиться однозависимостью циклов регенерации (т.е. когда зависимы только два соседних цикла). Как и в случае сильной регенерации существует предельное распределение Ре процесса Z (см. [9] для дискретного случая и [17] для процесса с непрерывным временем). Для k-зависимых случайных величин существует аналог центральной предельной теоремы (см. 1.4). На основе этой теоремы можно построить доверительный интервал для оценки стационарной характеристики слабо регенерирующего процесса (см. 3.2.). Для построения моментов слабой регенерации можно использовать метод обновляющих событий А.А. Боровкова [36]. Пусть последовательность {Zn,n 0} определяется рекурсивным соотношением где н.о.р.с.в. Хп принимают значения на некотором пространстве состояний X, д\ : Е х Xі — Е - измеримая функция, где Хк = X х... х X. Последовательность {Хп} мы будем называть управляющей последовательностью.
Элементы {Хп} в теории массового обслуживания обычно описывают входной поток и интервалы обслуживания. Зафиксируем значение Zn = z, тогда значения Zn+Tn для любого т 0 можно вычислить с помощью z,Xn,... ,Xn+m-i, так Предположим, что существует такое целое число L 0 и измеримые подмножества В[Ь) єХх...хХ = Хьи множество С Є Е, что для любых значений z\,Z2 С и (xi,.. .,XL) Є B(L) выполняется следующее соотношение: Если С состоит только из одной точки, то равенство (1.3) выполняется для любых L и B{L). В противном случае, равенство (1.3) означает независимость от прошлого (до попадания в С) состояния процесса Z через L шагов после того, как процесс попал во множество состояний С, а управляющая последовательность Хп - во множество состояний B(L). Введем события Тогда моменты появления события Qn, образуют последовательность моментов регенерации {рп} (т.е. если событие Qn происходит, то мо мент времени n + L является моментом регенерации). Это вытекает из равенства (1.3) и того, что моменты регенерации являются моментами остановки относительно семейства сг-алгебр {Зп}» 3n = a(Zo,Xo,... ,Xn). Кроме того, пост-процесс {Zn+pk}n a не зависит от моментов регенерации {/?о, ,/}. Следовательно, процесс Z является слабо регенерирующим. Замечание. Поведение слабо регенерирующего процесса после момента регенерации зависит от L значений процесса на предыдущем цикле. При таком определении циклы регенерации являются однозави-симыми (т.е. зависимы только два соседних цикла). Событие Qn называется обновляющим событием [3]. Если событие fin происходит, то интервал [га, n + L) является периодом обновления, момент начала периода обновления обозначим jn = п.
В этом параграфе приводится аналог центральной предельной теоремы для к-зависимых случайных величин, которая далее используется для построения доверительных интервалов для различных характеристик процессов в сетях обслуживания, допускающих существование моментов слабой регенерации. Определение 3 [35]. Последовательность случайных величин Уї, І25 называется к-зависимой, если для любого целого j 1 подпоследовательности св. Yi,...,Yj и Yk+j+i, Yk+j+2, независимы. Определение 4 [13]. Последовательность св. Уї,1 ,... называется стационарной в узком смысле, если распределения последовательностей Y[, Y2,... и Yj+i, Yj+2,. . совпадают, для всех j 0. Теорема 3 [35]. Пусть Y\, Уг,... - стационарная в узком смысле последовательность к-зависимых случайных величин с конечной дисперсией, п обозначим Sn = 2 Yj. Тогда j=\ Рассмотрим стационарную в узком смысле последовательность независимых св. XL,X2, ... И сформируем новую св. Yj = XjXj+k- По следовательность Уі, У2,... образует стационарную последовательность k-зависимых случайных величин. Переформулируем теорему 3 для но вой последовательности УЇ, Уг, Обозначим и = M(1J), TOO = ГО(1}),о-о,г = cov(Yj,Yj+i) - математическое ожидание, дисперсию и ковариации соответственно (не зависят от j, что следует из стационарности последовательности). Заметим, что ООІ = 0 для всех і к. Нетрудно проверить, что MSn = пр, и для всех п к
Искусственная регенерация
Кроме слабой регенерации существует, так называемая, искусственная слабая регенерация, которая заключается в том, что исходный процесс заменяется на эквивалентный ему (по распределению) слабо регенерирующий процесс в соответствии с данным определением (см. 1.3). Важным частным случаем искусственной регенерации на основе метода расщепления (рассмотренной в 1.6 на примере цепи, возвратной по Харрису) является экспоненциальное расщепление. Этот метод применим для тех характеристик сетевых процессов, которые имеют распределения с тяжелыми хвостами. Далее дадим определение распределения с тяжелым хвостом, рассмотрим примеры таких распределений и методы оценки тяжести хвоста. Пусть F - функция распределения (ф.р.) неотрицательной случайной величины X. Определение 7 [41]. Функция распределения F имеет тяжелый хвост, если выполнено соотношение О, то есть для всех х хо график функции 1 — F(x) лежит выше, графика экспоненциальной функции е Хх (см. Рис. 1.2.). Если условие (1.10) не выполнено, то говорят, что ф.р. F имеет легкий хвост. К распределениям с легким хвостом относятся: экспоненциальное распределение, 7-распределение, гиперэкспоненциальное распределение. Для ф.р. с тяжелыми хвостами слраведливо следующее свойство [18]. Ниже рассмотрены два основных класса функций распределения с тяжелыми хвостами: субъэкспоненциальные ф.р. и ф.р., имеющие регулярно меняющийся хвост (т.е. хвост ф.р. является регулярно меняющейся функцией).
Первый класс ф.р. включает в себя второй. Субъэкспоненциальные распределения Среди распределений с тяжелыми хвостами выделяют подкласс S - семейство субъэкспоненциальных распределений. Пусть Xi,X2,... - н.о.р. неотрицательные св. с ф.р. F. Определение 8 [19]. Ф. p. F называется субъэкспоненциальной (F Є S), если выполняется следующее соотношение: Таким образом, сумма субъэкспоненциальных св. принимает большие значения в случае, если одно из слагаемых большое. Мы рассмотрели определение субъэкспоненциальной функции только на положительной оси (0, оо). Продолжим определение 8 для произвольных св. Ф.р. F на (—оо,+оо) называется субъэкспоненциальной, FG5, если 1 — F(x) 1 — G(a;) , при ж — +oo для некоторой G Є 5, определенной на (0,оо). Рассмотрим ф.р. ./о где - - математическое ожидание св. X с ф.р. F. (Fe - распределение стационарной задержки в теории восстановления). Заметим, что Fe не существует, если ШХ = оо. Соотношение (1.14) можно переписать в виде: Обозначим Xe св., соответствующую ф.р. Fe. Функция распределения Fe всегда имеет плотность на (0, оо) (1) Если F имеет тяжелый хвост, то Fe также имеет тяжелый хвост, причем более тяжелый, чем хвост F, т.е. (2) Если Fe имеет тяжелый хвост, то хвост Fe более тяжелый, чем хвост F и соотношение (1.15) выполняется. Таким образом, если одна из функций F или Fe имеет тяжелый хвост, то хвост Fe тяжелее, чем хвост F. Регулярно (правильно) меняющиеся хвосты Сначала введем понятие медленно меняющейся функции. Определение 9 [34]. Положительная функция L ( необязательно монотонная) называется медленно меняющейся, если L{t) Примером медленно меняющейся функции является логарифмическая функция Ln(x). Определение 10 [34]. Положительная функция и называется регулярно (правильно) меняющейся с индексом v (—оо v оо), если выполнено соотношение Будем говорить, что ф.р. F[x) имеет регулярно меняющийся хвост, если 1 — F{x) = x "L(x), v 0, где L(x) - медленно меняющаяся функция.
Утверждение 2 [34]. Пусть Fi(x), F2(x) имеют регулярно меняющиеся хвосты, т.е. 1 — Fi{x) = x vLi(x), где Li(x) - медленно меняющиеся функции. Тогда их свертка F = Fi F2 также имеет регулярно меняющийся хвост и Из утверждения 2 следует очень полезное следствие. Следствие 1. Если ф.р. F имеет регулярно меняющийся хвост, т.е. 1 — F(x) x vL{x), где L{x) - медленно меняющаяся функция, то l-F r\x) r-x-vL{x), (1.18) где F = F ... F - г-кратная свертка ф.р. F. Таким образом, если ф.р. F имеет регулярно меняющийся хвост, то F - субъэкспоненциаль-ная ф.р. Утверждение 3 [64]. Пусть F Є S. Тогда F имеет тяжелый хвост. Приведем примеры распределений с тяжелыми хвостами. (1) Распределение Вейбулла является субъэкспоненциальным; (2) Хвост распределения Парето относится к регулярно меняющимся; (3) Логнормальное распределение является субъэкспоненциальным, но хвост ф.р. не является регулярно меняющимся; (4) Логгамма-распределение имеет регулярно меняющийся хвост. О расщеплении функций распределения (ф.р.) уже говорилось выше в 1.6. В этом пункте речь пойдет об экспоненциальном расщеплении, которое возможно, если ф. р. имеет тяжелый хвост. Пусть Т - положительная св. с плотностью распределения f(x). Определение 11 [16]. Случайная величина Т называется экспоненциально расщепляемой, если существуют такие константы X О, г О и О q 1, что следующем виде: /Го, 12 1, _ / То, с вероятностью q; с вероятностью 1 — q, где св. Ті имеет плотность и To - имеет экспоненциальное распределение со сдвигом с параметром Л. Плотность То имеет вид Mt) = \\e-W\ для t т; для t т. Таким образом, плотность / расщепляется на две плотности f\ и /о» /о - сдвинутая экспонента: /( ) = «/o(t) + (l- z)/i(i), 0. Как видно из построения, распределения с тяжелыми хвостами удовлетворяют указанным выше условиям экспоненциального расщепления. В некоторых сетях с временем обслуживания, имеющим распределение с тяжелым хвостом, время ожидания заявки в сети и время прохождения заявкой сети также имеют тяжелый хвост, [22, 20]. Таким образом, для исследования сети обслуживания, имеющей времена обслуживания с тяжелым хвостом, можно применять метод экспоненциального расщепления, называемый искусственной регенерацией. Заметим, что чем тяжелее хвост распределения, тем больше площадь подграфика экспоненциальной функции, которую можно вписать в график плотности / (эта площадь равна q), и, следовательно, тем чаще появляются моменты искусственной регенерации (их частота растет вместе с вероятностью q).
Регенеративная структура сетевых процессов
Рассмотрим многоканальную систему типа GI/GI/m. Обозначим через {tn}n o - входной поток в систему, где tn - момент прихода п-й заявки в систему, to = 0, {sn}n i - н.о.р. времена обслуживания заявок, {тп = tn+i — tn}n i - н.о.р. интервалы между приходами заявок в систему, P(sn х) = В(х), Р(тп х) = А{х). Пусть Z = {Zn}n o - процесс, описывающий поведение системы в моменты времени {tn — 0} (например, размер очереди, время пребывания или время ожидания заявок в системе).
Предположим, что Zn = {0}, если в момент времени tn система пуста. Известно, [28] что для таких систем условие, является условием эргодичности (т.е. существует предельное распределение процесса {Zn}n o, не зависящее от начальных условий). Если условие эргодичности не выполнено, то очередь в системе неограниченно возрастает. Моменты сильной регенерации процесса Z естественно определить как Такая конструкция имеет смысл только если события {Zk = 0} действительно происходят, а это возможно при условии, что: В работе [17] доказываются следующие три утверждения: 1) Если условие (2.3) выполнено, то при условии (2.1) число моментов сильной регенерации бесконечно много с вероятностью единица, JP{Zf. = 0 для бесконечно многих к) = 1 и более того, процесс (3 положительно возвратен. 2) Если условие (2.1) выполнено, а условие (2.3) не выполнено, т.е. 8 — 0, то P(Zfc = 0) = 0 и моментов сильной регенерации не существует. 3) Если условие (2.3) выполнено, а условие эргодичности (2.1) не выполнено, то /Зп = со с вероятностью 1 для некоторого п, и тогда (Ai = Рп+1 = = 00). Смысл условия (2.3) состоит в том, что любая заявка может обслужиться в системе быстрее, чем в систему поступит следующая за ней, которая тогда застанет пустую систему. Если же потребовать выполнение более слабого условия которое вытекает из (2.1), то с вероятностью 1 некоторые заявки проходят систему "без столкновений" с другими заявками и система слабо регенерирует (точная конструкция требует дополнительных условий, см. (2.6)). Действительно, из (2.1) следует, что или из последнего неравенства вытекает условие (2.4). В качестве процесса Z рассмотрим процесс времени ожидания заявки в очереди. Пусть wn = (wn,...,Wn) - вектор Кифера-Вольфовица времен ожидания заявки с номером п в очереди системы, где Wn - время ожидания n-й заявки до освобождения і-го канала системы.
В векторе wn компоненты упорядочиваются по возрастанию для каждого п, поэтому номер канала не является фиксированным. Каналу на котором наименьшее время ожидания n-й заявки присваивается номер 1 и это время ожидания обозначается wn , каналу, на котором время ожидания - следующее по значению в порядке возрастания, присваивается номер 2 и т.д. где I = (1,0,..., 0); е = (1,1,...,) и R(x) - вектор, полученный из х упорядочиванием по возрастанию его компонент, т.е. R(xi,... ,жп) = Зафиксируем некоторый момент времени п. Определим событие: Если в момент времени п произошло событие fin , то время ожидания nm_! = 0, то есть в момент времени tn+m-i существует по крайней мере один свободный канал, и тогда этот момент времени можно считать моментом слабой регенерации [36] . Интервал [n, п + m — 1) является периодом обновления. В рассматриваемой системе его длина постоянна и равна m — 1. "Разделяющий барьер" а допускает зависимость только между соседними циклами. Действительно, если событие fin наступило, то вектор wn определяется только остаточными временами ожидания на каналах (начиная со второго), wn = (О,5г(п),..., Sm(n)), где Si{n) - незавершенное время обслуживания заявки с номером п на і-м канале. Причем, времена %(п) удовлетворяют соотношениям При этом, вектор времени ожидания в момент времени tn+m-i уже не зависит от ги ;, к п, но может зависеть от значений процесса {wn}n на периоде обновления. Действительно, Таким образом, если событие fin наступило, то процессы {wjfc к п} и {wfc+m-i» fc п} независимы. Пример [10]. В трехканальной системе GI/GI/3 моментом слабой регенерации является момент времени п + 2 ( L = 2), если в момент времени п произошло событие fin. На рис. 2.1 изображен пример, на котором на верхней горизонтальной оси откладывается время, три другие горизонтальные оси соответствуют каналам. Жирные горизонтальные стрелки соответствуют временам обслуживания, вертикальные стрелки - переходам между узлами, tn - уход n-й заявки из системы.
Методы повышения эффективности оценки среднего времени ожидания в сетях обслуживания
Сначала докажем теорему 6 о знаке ковариации для монотонных функций с разным числом аргументов. Теорема 6 Пусть Xi,..., Хп, Xn+i,..., Хп+р - независимые св., gi{xi,...,хп) и g2(xi,...,хп+р) - возрастающие функции по каждому аргументу. Тогда для любого целогор 0 cov{gi(Xlj..., Xn),g2{Xi,..., Хп, Xn+i,..., Хп+Р)) 0. (3.24) Доказательство: используем индукцию по п, предположив сначала р = 1. 1) п=1. Для всех х у выполняется соотношение т.к. функции д\ и д2 возрастают по переменной х\ = х. Следовательно, для любых двух с.в. X Y Таким образом, или Предположим, что X, Y, Х2 - независимые с.в, X uY одинаково распределены. Тогда 2) Предположим, что неравенство (3.24) верно для п = 1,..., к — 1 и рассмотрим независимые с.в. Х\,.. .Xk+i-
Обозначим X = (Xi,... ,Хк). Тогда из независимости с.в. следует, что М{91{Х)д2{Х,Хк+1)\Хк = хк) = M(9l{Xh ..., хк)д2{Хь ..., хк,Хк+1)). Из индуктивного предположения следует, что Возьмем математическое ожидание от обеих частей последнего неравенства, получим Последнее неравенство справедливо в силу того, что функции М(gi(X\Xk)) и M.{g2(X,Xk+i)\Xk) возрастают по Хк, а для п = 1 неравенство (3.24) Уже доказано. При р 1 доказательство проводится аналогично. Теорема доказана. Теперь теорему 6 применим к оценкам ковариаций и COV(YQ, ao)j входящим в доверительный интервал (3.5), построенный по моментам слабой регенерации для оценки среднего времени ожидания заявки в очереди одного узла типа GI/GI/m. Заметим, что оценки ковариаций COV(YQ,CXQ) И cov(Yo,a i) входят в доверительный интервал со знаком "минус", а оценка ковариаций COV(YQ,Y\) СО знаком "плюс". Поэтому, для сокращения длины доверительного интервала необходимо получить отрицательную оценку величины используя метод ОСЧ или метод ПСЧ. Рассмотрим вектор времени ожидания заявки с номером п в очереди в одном узле wn = (wn ,..., Wn ), где m - число каналов в данном узле (т 2), Wn - время ожидания заявки с номером п до освобождения і-го канала узла. Вектор времени ожидания wn заявки с номером п в очереди узла вычисляется по рекуррентной формуле где R - оператор упорядочивания по возрастанию (см. (2.5), глава 2), sn - время обслуживания n-й заявки в узле, тп - интервалы между приходами n-й и п + 1-й заявок в узел, тп = tn+\ — tn, tn - момент прихода заявки с номером п в узел. Заметим, что wn = p(sj, ТІ, г = 1,..., n — 1) - монотонная функция по каждой переменной (по sn возрастает, по тп убывает) [3]. Пусть В(х) и А{х) - функции распределения св. si и т\, соответственно. Обозначим, В 1(х), А г(х) - функции, обратные к ф.р. В(х) и А(х), соответственно. Теорема 7 Пусть Ui,U2,... - последовательность н.о.р. св., равномерно распределенных на [0, 1]. Предположим, что st- = Б-1(С/І) и 7 = .А-1 (/ї), і 1.
Предположим, что обновляющее событие щ , определенное формулой (2.6), произошло и Pi - первый момент слабой регенерации (fa = 0). Предположим, что 0 функция возрастающая по si и убывающая по т\. Тогда следующие три неравенства справедливы (см. обозначения п. 1.1.2): Доказательство: 1). Поскольку по условию торемы обновляющее событие fij произошло, то интервал [/ — m + 1,/) является периодом обновления (см. п. 2.2.1). Рассмотрим ковариацию Заметим, что в силу (2.5) каждая компонента вектора wn возрастает по sn и убывает по тп. Поэтому суммарное время ожидания заявки с номером п в узле Wn + + Wn является монотонной функцией по sn и тп. Обозначим Тогда Y0 = gi(rn, sn, n = 0,..., / - 1). С другой стороны, ао также является возрастающей функцией по sn, и убывающей по тп. Обозначим ао = д2{тт sn, п = 0,... ,/ — 1). Тогда Заметим, что функции А 1([/п) и Б-1(С/П) являются возрастающими, св. 1 — С/п также распределена равномерно на [О, 1], поэтому функции h\ и h2 возрастают по всем своим аргументам. Применим теорему 5 к ковариации между возрастающими функциями h\ и h2, получим (3.25). Поскольку no условию теоремы обновляющее событие Q произошло (см. (2.6)) и Pi - момент слабой регенерации, то а\ зависит
