Мультипликативность стационарного распределения в открытых сетях с многорежимными стратегиями

Курсовая работа
«Мультипликативность стационарного распределения в открытых сетях с многорежимными стратегиями обслуживания»
Введение
Важными задачами для развития современного общества являются сбор, обработка, хранение и распространение информации. Передача информации представляет собой основу для решения этих задач и потому требует тщательного изучения. Адекватное описание процесса передачи информации с помощью математических моделей может быть осуществлено в рамках теории массового обслуживания. При этом для многих реальных систем такой процесс моделируется посредством сетей массового обслуживания. Например, к указанному результату приводит математическое моделирование мультипрограммных вычислительных систем и анализ их производительности, проектирование и анализ сетей передачи данных и сетей ЭВМ.
В начале XX века датский ученый А.К. Эрланг, работавший на копенгагенской телефонной станции, поставил и решил ряд новых математическтх задач, позволивших оценивать характеристики телефонных и телеграфных линий связи. Это способствовало возникновению нового направления в теории вероятностей – теории массового обслуживания. На начальной стадии своего развития теория массового обслуживания имела дело с системами массового обслуживания, которые описываются потоками однородных заявок, поступающих в систему, процедурами обслуживания с помощью одного или нескольких каналов, процедурами формирования очередей и способами организации процесса ожидания заявок. Строгое научное описание случайных процессов в теории массового обслуживания и их всестороннее исследование впервые было осуществлено А.Я. Хинчиным. Он исследовал одноканальную систему с ожиданием, простейшим входным потоком и рекуррентным обслуживанием, установив для нее так называемый основной закон стационарной очереди: стационарное распределение числа заявок в системе совпадает с их стационарным распределением в случайные моменты ухода заявок из системы. Большой вклад в развитие теории массового обслуживания внесли Ю.К. Беляев, А.А. Боровков, Б.В. Гнеденко, Н. Джейсуолл, Дж.Р. Джексон, Ф.П. Келли, Дж. Кендалл, Дж.Ф.С. Кингмэн, Л. Клейнрок, Г.П. Климов, И.Н. Коваленко, С. Пальм, Ф. Поллачек, Ю.В. Прохоров, Дж. Риордан, Т. Саати, В.Л. Смит и др.
В 1957 г. Дж.Р. Джексон впервые ввел в рассмотрение понятие открытой сети массового обслуживания ([99]), а в 1967 г. Гордон и Ньюэлл ввели аналогичное понятие замкнутой сети ([91]). В отличие от системы массового обслуживания сеть представляет собой более сложное образование, состоящее из систем массового обслуживания, называемых узлами сети, которые взаимодействуют между собой с помощью некоторого вероятностного механизма. В открытых сетях заявки могут поступать извне, а также уходить из сети. В замкнутых сетях сохраняется постоянное число заявок, которые с помощью случайной маршрутизации могут перемещаться между узлами сети; при этом поступление заявок в сеть и уход заявок из сети невозможны.
Результаты Джексона и Гордона-Ньюэлла не использовались до тех пор, пока в 1971 г. Ф.Р. Мур [115] не обнаружил, что замкнутые сети адекватно описывают вычислительные системы со многими ресурсами. С этого момента теория сетей обслуживания стала быстро развиваться благодаря задачам, связанным с математическим моделированием мультипрограммных вычислительных систем и анализом их производительности, с проектированием и анализом сетей передачи данных и сетей ЭВМ. Дополнительный толчок к дальнейшему развитию теории дала разработка и использование в повсеместной практике различных глобальных и локальных сетей таких, например, как EZERNET, INTERNET и т.д. Значительный вклад в развитие теории сетей внесли Г.П. Башарин, А.А. Боровков, Э. Геленбе, Дж. Джексон, В.А. Ивницкий, Ф.П. Келли, Д. Кениг, Л. Клейнрок, Ю.В. Малинковский, М. Миязава, Б. Меламед, Р. Мюнтц, С.Е.М. Перс, П.К. Поллетт, А.Н. Рыбко, Р. Серфозо, Ю.М. Сухов, П. Тейлор, А.Л. Толмачев, Д. Тоусли, П. Уиттли, Дж. Уолрэнд, Г.И. Фалин, В. Хендерсон, Х. Чао, К. Ченди, Р. Шассбергер и многие другие.
Состояние сети массового обслуживания обычно характеризуется вектором, координаты которого описывают состояния отдельных узлов сети. В силу многомерности случайного процесса состояний и статистической зависимости между координатами исследование сетей массового обслуживания на порядок сложнее, чем исследование систем массового обслуживания. Даже в случае экспоненциальных сетей, когда случайный процесс состояний является марковским, его эргодическое стационарное распределение удовлетворяет настолько сложной системе уравнений, что решить ее удается в основном только тогда, когда решение имеет форму произведеня. Множители в этом произведении зависят только от свойств индивидуальных узлов. В имеющейся литературе по стационарному распределению экспоненциальных сетей практически не рассматриваются сети с ненадежными или частично ненадежными приборами. В считанных работах рассмотрены только очень частные вырожденные случаи и то для сетей, состоящих из двух узлов. В то же время в практических ситуациях оборудование может частично или полностью выходить из строя. Например, при работе на персональном компьютере очень часто нарушаются функциональные связи между некоторыми файлами, программами или другими элементами, хотя компьютер продолжает работать. Налицо частичная потеря работоспособности, а значит, уменьшение интенсивности обслуживания.
Поэтому в диссертационной работе предпринята попытка построения моделей, адекватно описывающих такую ситуацию. Рассмотрены экспоненциальные сети с многорежимными стратегиями обслуживания, в которых обслуживающие устройства в узлах частично ненадежны и в различных режимах функционирования работают с разными интенсивностями. Для таких сетей находится инвариантная вероятностная мера в мультипликативной форме.
1. Основная модель
Рассматриваются открытые сети массового обслуживания с простейшим входящим потоком, экспоненциальным обслуживанием в узлах и марковской маршрутизацией. Однолинейные узлы могут работать в нескольких режимах, время переключения с одного режима на другой имеет показательное распределение. Переключение происходит только на соседние режимы. Устанавливается условие квазиобратимости узлов, условие эргодичности сети и для квазиобратимого случая находится стационарное распределение состояний сети в мультипликативной форме.
Постановка задачи
В подавляющем числе работ, посвященных сетям массового обслуживания с мультипликативной формой стационарного распределения, используется понятие квазиобратимости. Это вызвано тем, что квазиобратимость узлов гарантирует существование инвариантной меры в форме произведения для соответствующего сети марковского процесса. Здесь нами также используется понятие квазиобратимости.
Аналитические модели сетей с ненадежными приборами почти не рассматривались в литературе в силу сложности нахождения инвариантной меры. Наша постановка позволяет исследовать сети, в которых приборы могут частично выходить из строя, работая при этом в «щадящем» режиме.
В сеть, состоящую из /> однолинейных узлов, поступает стационарный пуассоновский поток заявок с параметром />. Каждая заявка входного потока независимо от других заявок с вероятностью /> направляется в />-й узел />.Заявка, обслуженная в />-м узле, мгновенно с вероятностью /> направляется в />-й узел, а с вероятностью /> покидает сеть /> В />-м узле находится единственный прибор, который может работать в /> режимах. Состояние />-го узла характеризуется парой чисел />, где /> – число заявок в />-м узле, /> – номер режима, в котором работает прибор в />-м узле />. Длительность обслуживания прибором />-го узла, находящегося в состоянии />, имеет показательное распределение с параметром />, зависящим от состояния (т.е. от числа заявок /> в узле и режима /> его работы). Назовем 0 основным режимом работы. Время пребывания в основном режиме работы имеет показательное распределение с параметром />, после чего прибор переходит в режим 1. Для состояний />, у которых />, время пребывания в режиме /> также имеет показательное распределение, при этом с интенсивностью /> прибор />-го узла переходит в режим />, а с интенсивностью /> – в режим />. Время пребывания в последнем />-м режиме имеет показательное распределение с параметром />, после чего прибор переходит в />-й режим. Во время переключения прибора с одного режима работы на другой число заявок в узле не меняется.
Переход с режима 0 в режим 1 можно трактовать как частичную потерю работоспособности прибора, влекущую уменьшение интенсивности обслуживания с величины /> на />. Аналогично, переход с режима /> в режим /> означает переход прибора в более щадящий режим обслуживания. Переход с режима /> в режим /> означает восстановление тех функциональных возможностей, которые были утеряны прибором при переходе с режима /> в режим />.--PAGE_BREAK--
Состояние сети в момент времени /> будем характеризовать вектором />, где /> – состояние />-го узла в момент времени />. В соответствии с вышесказанным здесь /> – число заявок в />-м узле в момент />, /> – номер режима работы />-го узла в момент />.
Предположим, что />, если /> и />, если />, если /> и />, если />, если /> и />, если />, а уравнение трафика
/>
имеет единственное решение /> для которого /> (для этого достаточно, чтобы матрица />, где />, была неприводимой). Тогда /> – неприводимый марковский процесс на фазовом пространстве />, где />.
Цель 2.1 состоит в установлении условий эргодичности /> и выяснении необходимых и достаточных условий, при которых стационарное финальное распределение процесса />, где />, представляется в мультипликативной форме
/>
где /> зависит только от состояния />-го узла.
Отметим, что интенсивности перехода /> процесса /> из состояния /> в состояние /> равны
/>
/>
/>
для всех иных состояний /> они равны нулю. Здесь /> – вектор, все координаты которого равны нулю кроме /> – вектор, все координаты которого равны нулю кроме /> – индикатор множества />.
Анализ изолированного узла
Для упрощения обозначений в данном разделе будет опускаться индекс />, указывающий номер узла. Например, /> – состояние узла, /> – пространство состояний узла, /> – номер режима работы прибора в узле, /> – стационарное распределение состояний узла и т.д. Рассмотрим изолированный узел, и предположим, что на него поступает простейший поток заявок с интенсивностью />. Если стационарное распределение существует, то стационарные вероятности удовлетворяют следующей системе уравнений равновесия:
/>
/>
/>
/>
/>
/>
/>
Для «заявко-сохраняющих» систем массового обслуживания (т.е. для которых совпадают средние интенсивности поступления и ухода заявок) один из возможных способов определения квазиобратимости выглядит следующим образом. Если на вход системы направлять простейший поток заявок с параметром />, то система называется квазиобратимой, если
/>
Здесь /> – часть интенсивности перехода системы из состояния /> в состояние />, обусловленная обслуживанием заявок. Напомним, что система называется обратимой, если для любых ее состояний /> и />
/>
где /> – интенсивность перехода системы из состояния /> в состояние />. Известно, что для систем с простейшим входящим потоком обратимость влечет квазиобратимость. Обратное утверждение, вообще говоря, неверно.
Для рассматриваемой нами задачи условие квазиобратимости (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) выполняется для некоторого />, т.е.    продолжение
--PAGE_BREAK--
/>
Тогда из (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) постоянным множителем.    продолжение
--PAGE_BREAK--
Замечание 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 Сети с переключением режимов при определенном количестве заявок в узле
Пусть />, где /> – вектор, все координаты которого равны нулю кроме /> – вектор, все координаты которого равны нулю кроме />. На фазовом пространстве /> задан многомерный марковский процесс />, где />, своими инфинитезимальными интенсивностями перехода
/>
/>
/>
Интенсивности перехода из состояния /> во все состояния, отличные от вышеперечисленных, предполагаются равными нулю. Здесь />, если /> и />, если /> и /> и />.
Марковский процесс /> описывает открытую сеть с простейшим входным потоком с параметром /> и вероятностью /> направления поступающей заявки в />-й узел. В />-м узле находится единственный экспоненциальный прибор с интенсивностью обслуживания />, зависящей от состояния узла. Заявка, обслуженная в />-м узле, переходит с вероятностью /> в />-й узел, а с вероятностью /> покидает сеть. Компонента /> выражает число заявок в />-м узле, а компонента /> – номер режима работы прибора. Прибор />-го узла может работать в /> режимах /> с показательно распределенным временем пребывания в них; /> – интенсивность увеличения номера режима на единицу, /> – интенсивность уменьшения номера режима на единицу.
Глобальные уравнения равновесия для стационарных вероятностей этого марковского процесса имеют следующую форму:
/>    продолжение
--PAGE_BREAK--
/>
/>
В 2.1 исследовался случай /> при /> при />. Однако на практике возможна ситуация, когда при определенных числах заявок в узлах режимы могут меняться, а при других числах – нет. Поэтому рассмотрим более общий случай, когда для каждого узла /> существует конечное или счетное множество индексов /> такое, что /> для всех />, у которых /> для некоторого /> и /> для всех /> иного вида (фактически в 2.1 рассматривался случай />).
Пусть /> – положительное решение уравнения трафика
/>
Рассмотрим марковский процесс /> на фазовом пространстве />, заданный инфинитезимальными интенсивностями
/>
/>
для всех иных состояний /> считаем, что />. Процесс /> описывает изолированный узел в фиктивной окружающей среде, в которой на узел посылается стационарный пуассоновский поток с параметром />, где /> найдено из уравнения трафика (2.2.1). Уравнения равновесия для стационарных вероятностей марковского процесса, описывающего такой узел, имеют следующий вид:
/>
для />
/>
для />
/>
/>
/>
/>
/>
/>
/>
для />
/>
Мы свяжем стационарное распределение /> процесса /> со стационарными распределениями /> процессов /> и будем интересоваться необходимыми и достаточными условиями выполнения равенства
/>
Лемма 2.3. Если для рассматриваемой системы входящий поток является простейшим, то обратимость и квазиобратимость эквивалентны.
Д о к а з а т.е. л ь с т в о. Для изолированного узла условие квазиобратимости (2.1.9) принимает вид
/>
а условие обратимости (2.1.10) – форму
/>
и для />
/>
Достаточно показать, что при выполнении (2.2.2) – (2.2.7) из (2.2.9) следует (2.2.10). Пусть /> при некотором фиксированном />. Докажем, что тогда для всех /> выполняется (2.2.10). При /> соотношение (2.2.10) следует из (2.2.4) и соотношения (2.2.9) для состояний /> и />. Предположим, что (2.2.10) выполняется для некоторого />, т.е.
/>
Тогда из (2.2.5) с учетом (2.2.11) и (2.2.9) для состояний /> и /> вытекает (2.2.10). Итак, (2.2.10) доказано с помощью индукции по />. Лемма доказана.
Лемма 2.4 [45, C.184]. Для квазиобратимости изолированного />-го узла необходимо и достаточно выполнения условий
а) для />при некотором />
/>
б) для всех />
/>
/>
При выполнении (2.2.12) для эргодичности />достаточно, чтобы сходился ряд
/>
где />. Финальное стационарное распределение процесса />определяется соотношениями    продолжение
--PAGE_BREAK--
/>
/>
/>
/>
где предполагается, что произведение, в котором нижний индекс больше верхнего, равно единице, а
/>
/>
Д о к а з а т.е. л ь с т в о. Рассмотрим случайное блуждание по точкам с целочисленными координатами первого квадранта плоскости, задаваемое уравнениями (2.2.2) – (2.2.7). Как уже ранее говорилось, для обратимости стационарного марковского процесса необходимо и достаточно, чтобы выполнялось циклическое условие Колмогорова: для любых различных состояний />
/>
Более того, известно, что для обратимости достаточно, чтобы условие (2.2.18) выполнялось для любых замкнутых путей из /> в /> без самопересечений. Равенство (2.2.12) есть условие Колмогорова (2.2.18) для четырехзвенных путей, проходящих через вершины элементарного квадрата /> и идущих из /> в /> по и против часовой стрелки. Равенство (2.2.13) есть условие Колмогорова для />-звенных путей, проходящих через вершины прямоугольника /> и ведущих из /> в /> по и против часовой стрелки. Это доказывает необходимость условий (2.2.12) и (2.2.13) для обратимости, а значит (по лемме 2.3) квазиобратимости изолированного узла в фиктивной окружающей среде. Предположим, что (2.2.12), (2.2.13) выполнены. Любой замкнутый путь из /> в /> без самопересечений либо а) представляет собой некоторую однозвенную замкнутую дугу, либо б) проходит по границе некоторой фигуры, составленной из конечного числа примыкающих друг к другу элементарных квадратов и определенных выше /> — звенных прямоугольников. Для случая а) циклическое условие (2.2.18) выполняется автоматически. В случае б) перемножим равенства (2.2.12) для всех элементарных квадратов и равенства (2.2.13) для всех прямоугольников, из которых состоит упомянутая фигура. Так как прямоугольники могут соприкасаться только «длинными» сторонами, то при этом интенсивности перехода для тех направленных дуг, которые не принадлежат границе фигуры, войдут множителями как в левую, так и в правую части. После сокращения на них получится циклическое условие (2.2.18) для путей, идущих по границе фигуры по и против часовой стрелки. Достаточность условий (2.2.12) и (2.2.13) доказана.
Отметим также, что в силу того, что примененные в доказательстве элементарные квадраты и прямоугольники имеют в качестве замкнутых путей, идущих по их границам минимальные циклы, т.е. замкнутые пути с минимальным числом вершин, то условия (2.2.12) и (2.2.13) нельзя, вообще говоря, ослабить, и они являются минимально достаточными.
Докажем, что стационарное распределение изолированного узла в фиктивной окружающей среде имеет форму (2.2.15), (2.2.16). Полагая в (2.2.10) /> получим:
/>
откуда получаем
/>
Из (2.2.9) для /> находим, что
/>
Для таких же /> из (2.2.9) также следует, что
/>
в частности,
/>
Подставляя (2.2.21) в (2.2.19), а затем подставляя полученное равенство в (2.2.20), будем иметь для />
/>
Тем самым доказано (2.2.15).
Для /> из (2.2.9) следует, что
/>
Полагая в (2.2.10) />, получим:
/>
откуда
/>
Далее, из (2.2.9)
/>
Подставляя (2.2.24) в (2.2.23), а затем полученное равенство в (2.2.22), для /> будем иметь
/>
Таким образом, (2.2.16) доказано.
Наконец, (2.2.17) следует из того, что сумма всех стационарных вероятностей равна единице:
/>
/>
/>
Достаточность сходимости ряда (2.2.14) для эргодичности /> вытекает из теоремы Фостера />. Лемма 2.4 доказана полностью.
Основной результат 2.2 заключается в следующем.
Теорема 2.2. [45, C.184] Для выполнения (2.2.8) необходимо и достаточно, чтобы в нетерминальных узлах выполнялись условия (2.2.12), (2.2.13). При выполнении этого условия для эргодичности марковского процесса />, описывающего поведение сети, достаточно, чтобы сходился ряд
/>
где
/>
При этом в нетерминальных узлах стационарное распределение процесса /> имеет форму (2.2.15) – (2.2.17).    продолжение
--PAGE_BREAK--
Д о к а з а т.е. л ь с т в о. В /> для открытых сетей с «заявкосохраняющими» узлами установлено, что для мультипликативности стационарного распределения необходимо и достаточно, чтобы нетерминальные узлы являлись квазиобратимыми. Поэтому, с учетом условия квазиобратимости (2.1.16) для изолированного узла, которое в силу леммы 2.4 для узла с номером /> принимает форму (2.2.12), (2.2.13) имеет место первое утверждение теоремы.
Докажем, что при выполнении условия (2.2.25) процесс /> эргодичен. Как отмечалось ранее, /> неприводим. Остается воспользоваться эргодической теоремой Фостера />, согласно которой достаточно проверить, что система уравнений
/>
где /> – интенсивность перехода /> из состояния /> в состояние />; />, определяемая посредством (2.2.26), – интенсивность выхода /> из состояния />, имеет нетривиальное решение /> такое, что />. Действительно, беря />, где /> определяется (2.2.8), получим, что (2.2.27) превращаются в глобальные уравнения равновесия для сети, которым /> удовлетворяет. А ряд /> сходится, так как его члены отличаются от членов ряда (2.2.25) постоянным множителем.
Замечание 2.3. Отметим, что для эргодичности марковского процесса /> достаточно потребовать выполнения следующих двух условий, гарантирующих сходимость ряда (2.2.25):
для всех />
1) сходятся ряды
/>
/>
Здесь условие 2) гарантирует регулярность марковского процесса, который не может за конечное время делать бесконечное число скачков из одного состояния в другое.
Замечание 2.4. Если условия (2.2.12), (2.2.13) выполнены во всех узлах и ряд (2.2.25) сходится, то получается простой алгоритм для нахождения стационарных вероятностей:
1. Решается система линейных уравнений (2.2.1).
2. Проверяется выполнение условий (2.2.12), (2.2.13).
3. Определяется /> по формуле (2.2.26) и проверяется сходимость ряда (2.2.25).
4. Определяются /> с помощью соотношений (2.2.15) – (2.2.17).
5. Находится стационарное распределение состояний сети /> с помощью формулы (2.2.8).
При этом нормировку вероятностей можно производить не /> раз, как это делалось в пункте 4, а один раз, исходя из условия />. Отметим также, что если в сети есть терминальные узлы, в которых условия (2.2.12), (2.2.13) не выполняются, то алгоритм существенно усложнится, так как в этих узлах нельзя применить (2.2.15) – (2.2.17). Поэтому для таких узлов необходимо добавить процедуру численного решения системы уравнений (2.2.2) – (2.2.7) с последующей его нормировкой.
Замечание 2.5. Нетрудно понять, что совместное стационарное распределение чисел заявок в узлах имеет следующую форму:
/>
где
/>
/>
/>
/>
а совместное стационарное распределение режимов работы узлов – форму:
/>
где
/>
/>
Здесь /> – число индексов, таких, что
/>
которое, как упоминалось выше, конечно или счетно.
Исходя из этих соотношений можно построить также алгоритм подсчета числовых характеристик узлов в стационарном режиме. Например, можно найти среднее стационарное число заявок в каждом узле, средний стационарный режим работы каждого узла и т.п. В принципе можно построить алгоритм нахождения совместной стационарной производящей функции чисел заявок и режимов работы в узлах сети, алгоритмы нахождения совместной производящей функции чисел заявок и нахождения совместной производящей функции режимов работы узлов в установившемся состоянии.
Пусть /> – часть выходящего из />-го узла потока заявок, покидающих сеть /> – подмножество нетерминальных узлов />. Из леммы 2.4 и результатов работы /> вытекает
Следствие 2.2. Потоки />являются независимыми пуассоновскими потоками с параметрами />соответственно.
Заметим, что если условиям (2.2.12), (2.2.13) подчиняются все узлы, то /> – независимые пуассоновские потоки.
3. Примеры открытых сетей с переключением режимов
В 2.2 рассматривалась достаточно общая модель открытой сети с многорежимными стратегиями. Здесь рассматривается несколько полезных для приложений частных случаев этой модели. Во всех рассматриваемых ниже примерах предполагается, что для /> выполняется /> при /> и /> при />.
Случай />. Во многих практических ситуациях переход с одного режима работы на другие невозможен, когда в узле нет заявок. Поэтому пусть для всех /> выполняется /> при />. Пусть также для всех /> выполняется /> для /> и /> для />, а также /> для /> и /> для />. Это соответствует тому, что в модели из 2.2 полагается />.    продолжение
--PAGE_BREAK--
Следствие 2.3. Для того, чтобы стационарное распределение марковского процесса />представлялось в мультипликативной форме (2.2.8), необходимо и достаточно, чтобы во всех нетерминальных узлах сети выполнялись условия
/>
/>
Множители в (2.2.8) имеют форму
/>
/>
/>
где
/>
/>
В следующих двух случаях стационарное распределение всегда имеет форму произведения, поскольку марковский процесс, описывающий изолированный узел в фиктивной окружающей среде, обратим. Поэтому не надо накладывать никаких ограничений типа (2.2.12), (2.2.13).
Случай />. Прибор может переключаться с одного режима работы на другие только тогда, когда в узле нет заявок: для /> выполняется /> при /> и /> при />. Кроме того для всех /> выполняется />. Это соответствует тому, что в модели из 2.2 полагается />.
Следствие 2.4. Марковский процесс />эргодичен, а его стационарное распределение представляется в мультипликативной форме (2.2.8), множители в которой имеют форму
/>
где
/>
Случай />. Переход с одного режима работы прибора на другие возможен только тогда, когда в />-узле находится определенное число заявок />: для /> выполняется /> при /> и /> при />. Кроме того для всех /> выполняется />. Это соответствует тому, что в модели из 2.2 полагается />.
Следствие 2.5. Марковский процесс />эргодичен, а его стационарное распределение представляется в мультипликативной форме (2.2.8), множители в которой имеют форму
/>
/>
где
/>
/>
Заключение
В работе рассмотрена задача установления необходимых и достаточных условий, которые надо наложить на изолированные узлы открытой сети массового обслуживания с многорежимными стратегиями обслуживания, чтобы стационарное распределение состояний сети имело мультипликативную форму с множителями, зависящими от состояний отдельных узлов. При этом изолированные узлы помещаются в фиктивную окружающую среду, характеризующуюся поступлением в них пуассоновских потоков заявок. Такой критерий точечной независимости состояний открытой сети в стационарном режиме ее работы установлен как для случая, когда интенсивности перехода в соседние режимы работы строго положительны при любых числах заявок в узлах, так и для случая, когда при определенных числах заявок в узлах они строго положительны, а при других числах все они равны нулю.
При выполнении установленных условий определены достаточные условия эргодичности марковского процесса, описывающего состояния сети, и в аналитической форме найдены множители в мультипликативном представлении стационарного распределения. Построен алгоритм для расчета стационарных вероятностей состояний сети. Доказано также, что выходящие из сети потоки заявок являются пуассоновскими, статистически не зависящими друг от друга для разных узлов.
Список использованных источников
1. Анисимов B.B., Лебедев Е.А. Стохастические сети обслуживания. Марковские модели. – Киев: Лыбидь, 1992. – 205 с.
2. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. – М.: Наука. – 1989. – 336 с.
3. Башарин Г.П., Толмачев А.Л. Некоторые результаты теории сетей массового обслуживания // Методы развития теории телетрафика. – М. – 1970. – С. 52–65.
4. Башарин Г.П., Толмачев А.Л. Теория сетей массового обслуживания и ее приложения к анализу информационно-вычислительных систем // Итоги науки и техники. – М., 1983. – Т.21. – С. 3–119. – (Сер. Теория вероятностей. Матем. статистика. Теор. кибернетика / ВИНИТИ).
5. Бочаров П.П., Печинкин А.В. Теория массового обслуживания: Учебник. – М.: РУДН, 1995. – 529 с.
6. Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. – М.: Наука, 1977. – 568 с.
7. Горцев А.М., Назаров А.А., Терпугов А.Ф. Управление и адаптация в системах массового обслуживания. – Томск: ТГУ, 1978. – 208 с.
8. Добрушин Р.Л., Кельберт М.Я., Рыбко А.Н., Сухов Ю.М. Качественные методы теории сетей с очередями // Препринт. – М., 1986. – 50 с. – (ИППИ АН СССР).
9. Евдокимович В.Е., Малинковский Ю.В. Сети массового обслуживания с динамической маршрутизацией и динамическими вероятностными обходами узлов заявками // Проблемы передачи информации. – 2001. – Том 37, вып. 3. – С. 55–66.
10. Жожикашвили В.А., Вишневский В.М. Сети массового обслуживания. Теория и применение к сетям ЭВМ. – М.: Радио и связь. – 1988. – 192 с.
11. Ивницкий В.А. Сети массового обслуживания и их применение в ЭВМ // Зарубежная радиоэлектроника. – 1977. – №7. – С. 33–70.
12. Ивницкий В.А. Об условии независимости стационарных вероятностей состояний разомкнутой сети однолинейных систем с потерями от вида распределений длительностей обслуживания // Известия АН СССР. Техническая кибернетика. – 1981. – №4. – С. 136–140.
13. Ивницкий В.А. Об условии инвариантности стационарных вероятностей для сетей массового обслуживания // Теория вероятностей и ее применения. – 1982. – Т. 27, №1. – С. 188–192.
14. Ивницкий В.А. Об инвариантности стационарных вероятностей состояний для замкнутых сетей однолинейных СМО // ДАН УССР. А. – 1989. – №7. – С. 8–11.
15. Ивницкий В.А. Об условии инвариантности стационарных вероятностей состояний для сетей однолинейных СМО // Теория вероятностей и ее применения. – 1989. – Т. 34, №3. – С. 576–580.
16. Ивницкий В.А. Об инвариантности стационарных вероятностей состояний для сетей многолинейных систем массового обслуживания с абсолютным приоритетом поступающего требования и дообслуживанием // Исследование систем и сетей массового обслуживания: Тез. докл. 12 й Бел. зимней школы-семинара по ТМО, Гродно, янв.-февр. 1996 г. / Бел. гос. унив. – Минск, 1996. – С. 36–37.