лот. Пояснювальна записка Другий (магістерський) (рівень вищої освіти)
 Скачать 4.57 Mb.
|
 Рисунок 1.7 – Композиційна схема рішення задачі структурного синтезу у вигляді цільової діаграми [8] Завдання, що знаходиться в стані розв’язання, може бути подане набором даних, який містить значення поточного часу, інформацію про передбачувані і реальні дати початку і закінчення розв’язання задачі; вхідні і вихідні дані; набір ідентифікаційних даних для множини виконавців з позначенням їх обов’язків і прав в рамках виконання проекту структурно-топологічної оптимізації комп’ютерної мережі. Об’єднавши подання простору станів для процесу вирішення загального завдання структурного синтезу і подання інформаційної взаємодії об'єкта і суб'єкта проектування, з урахуванням типового маршруту проектування, розподілена динамічна задача структурного синтезу може бути подана наступним чином (рисунок 1.8). Математична модель проектованого об'єкта і технічна документація по проекту виділені як особливі дані, доступні на всіх етапах маршруту рішення задачі структурного синтезу мережі.  Рисунок 1.8 – Схема маршруту рішення розподіленої динамічної задачі структурного синтезу мережі [8] Такий маршрут розв’язання задачі структурного синтезу комп’ютерної мережі має на увазі застосування блочно-ієрархічної декомпозиції об'єкта У результаті аналізу було виявлено, що найбільш ефективним можна вважати метод направленого перебору та його модифікації, які реалізують розміщення вузлів на основі методів покоординатної оптимізації, кластеризації t-means та методу Tabu Search [9]. Метод пошуку з заборонами Tabu Search є одним з найбільш ефективним евристичних методів. Характерна риса цього методу полягає в процесі введення і зняття деяких штучних обмежень в ході пошуку оптимального рішення. Основним недоліком методу є його зупинка при досягненні локального оптимуму, бо при пошуку глобального оптимуму, очевидно, що глобальний оптимум є також і локальним, тому для успішного пошуку рішень виникає необхідність переходу від одного локального оптимуму до іншого. У методі з метою подолати вищеописаний недолік вводиться так званий список заборон Tabu List. Цей список містить деяку кількість попередніх рішень, і при виборі нового рішення забороняється вибирати рішення, що містяться в списку заборон. Даний прийом допомагає уникати застрягання в локальному оптимумі, розширює простір пошуку, дозволяючи алгоритму пошуку з заборонами знаходити найкращі рішення [10]. Найбільш простий, але в той же час досить неточний метод кластеризації t-means розбиває множину елементів векторного простору на заздалегідь відоме число кластерів k [11]. У ході алгоритму проводиться мінімізація середньоквадратичного відхилення на елементах кожного кластера. На кожній ітерації проводиться розрахунок центроїду для кожного кластеру, отриманого на попередньому кроці, після чого елементи мережі розбиваються на кластери відповідно до того, який з нових центрів виявиться ближчим за обраною метрикою. Алгоритм проводиться до тих пір, коли на ітерації не відбувається зміни кластерів. До основних проблем можна віднести те, що необхідно заздалегідь знати кількість кластерів. Також алгоритм дуже чутливий до вибору початкових центроїдів кластерів. Класичний варіант має на увазі випадковий вибір кластерів, що дуже часто було джерелом похибки. Існують ситуації, коли елемент мережі належить до різних кластерів рівною мірою. Процес пошуку оптимуму методом покоординатної оптимізації передбачає вибір довільної точки з її координатами. Пошук оптимуму здійснюється почерговою зміною кожного з необхідних показників. При цьому спочатку змінюють один фактор при фіксованих інших до тих пір, поки не припиняється приріст функції відгуку. Далі змінюється інший фактор при фіксованих інших і далі процедура повторюється. Даний метод досить простий, однак має деякі недоліки, наприклад, при великій кількості факторів потрібне велике число дослідів, щоб досягти оптимального значення. Також при деяких залежностях цей метод може призвести до помилкового результату. Як результат – знайдений екстремум буде помилковим [12]. Еволюційний синтез на основі генетичного алгоритму – це евристичний алгоритм пошуку, який використовується для вирішення завдань оптимізації та моделювання шляхом випадкового підбору, комбінування і варіації параметрів. В алгоритмі реалізуються процедури успадкування, мутації, відбору, кросинговеру. Кожна хромосома відображає множину місць розміщення вузлів у ході певної ітерації . У якості гену використовується код індексу вузла, а в якості функції пристосованості – критерій. Завдання формалізується таким чином, щоб рішення могло бути закодовано у вигляді вектора генів. Спочатку створюється множина генотипів випадковим чином та проводиться оцінка з використанням функції пристосованості, в результаті чого з кожним генотипом асоціюється певне значення, яке визначає наскільки добре фенотип вирішує поставлене завдання. З отриманої множини рішень вибираються рішення, до яких застосовуються генетичні оператори (схрещування та мутація), з урахуванням значення пристосованості у результаті отримують нові рішення. Для них також обчислюється значення пристосованості, і потім проводиться відбір кращих рішень в наступне покоління. Цей набір дій повторюється ітеративно, поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути: знаходження глобального, або субоптимального рішення; вичерпання числа поколінь, виділених на еволюцію; вичерпання часу, виділених на еволюцію. Таким чином, можна виділити такі етапи: задання цільової функції; створення початкової популяції; операції схрещування та мутації; обчислення значення нової цільової функції; формування нового покоління; перевірка виконання умов зупинки. Для вирішення поставленої задачі побудови мережі розглянемо інтерактивний метод побудови. Інтерактивний означає взаємодію, тобто у режимі бесіди користувач обирає розміщення елементів мережі та зв’язків між ними. При використанні даного методу з’являються наступні переваги: можливість перебудови мережі у випадку необхідності переміщення елементу мережі; використання самостійного пошуку оптимального варіанту мережі для вибору оптимального. 1.4 Постановка мети та задач дослідження За результатами аналізу проблеми структурно-топологічної оптимізації комп’ютерних мереж роботизованих систем були виділені такі основні задачі: розміщення комутаторів, роботизованих елементів та обладнання керування роботами; визначення параметрів комунікаційного обладнання та каналів зв'язку; вибору технології функціонування. У процесі вирішення деяких завдань структурно-топологічної оптимізації використовується нормативний підхід, який полягає у тому, що кількість комунікаційного обладнання та роботизованих елементів мережі визначається виходячи з затверджених нормативів. Даний підхід не враховує територіальне розташування та особливості елементів мережі, інших факторів. Аналіз завдань структурно-топологічної оптимізації комп’ютерних мереж роботизованих систем показав, що більшість з них відноситься до класу комбінаторних [13] та методи їх вирішення поділяють на: комбінаторні, відсікання [14] і наближені. У комбінаторних методах проводиться перебір варіантів топологічних структур. Часова складність більшості методів цієї групи має порядок від  до  (де n кількість можливих розміщень елементів системи; m кількість елементів системи). Але у наш час використання такого методу обмежує область застосування системами з відносно невеликим кількістю елементів.Наближені методи не знаходять широкого застосування в зв'язку з тим, що реалізація є складною та вони дозволяють лише наближено знаходити необхідні параметри. Характерною особливістю завдань структурно-топологічної оптимізації комп’ютерних мереж роботизованих систем є їх багатокритеріальність. Це ускладнює розробку формальних методів їх вирішення. Однією з основних є завдання вибору сукупності критеріїв оптимальності, для максимізації ефектів від їх функціонування і мінімізацію витрат на модернізацію. Зазвичай у якості єдиного критерію при вирішенні більшості завдань використовують вартісний критерій, та іноді використовують оперативність, живучість або надійність. Багатокритеріальні задачі можна спростити, якщо визначити основний критерій, а інші критерії використовувати у якості обмежень. Через неповну визначеність вихідних даних, високу обчислювальну складність методів вирішення, багатокритеріальність, а також наявність специфічних умов і обмежень завдання структурно-топологічної оптимізації комп’ютерних мереж роботизованих систем відносять до малоструктурованих. Для завдань такого виду оптимальними виявляються інтерактивні технології рішення, які дозволяють об’єднати найбільш ефективні математичні методи з досвідом і знаннями проектувальника або особи, яка приймає рішення. Такі технології реалізуються на основі систем підтримки прийняття управлінських або проектних рішень Decision Support System. Cистема підтримки прийняття рішень призначена для підтримки багатокритеріальних рішень у складному інформаційному середовищі та вирішує два основні завдання: вибір найкращого рішення з множини можливих (оптимізація) та впорядкування можливих рішень за бажаністю (ранжування) [15]. Актуальність теми визначається тим, що незважаючи на численні публікації, присвячені вирішенню проблеми структурно-топологічної оптимізації комп’ютерних мереж роботизованих систем, ця проблема ще далеко не вирішена і вимагає подальшого дослідження. З огляду на це, метою магістерської роботи є розробка засобів математичного та програмного забезпечення для структурно-топологічної оптимізації комп’ютерних мереж роботизованих систем. Для досягнення поставленої мети необхідно: обрати та удосконалити метод структурно-топологічної оптимізації централізованих комп’ютерних мереж роботизованих систем; розробити програмний засіб для вирішення завдання структурно-топологічної оптимізації комп’ютерних мереж роботизованих систем; провести дослідження ефективності методів оптимізації мереж. 1.5 Висновки до 1 розділу У ході аналізу комп’ютерних мереж у складі роботизованих систем визначено, що комп’ютерні мережі можуть складатись з деякої кількості комп’ютеризованих елементів (комп’ютерів, серверів, мережевих адаптерів тощо) і забезпечують обмін файлами між роботами, використання загальних ресурсів та надають можливість зручного керування роботизованими елементами. Для вирішення завдання топологічної оптимізації виробництва розглянуті особливості мереж різних типів, а локальні централізовані мережі обрані у якості базових. У процесі аналізу існуючих топологій була обрана деревовидна топологія через її переваги, серед яких: простота додавання нових вузлів; зручність управління; проста у масштабуванні; простота ідентифікації конкретного фрагменту мережі, а також можливість підключення до більшої мережі. Розглянуті методи побудови структури мережі: покоординатної оптимізації, метод кластеризації k-means, метод пошуку з заборонами Tabu Search. Проаналізувавши переваги та недоліки даних методів був обраний метод кластеризації, через те, що він простий у використанні, та має найменший час розрахунку варіанту розміщення елементів мережі серед зазначених методів. Як доповнення обраний інтерактивний метод побудови топологічної структури мережі, який дозволяє користувачеві самостійно проектувати топологію мережі та визначати вартість мережі з використанням різного обладнання. РОЗДІЛ 2 МАТЕМАТИЧНЕ ЗАБЕЗПЕЧЕННЯ ЗАДАЧІ СТРУКТУРНО-ТОПОЛОГІЧНОЇ ОПТИМІЗАЦІЇ КОМП’ЮТЕРНИХ МЕРЕЖ РОБОТИЗОВАНИХ СИСТЕМ Зазвичай задача проектування залежить від масштабних характеристик мережі, тому завдання проектування структури комп'ютерної мережі роботизовані системи є складним, бо при проектуванні мережі такого масштабу необхідно враховувати велику кількість параметрів: швидкість передачі даних, вартість каналів зв'язку, вартість комунікаційного обладнання, характеристики комунікаційних пристроїв, вимоги абонентів мережі до пропускних здібностей ліній зв'язку, вимоги до надійності мережі і до затримки передачі пакетів даних. 2.1 Постановка задачі топологічної оптимізації мереж Аналіз сучасного стану проблеми структурно-топологічної оптимізації комп’ютерних мереж роботизованих системи показав, що до теперішнього часу відсутній її формалізований комплексний опис з урахуванням структурних, топологічних, параметричних особливостей. Таким чином, в загальному вигляді задачу структурно-топологічної оптимізації комп’ютерної мережі роботизовані системи можна розглядати як комплекс завдань, що виникають при необхідності структурних, топологічних або параметричних змін у зв'язку зі змінами характеристик користувачів, розширенням множини функціональних завдань, вдосконаленням елементної бази та технологій, у рівнянні (2.1) Task = {Taski}, i = 1,6, (2.1) де Task1 – вибір принципів побудови; Task2 – реінжиніринг структури системи; Task3 – реінжиніринг топології; Task4 – визначення параметрів елементів і зв’язків мережі; Task5 – реінжиніринг технології функціонування; Task6 – оцінка ефективності P(S) і вибір кращого варіанта реінжинірингу  .На кожному етапі вирішення задач необхідно провести аналіз і дослідження задачі, після чого необхідно розробити алгоритм для її вирішення, далі йде програмоване або математичне вирішення задачі та аналіз результатів вирішення задачі [16]. 2.2 Математична модель задачі топологічної оптимізації мереж за вартісним критерієм Комп’ютерна мережа роботизованої системи складається з великої кількості комунікаційного обладнання, роботів та керувальних елементів мережі, які вимагають постійного контролю. Протягом усього життєвого циклу необхідно проводити оптимізацію та модернізацію окремих ділянок мережі або перепроектування всієї структури мережі. Завдання перепроектування структури корпоративної мережі складне і включає обробку багатьох параметрів і особливостей мережі, з урахуванням кількості виділених на даному етапі матеріальних засобів і ресурсів [16]. У загальному випадку життєвий цикл комп’ютерної мережі роботизованої системи можна описати вектором розвитку, згідно з формулою (2.2): , (2.2) де – початкова структура мережі; – кінцева структура мережі; Q – кількість етапів життєвого циклу. На кожному етапі в ході структурно-топологічної оптимізації структури мережі виділяють статичний і модифікований фрагменти мережі. Статичні фрагменти відповідають критерію оптимальності на даному етапі і не потребують перепроектування. А модифікований фрагмент не відповідає критерію оптимальності та потребує проведення певних робіт. Виходячи зі сказаного, комп’ютерну мережу роботизованої системи можна представити у вигляді об'єднання цих фрагментів  .Далі задача зводиться до синтезу оптимальної структури модифікованого фрагмента за критерієм оптимальності згідно з формулою (2.3): , (2.3) де – вартість структури i-го фрагменту мережі, яка визначається згідно з формулою (2.4); M – кількість комутаторів;  , (2.4)де N – кількість комутаторів у і-му проектованому фрагменті; – вартість комутатора у і-му проектованому фрагменті; M – кількість роботизованих елементів, під’єднаних до j-го комутатора; – вартість кабелю за 1м;  – відстань між роботизованим елементом h та комутатором j у і-му проектованому фрагменті.При цьому повинно виконуватися обмеження, щоб витрати на топологічну оптимізацію i-го проектованого фрагменту мережі не перевищували обсягу виділених засобів згідно з формулою (2.5).  , (2.5)де  – обсяг коштів виділених на топологічну оптимізацію i-го проектованого фрагменту мережі [17].2.3 Методи топологічної оптимізації мереж Для розв’язання задачі обрано метод, що використовує повний перебір різних варіантів розміщення вузлів, методи покоординатної оптимізації, кластеризації та метод Tabu Search. Алгоритм покоординатної оптимізації будується на покращенні початкового варіанту через оптимізацію розміщення кожного вузла при фіксованих розміщеннях попереднього вузла (рисунок 2.1). Процедура проводиться циклічно до досягнення локального екстремуму цільової функції. Алгоритм виконання методу покоординатного покращення. Крок 1. Задати вхідні дані: точки можливого розміщення вузлів; кількість вузлів |