Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



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

Скачати 16.64 Kb.

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




Скачати 16.64 Kb.
Дата конвертації24.05.2017
Розмір16.64 Kb.

УДК 004.89
ВИЗНАЧЕННЯ ОПТИМАЛЬНОГО ШЛЯХУ В ТРАНСПОРТНІЙ МЕРЕЖІ ЗВ’ЯЗКУ ТА АНАЛІЗ ЙОГО ОБЧИСЛЮВАЛЬНОЇ СКЛАДНОСТІ
Морфіянець О. О.

Науковий керівник – проф., д.т.н. Яровий А.А.

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

Телекомунікації Телекомуніка́ції, також електрозв'язок (англ. Telecommunications) - передавання, випромінювання та/або приймання знаків, сигналів, письмового тексту, зображень та звуків або повідомлень будь-якого роду дротовими, радіо, оптичними або іншими електромагнітними системами.
Транспорт Тра́нспорт (від лат. trans - portare) - сукупність засобів, призначених для переміщення людей, вантажів, сигналів та інформації з одного місця в інше.

Метою дослідження є підвищення швидкодії визначення оптимальної кількості каналів та трактів транспортної мережі зв’язку.

Озна́чення, ви́значення чи дефіні́ція (від лат. definitio) - роз'яснення чи витлумачення значення (сенсу) терміну чи поняття. Слід зауважити, що означення завжди стосується символів, оскільки тільки символи мають сенс що його покликане роз'яснити означення.
Транспортна мережа Транспортна мережа, або ядро мережі (backbone або core network), - це універсальна мережа, що реалізує функції транспортування/комутації й об’єднує окремі мережі доступу із забезпеченням транзиту трафіка між ними високошвидкісними каналами.
У дослідженні поставлено задачу знаходження оптимального шляху в транспортній мережі зв’язку: дано транспортну мережу зв’язку зі станціями та зв’язками між ними, кожний зв’язок характеризується пропускною здатністю, потрібно визначати оптимальний за пропускною здатністю шлях між двома заданими станціями у транспортній мережі зв’язку, а також потрібно мати змогу змінювати транспортну мережу зв’язку відповідно до вимог користувача.
Дослі́дження, до́сліди - (широко розуміючи) пошук нових знань або систематичне розслідування з метою встановлення фактів; (вузько розуміючи) науковий метод (процес) вивчення чого-небудь.



В дослідженні були розглянуті, проаналізовані та опротестовані наступні методи вирішення задачі: метод з використанням бінарного пошуку та пошуку у ширину, метод з використанням алгоритму Дейкстри, а також, після доведення еквівалентності поставленої задачі на графі та на максимальному остовному дереві, метод з використанням максимального остовного дерева та динамічних дерев Тар’яна та Слейтора.
Дина́міка (грец. δύναμις - сила) - розділ механіки,в якому вивчаються причини виникнення механічного руху. Динаміка оперує такими поняттями, як маса, сила, імпульс, момент імпульсу, енергія.
Алгоритм Дейкстри - алгоритм на графах, відкритий Дейкстрою. Знаходить найкоротший шлях від однієї вершини графа до всіх інших вершин. Класичний алгоритм Дейкстри працює тільки для графів без циклів від'ємної довжини.
Наведена нижче таблиця демонструє отримані теоретичні та практичні результати:


Алгоритм вирішення задачі


Обчислювальна складність алгоритму зміни графу

Обчислювальна складність алгоритму відповіді на запит

Час роботи на графах розміром до 100000 вершин та ребер

Час роботи на графах розміром до 1000000 вершин та ребер

Бінарний пошук та пошук у ширину

O(1)

O(m ∙ log(m))

80 мс

911 мс

Алгоритм Дейкстри

O(1)

O(m ∙ ln(n)/ln(m/n))

153 мс

1329 мс

Максимальне остовне дерево та динамічні дерева

O(log(m))

O(m)

51 мс

168 мс


Скачати 16.64 Kb.