Мультипликативность стаціонарного розподілу у відкритих мережах з багаторежимних стратегіями

Курсова робота

"Мультипликативность стаціонарного розподілу у відкритих мережах з багаторежимних стратегіями обслуговування"

Введення

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

На початку XX століття данський учений А.К. Ерланг, що працював на копенгагенської телефонної станції, поставив і вирішив ряд нових математіческтх завдань, що дозволили оцінювати характеристики телефонних і телеграфних ліній зв'язку. Це сприяло виникненню нового напряму в теорії ймовірностей - теорії масового обслуговування. На початковій стадії свого розвитку теорія масового обслуговування мала справу з системами масового обслуговування, які описуються потоками однорідних заявок, що надходять у систему, процедурами обслуговування за допомогою одного або декількох каналів, процедурами формування черг і способами організації процесу очікування заявок. Суворе науковий опис випадкових процесів у теорії масового обслуговування та їх всебічне дослідження вперше було здійснено А.Я. Хинчина. Він досліджував одноканальну систему з очікуванням, найпростішим вхідним потоком і рекурентним обслуговуванням, встановивши для неї так званий основний закон стаціонарної черги: стаціонарний розподіл числа заявок в системі збігається з їх стаціонарним розподілом у випадкові моменти догляду заявок із системи. Великий внесок у розвиток теорії масового обслуговування внесли Ю.К. Бєляєв, О.О. Боровков, Б.В. Гнеденко, М. Джейсуолл, Дж.Р. Джексон, Ф.П. Келлі, Дж. Кендалл, Дж.Ф.С. Кінгмен, Л. Клейнрок, Г.П. Клімов, І.М. Коваленко, С. Пальм, Ф. Поллачек, Ю.В. Прохоров, Дж. Ріордан, Т. Сааті, В.Л. Сміт і ін

У 1957 р. Дж.Р. Джексон вперше ввів в розгляд поняття відкритої мережі масового обслуговування ([99]), а в 1967 р. Гордон і Ньюелл ввели аналогічне поняття замкнутої мережі ([91]). На відміну від системи масового обслуговування мережа являє собою більш складне утворення, що складається з систем масового обслуговування, званих вузлами мережі, які взаємодіють між собою за допомогою деякого імовірнісного механізму. У відкритих мережах заявки можуть надходити ззовні, а також йти з мережі. У замкнутих мережах зберігається постійне число заявок, які за допомогою випадкової маршрутизації можуть переміщатися між вузлами мережі; при цьому надходження заявок в мережу і догляд заявок з мережі неможливі.

Результати Джексона і Гордона-Ньюелла не використовувалися до тих пір, поки в 1971 р. Ф.Р. Мур [115] не виявив, що замкнуті мережі адекватно описують обчислювальні системи з багатьма ресурсами. З цього моменту теорія мереж обслуговування стала швидко розвиватися за допомогою завдань, пов'язаних з математичним моделюванням мультипрограмних обчислювальних систем і аналізом їх продуктивності, з проектуванням і аналізом мереж передачі даних та мереж ЕОМ. Додатковий поштовх до подальшого розвитку теорії дала розробка і використання в повсюдної практиці різних глобальних і локальних мереж таких, наприклад, як EZERNET, INTERNET і т.д. Значний внесок у розвиток теорії мереж внесли Г.П. Башарін, А.А. Боровков, Е. Геленбе, Дж. Джексон, В.А. Івницький, Ф.П. Келлі, Д. Кеніг, Л. Клейнрок, Ю.В. Малінковскій, М. Міязава, Б. Меламед, Р. Мюнтц, С.Е.М. Перс, П.К. Поллетт, О.М. Рибко, Р. Серфозо, Ю.М. Сухов, П. Тейлор, А.Л. Толмачов, Д. Тоуслі, П. Уиттли, Дж. Уолренд, Г.І. Фалін, В. Хендерсон, Х. Чао, К. Ченду, Р. Шассбергер і багато інших.

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

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

1. Основна модель

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

Постановка завдання

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

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

У мережу, що складається з однолінійних вузлів, надходить стаціонарний Пуассонівський потік заявок з параметром . Кожна заявка вхідного потоку незалежно від інших заявок з імовірністю направляється в -Й вузол . Заявка, обслужених у -Му вузлі, миттєво з імовірністю направляється в -Й вузол, а з ймовірністю залишає мережу У -Му вузлі знаходиться єдиний прилад, який може працювати в режимах. Стан -Го вузла характеризується парою чисел , Де - Число заявок в -Му вузлі, - Номер режиму, в якому працює прилад у -Му вузлі . Тривалість обслуговування приладом -Го вузла, що знаходиться в стані , Має показове розподіл з параметром , Що залежать від стану (тобто від числа заявок у вузлі і режиму його роботи). Назвемо 0 основним режимом роботи. Час перебування в основному режимі роботи має показове розподіл з параметром , Після чого прилад переходить в режим 1. Для станів , У яких , Час перебування в режимі також має показове розподіл, при цьому з інтенсивністю прилад -Го вузла переходить в режим , А з інтенсивністю - У режим . Час перебування в останньому -М режимі має показове розподіл з параметром , Після чого прилад переходить в -Й режим. Під час перемикання приладу з одного режиму роботи на інший число заявок у вузлі не змінюється.

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

Стан мережі в момент часу будемо характеризувати вектором , Де - Стан -Го вузла в момент часу . Відповідно до вищесказаного тут - Число заявок в -Му вузлі в момент , - Номер режиму роботи -Го вузла в момент .

Припустимо, що , Якщо і , Якщо , Якщо і , Якщо , Якщо і , Якщо , А рівняння трафіку

має єдине рішення для якого (Для цього достатньо, щоб матриця , Де , Була непріводімий). Тоді - Непріводімий марковський процес на фазовому просторі , Де .

Мета 2.1 складається у встановленні умов ергодичності та з'ясуванні необхідних і достатніх умов, при яких стаціонарне фінальне розподіл процесу , Де , Представляється у мультиплікативної формі

де залежить тільки від стану -Го вузла.

Відзначимо, що інтенсивності переходу процесу зі стану в стан рівні

для всіх інших станів вони дорівнюють нулю. Тут - Вектор, всі координати якого дорівнюють нулю крім - Вектор, всі координати якого дорівнюють нулю крім - Індикатор безлічі .

Аналіз ізольованого вузла

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

Для «заявки-зберігаючих» систем масового обслуговування (тобто для яких збігаються середні інтенсивності надходження та догляду заявок) один з можливих способів визначення квазіобратімості виглядає наступним чином. Якщо на вхід системи спрямовувати найпростіший потік заявок з параметром , То система називається квазіобратімой, якщо

Тут - Частина інтенсивності переходу системи зі стану в стан , Обумовлена обслуговуванням заявок. Нагадаємо, що система називається оборотною, якщо для будь-яких її станів і

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

Для розглянутої нами завдання умова квазіобратімості (2.1.9) приймає вигляд

а умова оборотності (2.1.10) - форму

Лемма 1.1 [43, C.131]. Якщо для даної системи вхідний потік є найпростішим, то оборотність і квазіобратімость еквівалентні.

Д о к о з а тобто л ь с т в о. Досить показати, що при виконанні (2.1.3) - (2.1.8) з (2.1.11) випливає (2.1.12). Спочатку доведемо, що для всіх виконується (2.1.12) при , Тобто рівність

При співвідношення (2.1.13) випливає з (2.1.3) і співвідношення (2.1.11), в якому . Припустимо, що (2.1.13) виконується для деякого , Тобто

Тоді з (2.1.4) з урахуванням (2.1.14) і (2.1.11) при слід (2.1.9). Отже, (2.1.9) доведено за допомогою індукції по .

Тепер доведемо, що для всіх виконується (2.1.12) при . При співвідношення (2.1.12) випливає з (2.1.6) і (2.1.11). Припустимо, що (2.1.12) вірно для деякого , Тобто

Тоді (2.1.12) випливає з (2.1.7), (2.1.11) і (2.1.15). Лема доведена.

Лемма 1.2 [43, C.131]. Для квазіобратімості ізольованого вузла необхідно і достатньо виконання умов

При виконанні (2.1.16) для ергодичності достатньо, щоб

Фінальне стаціонарний розподіл процесу визначається співвідношеннями

де передбачається, що твір, в якому нижній індекс більше верхньої, дорівнює одиниці, а

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

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

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

Для розглянутого нами блукання (2.1.20) перетворюється в (2.1.16), що доводить перше твердження леми 2.2.

З (2.1.11) випливає, що

а з (2.1.12) випливає, що

Підстановка (2.1.23) у (2.1.22) доводить (2.1.18). Достатність збіжності ряду (2.1.17) для ергодичності випливає з теореми Фостера . Лемма 2.2 доведена.

Стаціонарний розподіл мережі

Дотримуючись [32,33], -Й вузол назвемо термінальним або крайовим, якщо . Основний результат формулюється наступним чином.

Теорема 1.1 [43, C.132]. Для того, щоб стаціонарний розподіл відкритої мережі з багаторежимних стратегіями обслуговування у вузлах уявлялося у формі твору (2.1.2), необхідно і достатньо, щоб у нетермінальних вузлах виконувалася умова

При виконанні цієї умови для ергодичності марківського процесу , Що описує поведінку мережі, достатньо, щоб сходився ряд

де - Позитивне рішення рівняння трафіку (2.1.1),

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

Д о к о з а тобто л ь с т в о. У для відкритих мереж з «заявкосохраняющімі» вузлами встановлено, що для мультипликативности стаціонарного розподілу необхідно і достатньо, щоб нетермінальні вузли були квазіобратімимі. Тому, з урахуванням умови квазіобратімості (2.1.16) для ізольованого вузла, яке для вузла з номером приймає форму (2.1.24), має місце перше твердження теореми.

Доведемо, що при виконанні умови (2.1.24) процес ергодічен. Як зазначалося раніше, неприводим. Залишається скористатися ергодичної теоремою Фостера , Згідно з якою досить перевірити, що система рівнянь

де - Інтенсивність переходу зі стану в стан ; , Обумовлена за допомогою (2.1.26), - інтенсивність виходу зі стану , Має нетривіальне рішення таке, що . Дійсно, беручи , Де визначається (2.1.2), отримаємо, що (2.1.27) перетворюються в глобальні рівняння рівноваги для мережі, яким задовольняє. А низка збіжний, оскільки його члени відрізняються від членів ряду (2.1.25) постійним множником.

Зауваження 2.1. Відзначимо, що для ергодичності марківського процесу досить зажадати виконання наступних двох умов, що гарантують виконання (2.1.25):

1) сходиться ряд

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

Зауваження 2.2. Якщо умова (2.1.24) виконано у всіх вузлах і ряд (2.1.25) сходиться, то виходить простий алгоритм для знаходження стаціонарних ймовірностей:

1. Вирішується система лінійних рівнянь (2.1.1).

2. Перевіряється виконання умови (2.1.24).

3. Визначається за формулою (2.1.26) і перевіряється збіжність ряду (2.1.25).

4. Визначаються за допомогою співвідношення

де

(Формули (2.1.28), (2.1.29) виходять з (2.1.18), (2.1.19) з урахуванням персоніфікації -Го вузла і того, що на нього в ізоляції направляється найпростіший потік з параметром ).

5. Знаходиться стаціонарний розподіл станів мережі за допомогою формули (2.1.2).

При цьому нормування ймовірностей можна проводити не разів, як це робилося в пункті 4, а один раз, виходячи з умови . Відзначимо також, що якщо в мережі є термінальні вузли, в яких умова (2.1.24) не виконується, то алгоритм істотно ускладниться, тому що в цих вузлах не можна застосувати (2.1.28), (2.1.29). Тому для таких вузлів необхідно додати процедуру чисельного рішення системи рівнянь (2.1.3) - (2.1.8) з подальшою його нормуваннями.

Зауваження 2.3. Неважко зрозуміти, що спільне стаціонарний розподіл чисел заявок у вузлах має наступну форму:

де

а спільне стаціонарний розподіл режимів роботи вузлів - форму:

де

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

Нехай - Частина виходить з -Го вузла потоку заявок, які покидають мережу - Підмножина нетермінальних вузлів . З леми 2.2 і результатів роботи випливає

Слідство 1.1 [43, C.133]. Потоки є незалежними пуасонівськими потоками з параметрами відповідно.

Зауважимо, що якщо умові (2.1.23) підпорядковуються всі вузли, то - Незалежні пуассоновский потоки.

2 Мережі з перемиканням режимів при певній кількості заявок у вузлі

Нехай , Де - Вектор, всі координати якого дорівнюють нулю крім - Вектор, всі координати якого дорівнюють нулю крім . На фазовому просторі заданий багатовимірний марковський процес , Де , Своїми інфінітезимального інтенсивностями переходу

Інтенсивності переходу зі стану в усі стану, відмінні від перерахованих вище, вважаються рівними нулю. Тут , Якщо і , Якщо і і .

Марківський процес описує відкриту мережу з найпростішим вхідним потоком з параметром і ймовірністю напрямки надходить заявки в -Й вузол. У -Му вузлі знаходиться єдиний експонентний прилад з інтенсивністю обслуговування , Що залежить від стану вузла. Заявка, обслужених у -Му вузлі, переходить з імовірністю в -Й вузол, а з ймовірністю залишає мережу. Компонента висловлює число заявок в -Му вузлі, а компонента - Номер режиму роботи приладу. Прилад -Го вузла може працювати в режимах з показово розподіленим часом перебування в них; - Інтенсивність збільшення номера режиму на одиницю, - Інтенсивність зменшення номера режиму на одиницю.

Глобальні рівняння рівноваги для стаціонарних ймовірностей цього марківського процесу мають наступну форму:

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

Нехай - Позитивне рішення рівняння трафіку

Розглянемо марковський процес на фазовому просторі , Заданий інфінітезимального інтенсивностями

для всіх інших станів вважаємо, що . Процес описує ізольований вузол у фіктивній навколишньому середовищу, в якій на вузол надсилається стаціонарний Пуассонівський потік з параметром , Де знайдено з рівняння трафіку (2.2.1). Рівняння рівноваги для стаціонарних ймовірностей марківського процесу, що описує такий вузол, мають такий вигляд:

для

Ми зв'яжемо стаціонарний розподіл процесу зі стаціонарними розподілами процесів і будемо цікавитися необхідними і достатніми умовами виконання рівності

Лемма 2.3. Якщо для даної системи вхідний потік є найпростішим, то оборотність і квазіобратімость еквівалентні.

Д о к о з а тобто л ь с т в о. Для ізольованого вузла умова квазіобратімості (2.1.9) приймає вигляд

а умова оборотності (2.1.10) - форму

і для

Досить показати, що при виконанні (2.2.2) - (2.2.7) з (2.2.9) випливає (2.2.10). Нехай при деякому фіксованому . Доведемо, що тоді для всіх виконується (2.2.10). При співвідношення (2.2.10) випливає з (2.2.4) і співвідношення (2.2.9) для станів і . Припустимо, що (2.2.10) виконується для деякого , Тобто

Тоді з (2.2.5) з урахуванням (2.2.11) і (2.2.9) для станів і випливає (2.2.10). Отже, (2.2.10) доведено за допомогою індукції по . Лема доведена.

Лемма 2.4 [45, C.184]. Для квазіобратімості ізольованого -Го вузла необхідно і достатньо виконання умов

а) для при деякому

б) для всіх

При виконанні (2.2.12) для ергодичності достатньо, щоб сходився ряд

де . Фінальне стаціонарний розподіл процесу визначається співвідношеннями

де передбачається, що твір, в якому нижній індекс більше верхньої, дорівнює одиниці, а

Д о к о з а тобто л ь с т в о. Розглянемо випадкове блукання по точках з цілочисельними координатами першого квадранта площині, що задається рівняннями (2.2.2) - (2.2.7). Як уже раніше говорилося, для оборотності стаціонарного марківського процесу необхідно і достатньо, щоб виконувалося циклічне умова Колмогорова: для будь-яких різних станів

Більш того, відомо, що для оборотності достатньо, щоб умова (2.2.18) виконувалося для будь-яких замкнутих шляхів з в без самоперетинів. Рівність (2.2.12) є умова Колмогорова (2.2.18) для четирехзвенниє колій, що проходять через вершини елементарного квадрата і йдуть з в за і проти годинникової стрілки. Рівність (2.2.13) є умова Колмогорова для -Ланках колій, що проходять через вершини прямокутника і провідних фахівців із в за і проти годинникової стрілки. Це доводить необхідність умов (2.2.12) і (2.2.13) для оборотності, а значить (по лемі 2.3) квазіобратімості ізольованого вузла у фіктивній навколишньому середовищу. Припустимо, що (2.2.12), (2.2.13) виконані. Будь-який замкнутий шлях з в без самоперетинів або а) представляє собою деяку однозвенная замкнуту дугу, або б) проходить по межі деякої фігури, складеної з кінцевого числа примикають один до одного елементарних квадратів і визначених вище - Ланки прямокутників. Для випадку а) циклічне умова (2.2.18) виконується автоматично. У випадку б) перемножимо рівності (2.2.12) для всіх елементарних квадратів і рівності (2.2.13) для всіх прямокутників, з яких складається згадана фігура. Так як прямокутники можуть стикатися лише «довгими» сторонами, то при цьому інтенсивності переходу для тих спрямованих дуг, які не належать кордоні фігури, увійдуть множниками як в ліву, так і в праву частини. Після скорочення на них вийде циклічне умова (2.2.18) для шляхів, що йдуть по межі фігури за і проти годинникової стрілки. Достатність умов (2.2.12) і (2.2.13) доведена.

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

Доведемо, що стаціонарний розподіл ізольованого вузла у фіктивній навколишньому середовищі має форму (2.2.15), (2.2.16). Вважаючи в (2.2.10) отримаємо:

звідки отримуємо

З (2.2.9) для знаходимо, що

Для таких же з (2.2.9) також випливає, що

зокрема,

Підставляючи (2.2.21) у (2.2.19), а потім підставляючи отримане рівність в (2.2.20), будемо мати для

Тим самим доведено (2.2.15).

Для з (2.2.9) випливає, що

Вважаючи в (2.2.10) , Отримаємо:

звідки

Далі, з (2.2.9)

Підставляючи (2.2.24) у (2.2.23), а потім отримане рівність в (2.2.22), для будемо мати

Таким чином, (2.2.16) доведено.

Нарешті, (2.2.17) випливає з того, що сума всіх стаціонарних ймовірностей дорівнює одиниці:

Достатність збіжності ряду (2.2.14) для ергодичності випливає з теореми Фостера . Лемма 2.4 доведена повністю.

Основний результат 2.2 полягає в наступному.

Теорема 2.2. [45, C.184] Для виконання (2.2.8) необхідно і достатньо, щоб у нетермінальних вузлах виконувалися умови (2.2.12), (2.2.13). При виконанні цієї умови для ергодичності марківського процесу , Що описує поведінку мережі, достатньо, щоб сходився ряд

де

При цьому в нетермінальних вузлах стаціонарний розподіл процесу має форму (2.2.15) - (2.2.17).

Д о к о з а тобто л ь с т в о. У для відкритих мереж з «заявкосохраняющімі» вузлами встановлено, що для мультипликативности стаціонарного розподілу необхідно і достатньо, щоб нетермінальні вузли були квазіобратімимі. Тому, з урахуванням умови квазіобратімості (2.1.16) для ізольованого вузла, яке в силу леми 2.4 для вузла з номером приймає форму (2.2.12), (2.2.13) має місце перше твердження теореми.

Доведемо, що при виконанні умови (2.2.25) процес ергодічен. Як зазначалося раніше, неприводим. Залишається скористатися ергодичної теоремою Фостера , Згідно з якою досить перевірити, що система рівнянь

де - Інтенсивність переходу зі стану в стан ; , Обумовлена за допомогою (2.2.26), - інтенсивність виходу зі стану , Має нетривіальне рішення таке, що . Дійсно, беручи , Де визначається (2.2.8), отримаємо, що (2.2.27) перетворюються в глобальні рівняння рівноваги для мережі, яким задовольняє. А низка збіжний, оскільки його члени відрізняються від членів ряду (2.2.25) постійним множником.

Зауваження 2.3. Відзначимо, що для ергодичності марківського процесу досить зажадати виконання наступних двох умов, що гарантують збіжність ряду (2.2.25):

для всіх

1) сходяться ряди

Зауваження 2.4. Якщо умови (2.2.12), (2.2.13) виконані у всіх вузлах і ряд (2.2.25) сходиться, то виходить простий алгоритм для знаходження стаціонарних ймовірностей:

1. Вирішується система лінійних рівнянь (2.2.1).

2. Перевіряється виконання умов (2.2.12), (2.2.13).

3. Визначається за формулою (2.2.26) і перевіряється збіжність ряду (2.2.25).

4. Визначаються за допомогою співвідношень (2.2.15) - (2.2.17).

5. Знаходиться стаціонарний розподіл станів мережі за допомогою формули (2.2.8).

При цьому нормування ймовірностей можна проводити не разів, як це робилося в пункті 4, а один раз, виходячи з умови . Відзначимо також, що якщо в мережі є термінальні вузли, в яких умови (2.2.12), (2.2.13) не виконуються, то алгоритм істотно ускладниться, тому що в цих вузлах не можна застосувати (2.2.15) - (2.2.17 ). Тому для таких вузлів необхідно додати процедуру чисельного рішення системи рівнянь (2.2.2) - (2.2.7) з подальшою його нормуваннями.

Зауваження 2.5. Неважко зрозуміти, що спільне стаціонарний розподіл чисел заявок у вузлах має наступну форму:

де

а спільне стаціонарний розподіл режимів роботи вузлів - форму:

де

Тут - Число індексів, таких, що

яке, як згадувалося вище, звичайно або лічильно.

Нехай - Частина виходить з -Го вузла потоку заявок, які покидають мережу - Підмножина нетермінальних вузлів . З леми 2.4 і результатів роботи випливає

Слідство 2.2. Потоки є незалежними пуасонівськими потоками з параметрами відповідно.

Зауважимо, що якщо умовами (2.2.12), (2.2.13) підпорядковуються всі вузли, то - Незалежні пуассоновский потоки.

3. Приклади відкритих мереж з перемиканням режимів

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

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

Слідство 2.3. Для того, щоб стаціонарний розподіл марківського процесу уявлялося в мультиплікативної формі (2.2.8), необхідно і достатньо, щоб у всіх нетермінальних вузлах мережі виконувалися умови

Множники в (2.2.8) мають форму

де

У наступних двох випадках стаціонарне розподіл завжди має форму твору, оскільки марковський процес, що описує ізольований вузол у фіктивній навколишньому середовищу, звернемо. Тому не треба накладати ніяких обмежень типу (2.2.12), (2.2.13).

Випадок . Прилад може перемикатися з одного режиму роботи на інші тільки тоді, коли у вузлі немає заявок: для виконується при і при . Крім того для всіх виконується . Це відповідає тому, що в моделі з 2.2 покладається .

Слідство 2.4. Марківський процес ергодічен, а його стаціонарний розподіл представляється у мультиплікативної формі (2.2.8), множники в якій мають форму

де

Випадок . Перехід з одного режиму роботи приладу на інші можливий тільки тоді, коли в -Сайті знаходиться певна кількість заявок : Для виконується при і при . Крім того для всіх виконується . Це відповідає тому, що в моделі з 2.2 покладається .

Слідство 2.5. Марківський процес ергодічен, а його стаціонарний розподіл представляється у мультиплікативної формі (2.2.8), множники в якій мають форму

де

Висновок

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

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

Список використаних джерел

1. Анісімов BB, Лебєдєв Є.О. Стохастичні мережі обслуговування. Марковські моделі. - Київ: Либідь, 1992. - 205 с.

2. Башарін Г.П., Бочаров П.П., Коган Я.А. Аналіз черг в обчислювальних мережах. - М.: Наука. - 1989. - 336 с.

3. Башарін Г.П., Толмачов А.Л. Деякі результати теорії мереж масового обслуговування / / Методи розвитку теорії телетрафіка. - М. - 1970. - С. 52-65.

4. Башарін Г.П., Толмачов А.Л. Теорія мереж масового обслуговування та її застосування до аналізу інформаційно-обчислювальних систем / / Підсумки науки і техніки. - М., 1983. - Т.21. - С. 3-119. - (Сер. Теорія ймовірностей. Матем. Статистика. Теор. Кібернетика / ВІНІТІ).

5. Бочаров П.П., Печінкін А.В. Теорія масового обслуговування: Підручник. - М.: РУДН, 1995. - 529 с.

6. Гіхмана І.І., Скороход А.В. Введення в теорію випадкових процесів. - М.: Наука, 1977. - 568 с.

7. Горців А.М., Назаров А.А., терпуг А.Ф. Управління та адаптація в системах масового обслуговування. - Томськ: ТГУ, 1978. - 208 с.

8. Добрушино Р.Л., Кельберт М.Я., Рибко О.М., Сухов Ю.М. Якісні методи теорії мереж з чергами / / Препринт. - М., 1986. - 50 с. - (ІППІ АН СРСР).

9. Євдокимович В.Є., Малінковскій Ю.В. Мережі масового обслуговування з динамічною маршрутизацією і динамічними імовірнісними обходами вузлів заявками / / Проблеми передачі інформації. - 2001. - Том 37, вип. 3. - С. 55-66.

10. Жожікашвілі В.А., Вишневський В.М. Мережі масового обслуговування. Теорія та застосування до мереж ЕОМ. - М.: Радіо і зв'язок. - 1988. - 192 с.

11. Івницький В.А. Мережі масового обслуговування та їх застосування в ЕОМ / / Зарубіжна радіоелектроніка. - 1977. - № 7. - С. 33-70.

12. Івницький В.А. Про умови незалежності стаціонарних ймовірностей станів розімкнутої мережі однолінійних систем з втратами від виду розподілів тривалостей обслуговування / / Известия АН СРСР. Технічна кібернетика. - 1981. - № 4. - С. 136-140.

13. Івницький В.А. Про умови інваріантності стаціонарних ймовірностей для мереж масового обслуговування / / Теорія ймовірностей та її застосування. - 1982. - Т. 27, № 1. - С. 188-192.

14. Івницький В.А. Про інваріантності стаціонарних ймовірностей станів для замкнутих мереж однолінійних СМО / / ДАН УРСР. А. - 1989. - № 7. - С. 8-11.

15. Івницький В.А. Про умови інваріантності стаціонарних ймовірностей станів для мереж однолінійних СМО / / Теорія ймовірностей та її застосування. - 1989. - Т. 34, № 3. - С. 576-580.

16. Івницький В.А. Про інваріантності стаціонарних ймовірностей станів для мереж Багатолінійні систем масового обслуговування з абсолютним пріоритетом надходить вимоги і дообслужіваніем / / Дослідження систем і мереж масового обслуговування: Тез. докл. 12 й Бел. зимової школи-семінару з ТМО, Гродно, січень-берез. 1996 р. / Бел. держ. унів. - Мінськ, 1996. - С. 36-37.