Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ
“КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ”
ШМИГЕВСЬКИЙ МИКОЛА ВАСИЛЬОВИЧ
БАГАТОКАНАЛЬНІ МЕРЕЖІ ДЖЕКСОНА З
КЕРОВАНИМ ДЖЕРЕЛОМ ВИМОГ
01.05.01 – теоретичні основи інформатики та кібернетики
дисертації на здобуття наукового ступеня
кандидата фізико-математичних наук
КИЇВ-2000
Дисертацією є рукопис.
Робота виконана на кафедрі вищої математики № 2 Національного технічного університету України “Київський політехнічний інститут”.
Íàóêîâèé êåð³âíèê: êàíäèäàò ô³çèêî-ìàòåìàòè÷íèõ íàóê, ñòàðøèé íàóêîâèé ñï³âðîá³òíèê Ëåáºäºâ ªâãåí Îëåêñàíäðîâè÷,
Êè¿âñüêèé íàö³îíàëüíèé óí³âåðñèòåò ³ìåí³ Òàðàñà Øåâ÷åíêà, äîöåíò êàôåäðè ïðèêëàäíî¿ ñòàòèñòèêè.
Îô³ö³éí³ îïîíåíòè: äîêòîð ô³çèêî-ìàòåìàòè÷íèõ íàóê, ñòàðøèé íàóêîâèé
ñï³âðîá³òíèê Áðàò³é÷óê Ìèêîëà Ñåðã³éîâè÷,
²íñòèòóò ìàòåìàòèêè ÍÀÍ Óêðà¿íè,
ïðîâ³äíèé íàóêîâèé ñï³âðîá³òíèê â³ää³ëó âèïàäêîâèõ ïðîöåñ³â;
êàíäèäàò ô³çèêî-ìàòåìàòè÷íèõ íàóê,
äîöåíò Çàñëàâñüêèé Âîëîäèìèð Àíàòîë³éîâè÷,
Êè¿âñüêèé íàö³îíàëüíèé óí³âåðñèòåò ³ìåí³ Òàðàñà Øåâ÷åíêà, äîöåíò êàôåäðè ñèñòåìíîãî àíàë³çó òà òåî𳿠ïðèéíÿòòÿ ð³øåíü.
Ïðîâ³äíà óñòàíîâà: ²íñòèòóò ê³áåðíåòèêè ³ì. Â.Ì.Ãëóøêîâà ÍÀÍ Óêðà¿íè, â³ää³ë ìàòåìàòè÷íèõ ìåòîä³â òåî𳿠íàä³éíîñò³ ñêëàäíèõ ñèñòåì (ì.Êè¿â).
Захист відбудеться “ 27 ” квітня 2000 р. о 14 годині на засіданні спеціалізованої вченої ради Д 26.001.09 Київського національного університету імені Тараса Шевченка (03127, Київ, просп.Глушкова,6, факультет кібернетики).
3 дисертацією можна ознайомитись у Науковій бібліотеці Київського національного університету імені Тараса Шевченка за адресою:
01033, Київ, вул.Володимирська, 58.
Автореферат розісланий “ 20 ” березня 2000 р.
|
Вчений секретар спеціалізованої вченої ради |
Шевченко В.П. |
Актуальність теми. Роботи з проектування, впровадження, експлуатації та модернізації інформаційно-обчислювальних систем та мереж, мереж зв’язку стимулювали розвиток теорії масового обслуговування. Це привело до того, що Дж.Джексоном було введено поняття експоненційної мережі масового обслуговування (мережі черг) і були одержані результати у вигляді, який відбиває мережеву структуру моделі. Як характерні особливості цих результатів можна відзначити багатовимірність процесу обслуговування, що вивчається, збалансованість інтенсивностей потоків, мультиплікативну форму стаціонарного розподілу. Результати Дж. Джексона були розвинуті в роботах В.Гордона, Г.Ньюелла, Ф.Баскета, К.Мунтца, А.Ноетзела, Л.Клейнрока, К.Чанді, Д.Мартіна, Ф.Келлі, Дж.Уолренда, Р.Л.Добрушина, Г.П.Башаріна, П.П.Бочарова, В.А.Івницького, Г.І.Фаліна, А.Н.Дудіна, Ю.В.Малинковського, Ю.М.Сухова, М.Я. Кельберта, С.Ф.Яшкова, що привело до створення теорії мультиплікативних мереж масового обслуговування.
На розвиток теорії стохастичних мереж обслуговування значний вплив мали роботи І.І. Гіхмана, А.В. Скорохода, Ю.В. Прохорова та О.О. Боровкова, в яких було закладено основи методу дифузійної апроксимації. Цей підхід спрощує математичні викладки і дозволяє будувати апроксимативні формули для широкого класу задач. Методом дифузійної апроксимації складні стохастичні моделі вивчалися в роботах І.М. Коваленка, В.С. Королюка, В.В. Анісімова, М.М. Савчука, Є.О. Лебєдєва, Я.А. Когана, Р.Ш. Ліпцера, В.Вітта, Д.Іглехарта, Дж. Харрісона, М. Реймана та інш.
Моделі, що розглядаються в даній дисертації, відрізняються від класичних багатоканальних мереж Джексона тим, що параметри джерела вимог керуються марківським випадковим процесом. Це дозволяє більш повно досліджувати сучасні практичні задачі, пов’язані з управлінням складними технологічними процесами, створенням і експлуатацією мобільних мереж зв’язку та інформаційно-обчислювальних систем і мереж, в яких навантаження змінюється під впливом випадкового процесу. Задачі, що виникають при дослідженні таких мереж, виходять за рамки теорії мультиплікативних мереж і потребують розробки нових методів дослідження.
Зв’язок роботи з науковими програмами, планами, темами. Тематика дисертаційної роботи відноситься до планів наукових досліджень кафедри вищої математики № 2 фізико-математичного факультету Національного технічного університету України “Київський політехнічний інститут”, кафедри прикладної статистики та лабораторії ймовірносно-статистичних методів факультету кібернетики Київського національного університету імені Тараса Шевченка (бюджетні теми № 97064, № 97549), а також пов’язана з програмою INTAS – проекту № 96-0828.
Мета і задачі дослідження. Основною метою роботи є аналіз залежностей ймовірносних характеристик процесу обслуговування в багатоканальних мережах Джексона з керованим джерелом вимог та побудова ефективних алгоритмів, явних та апроксимативних формул для параметрів процесу обслуговування в перехідному та стаціонарному режимах.
Сформульована мета обумовлює наступні задачі досліджень:
- дослідження функціональних залежностей генератрис процесу обслуговування в перехідному режимі;
- пошук умов існування стаціонарного режиму для керованих мереж марківського та напівмарківського типу;
- вивчення асимптотичних властивостей біномних моментів та генератрис послідовності біномних моментів;
- побудова апроксимативного дифузійного процесу для мереж у перехідному та стаціонарному режимах при критичному навантаженні.
Застосовані методи досліджень базуються на апараті теорії масового обслуговування, теорії багатовимірного марківського відновлення, тауберових теорем для перетворень Лапласа, функціональних граничних теорем типу дифузійної апроксимації.
Наукова новизна одержаних результатів. Наукова новизна роботи полягає в тому, що вперше:
- знайдено характеристики процесу обслуговування в перехідному режимі в термінах перетворень Лапласа;
- установлено умови існування стаціонарного режиму для мереж Джексона марківського та напівмарківського типу з керованим джерелом вимог та вивчено властивості процесу обслуговування в стаціонарному режимі;
- для стаціонарного розподілу доведено узагальнений закон Джексона;
- запропоновано алгоритми ітераційного типу для побудови багатовимірної генератриси стаціонарного розподілу через біномні моменти процесу обслуговування;
- доведено функціональні граничні теореми типу дифузійної апроксимації в перехідному та стаціонарному режимах в умовах критичного навантаження мережі.
Практичне значення одержаних результатів. Дисертаційна робота має теоретичний характер і є внеском у перспективний напрямок досліджень з теорії масового обслуговування, пов’ÿçàíèé ç âèâ÷åííÿì ñèñòåì òà ìåðåæ ³ç êåðîâàíèìè ïàðàìåòðàìè.
Отримані в дисертації результати можуть знайти застосування в сучасних практичних задачах, пов’язаних з управлінням складними технологічними процесами, створенням і експлуатацією мобільних мереж зв’язку та інформаційно-обчислювальних систем і мереж, в яких параметри джерела вимог керуються марківським випадковим процесом.
Особистий внесок здобувача. Всі наукові результати, включені в дисертаційну роботу, одержано здобувачем самостійно. У роботах, íàïèñàíèõ ó ñï³âàâòîðñòâ³ ç ª. Î. Ëåáºäºâèì, íàóêîâîìó êåð³âíèêó íàëåæàòü ïîñòàíîâêè çàäà÷ òà ó÷àñòü â îáãîâîðåíí³ ðåçóëüòàò³â.
Апробація результатів дисертації. Результати роботи доповідались на наукових семінарах факультету кібернетики Київського національного університету імені Тараса Шевченка та Інституту кібернетики імені В.М.Глушкова НАН України, Чотирнадцятій Білоруській зимовій школі-семінарі з теорії масового обслуговування (Мінськ, 1998), Сьомій міжнародній науковій конференції імені академіка М.Кравчука (Київ, 1998), Міжнародному конгресі математиків (Берлін, Німеччина, 1998), Другому міжнародному симпозіумі з напівмарківських моделей (Комп’єн, Франція, 1998), Міжнародній конференції “Сучасні математичні методи дослідження телекомунікаційних мереж” (Мінськ, 1999).
Публікації. За темою дисертації опубліковано 10 наукових праць. Основні результати дисертації викладено в роботах [1-5], íàäðóêîâàíèõ у наукових фахових виданнях, які затверджено ВАК України.
Структура та обсяг роботи. Дисертаційна робота складається з вступу, трьох розділів, висновків, списку використаних джерел (89 найменувань). Загальний обсяг дисертації становить 127 сторінок, основний текст роботи (в т.ч. 3 рисунки) викладено на 119 сторінках.
У розділі 1 “Керовані мережі обслуговування марківського типу” основною моделлю, що вивчається - є - мережа. Процес надходження і обслуговування вимог у такій мережі відбувається наступним чином.
На кожний з “” обслуговуючих вузлів іззовні надходить потік вимог, який керується однорідним ланцюгом Маркова. Це означає, що моменти надходження вимог на - ий вузол співпадають з моментами змін станів ланцюга . У - ому вузлі для обслуговування вимог ми маємо необмежене число однотипних приладів. Вимога, яка надійшла для обслуговування в - ий вузол, займає будь-який прилад на час, розподілений за показниковим законом з параметром . Після обслуговування в - ому вузлі вимога з імовірністю надходить у вузол “” і з імовірністю залишає мережу, - матриця маршрутизації мережі.
Об’єктом дослідження є процес обслуговування вимог , де , - число зайнятих приладів в - ому вузлі в момент часу .
У підрозділі 1.1 дано огляд результатів для багатоканальних систем і мереж, які в наступних розділах дисертації будуть розвинуті для класу багатоканальних мереж з керованим джерелом вимог.
У підрозділі 1.2 вивчено перехідний режим процесу обслуговування вимог в - мережі.
Інформацію про перехідний режим містять генератриси вектора , де - число приладів, зайнятих в - ому вузлі вимогами, які надійшли в мережу через -ий вузол при умові, що в початковий момент керуючий процес знаходиться в стані “”. Основним результатом цього підрозділу є
Теорема 1.7. Генератриси , , , які визначають перехідний режим обслуговування вимог в мережі типу , є єдиним розв’язком системи інтегральних рівнянь
, ( 1)
де , - інфінітезимальні характеристики керуючого процесу ,
, , .
Доведення теореми 1.7 базується на лемах 1.1, 1.2.
Далі як наслідок (1) отримані інтегральні рівняння для першого і другого моменту процесу обслуговування в перехідному режимі (лема 1.3), а теорема 1.8 встановлює єдиність розв’язку цих рівнянь. У результаті перший і другий момент як функції часу знайдені в термінах перетворень Лапласа (лема 1.5).
Підрозділ 1.3 присвячений вивченню стаціонарного режиму функціонування - мереж.
Спочатку розглядається керована система обслуговування типу і для неї отримано наступний результат.
Теорема 1.9. Якщо для системи обслуговування типу керуючий ланцюг Маркова ергодичний і , то для будь-яких і
(2)
де - інфінітезимальна матриця, а - ергодичний розподіл - - вимірний вектор, складений з .
Співвідношення (2) являє собою матричний варіант формули Такача, яка отримана для системи типу без керування.
У наслідку 1.2 для першого і другого моменту стаціонарного розподілу отримано замкнені формули через параметри системи.
Далі вивчається стаціонарний режим для процесу обслуговування в мережі типу .
Нехай - число приладів, зайнятих в -ому вузлі у стаціонарному режимі, а - число приладів, зайнятих в -ому вузлі у стаціонарному режимі вимогами, які надійшли в мережу через -ий вузол, - вектор-функція, яка визначається перетворенням Лапласа
,
, ,
, , .
Основним результатом підрозділу 1.3 є
Теорема 1.11. Якщо для кожного ланцюг Маркова ергодичний, і спектральний радіус матриці маршрутизації менший , то для процесу обслуговування існує стаціонарний режим і
, , (3)
де - розв’язок рівняння балансу
, (4)
коли .
,
,
де - розв’язок рівняння балансу (4), коли , – -вимірний вектор, у якого - а компонента дорівнює 1, а інші 0.
У наслідку 1.3 отримано подання генератриси стаціонарного розподілу через генератриси перехідного режиму.
Підрозділ 1.4 присвячено узагальненню закону Джексона на випадок керованих мереж. Під законом Джексона будемо розуміти властивість незалежності компонент стаціонарного розподілу. Якщо для мережі справедливий цей закон, то структура зв’язків між вузлами мережі впливає на стаціонарний розподіл тільки через рівняння балансу. Оскільки для керованих мереж мультиплікативної форми стаціонарного розподілу немає, то закон Джексона в класичному розумінні для них не виконується. Тому було введено поняття узагальненого закону Джексона, коли незалежність компонент замінюється на некоррельованість.
Умови застосовності узагальненого закону Джексона містить
Теорема 1.14. Нехай умови теореми 1.11 виконуються і матрицю можна подати у вигляді
, , , (5)
де , , , власні числа матриці . Тоді якщо для кожного функції
,
де , перетворюються в на спектрі , матриці , то
, . (6)
У розділі 2 “Мережі з керованим джерелом вимог напівмарківського типу” вивчається більш загальна модель мереж з керованим джерелом вимог. Узагальнення має відношення до двох елементів попередньої моделі. По-перше, ускладнюється алгоритм керування вхідним потоком, по-друге, знімається припущення про показниковість часу обслуговування вимог.
Зупинимося на опису моделі. На “” обслуговуючих вузлів іззовні надходить один загальний вхідний потік вимог, який керується ланцюгом Маркова згідно наступного алгоритму. Моменти надходженння вимог співпадають з моментами , змін станів ланцюга . Якщо в момент ланцюг переходить в стан “”, то вимога з номером з імовірністю надходить для обслуговування у вузол , , - прямокутна матриця розміром .
У кожному вузлі ми маємо необмежене число однотипних обслуговуючих приладів, , - функція розподілу часу обслуговування в - ому вузлі. Після обслуговування в - ому вузлі вимога з імовірністю надходить в вузол “” і з імовірністю залишає мережу.
Для зручності посилань мережі такого типу будемо позначати через .
У підрозділі 2.1 для - мереж вивчається перехідний режим процесу обслуговування , , де , - число зайнятих приладів в - ому вузлі в момент часу , якщо в початковий момент мережа порожня та .
Показано (лема 2.1), що генератриси , векторів є єдиним розв’язком інтегральних рівнянь
(7)
,
,
де - перехідні ймовірності напівмарківського процесу , який визначається напівмарківською матрицею
,
Далі (лема 2.2, наслідок 2.1) використовуючи співвідношення (7) в термінах перетворень Лапласа знайдені перший і другий моменти процесу обслуговування як функції часу.
У підрозділі 2.2 вивчено стаціонарний режим процесу обслуговування вимог в - мережі.
Основним результатом цього підрозділу є
Теорема 2.1. Нехай ланцюг ергодичний, спектральний радіус матриці маршрутизації менший , та для . Тоді для процесу обслуговування , існує стаціонарний режим і
, (8)
де - генератриса стаціонарного розподілу.
Доведення цього результату базується на лемах 2.3 - 2.6 і результатах теорії багатовимірного марківського відновлення. Основною складністю є перевірка умови безпосередньої інтегровності за Ріманом.
Характеристики процесу обслуговування в стаціонарному режимі вивчено в
Теорема 2.2. Якщо виконуються умови теореми 2.1, то
, ,
де розв’язок рівняння балансу (4), коли ;
,
де функції , - перший і другий моменти процесу обслуговування і перетворення Лапласа , , функцій мають вигляд
,
, , - перетворення Лапласа функцій розподілу .
Порівняння теореми 2.2 з аналогічними результатами для мереж інших типів показує, що формула розрахунку математичних сподівань у стаціонарному режимі для , і - мереж інваріантна відносно типу моделі. При цьому самі стаціонарні розподіли суттєво відрізняються.
У підрозділі 2.3 вивчено властивості біномних моментів , , процесів обслуговування і .
Нехай
,
де функції , визначаються системою інтегральних рівнянь
,
,
.
Обмеженість доведена в лемі 2.8.
Позначимо через
,
.
Асимптотичні властивості біномних моментів вивчено в наступних двох теоремах.
Теорема 2.3. Нехай ланцюг Маркова ергодичний, спектральний радіус матриці менший , і для . Тоді
, ,
для довільних , функції безпосередньо інтегровні за Ріманом на і
. (9)
Теорема 2.4. Якщо виконуються умови теореми 2.3, то в області
існують генератриси , , біномних моментів , і
.
Оскільки генератриса стаціонарного розподілу , то рекурентне співвідношення (9) являє собою ефективний засіб обчислення характеристик стаціонарного розподілу. У випадку - мереж ця можливість реалізована в теоремі 2.5 і наслідку 2.2.
У підрозділі 2.4 розглянуто мережі з декількома джерелами вимог і для них доведено теореми 2.6 - 2.8. Ці результати є аналогом відповідних тверджень підрозділів 2.2 - 2.3. Введення мереж з декількома джерелами вимог дозволило систематизувати клас моделей, які вивчаються в дисертації.
У підрозділі 2.5 вивчаються потоки вимог, що завершили обслуговування в мережах напівмарківського типу. У теоремах 2.9, 2.10 знайдено інтенсивності вихідних потоків для кожного вузла - мережі. Ці результати важливі для оцінки ефективності роботи мережі обслуговування.
У розділі 3 “Дифузійна апроксимація мереж при критичному навантаженні” метод дифузійної апроксимації застосовується до багатоканальних мереж обслуговування типу і як наслідок отримано результати для мереж з керованим джерелом вимог.
У 3.1 дано огляд результатів з дифузійної апроксимації і сформульовано дві основні теореми розділу 3.
Нехай параметри вхідних потоків і інтенсивності обслуговування , мережі типу залежать від “” (номера серії) наступним чином
1) існують константи такі, що
, ,
де - стандартний броунівський рух, - означає збіжність в рівномірній топології;
2) , .
Умови 1), 2) вказують на критичне навантаження в мережі.
Вивчається послідовність випадкових процесів
, ,
,
де , , ,
- розв’язок рівняння балансу (4) при .
Для нормованого процесу обслуговування , в перехідному режимі справедлива
Теорема 3.3. Нехай мережа типу задовольняє умовам 1), 2) і спектральний радіус матриці маршрутизації менший . Тоді послідовність випадкових процесів , на будь-якому скінченному проміжку збігається в - топології до дифузійного процесу з вектором переносу і матрицею дифузії
(10)
Крім для процесу обслуговування , вивчається послідовність
, , , ,
.
Процес описує стаціонарний режим функціонування мережі. Для нього справедлива
Теорема 3.4. Нехай мережа типу задовольняє умовам 1), 2) і спектральний радіус матриці маршрутизації менший . Тоді послідовність випадкових процесів , на будь-якому скінченному проміжку збігається в -топології до дифузійного процесу Орнштейна-Уленбека () з вектором переносу і матрицею дифузії , .
У підрозділі 3.2 доведено слабку (у розумінні скінченновимірних розподілів) збіжність до . У зв’язку з цим розглянемо два незалежних - вимірних гауссівських процеси і . Процес визначається середніми значеннями
,
і коваріаційними функціями
,
, .
Для процесу
, ,
, ,
, ,
, .
Для , доведено наступний результат.
Теорема 3.5. Нехай мережа типу задовольняє умовам 1), 2) і спектральний радіус матриці маршрутизації менший . Тоді скінченновимірні розподіли процесу збігаються до скінченновимірних розподілів .
Доведення цієї теореми базується на лемах 3.1, 3.2 і використовує подання процесу обслуговування в - мережі у вигляді суми процесів індикаторного типу.
Сумарний процес є дифузійним процесом з вектором переносу і матрицею дифузії виду (10). Однак теорема 3.5 у порівнянні з теоремою 3.3 містить більше інформації про структуру граничного процесу. Доданок відповідає за флуктуації вхідного потоку, а - за флуктуації часу обслуговування. Далі в підрозділі 3.3 твердження теореми 3.5 посилено до збіжності в рівномірній топології (теорема 3.6).
Підрозділ 3.4 містить результати про дифузійну апроксимацію , , які аналогічні тим, що були отримані в 3.2, 3.3 для послідовності , . У підрозділі 3.5 наведено застосування загальних граничних теорем 3.3, 3.4 до мереж з керованим джерелом вимог.
Ó âèñíîâêàõ ñôîðìóëüîâàíî îñíîâí³ ðåçóëüòàòè é âêàçàí³ øëÿõè ¿õ ìîæëèâîãî çàñòîñóâàííÿ.
У дисертації отримано нові науково обгрунтовані результати для класу стохастичних багатоканальних мереж Джексона з керованим джерелом вимог, які суттєво розвивають теорію мереж і в сукупності розв’язують важливе наукове завдання аналізу і розрахунку характеристик ефективності функціонування керованих моделей мережевої структури.
Основні наукові результати дисертації:
Знайдено характеристики процесу обслуговування в перехідному режимі у термінах перетворень Лапласа.
Установлено умови існування стаціонарного режиму для мереж Джексона марківського та напівмарківського типу з керованим джерелом вимог та вивчено властивості процесу обслуговування в стаціонарному режимі.
Для стаціонарного розподілу доведено узагальнений закон Джексона.
Запропоновано алгоритми ітераційного типу для побудови багатовимірної генератриси стаціонарного розподілу через біномні моменти процесу обслуговування.
5. Доведено функціональні граничні теореми типу дифузійної апроксимації в перехідному та стаціонарному режимах в умовах критичного навантаження мережі.
Результати дисертації можуть знайти застосування в сучасних практичних задачах, пов’язаних з управлінням складними технологічними процесами, створенням і експлуатацією мобільних мереж зв’язку та інформаційно-обчислювальних систем і мереж, в яких параметри джерела вимог керуються марківським випадковим процесом.
Лебедев Е.А., Шмигевский Н.В. О стационарном распределении управляемых сетей типа // Доповіді НАН України. Серія: математика, природознавство, технічні науки. - 1998. - № 2. - С. 120-123.
Шмигевський М.В. Керовані мережі з вузлами типу // Вісник Київського університету. Серія: фізико-математичні науки. - 1997. - № 3. - С. 222-230.
Шмигевський М.В. Про мережі Джексона у марківському випадковому середовищі // Вісник Київського університету. Серія: фізико-математичні науки. - 1999. - № 1. - С. 243-248.
Шмигевський М. В. Про одне узагальнення формул Такача для керованих мереж обслуговування // Вісник Київського університету. Серія :фізико-математичні науки. - 1999. - №3. – С. 281-287.
Шмигевський М. В. Про біномні моменти для багатоканальних мереж Джексона // Наукові вісті НТУУ “КПІ”. –1999. - №3.- С. 137-144.
Шмигевский Н.В. Об одном типе стохастических сетей в случайной среде // Массовое обслуживание. Потоки, системы, сети. Сборник материалов 14 Белорусской зимней школы-семинара по теории массового обслуживания. - Минск. - 1998. - С. 128-131.
Шмигевський М.В. Про закон Джексона для керованих стохастичних мереж// Сьома Міжнародна наукова конференція імені академіка М.Кравчука. 14-16 травня 1998 р. - Київ. - 1998. - С. 537.
Лебедев Е. А., Шмигевский Н. В. Сети обслуживания с многоканальными узлами в случайной среде // Кибернетика и системный анализ. –2000. – №1. – С.167 – 172.
Lebedev E.A., Shmygevskyy M.V. Controlled networks of queues with - nodes // Proceedings of the 2-nd International Symposium on Semi-Markov Models: Theory and Applications. - Universite de Technologie de Compiegne, France. - 1998. - Р. 1-6.
Lebedev E. A., Shmygevskyy M.V. Networks of queues with multiserver nodes and controlled sourse of calls // Proceedings of the International Conference “Modern mathematical methods of investigating the telecommunicational networks”. - Minsk, 1999. - P. 72-74.
Øìèãåâñüêèé Ì.Â. Áàãàòîêàíàëüí³ ìåðåæ³ Äæåêñîíà ç êåðîâàíèì äæåðåëîì âèìîã. – Ðóêîïèñ.
Äèñåðòàö³ÿ íà çäîáóòòÿ íàóêîâîãî ñòóïåíÿ êàíäèäàòà ô³çèêî-ìàòåìàòè÷íèõ íàóê çà ñïåö³àëüí³ñòþ 01.05.01 – òåîðåòè÷í³ îñíîâè ³íôîðìàòèêè òà ê³áåðíåòèêè. – Êè¿âñüêèé íàö³îíàëüíèé óí³âåðñèòåò ³ì. Òàðàñà Øåâ÷åíêà, Êè¿â, 2000.
Äèñåðòàö³þ ïðèñâÿ÷åíî ïåðñïåêòèâíîìó íàïðÿìêó òåî𳿠ìàñîâîãî îáñëóãîâóâàííÿ, ïîâ’язаному з вивченням систем та мереж із керованими параметрами. Вперше досліджено процес обслуговування вимог у багатоканальній мережі Джексона марківського та напівмарківського типу з керованим джерелом вимог. Методом перетворень Лапласа знайдено параметри обслуговування в перехідному режимі. Встановлено умови існування стаціонарного режиму і для стаціонарного розподілу доведено узагальнений закон Джексона. Властивості процесу обслуговування в стаціонарному режимі вивчено в термінах багатовимірних біномних моментів. Для перевантаженого режиму роботи багатоканальних мереж доведено функціональні граничні теореми типу дифузійної апроксимації. На основі проведених досліджень побудовано ефективні алгоритми, явні та апроксимативні формули для параметрів процесу обслуговуваня в перехідному та стаціонарному режимах.
Ключові слова: мережа обслуговування, кероване джерело вимог, перехідний режим, стаціонарний режим, закон Джексона, біномні моменти, перевантажений режим, дифузійна апроксимація.
Шмигевский Н.В. Многоканальные сети Джексона с управляемым источником требований. - Рукопись.
Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Киевский национальный университет им. Тараса Шевченко, Киев, 2000.
Диссертация посвящена перспективному направлению теории массового обслуживания, связанному с изучением систем и сетей с управляемыми параметрами. Впервые исследован процесс обслуживания требований в многоканальной сети Джексона марковского и полумарковского типа с управляемым источником требований.
Для производящих функций процесса обслуживания требований в переходном режиме получена система интегральных уравнений и изучены условия существования и единственности ее решения. В терминах преобразований Лапласа найдены характеристики процесса обслуживания в переходном режиме. При условии, что управляющая цепь Маркова эргодична, спектральный радиус матрицы маршрутизации меньше и интенсивности обслуживания требований , в каждом из узлов не равны , доказано существование стационарного режима. Установлено, что производящая функция стационарного распределения определяется параметрами сети и спектральными характеристиками матрицы , где , , - символ Кронекера. Найдены условия справедливости обобщенного закона Джексона, когда независимость компонент стационарного распределения заменяется на некоррелируемость. Показано, что достаточным условием некоррелируемости является обращение в нуль на спектре матрицы вектор-функции вида , где - интенсивность входного потока на - й узел, а , определяются параметрами цепи Маркова, которая управляет входным потоком на - й узел.
Процесс обслуживания требований в сетях полумарковского типа изучен в терминах многомерных биномиальных моментов. Для биномиальных моментов и их производящей функции получены системы интегральных уравнений типа марковского восстановления. Показано, что при условии эргодичности управляющей цепи Маркова, открытости сети и конечности математических ожиданий времен обслуживания, к системам интегральных уравнений применимы результаты асимптотической теории марковского восстановления. Как следствие доказано существование стационарного режима и предложен алгоритм итерационного типа для построения производящей функции стационарного распределения на основании биномиальных моментов.
Для перегруженного режима работы многоканальных сетей доказаны функциональные предельные теоремы типа диффузионной аппроксимации. Показано, что основными условиями для аппроксимации скачкообразного процесса обслуживания непрерывным диффузионным процессом является справедливость функциональной центральной предельной теоремы для входного потока и открытость сети. В случае переходного режима функционирования сети при критической нагрузке показана сходимость в равномерной метрике нормированного процесса обслуживания к многомерной диффузии с вектором переноса и матрицей диффузии , компоненты которой определены в явном виде через параметры сети. При стационарном режиме функционирования предельный процесс является многомерным диффузионным процессом Орнштейна-Уленбека.
На основе проведенных исследований построены эффективные алгоритмы, явные и аппроксимативные формулы для параметров процесса обслуживания в переходном и стационарном режимах.
Ключевые слова: сеть обслуживания, управляемый источник требований, переходной режим, стационарный режим, закон Джексона, биномиальные моменты, перегруженный режим, диффузионная аппроксимация.
Shmygevskyy M.V. Multi-channel Jackson’s networks with controlled source of calls. – Manuscript.
Thesis for the degree of candidate of physical and mathematical sciences, speciality 01.05.01 – theoretical bases of computer science and cybernetics. – Taras Shevchenko Kyiv University, Kyiv, 2000.
The thesis is devoted to perspective trend of queuing theory connected with investigation of queuing systems and networks with controlled parameters. Service process of calls in multi-channel Jackson’s networks of the Markov and semi-Markov type with controlled source of calls is investigated for the first time. Service parameters in transient regime are found by the Laplace transformation method. Conditions of existence in stationary regime are determined and the extended Jackson’s law is proved for stationary distribution. Service process properties in stationary regime are analyzed in terms of multivariate binomial moments. Functional limit theorems of the diffusion approximation type are proved for multi-channel systems in heavy traffic regime. Effective algorithms, evident and approximate formulae for the service process parameters in transient and stationary regimes are constructed on the basis of the performed research.
Key words: network, controlled source of calls, transient regime, stationary regime, Jackson’s law, binomial moments, heavy traffic regime, diffusion approximation.
______________________________________________________________________________
Підп.до друку 17.03.2000. Формат 60х84 1/16. Папір “Maestro Guttenberg”.
Друк виконано на обладнанні RISO – 1510. Ум. друк. арк. 1,25. Наклад 100 прим.
Замовлення № 47.
_______________________________________________________________________________
Фірма “ГНОЗІС”
01034, Україна, Київ-34, вул.Пушкінська, 12, оф.19
Тел./факс: 235-80-96, 228-37-34.