Курсова робота
"Замкнуті мережі з багаторежимних стратегіями обслуговування"

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

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


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



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

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



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

для

для







для і для

для

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

де - Нормуються постійна, що залежить від числа вузлів в мережі і від числа циркулюючих в ній заявок.
На відміну від відкритої мережі, тут зручніше користуватися введеної в [36,37,42] концепцією обмеженою квазіобратімості. Як там показано, для замкнутих мереж обмежена квазіобратімость дає більш широкі достатні умови для виконання (3.1.9), ніж квазіобратімость.
Лемма 1.1 [46, C.325]. Якщо для ізольованого вузла у фіктивній навколишньому середовищу вхідний потік є найпростішим, то оборотність і обмежена квазіобратімость еквівалентні.
Д о к о з а тобто л ь с т в о. Для ізольованого вузла умова обмеженою -Квазіобратімості з [36,37,42] приймає вигляд

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


і для

Досить показати, що при виконанні (3.1.2) - (3.1.8) з (3.1.10) випливає (3.1.11). Нехай при деякому фіксованому . Доведемо, що тоді для всіх виконується (3.1.11). При співвідношення (3.1.11) випливає з (3.1.4) і співвідношення (3.1.10) для станів і . Припустимо, що (3.1.11) виконується для деякого , Тобто

Тоді з (3.1.5) з урахуванням (3.1.12) і (3.1.10) для станів і випливає (3.1.11). Отже, (3.1.11) доведено за допомогою індукції по . Лема доведена.
Лемма 1.2 [46, C.325]. Для обмеженою -Квазіобратімості ізольованого -Го вузла необхідно і достатньо виконання умов
а) для при деякому

б) для всіх



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




де при остання нерівність треба замінити на .
Д о к о з а тобто л ь с т в о. Розглянемо випадкове блукання по точках з цілочисельними координатами прямокутника , Що задається рівняннями (3.1.2) - (3.1.8). Рівність (3.1.13) є циклічне умова Колмогорова (2.2.18) для четирехзвенниє колій, що проходять через вершини елементарного квадрата і йдуть з в за і проти годинникової стрілки. Рівність (3.1.14) є умова Колмогорова для -Ланках колій, що проходять через вершини прямокутника і провідних фахівців із в за і проти годинникової стрілки. Це доводить необхідність умов (3.1.13) і (3.1.14) для оборотності, а значить (по лемі 3.1) обмеженою -Квазіобратімості ізольованого вузла у фіктивній навколишньому середовищу. Припустимо, що (3.1.13), (3.1.14) виконані. Будь-який замкнутий шлях з в без самоперетинів або а) представляє собою деяку однозвенная замкнуту дугу, або б) проходить по межі деякої фігури, складеної з кінцевого числа примикають один до одного елементарних квадратів і визначених вище - Ланки прямокутників. Для випадку а) циклічне умова (2.2.18) виконується автоматично. У випадку б) перемножимо рівності (3.1.13) для всіх елементарних квадратів і рівності (3.1.14) для всіх прямокутників, з яких складається згадана фігура. При цьому інтенсивності переходу для тих спрямованих дуг, які не належать кордоні фігури, увійдуть множниками як в ліву, так і в праву частини. Після скорочення на них вийде циклічне умова (2.2.18) для шляхів, що йдуть по межі фігури за і проти годинникової стрілки. Достатність умов (3.1.13) і (3.1.14) доведена.
Доведемо, що стаціонарний розподіл ізольованого вузла у фіктивній навколишньому середовищі має форму (3.1.15), (3.1.16). Вважаючи в (3.1.11) отримаємо:

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


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

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

зокрема,

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

Тим самим доведено (3.1.15).
Для з (3.1.10) випливає, що


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

звідки

Далі, з (3.1.10)

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

Таким чином, (3.1.16) доведено для
Для з (3.1.10) випливає, що


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

звідки

Далі, з (3.1.10)

Підставляючи (3.1.26) у (3.1.25), а потім отримане рівність в (3.1.24), одержимо (3.1.16), яке таким чином доведено і для .
Так як - Непріводімий процес Маркова з кінцевим числом станів і безперервним часом, то за ергодичної теоремі Маркова [5] він є ергодичної. Лемма 3.2 повністю доведена.
Основний результат 3.1 полягає в наступному.
Теорема 1.1. [46, C.326], [53, C.159-160], [56, C.325-326] Марківський процес ергодічен. Для того, щоб його стаціонарний розподіл уявлялося у формі твору (3.1.9), достатньо, щоб у всіх вузлах мережі виконувалися умови (3.1.13), (3.1.14). При цьому множники в (3.1.9) мають форму (3.1.15), (3.1.16), в яких потрібно було, що , А постійна має вигляд:




де .
Д о к о з а тобто л ь с т в о. Так як марковський процес з безперервним часом і кінцевим числом станів є непріводімим, то він ергодічен по ергодичної теоремі Маркова [5]. В [42] для замкнутих мереж з «заявкосохраняющімі» вузлами встановлено, що для мультипликативности стаціонарного розподілу достатньо, щоб нетермінальні вузли були обмежено -Квазіобратімимі. Тому, з урахуванням умови обмеженою -Квазіобратімості для ізольованого вузла, яке в силу леми 3.2 для вузла з номером приймає форму (3.1.13), (3.1.14), має місце перше твердження теореми.
Нарешті, оскільки сума всіх стаціонарних ймовірностей повинна бути дорівнює одиниці, то підставляючи в рівність

замість твір (3.1.9) і враховуючи (3.1.15), (3.1.16), після очевидних перетворень отримаємо




звідки випливає (3.1.27). Теорема доведена.
Зауваження 3.1. Якщо умови (3.1.13), (3.1.14) виконані у всіх вузлах, то виходить наступний алгоритм для знаходження стаціонарних ймовірностей:
1. Вирішується система лінійних рівнянь (3.1.1). В якості використовуваного надалі набору береться будь-який набір із суворо позитивними координатами.
2. Перевіряється виконання умов (3.1.13), (3.1.14).
3. За формулою (3.1.27) визначається постійна нормировки .
4. Визначаються за допомогою співвідношень (3.1.15), (3.1.16).
5. Знаходиться стаціонарний розподіл станів мережі за допомогою формули (3.1.9).

Відзначимо також, що якщо в мережі є вузли, в яких умови (3.1.13), (3.1.14) не виконуються, то алгоритм істотно ускладниться, тому що в цих вузлах не можна застосувати (3.1.15), (3.1.16) . Тому для таких вузлів необхідно додати процедуру чисельного рішення системи рівнянь (3.1.2) - (3.1.8). При цьому зміниться також вираз для підрахунку унормує постійної . Відомо, що найбільш трудомістким етапом при обчисленні стаціонарного розподілу для замкнутих мереж є етап підрахунку унормує постійною. Існують різні чисельні процедури, розроблені для її обчислення, наприклад, аналіз середніх значень [10], або алгоритм, рекурентний за часом [4,10].

2. Приклади замкнутих мереж з перемиканням режимів
В 3.1 розглядалася досить загальна модель замкнутої мережі з багаторежимних стратегіями. Тут ми розглянемо декілька корисних для різних додатків приватних випадків цієї моделі. У всіх розглянутих нижче прикладах передбачається, що для виконується при і при .
Випадок . Нехай для всіх виконується для і для , А також для і для . Це відповідає тому, що в моделі з 3.1 покладається . Теорема 3.1 приймає наступний вигляд.
Слідство 2.1. Марківський процес ергодічен. Для того, щоб його стаціонарний розподіл уявлялося в мультиплікативної формі (3.1.9), достатньо, щоб у всіх вузлах мережі виконувалися умови


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

а постійна нормування має вигляд



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


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


а постійна нормування має вигляд



Випадок . Припустимо, що коли всі заявок скупчуються в одному вузлі, прилад не може переходити з одного режиму роботи на інші: при . Нехай також для всіх виконується для і для , А також для і для . Це відповідає тому, що в моделі з 3.1 покладається .
Слідство 2.3. Марківський процес ергодічен. Для того, щоб його стаціонарний розподіл уявлялося в мультиплікативної формі (3.1.9), достатньо, щоб у всіх вузлах мережі виконувалися умови


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

а постійна нормування має вигляд




Випадок . Коли у вузлі немає заявок або всі заявки скупчуються в ньому, перехід з одного режиму роботи на інші неможливий: при або . Нехай також для всіх виконується для і для , А також для і для . Це відповідає тому, що в моделі з 3.1 покладається .
Слідство 2.4. Марківський процес ергодічен. Для того, щоб його стаціонарний розподіл уявлялося в мультиплікативної формі (3.1.9), достатньо, щоб у всіх вузлах мережі виконувалися умови


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


а постійна нормування має вигляд



У наступних двох випадках стаціонарне розподіл завжди має форму твору, оскільки марковський процес, що описує ізольований вузол у фіктивній навколишньому середовищу, звернемо. Тому не треба накладати ніяких обмежень типу (3.1.13), (3.1.14).
Випадок . Прилад може перемикатися з одного режиму роботи на інші тільки тоді, коли у вузлі немає заявок: для виконується при і при . Крім того для всіх виконується . Це відповідає тому, що в моделі з 3.1 покладається .
Слідство 2.5. Марківський процес ергодічен, а його стаціонарний розподіл представляється у мультиплікативної формі (3.1.9), множники в якій мають форму

а постійна нормування має вигляд


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


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

Висновок

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

Література
1. Кеніг Д., Риков В.В., Шмідт Ф. Стаціонарні системи масового обслуговування з залежностями / / Підсумки науки і техніки. - М., 1981. - Т.18. - С. 95-186. - (Сер. Теорія ймовірностей. Матем. Статистика. Теор. Кібернетика / ВІНІТІ).
2. Клейнрок Л. Комунікаційні мережі. - М.: Наука, 1970. - 255 с.
3. Клейнрок Л. Обчислювальні системи з чергами. - М.: Світ, 1979. - 600 с.
4. Клімов Г.П. Стохастичні системи обслуговування. - М.: Наука, 1966. - 243 с.
5. Ковальов О.О. Мережі з ненадійними каналами і резервом / / Математичні методи дослідження мереж зв'язку та мереж ЕОМ. Тези доповідей VI Білоруської школи-семінару з ТМО. - Мінськ, 1990. - С. 70-71.
6. Ковальов О.О., Чікунова Н.А. Стаціонарний розподіл двовузлового замкнутої ненадійною мережі з ділився резервом / / Матеріали міжнародної конференції «Сучасні математичні методи дослідження телекомунікаційних мереж». - Мінськ, 1999. - С. 85-89.
7. Кофман А., Крюон Р. Масове обслуговування. Теорія і додатки. - М.: Світ, 1965. - 302 с.
8. Криленко А.В. Мережі масового обслуговування з кількома типами заявок, негайним обслуговуванням і обходами вузлів заявками / / Проблеми передачі інформації. - 1997. - Т. 33, Вип. 3. - С. 91-101.
9. Криленко А.В. Малінковскій Ю.В. Мережі масового обслуговування з миттєво обслуговуваними заявками II. Моделі з кількома тинами заявок / / Автоматика і телемеханіка. - 1998. - № 2. - С. 62-71.
10. Криленко А.В., Малінковскій Ю.В. Замкнуті мережі масового обслуговування з обходами вузлів і декількома класами заявок / / Becni Акад. навук Беларусi. Сер. ф1з.-мат. навук. - 1998. - № 2. - С.
11. Криленко А.В. Інваріантність стаціонарного розподілу замкнутих мереж масового обслуговування з обходами вузлів, неекспоненціальним обслуговуванням і декількома типами заявок / / Becni Акад. навук
12. Криленко О.В., Малінковскій Ю.В. Мережі обслуговування з обходами і декількома класами заявок / / Дослідження систем і мереж масового обслуговування: Тез. докл. 12-й Бел. зимової школи-семінару з ТМО, Гр., 1996 р. / Бел. держ. унів. - 1996. - С. 48-49.
13. Криленко А.В., Малінковскій Ю.В. Замкнуті мережі масового обслуговування з обходами вузлів і декількома класами заявок / / VII Білоруська математ. конф. Тез. докл. наук. конф., Мінськ, 18-22 лист. 1996 р. / Бел. матем. т-во, Бел. держ. унів., Ін-т матем-ки Академії наук Білорусі. - 1996.
14. Криленко А.В. Інваріантність мереж масового ообслужіваніем і обходами вузлів заявками / / Математичні методи дослідження телекомунікаційних мереж: Матеріали тринадцятого Бел. зимової шкіл. (Наук. конф. BWWQT-97), Мінськ, 3 - 1997 р. / Бел. держ. унів. - 1997. - С. 50-52.
15. Малінковскій Ю.В. Критерій точкової незалежності станів вузлів у відкритій стаціонарної марковської мережі обслуговування з одним класом заявок / / Теорія ймовірностей та її застосування. - 1990. - Т.35, № 4. - С. 779-784.
16. Малінковскій Ю.В. Мультипликативность стаціонарного розподілу відкритих мереж обслуговування зі стандартними вузлами і однотипними заявками / / Проблеми передачі інформації. - 1999. - Том 35, Вип.1. - С. 96-110.
17. Малінковскій Ю.В. Мультипликативность стаціонарного розподілу станів для одного класу мереж масового обслуговування / / Автоматика і телемеханіка. - 1988. - № 2. - С. 108-118.