Дипломна робота
Моделі відкритої мережі


Реферат
Об'єктом дослідження є відкриті мережі масового обслуговування. Предметом дослідження є стаціонарний розподіл станів мереж обслуговування.

Основною метою роботи є дослідження стаціонарного розподілу мереж масового обслуговування.

Для досягнення поставленої мети вирішуються наступні задачі:

визначається вид рівнянь рівноваги для розглянутих мереж;

перебуває стаціонарний розподіл всіх розглянутих типів мереж масового обслуговування;

для розглянутих моделей мереж масового обслуговування встановлюються достатні умови ергодичності;

доводиться інваріантність стаціонарного розподілу.

У роботі використовувалися методи теорії ймовірностей, теорії випадкових процесів, теорії масового обслуговування.

Для відкритої марковської і полумарковської моделі мережі масового обслуговування із циклічною маршрутизацією встановлюються достатні умови ергодичності й перебувають стаціонарні розподіли.

Всі результати роботи нові і є часткою случаємо наявних результатів по мережах масового обслуговування.

Робота має теоретичний характер. Практична значимість отриманих результатів обумовлена самим об'єктом дослідження. Мережі масового обслуговування є аналітичними моделями реальних мереж. А також практична значимість отриманих результатів дає можливість застосовувати їх до широкого класу задач при проектуванні й експлуатації реальних об'єктів.


Відгук
Інтенсивний розвиток інформаційних технологій послужив стимулом для побудови різноманітних математичних моделей мереж масового обслуговування. Більшу популярність серед дослідників придбала задача встановлення інваріантності стаціонарного розподілу стосовно розподілу часу обслуговування при певних дисциплінах обслуговування. Це пов'язане з тією обставиною, що в реальних мережах розподіл часу обслуговування, як правило, відмінно від показового. Крім того, часто дослідники вводять у мережі негативні заявки, оскільки вони мають різноманітні технічні інтерпретації (наприклад, негативна заявка - антивірусна програма в комп'ютері). Тому що в даній роботі розглядаються саме такі питання, то тема роботи без сумніву актуальна.

У роботі знайдений стаціонарний розподіл станів відкритої мережі масового обслуговування, що складає із трьох вузлів, при експонентних припущеннях з обліком і без обліку наявності в ній негативних заявок. Установлено достатні умови ергодичності. З'ясовано питання про стаціонарний розподіл. Досліджено нелінійні рівняння трафіка для мереж з негативними заявками. Для інверсійної дисципліни обслуговування з вибиванням із приладу заявки при надходженні нової заявки доведена інваріантність стаціонарного розподілу стосовно розподілів обслуговування у вузлах при фіксованих перших моментах цих розподілів.

У роботі є досить повний огляд літератури по темі дослідження й застосовуються строгі математичні методи.

У Висновках приводяться математичні результати.

Результати роботи мають значення для розвитку теорії мультиплікативних мереж масового обслуговування й можуть бути застосовані при експлуатації й проектуванні мереж ЕОМ, мереж передачі даних, інформаційно-обчислювальних мереж і т.д.




Введення
Теорія масового обслуговування надає можливість для адекватного опису й аналізу функціонування таких об'єктів, як телекомунікаційні мережі, мережі передачі даних, локальні мережі, мережі ЕОМ, які одержали широке поширення й розвиток в останні роки. У розвиток теорії мереж масового обслуговування істотний внесок внесли А.А. Боровков, Дж. Джексон, Г.Л. Добрушин, В. А. Ивницкий, Д. Кениг, Ю.В, Малинковский, Г.А. Медведєв, А.Л. Толмачев і багато хто інші.

Відправною крапкою в дослідженні мереж є знаходження стаціонарного розподілу ймовірностей станів. Оскільки більшу частину часу досліджуваний об'єкт проводить у сталому, стаціонарному режимі. Тому дослідження з теорії мереж, які функціонують у стаціонарному режимі, важливі як для теорії, так і для практики. За допомогою стаціонарного розподілу можуть бути знайдені різноманітні показники якості функціонування реальних систем: продуктивність, часи виконання завдань, завантаження й простої приладів і т.д.

Багато досліджень проводилися в припущенні часів обслуговування, хоча на практиці розподіл обслуговування найчастіше відрізняється від показового. Тому досить актуальним представляється доказ інваріантності стаціонарного розподілу станів мереж щодо функціонального виду законів розподілів часів обслуговування.

Основною метою роботи є дослідження стаціонарного розподілу мереж масового обслуговування й доказ інваріантності.




1. Марковська модель мережі із трьома вузлами
Визначення 1.1. Мережею масового обслуговування називається сукупність одночасно й взаємозалежна функціонуючих систем масового обслуговування, у якій циркулюють заявки, що переходять із однієї системи масового обслуговування в іншу.

Визначення 1.2. Системи масового обслуговування, з яких складається мережа, називають вузлами (полюсами, що обслуговують центрами).

Визначення 1.3. Мережа називається марковської, якщо вона описується марковським процесом.

Нехай є відкрита мережа масового обслуговування, що складає із трьох вузлів, у яку надходить найпростіший потік заявок з параметром . Причому, у першу систему масового обслуговування, що входить заявка надходить із імовірністю . Часи обслуговування заявок у різних вузлах незалежні, не залежать від процесу надходження заявок і мають показовий розподіл з параметрами  для -ого вузла, де  - число заявок в -ой системі, .

Дисципліни обслуговування заявок у системах мережі FCFS. Заявка, що завершує обслуговування в -ом вузлі миттєво з імовірністю  переходить в -ий вузол або з імовірністю  залишає мережа, причому  . .

Матриця переходу має такий вигляд:



Стан мережі описується випадковим процесом
,
де - число заявок в -ом вузлі в момент  . Покажемо, що - марковський процес. Стан  для  визначається:

числом заявок у вузлах у момент ;

моментами надходжень заявок у кожний вузол після моменту ;

моментами відходу заявок з кожного вузла після моменту .

Лема 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).



 

                                                

Малюнок 1.2.1
Він представляє із себе систему, що відрізняється від  тільки тем, що інтенсивність обслуговування  залежить від числа заявок у ній , .

Знайдемо стаціонарний розподіл для такого ізольованого процесу. Граф переходів зобразиться в такий спосіб.
                               
Рівняння рівноваги для вертикальних перерізів мають вигляд ( на малюнку 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)

= .

2.3 Доказ інваріантності стаціонарного розподілу
Згідно 1.2, для марковської моделі мережі із трьома вузлами отриманий вид стаціонарного розподілу, що визначається по формулі (1.2.9). При цьому часи обслуговування заявок мають показовий розподіл з параметрами  для -ого вузла, де  – число заявок в -ой системі, . Відповідно до розділу 2, для полумарковської моделі мережі із трьома вузлами, припускаємо, що тривалість обслуговування окремої вимоги розподілена за довільним законом. Нехай  – функція розподілу часу обслуговування -им приладом однієї заявки. Передбачається, що виконується умова, обумовлене формулою (2.1).

Відповідно до результату Севастьянова [6] і формулі (2.2.1), стаціонарний розподіл зберігає форму добутку (інваріантне) і при допущених допущеннях.

Таким чином, доведена інваріантність стаціонарного розподілу відкритої мережі масового обслуговування із трьома вузлами.




3. Марковська модель мережі із трьома вузлами й різнотипними заявками
Нехай є відкрита мережа масового обслуговування, що складає із трьох вузлів, у яку надходять два незалежних пуасоновських потоки заявок з  й  відповідно. Моменти надходження заявки (однаково з якого потоку) утворять новий потік, що називається суперпозицією або об'єднанням первісних потоків.

Позначимо через , ,  – імовірності надходження  заявок за час  відповідно для потоку з інтенсивністю , , сумарного потоку. Тому що заявки потоків з  й  надходять незалежно друг від друга, то по формулі повної ймовірності одержимо:


,      (3.1)
тобто суперпозиція пуасоновських потоків з інтенсивністю . [2]

Часи обслуговування заявок у різних вузлах незалежні, не залежать від процесу надходження заявок і мають показовий розподіл з параметрами  для -ого вузла, - константа ( ). Схематично мережа зображена на малюнку 3.1.

Заявки надходять двох типів: позитивні й негативні. Уперше модель уведена в роботі [8]. На малюнку 3.1 позитивні заявки позначені знайомий плюс, а негативні знайомий мінус, ,  – потоки на -ий вузол, – потік з -ого вузла, . На виході тільки позитивні заявки, далі позитивні заявки розбиваються на позитивні й негативні.

Дисципліни обслуговування заявок у системах мережі визначаються в такий спосіб.

а) Якщо на приладі немає заявок, те негативна заявка, що надходить на прилад, губиться;

б) Якщо на приладі немає заявок, те вступник позитивна заявка починає обслуговуватися;

в) Якщо на приладі заявка позитивна, те негативна заявка, що прийшла, вибиває заявку із приладу й позитивна заявка губиться.

г) Якщо в черзі  заявок позитивних, те прихожа негативна заявка, витісняє останню (позитивну) заявку й у черзі стає  заявка ( -ая позитивна й негативна заявка губиться).

Стан мережі описується випадковим процесом
,
де  – число позитивних заявок у момент , відповідно в першому, другому, третьому вузлі. Відповідно до розділу 1 і з огляду на формулу (3.1)  – марковський процес.

Таким чином, відповідно до визначення 1.3 і вищесказаному, побудована марковська модель відкритої мережі із трьома вузлами й різнотипними заявками.
3.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)
Позначимо й , тоді
.                                                                      (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.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)

.
Через  запишемо рівняння трафіка (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).

Результати роботи можуть бути застосовані при проектуванні й експлуатації мереж передачі даних, інформаційно-обчислювальних мереж, мереж ЕОМ і багатьох інших технічних об'єктів.




Список використаних джерел
Малинковський Ю.В. Теорія масового обслуговування. – К., 2003

Буриков А.Д., Малинковський Ю.В., Маталицкий М.А. Теорія масового обслуговування. – К., 2004

Івченко Г.И., Каштанів В.А., Коваленко И.Н. Теорія масового обслуговування. – К., 2004

Прохоров А.В., Ушаков В.Г., Ушаков Н.Г. Задачі по теорії ймовірностей: Основні поняття. Граничні теореми. Випадкові процеси. – к., 2003

Кениг Д., Штоян Д. Методи теорії масового обслуговування// Під ред. Г.П. Климова. – К., 2001

Гнеденко Б.В., Коваленко І.М. Введення в теорію масового обслуговування. – К., 2003

Ширяев О.М. Імовірність. – К., 2005

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 р.