Оптимальне управління інформаційними потоками в багатоканальних мережах

Размещено на http://www.allbest.ru/

КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ТАРАСА ШЕВЧЕНКА

УДК 519.21

01.05.04 - системний аналіз і теорія оптимальних рішень

Автореферат

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

ОПТИМАЛЬНЕ УПРАВЛІННЯ ІНФОРМАЦІЙНИМИ ПОТОКАМИ В БАГАТОКАНАЛЬНИХ МЕРЕЖАХ

Макушенко Ігор Анатолійович

КИЇВ - 2006

Дисертацією є рукопис.

Робота виконана на кафедрі прикладної статистики факультету кібернетики Київського національного університету імені Тараса Шевченка.

Науковий керівник: Доктор фізико-математичних наук, старший науковий співробітник Лебєдєв Євген Олександрович, Київський національний університет імені Тараса Шевченка, завідувач кафедри прикладної статистики факультету кібернетики.

Офіційні опоненти:

Доктор фізико-математичних наук, професор Єлейко Ярослав Іванович, Львівський національний університет імені Івана Франка, завідувач кафедри теоретичної та прикладної статистики;

Кандидат фізико-математичних наук, доцент Іксанов Олександр Маратович, Київський національний університет імені Тараса Шевченка, доцент кафедри дослідження операцій.

Провідна установа:

Інститут кібернетики імені В.М.Глушкова НАН України, відділ математичних методів дослідження операцій, м. Київ.

Захист відбудеться "18" травня 2006р. о 14.00 год. на засіданні спеціалізованої вченої ради Д 26.001.35 Київського національного університету імені Тараса Шевченка за адресою:03127, Київ, пр. Глушкова, 2, корп. 6, ф-т кібернетики, ауд. 40. (Тел. 2525883. Факс 252-59-77. E_mail: rada@unicyb.kiev.ua)

З дисертацією можна ознайомитись в науковій бібліотеці Київського національного університету імені Тараса Шевченка за адресою: 01033, Київ, вул. Володимирська, 58.

Автореферат розісланий "18" травня 200 р.

Вчений секретар спеціалізованої вченої ради П.М. Зінько



ЗАГАЛЬНА ХАРАКТЕРИСТИКА

Актуальність теми. Становлення теорії стохастичних мереж та її розвиток в значній мірі стимулювались практичними задачами з проектування та модернізації інформаційно-обчислювальних систем та мереж. Опис перших підходів до аналізу стохастичних мереж був наданий у роботах Дж. Джексона, В. Гордона, Г. Ньюелла, в яких були одержані результати для експоненціальних стохастичних мереж. Ці результати знайшли широке практичне застосування після виходу роботи Ф. Мура, який показав, що стохастичні мережі є адекватними моделями функціонування інформаційно-обчислювальних мереж. Слід зазначити, що область застосування моделей стохастичних мереж значно розширюється, якщо зняти припущення про експоненціальний характер часу обробки інформації у вузлах мережі, оскільки в реальних інформаційно-обчислювальних мережах функції розподілу часу обробки у вузлах відрізняються від експоненціальних. У теперішній час теорія стохастичних мереж одержала визнання як один з основних перспективних напрямків моделювання інформаційно-обчислювальних мереж та мереж зв'язку. Теоретичне дослідження стохастичних мереж та їх практичне застосування знайшли відображення в роботах Г.П. Башаріна, П.П. Бочарова, А.Л. Толмачова, В.Г. Бєлякова, Ю.І. Митрофанова, В.А. Жожикашвілі, В.М. Вишневського, В.В. Анісімова, Є.О. Лебєдєва, Л. Клейнрока, Д. Меламеда, Дж.В. Вонга, В. Вітта, В.А. Івницького, М.Я. Кельберта та інш.

Аналіз та синтез інформаційно-обчислювальних мереж, сучасних мереж мобільного зв'язку вимагає розв'язку оптимізаційних задач для стохастичних мереж. Загальну класифікацію типів постановок оптимізаційних задач і методів їх розв'язування дано у монографіях В.М. Глушкова та Л. Клейнрока. Головними є задачі розподілу інформаційних потоків, вибору пропускних спроможностей та топологічної структури мережі. Повнота розв'язку цих задач залежить від керуючих розподілів мережі, складності алгоритму маршрутизації та виду функцій вартості. В цьому напрямку досліджень можна виділити роботи Б.В. Гнеденка, І.М. Коваленка, О.Д. Соловйова, П.П. Печінкіна, С.Ф. Яшкова, М.В. Бурлакова, В.В. Мови, Л.О. Пономаренка, А.А. Назарова, В.В. Рикова, О.Д. Дудіна, В.І. Кліменок, Р.В. Конвея, В.Л. Максвелла, Л.В. Мюллера.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалась відповідно до плану наукових досліджень кафедри прикладної статистики факультету кібернетики Київського національного університету імені Тараса Шевченка в рамках науково-дослідної теми № 01БФ015-01 “Розвиток теорії і програмного забезпечення стохастичних та алгебраїчних систем із застосуванням в економіці, соціології, техніці та освіті” (№ держреєстрації 0101U002173), а також пов'язана з тематикою DFG проекту “Математичні моделі економічного ризику” № 436 UKR 113/70/0-1.

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

Сформульована мета обумовлює наступні задачі досліджень:

дослідження функціональних залежностей для генератрис процесу обробки інформації і накопичення прибутку в марковських та напівмарковських моделях багатоканальних стохастичних мереж;

вивчення асимптотичних властивостей систем інтегральних рівнянь, що описують роботу стохастичних мереж напівмарковського типу;

проведення класифікації оптимізаційних задач за параметрами мережі для немарковських моделей багатоканальних стохастичних мереж;

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

Застосовані методи досліджень базуються на апараті теорії масового обслуговування, теорії багатовимірного марковського відновлення, тауберових теорем для перетворень Лапласа, функціональних граничних теорем типу гауссівської апроксимації.

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

вивчено характеристики процесу обробки інформації і накопичення прибутку в марковських моделях багатоканальних стохастичних мереж;

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

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

досліджено тип оптимізаційних задач для багатоканальних стохастичних мереж з керованим вхідним потоком;

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

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

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

Особистий внесок здобувача. Всі наукові результати, включені в дисертаційну роботу, отримані здобувачем самостійно. У роботах, написаних у співавторстві з Лебєдєвим Є.О., проведення асимптотичного аналізу систем інтегральних рівнянь та знаходження цільових функцій для оптимізаційних задач у марковських та напівмарковських моделях багатоканальних стохастичних мереж виконано здобувачем, науковому керівнику належать постановки задач та участь в обговоренні результатів.

Апробація результатів дисертації. Дисертаційна робота пройшла достатню апробацію. Результати дисертаційної роботи доповідались на Міжнародній конференції “Belarussian Winter Workshop on Queung Theory” (Мінськ, 2001); Міжнародній конференції “Prediction and Decision Making under Uncertainties” (Київ, 2001); Міжнародній конференції “Problems of decision making and control under uncertainties” (Київ-Канів, 2002); Міжнародній конференції “Problems of decision making under uncertainties” (Алушта, 2003); Міжнародній конференції ''Prediction and decision making under uncertainties" (Тернопіль, 2004); Міжнародній конференції “Belarussian Winter Workshop on Queung Theory” (Мінськ, 2005); Міжнародній конференції “Problems of stochastic and discrete optimization” (Київ-Канів, 2005). Матеріали дисертаційного дослідження доповідалися на наукових семінарах Київського національного університету імені Тараса Шевченка.

Публікації. За темою дисертації опубліковано 10 наукових праць. Основні результати дисертації викладено в роботах [1] - [3], надрукованих у наукових фахових виданнях, які затверджено ВАК України.

Структура та обсяг роботи. Дисертаційна робота складається з вступу, трьох розділів, висновків, списку використаних джерел (89 найменувань). Загальний обсяг дисертації становить 128 сторінок, основний текст роботи (в т.ч. 3 рисунки) викладено на 119 сторінках.

ОСНОВНИЙ ЗМІСТ

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

У розділі 1 “Оптимальне керування вхідним потоком у марковських моделях стохастичних мереж” основною моделлю, що вивчається, є _ мережа з керованим джерелом вхідних інформаційних пакетів. Процес надходження і обробки пакетів інформації у такій мережі відбувається наступним чином.

На “r” вузлів обробки інформації надходить один зовнішній пуассонівський потік інформаційних пакетів інтенсивності “”. Пакет, що надійшов на вхід мережі, з імовірністю , надходить для обробки в i-тий вузол, .

Кожен з “r” вузлів представляє собою багатоканальну стохастичну систему. При надходженні інформаційного пакету у таку систему зразу починається його обробка. Час обробки розподілений за показниковим законом з параметром , . Після завершення обробки в i-ому вузлі пакет з імовірністю передається у вузол “j” і з імовірністю залишає мережу, - матриця маршрутизації мережі. Зручно ввести додатковий вузол з номером “” та інтерпретувати його як “вихід” з стохастичної мережі.

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

На процесі X(t), визначимо адитивний функціонал , де , - число пакетів, обробка яких завершилася в i-ому вузлі за час t. Оскільки визначає сумарний прибуток від роботи мережі на проміжку [0,t], то процес , будемо називати процесом накопичення прибутку. Через , , позначимо багатовимірну генератрису вектора .

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

Теорема 1.1. Для генератриси справедливе подання

де генератриси , є єдиним розв'язком системи інтегральних рівнянь .

Перейдемо до постановки оптимізаційних задач.

Якщо існують границі , то будемо позначати їх через , . Очевидно, що залежить від параметрів _ мережі:. У подальшому будемо вважати, що є заданими, а вибір вектора h знаходиться в нашому розпорядженні. Таким чином , . Аналогічно, якщо існують границі , то будемо позначати їх через.

Нехай , - прибуток від обробки одного пакету в i-ому вузлі. Тоді важливе значення має наступна задача

Розв'язок задачі (3), (4) представляє собою таке управління вхідним потоком, яке максимізує середній прибуток від роботи всієї мережі.

Очевидно, що - величина ризику, міра відхилення прибутку від очікуваного значення . Враховуючи це, ми приходимо до оптимізаційної задачі виду

де - задана величина середнього прибутку, - мінімальне значення функціоналу при обмеженнях (4).

Пріоритетність оптимізаційних задач (3), (4) і (5) - (7) залежить від мети управління стохастичною мережею.

Введемо позначення: - одинична матриця, - r_вимірний вектор, у якого компонента з номером дорівнює 1, а інші дорівнюють 0; - матриця розміром , у якій діагональний елемент з номером дорівнює 1, а інші елементи дорівнюють 0;.

Основним результатом першого розділу є наступне твердження.

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

У підрозділі 1.4 цей результат було узагальнено на випадок стохастичних мереж типу з періодично змінною за часом інтенсивністю вхідного потоку.

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

Задача на пошук максимуму прибутку від роботи мережі набуває такого вигляду:

(10)

Задача мінімізації ризику для мережі типу формулюється наступним чином:

Для того, щоб розв'язати задачі (10), (11), необхідно подати функціонали і через параметри мережі. Для цієї мети служить наступний результат.

Теорема 1.3. Якщо спектральний радіус матриці маршрутизації Р строго менший 1, тоді існують і

Доведення теореми 1.3 базується на наступному результаті.

Нехай , - гіллястий процес Беллмана-Харріса з 2r типами частинок Т1,…,Тr,Tr+1,…,T2r. Кожна з частинок типу Тi має випадкову тривалість життя з функцією розподілу , причому

Генератриси безпосередніх нащадків від однієї частинки типу Ті дорівнюють

Лема 1.1. Нехай виконуються умови теореми 1.3., тоді

визначаються як єдиний розв'язок взаємопов'язаних систем інтегральних рівнянь

У розділі 2 “Максимізація прибутку та мінімізація ризику в мережах напівмарковського типу” оптимізаційні задачі розглядаються для більш загальних моделей багатоканальних стохастичних мереж типу В цих моделях суттєво ускладнюється алгоритм керування вхідним потоком, а також знімається припущення про показниковість часу обробки інформаційних пакетів.

Алгоритм обробки інформації у такій мережі подано нижче.

У - мережі на “r” вузлів обробки інформації надходить один загальний потік пакетів, який керується напівмарковським процесом. Це означає, що моменти надходження пакетів співпадають з моментами змін станів x(t). Якщо у момент процес x(t) переходить у стан “i”, то пакет з номером “n” з імовірністю надходить для обробки у вузол “j”, - прямокутна матриця розміром . Через будемо позначати напівмарковську матрицю процесу x(t), - матриця перехідних імовірностей вкладеного ланцюга Маркова для x(t), , - функція розподілу часу перебування у стані “i”.

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

Дослідження процесу обробки інформації X(t) і накопичення прибутку S(t) у - мережах потребує вивчення багатовимірних процесів , , де _ число пакетів у j-ому вузлі в момент часу t, якщо у початковий момент мережа порожня, , і момент надходження першого пакету в мережу співпадає з моментом виходу з “i”; - число пакетів, обробка яких завершилася в j-ому вузлі за час t, якщо на керуючий напівмарковський процес накладені такі ж початкові умови. Через будемо позначати багатовимірні генератриси векторів , відповідно.

Для процесу накопичення прибутку доведено наступний результат.

Теорема 2.1. Функції , є єдиним розв'язком системи інтегральних рівнянь

На основі цього результату досліджено задачу максимізації прибутку в класі- мереж.

Нехай , - середній час перебування процесу х(t) у стані “i”. Якщо матриця перехідних імовірностей F вкладеного ланцюга Маркова для x(t) нерозкладна, то через будемо позначати стаціонарні імовірності вкладеного ланцюга, ,.

Теорема 2.2. Якщо для- мережі матриця F нерозкладна, , і спектральний радіус матриці маршрутизації P строго менший 1, то границя існує і

Наслідок 2.3. При виконанні умов теореми 2.2 задача максимізації середнього прибутку для мережі є задачею лінійного програмування виду

Зазначимо, що оптимізаційна задача (16), (17) розв'язується з точки зору менеджера мережі. Якщо користувач мережею може обирати матрицю H, то він буде намагатись мінімізувати функціонал у (16): шукати таке управління , яке забезпечить мінімум середніх витрат за обробку інформаційного потоку.

Перейдемо тепер до аналізу задачі мінімізації ризику в класі стохастичних мереж типу . Нехай - матриця відновлення для керуючого напівмарковського процесу x(t). Відомо, що якщо напівмарковська матриця F(t) - негратчаста, F - нерозкладна і , то

де - скінченна матриця, яка явно виписується через параметри x(t):

- матриця розміром, рядки якої однакові і співпадають з стаціонарним розподілом вкладеного ланцюга Маркова (- N-вимірний вектор, складений з одиниць, ,-П потенціал вкладеного ланцюга Маркова.

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

Теорема 2.4. Якщо для- мережі матриця F(t) негратчаста, F - нерозкладна, , спектральний радіус матриці маршрутизації P строго менший 1 і , то задача мінімізації ризику є задачею квадратичного програмування виду

У формулах (19), (20) і цільова функція, і обмеження, які окреслюють область допустимих значень, виписані явно через параметри- мережі. Для розв'язку задачі мінімізації ризику можна застосовувати ефективні алгоритми квадратичного програмування.

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

Наслідок 2.11. Якщо для- мережі виконуються умови теореми 2.4 і додатково то задача мінімізації ризику є задачею лінійного програмування, цільова функція якої задається формулою (21).

Наслідком (23) є те, що у класі - моделей при умові задача мінімізації ризику є задачею лінійного програмування. Для пуассонівського вхідного потоку ця умова, очевидно, виконується. Таким чином наслідок 2.11 пояснює той факт, що у класі марковських моделей стохастичних мереж (розділ 1) цільова функція для задач мінімізації ризику була лінійною.

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

У розділі 3 “Розв'язок оптимізаційних задач при критичному навантаженні в мережі” для побудови цільових функцій в оптимізаційних задачах використовується метод гауссівської апроксимації.

Спочатку розглядається модель _ мережі, в якій на структуру вхідного потоку не накладається ніяких обмежень. Для моделювання процесу обробки інформації сумісно з процесом накопичення прибутку будемо використовувати 2r-вимірний гіллястий процес Беллмана-Харріса, , який задається генератрисою безпосередніх нащадків: де , - компоненти матриці маршрутизації, - імовірність виходу пакету з мережі після обробки в i-ому вузлі. Тривалості життя мають функції розподілу: для (ф. р. часу обробки в i-ому вузлі) і

Режим критичного навантаження в- мережі означає, що її параметри залежать від “n” (номера серії) так, що виконуються наступні умови.

1) Для багатовимірного вхідного потоку (- кількість інформаційних пакетів, що надійшли іззовні в i-ий вузол мережі на проміжку часу) існують константи, такі, що

де, - r-вимірний процес броунівського руху з нульовим вектором математичних сподівань і кореляційною матрицею, символ “” означає слабку збіжність у рівномірній топології.

2) Послідовність (за параметром n) функцій розподілу часу обробки у вузлах мережі слабко збігається до граничної

Нехай для будь-яких випадкових векторів, ,

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

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

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

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

Розглянемо послідовність випадкових процесів, матриці визначаються так само, як і із заміною функції розподілу на.

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

Теорема 3.1. Нехай стохастична мережа типу у початковий момент часу порожня, задовольняє умовам 1), 2) і спектральний радіус матриці маршрутизації P строго менший 1. Тоді на будь-якому скінченному проміжку послідовність випадкових процесів, , слабко збігається у рівномірній топології до.

В підрозділі 3.3 на основі теореми 3.1 побудовано апроксимативний процес для перевантаженого режиму роботи мережі типу. Цей процес використовується для побудови цільових функцій в оптимізаційних задачах.

Так у наслідку 3.3 виписані цільові функції для задачі максимізації прибутку у перехідному та стаціонарному режимах при загальних умовах на параметри моделі.

В умовах критичного навантаження інтенсивності і елементи матриці (умова 1)) функціонально зв'язані, причому характер цього зв'язку невідомий і залежить від структури вхідного потоку. Тому при аналізі задачі мінімізації ризику і підрахунку функціоналів фіксується певна структура вхідного потоку.

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



ВИСНОВКИ

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

Основні наукові результати дисертації.

Знайдено характеристики процесу накопичення прибутку для марковських багатоканальних стохастичних мереж.

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

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

Доведена функціональна гранична теорема типу гауссівської апроксимації для процесу накопичення прибутку в умовах критичного навантаження в мережі.

Для немарковських моделей проведено класифікацію оптимізаційних задач за параметрами мережі.

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



СПИСОК ОПУБЛІКОВАНИХ НАУКОВИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Макушенко І.А., Лебєдєв Є.О. Оптимізація структури вхідного потоку для _ мережі // Вісник Київського університету. Серія: фізико-математичні науки. - 2001. - Вип. №3. - С. 257-268.

2. Макушенко І.А. Оптимізація структури вхідного потоку періодичної інтенсивності для _ мережі // Вісник Київського університету. Серія: фізико-математичні науки. - 2002. - Вип. №4. - С. 198-207.

3. Макушенко І.А., Лебєдєв Є.О. Керування напрямком вхідного потоку для багатоканальних мереж // Журнал обчислювальної та прикладної математики. Серія: фізико-математичні науки. - 2003. - Вип. №2 (89). - С. 26-36.

4. Makushenko I.A., Lebedev E.A. Optimization of input structure in the _ networks // Abstracts of the International Conference “Belarussian Winter Workshop on Queung Theory”, January 23-25, Minsk. - Минск, 2001. - С. 42_46.

5. Макушенко І.А. Про мінімізацію ризику в моделях мережевої структури // Наукові праці міжнар. конф. “Prediction and Decision Making under Unsertainties”, September 11-14, Kyiv. - К., 2001. - С. 104-106.

6. Макушенко І.А., Лебєдєв Є.О. Про оптимальне керування вхідним потоком періодичної інтенсивності // Abstracts of the International Conference “Problems of Decision Making and Control under Uncertainties”, May 14-19, Kiev - Kaniv. - К., 2002. - C. 77-78.

7. Makushenko I., Lebedev E. About risk structure minimization for controlled multi-channel networks // Abstracts of the International Conference “Problems of Decision Making under Uncertainties”, September 8-12, Alushta. - К., 2003. - С. 33_36.

8. Makushenko I., Lebedev E. About optimization of input structure in the _ networks // Abstracts of the International Conference “Prediction and Decision Making under Uncertainties”, May 29-30, Ternopil. - Т., 2004. - С. 35-36.

9. Макушенко И.А. Об оптимальном управлении входным потоком для многоканальных сетей полумарковского типа // Материалы междунар. научной конф. “Математические методы повышения эффективности функционирования телекоммуникационных сетей”, 22-24 февраля, Минск. - Минск, 2005. - С. 114-115.

10. Макушенко І.А. Про оптимізацію структури вхідного потоку для багатоканальних мереж // Наукові праці міжнар. конф. “Problems of Stochastic and Discrete Optimization”, May 2005, Kyiv - Kaniv. - К., 2005. - С. 85-86.



АНОТАЦІЇ

Макушенко І.А. Оптимальне управління інформаційними потоками в багатоканальних мережах. Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.04 системний аналiз i теорiя оптимальних рішень. Київський національний університет імені Тараса Шевченка, Київ, 2006.

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

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

Ключові слова: оптимальне управління, інформаційний потік, багатоканальна мережа, максимізація прибутку, мінімізація ризику, інтегральне рівняння, перевантажений режим, гауссівська апроксимація.



Макушенко И.А. Оптимальное управление информационными потоками в многоканальных сетях. Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.04 системный анализ и теория оптимальных решений. Киевский национальный университет имени Тараса Шевченко, Киев, 2006.

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

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

Проведен асимптотический анализ систем интегральных уравнений, которые описывают работу стохастической сети полумарковского типа. Показано, что к системам интегральных уравнений применимы результаты асимптотической теории марковского восстановления. Как следствие, для немарковских моделей проведена классификация оптимизационных задач в зависимости от параметров сети. Показано, что задача поиска максимума средней прибыли при любых значениях параметров сети является задачей линейного программирования. Если для случайного интервала времени между моментами поступления пакетов в моделях типа коэффициент вариации =1, то задача минимизации риска также является задачей линейного программирования. При задача минимизации риска является задачей квадратического программирования.

Разработан метод гауссовской аппроксимации для подсчета функционалов оптимизационных задач в условиях критической нагрузки в сети. Показано, что основными условиями для аппроксимации процесса накопления прибыли гауссовским процессом является справедливость функциональной центральной предельной теоремы для входного потока и открытость сети.

На основе проведенных исследований построены эффективные алгоритмы, явные и аппроксимативные формулы для целевых функций оптимизационных задач через параметры модели.

Ключевые слова: оптимальное управление, информационный поток, многоканальная сеть, максимизация прибыли, минимизация риска, интегральное уравнение, перегруженный режим, гауссовская аппроксимация.



Makushenko I.А. Optimal control of information flows in multi-channel networks. Manuscript.

Thesis for the degree of candidate of physical and mathematical sciences, speciality 01.05.04 systems analysis and theory of optimal decisions. Kyiv Taras Shevchenko national university, Kyiv, 2006.

The thesis is devoted to perspective direction of queuing theory connected with investigation of queuing systems and networks with controlled parameters. For multi-channel stochastic networks the characteristics of accumulative process of income are firstly investigated. In the case of fixed and periodical-variable rate of input flow goal functions of optimization problems are found. Asymptotical analysis of systems of integral equations for semi-Markov stochastic networks is realized. For multi-channel stochastic networks with controlled input flow the type of optimization problems is determined. To calculate of goal functions for stochastic networks in heavy traffic the method of Gaussian approximation is developed.

Effective algorithms, evident and approximate formulas for the goal functions of optimization problems via model parameters are constructed on the basis of the performed research.

Key words: optimal control, information flow, multi-channel network, maximization of income, minimization of risk, integral equation, heavy traffic regime, Gaussian approximation.

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