Главная > Разное > Теоретические основы проектирования компьютерных сетей
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

1.6.3 Метод введения дополнительной переменной

Сущность этого метода исследования немарковских процессов состоит в расширении пространства состояний процесса за счет введения в его описание некоторых дополнительных компонент с тем, чтобы полученный многомерный процесс был марковским. Если удается провести исследование этого марковского процесса (например, с помощью метода»), то затем распределение исходного немарковского процесса получается, как правило, элементарным образом.

Для иллюстрации снова, как и в подпункте 1.6.1, рассмотрим систему M\G\1, то есть, однолинейную СМО с ожиданием, на вход которой поступает простейший поток интенсивности А, а время обслуживания запроса имеет произвольное распределение с функцией распределения ее преобразованием Лапласа - Стилтьеса и конечными начальными моментами

Мы уже отметили, что в случае этой системы процесс - число запросов в системе в момент t - не является марковским. Проанализировав причину немарковости процесса мы видим, что если включить в описание процесса дополнительную компоненту имеющую смысл либо времени обслуживания, прошедшего к данному моменту времени t, либо времени, оставшегося до окончания обслуживания этого запроса, то полученный двумерный случайный процесс является марковским. Оба варианта марковизации примерно одинаково популярны в литературе. Изложим здесь второй вариант.

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

Введем в рассмотрение функции:

Утверждение 12. Функции удовлетворяют следующей системе уравнений:

Доказательство состоит в применении формулы полной вероятности и анализе возможных переходов процесса за время и вероятностей соответствующих переходов. В результате приходим к следующей системе разностных уравнений для интересующих нас функций:

Деля обе части уравнений (1.71) на и устремляя к нулю, получаем систему (1.68) - (1.70).

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

Условием существования пределов (1.72) является выполнение неравенства:

Будем далее считать это условие выполненным.

Переходя в (1.67) - (1.70) к пределу при , получаем следующую систему уравнений для стационарного распределения вероятностей процесса

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

Умножая уравнения системы (1.73) - (1.75) на соответствующие степени и суммируя, получаем следующее уравнение для производящей функции

Для решения дифференциально-функционального уравнения (1.76) введем в рассмотрение преобразование Лапласа:

Применяя преобразование Лапласа к обеим частям уравнения (1.76) и используя сведения о связи преобразований Лапласа и Лапласа-Стилтьеса, а также свойство 3 преобразования Лапласа - Стилтьеса, получаем уравнение вида:

Известно, что производящая функция является аналитической (то есть, представимой в виде сходящегося степенного ряда) функцией при |z| < 1, а преобразование Лапласа аналитично в области Res > 0. Поэтому для любого при левая часть соотношения (1.77) обращается в нуль. Следовательно, при таком s обращается в нуль и правая часть (1.77). Из этого условия после несложных преобразований получаем:

Подставляя (1.78) в (1.77), получаем:

Формула (1.79) дает вид искомого стационарного распределения с точностью до значения вероятности . Сейчас уместно вспомнить, что мы рассматриваем двумерный марковский процесс вынужденно, интересующий нас процесс - число запросов в системе в момент t является немарковским.

Несложно видеть, что стационарные распределения процессов связаны соотношениями:

Поэтому производящая функция определяется как:

Вспоминая связь преобразований Лапласа и Лапласа - Стилтьеса, а также свойство 4 преобразования Лапласа - Стилтьеса, получаем:

откуда с учетом (1.79) получаем:

Вычисляя из условия нормировки константу в виде мы окончательно получаем уже известную нам формулу Поллячека - Хинчина:

Отметим, что из нее элементарно следует уже известная нам формула для стационарного распределения числа запросов в системе М|М|1:

Для системы M\D\1 с постоянным временем обслуживания запросов явные выражения для стационарных вероятностей следующие:

<< Предыдущий параграф Следующий параграф >>
Оглавление