Главная Контакты Добавить в избранное Авторы Вопросы и ответы
,

УДК 681.3

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

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

Вступ.

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

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

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

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

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

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

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

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

 

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

 

.

(1)

 

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

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

 

f(x) >min, xX.

(2)

 

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

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

 

.

(3)

 

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

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

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

 

,

(4)

 

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

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

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

Для великих гетерогенних мереж реалізацією алгоритму 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 с.

 

 





Ответы на вопросы [_Задать вопроос_]

Оптимальное управление объектами и системами

Тимченко В.Л. Формирование динамических принципов управления подвижным объектом на основе метода структурно ― переключаемых обратных связей

Лебеденко Ю.О., Рудакова Г.В. Модель нечіткого виводу для оптимального управління перетворювачем частоти в системах автономного живлення

Ладанюк А.П., Кроніковський Д.О. Екстремальна адаптивна система з непараметричною ідентифікацією та багатопараметричним регулятором

Ладієва Л.Р., Дубік Р.М. Оптимальне керування процесом контактної мембранної дистиляції

Писаренко А.В., Дробот І.Ю. Алгоритм синтезу систем зі змінною структурою у ковзному режимі

Погребняк И.Ф. Формализация проблемы управления организационными системами в условиях неопределенности

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

Дорогов А.Ю., Лесных В.Ю., Раков И.В., Титов Г.С. Алгоритмы оптимального движения мобильных объектов по пересеченной местности и транспортной сети

Михайленко В.С., Ложечников В.Ф. Сравнительный анализ комплексного и нечеткого регуляторов при управлении многомерным объектом

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

Луцька Н.М., Заєць Н.А., Ладанюк А.П. Синтез та порівняння багатовимірних регуляторів для колонної дифузійної установки цукрового заводу.

Корнієнко Б.Я., Снігур О.В. Оптимізація параметрів процесу зневоднення і гранулоутворення в апараті псевдозрідженого шару

Ладієва Л.Р., Зав'ялова Т.П. Оптимізація плівкового апарату роторного типу за максимальною продуктивністю

Лебеденко Ю.О. Оптимальне управління безпосереднім перетворювачем частоти за критерієм мінімізації негативного впливу на живильну мережу

Тарасюк В.П., Алдохіна А.С. Основні положення методики побудови оптимального розкладу управління обладнанням паралельних технологічних процесів на основі експертних оцінок.

Стопакевич А.А. Новые соотношения для синтеза цифровых оптимальных одномерных систем управления для объектов с запаздыванием.

Ладієва Л.Р.,. Жулинський О.А Оптимізація установки контактної мембранної дистиляції.

Батурінець Є. В., Пасенченко Ю. А. Управління матеріальними запасами з обмеженнями на складські приміщення

Смітюх Я.В., Кишенько В. Д. Оптимізація управління процесами брагоректифікації.

Рябкин Ю.В, Карнаух В.В. Квазиоптимальная обработка коротких радиоимпульсов в акустооптическом спектроанализаторе.

Песчанский А.И. Оптимальное техническое обслуживание двухкомпонентной параллельной системы с учетом наработки каждого элемента.

Лебеденко Ю.А. Исследование непосредственного преобразователя частоты с оптимальным управлением.

Исаев Е.А., Чернецкая И.Е., Завальнюк О.П. К вопросу принятия решений при оптимизации гранулирования рыбной муки в барабане.

Кириллов О.Л., Якимчук Г.С. Оптимальное управление технологическим процессом заполнения слабопроводящими заряжающимися жидкостями (СПЗЖ) замкнутых объемов.

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

Поливода О.В., Бражник А.М. Метод компенсации ошибок идентификации при оптимальном управлении

Марасанов В.В., Забитовская О.И., Щербина Е.В. Энтропийные методы оптимизации гравитационных моделей.

Балтовский А.А. Синтез оптимального закона управления большой системой на основе композиции локальных оптимальных решений

Луцька Н.М. Синтез оптимальних регуляторів для систем автоматизації технологічних комплексів неперервного типу.

Кондратенко Г. В., Кондратенко Ю. П., Мухортова К. В. Синтез нечетких регуляторов на основе объектно-ориентированных технологий.

Чернецкая И.Е., Исаев Е.А., Лебеденко Ю.А. Система автоматической оптимизации окомкования железорудного концентрата в условиях ЦГОКа

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

Усов А. В., Дубров К. А. Оптимизация  и управление термомеханическими процессами при получении феррокерамических изделий для отклоняющих систем

Кучеров Д.П. Алгоритм обучения субоптимальному по быстродействию управлению динамической системой второго порядка без нулевых полюсов

Ладанюк А.П., Луцька Н.М., Лобок О.П. Розробка багатовимірних оптимальних регуляторів для об'єктів одного класу.

Маломуж Т.В. Оптимальное управление на основе интеллектуальных систем

Марончук И.Е., Кучерук А.Д., Данилец Е.В., Ерохин С.Ю., Чорный И.В. Опти-мизация двухкоординатных позиционно-чувствительных фотоприемников.