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

Поставлена мета досягається шляхом рішення таких задач дисертаційного дослідження: - розробка теоретичних основ рішення задач управління які базуються на розробці методів рішення задач булевого програмування та теорії графів на основі рангового підходу, який дозволяє знизити часову складність та погрішність отриманих рішень; У якості основних критеріїв ефективності функціонування мережі у роботі використовувались коефіцієнт збереження ефективності, що характеризує ступінь впливу відмов на ефективність застосування мережі за призначенням і показник оперативності рішення задач динамічного управління в мережі за деякий припустимий час рішення Тд , що кількісно оцінюють імовірністю Р(Т) рішення комплексу задач динамічного управління потоками інформації в мережах Р(Т) за час Т, не перевищуючий Тд: Ксэ = ; (1) ; Р(т) = 1-е , де Ев - корисний ефект операції управління; E? - значення показника ефективності функціонування мережі після здійснення керуючого впливу в мережі; E0 - номінальне значення показника ефективності функціонування мережі. Серед задач оптимізації на графах з погляду побудови інтелектуальних телекомунікаційних мереж і процесів управління в них, на основі проведеного аналізу, можна виділити такі задачі: задачі визначення найкоротших шляхів і найкоротших гамільтонових шляхів у графах; задача визначення мінімальних верхових покрить і незалежних максимальних множин, у довільних графах; задача оптимального фарбування графів; задачі “виконавчість” і “3-виконавчість”; задачі ізоморфізму підграфів і графів. Таким чином, існує проблема оперативного рішення задач динамічного управління мережею, формальними моделями яких є задачі ЦЛП із БЗ великої розмірності і задачі нелінійного булевого програмування. Таким чином, при розробці паралельних алгоритмів рішення задачі ЦЛП із БЗ, крім протиріччя між точністю рішення задачі і часом її рішення виникає ще одне протиріччя між сильною звязаністю задачі і необхідністю її розпаралелювання з метою одержання припустимого часу рішення.У даній роботі на основі теоретичних досліджень вирішена важлива науково-технічна проблема, повязана з підвищенням оперативності рішення задач управління в телекомунікаційних системах та мережах на основі рангових методів рішення задач булевого програмування і теорії графів.Створені наукові основи рангових методів рішення задач булевого лінійного та нелінійного програмування, а також теорії графів, застосування яких дозволяє підвищити оперативність управління в телекомунікаційних системах та мережах завдяки: - зниженню часової складності алгоритмів їх рішення та, відповідно, зменшенню часу реалізації алгоритмів управління в телекомунікаційних системах та мережах; використанню рангового підходу до організації обчислювального процесу, утворюючого можливості ефективно розпаралелити процес рішення задач управління телекомунікаційними системами та мережами, що дозволяє додатково підвищити оперативність рішення задач управління в них. Показано, що використання розроблених методів рішення задач булевого програмування і теорії графів дозволяє на основі єдиного підходу оперативно вирішувати наступний комплекс задач управління в телекомунікаційних системах та мережах: - управління рішенням задач і використанням обчислювальних ресурсів мереж в умовах змінення її конфігурації; Розроблені алгоритми визначення шляхів з максимальною пропускною здатністю, що на відміну від відомих, дозволяють вирішувати дану задачу для мереж, які моделюються довільними графами. Часова складність розробленого послідовного алгоритму не перевищує О(n2) і О(n) паралельного алгоритму при його реалізації на n процесорних елементах, що дозволяє в n разів скоріше вирішувати задачу визначення шляхів з максимальною пропускною спроможністю в телекомунікаційних мережах та забезпечити управління мережею у реальному часі.Використання розроблених рангових методів рішення задач булевого програмування і теорії графів дозволяє одноманітно і оперативно вирішувати задачі управління телекомунікаційними мережами. Імітаційне моделювання алгоритму функціонування мережі показало, що: - рішення задач перерозподілу завдань в мережі , у випадку відмови процесорних модулів на вузлах мережі, дозволяє підвищити значення показника Ев від 25% до 85% (що дозволило підвищити ефективність управління мережами - акт реалізації в в/ч А-0161, 1998 р.); оптимальне планування відбудови обєктів мережі дозволяє зменшити у 2-3 рази та більше час відбудови мережі, що позитивно впливає на управління телекомунікаційними системами та мережами у цілому. При цьому, значення показника оперативності Р ? 0,9 може бути забезпечено для задач що мають від 250 до 500 змінних. На основі розроблених методів рішення задач булевого програмування і теорії графів запропонована архітектура паралельних обчислювальних структур циклічного типу для рішення задач динамічного управління в телекомунікаційних мережах, яка дозволяє вирішувати задачі управління з високою оперативністю.