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

со

СП

« 22 РОССИЙСКАЯ АКАДЕМИЯ НАУК

° ас СИБИРСКОЕ ОТДЕЛЕНИЕ

^ ^ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР ю

о- ,г-

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

ВАСЕНЕВА Евгения Леонидовна

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

СВЯЗИ

05.13.16. Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

Автореферат

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

Новосибирск 1996

Работа выполнена в Вычислительном центре Сибирского отделения РАН.

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

Погасов ВХ

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

Евстигнеев В.А.

кандидат технических наук ••••■. Букрегв Е.М. - • '

Ведущая организация : Сибирская государственная академия телекоммуникаций и информатики .

' . Защита .состоится «■-3 7 » ^е^д'Г^ 199 ¿г. в' часов на заседании специализированного совета Д 002.10.02 в Вычислительном Центре . СО РАН по' адресу: 630090, г; Новосибирск, ир. Ак. Лаврентьева^.

С диссертацией можно ознакомиться в библиотеке ВЦ СО-РАН. .

■ Автореферат разослан «

»У100^4 ' 1996 г.' ' "■ ;. :

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

спедаалюированного совета Д 0002.10.02 -' • ,:-."■

кандидат технических наук ; , ' . ' ' . . .

Г.И.Забиняко.

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

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

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

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

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

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

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

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

Научная новизна и значимость заключаются в: _______

----------« разработке технологии решения задач исследования и оптимизации структур

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

Практическая ценность и внедрение.. Предложенные методы и алгоритмы автоматизации проектирования реализованы в программных средствах поддержки Диалоговой системы моделирования и оптимизации сетей связи. Полученные в диссертации теоретические результаты использовались при разработке диалоговых систем для исследования сетей связи различного . назначения. Программная модель анализа развития вторичных сетей связи с коммутацией каналов использована при разработке комплексной научно-технической программы развития и совершенствования единой сети связи специального назначения (НИИСА, Москва).

Разработанные методы автоматизации исследования при проектировании сети электросвязи города и программные средства их поддержки внедрены в учебном процессе на кафедре АЭС СибГАТИ.

. Апробация работы. Основные положения диссертационной работы докладывались, обсуждались и получили положительную оценку на Второй Всесоюзной конференции "Моделирование систем информатики" (Новосибирск, 1990 г.); Российской научно-технической конференции "Информатика и проблемы телекоммуникаций" (Новосибирск, 1994 п ), конференции молодых ученых ВЦ СО РАН (Новосибирск, 1995 г.), межрегиональной конференции "Проблемы информатизации региона" (Красноярск, 1995 г.), международной

научно-методической конференции "Новые информационные технологии в университетском образовании" (Новосибирск, 1996г.).

Публикации. По результатам проведенных исследований опубликовано 9 печатных работ и 12 научных отчетов.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы из 100 наименований. Общий объем работы 141 страница, в том числе 26 рисунков, приложение на 12 страницах и список литературы на 10 страницах.

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

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

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

3. Методы решения оптимизационных задач, возникающих на этапах перспективного ■ проектирования сети электросвязи города в рамках Диалоговой системы моделирования. .

•4. Методы решения задач модернизации сетей абонентского доступа с учетом ■ведущих тенденций эволюции этих сетей и вовлечением проектировщика в процесс принятия решения.

Содержание работы.

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

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

первичнее и вторичные. Счр/туха сг\.с исдым/^:^ графой, в.

котором ъершшш соотЕетствукл ::..-.•. у>лам. ребра - соединительным лщшнм. Вторичная сеть строи» ся »а базе шрьичной, и , если рассматривать ее отдельно от первичной,' юе х-зротпр' моделируется графой, с верширами, соответствующими узлам езяш/и ребрами - каналам ши пучкам каналов. .

Моделирование структуры вторичной сети, в виде графа не шражает иерархичность сетей сахзл, тою, что вторичная сеть рассматривался кмс сеть, построенная на базе канйлок первичной сета. Для моделирования сетей с учетом реализации одной сети в другой используются гииерсеть, образуемая тройкой 5=(0],(;.>,Г ), где 0|=(Х1 Д|) и О^ГХгДг) - графы, причем множество вершин Хг графа -является подмножеством вершин X) графа в), а Б* - отображение множества ребер Иг графа С2 в множество простых цепей 0(00 графа О]..

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

тахф='тах{<ь1ф2,...,ф,;фч+ьф2,'...,фсг} ' ' . ■

хс:Х хеХ

часть из которых' ф1,ф2,...,фч лексикографически упорядочена (обычно это стоимостные критерии).

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

Можно привести следующую схему решения оптимизационной задачи с участием человека в процессе принятия решения. Проектировщик задает условия задачи (целевую функцию и ограничения), и программный модуль на модели отыскивает один или несколько вариантов решений и вычисляет' его

характеристики. Jitcm челов'У о?<ента»ет решения, и, при необходимости коррсктгру л' условия задачи, Ктерзкии повторяются до тех пор, пока не будет найдено приемлемое решение, которое и реализуется на объекте. Другая схема поиска ретенкя предполагает ^посредственное вмешательство человека в работу !_г-;~р1ггка. В этом случае проектировщик перед начатом работы vsh-iitit/оттрясаемые параметры алгоритма и следит за ходом его работы, г:?гучэ.% промежуточны? результаты, отсекая неперспективные с его точки LpR-ny чглргвленкя.

В" STop'tS главе приведены принципы построения и структура Диак гс зой системы моделирования и оптимизации структур сетей связи.

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

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

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

Исследователь, разрабатывает сетевую модель, адекватную его классу задач, формулирует целевые функции и ограничения на задачу. Информацию о модели он вводит двумя способами: либо помещает в базу данных с помощью СУБД, либо вводит в структурированном виде с использованием графического интерфейса. Кроме того, пользователь готовит базу данных, содержащую нормативно-справочную информацию и экономические характеристики для подготовки проектной документации и смет. Входные данные с помощью системы управления базами данных и преобразуются во внутреннее представление данных в оперативной памяти. Графический интерфейс и пакет

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

При разработке системы моделирования и оптимщации сетевых структур важное зцаче1ше имеет построение диалогового интерфейса. В методическом плане диалог обеспечивает решение слабоформализовашшх задач за счет активного вовлечения человека в процесс поиска приемлемого результата на базе инструментальных программных Средств и использования его опыта и интуиции. '•.'•■'••'.'■.

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

Предлагаются следующие элементы графической среды.

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

2. Объекты. Каждый объект соответствует элементу сети связи; пункту связи, линии или каналу. Объект имеет тип, графическое представление и набор параметров, зависящий от его типа н от класса решаемых проектных задач.

3. Функции. В их набор входят функции'манипулирования объектами и задачи, которые могут, быть решены для одного объекта или группы объектов. Частные задачи оптимизации тйюкс могут бьпь включены в набор функций, таким образом, система приобретает ' возможности своего рода интеллектуального калькулятора, . пользуясь которым: проектировщик : исследует свойства модели й. решает некоторые задачи/ .

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

Третья глава содержит содержательную и математическую постановку задачи перспективного проектирования сети электросвязи города (СЭГ). Структура сети электросвязи города моделируется гиперсетыо .3==(01,02,0з,С4,Р*1,Р*2,Г*зХ включающей в себя граф 0| генерального плана застройки города, граф Ог кабельной канализации, граф йз кабельных линий связи и граф G^ пучков .соединительных линий. Задача оптимизации состоит в определении структуры пшерсети 5 при условии минимизации функционала Ф при ряде ограничений » требовании. Функционал Ф состоит нз четырех компонент, отражающих стоимость абонентских линий, соединительных линий внутри узлового района и межузловых и стоимость строительных работ. Таким образом, поставленную задачу можно решать поэтапно. Решение каждой подзадачи происходит в интерактивном режиме, где проектировщик может накладывать дополнительные ограничения, изменять целевую функцию или же самостоятельно выработать вариант решешм. В каждом случае система вычисляет стоимостные и технические характеристики варианта для анализа проектировщиком и последующего ввода дополнительных ограничений или корректировки модели- или данных. Если все решения неудовлетворительны, можно вернуться к любой подзадаче. Все .промежуточные решения могут быть запомнены. В результате будет выработано реше!ше, адекватное требованиям проекта.

Пакет программ, реализующий проектные процедуры, графический интерфейс проектировщика, набор модулей для построения сетевой модели и система управления базой данных объединены в открытую для модификации диалоговую систему, представляющую собой эффективный инструмент для решения проектных задач. Дшшая система внедрена в СибГАТИ в учебном процессе. '

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

Последняя задача, описанная в данной работе, это задача оптимального построения'и развития сетей абонентского доступа. Главной особенностью эволюции абонентских сетг-1 кокно считать использование цифровых. систем передач и современкнх- ь&дошииицях систем, таких, как- оптоволокно и радиорелейные, и лазерные линии. Наиболее перспективной моделью будп кольцевая структура первичной сети, з которой ЩУ(МВК) связаны оптоволоконным на5йлем, а от каждого ЦКУ к "Л'.пефонному аппарату проложен* либо витая пара, либо опгозолокно, в»бс* к качестве направляющих ск-тгем используются радиорелейные линии.' Така?. модель позволит существенно сократить расход кабельной продукции, минимизировав стоимость направляющих систем, обеспечит высокую живучесть сети и ввести процедуры управления пропускной способностью за счет изменения соединений в ЦКУ и

мвк.' '

В настоящее время в лаборатории ММИС ВЦ СО РАН разрабатывается по заказу ЛОНИИС (г. Сакхт-Петербург) диалоговая система моделирования и оптимизации сетей абонентского доступа. Диалоговая система позволяет проектировщику решать три класса задач: задачу паспортизации сети, реконструкции и развития сетей. Задача паспортизации весьма трудоемка и имеет самостоятельное значение для ГТС. Хранение в базах данных и обновление информации об элементах сети электросвязи и их характеристиках

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

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

Основные результаты работы:

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

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

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

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

5. Разработаны алгоритмы диалоговой оптимизации решения задач на этапах

• ' проектирования сети электросвязи города (СЭГ). Предложена модель анализа

вариантов и пршштия решений в процессе перспективного проектирования

• - СЭГ.

6. На основе предложенных методов и программных средств создана учебная диалоговая система поддержки лабораторного практикума, курсового и дипломного проектирования по курсу «Автоматизация проектирования сетей ■связи».

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

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

Публикации по теме диссертации.

Диалоговая система для анализа й синтеза сетей связи. Тезисы докладов. 2-ой ВК "Моделирование систем информатики" 25-27 сентября. 1990г. Новосибирск, 1стр. (соавтор Бежаева Е.Б.) .

2. О задаче синтеза оппшачьных сетей с групповыми каналами. Сборник СМ 17 ВЦ СОАН ,1991г. Новосибирск, 12с. (соавтор Бежаева Е.Б.)

3. Программный комплекс автоматизации проектирования и оптимизации сетевых объектов. Тезисы российской научно-технической конференции "Информатика и проблемы телекоммуникаций", 28-29 апреля 1994 г., Новосибирск, НЭИС. (соавторы Попков В.К., Бежаева Е.Б., Проскуряков В.А.)

4. Диалоговая система развития вторичных сетей связи с коммутацией каналов. Труды ВЦ СО РАН. Серия Моделирование информационных сетей. Новосибирск. 1995 г. (соавтор Бежаева Е.Б.)

5. Система автоматизации исследований при перспективном проектировании городской телефонной сети. Труды конференции молодых ученых ВЦ СО РАН, Новосибирск, 1995г. с. 27-40. '•'..'■•

6. New information technology in Higer Education. В печати. (соавторы Попков В.К., Проскуряков В.К., Бежаева Е.Б., Костюкова Н.И.)

7. Диалоговая система автоматизации исследований структурных моделей телекоммушпеациошплх сетей. Труды межрегиональной конференции "Проблемы информатизации региона". Красноярск, 27-29 ноября 1995 г. (слоавтор Бежаева Е.Б.)

8. Разработка математических и программных средств поддержки мультидиалогового моделирования и оптимизации информационных сетей. Итоговый отчет по проекту N 262.4, шифр "Пролог", по программе "Информатизация России", 1995, hhb.N02.9.60 001870, 60 с. ( соавторы Попков В.К., Проскуряков В.А. и др.)

9. Открытая обучающая система моделирования и оптимизации сетевых структур. Материалы международной научно-методической конференции "Новые информационные технологии в университетском образовании", 19-22 марта 1996г., г.Новосибнрск, 1с. ( соавторы Бежаева Е.Б., Костюкова Н.И., Попков В.К.)