Г. В. Попков, Попков, Величко
В. К.
В. В.
Математические основы
моделирования сетей связи
Рекомендовано УМО по образованию в области
инфокоммуникационных технологий и систем связи
в качестве учебного пособия для студентов
высших учебных заведений, обучающихся по направлению
подготовки 210700 – Инфокоммуникационные технологии
и системы связи квалификации (степени) «бакалавр»
и квалификации (степени) «магистр»
Москва
Горячая линия - Телеком
2012
Стр.1
УДК 621.395.74+519.711.3
БКК 32.882
П57
Попков Г. В., Попков В. К., Величко В. В.
П57 Математические основы моделирования сетей связи. Учебное пособие
для вузов. – М.: Горячая линия–Телеком, 2012. – 183 с.: ил.
ISBN 978-5-9912-0266-7.
Рассмотрены основные математические модели сетей на примере сетей
абонентского доступа (САД). Обсуждаются вопросы исследования и разработки
методов оптимизации проектирования САД, позволяющие находить
наиболее экономичные и технически правильные проектные решения для современных
абонентских оконечных устройств, средств коммутации и передачи
сообщений. Впервые в практике формализации абонентских сетей рассмотрено
использование гиперсетевых моделей, обеспечивающих наиболее
адекватное представление САД. Приведены не только новые модели, но и
корректные постановки задач синтеза сетей, а также рассмотрены методы их
решения.
Для студентов вузов, обучающихся по программам бакалавриата и магистратуры
направления 210700 – «Инфокоммуникационные технологии и системы
связи» профиль подготовки «Сети связи и системы коммутации», будет
полезно студентов других инфокоммуникационных специальностей, проектировщиков,
связанных с оптимальным проектированием систем сетевой
структуры, аспирантов.
БКК 32.882
Адрес издательства в Интернет WWW.TECHBOOK.RU
Учебное издание
Попков Глеб Владимирович, Попков Владимир Константинович,
Величко Вячеслав Витальевич
Математические основы моделирования сетей связи
Учебное пособие для вузов
Художник В. Г. Ситников
Подготовка оригинал-макета Н. В. Дмитриевой
Подписано к печати 25.04.2012. Формат 60×88 1/16. Усл. печ. л.11,38.
Тираж 500 экз. (1-й завод 200 экз.)
ООО «Научно-техническое издательство «Горячая линия–Телеком»
ISBN 978-5-9912-0266-7
© Г. В. Попков, В. К. Попков,
В. В. Величко, 2012
© Издательство «Горячая линия–Телеком», 2012
Стр.2
ОГЛАВЛЕНИЕ
Предисловие...................................................................................................6
Глава 1. Основные принципы проектирования современных
абонентских сетей............................................................................7
1.1. Описание и принципы проектирования САД.................................8
1.1.1. Термины, и основные понятия............................................ 8
1.1.2. Существующие принципы проектирования
абонентских сетей........................................................................ 14
1.2. Современные и перспективные средства доступа
пользователей к сетям электросвязи....................................................17
1.2.1. Кабельные системы доступа ............................................. 17
1.2.2. Применение радиосредств на абонентских сетях ........... 23
1.2.3. Лазерные системы доступа ............................................... 26
1.3. Услуги в САД...................................................................................27
1.3.1. Поддержка широкополосных услуг ................................. 27
1.3.2. Рынок услуг сетей САД..................................................... 67
Глава 2. Методологические вопросы разработки оптимальных сетей
абонентского доступа....................................................................71
2.1. Общий подход к проектированию.................................................71
2.2. Основные этапы проектирования...................................................73
2.3. Методика диалоговой оптимизации САД.....................................79
2.3.1. Методологические вопросы описания и анализа
сетей электросвязи ....................................................................... 82
2.3.2. Технология формулировки задач
проектирования САД.................................................................. 86
2.3.3. Методы и алгоритмы для поиска оптимальных САД..... 90
2.3.4. О технологии мультидиалогового моделирования
и оптимизации сетей связи.......................................................... 94
2.4. Маркетинговые исследования в задаче поиска проектного
решения САД..........................................................................................97
2.4.1. Постановка задачи ............................................................. 98
2.4.2. Классификация услуг электросвязи ................................. 99
Глава 3. Построение первичной сети абонентского доступа.................100
3.1. Содержательная постановка задачи построения САД...............100
3.2. Математическая модель структуры сети
абонентского доступа...........................................................................105
3.3. Декомпозиция и задача выбора способов организации
связи САД..............................................................................................111
3.3.1. Определение верхней оценки типа и числа заявок
на услуги связи (телефония, передача данных) разбиение
территории на однородные участки ......................................... 111
Стр.3
4
Математические основы моделирования сетей связи
3.3.2. Определение способов организации связи на каждом
участке для предоставления услуг телефонной связи
и передачи данных ..................................................................... 111
3.4. Поиск вторичных сетей с различными способами
организации связи.................................................................................113
3.4.1. Задача районирования территории САД и оценка........ 113
3.4.2. Задача поиска вторичной сети с симметричными
кабельными линиями связи....................................................... 116
3.4.3. Задача поиска вторичной сети с использованием
волоконно-оптических линий связи (ВОЛС)........................... 118
3.4.4. Задача поиска вторичной сети с использованием
систем радиодоступа (РД) ......................................................... 119
3.4.5. Анализ и выбор способа организации связи ................. 121
3.5. Построение сети абонентского доступа ......................................121
3.5.1. Задача поиска сети кабельной канализации .................. 121
3.5.2. Построение первичной сети............................................ 123
3.6. Оценка капитальных затрат на САД............................................126
Глава 4. Основные процедуры синтеза САД...........................................127
4.1. Обобщённый алгоритм оптимизации САД и его
декомпозиция на частные задачи теории графов
и теории гиперсетей .............................................................................127
4.2. Поиск кратчайших маршрутов и модель топоосновы................129
4.2.1. Задача поиска кратчайших цепей в графе ..................... 129
4.2.2. Задача поиска кратчайшего пути в гиперсети............... 130
4.2.3. Математическая модель топоосновы
для кабельных линий ................................................................. 131
4.3. Размещение медианных вершин в гиперсетях............................132
4.3.1. Медианы в гиперсетях..................................................... 133
4.3.2. В-медиана в гиперсети .................................................... 135
4.3.3. О задаче поиска медианы графа на плоскости.............. 136
4.4. Задачи поиска связующих сетей ..................................................136
4.4.1. Задача поиска кратчайшего циклического маршрута
в гиперсетях................................................................................ 137
4.4.2. Задача поиска дерева Штейнера в гиперсети ................ 138
4.4.3. Поиск части графа с заданной связностью.................... 139
4.4.4. Покрытие графа сетями специального вида.................. 139
4.5. Задачи поиска покрывающих вершин или ребер
в гиперграфах и гиперсетях.................................................................143
4.5.1. Задача о минимальном покрытии вершин
гиперграфа ребрами................................................................... 143
4.5.2. Задача поиска максимально независимого множества
в гиперграфе ............................................................................... 145
Стр.4
Оглавление
5
Глава 5. Разработка интерактивной системы поиска проектных
решений в сетях электросвязи....................................................147
5.1. Принципы построения и структура интерактивной системы
поиска проектных решений.................................................................147
5.2. Описание работы пользователя с интерактивной системой......151
5.3. Использование интерактивной системы в процессе
обучения студентов вузов....................................................................153
5.4. Графический интерфейс системы ................................................154
5.4.1. Описание реализации графического редактора ............ 155
5.4.2. Описание возможностей работы редактора .................. 159
Глава 6. Варианты задач............................................................................163
Литература..................................................................................................179
Стр.5
ПРЕДИСЛОВИЕ
В настоящее время в процесс обучения активно внедряются программные
технологии на базе персональных ЭВМ, применяемые для
передачи ученику учебного материала и контроля степени его усвоения.
При этом на рынке программного продукта за последнее десятилетие
появилось большое количество обучающих систем, в том числе и автоматизированных
(АОС), которые охватывают различные предметные
области и призваны решать задачи обучения на всех этапах – от средней
школы до высших учебных заведений. Математическое моделирование,
компьютерная техника и технология становятся одним из основных инструментов
познавательного процесса. Лабораторные работы по математическому
моделированию кроме пополнения знаний непосредственно
по специальности помогают в выработке навыков формирования математических
моделей, в выборе и использовании адекватных методов и
средств их анализа, в интерпретации полученных результатов. Наибольшую
ценность с точки зрения идеи разработки составляют компоненты,
организующие обратную связь со студентом. Именно в них сосредоточены
механизмы искусственного интеллекта.
Целью данного учебного пособия является познакомить студента с
основами графового представления телекоммуникационных сетей и
возможностями математического аппарата, возникающего при данном
представлении. В основе пособия лежат типичные задачи, встающие
перед проектировщиком, такие как расчёт минимального пути или выбор
оборудования. На основе алгоритмов данных задач строятся отдельные
примеры, с приближением к реальным условиям, возникающим
при эксплуатации и проектировании телекоммуникационных сетей.
Для визуализации учебного пособия используется программный
продукт – демо-версия перспективной разработки учёных ИВМиМГ СО
РАН GraphEditor. Интерфейс используемой программы, интуитивно понятен
и прост для освоения его студентами. Широкий спектр задач, возникающих
в процессе проектирования и эксплуатации телекоммуникационных
сетей, решается с помощью методов теории графов с применением
оптимальных комбинаторных алгоритмов. Математической
моделью структуры сети служит граф с соответствующими характеристиками.
Каждому студенту предлагается свой вариант начального графа
вместе с исходными данными и заданием. В процессе обучения граф
становится детально просчитанным и оптимально подходящим для каждого
варианта проектного задания. Таким образом, в конце курса обучения
у каждого студента будет собственная спроектированная и рассчитанная
им модель телекоммуникационной сети.
Стр.6
Глава 1. ОСНОВНЫЕ ПРИНЦИПЫ
ПРОЕКТИРОВАНИЯ СОВРЕМЕННЫХ
АБОНЕНТСКИХ СЕТЕЙ
Сеть абонентского доступа представляет собой самый дорогой и
наименее эффективно используемый элемент в системе электросвязи.
По этой причине оптимизация проектирования сетей абонентского доступа
(САД) рассматривается как одна из наиболее важных задач для современной
телекоммуникационной системы.
Задачи оптимизации проектирования САД вытекают из необходимости
заблаговременного выбора технических средств, обеспечивающих
удовлетворение потребностей в передаче информации. Разработка
методов оптимизации проектирования сетей абонентского доступа и ее
применение на различных этапах создания сетей доступа должна позволить
находить наиболее экономичные и технически правильные решения
для используемых оконечных устройств, средств коммутации и передачи
сообщений. Задачи оптимизации проектирования сетей абонентского
доступа (далее сети доступа) состоят в следующем:
1. Разработка математических моделей для задачи оптимизации структур
САД с учетом соответствующего состояния техники и технологии,
а также с учетом градостроительных факторов.
2. Определение этапов создания сетей доступа для эффективной реализации
проектируемых на длительный срок структур.
3. Разработка методов оптимизации САД. При этом учитываются не
только интересы заказчиков, но и следующие факторы:
может ли минимизироваться стоимость САД и достигаться
больший эффект при соответственно высоких инвестиционных
затратах;
могут ли разрабатываться такие структуры САД, которые при
тех же затратах обладают наибольшей надежностью.
Проблема оптимизации сетей связи включает в себя такие подзадачи,
как:
1) адекватную постановку задачи синтеза сети;
2) проблему выбора и размещения элементов сети;
3) декомпозицию исходной модели и интерпретацию полученных
результатов;
4) оптимизацию транспортной (первичной) сети электросвязи при
известных способах организации коммуникационных (вторичных) сетей
электросвязи;
5) синтез сети электросвязи с учетом динамики получения средств
и распределения абонентов сети [68, 69].
Стр.7