Відкриті мережі з багаторежимних стратегіями обслуговування та інформаційними сигналами

Міністерство освіти Республіки Білорусь

Заклад освіти

«Гомельський державний університет ім. Ф. Скорини »

Математичний факультет

Кафедра ТБ і мат статистики

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

ВІДКРИТІ МЕРЕЖІ З Багаторежимний Стратегія обслуговування І Інформаційні сигнали

Виконавець:

Студент групи М-32 Левашов А.Ю.

Науковий керівник:

Канд. фіз-мат. наук, доцент

Малінковскій М.Т.

Гомель 2007

ЗМІСТ

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ

ВСТУП

1. ВІДКРИТІ МЕРЕЖІ З Багаторежимний Стратегія обслуговування і негативні ЗАЯВКАМИ

2. ВІДКРИТІ МЕРЕЖІ З Багаторежимний Стратегія обслуговування І Інформаційні сигнали ДВОХ ТИПІВ

ВИСНОВОК

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

ПЕРЕЛІК УМОВНИХ ПОЗНАЧЕНЬ

- Число вузлів в мережі масового обслуговування, розмірність вектора станів марківського процесу, що описує мережу;

- Число заявок, що циркулюють в замкнутій мережі;

- Матриця маршрутизації для відкритої мережі;

- Матриця маршрутизації для замкнутої мережі;

- Стан -Го вузла;

- Число заявок в -Ом вузлі ( для відкритої мережі, для замкнутої мережі);

- Номер режиму роботи приладу в -М вузлі ;

- Стан -Го вузла в момент часу ;

- Число заявок в -М вузлі в момент часу ;

- Номер режиму роботи приладу в -М вузлі в момент часу ;

- Стан мережі масового обслуговування;

- Марковський процес, що описує стан мережі масового обслуговування в момент часу ;

- Марковський процес, що описує стан ізольованого вузла в фіктивної навколишньому середовищі;

- Простір станів випадкового процесу і марківського процесу у випадку відкритої мережі;

- Простір станів випадкового процесу і марківського процесу у разі замкнутої мережі;

- Простір станів марківського процесу для відкритої мережі та для замкнутої мережі);

- Інтенсивність переходу марківського процесу з безперервним часом і не більше ніж рахунковим простором станів зі стану в стан ;

- Інтенсивність виходу марківського процесу зі стану ;

- Стаціонарний розподіл марківського процесу .

- Стаціонарний розподіл марківського процесу у випадку відкритої мережі;

- Стаціонарний розподіл марківського процесу у разі замкнутої мережі;

- Інтенсивність пуассонівського потоку, що надходить у відкриту мережу;

- Інтенсивність пуассонівського потоку позитивних заявок;

- Інтенсивність пуассонівського потоку негативних заявок (сигналів);

- Інтенсивність пуассонівського потоку сигналів, що збільшують номер режиму;

- Інтенсивність пуассонівського потоку сигналів, які зменшують номер режиму;

- Інтенсивність обслуговування приладом -Го вузла, що знаходиться в стані ;

- Інтенсивність переходу приладу -Го вузла з режиму на режим ;

- Інтенсивності потоків позитивних заявок, негативних сигналів, сигналів збільшення номера режиму, сигналів зменшення номера режиму відповідно в -Й вузол відкритої мережі;

- Ймовірності напрями в -Й вузол надходять у відкритий мережа позитивних заявок, негативних сигналів, сигналів зменшення номера режиму, сигналів збільшення номера режиму відповідно;

- Ймовірності для заявки, обслужених у -М вузлі, перейти в -Й вузол з перетворенням її в позитивну заявку, негативний сигнал, сигнал зменшення номера режиму, сигнал збільшення номера режиму відповідно;

- Індикатор події , Що дорівнює 1, якщо відбувається, і рівний 0, якщо не відбувається.

ВСТУП

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

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

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

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

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

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

1. ВІДКРИТІ МЕРЕЖІ З Багаторежимний Стратегія обслуговування і негативні ЗАЯВКАМИ

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

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

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

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

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

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

Лемма 1.1 [54, C.91]. Система рівнянь (4.1.1), (4.1.2) має рішення

Доказ. Так як - Безперервна функція від і , То доказ випливає з результату [90], отриманого в цій роботі за допомогою теореми Брауера про нерухому точку.

Надалі будемо припускати, що існує рішення (4.1.1), (4.1.2), для якого все . Для того, щоб це виконувалося, треба накласти деякі умови на маршрутизацію заявок в мережі. Наприклад, таке рішення буде свідомо існувати, якщо при кожному виконується умова . Насправді можна накласти набагато менш жорсткі умови. Усюди надалі під словами рішення (4.1.1), (4.1.2) буде розумітися саме таке рішення. Це припущення гарантує неприводимого марківського процесу на фазовому просторі , Де .

Ізольований вузол у фіктивній довкіллю.

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

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

З цих рівнянь легко визначаються стаціонарні ймовірності станів ізольованого вузла в фіктивної навколишньому середовищі:

де

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

Згідно ергодічеськой теоремі Фостера [82] для ергодичності марківського процесу, що описує ізольований вузол в фіктивної навколишньому середовищу, досить існування нетривіального неотрицательного рішення системи рівнянь рівноваги такого, що

Якщо

то в силу (4.1.6) ряд сходиться як сума геометричної прогресії зі знаменником, меншим одиниці. При виконанні умови

інтенсивність виходу зі стану обмежена:

Тому при виконанні умов

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

Основний результат. Нехай - Інтенсивність переходу процесу зі стану в стан , - Інтенсивність його виходу зі стану , - Вектор , У якого всі крім рівні 0, а , І все , - Вектор , У якого всі і все крім рівні 0, а . Очевидно, інтенсивності переходу процесу мають такий вигляд:

для всіх інших станів виконується .

Інтенсивність виходу виходить складанням цих інтенсивностей:

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

Теорема 1.1. [54, C.92], [55, C.180] Якщо для всіх виконуються умови (4.1.3) і нерівності (4.1.7), то марковський процес ергодічен, а його фінальне стаціонарний розподіл має форму твори

де - Стаціонарний розподіл ізольованого -Го вузла в фіктивної навколишньому середовищі, яке визначається за допомогою співвідношень (4.1.6).

Доказ. Для доказу того, що , Визначені в (4.1.15), утворюють стаціонарний розподіл марківського процесу , Достатньо [94,97,103] підібрати функцію

яка задовольняла б співвідношенням

Якщо такі вдасться знайти (див. [94,97,103]), то виявиться, що будуть інфінітезімальнимі інтенсивностями переходу для зверненої в часі ланцюга Маркова , А - Стаціонарними ймовірностями для і . Покладемо

для всіх інших станів покладемо . Для функції співвідношення (4.1.16) дійсно виконується, що легко перевіряється підстановкою в нього рівностей (4.1.8) - (4.1.13), (4.1.18) - (4.1.23) і використання (4.1.4), (4.1. 5). Залишається довести (4.1.17). Складаючи (4.1.18) - (4.1.23), одержимо, що

Використовуючи (4.1.1) - (4.1.2), маємо

Застосовуючи знову (4.1.1) - (4.1.2), а також властивості індикаторів, отримаємо

Порівнюючи отриманий результат з (4.1.14), робимо висновок, що для будь-якого стану . Доведемо, що при виконанні умов (4.1.7) марковський процес ергодічен. Згідно ергодічеськой теоремі Фостера [82], для цього достатньо довести, що існує нетривіальне невід'ємне рішення рівнянь глобальної рівноваги

таке, що ряд сходиться. Складаючи (4.1.16) за всіма , Переконуємося, що є рішенням (4.1.24). З (4.1.14) випливає, що

Оскільки ряд

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

За ергодічеськой теоремі Фостера це означає, що марковський процес ергодічен. Таким чином, теорема доведена повністю.

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

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

2. Вирішується система нелінійних рівнянь (4.1.1) - (4.1.2).

3. Перевіряється виконання (4.1.7).

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

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

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

Неважко переконатися, складаючи (4.1.15) по всіх можливих значень , Що спільне стаціонарний розподіл чисел позитивних заявок у вузлах має наступну форму:

де кожен множник має геометричне розподіл

Твірна функція стаціонарного розподілу числа заявок в -М вузлі має вигляд

а -Й факторіальних момент є

Як і слід було очікувати, в стаціонарному режимі середнє число позитивних заявок і дисперсія числа позитивних заявок в кожному вузлі,

прагнуть до нуля, коли завантаження цього вузла

Точно так само, складаючи (4.1.15) по всіх можливих значень , Визначимо спільне стаціонарний розподіл режимів у вузлах мережі:

де

Середній номер режиму роботи -Го вузла в стаціонарній мережі знаходиться як

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

2. ВІДКРИТІ МЕРЕЖІ З Багаторежимний Стратегія обслуговування І Інформаційні сигнали ДВОХ ТИПІВ

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

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

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

Цей процес описує мережу, що складається з однолінійних вузлів, в яку надходять чотири незалежних стаціонарних пуассонівського потоку: позитивних заявок з параметром , Негативних сигналів з параметром , Сигналів зменшення режиму з параметром , Сигналів збільшення режиму з параметром . Надходження негативного сигналу в вузол зменшує число заявок в ньому на одиницю, якщо число заявок у вузлі більше нуля, і не робить ніяких змін, якщо у вузлі немає заявок. Сигнал зменшення режиму при вступі до -Й вузол з режимом переводить його в режим роботи , Не змінюючи числа заявок у вузлі, і не робить ніяких змін, якщо вузол знаходиться в режимі роботи 0; сигнал збільшення режиму при вступі до -Й вузол з режимом переводить його в режим роботи , Не змінюючи числа заявок у вузлі, і не робить ніяких змін, якщо вузол знаходиться в режимі роботи . Після цих операцій інформаційні сигнали пропадають, не надаючи більше впливу на мережу. Вступники позитивна заявка, негативний сигнал, сигнал зменшення і сигнал збільшення режиму направляються в -Й вузол відповідно з імовірностями . Позитивна заявка, обслужених у -М вузлі, миттєво прямує в -Й вузол, з імовірністю залишаючись позитивною, з імовірністю перетворюючись на негативний сигнал, з імовірністю - В сигнал зниження режиму, з імовірністю - В сигнал підвищення режиму, або з імовірністю покидає мережа . Тривалість обслуговування приладом -Го вузла позитивних заявок має показовий розподіл з параметром . Режими роботи та інтенсивності переходу з режиму на режим визначаються як у попередньому розділі. Стан мережі в момент часу описується так само, тільки тепер - Число позитивних заявок в -М вузлі в момент .

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

Рівняння (4.2.3) мають рішення. Дійсно, перші два рівняння в (4.2.3) збігаються з рівняннями трафіку (4.1.1), (1.1.2), які мають рішення . Очевидно, за знайденими з третього і четвертого рівнянь (4.2.3) однозначно визначаться .

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

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

З рівнянь (4.2.5) знаходимо

Вважаючи в (4.2.6) і замінюючи на , Отримаємо:

звідки

Підставляючи це в (4.2.7), маємо:

З умови нормування знаходимо, що

В силу теореми Фостера [82] для ергодичності ізольованого вузла достатньо виконання нерівностей

Доказ дослівно повторює те, що використовувалося при доказі аналогічного затвердження в 4.1.2, із заміною оцінки для наступної оцінкою:

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

Теорема 2.2. [45, C.186] Якщо для всіх виконуються умови (4.2.4) і (4.2.10), то марковський процес ергодічен, а його стаціонарний розподіл має форму твору (4.1.15), де визначаються за допомогою співвідношень (4.2.8), (4.2.9).

Доказ. Для доказу того, що , Визначені в (4.1.15), (4.2.5), (4.2.6), утворюють стаціонарний розподіл марківського процесу , Достатньо [94,97,103] підібрати функцію яка задовольняла б співвідношенням

для всіх інших станів покладемо . Для функції (4.2.11) дійсно виконується, що легко перевіряється підстановкою в нього рівностей (4.2.1), (4.2.13) і використання (4.2.8), (4.2.9). Залишається довести (4.2.12). Складаючи (4.2.13), одержимо, що

Використовуючи (4.2.3), маємо

Застосовуючи знову (4.2.3), властивості індикаторів і той факт, що , Одержимо

Порівнюючи отриманий результат з (4.2.2), робимо висновок, що для будь-якого стану .

Доведемо, що при виконанні умов (4.2.10) марковський процес ергодічен. Згідно ергодічеськой теоремі Фостера [82], для цього достатньо довести, що існує нетривіальне невід'ємне рішення рівнянь глобальної рівноваги

таке, що ряд сходиться. Складаючи (4.2.11) за всіма , Переконуємося, що є рішенням (4.2.14). З (4.2.2) випливає, що

Оскільки ряд

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

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

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

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

3. Перевіряється виконання (4.2.10).

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

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

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

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

де кожен множник має геометричне розподіл

Твірна функція стаціонарного розподілу числа заявок в -М вузлі має вигляд

а -Й факторіальних момент є

прагнуть до нуля, коли завантаження цього вузла

де

Середній номер режиму роботи -Го вузла в стаціонарній мережі знаходиться як

Аналіз виходять з мережі потоків позитивних заявок не проводився, оскільки, як і в попередньому підрозділі, такі потоки носять складний характер через нелінійності рівнянь трафіку.

ВИСНОВОК

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

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

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

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.

17. Кельберт М.Я., Сухов Ю.М. Математичні питання теорії мереж з чергами / / Підсумки науки і техніки. - М., 1988. - Т.26. - С.3-96. - (Сер. Теорія ймовірностей. Матем. Статистика. Теор. Кібернетика / ВІНІТІ).

18. Кеніг Д., Риков В.В., Шмідт Ф. Стаціонарні системи масового обслуговування з залежностями / / Підсумки науки і техніки. - М., 1981. - Т.18. - С.95-186. - (Сер. Теорія ймовірностей. Матем. Статистика. Теор. Кібернетика / ВІНІТІ).

19. Клейнрок Л. Комунікаційні мережі. - М.: Наука, 1970. - 255с.

20. Клейнрок Л. Обчислювальні системи з чергами. - М.: Мир, 1979. - 600С.

21. Климов Г.П. Стохастичні системи обслуговування. - М.: Наука, 1966. - 243с.

22. Ковальов О.О. Мережі з ненадійними каналами і резервом / / Математичні методи дослідження мереж зв'язку та мереж ЕОМ. Тези доповідей VI Білоруської школи-семінару з ТМО. - Мінськ, 1990. - С.70-71.