Дипломная работа: Базовый процесс обработки вызовов
Рисунок 3.1– Иллюстрация поведения полумарковского процесса
Из приведенного определения следует, что если игнорировать случайный характер времени ожидания и интересоваться только моментами перехода, то процесс будет представлять собой однородную цепь Маркова (или вложенным марковским процессом). Однако при учете пребывания процесса в разных состояниях в течении случайного отрезка времени процесс не будет удовлетворять уравнению Маркова (если не все времена ожидания распределены экспоненциально). Следовательно, процесс является марковским только в моменты перехода. Сказанное оправдывает название «полумарковский процесс» или «полумарковская цепь».
При заданном начальном состоянии дальнейшее поведение полумарковского процесса (полумарковской цепи) полностью определяется матрицей вероятностей перехода , , , и матрицей функций распределения или (для непрерывных случайных величин ) матрицей плотностей вероятностей [17].
В рамках исследований полумарковских процессов с позиций теории массового обслуживания наибольший интерес представляет анализ взаимосвязи времени достижения и времени пребывания в состояниях полумарковского процесса. Согласно [16] данный анализ основывается на реализации элементарного процесса чистой гибели. В качестве примера рассмотрим систему , т.е. однолинейную систему массового обслуживания с ожиданием (буфером неограниченной емкости), в которую поступает простейший поток запросов (вызовов) интенсивности , а время обслуживания запросов (вызовов) имеет показательное распределение с параметром .
Исследуя поведение этой системы, можно установить, что случайный процесс – число вызовов в системе в момент – является процессом гибели и размножения с вероятностью равной [16]:
, . (3.3)
Анализ данной системы в рамках элементарного процесса чистой гибели основан на исследовании соответствующего графа перехода из одного состояния в другое. Простейший граф перехода имеет вид, показанный на рис. 3.2.
Рисунок 3.2 – Граф переходов элементарного процесса чистой гибели
Обозначим через , , вероятность пребывания процесса в состоянии с номером , а через функцию распределения времени первого достижения процессом состояния с номером . Тогда между этими функциями можно установить следующие зависимости:
, .
Подставляя эти выражения в условие формировки получим
. (3.4)
Следовательно, в рассматриваемом элементарном процессе чистой гибели вероятность пребывания процесса в промежуточном состоянии оказывается равной разности функций распределения времени первого попадания процесса в это состояние и времени попадания в следующее состояние. Добавляя и вычитая в правой части уравнения (3.4), затем помножив полученное выражение на и про интегрировав сначала по в бесконечных пределах, а затем по частям, получим [18]
, (3.5)
где – -й начальный момент распределения случайной величины времени попадания процесса в -е состояние . В частности, из формулы (3.5) видно. Что при
. (3.6)
В результате находим, что площадь под кривой числено равна разности разных средних времен попадания процесса в состояния 2 и 1, а интегральная мера численно равна среднему времени, проведенному процессом в состоянии единицы [18].
Физический смысл полученного результата можно пояснить следующим образом. Обозначим через случайный момент времени попадания процесса в состояние , а через длительность пребывания процесса в этом состоянии. Тогда для процесса с графом переходов на рис. 3.2, можно составить следующее уравнение баланса времени:
. (3.7)
Возведя выражение (3.21) в квадрат и применив операцию математического ожидания, учитывая при этом независимость случайных величин и получим аналогичное (3.19) выражение для расчета интегральных мер. Так при находим
.
Аналогичным образом, возводя уравнение (3.7) в степень всякий раз будем получать выражения для расчета интегральных мер вида через начальные моменты случайной длительности пребывания процесса в состоянии единицы и первого попадания в нее.
В результате определяется полный набор интегральных мер вида , с помощью которого можно судить о поведении функции .
3.2 Аналитические решения для простейших полумарковских процессов
Описание поведения систем массового обслуживания с помощью распределений моментов первого, второго и последующих достижений системой того или иного состояния, показанных на примере элементарного процесса чистой гибели, оказывается очень полезным в целом ряде практических исследований. Поэтому целесообразно рассмотреть примеры полумарковских процессов, для которых возможно получение подобных результатов в аналитической форме или в виде эффективных вычислительных процедур.
Для начала рассмотрим простейших процесс, имеющий только два состояния (рис. 3.3). Обозначим через функцию плотности распределения времени пребывания процесса в состоянии 0, а через – в состоянии 1.
Рисунок 3.3 – Простейший процесс
Соответственно и их преобразования Лапласа. В соответствии с [16], преобразованием Лапласа распределения будем называть функцию , определяемую как:
. (3.8)
Если чисто мнимая переменная, преобразование Лапласа совпадает с характеристической функцией . Областью определения функции обычно считается правая полуплоскость комплексной плоскости. Однако, без существенного ограничения сущности, в рамках проводимого анализа можно рассматривать как действительное положительное число.
Состояние процесса, приведенного на рис. 3.3 опишем с помощью функции распределения момента -го попадания процесса в -ю вершину: . Тогда, учитывая независимость времен пребывания процесса в вершинах 0 и 1, рассматриваемая последовательность переходов будет иметь вид
, (3.9)
где – преобразование Лапласа функции .
На основании этих соотношений находят разнообразные характеристики процесса. Так вероятность пребывания процесса в нулевой вершине может быть определена из условия
. (3.10)
Применяя к выражению (3.10) преобразование Лапласа и используя формулы (3.9), получаем
. (3.11)
Если в момент процесс находится в нулевой вершине, то и формула (3.11) принимает вид
. (3.12)
Определение разложения в ряд функции делает удобным оценку переходного режима.
Увеличим число вершин графа на единицу (рис. 3.4.). Заметим, что в этом случае процесс блужданий относительно нулевой вершины может быть описан с помощью некоторого эквивалентного процесса, соответствующего переходам на вспомогательном графе изображенном на рисунке 3.5а.
Рисунок 3.4 – Полумарковский процесс с трема состояниями
Рисунок 3.5 – Эквивалентные графы для исследования: а) блужданий относительно нулевого состояния; б) возврата в нулевое состояния; в) блужданий относительно промежуточного состояния
Обозначим через плотность вероятности времени первого перехода процесса из группы состояний {1,2} в нулевое состояние при начале блужданий из состояний 1. Тогда
. (3.13)
Определим функцию . Для этого воспользуемся формулами (3.12), записанными для графа, изображенного на рисунке 3.5б:
;
, ,
где , преобразования Лапласа дефектных случайных величин времени, проводимого процессом в состоянии 1 перед переходом соответственно в состоянии 0 и 2.
С помощью последних выражений находим преобразование Лапласа распределения времени первого попадания процесса в состояние А для графа, изображенного на рис 3.5б
.
Состояние в общем случае описывается уравнением вида
, (3.14)
где – некоторый линейный оператор.
Это уравнение описывает еще одно общее и важное свойство марковских процессов, для которых эволюция вероятности перехода . Заметим, что это свойство позволяет исследовать поведение марковских процессов при помощи хорошо разработанных методов решения соответствующих дифференциальных уравнений.
Отсюда, учитывая, что начальные условия для рассматриваемого случая , получаем
.
Теперь из условия находим необходимую функцию
. (3.15)
Подставляя выражение (3.15) в формулу (3.13), получаем преобразование Лапласа вероятности пребывания процесса в нулевом состоянии
. (3.16)
Для определения функции рассмотрим блуждания относительно первого состояния и построим для них эквивалентный граф (рис. 3.5в). Здесь преобразования Лапласа времени пребывания в состоянии 1 и вне этого состояния определяется из соотношений
, (3.17)
полученных из условия равенства распределений времени пребывания процесса в состоянии 1 и времени возврата в это состояние для исходного графа (рис. 3.4) и эквивалентного (рис. 3.5в). Разрешая систему уравнений (3.17) относительно неизвестных функций, находим
. (3.18)
Теперь на основе формулы (3.13), учитывая совпадения форм графов, изображенных на рисунке 3.8, а и б, и используя (3.18), находим преобразование Лапласа вероятности пребывания процесса в состоянии 1
, (3.19)
где .
Функция в данном случае может быть найдена из условия нормировки . Расположения изображений в ряды по степеням для оценки переходных режимов находим путем применения в формулах (3.16) и (3.19) правил операций над рядами по известных разложениям и .
Страницы: 1, 2, 3, 4, 5, 6, 7, 8