Українська державна академія залізничного транспорту

(61050, м. Харків, майд. Фейєрбаха, 7)

Осієвський Сергій Валерійович

УДК 681.324

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

05.12.02 "Телекомунікаційні системи та мережі"

АВТОРЕФЕРАТ

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

Харків – 2003

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

Робота виконана в Харківському військовому університеті

Науковий керівник: | кандидат технічних наук професор Соколов Сергій Олексійович, начальник кафедри „Обчислювальних систем та мереж”

Харківського військового університету Міністерства оборони України, м. Харків.

Офіційні опоненти: - | доктор технічних наук професор
Загарій Геннадій Іванович,
зав. кафедрою "Автоматики та комп'ютерних систем управління" Української державної академії залізничного транспорту Міністерства транспорту України, м. Харків.

- | кандидат технічних наук, старший науковий співробітник
Кучук Георгій Анатолійович, начальник науково-дослідного відділу ІОЦ Харківського військового університету Міністерства оборони України, м. Харків.

Провідна установа | Харківський національний університет радіоелектроніки, кафедра “Телекомунікаційних систем”, Міністерство освіти і науки України,
м. Харків.

Захист відбудеться “24” червня 2003 р. о “15” годині на засіданні спеціалізованої вченої ради Д .820.01 при Українській державній академії залізничного транспорту за адресою:

Україна, 61050, м. Харків, майдан Фейєрбаха, 7.

З дисертацією можна ознайомитись в бібліотеці академії.

Відгук на автореферат просимо надсилати за адресою:
Україна, 61050, м. Харків, майдан Свободи, 6.

Автореферат розісланий “22” травня 2003 р.

Вчений секретар

спеціалізованої вченої ради

к.т.н., доцент М.В. Книгавко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Стрімкий розвиток засобів зв'язку та обчислювальної техніки, а також наявність можливості їхньої взаємної інтеграції сприяли появі однієї з найскладніших кібернетичних систем – інтелектуальної мережі (ІМ), яка є логічним розвитком існуючих телекомунікаційних мереж (ТМ). Інтелектуальні мережі знайшли своє застосування в таких розвинутих країнах, як США, Японія, Італія, Франція, Німеччина. Українськими науковцями Стєкловим В.К., Беркман Л.Н. запропонована концепція поетапного впровадження функціональних можливостей інтелектуальної мережі в Україні. Відповідно до цієї концепції на першому етапі реалізації платформи ІМ в Україні на основі існуючої телефонної мережі загального користування передбачаються ряд системно-технічних рішень:

– охоплення новими послугами максимально можливої кількості абонентів;

– мінімізація модернізації устаткування, що знаходиться в експлуатації;

– впровадження цифрової техніки комутації та передачі інформації;

– впровадження перспективних засобів обробки інформації.

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

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

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

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

Існує ряд робіт авторів Ліпаєва В.В., Нікітіна А.І., Колосова Л.В. та ін., у яких розкриті положення теорії планування та диспетчеризації процесів, що дозволяють виконати попередню підготовку робіт, реалізація яких вимагає багатопрограмного режиму роботи однопроцесорної або багатопроцесорної обчислювальної системи. Однак, дослідження в області теорії побудови ефективних систем планування обробки запитів абонентів і транзакцій ще не дали практичних алгоритмів і програм, що дозволяють із незначними накладними витратами застосовувати їх для створення програмних продуктів і їхньої реалізації в інформаційних обчислювальних та телекомунікаційних мережах. Складність задач які вирішуються у цьому напрямку, обумовлена тим, що більшість з них носить комбінаторний характер, характеризується експоненціальною часовою складністю і відноситься до класу NP-повних задач, а їх рішення засобами ЕОТ наштовхується на труднощі пов'язані з великими витратами машинного часу та пам'яті. Ще однією перешкодою при рішенні цієї задачі є відсутність достатньо адекватних математичних моделей процесів обробки запитів абонентів у МБД ТМ. Невідповідність теоретичних (класичних) моделей і реальних процесів обробки запитів у складних системах найчастіше обумовлена тим, що в класичних моделях, як правило, ігноруються істотні розходження між кількістю очікуваних запитів та реальним робочим навантаженням МБД ТМ. Враховуючи наявність протиріччя між постійним зростанням кількості абонентів і об’ємом послуг які надаються абонентам та неспроможністю телекомунікаційних систем оперативно і якісно забезпечити потрібну абонентам кількість послуг з метою зменшення середнього часу реалізації запитів абонентів і транзакцій доцільно розробити засоби планування реалізації робочого навантаження. Таким чином забезпечується побудова такого графіку реалізації транзакцій та запитів абонентів, що дозволяє виключити вплив складових робочого навантаження один на одного. При цьому сам процес формування графіку реалізації здійснюється в реальному масштабі часу.

Зв'язок з науковими програмами, планами, темами. Дослідження в дисертаційній роботі проводилися у відповідності з наступними нормативними актами:

1. Концепцією розвитку Єдиної національної системи зв'язку України до 2010 р. Четверта редакція.

2. Завданнями Національної програми інформатизації України на 2000 – 2005 р.

3. Законом України “Про зв'язок”.

4. Планами НДР МО України, ХВУ.

Основні результати дисертаційної роботи використані в 3-х науково-дослідних роботах: шифри “Куб” (звіт №3816, інв. №13076), “Тор” (звіт №3822, інв. №13078), “Мрія” (звіт №3824, інв. №13077).

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

Відповідно до поставленої мети необхідно вирішити наступні задачі досліджень:

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

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

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

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

5. Розробити алгоритми реалізації розроблених методів.

Об'єктом досліджень є підсистема управління реалізацією робочого навантаження в МБД ТМ.

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

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

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

1. На основі вивчення й аналізу застосування рангового підходу до рішення задач дискретної оптимізації вперше розроблено метод рішення задачі пошуку найкоротшого гамільтонового шляху на основі рангового підходу, що дає обчислювальну складність рішення задачі в гіршому випадку O(cn3), при с=const. Тим самим досягається рішення задачі в масштабі реального часу. Застосування методу дозволяє:

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

- зменшити час рішення задачі пошуку найкоротшого гамільтонового шляху в 24 рази порівняно з існуючими методами.

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

3. Вдосконалено спосіб отримання оцінки операторів ММД застосування якого дозволяє спростити семантичну складність запитів абонентів, сформувати вихідні дані для алгоритмів побудови планів реалізації запитів абонентів і транзакцій у МБД ТМ.

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

Практична значимість результатів полягає в наступному:

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

– розроблено алгоритм формування графіку реалізації запитів користувачів і транзакцій, що може бути інтегрованим як у статичні так і динамічні системи обробки даних та забезпечує рішення задачі формування графіка реалізації запитів користувачів і транзакцій при числі операторів ММД 3<n<100 за час Тнеобх.=1хв., що збільшує кількість операторів ММД, які реалізуються одночасно, у 3 рази в порівнянні з існуючими методами;

– результати досліджень впровадженні при виконанні дослідно - конструкторських робіт та науково-дослідних роботах НТ СКБ “Полісвіт” (акт про впровадження від 09.01.03 р.), навчальному процесі Харківського військового університету (акт про впровадження від 03.03.03 р.), навчальному процесі Харківського державного економічного університету (акт про впровадження від 21.02.03 р.).

Особистий внесок здобувача. Всі положення та результати, що виносяться на захист, отримані автором самостійно. Внесок здобувача в публікації, виконані в співавторстві, полягає в наступному: у роботі 1 автором на основі класифікації алгоритмів модифікації узагальненої процедури А0 проведена перевірка правильності запропонованих стратегій відсікання неперспективних варіантів пошуку рішення задач з використанням рангового підходу; у роботі 2 автором запропоновано спосіб визначення мінімально віддаленої вершини та проведено оцінку ефективності її використання; у роботі 3 запропоновано стратегії виділення коридорів зон пошуку рішення NP-повних задач; у роботі [6] автором запропоновано алгоритм пошуку найкоротшого гамільтонового шляху для рішення задачі диспетчеризації множини запитів користувачів; у роботі [7] автором запропоновано метод виявлення конфліктів та протиріч при обслуговуванні множини запитів користувачів; у роботі [8] автором запропоновано паралельний алгоритм пошуку найкоротшого гамільтонового шляху в довільних реберно-зважених графах.

Апробація результатів дисертації. Основні положення дисертації доповідалися та обговорювалися на:

- II Всеукраїнській науково – технічній конференції “Актуальні проблеми та перспективи розвитку фінансово-кредитної системи України”, м. Харків: 2002 р;

- 15 Міжнародній школі – семінарі "Перспективні системи управління на залізничному, промисловому і міському транспорті", м. Алушта: 2002 р;

- міжнародній науково-технічній конференції "Проблеми інформатики і моделювання", м. Харків: 2002 р;

- науково-технічних семінарах “Синтез, обработка и отображение информационных моделей” Наукової ради НАНУ по проблемі “Теоретическая электротехника и электронное моделирование”, м. Харків: 2000 – 2002 р.

- науково – технічних семінарах кафедри “Обчислювальних систем та мереж” ХВУ, м. Харків: 2000-2003 р.

Публікації. Основні положення дисертаційної роботи опубліковані в 11 наукових працях, які включають 5 наукових статей, 3 тези і матеріали всеукраїнських й міжнародних конференцій та семінарів, 3 звіти по науково-дослідних роботах.

Структура роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, списку використаних джерел і восьми додатків. Повний обсяг роботи складає 224 сторінки машинописного тексту, з яких обсяг основного тексту складає 161 сторінку; додатки, список використаних джерел, малюнки і таблиці 63 сторінки. Робота ілюстрована малюнками, приведено 6 таблиць. Список використаних джерел складається з 110 найменувань.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

У першому розділі наведені результати аналізу особливостей процесу реалізації робочого навантаження в мережній базі даних телекомунікаційної мережі. В результаті аналізу було визначено, що наявність запитів абонентів і транзакцій до МБД ТМ, за логічними умовами яких, виникає необхідність обробки даних у пересічних областях пошуку, різко знижує відповідність структур зберігання інформації вимогам цілісності даних. Це, в свою чергу, знижує якість обслуговування абонентів та збільшує часові затримки. Такий висновок підтверджується проведеною оцінкою існуючих способів і засобів рішення задачі формування графіка реалізації множини запитів абонентів і транзакцій. Показано, що існуючі методи не забезпечують здатність підсистеми управління реалізації робочого навантаження в МБД ТМ здійснювати обробку множини запитів абонентів у реальному масштабі часу для кількості запитів n>35. Визначено, що досягти необхідного результату в оперативності та якості обслуговування запитів абонентів можливо завдяки оптимальному плануванню реалізації робочого навантаження в МБД ТМ. Виходячи з вказаних недоліків та поставленої мети, обґрунтований показник ефективності рішення задачі формування графіка реалізації запитів абонентів та транзакцій:

, (1)

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

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

(2)

де Рдоп – мінімально допустиме значення ймовірності своєчасного рішення задачі.

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

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

З метою розробки алгоритмів пошуку найкоротших гамільтонових шляхів усім можливим станам досліджуваної системи поставлено у відповідність граф G(V,E), де - вершини, що відповідають можливим станам системи, Е – дуги, що відповідають переходам між відповідними станами системи. Для визначення напрямків розгалужень у графі G(V,E) виконано перехід до простору з n(n-1) станами. Для цього кожному з n станів поставлено у відповідність ще (n-1) стан, що характеризує спосіб досягнення наступного стану з множини {1,2.....n}. При цьому в якості стану, що добавляється визначено ранг шляху в графі G(V,E). Такий простір станів можна представити у вигляді стягнутого дерева всіх шляхів відображеного графом D (рис. 1). З метою скорочення алгоритмічної та обчислювальної складності розроблених алгоритмів пошуку найкоротшого гамільтонового шляху введено процедуру А, що дозволяє відсікати безперспективні шляхи розгалуження дерева всіх шляхів.

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

, (3)

де (j, p) - ребро графа D, n-число різних вершин у графі D.

Виділено наступні особливості роботи процедури А:

1. Коли процедура А на кожному кроці побудувала шляхи в множині тобто, принцип оптимальності роботи процедури не порушувався і друга.

2. Коли до однієї з вершин жодного шляху побудувати не можливо.

Остання обставина можлива в двох випадках:

а) якщо граф, що аналізується неповний і до вершини р не існує шляхів рангу r=k ;

б) коли вершина р буде введена в усі шляхи попереднього рангу.

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

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

Використовуючи процедуру А, можна сформувати всі можливі множини для вершини s. Таким чином реалізується один етап виконання алгоритму А1. Оскільки один етап пошуку не здатний задовольнити потребу в рішенні задачі пошуку найкоротшого гамільтонового шляху, необхідно виконати n-етапів, де n – кількість вершин графа. В результаті роботи алгоритму А1 формуються підмножини шляхів . Якщо позначити довжину найкоротшого гамільтонового шляху в підмножинах через , то найкоротшим гамільтоновим шляхом на k-му етапі пошуку буде гамільтоновий шлях довжина якого становить

. (4)

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

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

Правило 1. Процедуру А в алгоритмах пошуку найкоротшого гамільтонового шляху можна не використовувати для тих вершин р, до яких не існує шляхів рангу r=k, оскільки існує велика ймовірність того, що в оптимальному гамільтоновому шляху вершина р на k-м місці стояти не буде. Використання даного правила дозволяє побудувати алгоритм А2. Правильність запропонованого правила підтверджена експериментальними дослідженнями.

Для реалізації введеного правила 1 формується масив В, елементами якого є відповідні значення номерів вершин j до яких на ранзі r=k шляхи побудувати не вдалося. Заповнення масиву В елементами виконується після перевірки результатів роботи процедури А на кожному із етапів у відповідності зі співвідношенням

. (5)

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

Застосування розробленого способу визначення мінімально зваженої вершини до алгоритму А1 дозволив побудувати алгоритм А3.

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

У третьому розділі проведено експериментальне дослідження розроблених алгоритмів пошуку найкоротшого гамільтонового шляху. Для об’єктивної оцінки розроблених алгоритмів обрано наступні показники ефективності:

- ймовірність своєчасного рішення задачі

; ? (6)

- кількість елементарних операцій (ЕО) сумування та порівняння;

- для оцінки якості наближених алгоритмів обрані абсолютна та відносна похибки:

, (7)

. (8)

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

- tср  - середній час рішення задачі;

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

Крім основних характеристик алгоритмів визначені вимоги кожного з алгоритмів до технічних ресурсів ЕОМ. Відповідно до стратегій дослідження алгоритмів, заснованих на ранговому підході, визначені зони, на яких виконувалися дослідження. Це пов’язано в першу чергу з заздалегідь відомим обмеженням еталонних алгоритмів на обчислювальну складність. Загальна розмірність задачі розбита на три умовно виділені зони (0-12), (13-30), (31-100). Для дослідження характеристик алгоритмів і їхньої поведінки на різних розмірностях розроблено пакет прикладних програм “Analizator”. Використовуючи необхідні значення часу циклу моделювання і відведеного (Тдоп.) часу (1, 3, 10, 30 хвилин), було визначено значення показника Р. Аналіз імовірності своєчасного рішення задачі пошуку найкоротшого гамільтонового шляху з використанням розроблених алгоритмів показав, що ймовірність своєчасного рішення задачі буде: при Р?0,9 для алгоритму А1 при 25n<35, для алгоритму А2 при 25n<50, для алгоритму А3 при 30n<100. Результати досліджень показують стабілізацію похибки (<3% ) зі збільшенням розмірності задачі. Тому найбільш доцільною буде стратегія розробки адаптивного алгоритму реагуючого на зміну розмірності задачі для приведення похибки рішення задачі в діапазон 1%<<3%, при заданих часових обмеженнях.

Достовірність і обґрунтованість отриманих результатів підтверджується доброю збіжністю теоретично отриманих результатів з результатами проведеного експериментального дослідження.

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

Реалізація способу формування навантаження на дугах графа , у значній мірі залежить від того, які навантажувальні аспекти враховуються при рішенні задачі формування графіка реалізації запитів абонентів та транзакцій. У роботі в якості впливаючих характеристики розглянуто два аспекти: аспект фільтруючої потужності (ФП) й аспект фізичної організації (ФО). Кожний із зазначених аспектів враховується в залежності від необхідних кінцевих результатів. Оскільки в роботі потрібно вирішити задачу підвищення оперативності реалізації робочого навантаження МБД ТМ, то у якості визначального враховувався аспект ФП. Цей аспект визначається двома факторами: власною ФП умови для конкретного атрибуту та місцем даної умови в диз'юнктивній нормальній формі умов, тобто розмірністю множини елементарних кон'юнкцій, до якої воно входить. Перший фактор, в свою чергу, визначається кількісною функцією , що визначає кількість екземплярів у МБД, які мають значення х, та заданим у запиті інтервалом значень (х1,х2) для атрибуту . Таким чином власна ФП умови характеризується кількістю екземплярів із значеннями x1 < x < x2. У загальному випадку умова, що входить до множини елементарних кон'юнкцій, що складається з одного елемента, володіє порівняно більшою ФП у порівнянні з такою ж умовою, що входить до множини елементарних кон'юнкцій, яка має кількість елементів більше одного. Оскільки різні комбінації умов мають різні підсумкові ФП, для опису чисел на дугах формується -мірна матриця, елементи якої визначають підсумкові ФП при перевірці кожного на різні комбінації умов. Стосовно до графа це означає, що число на дузі, що входить у деяку вершину, залежить від складу вершин, пройдених до неї, і визначається в момент переходу .

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

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

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

Перший етап реалізації процедури грунтується на співвідношеннях модифікації операторів реляційної алгебри та способах отримання оцінки вже модифікованих операцій. Вихідними даними являються: фрагменти запитів абонентів та транзакцій, максимально допустимий час реалізації (залежить від режиму функціонування МБД), статистика МБД. Різним семантичним ділянкам запитів і транзакцій, поставлено у відповідність, операції реляційної алгебри. Цей етап виконується з метою спрощення семантичних фрагментів запитів і зниження кардинальности предикату реалізованого запиту абонента (транзакції). На наступному кроці здійснюється власне оцінка кардинальності операндів операторів приведених до оптимального вигляду. У зв'язку з тим, що не всі оператори мають кардинальность операнда O(n), виконується вибірка за умовою верхньої границі вартості операнда. В результаті такої вибірки отримано два підкласи операторів. У перший підклас вибираються оператори селекції, проекції без видалення дублів, конвертування, присвоювання. Інші оператори віднесені до другого підкласу. Наявності значного числа операторів з кардинальністю операнда O(n2) можуть сприяти логічні умови, обумовлені запитами абонентів. Далі оператори другого класу розбиваються на дві множини в залежності від того, відносяться вони до класу операторів заснованих на операції з'єднання або декартового добутку. На наступному кроці до розбитих на підкласи операторів застосовуються вираження оптимізації, і здійснюється формування вагової характеристики, що залежить від кінцевого вираження кардинальності операнда і відповідного обсягу необхідної при реалізації оператора інформації. Сформовані оцінки є навантажувальними характеристиками графа пошуку найкоротшого гамільтонового шляху, сформованого на основі матриці зв’язків між операторами в запитах абонентів. На другому етапі в залежності від верхньої оцінки необхідного часу реалізації множини запитів абонентів та транзакцій вибирається алгоритм формування плану реалізації робочого навантаження. Результатом виконання даного етапу є упорядкований план реалізації, у якому вершинам графа G ставляться у відповідність оператори мови маніпулювання даними. Отриманий результат записується в мережний каталог бази даних з метою ведення історії реалізації робочого навантаження та виконання плану СУБД. Таким чином, розроблений алгоритм відображає кроки рішення задачі побудови оптимального плану реалізації робочого навантаження в мережній базі даних. Два етапи відображених у приведеному алгоритмі формування графіка реалізації запитів абонентів та транзакцій відповідають задачам, пошук рішення яких виконувався в даній роботі. Результатом рішення даних задач є сформований графік реалізації робочого навантаження з урахуванням верхньої оцінки припустимого часу реалізації запитів користувачів і транзакцій.

Відповідно до обраного критерію ефективності в роботі виконана оцінка показника ефективності функціонування розробленого модуля управління (рис. 3). В якості стратегій рішення задачі формування графіка реалізації запитів користувачів та транзакцій, визначені наступні:

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

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

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

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

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

Результати аналізу графіку оцінки показника ефективності W(ui) та ймовірності надходження на обробку сумарного числа запитів абонентів і транзакцій показують, що використання точних методів є ефективним тільки на ділянці до 16 запитів абонентів, та там, де потрібна висока точність обчислень з досить низькими вимогами до часу реалізації робочого навантаження. Розроблений метод є наближеним, з досить високою точністю, максимальне відхилення від еталонного значення, яке було зафіксовано, склало 0,023 відносних одиниць. Такі результати дозволяють використовувати розроблений метод в системах оперативної диспетчеризації запитів абонентів та транзакцій при значних рівнях робочого навантаження

ВИСНОВКИ

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

2. Найбільш важливими науковими і практичними результатами, отриманими в роботі, є:

- метод рішення задачі пошуку найкоротшого гамільтонового шляху, на основі рангового підходу, застосування якого дозволяє зменшити похибку рішення задачі розробленими алгоритмами при використанні алгоритму А2 до 10 %, при використанні алгоритму А3 до 3%, алгоритму А1 - 1,5%; знизити час рішення задачі пошуку найкоротшого гамільтонового шляху, для розмірностей задачі 30<n<100.

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

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

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

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

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

- зменшити час обробки робочого навантаження в МБД ТМ у 24 рази;

- знизити вимоги до обсягу оперативної пам’яті в 6 разів;

- забезпечити універсальність і відкритість програмних процедур побудови реалізації робочого навантаження в МБД ТМ.

4. Достовірність отриманих у роботі результатів підтверджується:

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

- несуперечністю відомим результатам;

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

5. Основні результати дисертаційної роботи знайшли своє відображення в 3 звітах з НДР, а також використані в розробках НТ СКБ “Полісвіт”, у навчальному процесі ХВУ, у навчальному процесі ХДЕУ, що підтверджується відповідними актами про впровадження.

Отримані результати можуть бути використані при проведенні науково-дослідних і дослідно-конструкторських робіт зі створення нових технічних засобів і програмних продуктів для обробки інформації в МБД ТМ, у навчальному процесі ВНЗ України.

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

1. Королев А.В., Голубничий Д.Ю., Третьяк В.Ф., Осиевский С.В. Результаты экспериментального исследования алгоритмов целочисленного линейного программирования с булевыми переменными // Інформаційно-керуючі системи на залізничному транспорті. – 2001. – №4. – С. 33-39.

2. Осиевский С.В., Тимченко А.А. Процедура определения точки входа на основе анализа векторов весовых характеристик исходного графа состояний // Системи обробки інформації. – Харків: НАНУ, ПАНМ, ХВУ. – 2002. – Вип. 6 (22). – С. 281 – 284.

3. Соколов С.А., Кавун С.В., Осиевский С.В. Метод отсечения неперспективных вариантов решения задачи целочисленного линейного программирования с булевыми переменными // Інформаційно - керуючі системи на залізничному транспорті. – 2001. – №5. – С. 35-38.

4. Осиевский С.В. Способ решения задачи параллельной обработки запросов к базам данных // Системи обробки інформації. – Харків: НАНУ, ПАНМ, ХВУ. – 2002. – Вип. 5 (21). – С. 197 – 204

5. Осиевский С.В. Оценка числа дисковых операций операторов языка манипулирования данными в сетевой базе данных // Системи обробки інформації. – Харків: НАНУ, ПАНМ, ХВУ. – 2003. – Вип. 1 . – С. 92 – 98.

6. Соколов С.А., Осиевский С.В. Алгоритм поиска кратчайшего гамильтонового пути для решения задачи диспетчеризации множества запросов пользователей к БД сложных информационных структур // Інформаційно-керуючі системи на залізничному транспорті. – 2002. – №4, 5. – С. 32 -33.

7. Осиевский С.В., Бучак Н.И. Метод выявления и разрешения конфликтов и противоречий при функционировании баз данных // Проблеми інформатики і моделювання. Материалы международной НТК. – Харків:НТУ“ХПІ”. – 2002. – С.9

8. Шамов С.А., Осиевский С.В. Параллельный алгоритм определения кратчайших гамильтоновых путей в произвольных графах для обеспечения устойчивого функционирования компьютерной информационной системы // Матеріали ІІ Всеукраїнської науково-технічної конференції “Актуальні проблеми та перспективи розвитку фінансово-кредитної системи України”. _Харків: Фінарт, 2002. – С. 370 - 371.

АНОТАЦІЯ

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

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

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

Для підвищення ефективності управління мережною базою даних телекомунікаційної мережі розроблені: метод рішення задачі пошуку найкоротшого гамільтонового шляху на основі рангового підходу, що дає обчислювальну складність рішення задачі в гіршому випадку O(cn3), при с=const, метод формування графіка реалізації запитів користувачів і транзакцій в МБД ТМ на основі рішення задачі пошуку найкоротшого гамільтонового шляху в довільному реберно-зваженому графі, спосіб визначення мінімально віддаленої вершини з метою визначення точки входу в структуру графу пошуку найкоротшого гамільтонового шляху, що дозволяє скоротити кількість елементарних операцій при реалізації алгоритмів пошуку найкоротшого гамільтонового шляху та уникнути аналізу неперспективних варіантів пошуку при рішенні задачі.

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

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

АННОТАЦИЯ

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

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

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