Для «заявко-сохраняющих» систем массового обслуживания (т.е. для которых совпадают средние интенсивности поступления и ухода заявок) один из возможных способов определения квазиобратимости выглядит следующим образом. Если на вход системы направлять простейший поток заявок с параметром , то система называется квазиобратимой, если
Здесь – часть интенсивности перехода системы из состояния в состояние , обусловленная обслуживанием заявок. Напомним, что система называется обратимой, если для любых ее состояний и
где – интенсивность перехода системы из состояния в состояние . Известно, что для систем с простейшим входящим потоком обратимость влечет квазиобратимость. Обратное утверждение, вообще говоря, неверно.
Для рассматриваемой нами задачи условие квазиобратимости (2.1.9) принимает вид
а условие обратимости (2.1.10) – форму
Лемма 1.1 [43, C.131]. Если для рассматриваемой системы входящий поток является простейшим, то обратимость и квазиобратимость эквивалентны.
Д о к а з а т.е. л ь с т в о. Достаточно показать, что при выполнении (2.1.3) – (2.1.8) из (2.1.11) следует (2.1.12). Сначала докажем, что для всех выполняется (2.1.12) при, т.е. равенство
При соотношение (2.1.13) следует из (2.1.3) и соотношения (2.1.11), в котором . Предположим, что (2.1.13) выполняется для некоторого , т.е.
Тогда из (2.1.4) с учетом (2.1.14) и (2.1.11) при следует (2.1.9). Итак, (2.1.9) доказано с помощью индукции по .
Теперь докажем, что для всех выполняется (2.1.12) при . При соотношение (2.1.12) следует из (2.1.6) и (2.1.11). Предположим, что (2.1.12) верно для некоторого , т.е.
Тогда (2.1.12) вытекает из (2.1.7), (2.1.11) и (2.1.15). Лемма доказана.
Лемма 1.2 [43, C.131]. Для квазиобратимости изолированного узла необходимо и достаточно выполнения условий
При выполнении (2.1.16) для эргодичности достаточно, чтобы
Финальное стационарное распределение процесса определяется соотношениями
где предполагается, что произведение, в котором нижний индекс больше верхнего, равно единице, а
Д о к а з а т.е. л ь с т в о. Рассмотрим случайное блуждание по точкам с целочисленными координатами первого квадранта плоскости с возможными переходами в соседние (слева, справа, сверху, снизу) состояния и обычной модификацией для точек на координатных осях. Покажем, что для его обратимости необходимо и достаточно, чтобы для всех
что выражает равенство произведения интенсивностей перехода по замкнутому пути, проходящему через вершины элементарного квадрата и ведущему из вершины в себя по часовой стрелке, такому же произведению интенсивностей по пути против часовой стрелки. Известно , что для обратимости стационарного марковского процесса необходимо и достаточно, чтобы выполнялось циклическое условие Колмогорова: для любых различных состояний
Более того, известно, что для обратимости достаточно, чтобы условие (2.1.21) выполнялось для любых замкнутых путей из в без самопересечений. Равенство (2.1.20) есть условие Колмогорова (2.1.21) для четырехзвенных путей, проходящих через вершины элементарного квадрата. Это доказывает необходимость условия (2.1.20). Предположим, что (2.1.20) выполнено. Любой замкнутый путь из в без самопересечений либо а) представляет собой некоторую однозвенную замкнутую дугу, либо б) проходит по границе некоторой фигуры, составленной из конечного числа примыкающих друг к другу элементарных квадратов. Для случая а) циклическое условие (2.1.21) выполняется автоматически. В случае б) перемножим равенства (2.1.20) для всех элементарных квадратов, из которых состоит упомянутая фигура. При этом интенсивности перехода для тех направленных дуг, которые не принадлежат границе фигуры, войдут множителями как в левую, так и в правую части. После сокращения на них получится циклическое условие (2.1.21) для путей, идущих по границе фигуры по и против часовой стрелки. Достаточность условия (2.1.20) доказана.
Для рассматриваемого нами блуждания (2.1.20) превращается в (2.1.16), что доказывает первое утверждение леммы 2.2.
Из (2.1.11) следует, что
а из (2.1.12) вытекает, что
Подстановка (2.1.23) в (2.1.22) доказывает (2.1.18). Достаточность сходимости ряда (2.1.17) для эргодичности вытекает из теоремы Фостера . Лемма 2.2 доказана.
Стационарное распределение сети
Следуя [32,33], -й узел назовем терминальным или оконечным, если . Основной результат формулируется следующим образом.
Теорема 1.1 [43, C.132]. Для того, чтобы стационарное распределение открытой сети с многорежимными стратегиями обслуживания в узлах представлялось в форме произведения (2.1.2), необходимо и достаточно, чтобы в нетерминальных узлах выполнялось условие
При выполнении этого условия для эргодичности марковского процесса , описывающего поведение сети, достаточно, чтобы сходился ряд
где – положительное решение уравнения трафика (2.1.1),
причем для случаев, когда не определены, они полагаются равными нулю.
Д о к а з а т.е. л ь с т в о. В для открытых сетей с «заявкосохраняющими» узлами установлено, что для мультипликативности стационарного распределения необходимо и достаточно, чтобы нетерминальные узлы являлись квазиобратимыми. Поэтому, с учетом условия квазиобратимости (2.1.16) для изолированного узла, которое для узла с номером принимает форму (2.1.24), имеет место первое утверждение теоремы.
Докажем, что при выполнении условия (2.1.24) процесс эргодичен. Как отмечалось ранее, неприводим. Остается воспользоваться эргодической теоремой Фостера , согласно которой достаточно проверить, что система уравнений
где – интенсивность перехода из состояния в состояние ; , определяемая посредством (2.1.26), – интенсивность выхода из состояния , имеет нетривиальное решение такое, что . Действительно, беря , где определяется (2.1.2), получим, что (2.1.27) превращаются в глобальные уравнения равновесия для сети, которым удовлетворяет. А ряд сходится, так как его члены отличаются от членов ряда (2.1.25) постоянным множителем.
Замечание 2.1. Отметим, что для эргодичности марковского процесса достаточно потребовать выполнения следующих двух условий, гарантирующих выполнение (2.1.25):
1) сходится ряд
Здесь условие 2) гарантирует регулярность марковского процесса, который не может за конечное время делать бесконечное число скачков из одного состояния в другое.
Замечание 2.2. Если условие (2.1.24) выполнено во всех узлах и ряд (2.1.25) сходится, то получается простой алгоритм для нахождения стационарных вероятностей:
1. Решается система линейных уравнений (2.1.1).
2. Проверяется выполнение условия (2.1.24).
3. Определяется по формуле (2.1.26) и проверяется сходимость ряда (2.1.25).
4. Определяются с помощью соотношения
где
(Формулы (2.1.28), (2.1.29) получаются из (2.1.18), (2.1.19) с учетом персонификации -го узла и того, что на него в изоляции направляется простейший поток с параметром ).
5. Находится стационарное распределение состояний сети с помощью формулы (2.1.2).
При этом нормировку вероятностей можно производить не раз, как это делалось в пункте 4, а один раз, исходя из условия . Отметим также, что если в сети есть терминальные узлы, в которых условие (2.1.24) не выполняется, то алгоритм существенно усложнится, так как в этих узлах нельзя применить (2.1.28), (2.1.29). Поэтому для таких узлов необходимо добавить процедуру численного решения системы уравнений (2.1.3) – (2.1.8) с последующей его нормировкой.
Замечание 2.3. Нетрудно понять, что совместное стационарное распределение чисел заявок в узлах имеет следующую форму:
а совместное стационарное распределение режимов работы узлов – форму:
Исходя из этих соотношений можно построить также алгоритм подсчета числовых характеристик узлов в стационарном режиме. Например, можно найти среднее стационарное число заявок в каждом узле, средний стационарный режим работы каждого узла и т.п. В принципе можно построить алгоритм нахождения совместной стационарной производящей функции чисел заявок и режимов работы в узлах сети, алгоритмы нахождения совместной производящей функции чисел заявок и нахождения совместной производящей функции режимов работы узлов в установившемся состоянии.
Пусть – часть выходящего из -го узла потока заявок, покидающих сеть – подмножество нетерминальных узлов . Из леммы 2.2 и результатов работы вытекает
Следствие 1.1 [43, C.133]. Потоки являются независимыми пуассоновскими потоками с параметрами соответственно.
Заметим, что если условию (2.1.23) подчиняются все узлы, то – независимые пуассоновские потоки.
Пусть , где – вектор, все координаты которого равны нулю кроме – вектор, все координаты которого равны нулю кроме . На фазовом пространстве задан многомерный марковский процесс , где , своими инфинитезимальными интенсивностями перехода
Интенсивности перехода из состояния во все состояния, отличные от вышеперечисленных, предполагаются равными нулю. Здесь , если и , если и и .
Марковский процесс описывает открытую сеть с простейшим входным потоком с параметром и вероятностью направления поступающей заявки в -й узел. В -м узле находится единственный экспоненциальный прибор с интенсивностью обслуживания , зависящей от состояния узла. Заявка, обслуженная в -м узле, переходит с вероятностью в -й узел, а с вероятностью покидает сеть. Компонента выражает число заявок в -м узле, а компонента – номер режима работы прибора. Прибор -го узла может работать в режимах с показательно распределенным временем пребывания в них; – интенсивность увеличения номера режима на единицу, – интенсивность уменьшения номера режима на единицу.
Глобальные уравнения равновесия для стационарных вероятностей этого марковского процесса имеют следующую форму:
В 2.1 исследовался случай при при . Однако на практике возможна ситуация, когда при определенных числах заявок в узлах режимы могут меняться, а при других числах – нет. Поэтому рассмотрим более общий случай, когда для каждого узла существует конечное или счетное множество индексов такое, что для всех , у которых для некоторого и для всех иного вида (фактически в 2.1 рассматривался случай ).
Страницы: 1, 2, 3
