РЕФЕРАТ
41 страница, 6 рисунков, 9 источников.
Ключевые слова: открытая сеть массового обслуживания, цепь Маркова, эргодичность, уравнения равновесия, стационарное распределение.
Объектом исследования является открытые сети массового обслуживания. Предметом исследования является стационарное распределение состояний сетей обслуживания.
Основной целью работы является исследование стационарного распределения сетей массового обслуживания.
Для достижения поставленной цели решаются следующие задачи:
определяется вид уравнений равновесия для рассматриваемых сетей;
находится стационарное распределение всех рассматриваемых типов сетей массового обслуживания;
для рассматриваемых моделей сетей массового обслуживания устанавливаются достаточные условия эргодичности;
доказывается инвариантность стационарного распределения.
В работе использовались методы теории вероятностей, теории случайных процессов, теории массового обслуживания.
Для открытой марковской и полумарковской модели сети массового обслуживания с циклической маршрутизацией устанавливаются достаточные условия эргодичности и находятся стационарные распределения.
Все результаты работы новые и являются частным случаем имеющихся результатов по сетям массового обслуживания.
Работа имеет теоретический характер. Практическая значимость полученных результатов обусловлена самим объектом исследования. Сети массового обслуживания являются аналитическими моделями реальных сетей. А также практическая значимость полученных результатов дает возможность применять их к широкому классу задач при проектировании и эксплуатации реальных объектов.
ОТЗЫВ
на конкурсную работу Гарбузы Игоря Владимировича
на тему: “Марковская и полумарковская модели открытой сети с тремя узлами”
Интенсивное развитие информационных технологий послужило стимулом для построения разнообразных математических моделей сетей массового обслуживания. Большую популярность среди исследователей приобрела задача установления инвариантности стационарного распределения по отношению к распределению времени обслуживания при определенных дисциплинах обслуживания. Это связано с тем обстоятельством, что в реальных сетях распределение времени обслуживания, как правило, отлично от показательного. Кроме того, часто исследователи вводят в сети отрицательные заявки, поскольку они имеют разнообразные технические интерпретации (например, отрицательная заявка – антивирусная программа в компьютере). Так как в данной работе рассматриваются именно такие вопросы, то тема работы без сомнения актуальна.
В работе найдено стационарное распределение состояний открытой сети массового обслуживания, состоящей из трех узлов, при экспоненциальных предположениях с учетом и без учета наличия в ней отрицательных заявок. Установлены достаточные условия эргодичности. Выяснен вопрос о мультипликативности стационарного распределения. Исследованы нелинейные уравнения трафика для сетей с отрицательными заявками. Для инверсионной дисциплины обслуживания с выбиванием с прибора заявки при поступлении новой заявки доказана инвариантность стационарного распределения по отношению к распределениям длительностей обслуживания в узлах при фиксированных первых моментах этих распределений.
В работе имеется достаточно полный обзор литературы по теме исследования и применяются строгие математические методы.
В Выводах приводятся математические результаты.
Результаты работы имеют значение для развития теории мультипликативных сетей массового обслуживания и могут быть применены при эксплуатации и проектировании сетей ЭВМ, сетей передачи данных, информационно-вычислительных сетей и т.д.
С докладами по данной тематике конкурсант участвовал в следующих конференциях:
V международная межвузовская научно-технической конференции студентов, магистрантов и аспирантов «Исследования и разработка в области машиностроения, энергетики и управления 2005»
Гомель, 12-13 мая 2005 года.
20.06.2005 заведующий кафедрой математического анализа,
доктор физико-математических наук,
профессор Малинковский Ю.В. ______________
СОДЕРЖАНИЕ
ВВЕДЕНИЕ
1 МАРКОВСКАЯ МОДЕЛЬ СЕТИ С ТРЕМЯ УЗЛАМИ
1.1 Уравнения глобального равновесия
1.2 Отыскание стационарных вероятностей
1.3 Достаточное условие эргодичности
2 ПОЛУМАРКОВСКАЯ МОДЕЛЬ СЕТИ С ТРЕМЯ УЗЛАМИ
2.1 Дифференциально-разностные уравнения Колмогорова
2.2 Поиск решения дифференциально-разностных уравнений
Колмогорова
2.3 Доказательство инвариантности стационарного распределения
3 МАРКОВСКАЯ МОДЕЛЬ СЕТИ С ТРЕМЯ УЗЛАМИ И РАЗНОТИПНЫМИ. ЗАЯВКАМИ
3.1 Составление уравнений трафика
3.2 Нахождение решений уравнений трафика
3.3 Уравнения равновесия
3.4 Определение вида стационарного распределения
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Приложение 1 Список опубликованных работ
Приложение 2 Ксерокопии опубликованных работ
ВВЕДЕНИЕ
Теория массового обслуживания предоставляет возможность для адекватного описания и анализа функционирования таких объектов, как телекоммуникационные сети, сети передачи данных, локальные сети, сети ЭВМ, которые получили широкое распространение и развитие в последние годы. В развитие теории сетей массового обслуживания существенный вклад внесли А.А. Боровков, Дж. Джексон, Г.Л. Добрушин, В. А. Ивницкий, Д. Кениг, Ю.В, Малинковский, Г.А. Медведев, А.Л. Толмачев и многие другие.
Отправной точкой в исследовании сетей является нахождение стационарного распределения вероятностей состояний. Поскольку большую часть времени изучаемый объект проводит в установившемся, стационарном режиме. Поэтому исследования по теории сетей, которые функционируют в стационарном режиме, важны как для теории, так и для практики. С помощью стационарного распределения могут быть найдены разнообразные показатели качества функционирования реальных систем: производительность, времена выполнения заданий, загрузка и простои приборов и т.д.
Многие исследования проводились в предположении экспоненциальности времен обслуживания, хотя на практике распределение длительностей обслуживания зачастую отличается от показательного. Поэтому весьма актуальным представляется доказательство инвариантности стационарного распределения состояний сетей относительно функционального вида законов распределений времен обслуживания.
Основной целью работы является исследование стационарного распределения сетей массового обслуживания и доказательство инвариантности.
1. МАРКОВСКАЯ МОДЕЛЬ СЕТИ С ТРЕМЯ УЗЛАМИ
Определение 1.1. Сетью массового обслуживания называется совокупность одновременно и взаимосвязано функционирующих систем массового обслуживания, в которой циркулируют заявки, переходящие из одной системы массового обслуживания в другую.
Определение 1.2. Системы массового обслуживания, из которых состоит сеть, называют узлами (полюсами, обслуживающими центрами).
Определение 1.3. Сеть называется марковской, если она описывается марковским процессом.
Пусть имеется открытая сеть массового обслуживания, состоящая из трёх узлов, в которую поступает простейший поток заявок с параметром />. Причём, в первую систему массового обслуживания, входящая заявка поступает с вероятностью />. Времена обслуживания заявок в различных узлах независимы, не зависят от процесса поступления заявок и имеют показательное распределение с параметрами /> для />-ого узла, где /> — число заявок в />-ой системе, />.
Дисциплины обслуживания заявок в системах сети FCFS. Заявка, завершающая обслуживание в />-ом узле мгновенно с вероятностью /> переходит в />-ый узел или с вероятностью /> покидает сеть, причём />/>. Схематически сеть изображена на рисунке 1.1.--PAGE_BREAK--
/>/>/>
/>/>
/>/>/>
/>/>
/>
/>/>
/>Рисунок 1.1
Матрица перехода имеет следующий вид:
/>
Состояние сети описывается случайным процессом
/>,
где /> — число заявок в />-ом узле в момент />/>. Покажем, что /> — марковский процесс. Состояние /> для /> определяется:
числом заявок />в узлах в момент />;
моментами поступлений заявок в каждый узел после момента />;
моментами ухода заявок из каждого узла после момента />.
Лемма 1.1 (об “отсутствии памяти” у показательного распределения).
Если /> имеет показательное распределение с параметром />, то при любых /> и />
/>.
Доказательство. По определению условной вероятности
/>/>.
Моменты внешних поступлений в первый узел после момента /> не зависят от предыстории сети до момента />, так как поток извне на первый узел пуассоновский; моменты поступлений заявок с узлов на данный узел после момента /> в силу “отсутствия памяти” у показательного распределения времени обслуживания заявок в узлах (см. лемму 1.1). Аналогично доказывается, что моменты уходов заявок из узлов после момента /> не зависят от предыстории /> до момента />. Таким образом, закон распределения /> для /> определяется распределением />. Значит, /> — марковский процесс. [1]
Таким образом, в соответствии с определением 1.3 и вышесказанном, построена марковская модель открытой сети с тремя узлами.
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).
/>
/>/>/> продолжение
--PAGE_BREAK--
Рисунок 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) и есть искомое условие эргодичности. Если это условие будет выполнятся, то будет существовать единственное стационарное распределение, совпадающее с эргодическим.
2. ПОЛУМАРКОВСКАЯ МОДЕЛЬ СЕТИ С ТРЕМЯ УЗЛАМИ продолжение
--PAGE_BREAK--
Пусть имеется открытая сеть массового обслуживания, состоящая из трёх узлов, в которую поступает простейший поток заявок с параметром />. Причём, в первую систему массового обслуживания, входящая заявка поступает с вероятностью />. Времена обслуживания заявок в />-ом узле заданы функцией распределения времени обслуживания />-ым прибором одной заявки />, />. При этом налагается следующее требование
/>, />. (2.1)
Дисциплины обслуживания заявок в системах сети LCFS PR — заявка, поступающая в />-ый узел, вытесняет заявку с прибора и начинает обслуживаться. Вытесненная с прибора заявка становится в начало очереди. Схематически сеть изображена на рисунке 2.1.
/>/>
/>/>
/>/>/>
/>/>
/>
/>
Рисунок 2.1
Состояние сети описывается случайным процессом
/>,
где />, />, /> — остаточное время обслуживания заявки, стоящей в />-ой позиции.
Примечание. Случайный процесс
/>,
где /> — число заявок в />-ом узле в момент />/>, не является марковским процессом. Для марковизации процесса включаем дополнительные переменные. Чтобы /> был марковским процессом, дополнительные переменные возьмем, как остаточные времена от момента времени /> до полного завершения соответствующих времен. Значит, процесс /> -марковский процесс.
Таким образом, из вышесказанного следует, что построена полумарковская модель открытой сети с тремя узлами.
2.1 Дифференциально-разностные уравнения Колмогорова
В соответствии методом дифференциальных уравнений и рисунком 2.1, составим следующие уравнения
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>, (2.1.1)
где />, />.
Воспользуемся следующими формулами:
/>
/>,
/>
/>
/>
/>[7]
Тогда уравнения (2.1.1) запишутся следующим образом
/>
/>/>
/>
/>
/>
/>
/>
/>/>
/>
/>
/>
/>
/>
/>
/>/>
/> продолжение
--PAGE_BREAK--
/>
/>/>
/>
/>(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), получим
/>
/>
/>
/>
/>
/>
/>
/>
/> продолжение
--PAGE_BREAK--
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
/>
Таким образом, 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.
/>
/>
/>/>/>
/>/>/>/>
/>/>
/>/>/>/>
/>/>/>/>/>/>/>
/>/>
/>
/>/>
Рисунок 3.1
Заявки поступают двух типов: положительные и отрицательные. Впервые модель введена в работе [8]. На рисунке 3.1 положительные заявки обозначены знаком плюс, а отрицательные знаком минус, />, /> – потоки на />-ый узел, />– поток с />-ого узла, />. На выходе только положительные заявки, дальше положительные заявки разбиваются на положительные и отрицательные.
Дисциплины обслуживания заявок в системах сети определяются следующим образом.
а) Если на приборе нет заявок, то отрицательная заявка, поступающая на прибор, теряется;
б) Если на приборе нет заявок, то поступающая положительная заявка начинает обслуживаться;
в) Если на приборе заявка положительная, то пришедшая отрицательная заявка выбивает заявку с прибора и положительная заявка теряется. продолжение
--PAGE_BREAK--
г) Если в очереди /> заявок положительных, то приходящая отрицательная заявка, вытесняет последнюю (положительную) заявку и в очереди становится /> заявка (/>-ая положительная и отрицательная заявка теряется).
Состояние сети описывается случайным процессом
/>,
где /> – число положительных заявок в момент />, соответственно в первом, втором, третьем узле. В соответствии с разделом 1 и учитывая формулу (3.1) /> – марковский процесс.
Таким образом, в соответствии с определением 1.3 и вышесказанном, построена марковская модель открытой сети с тремя узлами и разнотипными заявками.
3.1 Составление уравнений трафика
/>Рассмотрим изолированный />-й узел (/>), считая, что на него поступает поток заявок интенсивности />. Граф переходов изобразится следующим образом.
/>
/>/>/>/>/>
/>/>
/>
/>/>/>0 1 2 … />/> …
/>/>/>/>
/>/>/>
Рисунок 3.1.1
Тогда в соответствии с рисунком 3.1.1, получим следующие соотношения
/>, />, (3.1.1)
где />.
Согласно рисунку 3.1
/>, />. (3.1.2)
Для марковской модели сети с тремя узлами и разнотипными заявками уравнения трафика имеют следующий вид:
/>,
/>,
/>,
/>,
/>,
/>.
Учитывая формулу (3.1.2) запишем ещё три уравнения
/>,
/>,
/>.
Таким образом, уравнения трафика имеют следующий вид
/>. (3.1.3)
/>, (3.1.4)
/>, (3.1.5)
/>, (3.1.6)
/>, (3.1.7)
/>, (3.1.8)
/>, (3.1.9)
/>, (3.1.10)
/>, (3.1.11)
Подставим формулу (3.1.9) в (3.1.5) и (3.1.6), формулу (3.1.10) в (3.1.7) и (3.1.8), а формулу (3.1.11) в (3.1.3) и (3.1.4). Тогда уравнения трафика запишутся следующим образом
/>, (3.1.12)
/>, (3.1.13)
/>, (3.1.14)
/>, (3.1.15)
/>, (3.1.16)
/>. (3.1.17)
3.2 Нахождение решений уравнений трафика
Положительность решения уравнений трафика для достаточно общей модели доказана в работе [9].
Для нахождения решений уравнений трафика составим уравнение относительно />. Для этого преобразуем формулу (3.1.12), перенесём всё в левую часть и приведём к общему знаменателю
/>. (3.2.1)
Так как />, то формула (3.2.1) примет следующий вид
/>. (3.2.2)
Подставляя формулу (3.1.14) и (3.1.15) в (3.1.16) имеем
/>.
Приводим к общему знаменателю
/>. (3.2.3)
Подставим формулу, полученную из формулы (3.1.13) вычетом формулы (3.1.12), получим />, в формулу (3.2.3), получим
/>,
/>. (3.2.4)
Обозначим />и />, тогда продолжение
--PAGE_BREAK--
/>. (3.2.5)
В соответствии с формулами (3.1.16) и (3.1.17)
/>. (3.2.6)
Учитывая формулу (3.2.6) и (3.2.5), получим
/>. (3.2.7)
Подставим формулы (3.2.5) и (3.2.6) в формулу (3.2.2), имеем
/>. (3.2.8)
Так как />, то формула (3.2.8) примет следующий вид
/>. (3.2.9)
Раскрывая скобки и приводя подобные члены, запишем формулу (3.2.9) в виде
/>(3.2.10)
Таким образом, полученное уравнение (3.2.10) квадратное, то есть
/>, (3.2.11)
где коэффициенты />, учитывая обозначения />и формулу (3.2.10), определяются следующим образом
/>, (3.2.12)
/>
/>, (3.2.13)
/>. (3.2.14)
Для уравнения (3.2.11) найдём дискриминант, учитывая формулы (3.2.12), (3.2.13), (3.2.14), имеем
/>
/>.
Для получения решения уравнения (3.2.11) должно выполнятся следующее условие />, а это возможно тогда, когда
/>.
Согласно формуле />, получим
/>,
то есть
/>. (3.2.15)
В соответствии с рисунком 3.1, формула (3.2.15) есть условие эргодичности. Если это условие не выполняется, то нет стационарного распределения.
Учитывая формулы (3.2.12), (3.2.14), (3.2.15) получим, что />, />. Согласно обратной теореме Виета, если /> — корни уравнения (3.2.11), то выполняются следующие соотношения
/>/>
/>
Так как />, то один из корней положительный и один отрицательный.
Таким образом, уравнение (3.2.11) имеет одно положительное решение. То есть система уравнений трафика (3.1.12) – (3.1.17) имеет положительное решение.
3.3 Уравнения равновесия
В соответствии, с рисунком 3.1 составим уравнения равновесия
/>
/>
/>
/>
/>
/>
/>
/>(3.3.1)
/>.
3.4 Определение вида стационарного распределения
Стационарное распределение представимо в форме произведения множителей характеризующих узлы; каждый множитель есть стационарное распределение узла, то есть
/>.
Стационарное распределение />-ого узла имеет вид
/>,
где
/>, />.
Таким образом, стационарное распределение имеет следующий вид
/>
/>. (3.4.1)
Обозначим через
/>, />, />.
Тогда в этих обозначениях формула (3.4.1) запишется в следующем виде
/>. (3.4.2)
Подставляя формулу (3.4.2) в уравнения равновесия (3.3.1), получим
/>
/>
/>(3.4.3)
/>
/>.
Разделим обе части уравнения (3.4.3) на />, получим
/>
/>
/>
/>(3.4.4) продолжение
--PAGE_BREAK--
/>.
Через />запишем уравнения трафика (3.1.12) – (3.1.17)
/>, (3.4.5)
/>, (3.4.6)
/>, (3.4.7)
/>, (3.4.8)
/>, (3.4.9)
/>. (3.4.10)
Так как />, (/>), то получим следующие соотношения
/>, (3.4.11)
/>, (3.4.12)
/>. (3.4.13)
Рассмотрим всевозможные случаи числа заявок в марковской модели сети с тремя узлами и разнотипными заявками. То есть следующие случаи
1) />, />, />;
2) />, />, />;
3) />, />, />;
4) />, />, />;
5) />, />, />;
6) />, />, />;
7) />, />, />;
8) />, />, />;
Подставляя значения />в уравнение (3.4.4), учитывая уравнения (3.4.5) – (3.4.13), проверим, удовлетворяет стационарное распределение (3.4.1) уравнениям равновесия (3.3.1). Рассмотрим каждый из случаев 1) – 8) отдельно.
Рассмотрим первый случай />, />, />
/>.
Согласно формуле (3.4.6) />, формуле (3.4.8) />, />, формуле (3.4.10) />, формуле (3.4.9) />, получим
/>,
/>.
В соответствии с формулой (3.4.5) />, формулой (3.4.12) />, формулой (3.4.13) />. Из формул (3.4.9), (3.4.10) />, тогда имеем
/>,
/>.
Согласно формуле (3.4.9) />, формуле (3.4.10) />. Из формул (3.4.7) и (3.4.8) />, получим
/>,
/>.
А это есть формула (3.4.11), то есть случай 1) выполняется.
Рассмотрим второй случай />, />, />
/>
/>,
Согласно формуле (3.4.5) />, формуле (3.4.6) />, формуле (3.4.8) />, />, формуле (3.4.10) />, формуле (3.4.10) />. Из формул (3.4.5) и (3.4.6) />. Раскроем скобки и перенесём всё в правую часть, получим
/>.
В соответствии с формулой (3.4.13) />, формулой (3.4.12). Из формул (3.4.9), (3.4.10) />, тогда
/>.
Согласно формуле (3.4.11) />, />, формуле (3.4.12) />. Из формул (3.4.7) и (3.4.8) />, получим
/>.
/>, то есть случай 2) выполняется.
Аналогично выполняются 3) – 8).
Таким образом, случаи 1) – 8) превращаются в верное равенство. То есть стационарное распределение (3.4.1) есть решение уравнения равновесия (3.3.1), если выполняется условие эргодичности />, />.
ЗАКЛЮЧЕНИЕ
В работе проведено исследование открытых марковских и полумарковских сетей массового обслуживания с тремя узлами и циклической маршрутизацией.
Получены следующие основные результаты:
Для марковской модели сети с тремя узлами, записаны уравнения равновесия (формула 1.1.3), получено достаточное условие эргодичности (формула 1.3.1) и найдено стационарное распределение (формула 1.2.9).
Для полумарковской модели сети с тремя узлами, определен вид дифференциально-разностных уравнений Колмогорова (формула 2.1.4), найдено стационарное распределение (формула 2.2.1) и доказана инвариантность (см. 2.3).
Для марковской модели сети с тремя узлами и разнотипными заявками, составлены уравнения равновесия (формула 3.3.1), найдено стационарное распределение (формула 3.4.1) и получено достаточное условие эргодичности (формула 3.2.15).
Результаты работы могут быть применены при проектировании и эксплуатации сетей передачи данных, информационно-вычислительных сетей, сетей ЭВМ и многих других технических объектов.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Малинковский Ю.В. Теория массового обслуживания. – Гомель: Бел ГУТ, 1998. – 100с.
Буриков А.Д., Малинковский Ю.В., Маталыцкий М.А. Теория массового обслуживания. – Гродно: ГрГУ, 1984. – 108с.
Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания. – М.: Высшая школа, 1982. – 256с.
Прохоров А.В., Ушаков В.Г., Ушаков Н.Г. Задачи по теории вероят-ностей: Основные понятия. Предельные теоремы. Случайные процессы. – М.: Наука. Главная редакция физ.-мат. литературы, 1986. – 328с.
Кениг Д., Штоян Д. Методы теории массового обслуживания: Пер. с нем.// Под ред. Г.П. Климова. – М.: Радио и связь, 1981. – 128с.
Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. – М.: Наука, 1966. – 431с.
Ширяев А.Н. Вероятность. – М.: Наука. Главная редакция физ.-мат. литературы, 1980 – 575с.
Gelenbe E. Product Form Queueing Networks with Negative and Positive Customers // J. Appl. Probab. – 1991. – V. 28. – P. 656 – 663.
Gelenbe E., Shassberger R. Stability of Product-Form G-networks // Probab. in Eng. and Inform. Sci. – 1992. – No. 6. – P. 271 – 276.
Приложение 1 Список опубликованных работ
Гарбуза И.В. Марковская и полумарковская модели открытой сети с тремя узлами// Материалы V международной межвузовской научно-технической конференции студентов, магистрантов и аспирантов «Исследования и разработка в области машиностроения, энергетики и управления 2005» Гомель, 2005 г.
Гарбуза И.В. Стационарное распределение и его инвариантность для модели открытой сети с тремя узлами// Творчество молодых’2005 Сборник научных работ студентов и аспирантов Гомельского Государственного университета им. Ф. Скорины. Гомель, 2005 г.