РЕФЕРАТ
41 страница, 6 рисунков, 9 источников.
Ключевые слова: открытая сеть массового обслуживания, цепь Маркова, эргодичность, уравнения равновесия, стационарное распределение.
Объектом исследования является открытые сети массового обслуживания. Предметом исследования является стационарное распределение состояний сетей обслуживания.
Основной целью работы является исследование стационарного распределения сетей массового обслуживания.
Для достижения поставленной цели решаются следующие задачи:
1) определяется вид уравнений равновесия для рассматриваемых сетей;
2) находится стационарное распределение всех рассматриваемых типов сетей массового обслуживания;
3) для рассматриваемых моделей сетей массового обслуживания устанавливаются достаточные условия эргодичности;
4) доказывается инвариантность стационарного распределения.
В работе использовались методы теории вероятностей, теории случайных процессов, теории массового обслуживания.
Для открытой марковской и полумарковской модели сети массового обслуживания с циклической маршрутизацией устанавливаются достаточные условия эргодичности и находятся стационарные распределения.
Все результаты работы новые и являются частным случаем имеющихся результатов по сетям массового обслуживания.
Работа имеет теоретический характер. Практическая значимость полученных результатов обусловлена самим объектом исследования. Сети массового обслуживания являются аналитическими моделями реальных сетей. А также практическая значимость полученных результатов дает возможность применять их к широкому классу задач при проектировании и эксплуатации реальных объектов.
ОТЗЫВ
на конкурсную работу Гарбузы Игоря Владимировича
на тему: “Марковская и полумарковская модели открытой сети с тремя узлами”
Интенсивное развитие информационных технологий послужило стимулом для построения разнообразных математических моделей сетей массового обслуживания. Большую популярность среди исследователей приобрела задача установления инвариантности стационарного распределения по отношению к распределению времени обслуживания при определенных дисциплинах обслуживания. Это связано с тем обстоятельством, что в реальных сетях распределение времени обслуживания, как правило, отлично от показательного. Кроме того, часто исследователи вводят в сети отрицательные заявки, поскольку они имеют разнообразные технические интерпретации (например, отрицательная заявка – антивирусная программа в компьютере). Так как в данной работе рассматриваются именно такие вопросы, то тема работы без сомнения актуальна.
В работе найдено стационарное распределение состояний открытой сети массового обслуживания, состоящей из трех узлов, при экспоненциальных предположениях с учетом и без учета наличия в ней отрицательных заявок. Установлены достаточные условия эргодичности. Выяснен вопрос о мультипликативности стационарного распределения. Исследованы нелинейные уравнения трафика для сетей с отрицательными заявками. Для инверсионной дисциплины обслуживания с выбиванием с прибора заявки при поступлении новой заявки доказана инвариантность стационарного распределения по отношению к распределениям длительностей обслуживания в узлах при фиксированных первых моментах этих распределений.
В работе имеется достаточно полный обзор литературы по теме исследования и применяются строгие математические методы.
В Выводах приводятся математические результаты.
Результаты работы имеют значение для развития теории мультипликативных сетей массового обслуживания и могут быть применены при эксплуатации и проектировании сетей ЭВМ, сетей передачи данных, информационно-вычислительных сетей и т.д.
С докладами по данной тематике конкурсант участвовал в следующих конференциях:
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. Сеть называется марковской, если она описывается марковским процессом.
Пусть имеется открытая сеть массового обслуживания, состоящая из трёх узлов, в которую поступает простейший поток заявок с параметром 
. Причём, в первую систему массового обслуживания, входящая заявка поступает с вероятностью 
. Времена обслуживания заявок в различных узлах независимы, не зависят от процесса поступления заявок и имеют показательное распределение с параметрами 
для 
-ого узла, где 
- число заявок в -ой системе, $IMAGE7$.
Дисциплины обслуживания заявок в системах сети FCFS. Заявка, завершающая обслуживание в -ом узле мгновенно с вероятностью $IMAGE9$ переходит в $IMAGE10$-ый узел или с вероятностью $IMAGE11$ покидает сеть, причём $IMAGE12$ $IMAGE13$. Схематически сеть изображена на рисунке 1.1.
$IMAGE14$
Рисунок 1.1
Матрица перехода имеет следующий вид:
$IMAGE16$
Состояние сети описывается случайным процессом
$IMAGE17$,
где $IMAGE18$- число заявок в -ом узле в момент $IMAGE20$ $IMAGE13$. Покажем, что $IMAGE22$- марковский процесс. Состояние $IMAGE23$ для $IMAGE24$ определяется:
1) числом заявок $IMAGE25$в узлах в момент $IMAGE20$;
2) моментами поступлений заявок в каждый узел после момента $IMAGE20$;
3) моментами ухода заявок из каждого узла после момента $IMAGE20$.
Лемма 1.1 (об “отсутствии памяти” у показательного распределения).
Если $IMAGE29$ имеет показательное распределение с параметром , то при любых $IMAGE31$ и $IMAGE32$
$IMAGE33$.
Доказательство. По определению условной вероятности
$IMAGE34$ $IMAGE35$.
Моменты внешних поступлений в первый узел после момента $IMAGE20$ не зависят от предыстории сети до момента $IMAGE20$, так как поток извне на первый узел пуассоновский; моменты поступлений заявок с узлов на данный узел после момента $IMAGE20$ в силу “отсутствия памяти” у показательного распределения времени обслуживания заявок в узлах (см. лемму 1.1) . Аналогично доказывается, что моменты уходов заявок из узлов после момента $IMAGE20$ не зависят от предыстории $IMAGE22$ до момента $IMAGE20$. Таким образом, закон распределения $IMAGE23$ для $IMAGE24$ определяется распределением $IMAGE22$. Значит, $IMAGE22$ - марковский процесс. [1]
Таким образом, в соответствии с определением 1.3 и вышесказанном, построена марковская модель открытой сети с тремя узлами.
1.1 Уравнения глобального равновесия
Предположим, что существует стационарное распределение. Составим уравнение равновесия для стационарных вероятностей $IMAGE46$, которые для сетей называются глобальными уравнениями равновесия (баланса).
Из состояния $IMAGE47$ сеть может выйти либо за счёт поступления заявки в неё (интенсивность ), либо за счёт обслуживания заявки одним из узлов, например, - ым (интенсивность ). Поэтому интенсивность выхода из состояния $IMAGE51$ для марковского процесса $IMAGE22$ равна $IMAGE53$, где $IMAGE54$ - индикаторная функция множества $IMAGE55$. Следовательно, поток вероятности из состояния $IMAGE51$ равен:
$IMAGE57$. (1.1.1)
Войти же в состояние $IMAGE51$ можно либо из состояния $IMAGE59$, если в сеть поступит заявка, направленная в первый узел ( интенсивность $IMAGE60$), либо из состояния $IMAGE61$, если заявка завершит обслуживание во втором узле и уйдёт из сети ( интенсивность $IMAGE62$), либо, наконец, из состояний $IMAGE63$, ( $IMAGE64$, $IMAGE65$), если заявка завершит обслуживание на первом, (втором, третьем) узле и перейдёт соответственно во второй, ( третий, первый) (интенсивность $IMAGE66$, ( $IMAGE67$, $IMAGE68$)). Поэтому поток вероятности в состояние $IMAGE51$
$IMAGE70$
$IMAGE71$
$IMAGE72$. (1.1.2)
Приравнивая потоки вероятности из состояния $IMAGE51$ (формула 1.1.1) и в состояние $IMAGE51$ (формула 1.1.2), получаем глобальные уравнения равновесия
$IMAGE75$
$IMAGE76$
$IMAGE71$
$IMAGE72$. (1.1.3)
1.2 Отыскание стационарных вероятностей
Составим уравнение трафика, используя следующую формулу
$IMAGE79$, (1.2.1)
$IMAGE80$,
где $IMAGE9$ - вероятности перехода.
Решим полученную систему уравнений
$IMAGE82$
Таким образом, уравнение трафика имеет единственное положительное решение $IMAGE83$, то есть $IMAGE84$. Положительное в том смысле, что $IMAGE85$.
Рассмотрим изолированный -й узел, считая, что на него поступает простейший поток заявок интенсивности $IMAGE87$ (см. рисунок 1.2.1).
$IMAGE88$
$IMAGE87$
$IMAGE90$ $IMAGE91$
Рисунок 1.2.1
Он представляет из себя систему, отличающуюся от $IMAGE93$ только тем, что интенсивность обслуживания зависит от числа заявок в ней , $IMAGE7$.
$IMAGE97$Найдем стационарное распределение для такого изолированного процесса. Граф переходов изобразится следующим образом.
$IMAGE98$
$IMAGE99$ $IMAGE100$ $IMAGE101$ $IMAGE87$ $IMAGE87$ $IMAGE87$