Быстрый поиск

Дипломная работа: Базовый процесс обработки вызовов

Рисунок 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) правил операций над рядами по известных разложениям и .