Державний комітет зв'язку та інформатизації України
 |
Українська державна академія зв'язку ім. О.С. Попова
Кафедра Мереж зв'язку
ЭЛЕМЕНТИ СИНТЕЗУ Й АНАЛІЗУ
ТЕЛЕКОМУНІКАЦІЙНИХ МЕРЕЖ
Методичні вказівки і комплексне завдання для студентів
усіх форм навчання з дисципліни “Мережі зв’язку”
(Спеціальність “Телекомунікації”)
ЗАТВЕРДЖЕНО
Радою факультету
“Інформаційні мережі”
Протокол №
від_______________
Одеса 2000
УДК 621.391
План НМВ 1999/2000 навч. р.
Рецензенти: Г.С. Гайворонська
О.О. Вараксін
Укладач: Л.А. Нікітюк
Наведено ключові положення та методичні вказівки для виконання комплексного завдання, сформульовано додаткові прикладні задачі синтезу та аналізу телекомунікаційних мереж й вимоги до їхнього розв'язання. Наведено варіанти індивидуальних завдань.
СХВАЛЕНО
на засіданні кафедри
Мереж зя´язку
і рекомендовано до друку
Протокол №16
Від 6.07.99 р.
ЗМІСТ
| стр. | ||
| 1 | Загальні положення | |
| 2 | Ключові положення | |
| 2.1 Загальне поняття про задачі синтезу й аналізу мереж зв'язку | ||
| 2.2 Модельне подання мережі зв'язку як об'єкта синтезу й аналізу | ||
| 2.3 Елементи теорії оптимізації на графах і мережах | ||
| 2.3.1 Синтез мережі мінірисьної вартості | ||
| 2.3.2 Визначення медиани графа | ||
| 2.3.3 Визначення центру графа | ||
| 2.3.4 Визначення циклу найменшої довжини | ||
| 2.3.5 Перебування найкоротшого шляху в мережі, що зв'язує | ||
| 2.3.6 Визначення множини шляхів заданої транзитності | ||
| 2.3.7 Задача про потоки | ||
| 3 | Комплексне завдання | |
| 3.1 Побудова моделей телекомунікаційної мережі | ||
| 3.2 Синтез мережі абонентського доступу | ||
| 3.3 Синтез мережі міжвузлового зв'язку | ||
| 3.4 Побудова маршрутних матриць | ||
| 3.5 Оцінка пропускної здатності мережі поміж парою пунктів | ||
| Список літератури | ||
| Додаток А | ||
| Додаток Б | ||
Загальні положення
Комплексне завдання охоплює матеріал, що містить загальні принципи побудови телекомунікаційних мереж як об'єктів синтезу й аналізу.
Практика проектування, експлуатації й модернізації (реконструкції, розвитки) телекомунікаційних мереж висуває різноманітні задачі, розв´язання яких припускає їхню форрисізацію в термінах математичних моделей синтезу й аналізу мереж і вибір адекватних методів розв´язання серед всієї множини існуючих методів.
Ціллю комплексного завдання є ознайомлення з елементами математичного апарата синтезу й аналізу мереж і набуття прак-тических навичок в розв´язанні конкретних задач, що вони виникають при їхньому проектуванні й експлуатації.
Для виконання комплексного завдання необхідно вивчити поділи "Ключові положення" та "Комплексне завдання" цих методичних вказівок і обрати індивідуальний варіант вихідних даних, обумовлений номером, складеним з двох останніх цифр студентського квитка (див. Додаток А).
Виконані відповідно до завдання розрахунки разом із постановками задач, загальними поясненнями принципів їхнього розв´язання й матеріалом, що ілюструє, необхідно оформити у виді пояснительной записки з титульним аркушем (форму титульного аркуша наведено в Додатку Б).
Пояснительная записка має містити вступ й розділи, відповідні числу завдань. У вступі слід навести такі положення, як призначення телекомунікаційних мереж та їхня загальна характеристика, принципи структурної організації, основні компоненти й сегменти мереж, загальна характеристика задач синтезу й аналізу мереж зв'язку тощо.
2 Ключові положення
Загальне поняття про задачі синтезу й аналізу мереж зв'язку
Всі задачі, що вони виникають при побудові й експлуатації телекоммуни-кационних мереж, можна поділити на два класи: задачі синтезу й задачі аналізу.
" Синтез " у перекладі з грецької означає поєднання, складання.
Задача синтезу мережі виникає як при побудові нової мережі, так і при реконструкції й розвиткові існуючих мереж. Ця задача має техніко-економічний характер, тому що найчастіше відшукується розв´язання, оптирисьне з низки економічних показників, наприклад, мінімуму капіталовкладень.
При синтезі мережі зазвичай вважається заданим розташування пунктів мережі. Конфігурація (топологія) же ліній зв'язку може змінюватися за оптимізації економічних показників. Це дозволяє використовувати витрати на лінії зв'язку в якості цільового критерію оптирисьного синтезу мережі. На конфігурацію ліній можуть бути накладені обмеження у вигляді вилучення окремих географічних трас при організації зв'язку поміж пунктами, наприклад, якщо вони перетинають водяні або гірські перепони.
До окремих задач синтезу можна віднести задача вибору оптирисьної топології мережі, вибір оптирисьної кількості й місця розташування вузлів комутації тощо.
Задача аналізу є актуальні для існуючої (синтезованої мережі). До них належать задачі відшукування оптирисьних шляхів передавання інформаційних повідомлень, визначення сукупності шляхів заданої транзитності, оцінки пропускної здатності мережі, ймовірності встановлення сполучення поміж пунктами тощо.
У класі задач аналізу розглядаються також питання розрахунку характеристик і параметрів як мережі у цілому, так і окремих її елементів. До таких характеристик відносять якість обслуговування на мережі, параметри надёжности й живучості.
Для того, щоб розв´язати конкретну задачу синтезу чи аналізу телекомунікаційної мережі, її необхідно форрисізувати, тобто записати у виді схеми: що дано, що необхідно визначити і за яких обмежень.
Форрисізацію можна виконати у словесній формі (така форма має назву вербальної моделі задачі) або у виді математичної моделі, що описує задачу в термінах тієї чи іншої теорії (наприклад, теорії графів, теорії оптирисьних розв´язків тощо).
Здійснення форрисізації потребує не лише розуміння проблеми, що постає, але й вибору відповідної моделі самого об'єкта (мережі зв'язку). Модельне (спрощене) подання об'єкта синтезу чи аналізу дає змогу виявити й відбити найбільш істотні з точки зору посталої проблеми елементи об'єкта і зв'язки поміж ними, не відволікаясь на деталі.
Для модельного подання мереж зв'язку найбільше часто використовуються графові моделі. На основі моделі об'єкта та її параметрів (кількості пунктів і ліній мережі, відстаней поміж пунктами, пропускної здатності вузлів і ліній мережі, вартісних параметрів тощо) можна побудувати математичну модель, що відбиває залежність між шуканими параметрами й незалежними змінними задачі у вигляді математичних функцій.
В задачах синтезу й аналізу мереж зв'язку найчастіше використовуються математичні моделі оптимізації, де места розв´зання задачі записується у виді так називаної цільової функції, для котрої необхідно відшукати е кстремум ( мінімум чимаксимум). На вхідні в її параметри можуть накладатися обмеження, що вони вказуватимуть, в яких межах можуть змінюватися значення шуканих параметрів.
О з н а ч е н н я. Задачі, в яких відшукується екстремум (мінімум чи максимум) певної цільової функції, що відбиває критерій оптирисьності розв´язання задачі, називаються екстрерисьними.
Характерною рисою екстрерисьних задач синтезу й аналізу телекомунікаційних мереж є їхня велика розмірність. Формулювання цих задач у термінах графових та мережних моделей дозволили дістати низку ефективних, із погляду подолання обчислювальної складності, методів і алгоритмів їхнього розв´язання, орієнтованих на застосуванні ЕОМ. Деякі з таких алгоритмів розглянуто нижче.
Під алгоритмом розуміється процедура, що вона забезпечує дістання оптирисьного розв´язку задачі, виконання якої можна доручити ЕОМ. Розрізняють алгоритми точні й наближені, так називані евристичні.
Точні алгоритми завжди гарантують віднайдення оптирисьного розв´язку (глобального оптимуму цільової функції). Наприклад, алгоритм повного перебору всіх можливих розв´язків із вибором найкращого серед них, є точним алгоритмом.
Однак точні алгоритми, як правило, доволі трудомісткі з обчислювальної точки зору. Тому на практику часто використовують більш прості алгоритми, що забезпечують швидке дістання розв´язку з прийнятної для практики точністю. Такі алгоритми будуються з використанням раціональних, з точки зору логіки людини, правил виконання обчислень. Ці правила називаються евристиками і, як показує практика, дозволяють дістати розв´язок, близький до оптирисьного. Наприклад, задача визначення замкнутого контуру найменшої довжини, що забезпечує обхід усіх пунктів мережі, може бути розв´язана шляхом повного перебору всіх можливих контурів із вибором серед них контуру найменшої довжини, тобто точного алгоритму. Відомо, що для мережі, котра містить n пунктів, кількість можливих контурів становить порядку n!, отримання яких для мережі розміром n>30 являє значні трудності. Однак використання евристики: " кожного кроку рухаємося лише до найближчого пункту " забезпечує дістання прийнятного розв´язку за час, необхідний для побудови лише одного контуру.
Евристичні алгоритми використовуються також у тих випадках, коли побудувати точний алгоритм не вдасться через складність математичної моделі задачі (її нелінійність, дискретність тощо).
