(1.2.9)
= .
1.3 Достатня умова ергодичності
Теорема 1.3.1 (Теорема Фостера).
Регулярна Марковська ланцюг з безперервним часом і рахунковим числом станів ергодична
має нетривіальне рішення таке, що При цьому існує єдиний стаціонарний розподіл, що збігається з ергодичним. [2, с. 8-14]
Ергодичність досліджуємо відповідно до теореми 1.3.1. Розглянемо умови теореми.
Регулярність треба з того, що .
, , .
Відповідно до малюнка 1.1, одержимо:
Таким чином, регулярність виконується.
Тому що всі стани повідомляються з нульовим, тобто в будь-який стан можна перейти з нульового й у можна перейти з будь-якого стану, шляхом надходження, обслуговування й відходу заявок з мережі.
Примітка – тут ураховується, що матриця переходів неприводима.
Як нетривіальне рішення системи рівнянь із теореми 1.3.1 візьмемо . Тоді для ергодичності буде потрібно, щоб . Тоді одержимо,
,
де
Останній ряд сходиться по ознаці порівняння, якщо сходиться ряд
(1.3.1)
Умова (1.3.1) і є шукана умова ергодичності. Якщо ця умова буде виконаються, то буде існувати єдиний стаціонарний розподіл, що збігається з ергодичним.
2. Полумарковська модель мережі із трьома вузлами
Нехай є відкрита мережа масового обслуговування, що складає із трьох вузлів, у яку надходить найпростіший потік заявок з параметром . Причому, у першу систему масового обслуговування, що входить заявка надходить із імовірністю . Часи обслуговування заявок в -ом вузлі задані функцією розподілу часу обслуговування -им приладом однієї заявки , . При цьому накладає наступна вимога
, . (2.1)
Дисципліни обслуговування заявок у системах мережі LCFS PR - заявка, що надходить в -ий вузол, витісняє заявку із приладу й починає обслуговуватися. Витиснута із приладу заявка стає в початок черги. Схематично мережа зображена на малюнку 2.1.
Стан мережі описується випадковим процесом
де , , - залишковий час обслуговування заявки, що коштує в -ой позиції.
Примітка. Випадковий процес
де - число заявок в -ом вузлі в момент , не є марковським процесом. Для марковизації процесу включаємо додаткові змінні. Щоб був марковським процесом, додаткові змінні візьмемо, як залишкові часи від моменту часу до повного завершення відповідних часів. Виходить, процес - марковський процес.
Таким чином, з вищесказаного треба, що побудовано полумарковська модель відкритої мережі із трьома вузлами.
2.1 Диференційно-різницеві рівняння Колмогорова
У відповідності методом диференціальних рівнянь і малюнком 2.1, складемо наступні рівняння
, (2.1.1)
де , .
Скористаємося наступними формулами:
[7]
Тоді рівняння (2.1.1) запишуться в такий спосіб
(2.1.2)
Зважаючи на те, що деякі події є неможливими (вони дорівнюють нулю), рівняння (2.1.2) приймуть наступний вид
Розкладання функції в ряд Тейлора, має вигляд
де - позиція елемента й відповідно.
Використовуючи розкладання функції в ряд Тейлора, перетворимо рівняння (2.1.3)
.
Переносимо в ліву частину рівності, потім ділимо обидві частини на й спрямовуємо , одержимо
(2.1.4)
Таким чином, рівняння (2.1.4) і є шукані рівняння Колмогорова.
2.2 Пошук рішення диференційно-різницевих рівнянь Колмогорова
Рішенням рівнянь Колмогорова (2.1.4) є:
Перевіримо знайдене рішення (2.2.1) безпосередньою підстановкою в рівняння (2.1.4), одержимо
Таким чином, 0=0, тобто рішення (2.2.1) задовольняє рівнянням (2.1.4).
2.3 Доказ інваріантності стаціонарного розподілу
Згідно 1.2, для марковської моделі мережі із трьома вузлами отриманий вид стаціонарного розподілу, що визначається по формулі (1.2.9). При цьому часи обслуговування заявок мають показовий розподіл з параметрами для -ого вузла, де – число заявок в -ой системі, . Відповідно до розділу 2, для полумарковської моделі мережі із трьома вузлами, припускаємо, що тривалість обслуговування окремої вимоги розподілена за довільним законом. Нехай – функція розподілу часу обслуговування -им приладом однієї заявки. Передбачається, що виконується умова, обумовлене формулою (2.1).
Відповідно до результату Севастьянова [6] і формулі (2.2.1), стаціонарний розподіл зберігає форму добутку (інваріантне) і при допущених допущеннях.
Таким чином, доведена інваріантність стаціонарного розподілу відкритої мережі масового обслуговування із трьома вузлами.
3. Марковська модель мережі із трьома вузлами й різнотипними заявками
Нехай є відкрита мережа масового обслуговування, що складає із трьох вузлів, у яку надходять два незалежних пуасоновських потоки заявок з й відповідно. Моменти надходження заявки (однаково з якого потоку) утворять новий потік, що називається суперпозицією або об'єднанням первісних потоків.
Позначимо через , , – імовірності надходження заявок за час відповідно для потоку з інтенсивністю , , сумарного потоку. Тому що заявки потоків з й надходять незалежно друг від друга, то по формулі повної ймовірності одержимо:
, (3.1)
тобто суперпозиція пуасоновських потоків з інтенсивністю . [2]
Часи обслуговування заявок у різних вузлах незалежні, не залежать від процесу надходження заявок і мають показовий розподіл з параметрами для -ого вузла, - константа ( ). Схематично мережа зображена на малюнку 3.1.
Дисципліни обслуговування заявок у системах мережі визначаються в такий спосіб.
а) Якщо на приладі немає заявок, те негативна заявка, що надходить на прилад, губиться;
б) Якщо на приладі немає заявок, те вступник позитивна заявка починає обслуговуватися;
в) Якщо на приладі заявка позитивна, те негативна заявка, що прийшла, вибиває заявку із приладу й позитивна заявка губиться.
г) Якщо в черзі заявок позитивних, те прихожа негативна заявка, витісняє останню (позитивну) заявку й у черзі стає заявка ( -ая позитивна й негативна заявка губиться).
де – число позитивних заявок у момент , відповідно в першому, другому, третьому вузлі. Відповідно до розділу 1 і з огляду на формулу (3.1) – марковський процес.
Таким чином, відповідно до визначення 1.3 і вищесказаному, побудована марковська модель відкритої мережі із трьома вузлами й різнотипними заявками.
3.1 Складання рівнянь трафіка
Розглянемо ізольований -й вузол ( ), уважаючи, що на нього надходить потік заявок інтенсивності . Граф переходів зобразиться в такий спосіб.
Тоді відповідно до малюнка 3.1.1, одержимо наступні співвідношення
, , (3.1.1)
де .
Відповідно до малюнка 3.1
, . (3.1.2)
Для марковської моделі мережі із трьома вузлами й різнотипними заявками рівняння трафіка мають такий вигляд:
З огляду на формулу (3.1.2) запишемо ще три рівняння
Таким чином, рівняння трафіка мають такий вигляд
. (3.1.3)
, (3.1.4)
, (3.1.5)
, (3.1.6)
, (3.1.7)
, (3.1.8)
, (3.1.9)
, (3.1.10)
, (3.1.11)
Підставимо формулу (3.1.9) в (3.1.5) і (3.1.6), формулу (3.1.10) в (3.1.7) і (3.1.8), а формулу (3.1.11) в (3.1.3) і (3.1.4). Тоді рівняння трафіка запишуться в такий спосіб
, (3.1.12)
, (3.1.13)
, (3.1.14)
, (3.1.15)
, (3.1.16)
. (3.1.17)
3.2 Знаходження рішень рівнянь трафіка
Позитивність рішення рівнянь трафіка для досить загальної моделі доведена в роботі [9].
Для знаходження рішень рівнянь трафіка складемо рівняння відносно . Для цього перетворимо формулу (3.1.12), перенесемо все в ліву частину й приведемо до загального знаменника
. (3.2.1)
Тому що , те формула (3.2.1) прийме наступний вид
. (3.2.2)
Підставляючи формулу (3.1.14) і (3.1.15) в (3.1.16) маємо
Приводимо до загального знаменника
. (3.2.3)
Підставимо формулу, отриману з формули (3.1.13) відрахуванням формули (3.1.12), одержимо , у формулу (3.2.3), одержимо
. (3.2.4)
Позначимо й , тоді
. (3.2.5)
Відповідно до формул (3.1.16) і (3.1.17)
. (3.2.6)
З огляду на формулу (3.2.6) і (3.2.5), одержимо
. (3.2.7)
Підставимо формули (3.2.5) і (3.2.6) у формулу (3.2.2), маємо
. (3.2.8)
Тому що , те формула (3.2.8) прийме наступний вид
Розкриваючи дужки й приводячи подібні члени, запишемо формулу (3.2.9) у вигляді
Таким чином, отримане рівняння (3.2.10) квадратне, тобто
, (3.2.11)
де коефіцієнти , з огляду на позначення й формулу (3.2.10), визначаються в такий спосіб
, (3.2.12)
, (3.2.13)
. (3.2.14)
Для рівняння (3.2.11) знайдемо дискримінант, з огляду на формули (3.2.12), (3.2.13), (3.2.14), маємо
Для одержання рішення рівняння (3.2.11) повинне виконаються наступна умова , а це можливо тоді, коли
Відповідно до формули , одержимо
тобто
. (3.2.15)
Відповідно до малюнка 3.1, формула (3.2.15) є умову ергодичності. Якщо ця умова не виконується, то немає стаціонарного розподілу.
З огляду на формули (3.2.12), (3.2.14), (3.2.15) одержимо, що , . Відповідно до зворотної теореми Вієта, якщо - корінь рівняння (3.2.11), те виконуються наступні співвідношення
Тому що , те одне з корінь позитивний і один негативний.
Таким чином, рівняння (3.2.11) має одне позитивне рішення. Тобто система рівнянь трафіка (3.1.12) - (3.1.17) має позитивне рішення.
3.3 Рівняння рівноваги
У відповідності, з малюнком 3.1 складемо рівняння рівноваги
(3.3.1)
3.4 Визначення виду стаціонарного розподілу
Стаціонарний розподіл представимо у формі добутку множників вузли, що характеризує; кожний множник є стаціонарний розподіл вузла, тобто
Стаціонарний розподіл вузла має вигляд
, .
Таким чином, стаціонарний розподіл має такий вигляд
. (3.4.1)
Позначимо через
Тоді в цих позначеннях формула (3.4.1) запишеться в наступному виді
. (3.4.2)
Підставляючи формулу (3.4.2) у рівняння рівноваги (3.3.1), одержимо
(3.4.3)
Розділимо обидві частини рівняння (3.4.3) на , одержимо
(3.4.4)
Через запишемо рівняння трафіка (3.1.12) – (3.1.17)
, (3.4.5)
, (3.4.6)
, (3.4.7)
, (3.4.8)
, (3.4.9)
. (3.4.10)
Тому що , ( ), те одержимо наступні співвідношення
, (3.4.11)
, (3.4.12)
. (3.4.13)
Розглянемо всілякі випадки числа заявок у марковської моделі мережі із трьома вузлами й різнотипними заявками. Тобто наступні випадки
1) , , ;
2) , , ;
3) , , ;
4) , , ;
5) , , ;
6) , , ;
7) , , ;
8) , , ;
Підставляючи значення в рівняння (3.4.4), з огляду на рівняння (3.4.5) – (3.4.13), перевіримо, задовольняє стаціонарний розподіл (3.4.1) рівнянням рівноваги (3.3.1). Розглянемо кожний з випадків 1) - 8) окремо.
Розглянемо перший випадок , ,
Відповідно до формули (3.4.6) , формулі (3.4.8) , , формулі (3.4.10) , формулі (3.4.9) , одержимо
Відповідно до формули (3.4.5) , формулою (3.4.12) , формулою (3.4.13) . З формул (3.4.9), (3.4.10) , тоді маємо
Відповідно до формули (3.4.9) , формулі (3.4.10) . З формул (3.4.7) і (3.4.8) , одержимо
А це є формула (3.4.11), тобто випадок 1) виконується.
Розглянемо другий випадок , ,
Відповідно до формули (3.4.5) , формулі (3.4.6) , формулі (3.4.8) , , формулі (3.4.10) , формулі (3.4.10) . З формул (3.4.5) і (3.4.6) . Розкриємо дужки й перенесемо все в праву частину, одержимо
Відповідно до формули (3.4.13) , формулою (3.4.12). З формул (3.4.9), (3.4.10) , тоді
Відповідно до формули (3.4.11) , ,формулі (3.4.12) . З формул (3.4.7) і (3.4.8) , одержимо
, тобто випадок 2) виконується.
Аналогічно виконуються 3) - 8).
Таким чином, випадки 1) – 8) перетворюються у вірну рівність. Тобто стаціонарний розподіл (3.4.1) є рішення рівняння рівноваги (3.3.1), якщо виконується умова ергодичності , .
Висновок
У роботі проведене дослідження відкритих марковских і полумарковских мереж масового обслуговування із трьома вузлами й циклічною маршрутизацією.
Отримано наступні основні результати:
Для марковської моделі мережі із трьома вузлами, записані рівняння рівноваги (формула 1.1.3), отримана достатня умова ергодичності (формула 1.3.1) і знайдена стаціонарний розподіл (формула 1.2.9).
Для полумарковської моделі мережі із трьома вузлами, визначений вид диференційно-різницевих рівнянь Колмогорова (формула 2.1.4), знайдений стаціонарний розподіл (формула 2.2.1) і доведена інваріантність (див. 2.3).
Для марковської моделі мережі із трьома вузлами й різнотипними заявками, складені рівняння рівноваги (формула 3.3.1), знайдений стаціонарний розподіл (формула 3.4.1) і отримана достатня умова ергодичності (формула 3.2.15).
Результати роботи можуть бути застосовані при проектуванні й експлуатації мереж передачі даних, інформаційно-обчислювальних мереж, мереж ЕОМ і багатьох інших технічних об'єктів.
Список використаних джерел
Малинковський Ю.В. Теорія масового обслуговування. – К., 2003
Буриков А.Д., Малинковський Ю.В., Маталицкий М.А. Теорія масового обслуговування. – К., 2004
Івченко Г.И., Каштанів В.А., Коваленко И.Н. Теорія масового обслуговування. – К., 2004
Прохоров А.В., Ушаков В.Г., Ушаков Н.Г. Задачі по теорії ймовірностей: Основні поняття. Граничні теореми. Випадкові процеси. – к., 2003
Кениг Д., Штоян Д. Методи теорії масового обслуговування// Під ред. Г.П. Климова. – К., 2001
Гнеденко Б.В., Коваленко І.М. Введення в теорію масового обслуговування. – К., 2003
Ширяев О.М. Імовірність. – К., 2005
Gelenbe E. Product Form Queueing Networks with Negative and Positive Customers // J. Appl. Probab. - 1991. - V. 28. - P. 656 - 663.
Gelenbe E., Shassberger R. Stability of Product-Form G-networks // Probab. in Eng. and Inform. Sci. - 1992. - No. 6. - P. 271 - 276.
Додаток 1. Список опублікованих робіт
Гарбуза И.В. Марковська й полумарковська моделі відкритої мережі із трьома вузлами// Матеріали V міжнародної межвузовской науково-технічної конференції студентів, магістрантів і аспірантів «Дослідження й розробка в області машинобудування, енергетики й керування 2005» Гомель, 2005 р.
Гарбуза И.В. Стаціонарний розподіл і його інваріантність для моделі відкритої мережі із трьома вузлами// Творчість молодих'2005 Збірник наукових праць студентів і аспірантів Гомельського Державного університету ім. Ф. Скорини. Гомель, 2005 р.
Страницы: 1, 2
