Исследование и разработка моделей и методов оптимизации структур телекоммуникационных систем. 05. 13. 17 теоретические основы информатики

Вид материала

Содержание

Общая характеристика работы
Цель диссертационной работы
Задачи исследования. Для достижения поставленной цели в работе решаются следующие задачи
Методы исследования
Основные положения представленные к защите
Практическая ценность результатов.
Личное участие.
Структура и объём работы
Краткое содержание работы
В первой главе
Вторая глава
В третьей главе
Scemu = Sоб + SкабАБ.сети + Sк
Метрические характеристики
Стоимостные характеристики
Целевая функция
Одновременный поиск в направлении нескольких экстремумов.
Было проведено сравнение характеристик эффективности работы исследуемых алгоритмов.
Основные результаты и выводы
1. Галямов В.А. Задача синтеза первичной сети электросвязи города. Российская научно-техническая конференция. - Новосибирск, Сиб
...
Полное содержание

Подобный материал:

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

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

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

05.13.17 – теоретические основы информатики

АВТОРЕФЕРАТ

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

кандидата технических наук

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

Работа выполнена в Институте Вычислительной Математики и Математической Геофизики (ИВМиМГ) СО РАН.

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

наук, профессор В.К. Попков

Официальные оппоненты: доктор технических наук,

профессор Носов В.И.

кандидат технических наук Деревяшкин В.М.

Ведущее предприятие: ОАО Гипросвязь-4,

г. Новосибирск

Защита диссертации состоится « 21 » сентября 2006 г.

в 15 - 00 на заседании диссертационного совета Д 219.005.02 в

Сибирском Государственном Университете Телекоммуникаций и Информатики по адресу: 630 102, Новосибирск, ул. Кирова, 86

С диссертацией можно ознакомиться в библиотеке СибГУТИ.

Автореферат разослан «____» ___________ 2006 г.

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

диссертационного совета Д219.005.02

к.т.н., доцент Резван И.И.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Постановка задачи синтеза сети.
Проблема выбора и размещения элементов сети.
Задача декомпозиции исходной модели
Синтез сети с учётом распределения абонентов.

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

Универсальность - возможность использования однотипных каналов для передачи сигналов различных систем (данные, голос, видео);
Совместимость со стандартным активным оборудованием любых производителей;
Избыточность - наличие достаточного количества резервных каналов связи, необходимых для расширения системы в процессе эксплуатации;
Гибкость - простота и удобство обслуживания системы при внесении изменений в ее конфигурацию;
Надежность - способность системы сохранять рабочие параметры в заданных диапазонах в течение всего срока эксплуатации / гарантийного срока;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть известны:

Границы района проектируемой сети.
Типы застроек в этом районе и типовые планы зданий.
Заявки на услуги связи (телефонная связь, передача данных, кабельное телевидение), виды возможных приложений.
Типы кабелей и коммутационного оборудования (выпускаемые производством на день проектирования).
Стоимостные характеристики: кабелей, систем передачи, коммутационного оборудования, подготовки помещений для станций и узлов, строительных работ по канализации (если отсутствует телефонная) и пр.
Нормы на категории и длины кабелей и шнуров СКС.
Возможные места расположения коммутационного и другого оборудования.
Емкость телефонных станций, пропускная способность ЛВС и требование на конфиденциальность.
Сеть ситуационных трасс и существующая кабельная канализация для внешних магистралей.

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

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

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

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

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

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

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

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

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

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

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

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

S_cemu = S_об + S_{кабАБ.сети}+ S_к

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

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

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

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

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

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

Структура СКС рассматривается с учётом разделения её на подсистемы. Структурированная кабельная система задается гиперсетью N=(X,V,A,B,C), где:

X=(x₁,..x_n)- множество вершин

V=(v,..,v) – множество ветвей

A=(a,..,a) – множество рёбер внешней магистрали

B=(b,..,b) – множество рёбер внутренней магистрали

C=(c,..,c) – множество рёбер горизонтальной магистрали

R= A+B+C .

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

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

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

Для каждой ветви v V определяется p(v) – длина участка ситуационной трассы; для каждого ребра, r  R r_ij– длина ребра

Стоимостные характеристики:

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

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

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

a_ijk – стоимость кабельной линии категории k от j -й точки подключения до i -й распределительной этажа, включая стоимость розеточного модуля той же категории.

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

Целевая функция

Линейные сооружения:

(S)= a(v)p(v) + b(r)p(r), v V, r R= A+B – стоимость монтажных и строительных работ для магистралей, первое слагаемое определяет затраты на кабельную канализацию и кабельные каналы, а второе на монтаж и стоимость кабеля.

 a_ijk , r_ijk  C – стоимость кабельных линий категории k от j -х точки подключения до i -х распределительных этажа, включая стоимость розеточного модуля той же категории. Определяет затраты на горизонтальную подсистему.

Узловые сооружения:

∑d_i– суммарные затраты на размещение узлов сети на этаже в i-х пунктах.

 с_к – суммарная стоимость коммутационного оборудования типа k, включая стоимость её монтажа.

U=∑d_i₊ с_к

Таким образом, вся сеть будет оцениваться функцией: Q=(S)+ U.

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

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

Длины r_ijk  R – кабельных линий типа k меньше верхней оценки длины линии, характеризующей выполнения норм по затуханию.
Прокладка внешней магистрали осуществляется согласно топооснове, сети ситуационных трасс и с учётом существующей канализации.
Предполагаемые нагрузки на услуги телефонной связи и передачи данных и других услуг не превышают возможности коммутационного оборудования. Напротив, осуществляется резервирования ресурсов линейных трактов и коммутационного оборудования.

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

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

В работе описаны алгоритмы для задач построения СКС:

1) Задача построения кабельной канализации.

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

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

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

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

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

Q(S)= a(v)p(v) + e (d(u))p(u) +∑с(d(z)) ,

uU vF(u) uU zZ

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

r W^-1(u) v F(u)

Первое слагаемое в выражении для Q(S) представляет собой стоимость строительных работ при создании сети связи (т. е. гиперсети S) , второе – стоимость монтажных работ, третье - стоимость оборудования коммутации.

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

длины ветвей v V – p(v);

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

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

стоимости e(d(u)) монтажных работ на единицу длины ребра графа PU как функция его ёмкости (под ёмкостью ребра графа PU понимается сумма ёмкостей тех рёбер из графа WS трассы которых проходят по этому ребру);

c(d(z)) – стоимость оборудования (аппаратура коммутации), установленного в вершине графа PU как функция ёмкости этой вершины(ёмкость вершины – это сумма ёмкостей рёбер графа PU, инцидентных этой вершине).

Граф PS можно интерпретировать как схему ситуационных трасс, в которой отражена существующая сеть кабельной канализации и инженерных сооружений для организации линий связи, т.е. вершины соответствуют, например, узлам линейных сооружений различных подсистем, колодцам различного назначения, кабельным вводам в здание и другим возможным объектам, а рёбра – участкам улиц, возможным трассам прокладки кабеля в здании, кабельной канализации и др.

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

PU – схема кабельной канализации и схема кабелей. Вершины соответствуют местам в которых оканчиваются кабели (т.е. местам, в которых осуществляется сращивание нескольких кабелей или ввод кабеля в коммутационную станцию или узел), а рёбра кабелям.

Отображение W задаёт траекторию участков кабельной канализации и кабелей. Каждое r = (x,y)R является цепью между вершинами x,y в графе PU с весами рёбер p(u), где p(u)=p(v).

В рассматриваемой задаче осуществляется трассировка рёбер rR непосредственно в PS, а затем на последнем этапе восстанавливается граф PU, так как можно считать, что граф PU является частью графа PS и трассировочная функция F- тождественная, т.е. для любых u  U F(u) = u.

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

MIN{Q(S)= a(v)p(v) + e (d(u))p(u) +∑с(d(z))} , где

uU vF(u) uU zZ

d(u)=∑d(r) p(u)=∑p(v)

r W^-1(u) v F(u)

p(v)>0; a(u)>=0; e(d(u))>0; c(d(z))>=0; d(r)>0;

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

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

Схема алгоритма представлена на рисунке 2.

Алгоритм итеративен, количество итераций k = | R |.

1. Зафиксируем одно ребро r графа WS.

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

3. Запишем μ (r) в PU.

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

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

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

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

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

Одновременный поиск в направлении нескольких экстремумов.

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

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

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

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

Применение стратегии элитизма
Применение двух критериев останова одновременно
Повышение вероятности мутации бита хромосомы

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

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

График 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.

Blog