автореферат диссертации по радиотехнике и связи, 05.12.14, диссертация на тему:Исследование и разработка диалоговых систем моделирования структурно-надежных сетей электросвязи

ю

сп

сп

з а о-

со »

Министерство связи Российской Федерации Сибирская Государственная Академия телекоммуникаций и информатики

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

БЕЖАЕВА Елена Борисовна

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

Специальность

05.12.14. Сети связи, узлы связи и распределение информации

N

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

Автореферат

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

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

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

I

Научный руководитель:

доктор физико-математических • наук, академик МАИ Попков В.К.

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

доктор физико-математических наук Евстигнеев В.А. кандидат технических наук Букреев Е.М.

Ведущая организация: АООТ ГИПРОСВЯЗЬ-4

Защита состоится " 23 " мая 1995 г. в 14 часов на заседаний специализированного совета Л118.07.01 в 625 ауд. Сибирской Государственной академии телекоммуникаций и информатики. Адрес: 630125, Новосибирск, ул. Кирова, 86 . ^

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

Автореферат разослан 99.5г. .

Ученый секретарь специализированного совета к.т.н., профессор член-корр. МАИ

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

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

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

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

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

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

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

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

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

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

2. Разработка способов представления математических моде-

лей сетей связи и технологических алгоритмов их исследования в диалоговой системе моделирования.

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

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

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

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

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

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

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

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

Весь комплекс программ написан на языке Си для IBM PC XT/AT и выполнен как развивающийся и открытый для дальнейших модификаций.

Диалоговая Система Моделирования Сетей Связи (ДСМСС) внедрена в ВЦ СО РАН и используется для автоматизации научных исследований математических моделей сетевых структур. Ее разработка велась в рамках Республиканской научно-технической программы "Информатизация России".

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

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

Апробация работы. Основные положения диссертационной ра-

боты докладывались, обсуждались и получили положительную оценку на Всесоюзной Научно-технической конференции "Микропроцессорные системы автоматизации технологии производства" (Новосибирск, 1987 г.), IV Всесоюзном совещании "Прикладные задачи на графах и сетях" (Новосибирск, 1989 г.), 2-й Всесоюзной конференции "Моделирование систем информатики" (сентябрь 1990 г.), Международной научно - технической конференции "Проблемы функционирования информационных сетей" (Новосибирск, 1991 г.), XXXV научно - методической конференции НЭИС (Новосибирск, 1994 г.), Российской научно -методической конференции "Новые информационные технологии в университетском образовании" (Новосибирск, 1994 г.), Дальневосточной школе-семинаре " Моделирование естественных процессов" им. Ак. Золотова (Находка, 1994 г.), XXXVI Научно - методической конференции "Проблемы перехода на многоуровневую систему обучения"(СибГАТИ, Новосибирск, 1995г.).

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, приложения и списка литературы из 83 наименований. Общий объем работы 155 страниц машинописного текста, в том числе основной текст изложен на 105 страницах, иллюстрации на 23 страницах, список литературы занимает 7 страниц и приложение на 20 страницах.

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

1. Программный комплекс Системы Лиалогового Моделирования Сетей Связи - инструментальное средство, позволяющее более эффективно разрабатывать широкий класс моделей для исследования сетей связи.

2. Интегрированное представление информации о модели сети обеспечивает единое интерактивное исследование и получение совокупности конструктивных и программно-информационных параметров для оценки исследуемого объекта.

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

4. Метод построения диалога для анализа вариантов развития телефонной сети специального назначения.

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

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

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

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

Наиболее подходящими моделями структуры сети являются графовые математические объекты (графы, сети, гиперсети и т.п.). Проблема оптимизации сети связи принадлежит к классу многокритериальной оптимизации. Для ее решения применяются методы декомпозиции и агрегирования. Метод декомпозиции позволяет выделить набор частных подзадач в системе непрерывных критериев Ф = 4>1,ф2,...фк, а агрегирование - получить обобщенное решение. Поскольку при оптимизации структуры сети основным требованием является уменьшение затрат на ее реализацию, или модернизацию, то основным критерием ф может быть стоимость сети, а компоненты вектора Ф - показатели надежности и живучести, пропускная способность, качество обслуживания и др.

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

Во второй главе рассматриваются принципы построения, информационные аспекты, применение и особенности организации диалога при разработке Диалоговой Системы Моделирования Сетей Связи (ЛСМСС).

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

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

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

Третья глава посвящена разработке методов автоматизации исследований при перспективном проектировании СЭГ с применением средств диалогового моделирования.

Проблемы оптимизации структуры СЭГ не могут быть удовлетворительно решены в автоматическом режиме по причине использования трудноформализуемой информации и высокой'трудо-емкости большинства алгоритмов.

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

Структура СЭГ представлена гиперсетью

5 = ((Уь С?2! ^з» Д).

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

Разработан и реализован метод, заключающийся в применении совокупности эффективных теоретике - графовых алгоритмов для анализа вариантов при построении топологии СЭГ с разби-

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

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

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

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

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

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

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

Методы и алгоритмы реализованы в виде программного обеспечения в рамках ЛСМСС.

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

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

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

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

2. Разработана структура и инструментальные средства поддержки Диалоговой Системы Моделирования Сетей Связи. Ее основными компонентами являются: интерактивная графическая среда, позволяющая эффективно работать с сетевой моделью; база данных сетевой модели; проблемно-ориентированные ППП решения задач анализа и синтеза сетей связи.

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

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

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

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

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

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

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

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

Автор благодарит своего руководителя Попкова В.К., Васнееву Е.Л. и Проскурякова В.А. за поддержку в создании Диалоговой Системы Моделирования сетей связи.

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

1. Пакет прикладных программ "Анализ и синтез сложных систем" (комплект программной документации) BLI СО АН СССР, 1222с., Новосибирск, 1984, ГОС ФАП, per N ÍI007484. (совместно с Нечеиуренко М.И. и др./

2. Генератор диалоговых систем ввода и редактирования данных. Тезисы ВНТК "Микропроцессорные системы автоматизации технологии производства". Новосибирск, 19S7r. 1с. (Соавтор Ка-уль С.Б.)

3. Интерактивная система для описания, анализа и синтеза объектов сетевой структуры. Тезисы докладов ВК " Моделирование систем информатики." 13-15 сентября 1988г., Новосибирск, 1с. (Соавтор Кауль С.Ь.!

4. О задаче синтеза оптимальных сетей циркулярной связи. Тезисы докладов IV Всесоюзного совещания "Прикладные задачи на графах и сет ях", 17-19окт., 1989г., Новосибирск, "2с.

5. Диалоговая система для анализа и синтеза сетей связи. Тезисы докладов 2-ой ВК "Моделирование систем информатики" 2527 сентябри ННЮг., Новосибирск. 1с. 'соавтор Васенева Е.Л.)

fi. Тексты программ "Сети и задачи оптимизации", "('вязность" в книге Алгоритмы и программы решения на графах и сетях, под ред. Нечепуренко М.И.,Новосибирск, Наука, Сибирское отделение. 1990г.

7. О задаче синтеза оптимальных сетей с групповыми канала-

ми. Сборник СМ 17 ВЫ СОАН, 1991г. Новосибирск, 12с. (соавтор Васенева Е.Л.)

8. О построении мультидиалоговых систем моделирования и оптимизации сетей связи. Сб. трудов Моделирование информационных сетей, Новосибирск, ВЦ СО РАН, 1994г., 12с. (соавтор Попков В.К.)

9. Применение программных

средств автоматизации проектирования в учебном процессе. Тезисы докладов XXXV научно-методической конференции НЭИС, Новосибирск, февраль 1994г., 1с. (соавтор Попков В.К.)

10. Использование графических средств ПЭВМ при обучении студентов основам автоматизации проектирования. Тезисы докладов XXXV научно-методической конференции НЭИС, Новосибирск, февраль 1994г., 1с. (соавтор Попков В.К. и др.)

11. Некоторые вопросы разработки электронного учебника по курсу "Автоматизация проектирования сетей связи". Материалы Российской научно - методической конференции "Новые информационные технологии в университетском образовании", Новосибирск, НГУ, март 1994г., 5с. (соавторы Попков В.К., Костюкова Н.И.)

12. Программный комплекс автоматизации проектирования и оптимизации сетевых объектов. Российская научно - техническая конференция "Информатика и проблемы телекоммуникаций", 2829 апреля 1994г., Новосибирск, НЭИС. 1с. (соавторы Попков В.К., Проскуряков В.А. Васенева Е.Л.)

13. Разработка перспективного проекта СЭГ на ПЭВМ IBM PC. Российская научно- - техническая конференция "Информатика и проблемы телекоммуникаций", 28-29 апреля 1994г., Новосибирск, НЭИС, 1с. (соавторы Прохорова Н.И., Танцурина E.H.)

14. Использование графического редактора в локальной вычислительной сети при контроле знаний студентов. Тезисы докладов XXXVI научно-методической конференции Сиб. ГАТИ, Новосибирск, февраль 1995г., 1с. (соавторы Попков В.К., Проскуряков В.А., Прохорова Н.И.)

Подписано в печать 12.04.95 Формат бумаги 60*84/16 Объем 1.0 печ.л. Тираж 100 экз. Заказ N 39

Ротапринт ВЦ 00 РАН, Новосибирск-90