Цифровий оптимальний екстраполятор нестаціонарного трафіку комп’ютерних мереж

УКРАЇНА (19) UA (11) 60390 (13) U (51) МПК G06G 7/30 (2006.01) G05B 13/02 (2006.01) G05B 15/02 (2006.01) МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ видається під відповідальність власника патенту ОПИС ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) ЦИФРОВИЙ ОПТИМАЛЬНИЙ ЕКСТРАПОЛЯТОР НЕСТАЦІОНАРНОГО ТРАФІКУ КОМП'ЮТЕРНИХ МЕРЕЖ 1 тервал кореляції завади;  2 - середнє квадратич не відхилення завади; γ - параметр нелінійності нестаціонарного випадкового трафіку; my1 , my 2 , my 3 - математичні сподівання значень трафіку, що спостерігають у моменти часу t1, t2, t3, 2 2 2 відповідно;  y1 ,  y 2 ,  y 3 - середні квадратичні відхилення значень Y1, Y2, Y3 у моменти часу t1, t2, t3, відповідно; паралельно з другого виходу бази даних БД (блок 1) по команді БУС-2 на вхід систе  mY    m Y1 m Y2  m Y3  2 2  k Y t1, t 2   k Y t 2 , t 3  ; Y mY 2 2  m Y1  2  2 2  2 1  2k Y t1, t 2  Y Y виконують оптимальну екстраполяцію та обчис* люють по команді БУС-4 значення Y3 за формулою непрямих вимірювань: min  m2 Y  3  2  Y 3   opt m Y1 m Y3  k Y t1, t 3       2   1   opt m Y2 m Y3  k Y t 2 , t 3            opt m Y1  1   opt m Y2   2     2  opt 2  2 opt 1   opt k Y t1, t 2   1   opt Y 1 h1 за формулою непрямих вимірювань: DY3  h1  , D opt  ; min 2 2 Y  раполяції ; h2 за формулою непрямих вимірювань: DY3  , h2  * D Y3   (13) 2 де DY3  - дисперсія значення випадкового сигналу, що буде спостерігатися у момент часу t3, D opt - мінімальна дисперсія похибки екстmin  60390  D  opt (11) * по команді БУС-5 значення Y3 запам'ятовують в обчислювачі (блок 5); далі за командою БУС-6 обчислюють (блок 5) Dε(αopt)min за формулою непрямих вимірювань: U * Y3  Y2  opt Y1  Y2  ; UA  , 2, , m y1 , m y 2 , m y 3 ,  y12,  y 22,  y 32 , де  - ін ми моніторингу та вимірювань трафіку (блок 2) подають значення моментів часу t1, t2, у які спостерігають і вимірюють попередні значення Y1, Y2 - огинаючої трафіку, а на вхід обчислювача (блок 5) по команді БУС-3 подають момент часу t3, для якого в ньому обчислюють αopt за формулою непрямих вимірювань:  opt  (19) (21) u201006549 (22) 28.05.2010 (24) 25.06.2011 (46) 25.06.2011, Бюл.№ 12, 2011 р. (72) ГУЗІЙ МИКОЛА МИКОЛАЙОВИЧ, АНДРЕЄВ ОЛЕКСАНДР ВОЛОДИМИРОВИЧ, ІГНАТОВ ВОЛОДИМИР ОЛЕКСІЙОВИЧ, АНДРЄЄВ ВОЛОДИМИР ІЛЛІЧ (73) НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ (57) Оптимальний екстраполятор нестаціонарного трафіку комп'ютерних мереж, який містить систему моніторингу трафіку та блок вимірювання трафіку, який відрізняється тим, що з метою підвищення точності та ефективності оптимальної екстраполяції для оптимальної екстраполяції нестаціонарного трафіку комп'ютерних мереж використовують декілька попередніх вимірювань огинаючої зашумленого сигналу нестаціонарного трафіку з апріорно відомими ймовірнісними характеристиками (математичні очікування, дисперсії, кореляційні функції сигналу та завади), в основу побудови оптимального екстраполятора кладуть визначення оптимального прогнозного (екстрапольованого) значення випадкового нестаціонарного трафіку на тлі завад за критерієм мінімуму дисперсії похибки; оптимальний екстраполятор має базу даних, таймер, блок управління і синхронізації, обчислювач, блок індикації; цикл вимірювань починають з того, що з першого виходу бази даних (блок 1) по команді блок управління синхронізацієї (БУС-1) на вхід обчислювача (блок 5) подають апріорно відомі параметри нестаціонарного трафіку: 2 3 * де DY3  дисперсія оцінки Y3 ; h3 за формулою непрямих вимірювань: h3    * DY3   D Y3 ; D opt  min min за формулою непрямих вимірювань: Цифровий оптимальний екстраполятор відноситься до теорії випадкових процесів та використання цієї теорії для розв'язання прикладних задач надійності, діагностування, контролю якості, обробки сигналів на тлі завад, контролю працездатності та прогнозуванні трафіку обчислювальних мереж, при макропрогнозуванні трендів в економіці при малих обсягах вибірок в часових рядах. Аналогом запропонованого пристрою є винахід, який відноситься до апаратних засобів управління декількома випадковими нестаціонарними процесами за допомогою адаптивної оцінки і збору інформації [1]. Більш конкретно, цей винахід стосується адаптивного пристрою контролю, в якому моніторинг минулих станів процесів використовується для екстраполяції поточного стану кожного процесу, що контролюється, а також для оцінки факторів невизначеності в кожному процесі. Недоліком є те, що не враховується дія завади. Аналогом запропонованого пристрою є також пристрій покращення зображення нелінійною екстраполяцією в частотному просторі [2]. У ньому вхідне зображення збільшується для того, щоб включити просторові частотні вузли, які мають частоти вищі ніж ті, що входять у вхідне зображення. Карта перетинів будується на основі вхідного зображення з використанням високоякісної прохідної фільтрувальної техніки. Збільшена карта створюється за допомогою використання нелінійного оператора до карти перетинів із збереженням фазових переходів перетинів вхідного зображення. Збільшена карта додається до вхідного зображення, щоб отримати результуюче зображення, яке має просторові частоти, більші ніж у вхідному зображенні. Простота обчислень і легкість реалізації дозволяють отримати покращене зображення в реальному часі для таких додатків як відеофони, покращення телевізійного зображення, реставрація старих фільмів. Недоліком пристрою є те, що в описі патенту не показано, як працює запропонований пристрій при впливі на зображення випадкової завади. Крім того, цей пристрій вимагає відносно великих обсягів спостережень для отримання спектру. Прототипом цифрового оптимального екстраполятора є винахід поліноміального екстраполятора нестаціонарного трафіку комп'ютерних мереж для прогнозування інтенсивностей інформаційних потоків в комп'ютерних мережах [3], що містить блок спостереження інтенсивностей та блок обчислення їх екстрапольованих значень. Екстраполятор має блок числового інтегрування рівнянь настройки для коефіцієнтів апроксимуючого 60390 4 min   D  opt * Y3 min , після закінчення обчислень за командою БУС-7 з виходу обчислювача (блок 5) передають інформацію на вхід блока індикації (блок 6) та на вхід бази даних (блок 1). полінома, праві частини яких формуються блоком спостережень інтенсивностей потоків за допомогою блока формування функції середньоквадратичного відхилення та блока обчислення її градієнта по коефіцієнтах полінома. Недоліком патенту є те, що не показано, як працює запропонований пристрій при впливі на мережу випадкової завади. Крім того, цей пристрій не виконує оптимальну екстраполяцію. Конкретизація постановки задачі оптимальної екстраполяції випадкового нестаціонарного трафіку (ВНТ) на тлі завади виконана наступним чином. Вводять такі основні позначення: X(t) - випадковий нестаціонарний сигнал, значення якого прогнозуються; ξ(t) - випадкова завада, що спотворює дані спостережень; Y(t) - випадковий сигнал, реалізація якого спостерігається, ti, і=1, n - і-й момент спостереження, Y(ti)=Yi - і-e значення Y(t) в момент часу спостереження ti, Yn+1-Y(tn+1) - значення Y(t), що прогнозується (екстраполюється), Т=tn-t1 - інтервал спостереження,  =tn+1-tn - інтервал екстраполяції (прогнозу), M[Y(t)]=m(t) - математичне сподівання Y(t), 2 D[Y(t)]=M[Y(t)-m(t)] - дисперсія Y(t), k(ti, tj)=M{[Y(ti)-m(ti) ][Y(tj) - m(tj)]} - кореляційна функція Y(t), kξ(ti, tj)=M{[ξ(ti)-mξ][ξ(tj)-mξ]} - кореляційна функція завади ξ(t), M[ξ(t)]=mξ(t) - математичне сподівання завади ξ(t). На Фіг.1 показані всі основні характеристики і параметри екстраполяції ВНТ. Неважко помітити різницю Хn+1 від Yn+1, та вплив завади ξ(t) на характеристики Yn+1. Для спрощення на Фіг.1 показано два спостереження (n=2), в результаті спостереження отримують значення Y1, Y2 замість істинних значень X1, Х2, по яким необхідно визначити Х3, але насправді оптимально спрогнозувати значення Y3. Задача екстраполяції полягає в тому, щоб у найкращий спосіб по значенням Y1, Y2 що спосте* рігають, отримати оцінку Y3 майбутнього значення Y3. З постановки задачі зрозуміло, що найкраща екстраполяція включає не тільки прогнозування Y3, * а й зменшення похибки спостережень   Y3  X3 . Для коректної постановки задачі введено такі припущення: 5 60390 1. Сигнал, що спостерігають, розглядається як «адитивна суміш» огинаючої трафіку X(t) і завади ξ(t) [5] Y(t)=X(t)+ξ(t) (1). * 2. Оцінку Y3 істинного значення Х3 в момент часу t3 розглядають як лінійну комбінацію (функцію) попередніх значень, що спостерігають * (2). Y3  1Y1  2 Y2 3. Вважають, що параметри α1, α2 задовольняють вимозі нормування α1+α2=1 (3), тоді α1=α, α2=1-α, а оцінка * Y3  Y2  Y1  Y2  (4). * Y3 Оцінка по формулі (4) має наглядне фізичне пояснення: Y2 - опорне значення, α(Y1-Y2) «добавка», яка є добутком різниці ∆Y12=Y1-Y2 значень трафіку на інтервалі спостереження та параметру екстраполяції α. 4. Припускають, що завада ξ(t) являє собою випадковий стаціонарний гаусовський сигнал з характеристиками M[ξ(t)]=mξ=0, M[ξ(t1), ξ(t2)]=kξ(∆t), (5), де kξ(∆t) - кореляційна функція завади, що визначають за формулою k  t   2r t   де 2  (6), дисперсія (потужність) завади  Dt , r t  - нормована кореляційна функція 6 льного вибору параметру оптимізації а по відповідному критерію оптимізації. * Таким чином, для оптимізації оцінки Y3 необхідно вибрати критерій оптимізації та використати α як керовану змінну оптимізації. Найбільш розповсюдженим, що відповідає змісту цієї задачі є метод максимальної правдоподібності [5], який при обраних вхідних даних приводить до використання середньоквадратичного критерію методу найменших квадратів у вигляді * квадрату відстані між Y3 та Y3 в евклідовому просторі:  * 2 D   M Y3  Y3  (13).   За змістом критерій (13) є дисперсію похибки екстраполяції ε: D    MY3  Y2  Y1  Y2 2 (14). Для розв'язання задачі оптимізації використовують класичний метод знаходження мінімуму функції однієї змінної. Беруть похідну від Dε по α, та прирівнюють її нулю, враховують те, що друга похідна більша нуля, вирішують отримане рівняння відносно α, отримують: MY2 Y2  Y1  MY3 Y2  Y1 opt  (15). M Y2  Y12 При обчисленні математичних очікувань в формулі (15) враховують наступні співвідношення для характеристик випадкових процесів:   DXt   2 0 2  1 t      t  2       (9), (10), k x ti, t j  M Xti   mti  X t j  m t j  2  1 (11), t it j де через ti, tj позначені і-ий та j-ий моменти спостережень, 7. Враховують те, що ВНТ та завада є незалежними сигналами, тоді M Xti   mti   t j  m  0 (12).     Якщо характеристики ВНТ (9-11) та завади (6) відомі, припущення (1)-(7) виконують, коректно ставлять задачу оптимізації оцінки (4) значення X(t) в наступний момент часу tn+1 шляхом оптима  (16),  i2ti2  2 0  2  (17),   (18), M Yi2  mi2 (19),   i 0 MXt   m0  m1 t  mt  2 i Y M Yi  Yj  rij  mim j  k Y ti, t j (7), i де q=1 детерміновані параметри завдання нелінійності і нестаціонарності трафіку γ0, γ1 задовольняють умовам: 0≤γ0≤1, 0≤γ1≤2, а коефіцієнти a0, a1 являють собою випадкові незалежні величини, що мають гаусовські розподіли з такими, математичними сподіваннями і дисперсіями відповідно: 2 2 Ma0   m0; Da0   0; Ma1  m1; Da1  1 (8). 6. Для визначеності припускають, що γ0=0, а γ1=γ=1/2, тоді числові характеристики ВНТ приймають такий конкретний вигляд : 2 0 DYti   q  it   MYi   m0  m1ti завади, інтервал часу ∆t=t2-t1. 5. Припускають, що математична модель X(t) має вигляд: Xt       2 Y 2 2 i  0  i2ti2   2 Y    k Y ti, t j  2 0 2  1 (20),  tit j  2r ti   tj  (21). З урахуванням (16-21) в кінцевому результаті для αopt отримують: opt   mY 2   mY  mY 2  2 Y  m Y1 m Y2  m Y3  2 2  k Y t1, t 2   k Y t 2, t 3  Y 2 1 2  2 1  2k Y t1, t 2  Y (22). При оптимальному значенні параметра екстраполяції αopt дисперсія похибки екстраполяції приймає мінімальне значення, яке визначають за наступною формулою непрямих вимірювань:  D   opt min  m 2 Y   2  Y 3 3   opt m Y1 m Y3  k Y t 1, t 3       2   1   opt m Y2 m Y3  k Y t 2 , t 3             opt m Y1  1   opt m Y2  2   (23),  2   opt  2  2 opt 1   opt k Y t 1, t 2   Y  1  1   opt 2  2 Y 2 На Фіг.2 показана залежність Dε(α) для одного з експериментів. Оптимальне рішення існує не при 7 60390 всіх початкових даних, тому треба уважно підходити до їх визначення. Структура формули (23) стає вельми наглядною, якщо її представити у вигляді:  *2  2 * D opt  M Y3  2M Y3 Y3  M Y3  (24). min         * Якщо кореляція Y3 та Y3 є повною, тоді Dε(αopt)min=0, тому що  *2  2 * 2 M Y3  M Y3   2M Y3 Y3  2M Y3 (25).         * Дисперсію оцінки Y3 отримують за формулою непрямих вимірів (4)    * 2 D Y3  opt 2 1  1  opt Y    2opt 1  opt k Y t1, t 2  2 2 Y 2  (26). * Оцінку Y3 отримують у вигляді зваженої суми значень Y1, Y2, що спостерігають, з оптимальними ваговими коефіцієнтами αopt та (1 - αopt), тому дисперсія оптимальної оцінки   * (27). D Y3  DY3  Нерівність (27) показує, що оптимальна екстраполяція дає меншу дисперсію оптимальної оцінки, ніж дисперсія очікуваного значення, що спостерігають. Цей висновок дуже важливий для практичних застосувань. З нього випливає, що оптимальна екстраполяція, якщо вона можлива, є корисною тому, що суттєво підвищує точність оцінювання значень ВНТ. Ефективність оптимального способу екстраполяції оцінюють за наступними формулами непрямих вимірювань системи оцінювання ефективності екстраполяції. Відношення сигнал/шум на виході оптимального екстраполятора: DY3  h1  (28), D opt  min де D[Y3] - дисперсія випадкового сигналу, яку спостерігають у момент часу t3, Dε(αopt)min - мінімальна дисперсія похибки екстраполяції. Відношення дисперсії випадкового сигналу, яку спостерігають у момент часу t3, до дисперсії   * екстрапольованого значення сигналу D Y3 . h2  DY3    (29). * D Y3 Відношення різниці між дисперсією випадкового сигналу, яку спостерігають у момент часу t3, та   * дисперсією екстрапольованого сигналу D Y3 мінімальної дисперсії похибки екстраполяції: h3    * DY3   D Y3 D opt  min до (30). Для оцінки середньої величини похибки екстраполяції використовують абсолютну похибку * m  m3  m3 (31), та відносну похибку оптимальної екстраполяції 8 min   D  opt * Y3 min (32). На Фіг.3 показана узагальнена структурна схема пристрою. Структурна схема містить: блок 1 - база даних; блок 2 - система моніторингу трафіку; блок 3 таймер ; блок 4 - блок управління; блок 5 - обчислювач; блок 6 - блок індикації. Входом схеми є апріорні дані трафіку комп'ютерної мережі, які зберігаються в базі даних БД (блок 1) і система моніторингу трафіку (блок 2), що спостерігає та вимірює трафік каналу передачі інформації. Виходом схеми є обчислювач, який видає значення αopt, Dε(αopt)min, δmin. Цифровий оптимальний екстраполятор працює таким чином. Цифровий цикл вимірювань починається з того, що по команді (блок управління синхронізацією) БУС-1 з бази даних в обчислювач записують апріорно відомі параметри нестаціонарного трафіку:  , 2, , m y1 , m y 2 , m y 3 ,  y12,  y 22,  y 32 , де  - ін тервал кореляції завади;  2 - середнє квадратич не відхилення завади; γ - параметр нелінійності нестаціонарного випадкового трафіку; my1 , my 2 , my 3 - математичні сподівання значень трафіку, що спостерігається, у моменти часу t1, t2, 2 2 2 t3 відповідно;  y1 ,  y 2 ,  y 3 - середні квадратичні відхилення значень Y1, Y2, Y3 у моменти часу t1, t2, t3, відповідно; паралельно з другого виходу бази даних БД (блок 1) по команді БУС-2 на вхід системи моніторингу та вимірювань трафіку (блок 2) подають значення моментів часу t1, t2 - протягом яких відбуваються спостереження значень Y1, Y2 огинаючої трафіку, а на вхід обчислювача (блок 5) по команді БУС-3 подають момент t3, для якого виконують оптимальну екстраполяцію та далі за командою БУС-4 в обчислювачі (блок 5) обчислю* ють αopt за формулою (22) та значення Y3 . При вимірюванні значень Y1, Y2 їх передають і запам'ятовують в пам'яті обчислювача (блок 5). По ко* манді БУС-5 значення Y3 запам'ятовують в обчислювачі (блок 5); за командою БУС-6 обчислюють Dε(αopt)min за формулою (23), h1, h2, h3 (за формулами (28)-(30)) та δmin по формулі (32). Після закінчення обчислень з обчислювача по команді БУС-7 передають інформацію на блок індикації (блок 6) і записують в базу даних (блок 1). На цьому цикл роботи цифрового оптимального екстраполятора закінчують. Приклад 1. В цьому прикладі наведені результати експерименту, що був проведений методом цифрового статистичного імітаційного моделювання оптимального екстраполятора. Виконують * оптимальну екстраполяцію значення Y3 по двом попереднім значенням Y1, Y2. Результати вимірювання Х1, Х2, Х3, Y1, Y2, Y3 моделюють реалізаціями випадкових величин за допомогою функції (33) системи MathCAD Yi=rnorm{n,M[Y],ζ}, (33), 9 60390 i=1,3 де число n реалізацій для кожної точки вибрано n=1, M[Yi] - математичне очікування трафіку, ζ середньоквадратичне відхилення трафіку, що спостерігається, яке обчислюють за формулою (17). Для моделювання роботи структурної схеми пристрою оптимального екстраполятора була розроблена програма на мові системи MathCAD. Вона використовує різні вхідні дані експериментів і виконує статистичні експерименти. В експерименті були обрані наступні початкові дані: t1=6c; t2=10с; t3=12c, де t1, t2 - моменти часу, в які спостерігаються реалізації Y1, Y2 нестаціонарного випадкового трафіку, t3 - момент часу, для якого виконують екстраполяцію, 10 ∆ηξ=0,5с - інтервал кореляції завади, ζξ=0,01B, m0=1B, m1=0,1В/с, ζ0=0,1В, ζ1=0,01В. Реалізації Yi утворюють за допомогою функції генерації випадкових чисел (33) з гаусовським розподілом при заданих n, M[Yi], ζ. В експерименті задають точність моделювання «шість знаків після коми». Наприклад, в результаті однократного використання операції (33) отримані такі реалізації вимірювань: Y1=1,030483, Y2=1,029272, Y3=1,016351. В таблиці показано результати експерименту, а на Фіг.4 відображені графіки X(t), Y(t) та Z(t), де * Z(t) відображає Y3 на графіку. На Фіг.2 відображений графік Dε(α)=f(α) для різних значень α. Таблиця Результати експерименту X1 1,015018 X2 1,024681 X3 1,028772 Y1 1,030483 Y2 1,029272 Y3 1,016351 * Y3 αopt D[Y3] * D Y3 Dε(αopt)min h1 1,028786 h2 0,994706 Dε(α)2 0,000121 -0,401238 ξ1 0,015465 α2 -0,4 0,0113 ξ2 0,004591 Dε(α)3 0,000837 0,01136 ξ3 -0,01242 α3 -0,8 0,0002 Dε(α)1 0,001047 Dε(α)4 0,001811 56,49051 α1 0 α4 -1 Аналіз результатів експерименту показує працездатність і високу ефективність способу за Фіг.3 навіть при низькому відношенню середньоквадратичних значень сигнал/шум: приблизно 3-4. За результатами експерименту зроблені такі висновки: 1. Показник ефективності оптимальної екстраполяції h1 показує, що оптимальна екстраполяція забезпечує достатньо високу точність - дисперсія похибки (шумів) екстраполяції в 56 разів менше дисперсії самого нестаціонарного трафіку. 2. В результаті оптимальної екстраполяції значення Y3 для моменту часу t3=12с знаходиться ближче до Х3 ніж Y3 (дивись графік Фіг.4); диспер   * сія D Y3 оптимально екстрапольованого значення приблизно у h2 = 0,99 разів більше, ніж дисперсія D[Y3] значення сигналу, що буде спостерігатися в t3 . 3. Показник ефективності оптимальної екстраполяції h3 показує, що оптимальна екстраполяція забезпечує різницю між дисперсією D[Y3] і диспер   * сією оптимальної оцінки D Y3 вдвічі меншу дисперсії Dε(αopt)min похибки екстраполяція. 4. Графік Фіг.2 показує, що дисперсія Dε(αopt) має мінімум при значенні αopt.   Тому, якщо є можливість отримати необхідні вихідні дані, завжди корисно проводити оптимальну екстраполяцію. Наведені результати експерименту наглядно ілюструють новизну, корисність та високу ефективність пристрою, що пропонуються. Список використаних джерел: 1. United States Patent №4,635,182. Kenneth J. Hintz. Apparatus for controlling multiple time-varying processes. Jan. 6, 1987. 2. United States Patent №5,717,789. Image enhancement by non-linear extrapolation in frequency space. Inventors: Charles H. Anderson, Hayik R. Greenspan, California. Institute bjf Technology. Pasadena. Feb. 10, 1998. 3. Патент України № 31664. Поліноміальний екстраполятор для прогнозування інтенсивностей інформаційних потоків в комп'ютерних мережах. Винахідники: Жуков І.А., Антонов В.К., Дрововозов В.І., Аль-Сурікі Ібрагім. Київ, Національний авіаційний університет. Квітень. 25.2008р, Бюл. №8. 4. Дьяконов В.П. Энциклопедия MathCAD 2001 и MathCAD 11. М.: Изд. Солон-пресс. - 2004. 832с. 5. Игнатов В.А. Теория информации и передачи сигналов. Учебник для вузов. 2-ое изд. Перераб. и доп. М: Радио и связь. 1990. - 280с. 11 Комп’ютерна верстка Н. Лиcенко 60390 Підписне 12 Тираж 24 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601