Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP|G| ∞

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2004
1. Verfasser:	Шумська, А.А.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України 2004
Schriftenreihe:	Системні дослідження та інформаційні технології
Schlagworte:	Математичні методи, моделі, проблеми і технології дослідження складних систем
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/50352
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞ / А.А. Шумська // Систем. дослідж. та інформ. технології. — 2004. — № 3. — С. 91-102. — Бібліогр.: 24 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-50352
record_format	dspace
spelling	irk-123456789-503522013-10-11T03:07:27Z Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞ Шумська, А.А. Математичні методи, моделі, проблеми і технології дослідження складних систем Розглядається система масового обслуговування з нескінченною кількістю обслуговуючих пристроїв. В систему надходить груповий потік вимог, який керується напівмарковським процесом. Запропоновано метод прискореного моделювання стаціонарної ймовірності кількості вимог у системі, що ґрунтується на методі істотної вибірки та використовує центральну граничну теорему. Оцінки є асимптотично незміщеними. Виграш в дисперсії порівняно з методом Монте-Карло становить в середньому два порядки. Рассматривается система массового обслуживания с бесконечным количеством обслуживающих устройств. В систему поступает групповой поток требований, управляемый полумарковским процессом. Предложен метод ускоренного моделирования стационарной вероятности количества требований в системе, основанный на методе существенной выборки и использующий центральную предельную теорему. Оценки — асимптотически несмещенные. Выигрыш в дисперсии по сравнению с методом Монте-Карло составляет в среднем два порядка. A queueing system with the infinite number of servers and batch arrival process controlled by the semi-Markov process is investigated. A fast simulation method for the evaluation of the steady-state distribution of the number of customers in the system is proposed, which is based on essential sampling and the central limit theorem. The estimates are asymptotically unbiased. The gain in variance compared to the Monte Carlo method is on the average two orders of magnitude. 2004 Article Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞ / А.А. Шумська // Систем. дослідж. та інформ. технології. — 2004. — № 3. — С. 91-102. — Бібліогр.: 24 назв. — укр. 1681–6048 http://dspace.nbuv.gov.ua/handle/123456789/50352 519.21 uk Системні дослідження та інформаційні технології Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем
spellingShingle	Математичні методи, моделі, проблеми і технології дослідження складних систем Математичні методи, моделі, проблеми і технології дослідження складних систем Шумська, А.А. Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞ Системні дослідження та інформаційні технології
description	Розглядається система масового обслуговування з нескінченною кількістю обслуговуючих пристроїв. В систему надходить груповий потік вимог, який керується напівмарковським процесом. Запропоновано метод прискореного моделювання стаціонарної ймовірності кількості вимог у системі, що ґрунтується на методі істотної вибірки та використовує центральну граничну теорему. Оцінки є асимптотично незміщеними. Виграш в дисперсії порівняно з методом Монте-Карло становить в середньому два порядки.
format	Article
author	Шумська, А.А.
author_facet	Шумська, А.А.
author_sort	Шумська, А.А.
title	Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞
title_short	Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞
title_full	Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞
title_fullStr	Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞
title_full_unstemmed	Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞
title_sort	прискорене моделювання стаціонарного розподілу кількості вимог у системі smbap\|g\| ∞
publisher	Навчально-науковий комплекс "Інститут прикладного системного аналізу" НТУУ "КПІ" МОН та НАН України
publishDate	2004
topic_facet	Математичні методи, моделі, проблеми і технології дослідження складних систем
url	http://dspace.nbuv.gov.ua/handle/123456789/50352
citation_txt	Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP\|G\| ∞ / А.А. Шумська // Систем. дослідж. та інформ. технології. — 2004. — № 3. — С. 91-102. — Бібліогр.: 24 назв. — укр.
series	Системні дослідження та інформаційні технології
work_keys_str_mv	AT šumsʹkaaa priskorenemodelûvannâstacíonarnogorozpodílukílʹkostívimogusistemísmbapg
first_indexed	2025-07-04T12:01:36Z
last_indexed	2025-07-04T12:01:36Z
_version_	1836717704213430272
fulltext	© А.А. Шумська, 2004 Системні дослідження та інформаційні технології, 2004, № 3 91 УДК 519.21 ПРИСКОРЕНЕ МОДЕЛЮВАННЯ СТАЦІОНАРНОГО РОЗПОДІЛУ КІЛЬКОСТІ ВИМОГ У СИСТЕМІ ∞\|\|SMBAP G А.А. ШУМСЬКА Розглядається система масового обслуговування з нескінченною кількістю об- слуговуючих пристроїв. В систему надходить груповий потік вимог, який ке- рується напівмарковським процесом. Запропоновано метод прискореного мо- делювання стаціонарної ймовірності кількості вимог у системі, що ґрунтується на методі істотної вибірки та використовує центральну граничну теорему. Оцінки є асимптотично незміщеними. Виграш в дисперсії порівняно з методом Монте-Карло становить в середньому два порядки. ВСТУП В останні роки значна увага приділяється дослідженню, розвитку та впрова- дженню телекомунікаційних мереж у багатьох сферах людської діяльності. Це є однією з найбільш перспективних областей використання новітніх ін- формаційних технологій. Проведені дослідження [1] свідчать: процес, який описує кількість вимог в мережі, моделюється або системою масового об- слуговування з втратами, або системою з нескінченною кількістю обслуго- вуючих пристроїв. Добре відомо, що вхідний потік не завжди можна вважа- ти рекурентним, тобто в багатьох випадках інтервали між послідовними моментами надходження вимог не є незалежними випадковими величинами. Цю проблему до деякої міри вдалося розв’язати завдяки введенню такого поняття, як груповий потік вимог, що керується марковським процесом (в літературі використовується позначення BMAP — Batch Markovian Arrival Process) [2, 3]. Ця модель, яка узагальнює поняття пуасонівського потоку, виявилась досить плідною, і за останні роки опубліковано десятки робіт, присвячених розробці математичного апарату дослідження різних систем масового обслуговування з вхідними потоками типу BMAP та пошуку прак- тичних застосувань, де ця модель буде найбільш ефективною. Серед остан- ніх у цьому напрямку відмітимо роботи [4–7]. В той же час суто аналітич- ний підхід придатний лише до певної міри, оскільки вимагає розв’язання досить складних рівнянь, що, як правило, можна зробити лише чисельними методами. Якщо ж вхідний потік має більш складну структуру, ніж BMAP, то задача принципово ускладнюється. Альтернативний підхід, який в основному і використовується в інжене- рній практиці, ґрунтується на методі Монте-Карло [8]. Моделюючи вхідний потік та процес обслуговування вимог, можна з більш-менш достатньою то- чністю оцінити характеристики системи. Єдиною, але суттєвою проблемою при цьому лишається випадок, коли ймовірність q , що оцінюється, є малою величиною (наприклад, ймовірність втрати вимоги). Кількість іспитів, які треба провести для досягнення потрібної точності, пропорційна q/1 , і тому у випадку малих значень q метод Монте-Карло стає малоефективним. А.А. Шумська ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 92 В останні роки досить велика увага приділяється розвитку методів при- скореного моделювання, основною метою яких є зменшення дисперсії оцін- ки в порівнянні з методом Монте-Карло. Дуже часто цього вдається досягти поєднанням статистичного моделювання з аналітичним обчисленням ймові- рностей деяких подій. Стосовно телекомунікаційних мереж ефективні мето- ди прискореного моделювання розроблені в роботах [1, 9–13]. Метою про- ведених досліджень була стаціонарна ймовірність знаходження системи в множині блокуючих станів (надходження вимоги при такому стані системи означає її втрату). Розроблені методи спиралися на припущення: всі вхідні потоки є пуасонівськими. В цьому випадку стаціонарні ймовірності обчис- люються за явними аналітичними формулами, що суттєво спрощує обчис- лення. Якщо ж вхідні потоки не є пуасонівськими, то задача оцінки стаціо- нарних характеристик принципово ускладнюється. Одним із перспективних напрямків досліджень для подолання вказаної проблеми є створення асимптотичних методів, які ґрунтуються на припу- щенні про мале завантаження системи. Так, у роботі [14] в умовах малого завантаження досліджувалась асимптотична нечутливість стаціонарної ймовірності втрати вимоги в системі 0/// mGGI відносно функції розподілу часу обслуговування. У випадку великого завантаження в [15] розглядалася багатоканальна система масового обслуговування з декількома вхідними по- токами вимог. Було запропоновано метод прискореного моделювання стаціо- нарної ймовірності втрати вимоги, який ґрунтується на методі істотної вибір- ки та використовує центральну граничну теорему. Порівняно з методом Монте-Карло виграш в дисперсії становив декілька порядків. Нижче буде показано, що основні ідеї цього методу можуть бути використані і для до- слідження систем з такими складними вхідними потоками, як SMBAP. ПОСТАНОВКА ЗАДАЧІ Об’єктом дослідження цієї статті є система масового обслуговування ∞\|\|SMBAP G , тобто система з нескінченною кількістю ліній обслуговуван- ня, в яку надходить груповий потік вимог, що керується напівмарковським процесом (аналогічно до BMAP ми використовуємо позначення SMBAP — Semi-Markov Batch Arrival Process). Формальна конструкція процесу, який описує надходження вимог, задається таким чином. Нехай ...},2,1,0),,,{( =nnnn ατν — трьохмірний випадковий процес, визначений на деякому ймовірнісному просторі і такий, що приймає значен- ня у просторі станів SRE ×× + , де };,..,.1{ mE = );,0[ ∞=+R };,...,0{ sS = sm, — деякі натуральні числа. Вважається: ,00 i=ν ,00 =τ 00 =α з ймо- вірністю 1 (початковий розподіл, який для подальших міркувань ролі не грає і задається лише для строгого визначення процесу). Крім того, задаєть- ся функція },,,\|,,{)( 111 )( lyikyxjxQ nnnnnn k ij ====+<== +++ ατνατνP ,0,0,,,, >≥∈∈ xySlkEji яка не залежить від y і l та задовольняє співвідношення Прискорене моделювання стаціонарного розподілу кількості вимог у системі ∞\|\|SMBAP G Системні дослідження та інформаційні технології, 2004, № 3 93 1)()( =+∞∑ ∑ ∈ ∈Sk Ej k ijQ для довільного Ei∈ . Ця функція повністю визначає траєкторії процесу. Введений трьохмір- ний процес допускає таку інтерпретацію. Вимоги в систему надходять в моменти }{ nτ , де ),{( nn τν , ...},2,1,0=n — процес марковського відновлення, якому однозначно від- повідає напівмарковський процес із скінченною множиною станів E . У мо- мент nτ надходить nα вимог. В подальшому будемо використовувати більш зручні позначення EjiQijp Sk k ijnnij ∈+∞==== ∑ ∈ + ,,)(}\|{ )( 1 ννP — перехідні ймовір- ності вкладеного ланцюга Маркова; SkEjiQQijkq Sl l ij k ijnnn k ij ∈∈+∞+∞===== ∑ ∈ ++ ,,,)(/)(},\|{ )()( 11 )( νναP — ймовірність надходження k вимог при умові, що в цей момент відбувся пе- рехід із i в j ; ,)(/)(},\|{)( )()( 11 ∑∑ ∈∈ ++ +∞===<−= Sk k ij k ij Sk nnnnij QxQijxxF ννττP 0,, >∈ xEji — функція розподілу часу перебування напівмарковського процесу в стані i за умови, що наступним його станом буде j . Введений процес є узагальненням BMAP (якщо покласти =)(xFij xije λ−−=1 для всіх ,, Eji ∈ то отримаємо BMAP). Обслуговування вимог починається в момент їх надходження. Час об- слуговування має функцію розподілу )(xG . Припустимо, що вкладений ланцюг Маркова, який визначається пере- хідними ймовірностями }{ ijp , є незведеним і неперіодичним, а функції роз- поділу )}({ xFij не гратчасті, причому існують такі 0>δ і 0>ε , що εδ −≤∑ ∈ 1)(ij Ej F для всіх Ei∈ . Тоді напівмарковський процес буде ерго- дичним і таким же буде процес, який описує кількість вимог у системі. Мета статті — розробка методу прискореного моделювання стаціонарної ймовір- ності NP того, що в системі знаходиться, принаймні, N вимог. Очевидно, що для знаходження NP аналітичний підхід не ефективний. Теоретично для NP можна виписати явні аналітичні формули у вигляді ба- гатовимірних сум від багатовимірних згорток функцій розподілу. Але такий підхід не має перспектив практичної реалізації. З другого боку, як правило, середній час між надходженнями вимог значно менший за середній час об- слуговування вимоги, що свідчить про високе завантаження системи. В цьому випадку методи прискореного моделювання [16–24], які були розроб- лені для дослідження систем з малим завантаженням, є недостатньо ефек- тивними (дисперсія оцінок має той же порядок, що і при моделюванні мето- дом Монте-Карло). А.А. Шумська ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 94 Далі у статті пропонується метод прискореного моделювання, що ґрун- тується на сумісному використанні методу істотної вибірки, центральної граничної теореми та ідей прискореного моделювання у випадку малого за- вантаження системи. Оцінки асимптотично незміщені. Виграш в дисперсії порівняно з методом Монте-Карло ілюструє приклад, наведений в остан- ньому розділі статті. МОДЕЛЮВАННЯ НАДХОДЖЕННЯ ВИМОГ У СТАЦІОНАРНОМУ РЕЖИМІ Розглянемо довільний момент часу (позначимо його t ) і припустимо, що до цього моменту система функціонує нескінченно довго, тобто знаходиться у стаціонарному режимі. Для того щоб оцінити ймовірність присутності в мо- мент t щонайменше N вимог, необхідно вміти моделювати моменти над- ходження вимог до t і їх кількості. Перенумеруємо всі вимоги, які надійшли до моменту t , за правилом: чим раніше надійшла вимога, тим більший номер вона має. Позначимо ...,2,1, =rtr час від моменту надходження r -ї вимоги до моменту t (оскільки в один і той же момент можуть надійти декілька вимог, то деякі з цих моментів співпадають). Якщо розглядати лише R вимог, які надійшли останніми, то отримаємо наближену модель, а якщо ∞→R , то точну модель для знаходження стаціонарної ймовірності NP . Позначимо ),...,1,( RrtI rN = індикатор знаходження у системі в момент t щонаймен- ше N вимог, якщо відомі моменти надходження останніх R вимог. Тоді ),(lim RPP N R N ∞→ = де ),...,1,()( RrtIRP rNN == M . Подальші міркування будемо вести при фіксованому R . Збільшуючи R , можна досягти якої завгодно точності оцінки NP . Сформулюємо алгоритм моделювання послідовності }{ rt . Оскільки вкладений ланцюг Маркова є ергодичним, то існують стаціонарні ймовірно- сті P ∞→ = n i limπ },{ in =ν ,Ei∈ які задовольняють систему рівнянь ∑ ∑ ∈ ∈ =∈= Ej Ej jjiji Eip .1,, πππ (1) У подальшому нам стане в пригоді алгоритм моделювання станів ста- ціонарного ланцюга Маркова у зворотному напрямку, тобто в напрямку ми- нулого. В основі цього алгоритму лежать формули Байеса. А саме, згідно з розподілом }{ jπ моделюємо стан стаціонарного ланцюга Маркова у 0-й момент часу: .0 j=ν Тоді стан процесу в момент 1− моделюється згідно з розподілом Прискорене моделювання стаціонарного розподілу кількості вимог у системі ∞\|\|SMBAP G Системні дослідження та інформаційні технології, 2004, № 3 95 .,}\|{ 01 Ei p p p ji j iji El ljl iji ∈==== ∑ ∈ − π π π π ννP (2) Моменти надходження вимог моделюємо в напрямку минулого від мо- менту t , який вважається умовним нулем. Нумерація відповідних випадко- вих величин ведеться також в напрямку минулого – чим раніше надійшла вимога, тим більші номери мають випадкові величини, пов’язані з цією по- дією. Це стосується перш за все моментів }{ nu зміни станів напівмарковсь- кого процесу, які відлічуються від t у зворотному напрямку (наприклад, 1u — час від останньої до t зміни стану), послідовності }{ nz станів проце- су в моменти }0{ −nu і кількості }{ nx вимог, що надходять у відповідні мо- менти. Алгоритм моделювання послідовності }{ rt формулюється таким чи- ном. 1. Нехай 0=r (лічильник моментів }{ rt ), 1=n (лічильник моментів зміни стану процесу). Стан стаціонарного напівмарковського процесу моде- люємо згідно з відомими формулами. А саме, nz приймає значення j з ймовірністю ∑ ∈El lljj aa ππ , де ,∑ ∈ = El jljlj paa .)](1[ 0 duuFa jljl ∫ ∞ −= Не- хай .jzn = 2. Моделюємо час nθ , що пройшов від останнього моменту зміни ста- ну напівмарковського процесу, згідно з розподілом =< }{ xnθP ∫ −= x j j duuF a 0 ,)](1[1 де ∑ ∈ = El jljlj puFuF .)()( Покладемо .nnu θ= 3. Згідно з розподілом jiji p ππ , Ei∈ (2) моделюємо стан 1+nz лан- цюга Маркова. Нехай .1 izn =+ 4. Згідно з розподілом Skq k ij ∈,)( моделюємо кількість вимог nx , які надійшли в момент .nu Якщо надійшло 0>k вимог, то покладемо .... 11 +++ === nkrr utt Додаємо до r значення k ( krr +→ ). 5. Моделюємо випадкову величину 1+nθ (час перебування в стані i до переходу в стан j ) згідно з функцією розподілу )(xFij . Покладемо .11 ++ += nnn uu θ Позначаючи стан процесу в момент 01 −+nu через j (тоб- то jzn =+1 ) і збільшуючи n на 1 ( 1+→ nn ), повертаємось на крок 3 алго- ритму і моделюємо попередній стан ланцюга Маркова. Останні три кроки алгоритму повторюємо до тих пір, поки ε>− )(1 nuG , де 0>ε – верхня границя для ймовірності перебування в системі в момент t вимоги, що на- дійшла nu часу тому. Сформульований алгоритм дає змогу моделювати послідовність },,...,1,{)( RrtRU r == яку в подальшому вважаємо фіксованою. А.А. Шумська ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 96 АЛГОРИТМ ПРИСКОРЕНОГО МОДЕЛЮВАННЯ ЙМОВІРНОСТІ )(RPN При фіксованій послідовності )(RU необхідно оцінити ймовірність того, що, принаймні, N з R вимог залишаться в системі до моменту t . Викори- стаємо той же підхід, що і в роботі [15]. Введемо випадкові величини }{ rµ : ,1=rµ якщо ,rr t≥η і ,0=rµ як- що ,rr t<η де }1,{ ≥rrη — незалежні і однаково розподілені випадкові величини з функцією розподілу ).(xG При фіксованій послідовності )(RU випадкові величини },...,1,{ Rrr =µ є незалежними, хоча і різнорозподіле- ними. Кількість вимог в системі в момент t дорівнює ∑ = = R r r 1 µγ . Строго кажучи, до γ не може бути застосована центральна гранична теорема, оскільки не виконана умова Ліндеберга. В той же час чисельний аналіз по- казав, що розподіл γ з практичної точки зору достатньо добре апроксиму- ється нормальним розподілом з параметрами , 1 ∑ = == R r rga γM ,)1( 1 2 ∑ = −== R r rr ggγσ D де P=rg }{ rr t>η . Даний розподіл і будемо використовувати в подальшо- му для наближеної оцінки ймовірності втрати вимоги в момент t . Метод прискореного моделювання ймовірності )(RPN ґрунтується на допоміжному алгоритмі [15], який сформулюємо у вигляді леми. Нехай Kkk ,...,1, =β — випадкові величини, які приймають значення 1 з ймовірністю kb і 0 — з ймовірністю 1 – kb . Припустимо, що треба оці- нити ймовірність події ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ≥= ∑ = K k k zzB 1 )( β для деякого натурального чис- ла z . Позначимо =),( jih ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ≥∑ = K ik k jβP . Тоді ),1()}({ zhzB =P . Лема. Для довільної послідовності додатних чисел Kkk ,...,1, =ϕ і для довільних ,1,...,1 −= Ki zj ,...,1= має місце рекурентне співвідношення ),1,1(),( −+= jhCjih i i i ζ ϕζ M (3) де ∑ = =≡ K ik ki cCih ,,1)0,( ,,...,,)1( 1 Kikbbc k il lkkk =−= ∏ − = ϕ а випадкова величина iζ приймає значення },...,{ Kik ∈ з ймовірністю ./ ik Cc Прискорене моделювання стаціонарного розподілу кількості вимог у системі ∞\|\|SMBAP G Системні дослідження та інформаційні технології, 2004, № 3 97 Співвідношення (3) дає можливість рекурентно моделювати послідов- ність },{ kζ для якої .1= kζβ Добуток z вагових множників і дає незміщену оцінку ймовірності ),1()}({ zhzB =P . Виникає питання про дисперсію оцін- ки. Припустимо, що відомі точні значення )},({ jih для довільних i та j , але, незважаючи на це, для обчислення ),1( zh ми використовуємо алгоритм леми. Якщо покласти ),1,1( −+= jkhkϕ ,,...,1 Kk = то, як легко бачити, оцінка в (3) під знаком математичного сподівання має нульову дисперсію, що рівнозначно обчисленню за точною аналітичною формулою. Звідси випливає висновок: чим ближчими є значення }{ kϕ до ймовір- ностей )}1,1({ −+ jkh , тим меншою буде дисперсія оцінки, отримана за ал- горитмом леми. Як було зазначено вище, розподіл ⎪⎭ ⎪ ⎬ ⎫ ⎪⎩ ⎪ ⎨ ⎧ ≥= ∑ = K ik k jjih βP),( може бути з достатньо високою точністю апроксимований нормальним роз- поділом. Тому при великих значеннях K доцільно використовувати апрок- симацію ,, 1 ik dj k k k ≥⎟⎟ ⎠ ⎞ ⎜⎜ ⎝ ⎛ −− Φ= ρ ϕ де ∫ ∞− −=Φ x u duex , 2 1)( 2/2 π ∑ ∑ += += −== K kl K kl llklk bbbd 1 1 2 .)1(, ρ (4) Викладений вище підхід лежить в основі методу прискореного моде- лювання стаціонарної ймовірності )(RPN . Сформулюємо даний метод у ви- гляді алгоритму побудови оцінки )(ˆ RPN в одній реалізації для ймовірності )(RPN . 1. Розв’язуємо систему лінійних рівнянь (1) і знаходимо стаціонарний розподіл }{ jπ для вкладеного ланцюга Маркова. 2. Згідно з описаним вище алгоритмом будуємо послідовність }.,...,1,{)( RrtRU r == 3. Обчислюємо P=rg }{ rr t>η , .,...,1 Rr = 4. Покладемо 1)(ˆ =RPN (початкове значення оцінки), 0=κ (лічиль- ник моментів надходження вимог, обслуговування яких не закінчиться до моменту t ) і 0=δ (лічильник кількості вимог, обслуговування яких не за- кінчиться до моменту t ). 5. Згідно з алгоритмом леми будуємо перший момент κ>rtr , над- ходження вимоги, обслуговування якої не закінчиться до t . Для цього спочатку для кожного Rj ,...,1+= κ знаходимо ваговий множник jϕ , що наближено оцінює ймовірність знаходження в системі в момент t щонай- менше N вимог, при умові, коли обслуговування вимоги j не закінчиться А.А. Шумська ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 98 до t . Позначимо ∑ += = R jl lj 1 µγ кількість вимог з номерами вище j -го, об- слуговування яких не закінчиться до t . Як зазначено вище, достатньо точ- ною апроксимацією для розподілу jγ буде нормальний розподіл з парамет- рами , 1 ∑ += = R jl lj ga =2 jσ .)1( 1 ∑ += − R jl ll gg Умовою присутності у системі в момент t щонайменше N вимог буде ,1 Nj ≥++δγ тобто вибираємо ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ −−− Φ−= j j j aN σ δ ϕ 1 1 , де функція )(xΦ обчислюється згідно з формулами (4). Далі моделюємо згідно з алгоритмом леми. Для кожного κ>r обчис- люємо ,,...,1,)1( 1 Krbgc R rl lrrr +=−= ∏ += κϕ ∑ += = R j jcC 1 . κ Моделюємо номер r вимоги, обслуговування якої не закінчиться до t , а саме jr = з ймовірністю ./ Cc j Покладемо r=κ і збільшуємо δ на оди- ницю. 6. Обчислюємо κϕ/)(ˆ:)(ˆ RPCRP NN = (символ « =: » позначає присво- єння новому значенню деякої величини функції від її старого значення). Якщо ,N=δ то оцінка в одній реалізації для )(RPN побудована. Якщо ж ,N<δ то повторюємо алгоритм, починаючи з кроку 5. Теорема. Оцінка )(ˆ RPN є незміщеною, тобто )()(ˆ RPRP NN =M . Твер- дження теореми випливає безпосередньо із сформульованої вище леми, в якій наведено алгоритм побудови моментів надходження вимог, обслугову- вання яких не закінчиться до t . Введення вагових множників }{ rϕ суттєво підвищує точність оцінки. ЗВАЖЕНЕ МОДЕЛЮВАННЯ МОМЕНТІВ НАДХОДЖЕННЯ ВИМОГ У сформульованому вище алгоритмі моменти надходження вимог мо- делюються методом Монте-Карло. При фіксованій послідовності )(RU се- редня кількість вимог, які присутні в системі в момент t дорівнює ∑ = = R r a 1 P }{ rr t>η . Досвід моделювання згідно з наведеним вище алгорит- мом свідчить, що a змінюється в досить широкому діапазоні. Це негативно впливає на дисперсію оцінки )(ˆ RPN . Щоб запобігти цьому потрібен додат- ковий крок алгоритму, який дозволив би збільшувати значення a , звужую- Прискорене моделювання стаціонарного розподілу кількості вимог у системі ∞\|\|SMBAP G Системні дослідження та інформаційні технології, 2004, № 3 99 чи при цьому діапазон його зміни. Частково це вдається зробити за допомо- гою зваженого моделювання. Оцінки лишаються незміщеними за рахунок вагових множників. Припустимо, що всі функції розподілу )}({ xFij є абсолютно неперервни- ми з щільностями )}({ xfij . Нехай треба оцінити )( ijijij bB ξM= , де )(⋅ijb — деяка функція, яка відображає +R в +R , а випадкова величина ijξ має функ- цію розподілу )(xFij . Тоді для довільної константи 0>c має місце співвід- ношення ∫∫ ∞∞ === 00 )( )( )( )()/(1 )/( )( )( dxxf xf xcfc xcbdxcxf ccxf xfc xbB ij ij ij ijij ij ij ijij . )( )( )( ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ = ijij ijij ijij f cfc cb ξ ξ ξM Таким чином, моделюючи значення ijξ , оцінюємо ijB усередненням за значеннями )( ijij cb ξ з відповідними ваговими множниками. Згідно з цією формулою, вибираючи 1<c , маємо можливість зменшувати проміжки між зміною станів напівмарковського процесу, тим самим збільшуючи середню кількість вимог, присутніх в системі в момент t . Параметр c обирається з умови мінімізації дисперсії оцінки. Припустимо, що напівмарковський процес змінює стани в моменти }1,{ ≥nun , причому nz — стан процесу в момент 0−nu . Зменшимо про- міжки між моментами }{ nu за правилом ,1),( 11 ≥−+= ++ nuucvv nnnnn де }{ nc — вагові множники; 1<nc , а }1,{ ≥nvn — нові моменти зміни ста- нів напівмарковського процесу. Як показали чисельні розрахунки, значного скорочення дисперсії вдається досягти при лінійній апроксимації ,1)],(1[)1(1 ≥−−−= nvGcc nn де ]1,0(∈c — деяка константа, вибір якої здійснюється з умови мінімізації дисперсії. При цьому остаточна оцінка лишається незміщеною за рахунок введення вагових множників =nψ . )( ))(( 1 1 1 1 nnzz nnnzzn uuf uucfc nn nn − − + + + + Приклад Розглянемо чисельний приклад, яким проілюструємо виграш в дисперсії, що вдається досягти запропонованим методом порівняно з методом безпосе- реднього моделювання. Нехай напівмарковський процес має три стани, тоб- А.А. Шумська ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 100 то 3=m . Припустимо, що час між переходами процесу має розподіл Вейбулла, тобто 2)(1)( xa ij ijexF −−= , 0>x . Матриці )( ijaA = параметрів і )( ijpP = перехідних ймовірностей визначаються таким чином: ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = 02520 20015 20100 A , ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎝ ⎛ = 01,09,0 2,008,0 3,07,00 P . У момент переходу напівмарковського процесу в систему може надійти від однієї до трьох вимог (тобто 3=s ). Нехай =)(k ijq j/1 , jk ,...,1= , 0)( =k ijq , sjk ,...,1+= . Час обслуговування вимог має розподіл Вейбулла, 2 1)( xexG −−= . Розв’язавши систему лінійних рівнянь (1), маємо 46,01 =π ; 34,02 =π ; 20,03 =π . Позначимо L — кількість виконаних реалізацій; ),,(ˆ cLRPN — оцінка )(RPN , яка побудована за L реалізаціями запро- понованого вище алгоритму при фіксованому значенні c ( 1=c означає мо- делювання без попереднього етапу алгоритму); ),,(ˆ cLRVN — вибіркова дисперсія оцінки; ),,(ˆ),,(ˆ),,(ˆ cLRPcLRVcLRK NNN = — наближена оцінка відносної середньоквадратичної похибки; ),,(ˆ),,(ˆ),,(ˆ cLRVcLRPcLRW NNN = — наближена оцінка виграшу в дисперсії порівняно з методом Монте-Карло ( ),,(ˆ cLRPN (оцінка дисперсії у випадку використання методу Монте-Карло); )o(c — значення c , наближене до оптимального, яке мінімізує диспер- сію оцінки. Результати моделювання ймовірності )(RPN при різних значеннях N наведені в таблиці. При цьому ми обмежуємося розглядом 200=R вимог. При вказаних вище параметрах системи врахування більшої кількості вимог не має ніякого сенсу, оскільки ймовірність їх перебування у системі в мо- мент *t не перевищує 910− . Для отримання більш достовірних оцінок при різних N використову- ється різна кількість іспитів L . Спостерігається значне зростання відносної середньоквадратичної похибки )1,,(ˆ LRK N . Не вдається цього принципово уникнути і за рахунок оптимального вибору )o(c . В той же час при )o(cc = вдається досягти значного скорочення дисперсії оцінки (від 1,6 раз при 30=N до 21 разу при 50=N ) порівняно з випадком 1=c , тобто попе- редній етап алгоритму дає суттєвий ефект у скороченні дисперсії. Якщо ж порівнювати з моделюванням методом Монте-Карло, то виграш в дисперсії складає від 5,5 при 30=N до більш, ніж 70000 разів при 50=N . Прискорене моделювання стаціонарного розподілу кількості вимог у системі ∞\|\|SMBAP G Системні дослідження та інформаційні технології, 2004, № 3 101 Результати моделювання ймовірності )(RPN N 30 35 40 45 50 L 510 510 510 5 510⋅ 610 )1,,(ˆ LRPN 1,29 210−⋅ 6,32 410−⋅ 1,48 510−⋅ 2,12 710−⋅ 1,39 910−⋅ )1,,(ˆ LRVN 4,0 310−⋅ 1,2 410−⋅ 7,4 710−⋅ 2,8 910−⋅ 4,3 1310−⋅ )1,,(ˆ LRK N 4,9 17,3 58,2 247,2 471,5 L 510 510 510 2 510⋅ 3 510⋅ )o(c 0,90 0,75 0,70 0,65 0,65 ),,(ˆ )o(cLRPN 1,31 210−⋅ 6,29 410−⋅ 1,71 510−⋅ 2,45 710−⋅ 1,47 910−⋅ ),,(ˆ )o(cLRVN 2,4 310−⋅ 3,1 510−⋅ 1,1 710−⋅ 2,3 1010−⋅ 2,0 1410−⋅ ),,(ˆ )o(cLRK N 3,7 8,8 19,3 61,9 96,9 ),,(ˆ )o(cLRWN 5,5 20 155 1065 73543 ВИСНОВКИ Для системи масового обслуговування з нескінченною кількістю обслуго- вуючих пристроїв і з груповим потоком вимог складної структури запропо- новано метод прискореного моделювання стаціонарної ймовірності кількос- ті вимог в системі. Цей метод дає можливість досліджувати системи, не орієнтуючись на пуасонівський характер вхідного потоку. Порівняно з ме- тодом Монте-Карло вдалося досягти суттєвого зменшення (в середньому на два порядки) дисперсії оцінки, а, отже, і часу моделювання. Отримані ре- зультати можуть бути ефективно використані для оцінки ймовірнісних ха- рактеристик телекомунікаційних мереж. ЛІТЕРАТУРА 1. Ross K.W. Multiservice Loss Models for Broadband Telecommunication Net- works. — London: Springer, 1995. — 288 р. 2. Neuts M.F. A Versatile Markovian Point Process // J. Appl. Probab. — 1979. — 16. — P. 764–779. 3. Lucantoni D.M. New Results on the Single Server Queue with a Batch Markovian Arrival Process // Communications in Statistics: Stochastic Models. — 1991. — 7, № 1. — P. 1–46. 4. Lucantoni D.M. The BMAP/G/1 Queue: A Tutorial // Models and Techniques for Performance Evaluation of Computer and Communication Systems / Eds. L. Do- natiello, R. Nelson. — Berlin: Springer. — 1993. — P. 330–358. 5. Baum D., Kalashnikov V. Spatial Generalization of BMAPs with Finite Phase Space // J. Math. Sci. — 2001. — 105, № 6. — P. 2504–2514. 6. Baum D., Kalashnikov V. Stochastic models for communication networks with mov- ing customers // Inform. Processes. — 2001. — 1, № 1. — P. 1–18. А.А. Шумська ISSN 1681–6048 System Research & Information Technologies, 2004, № 3 102 7. Баум Д., Коваленко И.Н. Графовые модели коммуникации мобильных устройств в зонах доступа // Кибернетика и системный анализ. — 2003. — № 5. — С. 107–121. 8. Hammersley J.M., Handscomb D.C. Monte Carlo Methods. – London: Methuen, 1964. — 178 p. 9. Mandjes M. Fast Simulation of Blocking Probabilities in Loss Networks // Europ. J. Oper. Res. — 1997. — 101. — P. 393–405. 10. Sadowsky J.S., Bucklew J.A. On Large Deviation Theory and Asymptotically Effi- cient Monte Carlo Estimation // IEEE Trans. Inform. Theory. —1990. — 36. — P. 579–588. 11. Sadowsky J.S. On the Optimality and Stability of Exponential Twisting in Monte Carlo Estimation // IEEE Trans. Inform. Theory. — 1993. — 39. — P. 119–128. 12. Simonian A., Roberts J.W., Theberge F., Mazumdar R. Asymptotic Estimates for Blocking Probabilities in a Large Multi-rate Loss Network // Adv. Appl. Probab. — 1997. — 29. — P. 806–829. 13. Lassila P.E., Virtamo J.T. Efficient Importance Sampling for Monte Carlo Simula- tion of Loss Systems // Proc. of the ITC-16, Teletraffic Engineering in a Com- petitive World. — Edinburgh: Elsevier. — 1999. — P. 787–796. 14. Kovalenko I.N., Atkinson J.B., Mikhalevich K.V. Three Cases of Light-traffic Insensi- tivity of the Loss Probability in a 0/// mGGI Loss System to the Shape of the Service Time Distribution // Queueing Systems. — 2003. — 45. — P. 245–271. 15. Шумская А.А. Оценка стационарной вероятности потери в системе массового обслуживания с рекуррентными потоками требований // Кибернетика и системный анализ. — 2004. — № 2. — С. 133–145. 16. Коваленко И.H. К расчету характеристик высоконадежных систем аналитико- статистическим методом // Электрон. моделирование. — 1980. —2, № 4. — С. 5–8. 17. Завадская Л.А. Об одном подходе к ускоpению моделиpования систем с pезеpвиpованием // Электpон. моделиpование. — 1984. — 6, № 6. — С. 57–60. 18. Glynn P.W., Iglehart D.L. Importance Sampling for Stochastic Simulations // Manag. Science. — 1989. — 35. — P. 1367–1392. 19. Шпак В.Д. Аналитико-статистические оценки нестационаpных хаpактеpистик надежности и эффективности полумаpковских систем // Кибеpнетика. – 1991. — № 3. — С. 103–107. 20. Asmussen S., Rubinstein R.J., Wang C.L. Regenerative Rare Events Simulation via Likelihood Ratios // J. Appl. Probab. — 1994. — 31. – P. 797–815. 21. Glasserman P., Liu T. Rare-event Simulation for Multistage Production-inventory Systems // Manag. Science. – 1996. — 42, № 9. — P. 1292-1307. 22. Kovalenko I.N., Kuznetsov N.Yu., Pegg Ph.A. Mathematical Theory of Reliability of Time Dependent Systems with Practical Applications. — Chichester: Wiley, 1997. — 303 p. 23. Кузнецов Н.Ю. Ускоренное моделирование вероятности отказа системы, состоящей из элементов существенно различной надежности // Ки- беpнетика и системный анализ. — 1999. — № 6. —С. 48–58. 24. Juneja S., Shahabuddin P. Fast Simulation of Markov Chains with Small Transition Probabilities // Manag. Science. — 2001. — 47, № 4. — P. 547–562. Надійшла 26.02.2004

Прискорене моделювання стаціонарного розподілу кількості вимог у системі SMBAP|G| ∞

Institution

Ähnliche Einträge