автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Исследование и разработка моделей и методов оптимизации структур телекоммуникационных систем

На правах рукописи

ГАЛЯМОВ Василий Александрович

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МОДЕЛЕЙ И МЕТОДОВ ОПТИМИЗАЦИИ СТРУКТУР ТЕЛЕКОММУНИКАЦИОННЫХ

СИСТЕМ.

05Л3.17 - теоретические основы информатики

АВТОРЕФЕРАТ

диссертации на соискание учёной степени кандидата технических наук

Новосибирск - 2006

Работа выполнена в Сибирском Государственном Университете Телекоммуникаций и Информатики.

Научный руководитель: доктор физико-математических

наук, профессор ВЛС. Пешков

Официальные оппоненты:

Ведущее предприятие:

доктор технических наук, профессор Носов В.И. кандидат технических наук Деревяшкин ВЖ ОАО Гипросвязь-4, г. Новосибирск

Защита диссертации состоится «21» сентября 2006 г. в 15-00. часов на заседании диссертационного совета Д 219.005.01 в Сибирском Государственном Университете Телекоммуникаций и Информатики по адресу: 630 102, Новосибирск, ул. Кирова, 86

С диссертацией можно ознакомиться в библиотеке СибГУТИ. Автореферат разослан « Д- » г.

Ученый секретарь

диссертационного совета Д219.005.02 к.т.н., доцент /Л7)

Резван И.И.

Общая характеристика работы

Актуальность темы. Растущая сложность проектов и масштабы телекоммуникационных систем заставляют обратить внимание на уровень и качество выполнения работ на всех стадиях реализации проекта и, не в последнюю очередь, па уровень выполнения собственно процесса проектирования. Актуальность данной задачи объясняется тем фактом, что разработать грамотный проект кабельной проводки даже в двух-трёх комнатах с несколькими десятками портов является весьма затруднительной процедурой. В тех же ситуациях, когда количество обслуживаемых рабочих мест достаточно большое и в составе телекоммуникационной системы (ТС) имеется магистральная подсистема, то становится очевидна задача оптимизации проектов для нахождения оптимального варианта их реализации, т.к. ТС является достаточно дорогим в плане финансовых вложений;

Необходимо отметить, что для получения оптимальных способов решения различных задач, возникающих в процессе проектирования, резко возрастают роль применения различных математических методов. Это требует модификации как используемых математических моделей и алгоритмов, так и методик по оптимизации проектируемых ТС. Разработка методов оптимизации проектирования ТС на примере структурированных кабельных систем (СКС) и её применение на различных этапах создания ТС должна позволить находить наиболее экономичные и технически правильные решения для используемого коммутационного оборудования, кабеля и т. д. '■"; ■

•Важнейшей особенностью подобных методик по оптимизации ТС является их системный подход и универсальность, что позволяет использовать сочетание математического аппарата методики с опытом и интуицией проектировщика. Развитие таких методик' позволит создать замкнутый цикл по проектированию, строительству и текущей эксплуатации систем и сетей связи на всех уровнях.

Цель диссертационной работы состояла в исследовании и разработке математических моделей ТС на примере СКС, разработке на их основе методики,

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

Задачи исследования. Для достижения поставленной цели.в работе решаются следующие задачи:

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

Исследование способов представления математических моделей СКС.

Разработка алгоритмов для задач анализа, синтеза и исследования СКС.

Методы исследования. Методической основой для решения поставленных задач являются: теория сетей связи, теория графов, теория гилерсетей, исследование операций, применение генетических алгоритмов, методы дискретной оптимизации.

Основные положения представленные к защите

- Новая математическая модель СКС на основе гиперсети.

- Методика разработки проектных решений.

- Обобщённая задача оптимизации СКС.

- Генетический алгоритм, используемый для решения задачи синтеза СКС.

Научная новизна работы и значимость заключается в следующем:

- Разработана математическая модель и формальная постановка задачи оптимизации структурированных кабельных систем.

- Созданы и модифицированы алгоритмы, позволяющие находить оптимальные проектные решения при построении различных телекоммуникационных систем.

Практическая ценность результатов. Разработанная методика и алгоритмы могут быть использованы в проектных организациях для применения методов оптимизации при анализе и синтезе проектных решений, что позволит сократить сроки и уменьшить трудоёмкость проектирования.

Личное участие. Личный вклад автора заключается в разработке методики построения оптимальных сетей СКС, постановки задачи, написании алгоритмов решения задач синтеза и анализа сетей.

Апробация работы. Основные результаты работы докладывались и обсуждались на российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск, 2005 г., а также на научных семинарах отд. Телекоммуникационных систем ИВМ и МГ СОР АН. 2002 г. — 2005 г.

Публикации. По теме диссертации опубликовано 7 печатных работ.

Структура и объём работы. Диссертационная работа состоит из введения, четырёх глав, заключения, приложения и списка литературы, содержащего 66 источников. Общий объём работы — 167 страниц. Основной текст диссертации изложен на 110 страницах и включает 2 таблицы, 16 рисунков, 4 графика.

Краткое содержание работы

Во введении обоснована актуальность темы диссертации, сформулированы цель, задачи, научная и практическая ценность работы. Обозначен круг вопросов исследования.

В первой главе рассмотрены существующие принципы построения современных структурированных кабельных систем. Приведено описание основных .элементов СКС.

Обозначены общие задачи оптимизации, возникающие при проектировании:

1) Разработка математических моделей для задачи оптимизации структур СКС с.учётом архитектурных и градостроительных факторов.

2) Определение этапов создания кабельных систем для эффективной реализации проектируемых на длительный срок структур.

3) Разработка методов оптимизации СКС.

При этом учитываются не только интересы заказчиков, но и следующие моменты:

- минимизация стоимости СКС и достижения большей ее функциональной эффективности при соответственно высоких затратах;

- разработка таких структур СКС, которые при тех же затратах обладают наибольшей надёжностью.

Проблема оптимизации сетей связи включает в себя следующие подзадачи:

1) Постановка задачи синтеза сети.

2) Проблема выбора и размещения элементов сети.

3) Задача декомпозиции исходной модели

4) Синтез сети с учётом распределения абонентов.

В соответствии со стандартами кабельная система составляет часть инфраструктуры здания (группы зданий). Общие принципы проектирования СКС подразумевают наличие у структурированных кабельных систем следующих свойств:

• Универсальность - возможность использования однотипных каналов для передачи сигналов различных систем (данные, голос, видео);

• Совместимость со стандартным активным оборудованием любых производителей;

• Избыточность - наличие достаточного количества резервных каналов связи, необходимых для расширения системы в процессе эксплуатации;

• Гибкость - простота и удобство обслуживания системы при внесении изменений в ее конфигурацию;

• Надежность - способность системы сохранять рабочие параметры в заданных диапазонах в течение всего срока эксплуатации / гарантийного срока;

Далее показаны' различные варианты топологического построения СКС. Дано краткое описание существующих систем связи, применяемых в настоящее время при организации СКС.

Существующая практика проектирования универсальных кабельных систем в нашей стране осуществляется следующим образом. Сначала' происходит формирование требований. Объект (объекты) обследуются, идет сбор и анализ данных об объекте. Формируется требования пользователей к системе.

При выборе места расположения аппаратной(здесь находятся наиболее важные сетевые устройства: УПАТС, серверы, коммутаторы и др.) крупных сетей, обслуживающих одновременно несколько зданий, при прочих равных условиях предпочтительным является её организация в центральной части 'обслуживаемой

территории. Это делается для того, чтобы минимизировать среднюю длину кабеля. Тоже самое относится и к кроссовым. Если на этаже многоэтажного здания предусмотрены несколько кроссовых этажа, то желательно, чтобы все они обслуживались разными стояками. В этом случае удаётся избежать на данном этаже горизонтальной прокладки кабелей внутренней подсистемы магистралей СКС и существенно повысить живучесть кабельной системы. В тех ситуациях, когда в силу каких либо причин данное условие не выполняется, допускается, чтобы кроссовая этажа была подключена к кроссовой здания транзитом через другие кроссовые этажа

Для каждого этажа здания намечаются места установки коммутационных узлов, используя при необходимости прочие варианты строительной реализации: ниши и шкафы. Далее составляют'схему сети горизонтальной подсистемы для каждого этажа в отдельности. ,

Для кабельных трасс подсистемы внешних магистралей составляют'схему кабельной канализации на основе схемы магистральной сети. Число каналов канализации на отдельна участках определяют исходя из количества и ёмкости кабелей.

Итак; в новых разрабатываемых автоматизированных системах проектирования должны присутствовать алгоритмы прокладки кабеля, определяющие оптимальный путь между узлами сети, учитывающие заполняемость кабель - каналов, осуществляющие при необходимости прокладку силовых и информационных кабелей в разных лотках, а также позволяющие рассчитать стоимость системы в реальном времени и оценить множество альтернативных наборов кабельного оборудования и выбрать из них наиболее лучший по критерию стоимость — качество.

Вторая глава посвящена методическим вопросам разработки оптимальных СКС. Развит системный подход к оптимизации моделирования и проектирования структурированных кабельных систем.

Проектирование СКС представляет собой весьма сложную проблему. Процесс проектирования сети целесообразно разделить на несколько этапов:

1. Постановка задачи, в результате которой выбираются критерии планирования сети и формируются исходные данные, формализованные по заранее заданным правилам.

2. Краткосрочное и долгосрочное прогнозирование исходных данных и выбор номенклатуры услуг.

3. Декомпозиция задачи, Состоящая в постановке вопросов по архитектурной и телекоммуникационной фазе проектирования.

4. Разработка возможных сценариев по созданию или развитию фрагмента телекоммуникационной системы,

5. Анализ возможных сценариев с учетом финансовых, технических и иных ограничений; выбор тех сценариев, которые могут быть реализованы.

6. Решение поставленной задачи путем использования соответствующих математических методов.

7. Интерпретация результатоврешения с учетом не формализуемых ограничений и составление необходимой проектной документации.

В работе предложена методика автоматизации поиска проектных решений для СКС, на основе теории гиперсетей и применения генетических алгоритмов. Показана применимость мультидиалоговой технологии моделирования и оптимизации для СКС.

В третьей главе ставится содержательная постановка задачи построения СКС. В общем виде задача сформулирована следующим образом. Пусть известны:

1. Границы района проектируемой сети.

2. Типы застроек в этом районе и типовые планы зданий.

3. Заявки на услуги связи (телефонная связь, передача данных., кабельное телевидение), виды возможных приложений. .

4. Типы кабелей и коммутационного оборудования (выпускаемые производством на день проектирования).

5. Стоимостные характеристики: кабелей, систем передачи, коммутационного оборудования, подготовки помещений для станций и узлов, строительных работ по канализации (если отсутствует телефонная) и пр.

6. Нормы на категории и длины кабелей и шнуров СКС.

7. Возможные места расположения коммутационного и другого оборудования.

8. Емкость телефонных станций» пропускная способность ЛВС и требование на конфиденциальность.

9. Сеть ситуационных трасс и существующая кабельная канализация для внешних магистралей.

Требуется определить:

1. Число сетевых узлов.

2. Номенклатуру оборудования.

3. Места расположения аппаратных и кроссовьтх, а также коммутационного оборудования и соответствующие им границы влияния.

4. Сеть канализации.

5. Трассы горизонтальной и магистральных подсистем.

6. Типы коммутационного оборудования и кабеля, их стоимость прокладки.

При следующих требованиях и ограничениях:

- минимизация капитальных суммарных затрат на сетевые узлы и линейные сооружения.

достаточная для всех вторичных сетей пропускная способность, удовлетворение всех каналов электросвязи определённым характеристикам (норма затухания, ёмкость)

ограниченная в пределах стандартных градаций ёмкость коммутационного оборудования, а также удовлетворение ёмкости систем передач заданным потребностям абонентов сети.

Анализ текущих затрат по всем вариантам реализации СКС показал, что эти затраты в основном зависят от капитальных вложений. Следовательно, при оптимизации СКС достаточно в целевую функцию включить только капитальные затраты.

В свою очередь изменение структуры линейных сооружений сети СКС приводит к изменению лишь некоторых составляющих капитальных вложения на строительство сети СКС в полном объёме. Общая величина капвложений на строительство сети определяется по формуле;

Scemu = ^кабАБ.еети S*

где S0g - стоимость приобретения и монтажа оборудования коммутации.

S каб.сети - общая стоимость приобретения, прокладки и монтажа кабелей сети СКС.

Sk - общая стоимость кабельных каналов, канализации, земляных работ, оборудования технических помещений на участках сети, по которым проходят трассы кабелей сети СКС.

Окончательно содержательную постановку задачи построения оптимальной структурированной кабельной системы можно сформулировать следующим образом:

Требуется, найти структуру СКС такую, чтобы капитальные затраты на ее строительство были минимальными и при этом были выполнены все выше перечисленные условия и ограничения.

Далее была подробно описана математическая модель структуры СКС -гиперсеть. Пример гиперсети на рисунке 1.

Структура СКС рассматривается с учётом разделения её на подсистемы. Структурированная кабельная система задается гиперсетью N=(X,V,A,B>C), где: Х^хь-.х,,)- множество вершин V=(v,,.,v) - множество ветвей А=(а,..,а) — множество рёбер внешней магистрали B=(b,..,b) - множество рёбер внутренней магистрали С=(с,..,с) — множество рёбер горизонтальной магистрали R= А+В+С.

Рис.1. Пример простейшей гиперсети.

Дня полного описания математической модели определены параметры её элементов.

Метрические характеристики

Для каждой ветви уе V определяется р(у) - длина участка ситуационной трассы; для каждого ребра, г е II г,]- длина ребра Стоимостные характеристики:

Стоимости а(у) строительных работ на единицу длины ветви V;

стоимости Ь(г) монтажных работ на единицу длины ребра;

<1; - затраты на размещение распределительной этажа в ¡-м пункте;

аук — стоимость кабельной линии категории к от ) -Й точки подключения до 1 -й

распределительной этажа, включая стоимость розеточного модуля той же

категории.

с к — стоимость коммутационного оборудования типа к, включая стоимость её

• • < 5 'V л • •; 1I I ' !

монтажа.

Целевая функция Линейные сооружения:

2д(у)р(у) + £Ь(г)р(г), уе V, ге К= А+В - стоимость монтажных и строительных работ для магистралей, первое слагаемое определяет затраты на

кабельную канализацию и кабельные каналы, а второе на монтаж и стоимость кабеля.

2 ауь , гук е С — стоимость кабельных линий категории к от 3 -х точки подключения до 1 -х распределительных этажа, включая стоимость розеточного модуля той же категории. Определяет затраты на горизонтальную подсистему. Узловые сооружения:

суммарные затраты на размещение узлов сети на этаже в 1-х пунктах. £ ск — суммарная стоимость коммутационного оборудования типа к, включая стоимость её монтажа.

Таким образом, вся сеть будет оцениваться функцией: 0=4^(5)+ и.

^ • . ^

Следовательно, задача построения оптимальной СКС заключается в минимизации суммарных затрат

При выполнении следующих требований и ограничений на синтез СКС.

1. Длины г^ е К - кабельных линий типа к меньше верхней оценки длины линии, характеризующей- выполнения норм по затуханию.

2. Прокладка внешней магистрали осуществляется согласно топооснове, сети ситуационных трасс и с учётом существующей канализации.

3. Предполагаемые нагрузки на услуги телефонной связи и передачи данных и других услуг не превышают возможности коммутационного оборудования. Напротив, осуществляется резервирования ресурсов линейных трактов и коммутационного оборудования.

Требуется определить:

1. Число сетевых узлов СКС, их границы влияния и места расположения.

' л .

2. Номенклатуру оборудования коммутации.

3. Сеть канализации и кабельных каналов.

4. Тип кабелей.

5. Полную сеть кабельных линий.

В работе описаны алгоритмы для задач построения СКС: 1) Задача построения кабельной канализации.

12

2) Задача трассировки, определения типа и ёмкости кабельных линий.

3) Задача определения мест расположения сетевых узлов, кроссовых и границ их влияния.

Разработаны алгоритмы, применяемые для решения задач синтеза:

определение общей структуры СКС при заданной схеме вторичных сетей; задача

оптимизация СКС представленная как задача размещения, поиск оптимального

варианта топологии сети типа 'кольцо'.

Подробно рассмотрена актуальная задача оптимизации структуры СКС при

заданной схеме вторичных сетей. Математическая постановка задачи:

Требуется построить гиперсеть S=(PS,PU,WS,F,W) такую, чтобы минимизировать

следующий функционал:

Q(S)=I Za(v)p(v) + (d(u))p(u) +Ic(d(z)), ueU veF(u) ueU zeZ

где d(u)=£d(r) p(u)=£p(v)

r eW'(u) ve F(u)

Первое слагаемое в выражении для Q(S) представляет собой стоимость

строительных работ при создании сети связи (т. е. гиперсети S) , второе -

стоимость монтажных работ, третье - стоимость оборудования коммутации.

Пусть заданы графы PS =(X,V), WS=(Y,R),

длины ветвей ve V — p(v);

для каждого ребра г е R его ёмкость d(r);

стоимости a(v) строительных работ на единицу длины ветви v;

стоимости e(d(u)) монтажных работ на единицу длины ребра графа PU как

функция его ёмкости (под ёмкостью ребра графа PU понимается сумма ёмкостей

тех рёбер из графа WS трассы которых проходят по этому ребру);

c(d(z)) - стоимость оборудования (аппаратура коммугации), установленного в

вершине графа PU как функция ёмкости этой вершины(ёмкость вершины — это

сумма ёмкостей рёбер графа PU, инцидентных этой вершине).

Граф PS можно интерпретировать как схему ситуациоштых трасс, в которой

отражена существующая сеть кабельной канализации и инженерных сооружений

для организации линий связи, т.е. вершины соответствуют, например, узлам

линейных сооружений различных подсистем, колодцам различного назначения, кабельным вводам в здание и другим возможным объектам, а рёбра - участкам улиц, возможным трассам прокладки кабеля в здании, кабельной канализации и Др.

- схема пучков соединительных линий: его вершинам соответствуют коммутационные станции и узлы, а рёбра - пучки соединительных линий между ними.

Ри — схема кабельной канализации и схема кабелей. Вершины

соответствуют местам в которых оканчиваются кабели (т.е. местам, в которых

осуществляется сращивание нескольких кабелей или ввод кабеля в

коммутационную станцию или узел), а рёбра кабелям.

Отображение W задаёт траекторию участков кабельной канализации и

кабелей. Каждое г = (х,у)еИ. является цепью между вершинами х,у в графе Ри с

весами рёбер р(и), где р(и)=£р(у).

В рассматриваемой задаче осуществляется трассировка рёбер геЯ

непосредственно в РЭ, а затем на последнем этапе восстанавливается граф Ри, так

как можно считать, что граф Р11 является частью графа РБ и трассировочная

функция К- тождественная, т.е. для любых и <= 0 Р(и) = и.

Таким образом, рассматривается следующая задача:

МПЭД(8)=1 2>(у)р(у) + Ее (<3(и))р(и) +£с(ОД)} , где

иеи уеР(и) иеи 7.^2.

<1(и)=Хс1(г) р(и)=£р(у)

г еУ/'^и) уе Р(и)

р(у)>0; а(и)>=0; е(<3(и))>0; с(с1(г))>=0; с3(г)>0;

Поставленная задача относится к числу ИР- полных задач.

Для ее решения разработан алгоритм, дающий приближенное решение этой задачи.

Схема алгоритма представлена на рисунке 2. Алгоритм итеративен, количество итераций к = | И 1. Зафиксируем одно ребро г графа

2. С помощью ГА найдём псевдооптимальный маршрут р.(г) на одном из остовов РБ.

3. Запишем ц (г) в Ри.

4. Меняем характеристики всех рёбер графа РЯ, которые вошли в маршрут ц (г), так чтобы для последующих маршрутов стоимость а(у) этих рёбер не учитывалась.

5. Повторяем эти действия (1-4) для следующего г.

Объединение ц (г) даст нам искомый Ри. Это позволит полностью определить искомую гиперсеть минимальной стоимости.

Рис.2. Общая схема алгоритма

Результатом проведённого исследования явилось успешное применение данного генетического алгоритма для решения задачи оптимизации структуры построения оптимальной линейной первичной сети. В процессе нахождения оптимальных параметров генетического алгоритма были внесены следующие изменения в модель классического ГА, позволившие достичь лучших результатов по сравнению с классической моделью: • Применение стратегии элитизма.

♦ Одновременный поиск в направлении нескольких экстремумов. Практическим результатом проделанной работы является разработанное программное приложение, позволяющее решать поставленную задачу за приемлемое время.

Общая схема функционирования модифицированного ГА показана на рисунке 3.

о>

Рис.3. Общая схема функционирования модифицированного генетического алгоритма.

В четвёртой главе приведена разработка генетических алгоритмов. В ходе разработки модели генетического алгоритма были успешно опробованы следующие приёмы:

• Применение стратегии элитизма

♦ Применение двух критериев останова одновременно

• Повышение вероятности мутации бита хромосомы

Итогом этой работы стала новая модель, позволяющая улучшить работу алгоритмов, применяющихся при решении задач синтеза СКС, описанных в предыдущей главе. Новизной модели является реализация механизма одновременного поиска в направлении нескольких экстремумов.

Было проведено сравнение характеристик эффективности работы исследуемых алгоритмов.

Г 120

100

.....

■ГА

♦мод ГА м коеГА || ~ Перебор

. 5 10 15 20 25 30 35 40 45

График 1. Сравнение усредненных значений процентов сходимости в .= зависимости от количества вершин.

Данный график является итоговой характеристикой эффективности работы разработанных алгоритмов, для наглядности на график также помещена кривая алгоритма «полный перебор». На графике отчетливо видно преимущество нового ГА над другими алгоритмами, причем, он менее чувствителен к увеличению размерности входного графа.

В приложении приведены фрагменты исходных текстов разработанной программы.

Основные результаты и выводы

Основные результаты диссертационной работы состоят в следующем:

1. Проведен анализ современных требований, предъявляемых к проектируемым структурированным кабельным системам

2. Показано применимость гиперсетей для моделирования СКС, доказывающая универсальность модели для многих объектов сетевых структур.

3. Предложена методика поиска проектных решений по построению оптимальных СКС, на основе гиперсетей и применения генетических алгоритмов.

4. Приведена системная постановка задачи синтеза СКС.

5. Разработаны алгоритмы для задач синтеза СКС.

6. В ходе разработки получен новый генетический алгоритм, успешно применимый к решению основных задач синтеза.

По теме диссертации опубликованы следующие работы:

1. Галямов В.А. Задача синтеза первичной сети электросвязи города. Российская научно-техническая конференция. - Новосибирск, СибГУТИ, 2005. с. 218-220.

2. Галямов В.А., Соловей С.С. Генетический алгоритм задачи размещения структурированной кабельной системы здания, - // Научное обозрение. -М.¡Издательство "НАУКА", 2005. -№5. -С.23-25.

3. Галямов В .А., Соловей С.С. Задача синтеза первичной сети электросвязи города. // Научное обозрение. - М.: Издательство "НАУКА", 2005. -№5.-С.29-36. „

4. Галямов В.А. О задаче оптимизации построения первичной сети связиУ/Труды ИВМ и МГ. Сер. Информатика. - Новосибирск, 2005. -№5. - С. 68-79

5. Галямов В.А. О задаче построения структурированных кабельных систем. -Новосибирск: Изд-во Новосиб. Ун-та, 2005. - 36 с. (Препринт)

6. Галямов В.А Соловей С.С. Генетический алгоритм задачи размещения структурированной кабельной системы здания.//Вестник НГУ. Сер. Информационные технологии.- Новосибирск, 2005. - 4 с.

7. Галямов В.А. Попков В.К. Задача синтеза первичной сети электросвязи города.// Вестник связи . Москва , 2005. - № 12 .С. 59-60.

Отпечатано в ЗАО РИЦ «Прайс-курьер», т. 330-72-02, Тираж 60 экз., заказ 395 от 10.07.2006 г.

Введение.

Глава 1. Принципы построения современных структурированных кабельных систем

1.1 Описание и принципы построения СКС.

1.2 Термины и основные понятия.

1 .ЗСуществующие принципы проектирования

1.4 Системы связи СКС.

ВЫВОДЫ.

Глава 2. Методические вопросы разработки оптимальных СКС.

2.1 Общий подход к проектированию.

2.2 Основные этапы проектирования.

2.3 Методика диалоговой оптимизации СКС.

2.3.1 Методические вопросы описания и анализа СКС.

2.3.2 Технология формулировки задач проектирования СКС.

2.3.3 Методы и алгоритмы для поиска оптимальных СКС.

2.3.4. О технологии мультидиалогового моделирования и оптимизации сетей связи.

ВЫВОДЫ.

Глава 3. О задаче построения структурированных кабельных систем.

3.1 Содержательная постановка задачи построения СКС.

3.2 Математическая модель структуры СКС.

3.3 Задача выбора способов организации СКС.

3.4 Построение структурированной кабельной системы.

3.5 Основные процедуры синтеза СКС.

3.5.1 Задача оптимизации структуры СКС при заданной структуре сетей приложений.

3.5.2 Задача оптимизации структуры СКС как задача размещения.

3.5.3 Задача поиска циклического маршрута в гиперсетях.

ВЫВОДЫ.

Глава 4. Реализация генетического алгоритма.

4.1 Введение в теорию генетических алгоритмов.

4.2 Программная реализация классического генетического алгоритма.

4.3 Программная реализация модифицированного генетического алгоритма.

4.4 Разработка и реализация принципиально нового генетического алгоритма для возможного использования и сравнения с классическим ГА.

4.5 Графики, сравнивающие характеристики разрабатываемых алгоритмов.

ВЫВОДЫ.

В диссертации предлагается исследование и разработка моделей и методов оптимизации структур телекоммуникационных систем на примере структурированных кабельных систем. Работа включает в себя формальную и математическую постановку задачи по построению оптимальных сетей связи. Разработаны новые алгоритмы решения такого рода задач.

Растущая сложность проектов и масштабы телекоммуникационных систем заставляют обратить внимание на уровень и качество выполнения работ на всех стадиях реализации проекта и, не в последнюю очередь, на уровень выполнения собственно процесса проектирования. Актуальность данной задачи объясняется тем фактом, что разработать грамотный проект кабельной проводки даже в двух-трех комнатах с несколькими десятками портов является весьма затруднительной процедурой. В тех же ситуациях, когда количество обслуживаемых рабочих мест достаточно большое и в составе телекоммуникационной системы (ТС) имеется магистральная подсистема, то становится очевидна задача оптимизации проектов для нахождения более оптимального варианта их реализации, т.к. ТС является достаточно дорогой в плане финансовых вложений.

Необходимо отметить, что для получения оптимальных способов решения различных задач, возникающих в процессе проектирования, резко возрастает роль применения различных математических методов. Это требует модификации как используемых математических моделей и алгоритмов, так и методик по оптимизации проектируемых телекоммуникационных кабельных систем. Разработка методов оптимизации проектирования ТС и их применение на различных этапах создания ТС должна позволить находить наиболее экономичные и технически правильные решения для ее реализации.

Важнейшей особенностью подобных методик по оптимизации ТС является их системный подход и универсальность, что позволяет использовать сочетание математического аппарата методики с опытом и интуицией проектировщика. Развитие таких методик позволит создать замкнутый цикл по проектированию, строительству и текущей эксплуатации систем и сетей связи на всех уровнях.

Цель диссертационной работы состояла в исследовании и разработке математических моделей ТС, разработке на их основе методики, алгоритмов построения оптимальных кабельных систем, а также анализа и синтеза объектов сетевых структур.

Задачи исследования

Для достижения поставленной цели в работе решаются следующие задачи:

- Разработка структуры и принципов построения системы моделирования сетей и автоматизированного поиска проектных решений.

- Исследование способов представления математических моделей ТС.

- Разработка алгоритмов для задач анализа, синтеза и исследования ТС.

Методы исследования.

Методической основой для решения поставленных задач являются: теория сетей связи, теория графов, теория гиперсетей, исследование операций, применение генетических алгоритмов, методы дискретной оптимизации.

Научная новизна работы и значимость заключается в следующем:

- Разработана математическая модель и формальная постановка задачи оптимизации структурированных кабельных систем.

- Созданы и модифицированы алгоритмы, позволяющие находить оптимальные проектные решения при построении телекоммуникационной системы

Практическая ценность результатов.

Разработанная методика и алгоритмы могут быть использованы в проектных организациях для применения методов оптимизации при анализе и синтезе проектных решений, что позволяет сократить сроки и уменьшить трудоемкость проектирования.

Личное участие

Личный вклад автора заключается в разработке методики построения оптимальных сетей СКС, постановки задачи, написании алгоритмов решения задач синтеза и анализа сетей.

Апробация работы Основные результаты работы докладывались и обсуждались на российской научно-технической конференции «Информатика и проблемы телекоммуникаций», Новосибирск, 2005 г. А также на научных семинарах отдела Телекоммуникационных систем ИВМ и МГ СОРАН. 2002 г. - 2005 г.

Публикации

По теме диссертации опубликовано 7 печатных работ.

Основные положения представленные к защите Новая математическая модель СКС на основе гиперсети. Методика разработки проектных решений. Обобщенная задача оптимизации СКС.

Генетический алгоритм, используемый для решения задачи синтеза СКС.

Структура и объём работы

Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы, содержащего 66 источников. Общий объем работы - 164 страниц. Основной текст диссертации изложен на 107 страницах и включает 2 таблицы, 16 рисунков, 4 графика.

выводы

В данной главе приведена разработка генетических алгоритмов. В ходе разработки модели генетического алгоритма были успешно опробованы следующие приемы:

• Применение стратегии элитизма

• Применение двух критериев останова одновременно

• Повышение вероятности мутации бита хромосомы

Итогом этой работы стала новая модель, позволяющая улучшить работу алгоритмов, применяющихся при решении задач синтеза СКС, описанных в предыдущей главе. Новизной модели является реализация механизма одновременного поиска в направлении нескольких экстремумов. Было проведено сравнение характеристик эффективности работы исследуемых алгоритмов.

ЗАКЛЮЧЕНИЕ

В ходе проделанной работы были решены все задачи, которые было необходимо решить для достижения поставленной цели.

Предложена методика поиска проектных решений по построению оптимальных СКС, на основе гиперсетей и применения генетических алгоритмов.

Показана возможность применения диалоговой технологии моделирования и оптимизации.

Приведена системная постановка задачи синтеза СКС.

Разработаны алгоритмы для задач синтеза СКС.

- В ходе разработки получена новая модель генетического алгоритма, в которой были успешно использованы некоторые подходы для улучшения в работе ГА,

• Использование одновременно двух критериев останова алгоритма

• Применение стратегии элитизма

• Поиск по нескольким экстремумам одновременно

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

1. Алиев И.И., Казанский С.Б. Кабельные изделия. М.: РадиоСофт, 2002.224 с.

2. Аппаратура сетей связи: справочные материалы по проектированию. 4.1, Ч.2.- М.: Гипросвязь, 1993. 133 с.

3. Батищев Д.И, Коган Д.И. Вычислительная сложность экстремальных задач переборного типа. Нижний Новгород: Нижегородский госуниверситет,1994. - 180 с.

4. Батищев Д.И Методы оптимального проектирования. М.: Радио и связь, 1984. -160 с.

5. Батищев Д.И. Поисковые методы оптимального проектирования. М.: «Сов. Радио», 1975. - 216 с.

6. Булгак В.Б., Варакин JI.E., Ивашкевич Ю.К., Москвитин В.Д.,Осипов В.Г. Концепция развития связи Российской федерации. М.: Радио и связь, 1995, 224 с.

7. Варакин J1.E. Экономика, связь, развитие общества: макроэкономические закономерности развития связи// Электросвязь, 1994. № 1.

8. Великанов K.M. Сети связи с беспроводным доступом. М.: Эко-Трендз, 1999, №12.

9. Верник С.М., Кочановский JI.H. Оптимизация линейных сооружений связи. М.: Радио и связь, 1984. - 136 с.

10. Габасов Р. Конструктивные методы оптимизации.Ч.З.:Сетевые задачи. -Минск, Из-во «Университетское», 1986. 224 с.

11. Галямов В.А. Задача синтеза первичной сети электросвязи города. Российская научно-техническая конференция. Новосибирск, СибГУТИ, 2005. с. 218-220.

12. Галямов В.А., Соловей С.С. Генетический алгоритм задачи размещения структурированной кабельной системы здания. // Научное обозрение. -М.:Издательство "НАУКА", 2005. -№5. -С.23-25.

13. Галямов В. А., Соловей С.С. Задача синтеза первичной сети электросвязи города. // Научное обозрение. М.: Издательство "НАУКА", 2005. -№5.-С.29-36.

14. Галямов В. А. О задаче оптимизации построения первичной сетисвязи //Труды ИВМ и МГ. Сер. Информатика. Новосибирск, 2005. -№5. - С. 66-78.

15. Галямов В.А. О задаче построения структурированных кабельных систем. Новосибирск: Изд-во Новосиб. Ун-та, 2005. - 36 с. (Препринт)

16. Галямов В.А Соловей С.С. Генетический алгоритм задачи размещения структурированной кабельной системы здания.//Вестник НГУ. Сер. Информационные технологии.- Новосибирск, 2005. 4 с.

17. Гимади Э.Х., Глебов Н.И. Экстремальные задачи принятия решений. -Новосибирск, НГУ, 1982. 80 с.

18. ГОСТ 34.201-89. Информационная технология. Комплекс стандартов на автоматизированные системы. Виды, комплектность и обозначение документов при создании автоматизированных систем. Издательство стандартов, 1991. - 14 с.

19. ГОСТ 2.119-73. Эскизный проект. Единая система конструкторской документации. Издательство стандартов, 1991. - 6 с.

20. Гроднев И.И. Волоконно-оптические линии связи. М.: Радио и связь, 1990.-223 с.

21. Дементьев В.Т., Ерзин А.И., Ларин Р.М., Шамардин Ю.В. Задачи оптимизации иерархических структур. Новосибирск: Издательство Новосибирского университета, 1996. - 167 с.

22. Евстегнеев В.А. Касьянов В.Н. Теория графов: обработка бесконтурных графов/ Отв. Ред. Поттосин И.В.; Рос. акад. наук. Сиб. отд-ние. Ин-т систем информатики. Новосибирск: Наука, 1998. - 385 с.

23. Иванова Т.И. Корпоративные сети связи. М.: Эко-Трендз, 2001. - 283 с.

24. Ионов А.Д. Волоконно-оптические линии передачи: Учеб. Пособие/Сиб.гос.ун-т телекоммуникаций и информатики. Новосибирск, 2003.-150с.

25. Ионов А.Д. Проектирование кабельных линий связи/ MC РФ, Сиб. гос. акад.телекоммуникаций и информатики. Новосибирск, 1995. - 59 с.

26. Замбицкий Д.К. Лозовану Д.Д. Алгоритмы решения оптимизационных задач на сетях. М.: Наука, 1983

27. Зыков A.A. Гиперграфы. //Успехи математических наук. Вып. 6., 1974. с.89- 154.

28. Зыков A.A. Основы теории графов. М.: Наука, 1987

29. Кауль С.Б. Об одной задаче синтеза гиперсетей//Системное моделирование. Новосибирск, ВЦ СО АН СССР, 1984, с. 17-34

30. Краснощекое П.С., Петров A.A. Принципы построения моделей. -М.:МГУ, 1983.

31. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.

32. Кульгин М.В. Технология корпоративных сетей. СПб.: Питер, 2000. -699 с.

33. Ладыженский Г.М. Архитектура корпоративных информационных систем// СУБД, 1997,№ 5 6.

34. Макаров A.A., Ковязин В.И. Автоматизация проектирования систем передачи данных: Учеб.пособие/ Одесский электротехн. ин-т связи. Одесса, 1987.-84 с.

35. Мальке Г., Гёссинг П. Волоконно-оптичекие кабели: Основы. Проектирование кабелей. Планирование систем: Пер. с англ. Новосибирск, 1997. - 264 с.

36. Математическое моделирование. M.: Мир, 1979. - 200 с.

37. Мурадян А.Г. Оптические кабели многоканальных линий связи. М.: Радио и связь, 1987.-198с.

38. Нечепуренко М.И., Попков В.К., Майнагашев С.М. Алгоритмы и программы решения задач на графах и сетях. Новосибирск, Наука, 1990.515 с.

39. Олифер В.Г. Компьютерные сети. Принципы, технологии, протоколы. -СПб.: ПИТЕР, 2002.-668 с.

40. Ope О. Теория графов. М.: Наука, 1968

41. Полунин А. Новое поколение УАТС от Simens//Cera, 2000, №4.

42. Попков В.К., Кауль С.Б., Нечепуренко М.И. Методы оптимизации структур зоновых сетей связи. Новосибирск, ВЦ, 1983.

43. Попков В.К. Математические модели связности. Ч.2.Гиперграфы и гиперсети. Новосибирск: Изд. ИВМГиМГ СО РАН, 2001 - 180 с.

44. Попков Г.В. Исследование и разработка методики оптимизации сетей абонентского доступа Диссертация, Новосибирск, СибГУТИ, 2002. 131 с.

45. Пятибратов А.П.Гудено Л.П., Кириченко A.A. Вычислительные системы, сети и телекоммуникации. М.: Финансы и статистика, 1998.- 398 с.

46. Ренделмен Д. Cisco представляет УАТС для IP сетей// PC Week/RE, 1999, №12.

47. Руководство по строительству линейных сооружений магистральных и внутризоновых кабельных линий связи. Министерство связи СССР. М.: Радио и связь, 1986. - 608 с.

48. Русеев Д.С. Технологии беспроводного доступа: справочник. СПб.: БВХ-Петербург, 2002, -334 с.

49. Семенов А.Б., Стрижаков С.К., Сунчелей И.Р. Структурированные кабельные системы. М.:ДМК-Пресс, 2002.- 640 с.

50. Семенов А.Б. Проектирование и расчет структурированных кабельных систем и их компонентов. М.:ДМК Пресс; М.: Компания АйТи, 2003. - 416 с.

51. Семёнов А.Б. Волоконная оптика в локальных и корпоративных сетях связи. М.: Компьютер Пресс, 1998.- 302 с.

52. Смирнов И.Г. Структурированные кабельные системы. -М.:ЭКО-ТРЕНДЗ, 1998. 178 с.

53. Смирнов И.Г. Новый стандарт СКС//Вестник связи. 2001. - № 5.- с. 6367.

54. Соколов H.A. Эволюция местных телефонных сетей. Пермь: Издательство ТОО Типография "Книга1,1994. - 375 с.

55. Соколов H.A. Телекоммуникационные сети. 41. 42. М.: Альварес Паблитинг, 2003. - 127 с.

56. Соколова О.Г., Разработка интерактивной системы анализа и синтеза проектных решений в сетях электросвязи. Диссертация, Новосибирск, ИВМ и МГ СО РАН, 2002.-140 с.

57. Сушков Ю.А. Связность гиперграфов. СПб, 2002

58. Телекоммуникации. Мир и Россия. Состояние и тенденции развития/ Под ред. Клещеева Н.Т. М.: Радио и связь, 1999.- 480с.

59. Тепляков И.М. Основы построения телекоммуникационных систем и сетей: Учеб. Пособие. М.: Радио и связь, 2004 - 327 с.

60. Уолрэнд Д. Телекоммуникационные и компьютерные сети. Вводный курс/ Пер. с англ. М.Е. Липкина, М.М. Птичникова; Под ред. В.Н. Стародубцева. М.: Пост-Маркет, 2001. - 476 с.

61. Фаронов В.В. Delphi. Программирование на языке высокого уровня. -СПб.: Питер, 2004. 639 с.

62. Харкер Д., Бекорн П., Снайдер Д. Интеллектуальные здания Проектирование и эксплуатация информационной инфраструктуры. Сети MP, 1996.- 135 с.

63. Цой С., Цхай С.Н. Прикладная теория графов. Алма-Ата: Наука, 1971

64. Эволюционные вычисления и генетические алгоритмы. // Обозрение прикладной и промышленной математики. Выпуск 5.Т.З. М.:"ТВП". - 1996.

65. Holland J.H. Adaptation in Natural and Artificial Systems. /The University of Michigan, 1975.

66. Goldberg D.E. Genetic Algorithms in Search, Optimization, and Mashine learning Addison- Wesley, 1989

67. Галямов B.A. Попков B.K. Задача синтеза первичной сети электросвязи города.// Вестник связи. Москва , 2005. № 12 .С. 59-60.