Реферат: Мультипликативность стационарного распределения в открытых сетях с многорежимными стратегиями обслуживания
Курсовая работа
«Мультипликативность стационарного распределения в открытыхсетях с многорежимными стратегиями обслуживания»
Введение
Важными задачами для развития современного общества являются сбор,обработка, хранение и распространение информации. Передача информациипредставляет собой основу для решения этих задач и потому требует тщательногоизучения. Адекватное описание процесса передачи информации с помощьюматематических моделей может быть осуществлено в рамках теории массовогообслуживания. При этом для многих реальных систем такой процесс моделируетсяпосредством сетей массового обслуживания. Например, к указанному результатуприводит математическое моделирование мультипрограммных вычислительных систем ианализ их производительности, проектирование и анализ сетей передачи данных исетей ЭВМ.
В начале XX века датский ученый А.К. Эрланг, работавший накопенгагенской телефонной станции, поставил и решил ряд новых математическтхзадач, позволивших оценивать характеристики телефонных и телеграфных линийсвязи. Это способствовало возникновению нового направления в теориивероятностей – теории массового обслуживания. На начальной стадии своегоразвития теория массового обслуживания имела дело с системами массовогообслуживания, которые описываются потоками однородных заявок, поступающих всистему, процедурами обслуживания с помощью одного или нескольких каналов,процедурами формирования очередей и способами организации процесса ожиданиязаявок. Строгое научное описание случайных процессов в теории массовогообслуживания и их всестороннее исследование впервые было осуществлено А.Я. Хинчиным.Он исследовал одноканальную систему с ожиданием, простейшим входным потоком ирекуррентным обслуживанием, установив для нее так называемый основной законстационарной очереди: стационарное распределение числа заявок в системесовпадает с их стационарным распределением в случайные моменты ухода заявок изсистемы. Большой вклад в развитие теории массового обслуживания внесли Ю.К. Беляев,А.А. Боровков, Б.В. Гнеденко, Н. Джейсуолл, Дж.Р. Джексон, Ф.П. Келли,Дж. Кендалл, Дж.Ф.С. Кингмэн, Л. Клейнрок, Г.П. Климов, И.Н. Коваленко,С. Пальм, Ф. Поллачек, Ю.В. Прохоров, Дж. Риордан, Т. Саати,В.Л. Смит и др.
В 1957 г. Дж.Р. Джексон впервые ввел в рассмотрениепонятие открытой сети массового обслуживания ([99]), а в 1967 г. Гордон иНьюэлл ввели аналогичное понятие замкнутой сети ([91]). В отличие от системымассового обслуживания сеть представляет собой более сложное образование,состоящее из систем массового обслуживания, называемых узлами сети, которыевзаимодействуют между собой с помощью некоторого вероятностного механизма. Воткрытых сетях заявки могут поступать извне, а также уходить из сети. Взамкнутых сетях сохраняется постоянное число заявок, которые с помощью случайноймаршрутизации могут перемещаться между узлами сети; при этом поступление заявокв сеть и уход заявок из сети невозможны.
Результаты Джексона и Гордона-Ньюэлла не использовались до техпор, пока в 1971 г. Ф.Р. Мур [115] не обнаружил, что замкнутые сетиадекватно описывают вычислительные системы со многими ресурсами. С этогомомента теория сетей обслуживания стала быстро развиваться благодаря задачам,связанным с математическим моделированием мультипрограммных вычислительныхсистем и анализом их производительности, с проектированием и анализом сетейпередачи данных и сетей ЭВМ. Дополнительный толчок к дальнейшему развитиютеории дала разработка и использование в повсеместной практике различныхглобальных и локальных сетей таких, например, как EZERNET, INTERNET и т.д.Значительный вклад в развитие теории сетей внесли Г.П. Башарин, А.А. Боровков,Э. Геленбе, Дж. Джексон, В.А. Ивницкий, Ф.П. Келли, Д. Кениг,Л. Клейнрок, Ю.В. Малинковский, М. Миязава, Б. Меламед, Р. Мюнтц,С.Е.М. Перс, П.К. Поллетт, А.Н. Рыбко, Р. Серфозо, Ю.М. Сухов,П. Тейлор, А.Л. Толмачев, Д. Тоусли, П. Уиттли, Дж. Уолрэнд,Г.И. Фалин, В. Хендерсон, Х. Чао, К. Ченди, Р. Шассбергери многие другие.
Состояние сети массового обслуживания обычно характеризуетсявектором, координаты которого описывают состояния отдельных узлов сети. В силумногомерности случайного процесса состояний и статистической зависимости междукоординатами исследование сетей массового обслуживания на порядок сложнее, чемисследование систем массового обслуживания. Даже в случае экспоненциальныхсетей, когда случайный процесс состояний является марковским, его эргодическоестационарное распределение удовлетворяет настолько сложной системе уравнений,что решить ее удается в основном только тогда, когда решение имеет формупроизведеня. Множители в этом произведении зависят только от свойствиндивидуальных узлов. В имеющейся литературе по стационарному распределениюэкспоненциальных сетей практически не рассматриваются сети с ненадежными иличастично ненадежными приборами. В считанных работах рассмотрены только оченьчастные вырожденные случаи и то для сетей, состоящих из двух узлов. В то жевремя в практических ситуациях оборудование может частично или полностьювыходить из строя. Например, при работе на персональном компьютере очень частонарушаются функциональные связи между некоторыми файлами, программами илидругими элементами, хотя компьютер продолжает работать. Налицо частичная потеряработоспособности, а значит, уменьшение интенсивности обслуживания.
Поэтому в диссертационной работе предпринята попытка построениямоделей, адекватно описывающих такую ситуацию. Рассмотрены экспоненциальныесети с многорежимными стратегиями обслуживания, в которых обслуживающиеустройства в узлах частично ненадежны и в различных режимах функционированияработают с разными интенсивностями. Для таких сетей находится инвариантнаявероятностная мера в мультипликативной форме.
1. Основная модель
Рассматриваются открытые сети массового обслуживания с простейшимвходящим потоком, экспоненциальным обслуживанием в узлах и марковскоймаршрутизацией. Однолинейные узлы могут работать в нескольких режимах, времяпереключения с одного режима на другой имеет показательное распределение.Переключение происходит только на соседние режимы. Устанавливается условиеквазиобратимости узлов, условие эргодичности сети и для квазиобратимого случаянаходится стационарное распределение состояний сети в мультипликативной форме.
Постановка задачи
В подавляющем числе работ, посвященных сетям массовогообслуживания с мультипликативной формой стационарного распределения,используется понятие квазиобратимости. Это вызвано тем, что квазиобратимостьузлов гарантирует существование инвариантной меры в форме произведения длясоответствующего сети марковского процесса. Здесь нами также используетсяпонятие квазиобратимости.
Аналитические модели сетей с ненадежными приборами почти нерассматривались в литературе в силу сложности нахождения инвариантной меры.Наша постановка позволяет исследовать сети, в которых приборы могут частичновыходить из строя, работая при этом в «щадящем» режиме.
В сеть, состоящую из /> однолинейныхузлов, поступает стационарный пуассоновский поток заявок с параметром />. Каждая заявка входногопотока независимо от других заявок с вероятностью /> направляетсяв />-й узел />.Заявка, обслуженная в />-м узле, мгновенно свероятностью /> направляется в />-й узел, а с вероятностью /> покидает сеть /> В />-м узле находитсяединственный прибор, который может работать в /> режимах.Состояние />-го узла характеризуетсяпарой чисел />, где /> – число заявок в />-м узле, /> – номер режима, в которомработает прибор в />-м узле />. Длительность обслуживанияприбором />-го узла, находящегося всостоянии />, имеет показательноераспределение с параметром />,зависящим от состояния (т.е. от числа заявок /> вузле и режима /> его работы).Назовем 0 основным режимом работы. Время пребывания в основном режиме работыимеет показательное распределение с параметром />,после чего прибор переходит в режим 1. Для состояний />, у которых />, время пребывания в режиме/> также имеет показательноераспределение, при этом с интенсивностью /> прибор/>-го узла переходит в режим />, а с интенсивностью /> – в режим />. Время пребывания впоследнем />-м режиме имеетпоказательное распределение с параметром />,после чего прибор переходит в />-йрежим. Во время переключения прибора с одного режима работы на другой числозаявок в узле не меняется.
Переход с режима 0 в режим 1 можно трактовать как частичную потерюработоспособности прибора, влекущую уменьшение интенсивности обслуживания свеличины /> на />. Аналогично, переход срежима /> в режим /> означает переход прибора вболее щадящий режим обслуживания. Переход с режима /> врежим /> означает восстановлениетех функциональных возможностей, которые были утеряны прибором при переходе срежима /> в режим />.
Состояние сети в момент времени /> будемхарактеризовать вектором />, где /> – состояние />-го узла в момент времени />. В соответствии свышесказанным здесь /> – число заявок в/>-м узле в момент />, /> – номер режима работы />-го узла в момент />.
Предположим, что />, если /> и />, если />, если /> и />, если />, если /> и />, если />, а уравнение трафика
/>
имеет единственное решение /> длякоторого /> (для этого достаточно,чтобы матрица />, где />, была неприводимой). Тогда/> – неприводимый марковскийпроцесс на фазовом пространстве />, где />.
Цель 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)выполняется для некоторого />, т.е.
/>
Тогда из (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 Сети с переключением режимов приопределенном количестве заявок в узлеПусть />, где /> – вектор, все координатыкоторого равны нулю кроме /> –вектор, все координаты которого равны нулю кроме />.На фазовом пространстве /> заданмногомерный марковский процесс />, где />, своими инфинитезимальнымиинтенсивностями перехода
/>
/>
/>
Интенсивности перехода из состояния /> вовсе состояния, отличные от вышеперечисленных, предполагаются равными нулю.Здесь />, если /> и />, если /> и /> и />.
Марковский процесс /> описываетоткрытую сеть с простейшим входным потоком с параметром /> и вероятностью /> направления поступающейзаявки в />-й узел. В />-м узле находитсяединственный экспоненциальный прибор с интенсивностью обслуживания />, зависящей от состоянияузла. Заявка, обслуженная в />-м узле,переходит с вероятностью /> в />-й узел, а с вероятностью /> покидает сеть. Компонента /> выражает число заявок в />-м узле, а компонента /> – номер режима работыприбора. Прибор />-го узла можетработать в /> режимах /> с показательнораспределенным временем пребывания в них; /> –интенсивность увеличения номера режима на единицу, /> –интенсивность уменьшения номера режима на единицу.
Глобальные уравнения равновесия для стационарных вероятностейэтого марковского процесса имеют следующую форму:
/>
/>
/>
В 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) для эргодичности /> достаточно, чтобы сходилсяряд
/>
где />. Финальное стационарноераспределение процесса /> определяетсясоотношениями
/>
/>
/>
/>
где предполагается, что произведение, в котором нижний индексбольше верхнего, равно единице, а
/>
/>
Д о к а з а т.е. л ь с т в о. Рассмотрим случайное блуждание поточкам с целочисленными координатами первого квадранта плоскости, задаваемоеуравнениями (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).
Д о к а з а т.е. л ь с т в о. В /> дляоткрытых сетей с «заявкосохраняющими» узлами установлено, что длямультипликативности стационарного распределения необходимо и достаточно, чтобынетерминальные узлы являлись квазиобратимыми. Поэтому, с учетом условияквазиобратимости (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 полагается />.
Следствие 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.