Система масового обслуговування

отримуємо:

.

1.5.2 Основні випадки розподілу станів системи

Потік викликів примітивний із параметром

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

.

Підставивши отриманий вираз у (5.19) отримаємо розподіл Енгсета: . (5.20)Потік викликів найпростіший із параметром , дисципліна обслуговування з явними втратами - тобто система . З (5.19) безпосередньо випливає перший розподіл Ерланга:

Розподіл Ерланга можна одержати також із розподілу Енгсета (5.20), якщо , а , але так, що .

Потік викликів примітивний з параметром

,

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

.

При цьому вираз (5.20) з урахуванням бінома Ньютона

приймає вигляд (якщо ): .(5.21)

1.5.3 Характеристики якості систем

Імовірність втрат за часом знаходиться з розподілу Енгсета (5.20) як імовірність зайнятості усіх каналів системи:

 . (5.24)

Формула (5.24) носить назву формули Енгсета. Значення цієї формули також табульовані у довідковій літературі [1].

Імовірність втрати виклику знаходиться згідно визначенню (3.9):

. (5.25)

Порівняння формул (5.24) і (5.25) показує, що завжди має місце нерівність:

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

Інтенсивність обслугованого навантаження:

(5.26)

Інтенсивність вхідного навантаження (математичне очікування параметру примітивного потоку викликів):

(5.27)

Інтенсивність потенційного навантаження

, (5.28)

1.6 Імовірність зайнятості визначених каналів

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

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

(5.34)

Для системи (модель Енгсета) формула буде відрізнятися:

(5.35)

У формулі (5.35) - кількість джерел викликів у примітивному потоці, - інтенсивність одного джерела, виражена в ерлангах.

Для системи з однаковим числом входів і виходів (джерел викликів та каналів обслуговування) має місце модель Бернуллі та формула:

1.7 Порівняння моделей та для рішення задачі структурного синтезу

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

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

Вважатимемо, що комутатор має вхадних та вихідних ліній.

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

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

Для систем з втратами найважливішою характеристикою якості є імовірність втрат за часом (п.3.4).

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

Будемо розглядати усі виклики, що надходять від абонентів, як загальний найпростіший потік з параметром:

Знайдемо вхідне навантаження:

Скориставшись першою формулою Ерланга (5.6), можна знайти наступні значення імовірність втрат (або блокування) при різній кількості вихідних ліній для розрахованого навантаження:

2. СМО з очікуванням

навантаження втрата канал бернуллі

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

.

Рисунок 6.1. Граф станів СМО з очікуванням

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

(6.1)

Позначимо для і при . Тоді з (6.1) одержуємо , звідки випливають два рекурентних співвідношення для обчислення імовірностей :

(6.2) .

Приймаючи значення послідовно рівними 0, 1, 2,... , одержуємо:

.

…

.

(5.36)

навантаження втрата канал бернуллі

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

Імовірність втрат за навантаженням знаходимо з урахуванням (5.28) і (5.26):

.(5.29)

З (5.29) випливає, що при кінцевому завжди має місце нерівність:

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

Розглянемо різницю:

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

Позначивши

,

після нескладного перетворення маємо розподіл Бернуллі:

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

.(5.23) Розподіл Пуассона (5.23) можна також одержати з розподілу Бернуллі (5.22) при та , але так що .

Таким чином, найбільш загальним із розглянутих чотирьох розподілів є розподіл Енгсета. З нього випливає, з одного боку, перший розподіл Ерланга, а з іншого боку - розподіл Бернуллі. З останніх двох, різними засобами, можна одержати розподіл Пуассона.

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

Таким чином, (6.3)

Для визначення імовірності скористаємося умовою нормування з урахуванням (6.3)

Звідки .(6.4)

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

1. Інтенсивність потоку викликів від вільного джерела в одну умовну одиницю часу , викл/у.о.ч.

2. Середня інтенсивність потоку викликів в одну умовну одиницю часу або інтенсивність навантаження, що надходить від джерела , викл/у.о.ч. . З (5.27): (5.30)

3. Інтенсивність потенційного навантаження від джерела , Ерл.

.(5.31)

4. Інтенсивність обслугованого навантаження, віднесена до одного джерела , Ерл. З (5.26): (5.32)

Порівнюючи (5.30) - (5.32), маємо:

Для зручності розрахунків, крім вищенаведених формул можна використовувати також наступні:

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

При помірних навантаженнях , можна користуватися наближеними формулами:

.

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

Знайдемо кілька значень цієї функції.

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

(6.5)

З урахуванням (6.3) і (6.5) одержуємо другий розподіл Ерланга:

(6.6)

Слід запам'ятати: цей вираз можна використовувати тільки при дотриманні умови існування усталеного режиму:

2.2 Характеристики якості обслуговування

2.2.1 Імовірність очікування для виклику, що надійшов

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

Вираз (6.7) називається другою формулою Ерланга.

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

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

2.2.2 Інтенсивність обслугованого навантаження

Відповідно до визначення інтенсивності обслугованого навантаження, використовуючи рекурентні співвідношення (6.2), одержуємо:

.(6.8)

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

.

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

.

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

2.2.3 Середня довжина черги

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

,

де - номер стану.

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

(6.9)

Формула (6.9) отримана з урахуванням другої половини (6.2), а також виразу для суми нескінченої геометричної прогресії .

2.2.4 Середня тривалість очікування початку обслуговування

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

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

З (6.10) і (6.9) можна отримати значення , виражене в умовних одиницях часу, тобто в одиницях середньої тривалості обслуговування:

.(6.11)

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

.

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

.(6.12)

.

Порівнюючи (6.12) і (6.9), отримуємо формулу, відому як формула Літла:

(6.13)

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

2.2.5 Імовірність перевищення довжиною черги заданої величини

Використовуючи послідовно разів друге рекурентне співвідношення (6.2), одержуємо:

(6.14)

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

2.2.6 Імовірність очікування більше припустимого часу

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

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

Тоді . (6.17) Підставивши (6.16) і (6.17) у (6.15), після ряду перетворень одержуємо:

.(6.18) Величина у (6.18) виражена в умовних одиницях часу.

2.3 Одноканальна система з очікуванням

Розглянемо систему та визначимо її основні характеристики.

Для такої системи основна умова існування усталеного режиму приймає вид .

Імовірність очікування для будь-якого виклику, що надійшов, за другою формулою Ерланга (6.7) має вигляд: .(6.19)

Середня довжина черги з (6.9) з урахуванням (6.19) .(6.20)

Імовірність перевищення чергою заданого значення знаходимо за (6.14) з урахуванням (6.19): .(6.21)

Середній час очікування для будь-якого та затриманого виклику, відповідно:

. (6.22)

.(6.23)

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

.(6.24)

2.4 Система з обмеженим числом місць в черзі

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

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

Така система є комбінованою - з очікуванням і втратами, або з умовними втратами. Детально вона розглянута в [3].

Наведемо її основні характеристики якості.

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

.(6.25)

Імовірність того, що виклик, який надійшов в систему в будь-який момент часу, застане усі лінії і всі місця для очікування зайнятими і отримає відмову, визначається:

.(6.26)

При заданих кількості ліній та величині втрат необхідну кількість місць для очікування можна розрахувати за формулою:

 .(6.27)

Середня тривалість очікування затриманих викликів:

.(6.28)

Приклад 5.1.

Для системи обчислити імовірності усіх станів системи при інтенсивності вхідного потоку 5 викл/хв і середньому часі обслуговування 24 с.

Рішення

Граф станів системи зображений на рис. 5.2.

Рисунок 5.2

Інтенсивність навантаження, що надходить:

.

Імовірності станів обчислюємо за першим розподілом Ерланга (5.4):

.

.

.

.

Приклад 5.2

Яку кількість каналів зайнято з максимальною імовірністю в системі , якщо виклики надходять у систему, в середньому, через 10 с і обслуговуються, в середньому, 20 с?

Рішення:

Максимуми першого розподілу Ерланга залежать від :

.

Який середній час обслуговування має бути в системі , щоб при обслуговуванні потоку з параметром 20 викл/хв в ній втрачалось не більше 3 % викликів?

Рішення

За формулою (5.5):

.

Отже потрібно знайти таке значення , при якому

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

.

Приклад 5.6

В системі в середньому зайнято 30 каналів. Визначити пропускну здатність одного каналу.

Рішення

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

Приклад 5.3

Розрахувати частку втрачених викликів в системі при . Як зміниться це значення при збільшенні на 50 %

Рішення

Частку втрачених викликів дає :

При збільшенні кількості каналів на 50 % отримуємо 3-канальну систему.

.

Знайдемо, наскільки покращалась якість обслуговування при збільшенні кількості каналів на 50 %:

 .

Таке суттєве покращання якості обслуговування спостерігається при невеликій кількості каналів. Якщо збільшити на 100 % (4 канали в системі), то якість обслуговування зміниться на 92,31%:

.

Приклад 5.5

Визначити пропускну здатність першого каналу при випадковому и послідовному занятті каналів в системі

Рішення

Спочатку знаходимо інтенсивність навантаження, що надходить:

.

Пропускну здатність першого каналу при випадковому занятті каналів визначаємо за (5.11). Для чого спочатку розрахуємо

.

Тоді,

.

Пропускну здатність першого каналу при послідовному занятті каналів визначаємо за (5.11). Для чого спочатку розрахуємо , адже :

 .

.

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

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

Якщо збільшити на 200 % (6 каналів в системі), то якість обслуговування зміниться на 99,75%:

.

Отже, залежність якості обслуговування від кількості каналів має вигляд, як приведено на рис. 5.4, де показано графіки при 5 значеннях :

.

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

Рисунок 5.4. Залежність від кількості каналів для різних значень

Перевірка:

а)

.

Графік розподілу приведено на рисунку 5.3.

Рисунок 5.3.

Отриманий збіг значень і - не випадковість. Перший розподіл

Ерланга має такі максимуми:

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

2. Якщо , то залежно від того, ціле чи дробове , максимумів два або один:

a. при цілому маємо 2 максимуми

b. при дробовому маємо 1 максимум

Приклад 5.7

Розрахувати основні характеристики якості для системи , для якої відома імовірність втрати виклику , якщо:

Виразимо інтенсивність джерела у вільному стані в ерлангах:

.

Інтенсивність обслугованого навантаження за (5.26):

Інтенсивність потенційного навантаження для одного джерела (5.31):

Інтенсивність вхідного навантаження за (5.27):

Середня інтенсивність джерела(5.30):

Таким чином, виконується співвідношення

Приклад 6.1.

Для системи , на вхід якої надходить навантаження з інтенсивністю 1 Ерл. обчислити:

частку часу, який система простоює

імовірність зайнятості 1 каналу в системі

імовірність знаходження у черзі 1 виклику.

Побудувати граф станів системи

Рішення

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

Оскільки граничні імовірності характеризують частку часу, яку система знаходиться у відповідному стані, то для обчислення частки часу, який система простоює, треба знайти за першою частиною (6.6):

.

Імовірність зайнятості 1 каналу в системі - це . Використовуючи те, що в усіх виразах (6.6) знаменник однаковий:

.

Імовірність знаходження у черзі 1 виклику - це , обчислюється за другою частиною (6.6):

.

Размещено на Allbest.ru