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

ХАРКІВСЬКИЙ ДЕРЖАВНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ

УДК 658.512.011.56: 681.324

МАТЕМАТИЧНЕ ЗАБЕЗПЕЧЕННЯ СИНТЕЗУ ТОПОЛОГІЧНИХ СТРУКТУР ТЕРИТОРІАЛЬНО РОЗПОДІЛЕНИХ ІНФОРМАЦІЙНИХ СИСТЕМ

05.13.12 - системи автоматизації проектувальних робіт

Автореферат дисертації на здобуття наукового ступеня

кандидата технічних наук

Імангулова Зульфія Аліївна

Харків 2000

Дисертацією є рукопис

математичний топологічний модель задача

Робота виконана на кафедрі системотехніки у Харківському державному технічному університеті радіоелектроніки, Міністерство освіти і науки України.

Науковий керівник кандидат технічних наук, доцент Безкоровайний Володимир Валентинович, Харківський державний технічний університет радіоелектроніки, доцент кафедри системотехніки

Офіційні опоненти: доктор технічних наук, професор, Годлевський Михайло Дмитрович, Національний технічний університет “ХПІ”, м. Харків, завідувач кафедри автоматизованих систем управління;

доктор технічних наук, професор, Нефьодов Леонід Іванович, Харківський державний технічний університет будівництва та архітектури, професор кафедри економічної кібернетики та інформатики

Провідна установа: Національний технічний університет України “КПІ”, кафедра автоматизованих систем обробки інформації та управління, Міністерство освіти і науки України, м. Київ

Захист відбудеться “17” квітня 2001 р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.02 у Харківському державному технічному університеті радіоелектроніки за адресою: 61166 м. Харків, пр. Леніна, 14.

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

Автореферат розісланий 15.03.2001 р.

Виконуючий обов'язки

вченого секретаря

спеціалізованої вченої ради С.Ю. Шабанов-Кушнаренко

Загальна характеристика роботи

Зростаючі потреби в інформаційно-обчислювальних ресурсах, нова технічна база, накопичений досвід експлуатації обчислювальних центрів та мереж ЕОМ вимагають подальшого удосконалювання організаційних форм застосування обчислювальної техніки. Одним зі шляхів вирішення цієї проблеми є створення територіально розподілених інформаційних систем (ТРІС) з використанням нових програмних та технічних розробок у галузях комп'ютерної техніки і телекомунікацій.

Проектування та побудова ТРІС є складним завданням, яке вимагає для свого вирішення великих витрат трудових, обчислювальних, матеріальних і часових ресурсів. Це приводить до необхідності розробки і використання технологій і засобів автоматизації проектування, створення систем автоматизованого проектування (САПР) таких об'єктів.

Актуальність теми. Характерною рисою ТРІС як об'єкта проектування є тісний взаємозв'язок її структурних (кількість і схема взаємозв'язку елементів) і топологічних (територіальна організація структури) параметрів, що значною мірою впливають на її вартісні і функціональні характеристики.

Задачі структурного синтезу територіально розподілених інформаційних, інформаційно-обчислювальних і телекомунікаційних систем розглядалися багатьма авторами. Значний внесок у розвиток даного напрямку дослідження внесли Артамонов Т.Г., Зайченко Ю.П., Зайченко Є.Ю., Кузьмін І.В., Максименков А.В., Петров Е.Г., Столяров Б.А., Шварц М., Янбих Г.Ф. Еттингер Б.Я., інші автори. Їхні роботи присвячені різним аспектам проектування таких систем: загальним питанням побудови мереж, моделям і методам визначення функціональних характеристик, методам синтезу топологічних структур і вивченню потенційних можливостей цих структур.

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана відповідно до плану науково-дослідних робіт Харківського державного технічного університету радіоелектроніки в рамках держбюджетної теми №107 “Розробка принципів, методології проектування і створення інформаційно-аналітичної системи підтримки прийняття рішень при керуванні соціально-економічним розвитком регіону” (№ ДР 0100U001342), що входить до координаційного плану Міністерства освіти і науки України.

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

Досягнення поставленої мети забезпечується в роботі шляхом розв'язання комплексу взаємопов'язаних задач:

- аналіз існуючих підходів до розв'язання проблеми структурного синтезу територіально розподілених систем і визначення на їхній основі принципів побудови ефективного математичного і програмного забезпечення для розв'язання задач синтезу топологічних структур ТРІС;

- розробка математичних моделей для розв'язання задач синтезу топологічних структур ТРІС з оцінкою альтернативних варіантів за показниками витрат, оперативності та живучості;

- розробка методів й алгоритмів розв'язання задач структурно-топологічного синтезу ТРІС у класі радіально-вузлових, деревоподібних та кільцевих структур, що відповідають різним наборам вимог “розмірність задачі - точність розв'язку - час рішення”;

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

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

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

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

Наукова новизна отриманих результатів. Наукова новизна результатів, отриманих у процесі виконання роботи, полягає в наступному:

- розроблено математичну модель задачі синтезу топологічних радіально-вузлових та деревоподібних структур ТРІС за критерієм вартості з одночасним визначенням місць можливого розміщення вузлів та зв'язків між абонентами, вузлами та центром (для лінійних та нелінійних залежностей вартості від продуктивності вузлів і пропускних здібностей каналів зв'язку);

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

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

- розроблена модифікація методу спрямованого перебору локальних екстремумів функції мети для розв'язання задачі синтезу радіально-вузлових топологічних структур ТРІС, що полягає у попередньому скороченні множини місць можливого розміщення вузлів;

- запропоновано модифікації методу еволюційного моделювання та їхня реалізація у вигляді генетичних алгоритмів стосовно до розв'язання задач синтезу топологій ТРІС у класах деревоподібних та кільцевих структур, що перевершують відомі методи за комплексним показником “точність - час розв'язання”;

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

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

Практичне значення отриманих результатів. Запропоновані у дисертаційній роботі методи, математичні моделі й алгоритми реалізовані у вигляді пакета програм для розв'язання задач синтезу топологічних структур ТРІС. Застосування створених засобів математичного та програмного забезпечення дозволяє за рахунок підвищення ступеня автоматизації скоротити терміни проектування, знизити витрати на розробку та створення систем, а за рахунок використання інтерактивної технології синтезу, поліпшити їхні функціональні характеристики.

Практичне значення результатів підтверджується їхнім впровадженням. Методи й алгоритми структурно-топологічної оптимізації були застосовані в АТ “Хартрон” при синтезі структури мережі збору первинної інформації в рамках розроблювальної АСУ технологічним процесом на АЕС (довідка № 42003-п / 102 від 7.07.2000 р.), а також на підприємстві “Завод ім. Малишева” - для визначення найбільш ефективної структури з'єднання мереж заводоуправління та комерційного управління з локальною обчислювальною мережею обчислювального центру у рамках розроблювальної корпоративної мережі підприємства (довідка № 41/68 від 11.10.2000 р.).

Розроблені алгоритми та пакет програм використовуються у навчальному процесі на кафедрі системотехніки Харківського державного технічного університету радіоелектроніки і включені до складу методичних вказівок до лабораторних робіт з дисципліни “Математичне та програмне забезпечення АСУ спеціального призначення” (акт впровадження від 18.10.2000 р.).

Особистий внесок здобувача. У роботах опублікованих зі співавторами особистий внесок здобувача складає: у [1] запропоновані склад та структура комплексу інтерактивного проектування топологічних структур інформаційно-обчислювальних систем (ІОС); у [2] запропоновані спосіб зниження обчислювальної складності задач оптимізації радіально-вузлових структур ІОС та алгоритми для визначення підмножин пунктів, на базі яких утворення вузлів не раціонально; у [3] розроблено генетичний алгоритм синтезу деревоподібних структур ТРІС, що дозволяє враховувати обмеження щодо числа рівнів мережі; у [4] запропоновані модифікації математичних моделей та алгоритмів оцінок кількості структурних елементів ІОС; у [5] запропоновані математичні моделі для визначення оцінок структурної живучості радіально-вузлових та деревоподібних структур ТРІС, виконана формалізація показників вартості, оперативності та живучості системи; у [7] запропонований склад математичного забезпечення для пакету програм інтерактивного проектування топології централізованих ІОС; у [8] запропоновано подальший розвиток методу синтезу структур ІОС за множиною показників ефективності.

Апробація результатів дисертації. Основні положення та результати дисертаційної роботи доповідалися та обговорювалися: на IV - VI Міжнародних конференціях “Теорія та техніка передачі, прийому та обробки інформації” (Харків - Туапсе, 1998, 1999, 2000); на III Міжнародному молодіжному форумі “Радіоелектроніка і молодь у XXI столітті” (Харків, 1999); на III Міський науково-практичній конференції “Актуальні проблеми сучасної науки у дослідженнях молодих учених Харківщини” (Харків, 2000); на семінарі “Системний аналіз, математичне моделювання та прийняття рішень у соціально-економічних та технічних системах” наукової ради НАН України з проблеми “Кібернетика” (Харків, 1999, 2000).

Публікації. За темою дисертації опубліковано 10 наукових праць, в тому числі 5 статей у виданнях, які увійшли до переліків ВАК України, та 5 публікацій у збірниках праць наукових конференцій.

Структура дисертації. Дисертація складається зі вступу, п'яти розділів основного змісту, висновків та двох додатків (на 36 с.) загальним обсягом 214 с., містить 36 ілюстрацій (на 15 с.), 9 таблиць (на 2 с.), список використаних джерел із 126 найменувань (на 11 с.).

Основний зміст роботи

У вступі обґрунтовується актуальність теми дослідження, формулюється мета та задачі роботи, її наукова новизна та практична цінність, наводяться дані про апробацію та публікацію результатів.

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

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

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

У результаті аналізу виявлено, що при синтезі ТРІС найбільш часто використовуються деревоподібні, радіально-вузлові та кільцеві структури. Ці структури є базовими для створення структур інших класів. Розглянуто методи та алгоритми синтезу деревоподібних, радіально-вузлових та кільцевих структур.

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

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

Метою створення ТРІС, є максимізація її ефективності, тобто одержання максимального ефекту від використання системи на одиницю затрачуваних ресурсів. Тому задачі синтезу ТРІС звичайно формулюються в термінах “ефект-вартість”.

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

Наявність сукупності критеріїв ефективності ТРІС визначає багатокритеріальний характер задачі синтезу її топологічної структури та значно ускладнює розробку формальних методів її розв'язання. Задача вибору оптимального розв'язку у багатокритеріальній ситуації полягає у ранжируванні альтернатив за множиною часткових (локальних) критеріїв.

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

Труднощі, пов'язані з побудовою великих ТРІС, викликають необхідність розв'язання проблеми автоматизації дослідження та проектування подібних систем. У зв'язку з цим, перспективним є створення інтерактивних САПР ТРІС. Обрані принципи побудови математичного та програмного забезпечення для розв'язання задач автоматизації проектування ТРІС, передбачають створення “відкритих” банків моделей, методів, програмних засобів та їхнє інтерактивне настроювання на розв'язання конкретної задачі, виходячи з умов “розмірність задачі - точність розв'язку - час розв'язання ”.

У третьому розділі розглядається постановка та математична модель задачі структурно-топологічного синтезу ТРІС.

Задача синтезу топологічної структури централізованої ТРІС може бути сформульована таким чином. Задані: множина абонентів , їх територіальне розміщення; місце розташування хост-ЕОМ; інтенсивності потоків запитів кожного абонента ; - упорядкована множина дискретних значень пропускних здатностей каналів зв'язку; - упорядкована множина дискретних значень продуктивностей вузлів; - продуктивність хост-ЕОМ; - середня довжина запитів i-го абонента; - середня довжина відповідей на запити абонентів; - вартість одиниці продуктивності вузла; - вартість одиниці пропускної здатності каналу зв'язку.

Прийняті наступні припущення: вузли можуть розміщуватися тільки в місцях розташування абонентів; хост-ЕОМ має фіксовану вартість та продуктивність, достатню для обробки повідомлень від усіх абонентів.

Необхідно визначити: кількість вузлів , місця їхнього розміщення (де - множина місць можливого розміщення вузлів), списки абонентів, що обслуговуються кожним із вузлів мережі .

При цьому сумарна вартість мережі повинна бути мінімальною.

(1)

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

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

Структурні обмеження:

- кожен пункт мережі повинний бути з'єднаний хоча б із ще одним пунктом (вузлом чи хост-ЕОМ)

(2)

- загальна кількість зв'язків у мережі

(3)

- вузли можуть бути підключені тільки до хост-ЕОМ і не можуть бути зв'язані між собою

(4)

Для ТРІС з радіально-вузловою структурою потрібно, щоб виконувалися обмеження (2) - (4), а для ТРІС з деревоподібною структурою - тільки обмеження (2) та (3).

Оперативність (час відповіді) системи визначається співвідношенням

(5)

де - середній час (затримка) передачі повідомлень від абонентів до хост-ЕОМ; - середній час обробки повідомлень у хост-ЕОМ; - середній час передачі відповідей від хост-ЕОМ абонентам.

Для моделювання процесів обробки запитів користувачів ТРІС використано апарат теорії масового обслуговування. Формалізацію показника оперативності системи виконано у вигляді моделі оцінки середнього часу очікування відповідей абонентами системи.

Для оцінки живучості структури ТРІС вибрано показник, що визначає середнє число абонентів, які залишаться приєднаними до хост-ЕОМ при одиночних виходах з ладу каналів зв'язку чи пунктів мережі. При цьому прийняті наступні допущення: імовірність того, що ушкоджено який-небудь канал зв'язку ТРІС чи вийшло з ладу обладнання якого-небудь пункта ідентична імовірності того, що ушкоджено будь-який інший канал зв'язку або вийшло з ладу обладнання будь-якого іншого пункту мережі; відновлення працездатності відсутнє, ушкоджений канал зв'язку або пункт ТРІС залишається непрацездатним; при виході з ладу обладнання хост-ЕОМ відновлення виконується негайно; в один момент часу може вийти з ладу тільки один канал зв'язку або пункт мережі, випадки, коли одночасно виявляються зруйнованими кілька каналів зв'язку чи пунктів не розглядаються.

У роботі передбачається, що абоненти ТРІС розташовані на нульовому рівні, а хост-ЕОМ - на найвищому рівні структури мережі.

Позначимо через - кількість пунктів, які будуть від'єднанні від хост-ЕОМ при виході з ладу обладнання i-го пункту (вузла чи абонента), який розташовано на q-му рівні; - кількість пунктів, що будуть від'єднанні від хост-ЕОМ при ушкодженні каналу зв'язку між i-м та j-м пунктами ТРІС.

З урахуванням цього

(6)

де , якщо j-й пункт розташований на s-му рівні, 0 - у протилежному випадку.

Кількість пунктів, від'єднанних від хост-ЕОМ при ушкодженні каналу зв'язку між i-м та j-м пунктами мережі визначається в такий спосіб

(7)

Умова вказує на те, що пункт i знаходиться на нижчому рівні щодо пункту j.

Тоді живучість ТРІС при одиночних виходах з ладу обладнання пунктів визначається за допомогою виразу

(8)

Живучість ТРІС при одиночних ушкодженнях каналів зв'язку визначається в такий спосіб

(9)

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

Оцінку якості топологічної структури ТРІС пропонується проводити за допомогою узагальненого критерію, побудованого на основі адитивної корисності

(10)

де - корисність (цінність) варіанта ; g - кількість показників ефективності (часткових критеріїв); - коефіцієнт, що характеризує ступінь важливості i-го часткового критерію, при цьому ; - значення функції корисності варіанта структури y по i-му частковому критерію.

Функція корисності часткових критеріїв визначається в такий спосіб

(11)

де - значення i-го часткового; - найгірше та найкраще значення критерію , - показник нелінійності.

Якщо відомі значення усіх функцій корисності , та визначено вектор переваг , то вибір для адитивної схеми (10) може бути зведений до задачі оптимізації виду

(12)

Ця задача може бути розв'язана за допомогою методів структурно-топологічної оптимізації систем.

Математична модель задачі синтезу кільцевих структур ТРІС може бути представлена у наступному вигляді

(13)

де - вартість i-го пункту мережі; - вартість каналу зв'язку між пунктами i та j мережі; n - кількість абонентів; =1, якщо пункт i з'єднано з пунктом j, 0 - у протилежному випадку.

Структурне обмеження вказує на те, що коефіцієнт зв'язності кільцевих структур дорівнює 2.

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

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

При цьому , де - підмножина пунктів, розміщення вузлів у яких може зменшити витрати на ТРІС.

Один із запропонованих способів визначення пунктів, що належать підмножині , полягає у побудові стягуючого дерева (СД). Підмножину утворюють висячі вершини СД. Ідея алгоритму синтезу СД та виділення підмножини абонентів полягає в тому, що СД будується від найбільш віддалених вершин до центру. Вершини, що знаходяться далі від центра, приєднуються до тих, що розташовані ближче до центра. Для цього вибираємо довільну вершину i та приєднуємо її до центра. Потім знаходимо вершину j, найближчу до обраної. Якщо (0 - номер, що відповідає центру) та виконується умова (відстань від центра до вершин i та j відповідно), то переприєднуємо i до j. Процедура повторюється до тих пір, поки не будуть перебрані усі вершини.

Для побудови СД мінімальної вартості та виділення підмножини використані алгоритми також Прима та Краскала.

Суть алгоритму виділення підмножини пунктів , на основі списку “найближчих сусідів” кожного абонента полягає в наступному. Для кожного з n абонентів мережі формується список з В його “найближчих сусідів”, де В - розмір області “найближчих сусідів”. Абонент i може бути включений до списку “найближчих сусідів” абонента j у тому випадку, якщо виконуються наступні умови: відстань від центра до абонента i повинна бути меншою, ніж від центра до абонента j (); відстань між абонентами i та j повинна бути меншою, ніж відстань від центра до абонента j (). Якщо ці обмеження не виконуються, то абонент i не включається до списку “найближчих сусідів” абонента j. Потім для кожного абонента j мережі обчислюється частота його появи у списках “найближчих сусідів” ( ) та визначаємо як множину пунктів, для яких .

Ефективність алгоритму значною мірою залежить від вибору розміру області “найближчих сусідів” В. Шляхом експериментальних досліджень було виявлено, що найкращим для даного алгоритму є значення .

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

Оцінка точності запропонованих алгоритмів показала, що максимальна похибка, внесена цими алгоритмами, не перевищує 3%.

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

Для синтезу багаторівневих та кільцевих структур у роботі пропонується модифікація методу еволюційного моделювання, реалізована у вигляді генетичного алгоритму (ГА). Відмінною рисою ГА синтезу централізованих структур є те, що він дозволяє враховувати обмеження на максимальне число рівнів мережі, тобто синтезувати як ТРІС з радіально-вузловою структурою, так і деревоподібні мережі з довільним числом рівнів.

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

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

Другою метою було дослідження власне, обчислювальної ефективності розробленого генетичного алгоритму. Дослідження показали, що на ЕОМ на базі процесора Pentium II з тактовою частотою 350 МГц час синтезу деревоподібних структур розмірністю 25 пунктів складає в середньому 1 хв. 23 с., а структур розмірністю 50 пунктів - 2 хв. 45 с., при цьому середня похибка рішень не перевищує 2%.

Оцінка ефективності алгоритму синтезу кільцевих структур показала, що він перевершує по точності n-прохідний алгоритм “йди в найближчий” у середньому на 20%, а n-прохідний алгоритми формування опуклої оболонки пунктів - на 6%. При цьому час синтезу на ЕОМ із процесором Pentium II з тактовою частотою 350 МГц для ТРІС розмірністю 30 абонентів складає в середньому 1 хв. 13 с., а для ТРІС розмірністю 50 абонентів - 2 хв. 30 с.

У даному розділі розглянуто також математичні моделі та процедури обчислення оцінок оптимального числа вузлів у радіально-вузлових структурах, проведено аналіз їхньої точності. Експериментальні дослідження показали, що похибка визначення кількості вузлів за допомогою запропонованих оцінок не перевищує трьох вузлів. Застосування оцінок кількості структурних елементів ТРІС дозволяє знизити складність задач структурного синтезу таких систем та здійснювати вибір ефективних методів їхнього розв'язання.

П'ятий розділ присвячений опису можливостей розробленого пакету програм для інтерактивного проектування топологічних структур ТРІС NWDesigner, а також апробації розроблених засобів математичного та програмного забезпечення на прикладі розв'язання практичної задачі.

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

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

Висновки

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

Декомпозиція мети дослідження дозволила сформулювати множину взаємопов'язаних задач, у результаті вирішення яких:

1. Знайшли подальший розвиток принципи побудови математичного та програмного забезпечення для автоматизації проектування топологічних структур ТРІС у частині створення банків моделей, методів, алгоритмів, програмних засобів та їхнього інтерактивного настроювання для вибору найбільш ефективного методу розв'язання конкретної задачі.

2. Розроблено математичну модель задачі синтезу топологічних радіально-вузлових та деревоподібних структур ТРІС за критерієм вартості з одночасним визначенням місць можливого розміщення вузлів та зв'язків між абонентами, вузлами та центром (для лінійних та нелінійних залежностей вартості від продуктивності вузлів і пропускних здібностей каналів зв'язку);

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

4. Вперше запропоновано математичні моделі для визначення оцінок структурної живучості не надлишкових (радіально-вузлових та деревоподібних) структур ТРІС, що дозволяють оцінювати імовірність зв'язності системи шляхом визначення середнього числа абонентів, що залишаться приєднаними до хост-ЕОМ при одиночних ушкодженнях каналів зв'язку або обладнання вузлів системи.

5. Запропоновано підхід та розроблено алгоритми зниження обчислювальної складності задачі топологічного синтезу ТРІС шляхом виключення з множини місць можливого розташування вузлів пунктів, у яких вузли розміщувати нераціонально. На цій основі розроблена модифікація методу спрямованого перебору локальних екстремумів функції мети для розв'язання задачі синтезу радіально-вузлових топологічних структур ТРІС, яка дозволяє істотно скоротити час розв`язання практично без втрати його точності.

6. Запропоновано модифікації методу еволюційного моделювання та їхні реалізації у вигляді ГА стосовно до синтезу топологій ТРІС у класах деревоподібних та кільцевих структур, які перевершують відомі методи за комплексним показником “точність-час розв`язання”. Алгоритм синтезу деревоподібних структур дозволяє враховувати обмеження по числу рівнів та одержувати як радіально-вузлові, так і деревоподібні топології з заданою кількістю рівнів.

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

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

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

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

Список опублікованих праць за темою дисертації

1. Бескоровайный В.В., Имангулова З.А., Стадник И.А. Комплекс интерактивного проектирования топологических структур ИВС // Вестник ХГТУ. 1999. № 1(5). С. 33 - 36.

2. Бескоровайный В.В., Имангулова З.А. Алгоритмы оптимизации топологии ИВС на множестве радиально-узловых структур // Радиоэлектроника и информатика. 2000. № 2. С. 100-104.

3. Бескоровайный В.В., Имангулова З.А. Генетический алгоритм структурной оптимизации централизованных многоуровневых ИВС // Новые решения в современных технологиях: Вестник Харьковкого государственного политехнического университета. Вып. 83. Харьков: ХГПУ. 2000. С. 4-7.

4. Бескоровайный В.В., Имангулова З.А. Оценка количества структурных элементов при синтезе ИВС // Вестник ХГТУ. 2000. № 1(7). С. 199-204.

Бескоровайный В.В., Имангулова З.А. Математическая модель задачи синтеза топологии централизованных информационных сетей // Новые решения в современных технологиях: Вестник Харьковского государственного политехнического университета. Вып. 118. Харьков: ХГПУ. 2000. С. 11-14.

Имангулова З.А. Методы решения задачи структурного синтеза ИВС в условиях многокритериальности // Вісник Харківського університету. 2000. № 456. С. 130-133.

7. Бескоровайный В.В., Имангулова З.А. Математическое обеспечение интерактивной технологии структурно-топологического проектирования ИВС // 4-я Междунар. конф. “Теория и техника передачи, приема и обработки информации”. Научные труды. Харьков: ХТУРЭ, 1998. С. 355.

8. Бескоровайный В.В., Имангулова З.А. Реинжиниринг топологических структур территориально распределенных систем // 5-я Междунар. конф. “Теория и техника передачи, приема и обработки информации”. Научные труды. Харьков: ХТУРЭ, 1999. С. 384-386.

9. Имангулова З.А. Алгоритмы топологической оптимизации ИВС в классе радиально-узловых структур // 3-й Міжнародний молодіжний форум “Радіоелектроніка і молодь у XXI ст. ”. Доповіді. Харків: ХТУРЕ, 1999. С. 84-87.

10. Имангулова З.А. Математическое и программное обеспечение автоматизированного проектирования топологических структур ИВС // 6-я Междунар. конф. “Теория и техника передачи, приема и обработки информации”. Сб. научных трудов. Харьков: ХТУРЭ, 2000. С. 238-240.

Анотація

Імангулова З.А. Математичне забезпечення синтезу топологічних структур територіально розподілених інформаційних систем. - Рукопис.

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

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

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

Аннотация

Имангулова З.А. Математическое обеспечение синтеза топологических структур территориально распределенных информационных систем. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.12 - системы автоматизации проектных работ. - Харьковский государственный технический университет радиоэлектроники, Харьков, 2000.

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

Проведен анализ существующих подходов к решению проблемы структурного синтеза территориально распределенных систем. Этот анализ позволил определить принципы построения эффективного математического и программного обеспечения для решения задач синтеза топологических структур ТРИС.

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

Впервые предложены математические модели для определения оценок структурной живучести радиально-узловых и древовидных структур ТРИС, позволяющие оценивать вероятность связности системы путем определения среднего числа абонентов, которые останутся подсоединенными к хост-ЭВМ при одиночных повреждениях каналов связи или оборудования узлов системы. Предложенные оценки могут быть использованы для анализа степени работоспособности системы в целом, путем определения процента абонентов подключенных к системе при выходе из строя отдельных ее элементов или связей.

Предложен подход и разработаны алгоритмы снижения вычислительной сложности задачи топологического синтеза ТРИС. Суть подхода заключается в сокращении множества мест размещения узлов за счет исключения из него подмножества пунктов, в которых узлы размещать нерационально. На этой основе разработана модификация метода направленного перебора локальных экстремумов функции цели для решения задачи синтеза радиально-узловых топологических структур ТРИС, что позволяет существенно сократить время решения практически без потери его точности.

Предложены модификации метода эволюционного моделирования и их реализации в виде генетических алгоритмов применительно к решению задач синтеза топологий ТРИС в классах древовидных и кольцевых структур, превосходящие известные методы по комплексному показателю “точность-время решения”. Алгоритм синтеза древовидных структур позволяет учитывать ограничение на число уровней и получать как радиально-узловые, так и древовидные топологии с заданным числом уровней.

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

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

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

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

Abstract

Imangulova Z.A. Mathematical bases of the synthesis of topological structures of space-distributed information systems. - Manuscript.

Thesis for a candidate of technical sciences' degree on the speciality 05.13.12. - System of Automatization of Design Works. Kharkiv State Technical University of Radio Electronics, Kharkiv, 2000.

The thesis is devoted to the development of mathematical bases and software for automatization processes of designing topological structures of space-distributed information systems (SDIS).The mathematical model of the problem of synthesizing of radial, nodal, and tree topological structures is improved. Formalizing the system's cost, flexibility and tenacity of life indexes is realized. Mathematical models to determine estimations of structural tenacity of SDIS radial, nodal and tree structures as a result of single damages of communication channels and equipment of the system nodes are proposed for the first time. The modification of the method of directed exhaustion of local extremums of the purpose function to solve the problem of synthesizing SDIS radial and nodal topological structures is developed. Modifications of the method of evolutional modeling and their realization in the form of genetic algorithms as applied to the solution of problem synthesizing SDIS topologies in the classes of tree and ring structures are suggested. The method of multifactor estimation and selection of variants of SDIS topological structures on the bases of additive usefulness theory is developed. A package of programs of interactive synthesis SDIS topology in the class of radial, nodal and ring structures is developed.

Key words: topological structure, synthesis, effectiveness criterion, mathematical model, algorithm, information system.

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

...