Методи дослідження мереж масового обслуговування (стр. 2 из 13)
1.2 ДИСЦИПЛІНА ОБСЛУГОВУВАННЯ
Дисципліна обслуговування відображає правило, відповідно до якого здійснюється вибір повідомлення для обслуговування в центрі. Розрізняють безпріорітетні і пріоритетні дисципліни обслуговування. Прикладом безпріорітетних дисциплін є дисципліна обслуговування «першим прийшов — першим обслужений» (ПППО), відповідно до якої повідомлення, що надійшло в центр, стає в кінець черги повідомлень, які чекають обслуговування, якщо всі прилади центру зайняті, і негайно починає обслуговуватися, якщо вільний хоча б один прилад.
Хорошою ілюстрацією пріоритетних дисциплін є правило вибору повідомлення за принципом «останнім прийшов — першим обслужений» (ОППО). При обслуговуванні за принципом ОППО, повідомленню, яке щойно надійшло, привласнюється щонайвищий пріоритет і воно або починає негайно обслуговуватися, перериваючи обслуговування попередніх повідомлень (абсолютний пріоритет), або стає першим в черзі повідомлень, які чекають обслуговування (відносний пріоритет). Щодо повідомлення, обслуговування якого було перерване, можливі різні припущення: воно або покидає центр обслуговування (втрачається), або повертається в початок черги (обслуговування цього повідомлення або починається наново, або з перерваного місця).
Окрім дисципліни обслуговування ПППО і ОППО в теорії мереж МО велику роль відіграють ще дві дисципліни — розділення процесора (РП) і обслуговування без очікування (ОБО). У однолінійних центрах з дисципліною обслуговування РП кожне повідомлення незалежно від його положення в черзі обслуговується з інтенсивністю, обернено пропорційною кількості п повідомлень в центрі (іншими словами, кожне повідомлення обслуговується
c).1.3 МАРШРУТНА МАТРИЦЯ І ПОТОКИ В МЕРЕЖАХ
Перехід повідомлення з одного центру після закінчення обслуговування в ньому в іншій здійснюється відповідно до заданого маршруту, під яким розуміється послідовність відвідуваних повідомленням центрів мережі. Маршрут повідомлення по мережі МО задається матрицею маршрутів P, вид якої залежить від того, чи є мережа МО відкритою або замкненою. У відкриту мережу МО повідомлення надходять із зовнішнього джерела і можуть покидати мережу після завершення обслуговування. Якщо прийняти зовнішнє джерело за новий центр мережі і позначити індексом 0, то маршрут у відкритій мережі задається стохастичною матрицею
, де 
і 
— відповідно імовірність надходження в j-й центр повідомлення з джерела і імовірність покидання повідомленням мережі після закінчення обслуговування в і-му центрі; 
— імовірність того, що повідомлення, що йде з i-го центру, перейде в j-й центр 
Очевидно, що виконується рівність
Потік повідомлень, який входить з джерела в мережу визначається сумісним розподілом випадкових величин
, де 
— моменти надходження повідомлень 
Якщо випадкові величини Zk незалежні в сукупності, то такий потік називають потоком з обмеженою післядією і для його визначення достатньо задати набір функцій розподілу 
Важливу роль в теорії систем і мереж МО виконує рекурентний потік, для якого 
. Окремим випадком рекуррентного потоку є пуассонівський потік, для якого 
, де інтенсивність потоку λ може залежати від загального числа повідомлень N, що знаходяться в мережі.Для визначення потоків, що циркулюють в стаціонарному режимі у відкритій мережі МО, введемо коефіцієнти передачі ei такі, що eiλ(N) є загальною інтенсивністю потоку повідомлень в i-й центр мережі. Інтенсивність eiλ(N) складається з інтенсивності надходження повідомлень в і-й центр з джерела
і інтенсивності надходження від інших центрів 
Таким чином, величини ei задовольняють наступній системі лінійних рівнянь:
розв’язок якої через припущення про те, що стохастична матриця маршрутів Р є невиродженою, існує і єдиний.
У замкненій мережі МО повідомлення ззовні не надходять і не покидають мережу; кількість повідомлень, що циркулюють в ній, постійна і дорівнює N. Матриця Р, що визначає випадкові маршрути руху повідомлень, так же само, як і для відкритої мережі, передбачається стохастичною і нерозкладною, але не містить в цьому випадку нульових стовпця і рядка (джерело повідомлень відсутнє). Система лінійних рівнянь (1.3.2) набуде вигляду
Число незалежних рівнянь в системі (1.3.3) на одиницю менше кількості змінних, так що її рішення єдине з точністю до мультиплікативної константи. Іншими словами, якщо
— розв’язок системи рівнянь (1.3.3), то при 
розв’язком є і 
. Для відшукання однозначного розв’язку системи рівнянь (1.3.3) достатньо довільно задати значення ei ,наприклад покласти ei=1. У цьому випадку величину ei можна інтерпретувати як середнє число відвідувань повідомленням центру 
між двома послідовними відвідуваннями ним першого центру.Нехай
— потік, що проходить через 
-й центр 
в стаціонарному режимі. Тоді вираз 
зв'язує потоки, що проходять через i-й і перший центри мережі.1.4 ІНШІ ВИЗНАЧЕННЯ
В силу статистичної однорідності повідомлень, що циркулюють у відкритих і замкнених мережах МО, такі мережі називають однорідними. При цьому однорідну мережу МО називатимемо експоненціальною, якщо функції розподілу
є експоненціальними, і немарківською, якщо хоча б одна з цих функцій є довільною.Природним узагальненням однорідних мереж МО є мережі з кількома класами повідомлень, відмінними як маршрутами, так і тривалістю обслуговування в центрах. Така мережа може бути відкритою, замкненою або змішаною. Змішана мережа МО відкрита для одних класів повідомлень, які надходять в неї ззовні і після закінчення обслуговування покидають її, і замкнена для інших класів (кількість повідомлень кожного з таких класів усередині мережі постійна).
Основні підходи до дослідження мереж МО з кількома класами базуються або на прямому методі відшукання виразів для ймовірностей станів мережі з використанням техніки складання рівнянь локального балансу, або на методі складання рекурентних рівнянь для середніх значень.
РОЗДІЛ 2. СКЛАДАННЯ РІВНЯНЬ ЛОКАЛЬНОГО БАЛАНСУ ДЛЯ МЕРЕЖ МО
2.1 ОДНОРІДНІ ЕКСПОНЕНЦІАЛЬНІ МЕРЕЖІ
Опис математичного дослідження мереж МО доцільно почати з методів дослідження простих однорідних експоненціальних мереж, тобто мереж МО, в яких функції розподілу тривалості обслуговування в центрах є експоненціальними, а вхідні потоки повідомлень — пуассонівськими (якщо мережа є відкритою). Саме для мереж цього типу, був відзначений чудовий факт, що полягає у тому, що стаціонарна імовірність станів мережі має мультиплікативну форму. Цей факт є основою для подальших аналітичних досліджень більш загальних мереж МО, а також розробки ефективних алгоритмів розрахунку характеристик мереж МО.
2.1.1 РІВНЯННЯ ГЛОБАЛЬНОГО БАЛАНСУ ДЛЯ ЗАМКНЕНИХ МЕРЕЖ
Розглянемо однорідну замкнену мережу МО з багатолінійними центрами, дисципліною обслуговування ПППО, в якій циркулюють N повідомлень відповідно до матриці маршрутів
. Тривалість обслуговування повідомлення приладом i-го центру розподілена за експоненціальним законом з параметром 
, так, що загальна інтенсивність обслуговування будь-якого центру визначається виразом (1.1.1). Розглянемо багатовимірний випадковий процес