Методи дослідження мереж масового обслуговування (стр. 11 из 13)

де

— відповідно середнє значення і дисперсія інтервалів часу між повідомленнями вхідного потоку i-го центру;

, — середнє значення і дисперсія часу обслуговування повідомлень в центрі i. Відмітимо, що в стаціонарному режимі

де

— ймовірність відсутності повідомлень в i-му центрі. З урахуванням цих співвідношень з (5.4.12) витікає, що

залежить від двох невідомих параметрів

або

Введемо в (5.4.12) рівняння перетворення дисперсії

для суми двох незалежних потоків та

для просіяного потоку (P — ймовірність покидання повідомленням потоку).

Формули (5.4.12) i (5.4.13) дозволяють одержати систему рівнянь балансу дисперсій потоків, аналогічну рівнянням (5.4.10):

де

— дисперсія інтервалів часу між сусідніми повідомленнями потоку, що надходять в i-й центр.

РОЗДІЛ 6. МЕТОД ПОЛІНОМІАЛЬНОЇ АПРОКСИМАЦІЇ

6.1 ОПИС МЕТОДУ

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

Розглянемо замкнену однорідну мережу МО, яка складається з М центрів, в яких циркулюють N повідомлень відповідно до матриці маршрутів

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

Нехай

- інтенсивність потоку повідомлень через виділений центр (наприклад, перший). Тоді в стаціонарному режимі роботи мережі МО

де відносна інтенсивність потоку однозначно визначається із системи рівнянь:

Використовуючи формулу Літтла, загальну кількість повідомлень в мережі МО можна представити в наступному вигляді:

Тут

— час перебування повідомлення в i-му центрі.

Проведемо заміну змінної

Тоді середній час циклу (час між надходженнями повідомлень у виділений центр)

Даний метод заснований на декомпозиції початкової мережі на окремі незалежні центри і використанні аналога формули Поллячека — Хінчина для оцінки часу перетворення повідомлень в центрі:

Таким чином, задача наближеного аналізу замкненої мережі МО може бути сформульована як задача розв’язання рівняння

відносно змінної X₀(N), де

поліном степеня M:

Розв’язок отриманого поліноміального рівняння при умові

існує і єдиний. З вибраного виду полінома Р(Х) слідує, що при

розв’язок рівняння (6.1.1) асимптотично збігається з точним значенням.

6.2. ОЦІНКА ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ МЕТОДУ

Оцінку обчислювальної складності методу поліноміальної апроксимації проведемо для однорідних експоненціальних мереж. Для експоненціального розподілу тривалості обслуговування в центрах мережі рівняння (6.1.1) приймає вигляд:

де уведені позначення

та

При розв’язанні рівняння (6.2.2) використовується обмеження

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

Нехай ε — необхідна точність розв’язку. Позначимо

. Вважаючи без обмеження спільності

, одержуємо кількість ітерацій, необхідних для відшукання розв’язку з точністю ε:

Помітимо, що

тобто, при великій кількості центрів число ітерацій

РОЗДІЛ 7. Приклад розрахунку мережі МО

Розглянемо модель замкненої ієрархічної мережі МО, схема якої зображена на рисунку 7.1. У цій мережі циркулює N=30 заявок, у відповідності з маршрутною матрицею. Заявка, яка виходить з головного центру 1 потрапляє у один з аналітичних центрів 2-11, у яких проходить первинну обробку, а потім у центрах

12-18 вторинну та сортировку щодо призначення їх у виконуючі системи 19-20. Після закінчення обслуговування у центрах19-20 виконана заявка потрапляє у головний центр 1, у якому вона замінюється новою, та надходить у центри 2-11.

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

Рисунок 7.1 Приклад мережі МО

Далі приведена маршрутна матриця (табл.7.1) та інтенсивності обслуговування у центрах

(табл.7.2).

Таблиця 7.1 Маршрутна матриця

ij	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
1	0	0,1	0,05	0,15	0,1	0,05	0,1	0,05	0,15	0,2	0,05	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0,05	0,25	0,15	0,1	0,05	0,11	0,3	0	0
3	0	0	0	0	0	0	0	0	0	0	0	0,05	0,15	0,1	0,25	0,3	0,1	0,05	0	0
4	0	0	0	0	0	0	0	0	0	0	0	0,05	0,05	0,1	0,25	0,1	0,15	0,3	0	0
5	0	0	0	0	0	0	0	0	0	0	0	0,05	0,1	0,3	0,1	0,25	0,15	0,05	0	0
6	0	0	0	0	0	0	0	0	0	0	0	0,05	0,3	0,25	0,05	0,1	0,15	0,1	0	0
7	0	0	0	0	0	0	0	0	0	0	0	0,05	0,15	0,3	0,25	0,05	0,1	0,1	0	0
8	0	0	0	0	0	0	0	0	0	0	0	0,05	0,1	0,25	0,3	0,15	0,1	0,05	0	0
9	0	0	0	0	0	0	0	0	0	0	0	0,05	0,3	0,05	0,1	0,15	0,25	0,1	0	0
10	0	0	0	0	0	0	0	0	0	0	0	0,05	0,1	0,15	0,05	0,3	0,1	0,25	0	0
11	0	0	0	0	0	0	0	0	0	0	0	0,05	0,05	0,1	0,1	0,25	0,3	0,15	0	0
12	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0,5	0,5
13	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0,67	0,33
14	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0,5	0,5
15	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0,75	0,25
16	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0,25	0,75
17	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0,83	0,17
18	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0,25	0,75
19	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
20	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0

Таблиця 7.2 Інтенсивності обслуговування.