Стационарное распределение вероятностей состояний сетей обслуживания с обходами тема автореферата и диссертации по математике, 01.01.05 ВАК РФ
|
Якубович, Оксана Владимировна
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Минск
МЕСТО ЗАЩИТЫ
|
||||
|
1999
ГОД ЗАЩИТЫ
|
|
01.01.05
КОД ВАК РФ
|
||
|
|
||||
ЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ^ #
ДК 519.2 О
со § рН/ Ом
1—. /
Якубошич Оксана Владимировна
СТАДИОНА?НОЕ РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ СОСТОЯНИЙ СЕТЕЙ ОБСЛУЖИВАНИЯ С ОБХОДАМИ
01.01.05-теория вероятностен и математическая стилистика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени камдалатд физ^ко-матемагическкх яаук
Минск 1999
Работа выполнена в Гомельском государственном университете им. Ф.Скорины
Научный руководитель - доктор физико-математических наук профессор Малинковский Юрий Владимировна
Официальные оппоненты: доктор физико-математических на\ч
Дудин Александр Николаевич
доктор физико-математических нау! Маталыцкий Михаил Алексеевич
Оппонирующая организация - Институт технической киберкеп
Национальной Академии Наук Бела{:
Защита состоится 14. января 2000 г. в 10:00 на заседании сове' защите диссертаций Д 02.01.08 при Белорусском государстве: университете по адресу: 220050, г. Минск, пр.Ф.Скорины, 4, гла корпус, ауд. 206, тел.(017) 2265541
/
С диссертацией можно ознакомиться в библиотеке Белорусс государственного'университёта.
Автореферат разослан декабря 1999 г.
Ученый секретарь \
совета по защите диссертаций / 1
МЦ.Щ0*
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы диссертации.
Интенсивное развитие теории СеМО стимулируется расширением области применения данного раздела теории массового обслуживания. Стремительное развитие информатики и вычислительной техники требует разработки теоретических основ для исследования таких объектов, как сети ЭВМ, сети передачи данных, коммуникационные сети, локальные сети и т.д. Теория сетей массового обслуживания (СеМО) предоставляет удобный язык для адекватного описания функционирования больших систем, поскольку в терминах этой теории можно формализовать достаточно сложные модели.
Существенный вклад в развитие теории СеМО внесли В.В.Аниси-мов, Г.П.Башарин, А.А.Боровков, П.П.Бочаров, Е.Геленбе, Дж.Джек-сон, В.А.Ивницкий, Ф.П.Келли, М.Я.Кельберт, Д.Кениг, Л.Клейнрок, Ю.В.Ма/ганковский, Г.А.Медведев, Б.Меламед, Р.Мюнтц, Ю.М.Сухов, П.Тейлор, А.Л.Толмачев, Д.Тоусли, Дж.Уолренд, Г.И.Фалин, Дж.Ховард, К.Ченди, Р.Шасбергер, С.Ф.Яшков и др.
При исследовании СеМО наибольший интерес представляет изучение стационарного функционирования сетей, поскольку большую часть времени изучаемый объект проводит в установившемся режиме. Большинство работ по данному вопросу связано с возможностью представления стационарного распределения сети в виде произведения множителей, характеризующих стационарное распределение узлов сети, поскольку в настоящее время в противном случае сети не поддаются аналитическому исследованию. Классическими в этом смысле считаются результаты, полученные Джексоном, Гордоном и Ньюэллом. Дальнейшим обобщением таких моделей явились сети Келли, ВСМР -сети. Келли было установлено, что узлы, из которых состоит мультипликативная сеть, обладают свойством, которое он назвал квазиобратимостью, основанное на возможности представления процессов поступления и ухода функционалами от траекторий марковской цепи, описывающей состояние узла. В том или ином виде это понятие появлялось в работах многих авторов. Наиболее полно в своих работах понятие квазиобратимости использовал и оценил его значимость Уолренд. Нетрадиционный подход, позволяющий марковской цепи переходы из состояния в это же самое состояние, позволил перенести понятие квазиобратимости на модели, которые не являются
"заявко-сохраняющими".
Во многих практических ситуациях в отдельных узлах сети могут возникать проблемы, связанные с перегрузками. В связи с этим возникает необходимость уменьшать нагрузки на такие узлы. Одним из способов решения этой проблемы является введение обходов узлов заявками. Ю.В.Малинковским были рассмотрены модифицированные сети Джексона, в которых вероятность обхода узла зависела от его состояния, описанного числом заявок в узле. Для таких сетей были получены условия мультипликативности стационарного распределения, исследованы выходящие из сети потоки заявок.
При изучении стационарного распределения большой интерес представляет инвариантность (или нечувствительность) стационарного распределения по отношению к функциональной форме распределений длительностей обслуживания в узлах. Это связано с тем, что в реальных сетях распределения продолжительностей обслуживания часто отличаются от показательного. Доказательство инвариантности стационарного распределения позволяет при проектировании реальных сетей предполагать, что обслуживание в узлах имеет показательное распределение, наиболее удобное для моделирования.
В связи с этим весьма актуальным представляется исследование стационарного распределения более общей модели сети с обходами, в которой изолированный от сети узел описывается цепью Маркова с непрерывным временем, на предмет мультипликативности стационарного распределения и его инвариантности по отношению к распределениям продолжительностей обслуживания в узлах сети.
Связь работы с крупными научными программами, темами.
Полученные в работе результаты использовались при работе над госбюджетной НИР ГБЦМ 95-13 "Стационарное функционирование сетей массового обслуживания", № госрегистрации 1996756, выполненной по плану Министерства образования РБ в 1995-1997 гг. и госбюджетной НИР ГБЦМ 98-01 "Теоретические и прикладные вопросы теории меры и теории вероятностей", № госрегистрации 1998648, выполненной по плану Министерства образования и науки РБ в 1998-1999 гг.
Цель и задачи исследования.
Основной целью работы является разработка методов исследования стационарного распределения сетей массового обслуживания с обходами узлов заявками, установление условий представимости стацио-
а
нарного распределения а виде произведения, определение условий инвариантности стационарных вероятностей исследуемых сетей относительно распределений длительностей обслуживания в узлах, а также характера выходящих из открытой сети потоков заявок.
Для достижения поставленной цели решаются следующие задачи:
а) рассматриваются открытые и замкнутые сети массового обслуживания с обходами узлов заявками с экспоненциальным обслуживанием в узлах, в случае открытой сети входной поток — простейший, изолированный от сети узел описывается регулярной эргодической цепью Маркова с непрерывным временем, а вероятность обхода заявкой узла зависит от его состояния;
б) для построенных моделей находятся достаточные условия мультипликативности стационарного распределения, для открытой сети с обходами доказывается пуассоновость потоков заявок, выходящих из сети;
в) доказывается инвариантность стационарного распределения открытых и замкнутых сетей массового обслуживания с обходами узлов заявками относительно распределений длительностей обслуживания в узлах с инверсионной дисциплиной обслуживания и абсолютным приоритетом для поступающей в узел заявки;
г) устанавливается критерий мультипликативности стационарного распределения открытой сети массового обслуживания с обходами узлов заявками и открытой сети массового обслуживания с обходами и ограниченным временем ожидания в очередях.
Объект и предмет исследования.
Исследуются открытые и замкнутые сети массового обслуживания с обходами узлов заявками. Изучается стационарный режим работы таких сетей.
Гипотеза.
Стационарное распределение марковских сетей массового обслуживания с обходами узлов заявками имеет форму произведения в предположении, что узлы квазиобратимы, и инвариантно по отношению к распределению длительностей обслуживания в узлах в случае, когда поступающая в узел начинает обслуживаться немедленно, вытесняя заявку, находящуюся на приборе, в очередь.
Методология и методы проведенного исследования.
В работе использовались методы теории вероятностей, теории случайных (марковских) процессов, теории массового обслуживания. В исследованиях мультипликативности стационарного распределения
применялся метод локального баланса, при анализе выходящих потоков использовался метод обращения времени, для установления критерия мультипликативности использован нетрадиционный подход описания сети, позволяющий переходы из некоторого состояния в это же самое состояние с некоторой положительной интенсивностью.
Научная новизна и значимость полученных результатов.
1. Для открытых и замкнутых сетей массового обслуживания с обходами узлов заявками, в которых изолированый узел описывается марковским процессом, определены условия, при которых стационарное распределение такой сети имеет форму произведения.
2. Для открытой сети с обходами узлов заявками доказана пуас-соновость выходящих из сети потоков заявок.
3. Доказана инвариантность стационарного распределения сети с обходами относительно распределений длительностей обслуживания в узлах с инверсионной дисциплиной обслуживания и абсолютным приоритетом для поступающей в узел заявки.
4. Установлен критерий мультипликативности стационарного распределения открытой сети массового обслуживания с обходами узлов заявками и открытой сети с обходами и ограниченным временем ожидания в очереди.
Все результаты работы новые и являются развитием и обобщением имеющихся результатов по сетям массового обслуживания, в частности, по сетям с обходами узлов заявками на случай, когда состояние изолированного от сети узла описывается марковским процессом.
Результаты диссертации развивают научные представления о сетях массового обслуживания, работающих в стационарном режиме.
Практическая значимость полученных результатов.
Работа имеет теоретический характер. Практическая значимость полученных результатов определяется возможностью применять их к достаточно широкому классу задач при проектировании и эксплуатации реальных объектов таких, как сети ЭВМ, сети передачи данных, коммуникационные сети, локальные сети и т.д.
Основные положения диссертации, выносимые на защиту.
1. Стационарное распределение открытой и замкнутой сети массового с обходами узлов заявками, в которой изолированный узел описывается марковским процессом, имеет мультипликативную форму при условии квазиобратимости узлов сети. В случае открытой сети выходящие из нее потоки заявок являются пуассоновскими.
2. Для открытой и замкнутой сети массового обслуживания с инверсионной дисциплиной обслуживания и абсолютным приоритетом для поступающей в узел заявки стационарное распределение инвариантно по отношению к функциональному виду распределений длительностей обслуживания при фиксированных первых моментах.
3. Устанавливается критерий мультипликативности стационарного распределения открытых марковских сетей массового обслуживания с обходами узлов заявками и открытых марковских сетей с обходами и ограниченным временем ожидания в очереди.
Личный вклад соискателя.
Все результаты, приведенные в диссертации, получены автором самостоятельно. В совместных работах постановка задач и обсуждение результатов принадлежат научному руководителю. В работе [4] автору принадлежит раздел 5. В работе [1] автору принадлежат результаты, относящиеся к классу 2.
Апробация результатов диссертации.
Материалы диссертации докладывались на 12-й Белорусской зимней школе-семинаре по теории массового обслуживания "Исследование систем и сетей массового обслуживания" (Гродно, 1996), на VII Белорусской Математической конференции (Минск, 1996), на 13-й Белорусской зимней школе-семинаре по теории массового обслуживания "Математические методы исследования телекоммуникационных сетей" (международная научная конференция В\У\¥<ЗТ-97, Минск, 1997), на 14-й Белорусской зимней школе-семинаре по теории массового обслуживания "Математические методы исследования систем и сетей массового обслуживания" (международная научная конференция В\¥\¥С}Т-98, Минск, 1998), на Республиканской научно-технической конференции для студентов и аспирантов "Новые компьютерные технологии в науке, технике, производстве и индустрии развлечений" (Гомель, 1998),на II Республиканской научно-технической конференции для студентов и аспирантов "Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях" (Гомель, 1999), на 15-й Белорусской школе-семинаре по теории массового обслуживания "Современные математические методы исследования телекоммуникационных сетей" (международная научная конференция -99, Минск, 1999).
Опубликованность результатов.
Результаты диссертации отражены в 10 работах, из них 2 статьи в научных журналах, б статей в сборниках материалов научных конфе-
рендий, 2 тезисов научных конференций. Общее количество страниц опубликованных материалов — 42.
Структура и объем диссертации.
Диссертация состоит из введения, общей характеристики работы, четырех глав, заключения, списка используемых источников. Общий объем диссертации составляет 95 страниц. Общий объем 2 иллюстраций — 1 страница. Общее количество использованных источников равно 93.
ОСНОВНОЕ СОДЕРЖАНИЕ
В первой главе диссертации сделан обзор имеющихся в настоящее время работ по тематике диссертации, дается характеристика наиболее актуальных вопросов в направлении исследований, касающихся темы диссертации, и методов их решения.
В второй главе диссертации рассматривается весьма общая модель открытых и замкнутых сетей с обходами, в которой изолированный узел описывается некоторой цепью Маркова с непрерывным временем. В случае открытой сети входящий поток предполагается простейшим. Длительности обслуживания в узлах имеют показательное распределение. Определяются условия, при которых стационарное распределение вероятностей состояний таких сетей имеет форму произведения, а также исследуются потоки заявок из узлов, выходящие из сети.
В первом разделе второй главы рассматривается открытая сеть, состоящая из N однолинейных узлов, в которую поступает простейший поток заявок интенсивности Л. Каждая заявка входного потока
независимо от других заявок с вероятностью рог направляется в г -ый _ N■
узел (г = 1, АГ, ^ ро; = 1). Заявка, направленная в г-й узел (извне <=1
или с другого узла), с вероятностью , где х^ - состояние г-го узла, присоединяется к очереди, а с вероятностью 1 — ¡х} считается мгновенно обслуженной узлом (О < /х- < 1, г = 1,А). Заявка, обслуженная г-м узлом, независимо от других заявок с вероятностью р^ мгновенно направляется в узел, а с вероятностью р,о _ N
покидает сеть (г, у = 1, Л*", Ру = 1) • Предполагается, что матрица
1=1
(Piji hj = 0, iV), где poo = 0 неприводима. Тогда уравйение трафика имеет единственное решение > 0 (г = 1, N).
Предполагается, что если г-й узел рассматривать изолированно от сети и считать, что на него поступает простейший поток с параметром As*, а каждая поступающая заявка с вероятностью 1 — ji}, зависящей от состояния Х{ г-го узла в момент ее поступления, теряется, то состояние узла описывается стандартной консервативной цепью Маркова {¿¿(¿), t > 0} с непрерывным временем и не более чем счетным фазовым пространством Х{.
Через Qi(xi,ij) обозначены инфинитезимальные интенсивности перехода ii(t) из состояния Xi 6 Х{ в состояние £ Xi (i; ф Xi). Пусть iTi(xi,Xi) - условная вероятность того, что узел перейдет в состояние ii, если на него поступит заявка, заставшая его в состоянии Xi, = + 1. Здесь и в дальнейшем - число заявок в узле, находящемся в состоянии Х{, /л ¿(я,-, i,-) - интенсивность перехода из Xi в Xi за счет ухода заявок в г-ом узле, |zi| = (£¡1 — 1, |ccj| ф 0; V{[xi, Xi) - интенсивность перехода из хi в i,- за счет внутренних изменений в г-м узле (т.е. не связанных с поступлением и уходом заявок), \ii\ = \xi\, ii ф Xi. Тогда
<li(xu ii) = <
*£ifx}n{xi,Xi), если |£f| = l^il + 1; ßi(xi,xi), если )x,-| = ja;,] - 1, ja:,-) Ф 0;
fi(xi,xi), если |ij| = \xi\, Xi ф Xi;
0, в остальных случаях ,
при этом 7г*(:гг,:г*) > 0, ^¡(г,-, ж;) > 0, 1/,(а;,-, ж;) > 0, ^ щ{xi,xi) = 1, = fli(xi,Xi) - интенсивность
N=N+1 N=N-1
обслуживания заявок г -м узлом, когда он находится в состоянии ж,-; = а'г) - интенсивность выхода из состояния Ж;
за счет внутренних переходов г -го узла.
Пусть - состояние г-го узла в момент I, которое, вообще
говоря, отличается от ¡¡(Ь) (г = 1, ЛГ); х{£) = ..., хлг(^)) -
состояние сети в момент £. При сделанных предположениях х[Ь) -однородный марковский процесс с непрерывным временем и не более, чем счетным фазовым пространством X = Х1 х ... х Хц . Предполагается, что описанные выше параметры сети выбраны таким образом, что > 0} эргодичен. Тогда финальное распределение является
стационарным распределением. Считаем, что начальное распределние совпадает с ним; тогда > 0} - стационарный процесс.
Пусть {Ai(t),t > 0} и {Di(t),t > 0} соответственно — точечные процессы поступления и ухода заявок для г-го узла, причем в A(i) включаем как моменты окончания обслуживания г-ым узлом, так и моменты потери заявок в г-ом узле. Цепь Маркова £i(t) (г-ый узел) называется квазиобратимой (квазиобратимым) с учетом обходов, если при каждом t > 0 <r{.Dj(s),s < i}, Xi(t) и cr{Ai(t + s) — Aj(t), s > 0} независимы. Здесь cr{£(s), s G А} обозначает наименьшую о--алгебру, содержащую при каждом s € А все события вида {£(s) € В}, где В — любое борелевское множество.
Лемма 2.2. Для квазиобратимости изолированного узла с учетом обходов необходимо и достаточно, чтобы
teif£pi(xi) = Pi{Xi)\li{Xi,Xi),
N=M+i
[fl i(Xi) + Vi(Xi)}pi(Xi) = ^ Pi{Xi)X£if^7ri{Xi, Х{)1{Ыф0}+ |i<|=|ii|-l
+ Pii^ViixuXi), Xi £ Xi.
N=M
Теорема 2.1. Если все изолированные узлы квазиобратимы с учетом обходов, то стационарное распределение сети имеет мультипликативную форму
р{х) = pi(xi)..
где Pi(xi) зависят только от состояния i -го узла и могут быть выбраны как стационарные вероятности состояний изолированного i -го узла с обходами.
Приведены примеры открытых сетей с обходами с применением результатов раздела.
Во втором разделе второй главы рассматривается замкнутая сеть, состоящая из N однолинейных узлов, в которой циркулирует М заявок. Заявка, направленная в i -й узел, с вероятностью fx}, где Х{ - состояние г-го узла, присоединяется к очереди, а с вероятностью 1 — fx) считается мгновенно обслуженной узлом (0 < fx? < 1, г = 1, jV) . Заявка, обслуженная г-м узлом, независимо
от других заявок с вероятностью Pij мгновенно направляется в j_ N
й узел (i,j = 1, jV, J2Pij = 1) • Делается предположение, что ма-j=i
трица (pij,i,j = 1, N) - неприводима. Тогда уравнение трафика
имеет единственное с точностью до постоянного множителя решение £,- > 0 (г = 1, /V). Полагается, что если г-й узел рассматривать изолированно от сети и считать, что на него поступает простейший поток с параметром , а каждая поступающая заявка с вероятностью 1 — /х) , зависящей от состояния узла в момент ее поступления, теряется, то состояние узла описывается стандартной консервативной цепью Маркова t > 0} с непрерывным временем и не более
чем счетным фазовым пространством Х{.
Через qi{xi, ¡¡) обозначаются инфинитезимальные интенсивности перехода я,-(£) из состояния г,- 6 Х{ в состояние ¿с,- 6 Xi (ж,- ф г,). Пусть - условная вероятность того, что узел перейдет в со-
стояние Х{, если на него поступит заявка, заставшая его в состоянии хи [£¿1 = + 1; _ интенсивность перехода из Х{ в Х{ за
счет ухода заявок в г-ом узле, = \ц\ — 1, [х;| ф 0; ^¡(г,-, х,) - интенсивность перехода из Х{ в Х{ за счет внутренних изменений в г -м узле (т.е. не связанных с поступлением и уходом заявок), \х{\ = , Х{ ф Х{. Тогда
е«/®!^»^.^«). если = N1+1;
если |£,-| = - 1, |х<| ф 0; если |:с,-| = Х{ ф О, в остальных случаях ,
qi{xu Xi) = <
при этом Wi(xi,xi) > 0, (ij(xi,xi) > 0, i'i(xi,£i) > 0, Tvi(xi,xi) = 1, ¡ii(xi) = - интенсивность
|5,|=|ц|+1 |5¡l=l»i|-l
обслуживания заявок г-м узлом, когда он находится в состоянии x¡; щ(х{) — J2 ^í{xí,xí) - интенсивность выхода из состояния ¡с,-
\Xi\ = [Xi\,Xi¿Xi
за счет внутренних переходов i -го узла.
Предполагается, что изолированный от сети i -ый узел имеет конечную емкость М , т.е. если поступающая заявка застает узел в состоянии xí , для которого \х{\ — М, то эта заявка теряется.
Пусть xf{(t) — стационарная марковская цепь, описывающая состояния такого узла, Xf{ = {a:¡ £ X¡ : |£¿| < M} — фазовое пространство. Марковский процесс x¡f(t) (i -ый узел) называется ограниченно М-квазиобратимым с учетом обходов, если в равновесии процесс с обращенным временем xf^—t) описывает некоторый узел емкости М с таким же простейшим входным потоком, но, быть может, иными интенсивности выхода из состояний.
Пусть Xj(t) - состояние г-го узла в момент t, которое, вообще говоря, отличается от í,-(í) (г = 1, N); x(t) = (xi(t),... ,хjv(í)) -
состояние сети в момент £.
Предполагается, что число циркулирующих в замкнутой сети заявок не превосходит максимально возможного числа заявок, которые могут быть приняты всеми узлами. Тогда множество X = {х е Х\ х ... х Хц : |сс11 4-... + |глг| = М} непусто. х(Ь) - однородный марковский процесс с непрерывным временем и не более чем счетным фазовым пространством X . Делается предположение, что описанные выше параметры сети выбраны таким образом, что {х(£), t > 0} эрго-дичен. Тогда финальное распределение является стационарным распределением. Считаем, что начальное распределение совпадает с ним; тогда > 0} - стационарный процесс.
Лемма 2.5. Для ограниченной М-квазиобратимости изолированного узла с учетом обходов необходимо и достаточно, чтобы
[м.'Ы + (х,) = X
1^1=1^1-1
где - стационарная мера состояний изолированного {-го узла
с обходами емкости М .
Теорема 2.2. Если все изолированные узлы ограниченно М-квазиобратимы с учетом обходов, то стационарное распределение сети имеет мультипликативную форму
р{х) = С{М,М)р1{х1)...рх(хх),
где зависят только от состояния г -го узла и могут быть
выбраны как стационарные вероятности состояний изолированного г -го узла с обходами емкости М , С(.ЛГ, М) определяется из условия нормировки.
Результаты второго раздела проиллюстрированы примером.
В третьем разделе второй главы рассматривается открытая сеть с обходами.
Обслуживание заявки узлом назовем "фиктивным", если время обслуживания равно нулю (то есть заявка осуществляет обход узла), и "истинным" в противном случае. Для изучения выходящих потоков будет использован метод обращения времени, а выходные потоки в сети с обращенным временем являются входными в первоначальной
и
сети. В соответствии с этим выходным потоком первого рода с г-го узла назовем поток заявок, выходящих из сети после любого обслуживания ("истинного" или "фиктивного") г -ым узлом (г = 1,М).
Теорема 2.3. При выполнении условия квазиобратимости узлов с учетом обходов выходные потоки первого рода из узлов сети с обходами являются независимыми пуассоновскими.
В третьей главе рассматриваются открытые и замкнутые сети с обходами с инверсионной дисциплиной обслуживания в узлах и абсолютным приоритетом для поступающей в узел заявки. Устанавливается инвариантность стационарного распределения вероятностей таких сетей по отношению к распределению длительностей обслуживания заявок в узлах при фиксированных первых моментах.
В первом разделе третьей главы рассматривается открытая сеть массового обслуживания с обходами узлов заявками, состоящая из N однолинейных узлов. В сеть поступает простейший поток интенсивности А. Заявка, поступающая в узел, сразу становится на обслуживание, вытесняя заявку, находящуюся на приборе, в очередь. Заявка, вытесненная с прибора, становится в начало очереди, а при возобновлении обслуживания дообслуживается оставшееся время. Длительности обслуживания в узлах независимы, не зависят от процесса поступления и имеют произвольное распределение с фиксированными первыми моментами. Предполагается, что
т{Х{, Хг) = Ц{(хг), |5{| = |х,-| - 1,
где Цх{х¿,5,) - интенсивность перехода из состояния ж,- в х,- за счет ухода заявки, т.е. мы вынуждены предположить, что переход из Х{ в Х{ за счет обслуживания однозначен. Последнее означает, что граф переходов изолированного узла при отсутствии внутренних переходов имеет топологию дерева.
Полагается, что внутренние переходы, т.е. переходы, не связанные с поступлением и уходом заявок в узле, являются системными, т.е. происходят для изолированного узла с произвольным распределением длительностей обслуживания заявок с теми же интенсивностями, что и для марковского случая. Предполагается также, что для внутренних переходов выполняется следующее уравнение баланса
РгО^гОг.) = X М®«'®»). 1*.|=Ы
где р{{х{) - стационарное распределение изолированного узла с учетом обходов.
Состояние сети в момент времени Ь характеризуется вектором х({) = (хх^),... , где - состояние г-го узла в момент
Ь.
Теорема 3.1. Если все изолированные узлы квазиобратпимы с учетом обходов, то стационарное распределение состояний сети имеет мультипликативную форму
где ^¿(хх) - стационарное распределение изолированного узла с учетом обходов при экспоненциальном обслуживании.
Следствие. Стационарное распределение открытой сети массового обслуживания с обходами узлов заявками не зависит от распределений длительностей обслуживания, если фиксированы их первые моменты.
Во втором разделе третьей главы рассматривается такая же замкнутая сеть с с обходами, в которой циркулирует М заявок.
Теорема 3.2. Если все изолированные узлы ограниченно М-квазиобратимы с учетом обходов, то стационарное распределение сети имеет мультипликативную форму
р(х) = С(Ы, М)рх{хх).. .рм{хм),
где Рг{х{) могут быть выбраны как стационарные вероятности состояний изолированного г -го узла с обходами емкости М, С(ЛГ, М) определяется из условия нормировки.
Следствие. Стационарное распределение замкнутой сети массового обслуживания с обходами узлов заявками не зависит от функционального вида распределений длительностей обслуживания, если фиксированы их первые моменты.
В четвертой главе рассматривается открытая сеть массового обслуживания с обходами узлов заявками.
Для исследования применяется следующая методика. Если рассматривается некоторая система массового обслуживания (узел), описанная (описанный) однородной эргодической цепью Маркова х(2) с непрерывным временем и не более чем счетным пространством состояний X, через д(х,х) обозначены интенсивности перехода системы из состояния х £ X в состояние х £ X; то нетрадиционный подход позволяет системе переходить из состояния х в состояние х с некоторой произвольно выбранной интенсивностью. Тогда интенсивность
выхода из состояния х д(г) = д(х, х) больше на дополнительное
хеХ
слагаемое д(х,х) по сравнению с традиционным подходом.
В первом разделе четвертой главы рассматривается изолированный узел, состояние которого описывается однородной эргодической цепью Маркова с непрерывным временем и не более чем счетным пространством состояний. Заявка, поступающая в узел, с некоторой вероятностью, зависящей от текущего состояния узла, присоединяется к очереди, а с дополнительной вероятностью считается мгновенно обслуженной.
Для подходящей модификации квазиобратимости интенсивности перехода q(x,x) необходимо разбить на составляющие
q(x, х) = х) 4- ß(x, х) + 7(2;, х), х, х £ X,
где а(х,х) — интенсивность перехода из х в х за счет поступления заявки, ß(x,x) — интенсивность перехода из х в х за счет обслуживания заявки, -{(х,х) — интенсивность перехода из х в х за счет внутренних переходов. Заметим, что построенное разбиение не обязательно соответствует реальным поступлениям, уходам и внутренним переходам.
Если
а(х) =
хех
ä(x) = \p(x)]-lJ}Tp{x)ß{x,x),
х£Х
то узел называется квазиобратимым, если а(х) = а, ¿(ж) = а не зависят от состояния х . При этом <3(х) можно интерпретировать как интенсивность поступления заявок для процесса с обращенным временем, если состояние процесса, описывающего узел х.
Интенсивность перехода из состояния в это же самое состояние задастся следующим образом
q(x,x) = 2a(l- fx), х G X.
Для установления квазиобратимости рассматриваемого узла производится разбиение на частичные интенсивности следующим образом
с), если = |х| +1; если х = х.
а(х i]=f <*Ь1с{х,х),
в(х х) = i ^{х,*), если = I1' ~ 1' I1' ^ 0; ^ ' ' \ а(1 — fx), если х = х.
у(х, х) = v{x, х), \х\ — \х\, х ф х.
Лемма 4.1. Для квазиобратимости x{t) необходимо и достаточно, чтобы
ар(х) = X Р(гМг>+ Р(х)а(1 ~ fx)
х€Х,хфх
[а — а + ц{х) + v(x) + 2а(1 — fx)]p[x) = ар(х)тг(х, х)+
+p(z)a(l -fx)+ X Р(£Мг>х)•
х€Х, хфх
Затем N описанных узлов склеиваются в открытую сеть стандартным образом. Поступающий в сеть поток — простейший. Заявки перемещаются по сети согласно неприводимой матрице маршрутизации (pij,i,j = О, jV) , poo = 0. Назовем г-ый узел терминальным, если pa + pi0 = 1 (г = 1,N).
Далее получен критерий мультипликативности стационарного распределения открытой марковской сети с обходами.
Теорема 4.1. Для того, чтобы стационарное распределение открытой марковской сети с обходами представлялось в виде
р(х) =pi{x1) ...pN(xN),
необходимо и достаточно, чтобы все нетерминальные узлы в сети были квазиобратимы.
В втором разделе четвертой главы рассматривается такая же модель открытой марковской сети массового обслуживания с обходами узлов заявками, но дополнительно предполагается, что время ожидания заявки в очереди ограничено экспоненциально распределенной случайной величиной с параметром т (в сети для г -го узла параметр будете, г = 1,ЛГ).
Интенсивность перехода из состояния в это же самое состояние задается следующим образом
q(x,x) = 2a(l - fx), хеХ.
Для установления квазиобратимости рассматриваемого узла производится разбиение на частичные интенсивности следующим образом
если |х| = + 1; если х — х.
а(х х)-( a{X'X)-\a(l-Jx),
В(х x) = I + i
) + г(|2г| — 1)ш(х,х), если \х\ = |ж| — 1;
если х — х.
7(х, х) = и(х, х), = |х|, х ф х.
Доказывается следующая лемма.
Лемма 4.2. Для квазиобратимости х(1) необходимо и достаточно, чтобы
ар(х)= 53 Р(*)(Ф>Х) + т(1г1 - 1Мг,а;)) +р(х)а(1 -/г)
[а-а+^(х)+т(|а;|-1)+^(х)+2а(1-/г)]р(х) = 53 ар(х)п(х,х)+
х€Х,х^х
+р(г)а(1 -/х) + 53 Р^М^я). хбХ, х^х
Получен следующий критерий мультипликативности стационарного распределения вероятностей состояний описанной модели
Теорема 4.2. Для того, чтобы стационарное распределение открытой марковской сети с обходами узлов заявками и с ограниченным временем ожидания в очереди представлялось в виде
р{х) =р\(хх).. .ря{х!я),
необходимо и достаточно, чтобы все нетерминальные узлы в сети были квазиобратимы.
ЗАКЛЮЧЕНИЕ
В диссертационной работе проведено исследование стационарного распределения сетей массового обслуживания с обходами узлов заявками; при этом состояние изолированного от сети узла описывается произвольно и не обязано совпадать с числом заявок в узле.
Получены следующие основные результаты:
1. Для открытых [1,3,4] и замкнутых сетей массового обслуживания, в которых изолированный от сети узел описывается цепью Маркова с непрерывным временем, а вероятность обхода узла заявкой зависит от состояния узла, в который она направлена, доказана мультипликативность стационарного распределения сети при условии квазиобратимости с учетом обходов узлов, из которых состоит сеть [1].
2. Для открытых и замкнутых сетей массового обслуживания, в которых заявка с вероятностью, зависящей от состояния узла, в который она направлена, присоединяется к очереди узла при инверсионной дисциплине обслуживания с абсолютным приоритетом для
поступающей в узел заявки, доказана инвариантность стационарного распределения сети относительно распределений длительностей обслуживания в узлах [6,7,8].
3.Установлен критерий мультипликативности [9] стационарного распределения открытых сетей массового обслуживания, в которых изолированный от сети узел описывается цепью Маркова с непрерывным временем, вероятность обхода узла заявкой зависит от его состояния, а также критерий мультипликативности [10] стационарного распределения открытых сетей с обходами и с ограниченным экспоненциально распределенной случайной величиной временем ожидания в очереди.
СПИСОК ОПУБЛИКОВАННЫХ РАБОТ
1. Малинковский Ю.Б., Якубович О.В. Сети массового обслуживания с мгновенно обслуживаемыми заявками: I. Модели с одним типом заявок // Автоматика и телемеханика. - 1998. - №1. - С. 92-106.
2. Малинковский Ю.В., Якубович О.В. Замкнутые сети массового обслуживания с обходами узлов заявками. // Весщ Акадэмп навук Беларусь Сер. ф!з.-мат. навук. - 1999. - №1. - С.119-124.
3. Малинковский Ю.В., Якубович О.В. Марковские сети обслуживания с обходами. // Исследование систем и сетей массового обслуживания: Тез. докл. 12-й Бел. зимней школы-семинара по ТМО, Гродно, янв.-февр. 1996 г. / Бел. гос. унив. - Минск, 1996. - С.58.
4. Krylenko А. V., Malinkovsky Ум. V., Yakubovich О. V. Queueing networks with rounds of the nodes // Distributed Computer Communication Networks: Theory and Applications: Proc. of International Conférence, Tel-Aviv, 4-8 Nov. 1996. - P. 56 - 62.
5. Малинковский Ю.В., Якубович О.В. Замкнутые сети массового обслуживания с обходами узлов заявками. // VII Белорусская Математическая Конференция: Тез. докл. научн. конф., Минск, 18-22 нояб. 1996 г./ Бел. матем. общ-во, Бел. гос. унив., Ин-т матем-ки Академии наук Беларуси. - Минск, 1996. - С. 8 - 9.
6. Малинковский Ю.В., Якубович О.В. Инвариантность стационарного распределения в марковских сетях с обходами //Математические методы исследования телекоммуникационных сетей: Материалы 13-й Бел. зимней школы-семинара по ТМО (межд. науч. конф. BWWQT-97), Минск, 3-5 февр. 1997 г./ Бел. гос. унив. - Минск, 1997. - С.118-119.
7. Малинковский Ю.В., Якубович О. В. Инвариантность марковских сетей массового обслуживания с обходами узлов заявками и немед-
ленным обслуживанием //Математические методы исследования систем и сетей массового обслуживания: Материалы 14-Й Бел. зимней школы-семинара по ТМО (межд. науч. конф. В\У\\^Т-98), Минск, 27-29 янв. 1998 г./ Бел. гос. унив. — Минск, 1998. - С.121-122.
8. Якубович О.В. Инвариантность сетей массового обслуживания, в которых вероятность обхода зависит от состояния узла и номера предыдущего узла //Новые компьютерные технологии в науке, технике, производстве и индустрии развлечений: Материалы Респ. науч.-техн. конф. студентов и аспирантов, Гомель, 9-13 марта 1998 г. / Гомельский гос. унив. им. Ф.Скорины. — Гомель, 1998. — С.
9. Якубович О. В. Критерий мультипликативности стационарнрного распределения открытой сети с обходами //Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях: Материалы II Респ. науч.-техн. конф. студентов и аспирантов, Гомель, 15-20 марта 1999 г. / Гомельский гос. унив. им. Ф.Скорины. — Гомель, 1999. — С. 107-108.
10. Якубович О.В. Критерий мультипликативности стационарнрного распределения открытой марковской сети с обходами и ограниченным временем ожидания //Массовое обслуживание. Потоки, системы, сети: Материалы межд. конф. "Современные математические методы исследования телекоммуникационных сетей", 22-24 июня, 1999 г., Минск. Вып. 15. - Мн.:БГУ, 1999. - С. 104-105.
66-68.
РЕЗЮМЕ
Якубович Оксана Владимировна
Стационарное распределение вероятностей состояний сетей обслуживания с обходами
Ключевые слова: сеть массового обслуживания, вероятность состояний, обход узла заявками, квазиобратимость, стационарное распределение, форма произведения, инвариантность стационарного распределения.
Исследуются открытые и замкнутые сети массового обслуживания с обходами узлов заявками. Изолированный от сети узел описывается марковским процессом. Изучается стационарный режим работы таких сетей.
В диссертации получены следующие результаты.
1. Для открытых и замкнутых марковских сетей массового обслуживания с обходами доказана мультипликативность стационарного распределения сети при условии квазиобратимости узлов с учетом обходов. Доказано, что в открытой сети выходящие из сети потоки заявок независимые и пуассоновские.
2. Для открытых и замкнутых сетей массового обслуживания с обходами с инверсионной дисциплине обслуживания и абсолютным приоритетом доказана инвариантность стационарного распределения сети относительно функционального вида распределений длительностей обслуживания в узлах при фиксированных первых моментах.
3. Установлен критерий мультипликативности стационарного распределения открытых марковских сетей массового обслуживания с обходами, а такж;е критерий мультипликативности стационарного распределения открытых сетей с обходами и временем ожидания в очереди, ограниченным экспоненциально распределенной случайной величиной.
РЕЗЮМЭ
Якубснич Аксана Уладз1М1рауна
Стацыянарнае размеркаванне ¡мавернасцей станау сетак абслугоування з абыхода\п
Ключавыя словы: сетка масавага абслугоування, 1мавернасць ста-нау, абыход вузла заяукам1, ква31абарачальнасць, стацыянарнае размеркаванне, форма здабытку, шварыянтнасць стацыянарнага размер-кавання.
Даследуюцца адкрытыя I замкнутый сетт массавага абслугоування з абыходам1 вузлоу заяукамц у яюх ¡заляваны ад сетга вузел ашсваецца маркаусюм працэсам. Вывучаецца стацыянарны рэжьтм працы так^х сетак.
У дысертацьп атрыманы наступныя вышю.
1. Для адкрытых 1 замкнутых маркаусгах сетак масавага абслугоування з абыходам1 вузлоу заяукам! даказана мульцшлжатыунасць стацыянарнага размеркавання сетга пры умове кваз1абарачальнасш вузлоу сетк1 з уликам абыходау. Даказана, што у адкрытай сетке вы-хадныя з сетк1 пaтoкi заявак незалежныя 1 пуасонавы.
2. Для адкрытых 1 замкнутых сетак масавага абслугоування з абыходам1 з шверайнай дысцыплшай абслугоування 1 абсалютным прыярытэтам даказана шварыянтнасць стацыянарнага размеркавання сетю адносна функцыянальнага выгляду размеркаванняу абслугоування у вузлах пры фшсаваных першых момантах.
3. Установлены крытэрый мульцтлшатыунасщ стацыянарнага размеркавання адкрытых маркаусгах сетак масавага абслугоування з абыходам), а так сама крытэрый мульцтлжатыунасщ стацыянарнага размеркавання адкрытых маркаусгах сетак масавага абслугоування з абыходам! i часам чакання, абмежаваным экспаненцыяльна размер-каванай выпадковай вел^чыней.
SUMMARY
Yakubovich Oksana Vladimirovna
Stationary distribution of probability of states of queueing networks with rounds
Keywords: queueing network, probability of states, round of the node by customers, quasireversibility, stationary distribution, product form, in-sensitivity of stationary distribution.
Open and closed queueing networks with rounds of the nodes by customers are investigated. Isolated from network node is described by the Markov process. Stationary regime of the work of such networks is studied.
Dissertation has following results.
1. Stationary distribution of open and closed Markov queueing networks with rounds has a product form in case of quasireversibility of nodes in view of rounds. For open queueing network the departure flows of customers from network are proved to be independent and Poisson.
2. Insensitivity of stationary distribution of open and closed queueing networks with rounds and with inversion service discipline and interrupting of service on distribution of service durations is proved while fixing expected values.
3. Kriteria of product form of stationary distribution of Markov open and closed queueing networks with rounds is set. Kriteria of product form of stationary distribution of Markov open and closed Markov queueing networks with rounds and with waiting time limited by exponential random variable is installed.
