85726 (589863), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

1.1 Уравнения глобального равновесия

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

Из состояния сеть может выйти либо за счёт поступления заявки в неё (интенсивность ), либо за счёт обслуживания заявки одним из узлов, например, - ым (интенсивность ). Поэтому интенсивность выхода из состояния для марковского процесса равна , где - индикаторная функция множества . Следовательно, поток вероятности из состояния равен:

. (1.1.1)

Войти же в состояние можно либо из состояния , если в сеть поступит заявка, направленная в первый узел ( интенсивность ), либо из состояния , если заявка завершит обслуживание во втором узле и уйдёт из сети ( интенсивность ), либо, наконец, из состояний , ( , ), если заявка завершит обслуживание на первом, (втором, третьем) узле и перейдёт соответственно во второй, ( третий, первый) (интенсивность , ( , )). Поэтому поток вероятности в состояние

. (1.1.2)

Приравнивая потоки вероятности из состояния (формула 1.1.1) и в состояние (формула 1.1.2), получаем глобальные уравнения равновесия

. (1.1.3)

1.2 Отыскание стационарных вероятностей

Составим уравнение трафика, используя следующую формулу

, (1.2.1)

,

где - вероятности перехода.

Решим полученную систему уравнений

Таким образом, уравнение трафика имеет единственное положительное решение , то есть . Положительное в том смысле, что .

Рассмотрим изолированный -й узел, считая, что на него поступает простейший поток заявок интенсивности (см. рисунок 1.2.1).

Рисунок 1.2.1

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

Н айдем стационарное распределение для такого изолированного процесса. Граф переходов изобразится следующим образом.

0 1 2 … …

Рисунок 1.2.2

Уравнения равновесия для вертикальных сечений имеют вид ( на рисунке 1.2.2 оно изображено пунктирной линией ).

, , ,

Тогда

.

Из условия нормировки находим, что

.

Таким образом, , где равны

, (1.2.2)

, (1.2.3)

. (1.2.4)

Стационарное распределение существует и единственно, если выполняется условие эргодичности:

и (1.2.5)

Теорема 1.2.1.( Разложения Джексона) Пусть уравнение трафика (1.2.1) имеет единственное положительное решение и выполнено условие эргодичности (1.2.5). Тогда финальные стационарные вероятности состояний сети Джексона имеют вид

, (1.2.6)

где определяются по формуле

, (1.2.7)

в которой определяется формулой

. (1.2.8)

Согласно теореме 1.2.1, стационарное распределение представимо в форме произведения множителей характеризующих узлы; каждый множитель есть стационарное распределение узла, то есть

,

где из формулы (1.2.2), из формулы (1.2.3), из формулы (1.2.4).

Таким образом, стационарное распределение имеет следующий вид

(1.2.9)

= .

1.3 Достаточное условие эргодичности

Теорема 1.3.1 (Эргодическая теорема Фостера).

Регулярная Марковская цепь с непрерывным временем и счетным числом состояний эргодична, если она неприводима и система уравнений

имеет нетривиальное решение такое, что При этом существует единственное стационарное распределение, которое совпадает с эргодическим. [2, с. 8-14]

Эргодичность исследуем в соответствии с теоремой 1.3.1. Рассмотрим условия теоремы.

Регулярность следует из того, что .

, , .

Согласно рисунку 1.1, получим:

, , .

Таким образом, регулярность выполняется.

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

Примечание – здесь учитывается, что матрица переходов неприводима.

В качестве нетривиального решения системы уравнений из теоремы 1.3.1 возьмем . Тогда для эргодичности потребуется, чтобы . Тогда получим,

,

где

,

Последний ряд сходится по признаку сравнения, если сходится ряд

(1.3.1)

Условие (1.3.1) и есть искомое условие эргодичности. Если это условие будет выполнятся, то будет существовать единственное стационарное распределение, совпадающее с эргодическим.

2. ПОЛУМАРКОВСКАЯ МОДЕЛЬ СЕТИ С ТРЕМЯ УЗЛАМИ

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

, . (2.1)

Дисциплины обслуживания заявок в системах сети LCFS PR - заявка, поступающая в -ый узел, вытесняет заявку с прибора и начинает обслуживаться. Вытесненная с прибора заявка становится в начало очереди. Схематически сеть изображена на рисунке 2.1.

Рисунок 2.1

Состояние сети описывается случайным процессом

,

где , , - остаточное время обслуживания заявки, стоящей в -ой позиции.

Примечание. Случайный процесс

,

где - число заявок в -ом узле в момент , не является марковским процессом. Для марковизации процесса включаем дополнительные переменные. Чтобы был марковским процессом, дополнительные переменные возьмем, как остаточные времена от момента времени до полного завершения соответствующих времен. Значит, процесс -марковский процесс.

Таким образом, из вышесказанного следует, что построена полумарковская модель открытой сети с тремя узлами.

2.1 Дифференциально-разностные уравнения Колмогорова

В соответствии методом дифференциальных уравнений и рисунком 2.1, составим следующие уравнения

, (2.1.1)

где , .

Воспользуемся следующими формулами:

,

[7]

Тогда уравнения (2.1.1) запишутся следующим образом

(2.1.2)

Учитывая то, что некоторые события являются невозможными (они равны нулю), уравнения (2.1.2) примут следующий вид

(2.1.3)

Разложение функции в ряд Тейлора, имеет вид

где - позиция элемента и соответственно.

Используя разложение функции в ряд Тейлора, преобразуем уравнения (2.1.3)

.

Переносим в левую часть равенства, затем делим обе части на и устремляем , получим

(2.1.4)

.

Таким образом, уравнения (2.1.4) и есть искомые уравнения Колмогорова.

2.2 Поиск решения дифференциально-разностных уравнений Колмогорова

Решением уравнений Колмогорова (2.1.4) является:

(2.2.1)

.

Проверим найденное решение (2.2.1) непосредственной подстановкой в уравнения (2.1.4), получим

Таким образом, 0=0, то есть решение (2.2.1) удовлетворяет уравнениям (2.1.4).

2.3 Доказательство инвариантности стационарного распределения

Согласно 1.2, для марковской модели сети с тремя узлами получен вид стационарного распределения, который определяется по формуле (1.2.9). При этом времена обслуживания заявок имеют показательное распределение с параметрами для -ого узла, где – число заявок в -ой системе, . В соответствии с разделом 2, для полумарковской модели сети с тремя узлами, предполагаем, что длительность обслуживания отдельного требования распределена по произвольному закону. Пусть – функция распределения времени обслуживания -ым прибором одной заявки. Предполагается, что выполняется условие, определяемое формулой (2.1).

Согласно результату Севастьянова [6] и формуле (2.2.1), стационарное распределение сохраняет форму произведения (инвариантно) и при допущенных допущениях.

Таким образом, доказана инвариантность стационарного распределения открытой сети массового обслуживания с тремя узлами.

3. МАРКОВСКАЯ МОДЕЛЬ СЕТИ С ТРЕМЯ УЗЛАМИ И РАЗНОТИПНЫМИ ЗАЯВКАМИ

Пусть имеется открытая сеть массового обслуживания, состоящая из трёх узлов, в которую поступают два независимых пуассоновских потока заявок с интенсивностями и соответственно. Моменты поступления заявки (все равно из какого потока) образуют новый поток, который называется суперпозицией или объединением первоначальных потоков.

Обозначим через , , – вероятности поступления заявок за время соответственно для потока с интенсивностью , , суммарного потока. Так как заявки потоков с интенсивностями и поступают независимо друг от друга, то по формуле полной вероятности получим:

, (3.1)

то есть суперпозиция пуассоновских потоков с интенсивностью . [2]

Времена обслуживания заявок в различных узлах независимы, не зависят от процесса поступления заявок и имеют показательное распределение с параметрами для -ого узла, - константа ( ). Схематически сеть изображена на рисунке 3.1.

Характеристики

Список файлов ВКР