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

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

Нехай у процесі функціонування мережі в моменти часу t1, t2 , … ,ti в ПМ виникають пакети відмов {yj}, і для усунення кожного пакета відмов {yj} потрібне виконання комплексу робіт Рj, реалізація якого можлива при наявності множини - необхідних засобів і фахівців. Множину можна представити у вигляді об'єднання двох множин (31) де hj - множина засобів h-го типу, необхідних для виконання комплексу робіт Рj; - множина фахівців l-ї спеціальності, що можуть забезпечити виконання комплексу робіт Рj. Позначимо час відновлення, зв'язаний з усуненням {yj} пакета несправностей - tвj. Він визначається:

1) часом tкрj виконання робіт, лежачих на критичному шляху крj у сітковому графіку усунення j-ї відмови , де tqj - час виконання q-ї критичної роботи Рqj по усуненню j-ї відмови;

2) часом чекання tожj , що залежить від: а) часу виявлення tобнj j-ї відмови; б) часу ухвалення рішення tпрj на формування оптимального плану усунення відмови; в) часу доставки tдj виділених, відповідно до плану засобів Хj(ti), у місця призначення для здійснення комплексу робіт Рj. Таким чином, час чекання визначається

, (34)

де trj - затримка у виконанні комплексу робіт Рj через невиконання умови Хj(ti) Хнj(ti).

Єдиний показник, на який ми можемо впливати, за рахунок оптимального планування може полягати в розробці послідовності планів розподілів Пr(t1), Пr(t2), ... , Пr(tі), (33) які забезпечують максимальну функціональну важливість виконання всього комплексу робіт. Породження планів Пr(tі) здійснюється в процесі багаторазового рішення наступної задачі:

, (35)

при обмеженнях: а) на кількість необхідних засобів h-го типу для відновлення j-го пакета відмовлень; б) на кількість фахівців l-ї спеціальності для відновлення j-го пакета відмов

(36)

(37)

де bj - сумарна важливість задач U, що не можуть бути вирішені в о-Пм у результаті j-го відмовлення, тобто

, (38)

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

, (39)

, (40)

Тоді час відновлення Тв* усього комплексу робіт з урахуванням наявних ресурсів буде визначатися співвідношенням Тв* = tкр + tож (40) . У випадку, коли передбачені резервні засоби, час переходу на резерв може бути враховане в часі відновлення.

Оптимальне планування передислокації пунктів управління в нестаціонарній телекомунікаційній мережі

Нехай мобільний абонент знаходиться в точці з координатами , . Імовірність того, що він установить зв'язок з ПУ уі дорівнює Р(dі), де dі - відстань від точки з координатами , , до точки розташування уі з координатами i, i. Величина Р(dі) може розглядатися і як імовірність зв'язку з урахуванням рельєфу конкретної траси між зазначеними точками. Завдання полягає у визначенні мінімального числа ПУ і місць їхнього розміщення для забезпечення стійкого зв'язку. Для цього територію позиційного району представимо у вигляді матриці з M рядками і N стовпцями, у якій елементи aіj приймають значення, рівне 1, якщо ПУ, установлений на j позиції, може забезпечити виконання умови Ріj Рд, (припустиме значення імовірності зв'язку), при цьому будемо говорити, що ПУ встановлений на j позиції покриває і квадрат, і aіj = 0 - у противному разі. У загальному випадку задача оптимального розміщення ПУ зводиться до пошуку мінімального покриття всіх рядків у матриці A множиною стовпців, тобто необхідно знайти вектор x*, який мінімізує цільову функцію , і задовольняючий обмеженням

, (41)

, (42)

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

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

Управління виконанням завдань у вузлах телекомунікаційної мережі

Дані, необхідні для рішення задач, і розв'язувані задачі вводяться в локальну пам'ять процесорних елементів. Усі задачі початкової множини Ф{uj} Ф{uj} зберігаються в загальній пам'яті багатопроцесорної системи (БПС) і при відмовах ПМ виробляється завантаження задач у пам'ять працездатних ПМ відповідно до знайденого плану розподілу. Стан системи визначимо як двійкий набір =(1, 2, … ,n), де i = 0 для працездатних ПМ і i = 1 для непрацездатних ПМ. Число можливих станів дорівнює 2n. Ефективність Е БПС у стані s будемо характеризувати множиною задач, що може вирішувати обчислювальна система в цьому стані. Кожна задача характеризується ступенем важливості, що визначає мету функціонування системи і задається ваговими коефіцієнтами. Припустимо, що відомо час j рішення задачі j, ємність пам'яті Vj ,необхідна для збереження програм і даних, Е - мінімально припустиме значення Е, Q - мінімальний рівень відмовостійкості, Тд - мінімально припустимий час однократного рішення задачі. Вважаємо, що j ? Тд , Vj ? Vд , де Vд - припустима ємність пам'яті займаний задачею на всіх ПМ, тобто будь-яка задача uj Ф може бути вирішена в будь-якому ПМ. Для визначення необхідного рівня відмовостійкисті БПС Q необхідно:

1) визначити граничне число q-процесорних модулів m q, при якому система залишається працездатною;

2) для кожного стану, що містить число працездатних ПМ m q знайти такий план розподілу задач, який би забезпечував максимальне значення сумарного коефіцієнта важливості при наявності обмежень на час рішення задач і ємність пам'яті, зайняти задачами і вихідними даними для їхнього рішення. Для довільного стану s розглянута задача може бути зведена до наступної задачі булевого програмування

, (43)

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

; (44)

; (45)

; (46)

, (47)

Тут обмеження (44) означає те, що задача j вирішується на одному ПМ.

Управління потоками інформації і маршрутизацією в телекомунікаційних мережах

Кожній передачі повідомлень від вузла і до вузла j приписується деяка імовірність Ріj перехоплення повідомлень. Із систем діагностики в циклі відновлення інформації в мережах уводяться дані про зміну матриць Ріj. Очевидно, що шляхи передачі повідомлень у мережі повинні утворювати остовне дерево графу G - чи мережі підграфу G^ G, визначеного адміністратором мережі для обміну інформацією між абонентами мережі. Потрібно знайти таке остовне дерево, що мінімізує величину 1 - (1 - Ріj). Запропоновано паралельний алгоритм побудови найкоротшого остовного (НО) дерева графа на основі рангового підходу з тимчасовою складністю не перевищуючої О(n). Якщо порівняти розглянутий паралельний алгоритм визначення НО з паралельними алгоритмами визначення найкоротших шляхів (паралельна реалізація алгоритму Дейкстри, розділ 3) і перебування шляхів з максимальною пропускною спроможністю (розділ 5), то не важко бачити, що вони усі можуть бути реалізовані на одній і тій же паралельній обчислювальній структурі (ПОС) яка розглянута у розділі 6. Отже, при використанні такої ПОС адміністратор мережі може задавати показник якості, на основі якого варто вибирати метод маршрутизації в мережі. Крім визначення оптимальних маршрутів і забезпечення скритності передачі інформації в мережі необхідно вміти оцінювати і пропускну спроможність мережі. У підрозділі 3.3 роботи показано, що ця задача зводиться до рішення ЗНП, для якої в розділі 2 розроблені ефективні алгоритми її рішення.

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

Таким чином у розділі 5 показано, що задачі: розподілу зон управління в мережі; розміщення пунктів управління мережі з мобільними абонентами; оцінки пропускної спроможності мережі; можуть бути зведені до рішення ЗНП методами, розробленими на основі рангового підходу в розділі 2, а також задачі: розподілу завдань у мережі в умовах її деградації; реконфігурації бази даних у мережі в умовах її деградації; відновлення об'єктів мережі в умовах її деградації; управління виконанням завдань у вузлах мережі зводяться до задачі ЦЛП із БЗ типу 0,1-рюкзак і теж можуть бути ефективно вирішені на основі алгоритмів, розроблених у розділі 2; задача визначення оптимальних маршрутів (найкоротших шляхів, з максимальною пропускною спроможністю чи з максимальною надійністю), а також задача забезпечення заданої скритності при передачі інформації з мережі, можуть бути ефективно вирішені на основі рангового підходу на ПОС. При цьому часовий виграш, для задачі визначення шляхів з максимальною пропускною спроможністю, та для задач визначення найкоротших шляхів і шляхів з максимальною надійністю пропорційний n.

Імітаційне моделювання процесу функціонування мережі показало, що рішення задач: перерозподілу завдань в мережі , у випадку відмовлення процесорних модулів на вузлах мережі, дозволяє збільшити значення показника ЕВ від 25 до 85%; оптимальне планування відновлення об'єктів мережі дозволяє підвищити від 2 до 10% значення КГ мережі та зменшити в 2 - 3 рази і більш час відновлення мережі. Оперативність рішення задач управління в мережах на основі рангового підходу суттєво вище, ніж у відомих методів, при цьому значення показника оперативності Р ? 0,9 може бути забезпечене для задач утримуючих, від 250 до 500 змінних. Оцінка часової складності алгоритму функціонування мережі, показала, що вона не перевершує О(7n3m) у випадку її реалізації на одно процесорній системі і - О(7n2m) на ПОС із n-процесорами.

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

У додатку приведені додаткові відомості задачі класу NP; аналіз стану дослідження ПОС; аналіз методів визначення найкоротших шляхів і задач динамічного програмування; оцінка достовірності моделювання задач управління в телекомунікаційних мережах; результати експериментальних досліджень розроблених алгоритмів.

ВИСНОВКИ

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

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

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

Наукові результати

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

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

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

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

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

- управління маршрутизацією сполучень з забезпеченням мінімальної затримки передачі інформації в мережі;

- оцінка пропускної спроможності в умовах змінення конфігурації мережі;

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

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

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

- планування розміщення рухливих центрів управління і комутації мережі при передислокації абонентів;

- керування перерозподілом зон управління між серверами мережі;

- управління оптимальним пошуком інформації в мережі.

На основі рангового підходу у роботі запропоновані паралельні алгоритми визначення

найкоротших маршрутів з часовою складністю О(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р.)

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

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

1. Методы моделирования и дискретной оптимизации вычислительных систем реального времени. В.Я. Жихарев, В.М. Илюшко, Л.Г. Кравец, С. В. Листровой, В.С. .Харченко // Под ред. В.Я. Жихарева, Харьков - Житомир, ЖГУ, 2004.- 494 с.

2. Листровой С.В. Певнев В.Я. Вопросы построения параллельных вычислительных систем и параллельный алгоритм для решения задачи о кратчайшем пути // Электрон. моделирование.-1990. -Т. 12, № 1.-С. 14 - 23.

3. Листровой С.В. Архитектура параллельных вычислительных систем циклического типа // Электрон. моделирование.- 1992.- том 14, № 2. - С. 28-36.

4. Листровой С.В. Параллельный алгоритм для задачи о кратчайших маршрутах на графе // Изв. АН СССР. Техническая кибернетика. - 1990.- № 4.- С.189 - 196.

5. Листровой С.В., Хрин В.Н. Параллельный алгоритм определения путей с максимальной пропускной способностью // Кибернетика и системный анализ.- 1998.- № 2. - С. 125 - 134.

6. LISTROVOY S.V., GOLUBNICHIY D. Yu. and LISTROVAYA E.S. Solution Method on the Basis of Rank Approach for integer Linear Programming Problems with Boolean Variables // Engineering Simulation, 1999, Vol. 16, pp.707 - 725.

7. LISTROVOY S.V., TRETIAK V.F. and LISTROVAYA A.S. Parallel Algorithms of Calculation Process Optimization for the Boolean Programming Problems // Engineering Simulation,1999, Vol. 16, pp. 569-579.

8. LISTROVOY S.V. and GUL A. Yu. Method of Minimum Covering Problem Solution on the Basis of Rank Approach // Engineering Simulation,1999, Vol. 17, pp. 73 - 89.

9. Листровой С.В. Метод решения задачи 3 выполнимость // Электрон. моделирование.- 2001.-№ 6.- С. 66 - 76.

10. Листровой С.В. Яблочков С.В. Метод решения задачи определения минимальных вершинных покрытий и независимых максимальных множеств // Электронное моделирование.-2003г. - Т. 25, № 2. - С. 31- 40.

11. Листровой С.В., Гуль А.Ю. Метод решения задачи о минимальном покрытии на основе рангового подхода // Электрон. моделирование.- 1999. - № 1. - С. 58 - 70.

12. Листровой С.В., Голубничий Д.Ю., Листровая Е.С. Метод решения задач целочисленного линейного программирования с булевыми переменными на основе рангового подхода // Электрон. моделирование. - 1998. - Т. 20, № 6. - С. 14 - 32.

13. Листровой С.В. Параллельный алгоритм для решения задачи линейного программирования с булевыми переменными // Электронное моделирование. -1991. - Т 13, № 3. -С. 29 - 32.

14. Листровой С.В., Третьяк В.Ф., Листровая Е.С. Параллельные алгоритмы оптимизации вычислительного процесса для задач булевого программирования // Электронное моделирование. - 1998. - № 5. - С. 23 - 33.

15. Листровой С.В., Хрин В.Н. О возможности решения задач оптимального распределения ресурсов при управлении сложными системами в реальном масштабе времени // Известия АН России. Техническая кибернетика. - 1992. - № 4. - C.125 - 133.

16. Листровой. С.В., Симашкевич О.Н. Об использовании гарантированных прогнозов в методах решения задач булевого программирования // Электронное моделирование. - 2003. - Т. 25, № 4.-С. 89 - 103.

17. Листровой С.В., Хрин В.Н., Вешкин Д.М. Исследование вычислительной сложности алгоритма определения путей с максимальной пропускной способностью // “Обработка информации и обеспечение надежности систем управления”, Харьков: НАНУ, ПАНИ, ХВУ. -1997, С. 137 - 140.

18. Листровой С.В., Певнев В.Я. О возможности распараллеливания комбинаторных задач на дереве путей графа // Всесоюзный семинар Вопросы оптимизации вычислений, докл. Киев: Институт кибернетики им. В.М. Глушкова АН УССР,1987, 223 с.

19. Королев А.В., Крючков О.М., Листровой С.В., Третьяк В.Ф. Оптимальное планирование реализации алгоритмов в вычислительных системах // Промышленность стройматериалов, энергоресурса сбережения в условиях рыночных отношений. ч8. Математическое моделирование и информационные технологии. Труды международной конференции. - Белгород. -1997. -

С. 163 - 171.

20. Листровой С.В., Яблочков С.В. Метод решения задач “вершинное покрытие” и “независимое множество” // Системи обробки інформації, Харків, НАНУ, ПАНІ, ХВУ.-2001р, вип. 2001, С. 136 - 141.

21. Листровой С.В., Дробот О.А, Тимочко О.И. Алгоритм для идентификации изображений, работающий в масштабе реального времени // Искусственный интеллект. - Донецк: Национальная академия наук Украины. Институт проблем искусственного интеллекта .-2003.- С. 173 - 178.

22. Листровой С.В., Голубничий Д.Ю. Алгоритм решения одномерной задачи (0,1)-рюкзак Сб. статей "Информационные системы". - Харьков: НАНУ, ПАНИ, ХВУ, 1995, С. 59 - 62.

23. Листровой С. В. Гуль А.Ю. Листровая Е.С. Точный алгоритм решения задачи о минимальном покрытии // Сборник научных трудов Информатика Вып.5 Киев НАНУ - Наукова думка 1998, С. 32 - 36.

24. Королев А.В., Листровой С.В., Третьяк В.Ф. Эффективность параллельных алгоритмов оптимизации вычислительного процесса // Информационно-управляющие системы на ж.-д. транспорте. - 1997. - № 1. - С. 85 - 91.

25. Листровой С.В., Тимочко А.И., Гуль А.Ю. О возможностях построения интеллектуальных вычислительных систем // Радіоелектронні і комп'ютерні системи Харків: „ХАІ” № 3, 2003р.,

С. 155 - 163.

26. Устройство для определения путей в графе: А.С.1462352 МКИ 06F15/20 Листровой С.В. и др.- № 4306139(СССР); Заявлено 04.08.87.Опубл.28.02.89, Бюл. № 8. - 6с. ил.

27. Устройство для решения задач на графах: А.С.17658332 МКИ 06F15/20 Листровой С.В.и др. - № 4729168(СССР); Заявлено 09.08.89.Опубл.30.09.92, Бюл. № 36.- 3с. ил.

28. Устройство для решения задач на графах: А. С. 1832310 МКИ 06F15/20 Листровой С.В .и др. - № 4786697(СССР); Заявлено 30.01.90. Опубл.07.08.90, Бюл. № 29. - 4с. ил.

29. Устройство для решения задач на графах: А. С. № 1639303 МКИ 06F15/20 Листровой С.В. и др. - № 4474346(СССР); Заявлено16.08.88. Опубл.01.12.90, Бюл. № 72.- 2с. ил.

30. Устройство для решения задач на графах: А. С. 1705841 МКИ 06F15/20 Листровой С.В. и др. - № 4828057(СССР); Заявлено05.03.90. Опубл.15.01.92, Бюл. № 2.- 7с. ил.

31. Устройство для решения задач на графах: А.С. 2478401 МКИ 06F15/20 Листровой С.В. и др. - № 4784401(СССР); Заявлено 18.01.90.Опубл.30.08.93, Бюл. № 32.- 10с. ил.

АНОТАЦІЯ

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

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

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

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

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

Диссертация на соискание ученой степени доктора технических наук по специальности 05.12.02 - “Телекоммуникационные системы и сети”. - Украинская государственная академия железнодорожного транспорта, Харьков , 2005 .

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

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

Второй раздел посвящен разработке теории решения задач ЦЛП с БП на основе идей рангового подхода, который рассмотрен на примерах решения задач 0,1-рюкзак и задачи определения минимального покрытия и их экспериментальному исследованию.

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

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

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

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

- управление маршрутизацией сообщений в сети;

- оценка пропускной способности в условиях изменения конфигурации сети;

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

- оценка состояния сети и восстановление сети в случаях отказов ее функциональных элементов;

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

- планирование размещения подвижных центров управления и коммутации сети при наличии подвижных пунктов управления.

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

В приложении приведены: дополнительные сведения о сводимости задач класса NP, анализ состоянии вопроса исследования ПВС; анализ методов определения кратчайших путей и сводимости задачи динамического программирования к задаче определения кратчайших путей; оценка достоверности моделирования задач управления в телекоммуникационных сетях; результаты экспериментальных исследований разработанных алгоритмов.

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

Listrovoy S.V. Real-time control of telecommunication systems and networks on the basis of rank method of Boolean programming problems solution and on the basis of graphs theory. - Manuscript.

The dissertation is prepared for competition for a scientific degree of a doctor of engineering (speciality is No. 05.12.02 - telecommunication systems and networks). - Ukrainian state academy of a railway transportation, Kharkiv, 2005.

The dissertation is devoted to increasing effectiveness of control solution in telecommunication systems and networks on the basis of using rank methods of solving Boolean programming problems and graphs theory as well as development of parallel computing structures for their implementation. In the research work methods of solving Boolean linear and non-linear programming problems are suggested, as well as optimization problems on graphs on the basis of rank approach ideas permitting to increase effectiveness and accurateness of solving problems in optimal planning the process control in telecommunication systems and networks. Cyclical parallels' computing structures permitting to deparallelize the process of computations with optimal planning were developed.

Key words: discrete optimization, theory of graphs, NP-complete problems, real-time systems control.

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

...