Бацамут Володимир Миколайович

УДК 519.711:044.722

МОДЕЛІ І МЕТОДИ АВТОМАТИЗОВАНОГО УПРАВЛІННЯ

НАВАНТАЖЕННЯМ В МЕРЕЖНИХ СИСТЕМАХ ПЕРЕДАЧІ ДАНИХ

05.13.06 – автоматизовані системи управління

та прогресивні інформаційні технології

Автореферат

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

кандидата технічних наук

Харків – 2005

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

Робота виконана на кафедрі інформаційних систем і технологій в діяльності ОВС Національного університету внутрішніх справ, Міністерство внутрішніх справ України.

Науковий керівник: заслужений діяч науки і техніки України, доктор фізико-математичних наук, професор Яковлев Сергій Всеволодович, Національний університет внутрішніх справ, м. Харків, професор кафедри прикладної математики.

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

- доктор технічних наук, професор Левикін Віктор Макарович, Харківський національний університет радіоелектроніки, м. Харків, завідувач кафедри інформаційних управляючих систем;

- кандидат технічних наук Шостак Ігор Володимирович, Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, м. Харків, доцент кафедри програмного забезпечення комп’ютерних систем.

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

Херсонський національний технічний університет, кафедра інформаційних технологій, м. Херсон.

Захист відбудеться “22” червня 2005 р. о 15 00 годині на засіданні спеціалізованої вченої ради Д 64.052.01 Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14, тел: (057) 70-21-451.

З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, просп. Леніна, 14.

Автореферат розісланий “20” травня 2005 р.

Вчений секретар

спеціалізованої вченої ради С.Ф.Чалий

Загальна ХАРАКТЕРИСТИКА роботи

Актуальність теми. Елементом високоефективної діяльності органів внутрішніх справ (ОВС) України є АСУ Міністерства внутрішніх справ (МВС) організаційного типу, в основі якої лежить розподілена по всій території держави мережа передачі даних з комутацією пакетів (ПД-КП). Зібрані в єдину систему засоби автоматизації дозволяють виконувати вимоги щодо управління ОВС в умовах обмеженого часу на прийняття рішення і швидкої зміни обстановки.

Проведений аналіз мережі ПД МВС України показує, що зростання темпів й обсягів документообігу останнім часом викликає додаткове навантаження на мережу. Усе це впливає на ефективність застосування мережі за призначенням, рівень якої вже не повною мірою відповідає вимогам, особливо в години найбільшого навантаження (ГНН). Отже, у зв’язку з тим, що потоки й обсяги інформації мають випадковий характер, а пропускна здатність мережної системи обмежена, виникає задача ефективного управління її вхідним навантаженням.

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

Процеси, що відбуваються в мережі ПД під час функціонування, впливають на таку важливу її характеристику, як топологія. Через таку свою властивість, як зв’язність, топологія впливає на інформаційні процеси, що відбуваються в системі, тобто на якість обслуговування користувачів. Отже, виявляється взаємозалежність між поточною топологією (зв’язністю) мережної системи передачі даних та ефективністю її функціонування – здатністю обслужити навантаження, що надходить від абонентів. Таким чином, через постійні зміни топології системи під час її функціонування виникає необхідність у постійному контролі зв’язності її вузлових елементів, що надає можливість управляти вхідним навантаженням. Виходячи з зазначених недоліків відомих методів управління навантаженням і залежності якості обслуговування від поточної топології системи, стає актуальною задача розробки методу управління вхідним навантаженням мережних систем передачі даних на основі проведення контролю їх поточної топології.

Проблеми структурного аналізу, синтезу й оптимізації різного роду територіально-розподілених систем розглядалися й вирішувалися у працях Л.Клейнрока, В.М.Глушкова, Е.А.Якубайтіса, М.Шварца, В.Л.Волковича, О.М.Павлова, С.П.Присяжнюка, М.Д.Годлевського, О.А.Молчанова, Ю.Г.Стояна, Е.Г.Петрова, В.Є.Ходакова, В.П.Авраменка, В.М.Левикіна, А.Д.Тевяшева, С.В.Яковлева.

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

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

Зв’язок роботи з науковими програмами, планами, темами. Напрямок досліджень відповідає перспективним планам розвитку інфраструктури мережі ПД АСУ МВС України.

Дисертаційна робота виконана на факультеті управління та інформатики Національного університету внутрішніх справ (м. Харків) та у Військовому інституті ВВ МВС України (м. Харків) відповідно до планів НДР цих вузів, а також у рамках НДР “Аура”, розпочатої згідно з рішенням Головного управління ВВ МВС України, затвердженого Першим заступником командувача ВВ МВС України – начальником штабу, вих. № 3/8-2 від 02.01.2001 р.

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

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

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

- розробка математичної моделі та методу автоматизованого управління вхідним навантаженням мережі ПД на основі проведення контролю її поточної топології;

- розробка математичної моделі та методу оптимального відновлення мережної зв’язності зруйнованої (ушкодженої) інфраструктури мережі ПД;

- оцінка оперативності доставки інформації у мережі ПД з елементами контролю її поточної топології, розробка та обґрунтування рекомендацій щодо вдосконалення мережі ПД АСУ МВС України;

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

Об’єкт дослідження – мережні системи передачі даних.

Предмет дослідження – моделі і методи автоматизованого управління вхідним навантаженням у мережних системах передачі даних та оптимального відновлення мережної зв’язності в умовах її руйнування.

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

Наукова новизна одержаних результатів.

1. Вперше розроблені математична модель і метод автоматизованого управління вхідним навантаженням мережі ПД на основі проведення контролю зв’язності її поточної топології, який здійснюється шляхом визначення транзитивного замкнення (ТЗ) мережі, та дозволяють збалансувати рівень пропускної здатності мережі з рівнем вхідного трафіка.

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

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

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

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

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

- за рахунок встановлення відповідності рівня вхідного трафіка рівню пропускної здатності мережі ПД протидіяти переходу системи у стан перевантаження (блокування);

- за рахунок меншої обчислювальної складності алгоритму розрахунку транзитивного замкнення організувати контроль поточної топології в режимі реального часу на мережах ПД-КП-В з кількістю центрів комутації при заданому середньому часі встановлення логічного (віртуального) з’єднання Ткр=0,01 с;

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

Результати дослідження використані:

- під час розробки спеціального програмного забезпечення вирішення задачі оперативного моніторингу і відновлення мережної зв’язності деградованої мережі, що проводилася службою АСУ ГУВВ МВС України (акт про впровадження вих. № 3/8-268 від 03.01.2002 р.);

- у розробках АТ “Науково-дослідний інститут радіотехнічних вимірювань” за темами ДКР “Хвиля” та “Сейсмологія” (акт про впровадження від 28.08.2001 р.);

- у навчальному процесі ХВУ при проведенні лекцій та практичних занять на кафедрі № 1 (акт про впровадження від 15.06.2001 р., протокол засідання кафедри № 30 від 25.05.2001 р.).

Особистий внесок здобувача. Основні результати дисертаційної роботи отримані автором самостійно. Особистий внесок дисертанта щодо робіт, написаних у співавторстві, складає: у роботі [1] – розроблено матричний алгоритм знаходження зв’язків між сильними компонентами в орієнтованій структурі; [2] – здобувачем розроблено метод визначення кількості та індексного складу компонент зв’язності довільних неорієнтованих графів; [3] – розроблено методику визначення кількості та індексного складу компонент зв’язності на орієнтованих структурах; [4] – розроблено правило формування додаткової підмножини вершин зв’язного графа, з урахуванням якої здійснюється оптимальне відновлення мережної зв’язності між попередньо вибраною підмножиною.

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

- “Математичне та програмне забезпечення АСУ” (м. Харків, ХВУ, 10.11.1999 р.);

- “Актуальні проблеми будівництва та розвитку внутрішніх військ МВС України” (м. Харків, Військовий інститут внутрішніх військ МВС України, 28.04.2001 р.);

- 10 Ювілейній міжнародній конференції “Теорія і техніка передачі, прийому і обробки інформації” (м. Харків-Туапсе, 28.09.2004 р. – 01.10.2004 р.).

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

Структура та обсяг дисертації. Дисертаційна робота має у своєму складі: вступ, чотири розділи, висновки, список використаних джерел зі 115 найменувань, три додатки, 44 рисунки, 13 таблиць. Загальний обсяг роботи становить 180 сторінок, у тому числі 148 сторінок основного тексту.

Основний зміст роботи

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

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

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

Згідно з отриманими під час аналізу результатами автором сформульовано основні задачі дослідження.

Другий розділ присвячено дослідженню мережі ПД АСУ МВС України, моделюванню її інфраструктури, формалізованій постановці завдання дослідження, а також розробці відповідних моделей і методів автоматизованого управління навантаженням мережних систем ПД.

У розділі наведені результати дослідження процесу автоматизованої передачі інформації у мережі ПД АСУ МВС України. Розкриваються функціональна, топологічна структура та технологія дії мережі. Визначено, що у мережі ПД МВС України, яка є мережею ПД з комутацією пакетів у віртуальному режимі (ПД-КП-В), абоненти не володіють інформацією про поточну зв’язність мережі, у результаті чого на її входи продовжує надходити потік повідомлень, який на даний час фізично не може бути переданим, тобто загублений потік. Таким чином, завдяки обробці всіх замовлень, що надходять, відбувається неефективне використання лінійного і комутаційного обладнання. Навантаження на мережу, а отже, і затримки в ній, зростають.

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

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

Математична модель інфраструктури мережі ПД описується зв’язним неорієнтованим графом G=(V,E). Множина вершин подається у вигляді , де – множина, що описує ЦК мережі; – множина, що описує абонентські пункти мережі; – множина натуральних цілих чисел; – індекси вершин із множини ; – множина натуральних цілих чисел; – індекси вершин з множини суміжних даній вершині ; , , де n – загальна кількість вершин графа G.

Множина ребер подається , де – ребро, що моделює пучок каналів між вершинами типу , а – ребро, що моделює лінію прив’язки у напрямку від вершини типу до вершини типу . Кожна вершина характеризується своєю інтенсивністю обслуговування , тобто множиною переданих через неї і відмовлених нею за деякий час повідомлень і відповідно та об’ємом буферної пам’яті .

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

Тоді вхідне навантаження на будь-який центр комутації становитиме

. (1)

Ребра характеризуються пропускною здатністю Cij (індекси вказують напрям передачі). В умовах відсутності черг на кожній та при фіксованому об’ємі повідомлень час передачі кожного з них по встановленому віртуальному каналу становитиме .

Під час функціонування мережі ПД її топологія змінюється у часі. Тому кількість можливих станів структури G=(V, E) описується множиною різних топологій G={g}, g={gV, gЕ, gП}, де gV – набір недовантажених вершин, gE – набір недовантажених ребер, gП – топології можливих напрямів для передачі інформації. Виходячи з цього кожному топологічному стану структури відповідає свій набір властивостей системи, які характеризують її здатність виконувати необхідні функції, тобто , де – деяке відображення.

Якість обслуговування у мережі характеризувалася двома показниками:– середній час доставки повідомлення адресату та Q – ймовірність своєчасної доставки повідомлення адресату. У загальному вигляді можна записати такі моделі

(2), (3)

де – загальне навантаження на мережу; – інтенсивність обслуговування в мережі; g – поточна топологія структури мережі ПД; – коефіцієнт готовності системи; – об’єм повідомлення; C – пропускна здатність каналу зв’язку; – інтенсивність старіння інформації; – технологія дії мережі (мережі ПД з комутацією каналів, комутацією пакетів у дейтаграмному або віртуальному режимі тощо).

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

, .

Тоді для фіксованої пари вершин (абонентів) k та l час доставки повідомлення запишеться у вигляді

,

де Tкк – час комутації (встановлення віртуального каналу); – змінні, що характеризують наявність відповідного ребра у шляху між k -ю та l -ю вершинами в умовах поточної топології g.

На пропускну здатність мережі накладалися такі обмеження

, ,

,

,

, (4)

де будь-які, Т – транзитивне відношення зв’язності.

З метою виконання мережею ПД своїх функцій обмеження (4) має виконуватися для всіх можливих пар , тобто .

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

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

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

.

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

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

Поточний топологічний стан g інфраструктури мережі описується модифікованою матрицею суміжності , де

Контроль поточної топології g полягає у визначенні з деякою дискретизацією у часі матриці . Тому даний процес запишеться у вигляді , де m – множина циклів контролю, з наступним розрахунком матриць відповідно, де їх входження визначаються умовою

(5)

та інформують про наявність ТЗ між відповідними вузловими елементами (про можливість встановлення між ЦК віртуального з’єднання – шляху передачі даних) у топологічних умовах g на момент часу t.

Відповідно до виразу (5) модель управління вхідним навантаженням (процес реорганізації черг) для будь-якої вершини на кожному циклі управління запишеться у вигляді

,

, (6)

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

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

. (7)

При такому управлінні інтервали часу між замовленнями, для яких виконується умова (6), будуть наближатися до нескінченності (тобто ), а відповідна їм інтенсивність – до нуля (тобто ).

Тому вираз (7), що характеризує загальне навантаження на будь-яку вершину при граничних умовах, матиме такий вигляд

.

Далі відповідно до загальної структури мережі пропонується ієрархічна структура системи управління навантаженням (рис. 1). Для цього використано схему “менеджер-агент”. Вважається, що система управління (СУ) працює в автоматизованому режимі, виконуючи рутинні функції з управління мережею автоматично, а складні рішення надаючи приймати адміністратору мережі – аналітику.

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

Етап І. Прийняття аналітиком мережі рішення про необхідність обмеження вхідного навантаження

Етап ІІ. Якщо “так”, то на кожній розпочати процес визначення величин sij(tm) відповідно до виразу

і формування відповідних матриць .

Етап ІІІ. Розрахувати на кожній за отриманими матрицями матриці ТЗ мережі (визначити можливості встановлення логічного з’єднання між будь-якою парою при даних топологічних умовах g, що склалися на момент часу tm).

Етап ІV. Реорганізувати на кожній розташування повідомлень {pij} у вихідних чергах згідно з розрахованою матрицею ТЗ – за правилом

Зупинка роботи методу відбувається за рішенням аналітика мережі за умови сталого . В іншому випадку перейти до етапу ІІ.

Далі дисертантом розглядається модель оптимального відновлення мережної зв’язності на підмножині вершин вузлової основи моделюючого графа зруйнованої мережі ПД.

При відновленні зв’язності у зруйнованій мережі необхідно вирішити протиріччя між вимогами економічності процесу відновлення й ефективністю одержуваної в результаті топології мережі. Математично така задача розглядалася як задача побудови дерева найкоротших шляхів з коренем у деякій вершині або мінімального покриваючого дерева з обов’язковим урахуванням справних ліній зв’язку. Для розв’язання першої задачі є ефективний метод Дейкстри, а для розв’язання другої – методи Пріма, Краскала, Соліна та ін.

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

Задано неорієнтований граф G=(V,E), де – множина вершин графа, що моделює ЦК та абонентські пункти мережі; E={eij} – множина ребер графа, що моделює лінії зв’язку мережі, i та j – індекси вершини графа, , n – кількість вершин графа. Кожному ребру у відповідність поставлений ваговий коефіцієнт , який кількісно характеризує витрати на відновлення ребра (каналу зв’язку) між вершинами та . На моделюючому графі треба знайти підграф , де з дотриманням таких умов

, ,

, .

Модель оптимального відновлення зв’язності на заданій підмножині вершин графа запишеться у вигляді функціонала

, (8)

при обмеженнях

, (9)

, (10)

, (11)

. (12)

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

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

Першому етапу відповідає алгоритм А1:

, (13)

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

якщо , , , ,

де n – розмір моделюючого графа, m – номер обходу поточного масиву, T – транзитивне відношення зв’язності. Такі матричні перетворення автором названі L процедурою.

При першому вкладенні рядків (m=1) обчислюється проміжна матриця , на другому обході (m=2) отримується шукана матриця досяжності або масив ТЗ мережного об’єкта.

Теоретично вперше доведено, що ==…=, тобто працюючи за L процедурою, алгоритм обчислює ТЗ мережного об’єкта за два обходи поточного масиву (), що зменшує загальний час рахунку.

Фізичний сенс алгоритму полягає у його здатності за два обходи поточного масиву визначати наявність чи відсутність шляхів усіх рангів між усіма можливими парами вершин початкового графа. Його час рахунку оцінено як O(N3).

Другому етапу відповідає метод, заснований на побудові блочно-діагональної матриці з масиву ТЗ RG (13), а саме

,

де QG – масив зворотних досяжностей; – масив взаємних досяжностей; – блочно-діагональний масив; Gk – одиничний блок у складі або окрема підмережа у складі загальної мережі; k – кількість підмереж.

Кількість одиничних блоків у масиві вказує на кількість компонент зв’язності (КЗ), а номери вершин, що входять до складу кожного блоку, – на кількісний і якісний (індексний) склад кожної КЗ. Таким чином, визначається кількість можливих підмереж і вузловий склад кожної з них у структурі зруйнованої мережі ПД. Метод реалізований у вигляді окремого алгоритму А2.

Третьому етапу відповідає метод, що вирішує задачу оптимізації (8) при обмеженнях (9–12). Ребра, для яких xij=1 , будуть складати план оптимального відновлення мережної зв’язності зруйнованої мережі ПД.

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

Крок 1. За матрицею ваги початкового графа G, яка описує витрати на відновлення зв’язності до базового рівня топології, методом Флойда обчислити масив найкоротших шляхів RG (найменших ТЗ між всіма парами вузлових елементів графа G). З метою відрізнити значущий нуль (, лінія справна – ) від незначущого нуля (, лінія не існує – ) використовувати А-символіку, де A=const, .

Крок 2. За масивом RG для кожної вершини переглянути всі можливі набори по три вершини . Результат операції: індекси стовпців (вершин ) idx1, idx2, idx3; загальна сума значень найкоротших шляхів (ТЗ), що з’єднують дані три вершини з вибраною – .

Крок 3. Для кожної вершини по індексам, отриманим на кроці №2, обчислити відповідну суму .

Крок 4. Вершини , для яких виконується нерівність

, (14)

додати до складу початкової підмножини вибраних вершин K.

Вершини , для яких нерівність (14) не виконується, вилучити разом зі всіма інцидентними ребрами зі структури початкового G з відповідним корегуванням масиву RG. Якщо всі вершини проаналізовані, – перейти до кроку №5, у протилежному випадку – до кроку №2.

Крок 5. На зміненій таким чином підмножині вершин K згідно із скорегованим масивом RG побудувати повнозв’язну структуру початкового графа G.

Крок 6. На структурі відомим методом Краскала побудувати мінімальне покриваюче дерево. Отримати структуру .

Крок 7. Кожне ребро структури по початковій структурі G ідентифікувати методом Дейкстри. Отримати шукане .

Метод реалізований у вигляді окремого алгоритму А3. Його час рахунку оцінено як O(N3).

У четвертому розділі наведені результати експериментального дослідження оперативності і точності розроблених алгоритмів; якості обслуговування у мережі ПД-КП-В з управлінням вхідним навантаженням на основі проведення контролю її поточної топології, а також викладені рекомендації щодо вдосконалення АСУ МВС України.

Для оцінки ефективності розроблених алгоритмів були вибрані наступні показники.

Для алгоритму А1, що призваний контролювати зв’язність поточної топології:

1. tсер – середній час визначення ТЗ мережного об’єкта в секундах.

2. Кількість елементарних операцій (ЕО).

3. Коефіцієнт виграшу Кв у швидкодії

, (15)

де – кількість ЕО еталонного алгоритму, – кількість ЕО розробленого алгоритму.

4. Своєчасність розв’язання задачі вибраним алгоритмом, яка оцінюється відповідною ймовірністю

, (16)

де tсер – час розв’язання алгоритмом задачі на графі розміру nxn (n – кількість вершин графа, що моделює мережу); Ткр – гранично допустимий час на розв’язання задачі.

Для алгоритму А3, що розраховує план оптимального відновлення зв’язності:

1. Абсолютна і відносна похибки

, (17) , (18)

де P[X]– наближений розв’язок задачі, а P[X*] – точний розв’язок задачі.

Алгоритм А1 порівнювався з відомими алгоритмами Флойда, Уоршалла і Шимбела, що найчастіше використовуються на практиці і мають поліноміальну складність. Розмір моделюючого графа змінювався в діапазоні з кроком 10. На кожному кроці кожним із досліджуваних алгоритмів отримувались екземпляри часу Тi, де . Далі визначався середній час на розв’язання однієї задачі tсер. Вхідні дані формувалися двома способами:

а) щільність ненульових елементів у вхідній матриці постійна – (стаціонарні задачі);

б) щільність ненульових елементів змінювалася шляхом рандомізації в діапазоні {0, n2}, де n – кількість вершин моделюючого графа (динамічні задачі).

Дослідження показало, що розроблений алгоритм А1 на розряджених структурах у середньому на 8–14% володіє меншим tсер, ніж відомі алгоритми, а зі збільшенням розміру і щільності графа ця розбіжність зростає на 25–45%.

Для розрахунку коефіцієнта виграшу Kв за співвідношенням (15) визначалася кількість виконаних кожним алгоритмом ЕО. Виграш алгоритму А1 порівняно з найбільш ефективним алгоритмом Уоршалла на різних розмірах склав .

Для розрахунку показника згідно з виразом (16) як Ткр було вибрано 0,01 с, тобто середній час встановлення віртуального з’єднання. Задовільним вважався такий tсер, при якому виконується умова . Результати наведені у табл. 1.

Таблиця 1

Оцінка ефективності алгоритму А3 проводилася за відносною (17) та абсолютною (18) похибками наданих ним розв’язків відносно наближених розв’язків, що надавались алгоритмом Краскала. Як структура, на якій проводився експеримент, була вибрана структура першого рівня ієрархії мережі ПД АСУ МВС України (магістральна мережа).

Розмір моделюючого графа був прийнятий рівним n=6. Ваговими коефіцієнтами зв’язків вибрано середні часові витрати на відновлення працездатного стану відповідного напрямку, виражені в годинах. Для об’єктивного аналізу розв’язків, що надає алгоритм А3, перебиралися всі можливі підмножини K(V) вершин з множини V={l0,l1,l2,l3,l4,l5} потужності . Таким чином, кількість можливих підмножин вершин . На кожній підмножині вершин будувалися покриваючі дерева алгоритмами Краскала й алгоритмом А3. Абсолютна похибка розв’язків, що надавав алгоритм Краскала, становила , а відносна – .

Експериментальне визначення величин вибраних показників Q та викликане значними труднощами тому, що структура мережі ПД є ієрархічною, а практично всі величини, що входять до складу (2) та (3), випадково змінюються у часі. Тому дослідження було проведено на базі двополюсної мережі з параметрами: C=2400 біт/с, Ткк=0,01 с, =2,02 с, біт.

Результати експерименту для 1000 послідовно переданих повідомлень наведені у табл. 2.

Таблиця 2

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

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

==1–=. (19)

Задовільним вважався такий Tупр у межах якого виконується умова , тобто змін в об’єкті управління з заданою ймовірністю на визначеному інтервалі часу не відбувається. Результати визначення достатньої величини Tупр згідно з (19) при інтенсивності вхідного потоку =0,537 с-1 та інтенсивності обслуговування у мережі с-1 ( – режим перевантаження) наведені у табл. 3.

Таблиця 3

Інтервал Tупр, с | 1,2 | 1,0 | 0,5 | 0,3 | 0,2 | 0,1

Ймовірність | 0,170 | 0,326 | 0,684 | 0,816 | 0,902 | 0,941

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

ВИСНОВКИ

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

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

2. Вперше розроблена математична модель і метод автоматизованого управління вхідним навантаженням мережі ПД на основі проведення контролю зв’язності її поточної топології. В основу методу покладено новий алгоритм визначення транзитивного замкнення мережних об’єктів, що відрізняється від відомих введенням нової рекурсивної процедури подвійного диз’юнктивного вкладення відповідних рядків масиву суміжності моделюючого графа. Це дозволило залежно від розміру тестової задачі скоротити середній час tсер її розв’язання порівняно з відомими підходами. Для розряджених структур ці переваги складають у середньому 8–14 %, а для щільних – 25–45%.

3. Розроблений алгоритм визначення транзитивного замкнення дозволяє з ймовірністю своєчасно приймати рішення щодо необхідності реорганізації вихідної черги повідомлень даного ЦК при розмірі мережі ЦК та середньому часі встановлення віртуального з’єднання – Ткр=0,01 с, і як наслідок ефективно здійснювати управління вхідним навантаженням мережі. Найкращий аналог – алгоритм Уоршалла – з вимогою і при Ткр=0,01 с розв’язує дану задачу тільки на розмірі мережного об’єкта ЦК.

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

5. Розраховано величину циклу управління мережею. Для середніх інтенсивності вхідного потоку =0,537 с-1 та інтенсивності обслуговування с-1, що існують в мережі ПД АСУ МВС України в ГНН, вона дорівнює 0,2 с.

6. Виявлено основні чинники, що приводять до руйнування зв’язності в мережі. Вказано, що вона для мережі ПД в основному залежить від лінійного обладнання (каналів зв’язку). Таким чином, при моделюванні мережі ПД і проведенні дослідження наявність зв’язності ставилася у залежність тільки від стану з’єднувальних ліній.

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

8. Показано, що оптимальною топологією для відновлення зв’язності мережі ПД МВС України (з погляду ефективності передачі інформації) є дерево найкоротших шляхів з коренем у вузлі ГШ МВС України (м. Київ). Для вирішення цієї задачі є метод Дейкстри, який визначає як величини найкоротших шляхів, так і їх топологію. Але мережа, відновлена по топології дерева найкоротших шляхів, не є оптимальною щодо загальних сумарних витрат. Тому у випадках коли головним показником процесу відновлення мережної зв’язності є загальні витрати, запропоновано використовувати мінімальне покриваюче дерево.

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

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

11. Запропоновано, з метою постійного динамічного контролю за цілісністю зв’язності всієї мережі ПД, на базі центру комутації ГШ МВС України (м. Київ) організувати центр управління мережею.

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

1. Кузнецов А.В., Бацамут В.Н. Алгоритм поиска компонент связности в структуре сетевого объекта // Радиоэлектроника и информатика. – Х.: ХНУРЕ. – 2001. – № 3(16). – С. 100-103.

2. Кузнецов А.В., Бацамут В.Н. Построение транзитивно-рефлексивных замыканий бинарно-унарных отношений произвольных неорграфов // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ. – 1999. – Вип. 1(5). – С. 26-30.

3. Бацамут В.Н., Спорышев К.А. Алгоритм структурно-топологического синтеза транзитивно-рефлексивных замыканий на произвольно ориентированных графах // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ. – 2000. – Вип. 2(8). – С. 112-114.

4. Кузнецов О.В., Бацамут В.М. Алгоритм синтезу мінімального покриваючого дерева на довільній групі вершин зв’язного графа // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ. – 2002. – Вип. 1(17). – С. 133-140.

5. Бацамут В.Н. Анализ известных подходов к решению задачи поиска транзитивно-рефлексивных замыканий // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ. – 2000. – Вип. 3(9). – С. 61-68.

6. Бацамут В.Н. Алгоритм вычисления транзитивного замыкания сетевого объекта методом дизъюнктивного вложения строк массива смежности // Системи обробки інформації. – Х.: НАНУ, ПАНМ, ХВУ. – 2001. – Вип. 4(14). – С. 78-83.

7. Бацамут В.М. Метод управління вхідним навантаженням мереж передачі даних для підвищення оперативності доставки інформації // АСУ и приборы автоматики. – Х.: ХНУРЭ. – 2004. – Вып. 128. – С. 67-76.

8. Бацамут В.М. Алгоритм поиска транзитивно-рефлексивных замыканий в неориентированных графах // Тр. науково-технічної конф. “Математичне та програмне забезпечення АСУ”. – Х.: МОУ, ХВУ, 1999. – С. 33.

9. Бацамут В.М. Розробка системи топологічного контролю інфраструктури АСУ військами // Тр. науково-практичної конф. “Актуальні проблеми будівництва та розвитку внутрішніх військ МВС України”. – Х.: ВІ ВВ МВСУ, 2001. – С. 36-37.

10. Бацамут В.М. Об оптимальном восстановлении связности сетевого объекта // Тр. 10-й Юбилейной междунар. научной конф. “Теория и практика передачи, приема и обработки информации”. – Х.: ХНУРЭ, 2004. – Ч. 2. – С. 20-21.

Анотація

Бацамут В.М. Моделі і методи автоматизованого управління навантаженням мережних систем передачі даних. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 “Автоматизовані системи управління та прогресивні інформаційні технології”, Харківський національний університет радіоелектроніки, Харків, 2005 р.

У дисертації досліджено процес передачі інформації у мережі ПД АСУ МВС України, висвітлені основні його недоліки, проаналізовані підходи щодо підвищення ефективності мереж ПД у режимі перевантаження, вирішена актуальна науково-технічна задача розробки моделей і методів автоматизованого управління вхідним навантаженням мережних систем ПД. Управління засновано на періодичному здійсненні контролю поточної топології (зв’язності) системи, для чого використовується поняття транзитивного замкнення (ТЗ) мережного об’єкта. Розроблено новий алгоритм визначення ТЗ, який має поліноміальний час рахунку. На основі оцінки поточного ТЗ здійснюється допуск повідомлень до мережі або постановка в чергу на очікування. Розроблена відповідна математична модель контролю поточної топології й автоматизованого управління вхідним навантаженням мережі. Проведена оцінка якості обслуговування у мережі в якій проводиться управління навантаженням на основі контролю поточної топології.

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

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

Аннотация

Бацамут В.Н. Модели и методы автоматизированного управления нагрузкой в сетевых системах передачи данных. – Рукопись.

Диссертация