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

brief description

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

Лістровий С.В. Оперативне управління телекомунікаційними системами та мережами на основі рангових методів рішення задач булевого програмування та теорії графів Рукопис.
Дисертація на здобуття ученого ступеня доктора технічних наук за фахом 05.12.02-«Телекомунікаційні системи і мережі». Українська державна академія залізничного транспорту, Харків, 2005.
Дисертація присвячена підвищенню оперативності рішення задач управління у телекомунікаційними системами та мережами, моделями яких є оптимізаційні задачі булевого програмування і теорії графів і розробці архітектури паралельних обчислювальних систем для їхньої реалізації. У роботі запропоновані методи рішення задач булевого лінійного і нелінійного програмування, а також задач оптимізації на графах на основі ідеї рангового підходу, що дозволили підвищити оперативність і точність рішення задач оптимального планування процесом управління в телекомунікаційних системах і мережах. Розроблено архітектуру циклічних ПОС, що дозволяють розпаралелити процес обчислень при оптимальному плануванні.

У даній роботі на основі теоретичних досліджень вирішена важлива науково-технічна проблема, пов’язана з підвищенням оперативності рішення задач управління в телекомунікаційних системах та мережах на основі рангових методів рішення задач булевого програмування і теорії графів.
Результати які отримані у роботи мають самостійне значення, їх можливо використовувати як при побудові перспективних систем управління працюючих у реальному часі, так і при побудові систем штучного інтелекту.
При рішенні сформульованої у дисертаційній роботі проблеми отримані наступні основні наукові та практичні результати.
Наукові результати
Створені наукові основи рангових методів рішення задач булевого лінійного та нелінійного програмування, а також теорії графів, застосування яких дозволяє підвищити оперативність управління в телекомунікаційних системах та мережах завдяки:
зниженню часової складності алгоритмів їх рішення та, відповідно, зменшенню часу реалізації алгоритмів управління в телекомунікаційних системах та мережах;
використанню рангового підходу до організації обчислювального процесу, утворюючого можливості ефективно розпаралелити процес рішення задач управління телекомунікаційними системами та мережами, що дозволяє додатково підвищити оперативність рішення задач управління в них.
Показано, що використання розроблених методів рішення задач булевого програмування і теорії графів дозволяє на основі єдиного підходу оперативно вирішувати наступний комплекс задач управління в телекомунікаційних системах та мережах:
управління рішенням задач і використанням обчислювальних ресурсів мереж в умовах змінення її конфігурації;
управління маршрутизацією сполучень з забезпеченням мінімальної затримки передачі інформації в мережі;
оцінка пропускної спроможності в умовах змінення конфігурації мережі;
забезпечення адаптивного управління в вузлах мережі, до змінюющогося потоку завдань;
оцінка стану мережі і відбудова мережі у випадках відмов її функціональних елементів;
адаптивне відображення логічної структури бази даних мережі на її фізичну структуру в умовах деградації мережі;
планування розміщення рухливих центрів управління і комутації мережі при передислокації абонентів;
керування перерозподілом зон управління між серверами мережі;
управління оптимальним пошуком інформації в мережі.
На основі рангового підходу у роботі запропоновані паралельні алгоритми визначення
найкоротших маршрутів з часовою складністю О(n) для повно зв’язаних структур, а також послідовні та паралельні алгоритми визначення в мережах шляхів з максимальною пропускною спроможністю.
Розроблені алгоритми визначення шляхів з максимальною пропускною здатністю, що на відміну від відомих, дозволяють вирішувати дану задачу для мереж, які моделюються довільними графами. Часова складність розробленого послідовного алгоритму не перевищує О(n2) і О(n) паралельного алгоритму при його реалізації на n процесорних елементах, що дозволяє в n разів скоріше вирішувати задачу визначення шляхів з максимальною пропускною спроможністю в телекомунікаційних мережах та забезпечити управління мережею у реальному часі.
Розорблен комплексний підхід який дозволяє з єдиних позицій вирішувати широке коло задач управління телекомунікаційними системами та мережами, у вигляді універсального метода рішення довільних комбінаторних задач та задач оптимізації на графах, що уособлює загальну схему їх рішення. Можливості використання метода продемонстровані на широкому колі задач теорії графів та довільних задач булевого програмування, показано, що їх використання дозволяє знизити часову складність та погрішність рішень , які ми отримуємо.
Результати, які отримані на основі теореми розділу 3, дозволили вагомо знизити часову складність та погрішність рішення задач: визначення мінімальних вершинних покриттів і незалежних максимальних множин; оптимального фарбування графів, що має широке прикладне значення при створенні обчислювальних систем та мереж.
Розроблені алгоритми поліноміальної складності дозволяють одноманітно, з невеликою погрішністю ( яка зменшується з підвищенням числа обмежень) вирішувати задачі лінійного та нелінійного булевого програмування на запропонованій паралельній структурі циклічного типу.
Практичні результати.
Використання розроблених рангових методів рішення задач булевого програмування і
теорії графів дозволяє одноманітно і оперативно вирішувати задачі управління телекомунікаційними мережами.
Імітаційне моделювання алгоритму функціонування мережі показало, що :
рішення задач перерозподілу завдань в мережі , у випадку відмови процесорних модулів на вузлах мережі, дозволяє підвищити значення показника Еввід 25% до 85% (що дозволило підвищити ефективність управління мережами акт реалізації в в/ч А-0161, 1998р.);
оптимальне планування відбудови об’єктів мережі дозволяє зменшити у 2-3 рази та більше час відбудови мережі, що позитивно впливає на управління телекомунікаційними системами та мережами у цілому.
Оперативність рішення задач управління в телекомунікаційних мережах на основі рангового підходу на порядок вище, ніж у відомих методів. При цьому, значення показника оперативності Р 0,9 може бути забезпечено для задач що мають від 250 до 500 змінних.
Оцінка часової складності алгоритму функціонування мережі показала, що вона не перебільшує 7*О(n3m), у випадку її реалізації на одно процесорній системі, та 7*О(n2m) на ПОС з n процесорами.
Ранговий підхід може бути основою для створення наближених методів рішення NP-повних задач. Так, використання рангових алгоритмів до організації паралельних обчислень дозволило підвищити у 100 разів продуктивність пристрою управління роботизованної лінії виробництва. При цьому, умовний економічний ефект склав 7млн. руб. (Акт впровадження результатів дисертаційної роботи на заводі «Маяк» м. Курск, 1992р.).
На основі розроблених методів рішення задач булевого програмування і теорії графів запропонована архітектура паралельних обчислювальних структур циклічного типу для рішення задач динамічного управління в телекомунікаційних мережах, яка дозволяє вирішувати задачі управління з високою оперативністю.
У роботі запропоновані і проаналізовані абстрактні моделі організації паралельних обчислень на основі циклічної обробки інформації й адаптивності алгоритму обчислень до ширини алгоритму розв'язуваної задачі.
Адаптація архітектури обчислювальної системи до ширини алгоритму здійснюється за рахунок побудови у процесі реалізації алгоритму рішення задачі стягнутого дерева всіх шляхів, що дозволяє одержати максимальну паралельну форму алгоритму виконуваємої задачі (одержуємо алгоритм мінімальної висоти).
ПОС циклічного типу, які реалізовано на основі розглянутих моделей організації паралельних обчислювань, мають можливість нарощування своєї продуктивності за рахунок збільшення вкладеності системи
Запропоновано архітектуру ПОС циклічного типу, що дозволяє уникати конфліктні ситуації при обмінних операціях, що може дозволити ефективно вирішувати на таких ПОС сильно зв'язані задачі.
Застосування циклічних ПОС для реалізації алгоритмів з регулярною структурою дозволяє істотно знизити апаратурні витрати фактично без втрат у швидкодії.
Запропонована модель організації паралельних обчислень дозволяє розробляти мови паралельного програмування високого рівня в термінах звичного математичного апарата, оскільки спеціалізація процесорів на групу алгоритмів {Aj} може дозволити вирішувати цілі класи задач.
Достовірність отриманих результатів підтверджується даними математичного моделювання та добрим збіганням теоретичних результатів з експериментальними дослідженнями, а також практичним впровадженням результатів роботи. (акти реалізації в
в/ч А-0161,1998р., акт впровадження результатів роботи на заводі «Маяк» м. Курск 1992р., заключення по використанню результатів досліджень в підрозділах міністерства оборони 1991р., 1992р.)
Розроблені в дисертації методи рішення задач дискретної оптимізації і теорії графів в подальшому можливо використовувати при створенні перспективних систем автоматичного управління, які роблять у реальному часі, а також при побудові систем штучного інтелекту на основі баз знаній, та в системах економічного планування в різних галузях господарства.