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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Вступ

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

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

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

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

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

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

Поставлена мета досягається шляхом рішення таких задач дисертаційного дослідження:

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

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

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

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

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

Kсэ = ; (1) ; Р(т) = 1-е,

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

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

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

При цьому варто мати на увазі, що практично всі задачі комбінаторної оптимізації на графах можуть бути сформульовані як задачі цілочислового лінійного програмування з булевими змінними (ЦЛП із БЗ). Задачі ЦЛП із БЗ і велика частина комбінаторних оптимізаційних задач відносяться до класу NP-повних, і важко піддаються рішенню навіть при використанні сучасних ЕОМ. Підвищення продуктивності сучасної ЕОМ у 1000 разів дозволяє збільшити розмірність розв'язуваної задачі за прийнятний час на (5 - 7) змінних.

Тому, що при використанні комбінаторних методів обчислювальний процес є кінцевим за своєю побудовою, то питання про збіжність методу не виникає. Особливу важливість у цьому випадку здобуває оцінка практичної застосовності методів, тобто можливості одержання рішення задачі за припустимий час. Застосування методів гілок та кордонів для одержання точних рішень, при управлінні мережею, стає неможливим вже при розмірах задач, рівних 40. Відомі наближені і е - оптимальні алгоритми рішення задачі ЦЛП із БЗ самі по собі відносяться до NP-повних, тобто з підвищенням точності алгоритмів число кроків алгоритму, необхідне для забезпечення заданої точності, починає экспоненциально зростати. Використання локальних алгоритмів для рішення задачі ЦЛП із БЗ досить великої розмірності не може гарантувати наперед задану точність. Як показують дослідження, локальний екстремум може відрізнятись від глобального на 70 - 90%. Останнє неприпустимо, при динамічному управлінні в мережах спеціального призначення, оскільки це може призвести до того, що значення показника ефективності роботи мережі виявиться нижче припустимого, і цілі управління в системі не будуть досягнуті. Методи ж рішення довільних нелінійних задач булевого програмування практично відсутні. У сучасних мережах, через зазначені труднощі, для рішення задач, використовуються евристичні алгоритми, що базуються на деяких "розумних" правилах, і, так само як і локальні алгоритми, не гарантують одержання рішень з високою точністю. Таким чином, існує проблема оперативного рішення задач динамічного управління мережею, формальними моделями яких є задачі ЦЛП із БЗ великої розмірності і задачі нелінійного булевого програмування.

Слід зазначити, що спроби зменшити час рішення задач ЦЛП із БЗ за рахунок розпаралелювання зіштовхуються з іншою проблемою теорії паралельних обчислень, що полягає в тому, що з погляду теорії паралельних алгоритмів даний тип задач відноситься до класу сильно зв'язаних задач, які важко піддаються розпаралелювання. У роботах Сергиенко И.В. показано, що при реалізації методів гілок та кордонів на багатопроцесорних обчислювальних системах збільшення числа процесорних елементів призводить до зниження продуктивності системи в цілому і, що для цього класу задач необхідно визначати оптимальне число процесорних елементів, на якому доцільно вирішувати задачу. Таким чином, при розробці паралельних алгоритмів рішення задачі ЦЛП із БЗ, крім протиріччя між точністю рішення задачі і часом її рішення виникає ще одне протиріччя між сильною зв'язаністю задачі і необхідністю її розпаралелювання з метою одержання припустимого часу рішення. Тому в даній роботі, для усунення зазначених протиріч, при рішенні задач динамічного управління мережею і задач автоматизації процесу ухвалення рішення, розглядається рішення такого комплексу задач:

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

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

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

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

Формальні моделі, яких відповідно мають вигляд:

,

,

,

,

.

В основі ідеї рангового підходу лежить представлення n-мірного одиничного куба у виді графа GD, геометричний зміст якого полягає в наступному. Геометрично вершина k графа GD рангу r - це множина векторів (x1, x2, ... , xk, ... , xn), у яких xk = 1, а на позиціях від 1 до k знаходиться r одиниць. Ребру, що входить у вершину k графу GD , відповідає одиничний вектор (0, 0, ... , 0, 1, 0, ... , 0) n - мірного одиничного куба Bn з одиницею в k-й позиції.

Тоді, шляху рангу r у графі GD відповідає вектор , який дорівнює сумі одиничних векторів ребер, по яким він досяг вершину j рангу r, починаючи з вершини s. Множину шляхів у графі GD до вершин j, розташованим на ярусах від вершини s, можна представити у вигляді:

де - множина шляхів у графі GD від вершини s до вершин j, розташованих на r-х ярусах графа GD, ( ранг шляху О визначається числом ребер, що утворюють цей шлях ). Варто мати на увазі, що множину шляхів у графі GD відповідає множині векторів, що містять k одиниць. Отже, тобто кожному шляху в множині відповідає деякий вектор . Випливає:

Таким чином, граф GD являє собою упорядкований по рангах еквівалент n-мірного одиничного куба Bn , у якому шляхи О відповідають вершинам Bn. Для рішення задач у розділі 1 запропонована система каліброваних векторів що дозволяє звести рішення цих задач до визначення екстремальних шляхів у графі GD. Сформульовано:

- принцип оптимізації за напрямком, обумовлений співвідношенням:

- принцип виділення коридору в підмножинах:

,

де {Lw} правила відсікань шляхів у множинах ; - шлях з вершини s графу GD шлях у вершину p, що проходить через проміжну вершину j та задовольняє правилам {Lw}, тобто шлях отриман за рахунок приєднання до шляху ребра (j,p), якщо таке з'єднання не суперечить правилам {Lw}. Для рішення задач, запропонована узагальнена процедура А0, що дозволяє визначити локальні екстремуми в W-областях графу GD щораз і потім виділяти глобальний екстремум з n(n+1)/2 локальних, отриманих на основі принципу оптимізації за напрямком (11) з використанням правил відсікань{Lw} шляхів у множинах, що вводяться. У розділі розглянуті стратегії відсікання {Lw} безперспективних шляхів у множинах, що призводять до наближених і точних рішень задачі ЦЛП із БЗ, і побудоване множину ефективних точних і наближених алгоритмів рішення задач ЦЛП із БЗ. Запропоновано процедуру визначення гарантованих прогнозів і досліджений їхній вплив на часову складність алгоритмів і погрішність. Показано, що введення гарантованих прогнозів дозволяє на 40% знизити часову складність розроблюваних алгоритмів і підвищити їхню точність.

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

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

На основі методу рішення ЗНП побудовано алгоритм рішення задач "3-виконавчість" поліноміальної складності О(26m) для трьох змінних ( де m кількість диз'юнктів), та алгоритм експоненціальної складності для рішення задачі “k-виконавчість”", який працює у середньому як поліноміальний з часовою складністю О(0,25k3).

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

Теорема. Якщо f булева функція, побудована за графом G = (V, E) у вигляді добутку диз'юнктів (vі v vj), де {vі} О {0, 1} і при цьому кожен диз'юнкт (vі v vj) відповідає ребру (vі, vj), то всі набори змінних {vі, vj} на яких вона приймає значення "істинно", відповідають верховим покриттям у графі G = (V, E).

Наслідок. Для перерахування усіх верхових покрить графу G = (V, E) необхідно визначити ті системи значень змінних {vі, vj}, при яких вираз f (V1,V2...Vn) = 1 "істинний". Щоб знайти ці системи значень змінних {vі, vj} необхідно привести ліву частину до мінімальної ДНФ (диз'юнктивна нормальна форма), розкриваючи дужки і користуючись законом поглинання.

Така форма єдина через відсутність логічних заперечень. Показано, що на основі булевої функції, побудованої за довільним графом G = (V, E) з n вершинами можна побудувати конструкції Qі = Lі И Dі, де Lі - деяка підмножина вершин, вхідних у верхове покриття графа G = (V, E) без вершини і , а Dі - дводольний граф із ще непокритих ребер графу, і на їхній основі побудувати наближений алгоритм визначення мінімального верхового покриття в довільних графах з тимчасовою складністю, не перевищуючу О(n3), та середнім значенням похибки, не більш 6-7%. Проведено порівняльний аналіз розробленого алгоритму з відомими і показано, що часова складність даного алгоритму суттєво менше ніж у кращих відомих алгоритмів.

На основі розробленого алгоритму визначення мінімального верхового покриття і процедури динамічного програмування для фарбування графів, запропонованої Кристофидесом, побудований наближений алгоритм складності О(n3) для оптимального фарбування довільних графів.

У розділі розглянутий загальний підхід до рішення довільних задач теорії графів і дискретної оптимізації та побудований універсальний алгоритм їхнього рішення, який являє собою схему рішення довільних задач теорії графів. Робота розробленого в розділі підходу продемонстрована на прикладі рішення задач визначення незалежних максимальних зважених множин і задачі визначення найкоротшого гамільтонового циклу і показано, що якщо базові елементи, з яких будується цікавлячий нас об'єкт, характеризуються m + 1 ваговими характеристиками й оптимізація об'єкта здійснюється за однією ваговою характеристикою, то в загальному випадку при довільних об'єктах складність наближених алгоритмів не перевищить О(kn3), де k - число операцій, необхідних для визначення оптимальної ваги об'єкта при додаванні в нього ще одного базового елемента. У випадку, коли на m ваг об'єкта накладається обмеження, то в цьому випадку ми приходимо до задач лінійного і нелінійного булевого програмування. На основі запропонованої загальної схеми рішення комбінаторних задач у розділі розроблений і загальний метод рішення довільних задач булевого програмування, який дозволяє будувати наближені алгоритми, що володіють малою часовою складністю і погрішністю. Слід відзначити, що погрішність рішень алгоритмів побудованих на основі запропонованого методу для кожного комбінаторного об'єкту необхідно оцінювати окремо. Для опису всієї множини адитивних цілочислових функцій з довільними нелінійностями, які можуть виникнути на множині змінних {X1, X2 ... Xn}, уведене поняття породженої функції F(x) рівної:

,

де - сума всіх можливих сполучень добутків змінних, утримуючих у кожному добутку (не лінійності) r різних змінних; ; -цілочислові коефіцієнти, що знаходяться в добутках , утримуючих змінних. Позначимо через H множину усіх цілочислових адитивних функцій, які можна породити на основі F(x), покладаючи рівними нулю різні сполучення в. Множина H є повна у тому розумінні, що містить у собі всі можливі нелінійності, що складаються з усіх можливих сполучень змінних, утворюючих ці нелінійності, які можна взагалі побудувати на основі даної підмножини змінних {X1, X2 ... Xn}.

Розглянемо граф G(Х, Е), у якому вершини Хі та Хj з'єднані ребром (і, j), якщо вони можуть бути об'єднані в кліку. У графі G(Х, Е) кожній вершині Хі відповідає змінна Хі. Виділимо в графі G довільну кліку Q = , що складається з r вершин, де r < n, і розглянемо її перетинання з , а також з . Кожне перетинання можна охарактеризувати сумами коефіцієнтів, що стоять при у функціоналі та обмеженнях , при цьому в загальному випадку довільна кліка Q завжди буде характеризуватися відповідною вагою по функціоналу і не більш ніж m вагами по обмеженням . Таким чином, довільна задача булевого програмування може розглядатися як задача визначення кліки Q* максимальної ваги по вагах функціонала, у графі G, у якої всі m ваг по вагах обмежень не перевищують відповідно bj. Кожному шляху рангу r у графі D, який задає весь простір рішень, минаючому через вершини (vh, vk ... vp) у вихідному графі G розв'язуваної задачі відповідає кліка з (r - 1)- вершини (), що характеризується відповідною вагою за функціоналом і не більш ніж m вагами по обмеженнях. Вагові характеристики {dsjr-1} довільної кліки Qr-1(j) складаються з ваг (r - 1)- вершини й обумовлені одним зі шляхів О рангу r у графі D вони обчислюються, по вагам функціонала, шляхом підсумовування коефіцієнтів підмножини Lf ={}, стоячими при О Рf , де Рf - усі підмножини { }f задовольняючі умові f З Qr - 1(j) № Ж, а f визначається функціоналом . Аналогічно визначаються вагові характеристики по вагах обмежень шляхом підсумовування коефіцієнтів підмножини LВ = {}, що стоять при О РВ, де В усі підмножини, задовольняючі умові З Qr - 1(j) № Ж, а визначається обмеженнями . Таким чином, вагові характеристики клік Qr - 1(j) шляхів, що характеризуються множиною , по вагам функціонала й обмежень визначаються відповідно рівностями dsjf(r - 1) = ; dsjВ(r - 1) =.

Для рішення задачі розроблені три різних алгоритми, реалізуючі однопрохідні і n-прохідні процедури рішення задачі (15) з часовими складностями О(n5 k(m + 1)), О(n4 k(m + 1)), О(n3 k(m + 1)) і проведене їх експериментальне дослідження.

При дослідженні коефіцієнти у функціоналі й обмеженнях генерувалися за рівномірним законом розподілу у функціоналі у діапазоні від 0 до10, а у обмеженнях від 0 до 20. На кожну точку графіків при оцінці часової складності алгоритмів у середньому і погрішності алгоритмів вирішувалось не менше 50 тестових задач, результати отримані з довірчою імовірністю 0,95. У якості точного алгоритму використовувався розроблений алгоритм для рішення задачі квадратичного і лінійного програмування, скомбінований на основі використання ідей рангового підходу (для прогнозування верхньої оцінки рішення) і методу гілок та кордонів ( для відсівання безперспективних шляхів), який дозволив оцінити погрішності для задач до розмірності, не перевищуючої n = 70. Графіки залежності погрішності від розмірності (n) розв'язуваних задач і від числа обмежень (m) з яких видно, що погрішність алгоритмів зі збільшенням числа обмежень m асимптотично зменшується, а при m і 50 погрішність алгоритмів стабілізується і для задач лінійного програмування не перевищує 2%, а для задач квадратичного 5 - 10%. Рішення тестових задач показало, що збільшення діапазону зміни коефіцієнтів у функціоналі й обмеженнях призводить до різкого зниження погрішностей алгоритмів, перехід від нелінійностей одного порядку до нелінійностей більш високого порядку може призводити до незначного зростання погрішностей при невеликому числі обмежень, але з зростанням числа обмежень зростання погрішності дуже швидко компенсується. Експериментальне дослідження часової складності показало, що число оброблюваних векторів слабко залежить від числа обмежень і в середньому для алгоритмів часова складність не перевищує відповідно О(0,1n4, 9), О(0, 3n3, 7) та О(0, 4n2, 8).

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

Що дозволяє представити множину усіх шляхів {Мst}, між даною парою вершин s і t у вигляді наступного об'єднання підмножин Mst = Mr =1st U Mr = 2st U ... U Mr = n - 1st, де Mst r - множини шляхів між вершинами s і t рангу r і розглядати її як задачу визначення шляху деякого рангу r мінімальної довжини в множину Mst. Відмінною рисою запропонованих алгоритмів є те, що на кожному кроці роботи порівнюються величини шляхів того самого рангу. Ця відмінність від відомих алгоритмів дозволяє зробити ефективне розпаралелювання алгоритму визначення найкоротших шляхів у графі. На основі рангового підходу запропонована паралельна реалізація алгоритму Дейкстри для довільних повних графів, часова складність якого для повних графів не перевищує О(n).

Часовий виграш при розпаралелюванні на основі алгоритму Форда пропорційний n/rk , що визначається значенням середнього рангу найкоротшого шляху при рівномірному законі розподілу ваг довжин ребер приведений у таблиці 1.

Так з таблиці (1) видно, що для повного графа з 70 вершинами паралельний алгоритм у середньому за десять кроків визначить величину найкоротшого шляху.

Таблиця 1. Значення середнього рангу і максимального рангу найкоротшого шляху

n	25	30	35	40	45	50	60	70
rk	7	8	8	8	9	9	9	10
max r	11	11	11	12	12	12	14	12

У розділі так само побудований ефективний алгоритм визначення шляхів з максимальною пропускною спроможністю, що відрізняється від відомих тим, що пропускна спроможність мережі визначається не як , де k - будь-який s-t розріз у множині ребер Е, сіj - пропускні здібності ребер графа мережі, а використовуючи лише властивість шляхів графа, що полягають в тім, що пропускна спроможність шляху mst визначається ребром (і, j) ) О mst з найменшою пропускною спроможністю сіj тобто . На відмінну від відомих алгоритмів Френка і Фриша, застосовних тільки для орієнтованих графів, запропонований алгоритм може бути застосований для довільних графів і має часову складність для повних графів, не переважаючу O(n2) для його послідовної реалізації і - O(n) при його паралельній реалізації на основі рангового підходу.

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

Задача розподілу зон управління в телекомунікаційних мережах.

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

Задача повинна вирішуватись з урахуванням деградації мережі, у реальному часі. Для кожної вершини графу k О V' відповідно до G(V, E) можливо визначити множину абонентів {Аі}, які можуть бути опитані за час t Ј tдоп, будуючи дерева найкоротших шляхів з вершин k О V (на основі алгоритмів, наведених у розділі 4) і при цьому всі абоненти, для яких час опитування tі > tдоп, виключаються з підмножини {Аі }. Уведемо змінні bij та Xj, обумовлені наступними виразами:

,

.

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

Мінімізувати цільову функцію , задовольняючу обмеженням:

, .

В окремому випадку, коли tj = 1, ми приходимо до задачі визначення мінімального числа серверів, що охоплюють управлінням усю мережу, при цьому в зоні j-го сервера виконується нерівність tj Ј tдоп , де J = |V`|.

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

Для оцінки процесу управління розподілом задач у мережі будемо використовувати такі показники якості:

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

,

де nn - загальне число ПМ у мережі в стані Sn; mі - загальне число задач, що здатен вирішувати і-й ПМ у стані Sn; bmi - вага m-ї задачі і-го ПМ, що характеризує її важливість (пріоритет) для управляючої системи; - сумарний час доступу до даних у мережі, обумовлений розміщенням сегментів бази даних (БД) мережі на її фізичній структурі, де - середній час вибору 1 кілобайта інформації з і-го фрагмента у вузлі j; lij - коефіцієнт , що враховує швидкість вибору й обробки 1 мегабайта даних при звертанні до і-го фрагмента БД у j вузлі; Vi(b) - ємність зовнішньої пам'яті, необхідної для розміщення і-го фрагмента БД; pі - характеристика частоти використання і-го фрагмента БД при функціонуванні системи управління базою даних (СУБД); Кj - коефіцієнт, що показує швидкість доступу до даних на j-му вузлі мережі;

Тв - середній час відновлення мережі Тв.

Нехай мається Мі - управляючих процесорних модулів (ПМ), які служать для управління об'єктами Oe. Відмови системи зв'язку і відмови ПМ вважаємо незалежними. Під станом s(t) на момент часу t мають на увазі набір станів усіх модулів у цей момент, тобто s(t)=s1,…,sn , де si О {0,1} та:

Початковий стан системи s(t = 0) = s0 = 00…0. Нехай Ln - множина усіх станів системи; D = {М1,… Мn - множина усіх модулів системи; Wn = {U1, … ,UL}- множина усіх задач розв'язуваних у мережі в стані Sn; - підмножина задач, що працездатний модуль Мі здатний вирішувати, коли система знаходиться в стані Sn. Для стану s0 задана множина W0 = {Uj}, 0 = {Uj},і початковий розподіл задач між усіма модулями, тобто підмножини . Нехай Dfn = {Мi}n, Drn = {Мi}n - множини відповідно ПМ які відмовили і працездатних ПМ, що відповідають стану Sn ; Аfn - множина усіх власних задач модулів, що відмовили, для стану Sn; Аrn = W0\Аfn - множину усіх власних задач р-Пм для стану Sn. Кожна задача характеризується ступенем важливості, що визначає мету функціонування системи управління і задається ваговим коефіцієнтом {bmi}. Тоді результат перерозподілу задач визначається корисним ефектом Е, оцінюваним сумарною ваговою характеристикою множин задач, вирішуваних в мережі у даному стані Sn , який називають функціональною потужністю мережі (Еn). Крім того, кожна задача має ряд інших параметрів. Наприклад, середній час обслуговування (перебування) задачі m в і-му ПМ, що задається матрицею ккDТmiзз час пересилання (затримки) ззtmiзз, час пересилання (затримки) tі повідомлень задачі m в і-му ПМ і т.д. Тоді формальна модель задачі перерозподілу прийме такий вигляд. Необхідно забезпечити корисний максимальний ефект перерозподілу, , при обмеженнях:

; ; ; ,

де:

DTnдоп, Vnдоп, Tnдоп - припустимі граничні значення, відповідно, сумарного середнього часу обслуговування задачі в і-му ПМ, ємності пам'яті, необхідної для рішення задачі й часу перерозподілу інформації у всій мережі в цілому (визначається циклом відновлення інформації в мережі).

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

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

Виникнення відмов у мережі, пов'язаних з виходом з ладу елементів зовнішньої пам'яті, що містять сегменти баз даних (БД) мережі, можуть призвести до повного відмовлення мережі тому частина найбільш важливих фрагментів дублюють по різних вузлах мережі. Якщо число різних фрагментів бази даних мережі позначити через m, то для нормального функціонування мережі повинна виконуватись нерівність.

,

де:

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

,

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

, , , ,

де V0j - обсяг доступної для СУБД на вузлі j оперативної пам'яті; tіj - середній час передачі даних по експлуатованих каналах зв'язку; Тд - припустимий сумарний час передачі даних по мережі.

У БД важливо організувати ефективний пошук інформації, з погляду мінімізації часу її пошуку. Припустимо, що m записів зберігається в n масивах інформації довжини Сj і потрібно знайти всі m записів і при цьому провести перегляд масивів як можна меншої довжини. Складемо матрицю А = ||aij||, у якій стовпці відповідають масивам, а рядки відповідають записам, що містяться в масивах. Елемент aij дорівнює 1, якщо в j-м масиві міститься і-я запис, і 0 у противному разі. Тоді нам потрібно знайти мінімальне число масивів, у яких містяться m записів, якщо масиви однакової довжини, чи визначити число масивів мінімальної довжини, у яких містяться всі m записів у випадку масивів різної довжини. Що дозволить переглядати не всі масиви БД, число яких у БД може бути досить велике, і за рахунок цього зменшити час пошуку інформації. Ця задача відома як задача про мінімальне зважене покриття й у даному випадку вона має вигляд:

,

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

,

де n - число масивів; m - число записів, які необхідно знайти в n масивах; Сj - довжина j-го масиву. Рішення задачі на основі рангового підходу розглянуто в розділі 2.

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

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

,

де ahj - множина засобів h-го типу, необхідних для виконання комплексу робіт Рj; - множина фахівців l-ї спеціальності, що можуть забезпечити виконання комплексу робіт Рj. Позначимо час відновлення, зв'язаний з усуненням {yj} пакета несправностей - tвj. Він визначається:

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

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

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

Висновки

булевий телекомунікаційний ранговий

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

На основі рангового підходу у роботі запропоновані паралельні алгоритми визначення найкоротших маршрутів з часовою складністю О(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.

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

...