Содержание к диссертации
Введение
Глава 1. Принципы построения современных структурированных кабельных систем
1.1 Описание и принципы построения СКС 8
1.2 Термины и основные понятия 11
І.ЗСуществующие принципы проектирования 16
1.4 Системы связи СКС 19
ВЫВОДЫ 26
Глава 2. Методические вопросы разработки оптимальных СКС .
2.1 Общий подход к проектированию 27
2.2 Основные этапы проектирования 30
2.3 Методика диалоговой оптимизации СКС 36
2.3.1 Методические вопросы описания и анализа СКС 40
2.3.2 Технология формулировки задач проектирования СКС 43
2.3.3 Методы и алгоритмы для поиска оптимальных СКС 48
2.3.4. О технологии мультидиалогового моделирования
и оптимизации сетей связи 56
ВЫВОДЫ 60
Глава 3. О задаче построения структурированных кабельных систем .
3.1 Содержательная постановка задачи построения СКС 61
3.2 Математическая модель структуры СКС 66
3.3 Задача выбора способов организации СКС 69
3.4 Построение структурированной кабельной системы 71
3.5 Основные процедуры синтеза СКС 74
3.5.1 Задача оптимизации структуры СКС при заданной структуре
сетей приложений 74
3.5.2 Задача оптимизации структуры СКС как задача
размещения 81
3.5.3 Задача поиска циклического маршрута в гиперсетях 86
ВЫВОДЫ 89
Глава 4. Реализация генетического алгоритма.
4.1 Введение в теорию генетических алгоритмов 90
4.2 Программная реализация классического генетического алгоритма 93
4.3 Программная реализация модифицированного генетического алгоритма 94
4.4 Разработка и реализация принципиально нового генетического алгоритма для возможного использования и сравнения с классическим ГА 98
4.5 Графики, сравнивающие характеристики разрабатываемых алгоритмов 102
Выводы 106
Заключение 107
Литература
- Термины и основные понятия
- Методика диалоговой оптимизации СКС
- Математическая модель структуры СКС
- Программная реализация классического генетического алгоритма
Введение к работе
В диссертации предлагается исследование и разработка моделей и методов оптимизации структур телекоммуникационных систем на примере структурированных кабельных систем. Работа включает в себя формальную и математическую постановку задачи по построению оптимальных сетей связи. Разработаны новые алгоритмы решения такого рода задач.
Растущая сложность проектов и масштабы телекоммуникационных систем заставляют обратить внимание на уровень и качество выполнения работ на всех стадиях реализации проекта и, не в последнюю очередь, на уровень выполнения собственно процесса проектирования. Актуальность данной задачи объясняется тем фактом, что разработать грамотный проект кабельной проводки даже в двух-трех комнатах с несколькими десятками портов является весьма затруднительной процедурой. В тех же ситуациях, когда количество обслуживаемых рабочих мест достаточно большое и в составе телекоммуникационной системы (ТС) имеется магистральная подсистема, то становится очевидна задача оптимизации проектов для нахождения более оптимального варианта их реализации, т.к. ТС является достаточно дорогой в плане финансовых вложений.
Необходимо отметить, что для получения оптимальных способов решения различных задач, возникающих в процессе проектирования, резко возрастает роль применения различных математических методов. Это требует модификации как используемых математических моделей и алгоритмов, так и методик по оптимизации проектируемых телекоммуникационных кабельных систем. Разработка методов оптимизации проектирования ТС и их применение на различных этапах создания ТС должна позволить находить наиболее экономичные и технически правильные решения для ее реализации.
Важнейшей особенностью подобных методик по оптимизации ТС является их системный подход и универсальность, что позволяет использовать сочетание математического аппарата методики с опытом и интуицией проектировщика. Развитие таких методик позволит создать замкнутый цикл по проектированию, строительству и текущей эксплуатации систем и сетей связи на всех уровнях.
Цель диссертационной работы состояла в исследовании и разработке математических моделей ТС, разработке на их основе методики, алгоритмов построения оптимальных кабельных систем, а также анализа и синтеза объектов сетевых структур.
Задачи исследования
Для достижения поставленной цели в работе решаются следующие задачи:
- Разработка структуры и принципов построения системы моделирования сетей и автоматизированного поиска проектных решений.
- Исследование способов представления математических моделей ТС.
- Разработка алгоритмов для задач анализа, синтеза и исследования ТС.
Методы исследования.
Методической основой для решения поставленных задач являются: теория сетей связи, теория графов, теория гиперсетей, исследование операций, применение генетических алгоритмов, методы дискретной оптимизации.
Научная новизна работы и значимость заключается в следующем:
- Разработана математическая модель и формальная постановка задачи оптимизации структурированных кабельных систем.
- Созданы и модифицированы алгоритмы, позволяющие находить оптимальные проектные решения при построении телекоммуникационной системы Практическая ценность результатов.
Разработанная методика и алгоритмы могут быть использованы в проектных организациях для применения методов оптимизации при анализе и синтезе проектных решений, что позволяет сократить сроки и уменьшить трудоемкость проектирования.
Личное участие
Личный вклад автора заключается в разработке методики построения оптимальных сетей СКС, постановки задачи, написании алгоритмов решения задач синтеза и анализа сетей.
Апробация работы Основные результаты работы докладывались и обсуждались на российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск, 2005 г. А также на научных семинарах отдела Телекоммуникационных систем ИВМ и МГ СОРАН. 2002 г. - 2005 г.
Публикации
По теме диссертации опубликовано 7 печатных работ.
Основные положения представленные к защите
- Новая математическая модель СКС на основе гиперсети.
- Методика разработки проектных решений.
- Обобщенная задача оптимизации СКС.
- Генетический алгоритм, используемый для решения задачи синтеза СКС.
Структура и объём работы
Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы, содержащего 66 источников. Общий объем работы - 164 страниц. Основной текст диссертации изложен на 107 страницах и включает 2 таблицы, 16 рисунков, 4 графика.
В первой главе были рассмотрены существующие принципы построения современных структурированных кабельных систем. Было приведено описание основных элементов. Были обозначены общие задачи оптимизации, возникающие при проектировании. Вторая глава посвящена методическим вопросам разработки оптимальных СКС. Развит системный подход к моделированию и проектированию структурированных кабельных систем.
Предложена методика автоматизации поиска проектных решений для СКС, на основе гиперсетей и применения генетических алгоритмов. Показана применимость мультидиалоговой технологии моделирования и оптимизации для СКС.
В третьей главе ставится содержательная постановка задачи построения СКС. Далее была подробно описана математическая модель структуры СКС. Разработаны алгоритмы, применяемые для решения задач синтеза: определение общей структуры СКС при заданной схеме вторичных сетей; задача оптимизация СКС представленная как задача размещения, поиск оптимального варианта топологии сети типа кольцо .
В четвёртой главе приведена разработка генетических алгоритмов. В ходе разработки модели генетического алгоритма были успешно опробованы следующие приёмы:
• Применение стратегии элитизма
• Применение двух критериев останова одновременно
• Повышение вероятности мутации бита хромосомы
Итогом этой работы стала новая модель, позволяющая улучшить работу алгоритмов, применяемых при решении задач синтеза СКС, описанных в предыдущей главе. Новизной модели является реализация механизма одновременного поиска в направлении нескольких экстремумов. Было проведено сравнение характеристик эффективности работы исследуемых алгоритмов.
Термины и основные понятия
В данной работе не ставится задача по разработке новой терминологии структурированных кабельных систем, однако, существование различных стандартов диктует необходимость установить однозначное соответствие между понятиями, характерными для СКС.
Для решения подобной задачи целесообразно рассмотреть модели кабельных систем. В качестве основного материала, отражающего такие модели, соответственно, содержащего необходимый набор терминов на английском языке, использован справочник по стандартам СКС[52]. Аналогичные отечественные модели и термины заимствованы из [49, 50, 51, 53,62].
1. Структура СКС Под структурой СКС понимают модель построения системы из функциональных элементов и подсистем. Данный раздел определяет также интерфейсы точки для подключения терминального оборудования к структурированной системе и самой СКС - к сети общего пользования. Группы функциональных элементов образуют подсистемы СКС. Пример структуры СКС приведен на рис. 1.1.
2. Функциональные элементы СКС Структурированная кабельная система - среда передачи электромагнитных сигналов - состоит из элементов - кабелей и разъемов. Кабели, оснащенные разъемами и проложенные по определенным правилам, образуют линии и магистрали. Линии, магистрали, точки подключения и коммутации составляют функциональные элементы СКС. В американском стандарте к функциональным элементам относят два типа кабелей, три типа помещений, элемент конструкции здания и документацию телекоммуникационной инфраструктуры. В международных /европейских и американских стандартах используется разная терминология. Отличия показаны в таблице 1.
Международные I европейские стандарты подразделяют СКС на восемь функциональных элементов, американский - на семь. Только два из них совпадают. В первом случае функциональные элементы составляют среду передачи, то есть собственно структурированную кабельную систему. Это позволяет выделить подсистемы и провести точные границы между ними.
Во втором в состав функциональных элементов не вошла магистраль комплекса и все интерфейсы СКС и добавлены помещения, элементы зданий и система документирования. Это приводит к путанице и смешиванию понятий в технической литературе, проспектах производителей и документации, создаваемых по американской модели.
3. Подсистемы СКС Международные / европейские стандарты подразделяют СКС на три подсистемы: магистральная подсистема комплекса, магистральная подсистема здания, горизонтальная подсистема.
Магистральная подсистема комплекса включает магистральные кабели комплекса, механическое окончание кабелей (разъемы) в РП комплекса и РП здания и коммутационные соединения в РП комплекса. Магистральные кабели комплекса также могут соединять между собой распределительные пункты зданий.
Магистральная подсистема здания включает магистральные кабели здания, механическое окончание кабелей (разъемы) в РП здания и РП этажа, а также коммутационные соединения в РП здания. Магистральные кабели здания не должны иметь точек перехода.
Горизонтальная подсистема включает горизонтальные кабели, механическое окончание кабелей (разъемы) в РП этажа, коммутационные соединения в РП этажа и телекоммуникационные разъемы. В горизонтальных кабелях не допускается разрывов. При необходимости допускается одна точка перехода. Все пары и волокна телекоммуникационного разъема должны быть подключены. Телекоммуникационные разъемы не являются точками администрирования. Не допускается включения активных элементов и адаптеров в состав СКС.
Абонентские кабели для подключения терминального оборудования не являются стационарными и находятся за рамками СКС. Однако стандарты определяют параметры канала, в состав которого входят абонентские и сетевые кабели.
4. Распределительные пункты размещаются в телекоммуникационных помещениях и аппаратных. Телекоммуникационные помещения предназначены для установки панелей и шкафов, сетевого и серверного оборудования, обслуживающих весь или часть этажа. Аппаратные выделяют для телекоммуникационного оборудования, обслуживающего пользователей всего здания (например, УАТС, мультиплексоры, серверы) и размещения РП здания / комплекса. Панели / шкафы и оборудование РП этажа, совмещенные с РП здания / комплекса, также могут находиться в помещении аппаратной.
5. Интерфейсы СКС это гнездовые разъемы каждой из подсистем, обеспечивающие подключение оборудования и кабелей внешних служб методом подключения или коммутации. Для подключения к СКС достаточно одного сетевого кабеля. В варианте коммутации используют сетевой и коммутационный кабель и дополнительную панель.
Методика диалоговой оптимизации СКС
Данный раздел посвящен разработке методики получения оптимальных проектных решений для СКС. В настоящее время вопросы оптимизации рассматривались применительно к крупным техническим объектам и системам телекоммуникаций в частности. Были проведены также исследования по разработке диалоговых систем проектирования и планирования сетей связи. В процессе работы над проектом СКС в широком смысле этого термина могут быть с успехом использованы приёмы и методики, такие как сетевое планирование, линейное программирование. Но несмотря на это создание оптимальной СКС довольно сложная задача, а выше обозначенные методы нуждаются в дальнейшей разработке. В связи с этим предлагается методика решения задач на графах и гиперсетях моделирующих СКС, а также использующая генетические алгоритмы, для задач минимизации капитальных затрат на проектирование и строительство СКС.
В данной работе сделана попытка рассмотреть основные аспекты по проблеме решения прикладных задач в области построения СКС. В частности, предлагается прохождение всех этапов решения прикладной задачи, от формулировки цели до получения реально работающих алгоритмов. На рисунке 2.2 приведена схема методики моделирования и решения задач анализа и синтеза сложных систем. Методика состоит из трёх частей. В первой рассматриваются методологические вопросы описания и моделирования сетей электросвязи. Во второй части рассматриваются методические проблемы декомпозиции задачи и разработка процесса решения прикладной задачи. В третьей части рассматривается реализация конкретных алгоритмов по оптимизации построения СКС. В основном проблема построения СКС определяется следующими обстоятельствами:
Развитие СКС в первую очередь определяется потребностью пользователей в том или ином виде сервиса телекоммуникационных услуг (как-то телефония, передача данных, телевидение и т.д.) Это обуславливает тип и структуру СКС для данного здания или группы зданий. Причем мы будем говорить о трёх вероятных типах способов организации СКС. A) СКС построенная по так называемой классической радиальной схеме с использованием симметричных электрических кабелей и оптических кабелей. Б) СКС построенная только на оптическом кабеле, с кольцевой топологией при организации магистрали. B) СКС предыдущих вариантов в комплексе использующие радиоканальные сети.
Схемы А и Б позволяют организовать почти полный спектр телекоммуникационных услуг. Схема Б даёт определенный выигрыш по пропускной способности и значительно сокращает количество кроссовых на этажах. Но схема А довольно часто позволяет более гибко подходить к распределению ресурсов сети согласно требуемому сервису услуг, что позволяет достигать минимизации затрат. Вариант В используется в основном там, где необходимы связи с движущимися объектами.
Для решения задачи оптимизации построения структурированных кабельных систем применим методику, позволяющую в целом провести анализ задачи, осуществить её формальную и математическую постановку и применить конкретные оптимизационные алгоритмы по размещению оборудования, трассировки для выше перечисленных схем. Далее приводится основная модель структурированных кабельных систем и методика, по которой будет строится вся дальнейшая работа.
Рассмотрим методологические вопросы исследования и синтеза структур СКС. Прежде всего представляют интерес задачи, возникающие при анализе и синтезе сетей, связанные с применением методов теории графов, теории гиперсетей. Данная методика опирается на решение следующих задач: Разработка методов оценки параметров сетей и создание на базе полученных результатов упрощённых моделей сетей.
Разработка эффективных методов для автоматического анализа и синтеза структуры сетей связи с оптимальной топологией и с учетом совокупности задаваемых ограничений.
Исследование проблемы обеспечения: эффективности, качества, надёжности структурированных кабельных систем. Морфологическое описание СКС 1 .Элементы сетей: пункты связи (узлы): коммутационное оборудование двух основных разновидностей - информационные розетки и коммутационные панели; технические помещения: аппаратные и кроссовые.
Линии сетей: кабели горизонтальной, внутренней, внешней подсистемы, шнуры и т.п. 2. Структуры сетей: горизонтальная подструктура; внутренняя подструктура; внешняя подструктура. Общая структура СКС, определяемая всеми тремя подсистемами.
Математическая модель структуры СКС
В качестве математической модели СКС будем использовать гиперсеть описанную в [42,43]. Одним из основных понятий у нас будет фигурировать гиперсеть с иерархической вторичной сетью. Формально гиперсеть можно определить шестёркой AS = (X, V, R, Р, F,W) Абстрактной гиперсетью AS назовём совокупность, включающую такие объекты: X =(xi,..xn)- множество вершин; V=(vi,..,vg)- множество ветвей; R=(ri,..,rm)- множество ребер; Р: V— 2Х- отображение, сопостовляющее каждому элементу reR множество P(v) из X его вершин.Тем самым отображение Р определяет гиперграф PS=(X,V,P). F: R— 2Vps - отображение, сопостовляющее каждому элементу г eR множество P(v) его ветвей. Причём семейство подмножеств ветвей 2Vps содержит такие подмножества, ветви которых составляют связную часть гиперграфа FS=(V, R, F);
Для любого г є R W: г— 2P(F(r))- отображение, сопостовляющее каждому элементу reR подмножество W(r) eP(F(r)) его вершин, где P(F(r)) -множество вершин в PS, инцидентных ветвям F(r) из V .Таким образом, отображение W определяет гиперграф WS=(X, R, W). Абстрактная гиперсеть называется гиперсетью, если для любых v, г принадлежащих V, R P(v) = W(r) = 2. А для любых г из R множество F(r) входящее в V составляет маршрут в графе PS=(X,V).
Таким образом, первичная PS и вторичная сети WS гиперсети S являются графами, a F отображает рёбра WS =(ХД) в маршруты графа PS=(X,V).
Рассмотрим теперь структуру СКС с учетом разделения её на подсистемы. Зададим структурированную кабельную систему гиперсетью N=(X,V,A,B,C), где: Х=(хь„хп)- множество вершин V=(v5..5v) - множество ветвей А=(а,..,а) - множество рёбер внешней магистрали B=(b,..,b) - множество ребер внутренней магистрали С=(с,..,с) - множество ребер горизонтальной магистрали R=A+B+C.
Для полного описания математической модели определим параметры элементов сети различного назначения. Метрические характеристики p(v) - длина участка ситуационной трассы (длины ветвей ve V). гу- длина ребра, г є R стоимостные характеристики: стоимости a(v) строительных работ на единицу длины ветви v; стоимости b(r) монтажных работ на единицу длины ребра. U - затраты на размещение распределительной этажа в і-м пункте. аЧк - стоимость кабельной линии категории к от j -й точки подключения до і -й распределительной этажа, включая стоимость розеточного модуля той же категории. ск - стоимость коммутационного оборудования типа к, включая стоимость ее монтажа. Целевая функция СКС Линейные сооружения: (S) Za(v)p(v) + Zb(r)p(r), ve V, rє R= А+В - стоимость монтажных и строительных работ для магистралей, первое слагаемое определяет затраты на кабельную канализацию и кабельные каналы, а второе на монтаж и стоимость кабеля. Z a„jk, гцк є С - стоимость кабельных линий категории к от j -х точки подключения до і -х распределительных этажа, включая стоимость розеточного модуля той же категории. Определяет затраты на горизонтальную подсистему. Узловые сооружения: d,- суммарные затраты на размещение распределительных этажа в i-x пунктах. Е ск - суммарная стоимость коммутационного оборудования типа к, включая стоимость ее монтажа. U=Zd1 + ZcK
Таким образом, вся сеть будет оцениваться функцией: Q=lP(S)+ U. Следовательно, задача построения оптимальной СКС заключается в следующем: Q- Min При выполнении следующих требований и ограничений
1. rUk є R - кабельные линии типа к меньше верхней оценки длины линии, характеризующей выполнения норм.
2. Прокладка внешней магистрали осуществляется согласно топооснове, сети ситуационных трасс и с учетом существующей канализации.
3. Предполагаемые нагрузки на услуги телефонной связи и передачи данных и других услуг не превышает возможности коммутационного оборудования. Напротив, осуществляется резервирования ресурсов линейных трактов и коммутационного оборудования.
Требуется определить: 1. Число сетевых узлов СКС, их границы влияния и места расположения. 2. Номенклатуру оборудования коммутации. 3. Сеть канализации и кабельных каналов. 4. Тип кабелей. 5. Полную сеть кабельных линий.
Программная реализация классического генетического алгоритма
Главной причиной, мешающей исследовать поверхность многоэкстремальной многопараметрической исследуемой функции, явилось то, что нахождение даже одной точки данной поверхности (вычисление значения приспособленности одной хромосомы) требует временных затрат не менее, чем 0,1-0,15 сек на компьютере класса Intel Pentium4 3,06 GHz. Соответственно, модификация классического ГА велась в направлении достижения скорейшей сходимости в точке глобального экстремума (или близкой к ней) за минимальное число поколений при минимальном количестве особей в поколении. Список конечных изменений классического ГА:
1. Введена стратегия элитизма - при таком подходе хромосома с максимальной приспособленностью в родительском поколении копируется в дочернее поколение без изменений. Данная стратегия позволяет ускорить сходимость ГА, хотя и повышает риск останова ГА в точке локального экстремума.
2. Повышена вероятность мутаций с 10% до 50%
3. Для более полного контроля над механизмом мутаций используется вероятности мутации бита хромосомы - т.е., с вероятностью Р1 хромосома выбирается для мутации и с вероятностью Р2 мутирует каждый бит этой хромосомы.
4. Был введен второй критерий останова, так как критерий об изменении средней приспособленности поколения в пределах 5% оказался недостаточным. Дополнительный критерий работает, основываясь на количестве поколений, за которое приспособленность лучшей особи не менялась в пределах все тех же 5%.
5. Для полного исключения из расчетов нежизнеспособных особей был внедрен механизм, который включается при кроссинговере и мутации хромосомы. Данный механизм проверяет каждый ген хромосомы на то, попадает ли его значение в допустимый интервал для данного параметра функции. В случае, если значение гена выходит за пределы допустимого диапазона, для этого гена запускается процедура повторной мутации. Так происходит до тех пор, пока значение гена не окажется в допустимых пределах данного параметра функции. При тестировании ГА с учетом всех вышеприведенных модификаций были выявлены следующие позиции:
1. ГА сходится в точку глобального экстремума, либо в точку, находящуюся рядом с ней.
2. Скорость сходимости модифицированного ГА составляет приблизительно 40-50 поколений, т.е., за это время достигается точка глобального экстремума.
3. Количество поколений, необходимых для сходимости алгоритма, практически не меняется после того, как количество особей в поколении становится = 60.
Общая схема функционирования модифицированного ГА была представлена выше на рисунке 3. В принципе, данные результаты уже можно было считать вполне удовлетворительными, но в целях дальнейшей оптимизации ГА была решена следующая задача, в рамках которой был разработан совершенно новый ГА, серьезно отличающийся от классического. Совместно с Соловьем С.С. были проведены исследования по созданию нового генетического алгоритма. [12],[ 13]
Основной проблемой модифицированного ГА явилось то, что при использовании стратегии элитизма и относительно небольшом размере популяции особей повышается вероятность того, что ГА остановится в точке локального экстремума, а не глобального. Эксперименты полностью это опасение подтвердили - примерно в 30% случаев модифицированный ГА останавливался в точках локальных экстремумов, не достигая необходимого нам результата. Возникла проблема выхода из локальных экстремумов. Одним из вариантов решения этой проблемы является усиление мутаций, что позволяет выйти из локального экстремума случайным образом. Недостатком данного подхода является то, что мутируют хромосомы неуправляемо, т.е., как правило, мутировавшая хромосома быстро исчезает, не оставляя свои признаки в поколении, т.к. ее приспособленность, как правило, ниже приспособленности хромосомы в локальном экстремуме.
Ключевой идеей новой модификации ГА является то, что необходимо зафиксировать несколько направлений поиска, к разным экстремумам. Для этого необходимо, в рамках стратегии элитизма, сохранять не одну лучшую хромосому, а несколько (4-5, как было установлено впоследствии экспериментально), но не просто несколько лучших, а несколько отличающихся друг от друга лучших. Выбирается процент отличия, фиксируется первая хромосома.
