Автоматика.
    Автоматизация.
        Электротехнические
            комплексы и системы.

УДК 681.3

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

Бойченко О.В.

Вступ.

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

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

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

Аналіз останніх досліджень. Питання розробки та впровадження різноманітних моделей та алгоритмів для підвищення ефективності застосування управлінських інформаційно-телекомунікаційних систем спеціального призначення розглядалися в роботах таких видатних фахівців, як О. Оре, С. Гудман, С. Хідітміемі, Ю. Бардачов, Н. Соколова, В. Ходаков, О. Плотніков, Р. Бараненко та інших. Слід зазначити, що проаналізовані існуючі алгоритми пошуку найкоротшого шляху [1-4] є доволі складними для програмної реалізації, відзначаються великою обчислювальною складністю і не забезпечують необхідної швидкості пошуку інформаційних даних при застосуванні розгалужених інформаційно-аналітичних систем спеціального призначення з великою кількістю інформаційно-пошукових систем функціонального призначення та зв’язків між ними.

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

Основний матеріал.

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

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

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

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

Завдання оптимізації формулюється в загальному вигляді [4], коли задані множина Х і функція f(x), визначена на Х; і потрібно знайти точки мінімуму функції f на X, отримуємо наступний запис:

При цьому f називається цільовою функцією, Х – безліччю рішень, будь-який елемент xX – рішенням задачі.

Необхідно знайти точку глобального мінімуму функції f на множині X таку, що

Це завдання вирішується за допомогою методів дослідження операцій і засобів теорії прийняття рішень [5-7].

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

Для пошуку найкоротшого маршруту пропонується використовувати алгоритм SPF (Shortest Path First), розроблений Дейкстрой [9]. Відповідно до цього алгоритму найкоротший шлях між вершинами графа рівний [3]:

де        - відстані в мережі між суміжними вузлами  і ;

- найкоротший шлях між «джерелом» -  і -м вузлом;

- найкоротший шлях між «джерелом» і - попереднім вузлом в мережі.

Для великих гетерогенних мереж реалізацією алгоритму SPF є протокол OSPF (Open Shortest Path First) [10]. У OSPF процес побудови таблиці маршрутизації розбивається на два крупні етапи. На першому етапі кожен маршрутизатор будує граф зв’язків мережі, в якому вершинами графа є маршрутизатори і IP-мережі, а ребрами – інтерфейси маршрутизаторів. Всі маршрутизатори для цього обмінюються зі своїми сусідами тією інформацією про графу мережі, яку вони мають в своєму розпорядженні до даного моменту часу. Другий етап полягає в знаходженні оптимальних маршрутів за допомогою отриманого графа. Кожен маршрутизатор вважає себе центром мережі і шукає оптимальний маршрут до кожної відомої йому мережі. У кожному знайденому таким чином маршруті запам’ятовується тільки один крок – до наступного маршрутизатора, відповідно до принципу однокрокової маршрутизації. Дані про цей крок і потрапляють в таблицю маршрутизації.

Зважаючи на складність та трудомісткість завдання знаходження оптимального шляху на графі [1-4], пропонується застосування алгоритм SPF, який має за основу базу даних стану зв’язків та обчислює найкоротші шляхи між заданою вершиною S графа і рештою всіх вершин. Результатом роботи алгоритму є таблиця, де для кожної вершини V графа вказаний список ребер, що сполучають задану вершину S з вершиною V по найкоротшому шляху.

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

S - задана вершина (джерело шляхів);

E - безліч оброблених вершин, тобто вершин, найкоротший шлях до яких вже знайдений;

R - безліч вершин графа, що залишилися (тобто безліч вершин графа за вирахуванням безлічі E);

O - впорядкований список шляхів.

Пропонований алгоритм складається з повторюваних виконань наступних кроків:

1. Ініціалізувати E={S}, R={всі вершини графа, окрім S}. Помістити в О всі односегментні (завдовжки в одне ребро) шляхи, що починаються з S, відсортувавши їх в порядку зростання метрик.

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

3. Розглянемо P - найкоротший шлях в списку О. Видалити P з О. Хай V - останній вузол в P.

Якщо V належить E, перейти на крок 2; інакше P є найкоротшим шляхом з S в V; перенести V з R в E.

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

Протокол OSPF дозволяє зберігати в таблиці маршрутизації декілька маршрутів до однієї мережі. Якщо такі записи утворюються в таблиці маршрутизації, то маршрутизатор реалізує режим балансу завантаження маршрутів (load balancing), відправляючи пакети поперемінно по кожному з маршрутів.

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

Висновки

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

ЛІТЕРАТУРА

1.                  Бараненко Р.В. Оптимизация работы корпоративных компьютерных сетей / Р.В. Бараненко, В.Н. Козел, Е.А. Дроздова, А.О. Плотников // Научный журнал ААЭКС. - М, 2004. - №1(13). – С. 25-29.

2.                  Бардачев Ю.Н. Основы дискретной математики: учебное пособие [для студ. высш. учебн. завед.] / Ю.Н. Бардачев, Н.А. Соколова, В.Е. Ходаков. – Херсон: ХГТУ, 2000. – 356 с.

3.                  Оре О. Теория графов: монография / О.Оре. – М.: Наука, 1968. – 365 с.

4.                  Гудман С. Введение в разработку и анализ алгоритмов : учебное пособие [для студ. высш. учебн. завед.] / С. Гудман, С. Хидитмиеми. – К.: Вища школа, 1985. – 350с.

5.                  Коршунов Ю.М. Математические основы кибернетики: учебное пособие [для студ. высш. учебн. завед.] / Коршунов Ю.М. – М.: Энергия, 1980. – 424 с.

6.                  Петров Э.Г. Методы и средства принятия решений в социально-экономических и технических системах: учебное пособие [для студ. высш. учебн. завед.] / Э.Г. Петров, М.В. Новожилова, И.В Гребенник, Н.А. Соколова. – Херсон: ОЛДІ – плюс, 2003. – 380 с.

7.                  Зайченко Ю.П. Исследование операцій: монография / Зайченко Ю.П. – К.: Выща школа, 1986. - 222 с.

8.                  Горелик В.А. Исследование операций: монография / В.А. Горелик, И.А. Ушаков. – М.: Машиностроение, 1986. – 288 с.

9.                  Dijkstra E. Cooperating Sequential Processes / Dijkstra E. - Technological University, Eindhoven, The Netherlands, 1965. – 345 Р.

10.              Олифер В.Г. Компьютерные сети. Принципы, технологии, протоколы: монография / В.Г. Олифер, Н.А. Олифер. – СПб.: Питер, 2001. – 672 с.