автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Разработка интерактивной системы анализа и синтеза проектных решений в сетях электросвязи

ВВЕДЕНИЕ.

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

1.1 Теоретические модели сетей связи.

1.2 Математические модели структур сетей связи.

1.3 Основные задачи анализа и синтеза первичной сети.

1.3.1 Методы решения задач анализа и синтеза.

1 1.3.2 О задачах исследования живучести сетей связи.

1.4 Задачи проектирования сетей SDH.

1.5 Содержательная и математическая постановка задачи перспективного проектирования СЭГ.

2. Разработка интерактивной системы поиска проектных решений в сетях электросвязи.

2.1 Принципы построения и структура интерактивной системы поиска проектных решений.

2.2 Описание работы пользователя с интерактивной системой.

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

2.4 Графический интерфейс системы.

2.4.1 Описание реализации графического редактора.

2.4.2 Описание возможностей работы редактора.

3. Методы решения задач анализа и синтеза структур сетей связи с использованием интерактивной системы.

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

3.1.2 Задачи поиска покрытий в графе и их приложения в анализе сетей связи.

3.1.3 Задача перераспределения потоков в гиперсети.

3.2. Описание работы с задачами в интерактивной системе.

3.3. Алгоритмы для исследования живучести сетей связи.

3.3.1 Модель анализа надежности проектных решений.

3.3.2 Описание схемы моделирования восстановления первичной сети.

3.4 Задачи, связанные с переходом на цифровые сети и коммутации.

3.4.1 Применение интерактивной системы для задач проектирования сетей абонентского доступа.

3.4.2 О задачах мониторинга цифровых систем связи.

3.5 Общая схема поиска проектных решений с использованием интерактивной системы.

4. Экспертная подсистема и экспертный анализ проектных решений в интерактивной системе.

4.1 Описание экспертных систем.

4. 2 Проблемы многокритериальной оптимизации сетей связи.

4.3 Модели принятия решений в интерактивной системе.

4.4 Экспертные оценки экономических критериев при планировании и эксплуатации сетей связи.

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

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

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

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

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

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

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

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

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

- Исследование проблем многокритериальной оптимизации при проектировании сетей связи.

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

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

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

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

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

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

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

Приложения содержат результаты расчетов и программы отдельных алгоритмов.

Результаты диссертационной работы:

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

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

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

4. Исследование многокритериальное™ задачи проектирования сетей связи.

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

1. III Международная конференция "Современные информационные технологии", (СИТ-98) Новосибирск, 1998 г.

2. Международный семинар «Перспективы развития современных средств и систем телекоммуникаций», Хабаровск, 1999.

3. Международная научно-практическая конференции «Новые информационные технологии в университетском образовании», Новосибирск, 1999 г.

4. IV Международная конференция «Современные информационные технологии - 2000» («СИТ - 2000»), Новосибирск, 2000 г.

5. The 2nd International Workshop on Computer Science and Information Technologies", September 18-23, 2000, Ufa, Russia.

6. Международный симпозиум по проблемам информатики, модульных систем и сетей ICS-NET 2001. Москва, 2001 г.

7. XII Байкальская Международная конференция «Методы оптимизации и их приложения». Иркутск, 2001 г.

8. XXIX Международная конференция «Информационные технологии в науке, образовании, телекоммуникации и бизнесе", Украина, Гурзуф 2002 г.

9. Международная конференция «Вычислительные технологии и математическое моделирование в науке, технике и образовании» (ВТММ-2002), Алматы, 2002 г.

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

1. Bermond J. С., Bond J., Paoli M., Peyrat C. Graphs and interconnection networks: diameter and vulnerability. // London Math. Society, Lecture Notes, ser. 82, 1983, c. 1-30.

2. Cristofides N., Whitlock C. A. Network synthesis with connectivity constraints. A survey. // Operations Research 81. Proceeding of 9-th IFORS Conference. Hamburg, 1981, c. 655-673.

3. John E. Hopcroft, Richard M. Karp. An n3/2 algorithm for Maximum Matching in bipartite graphs. SIAM J. On computing, p. 105 1992.

4. Mateus G. R., Cruz F. R. В., Luna H. P. L. An algorithm for hierarchical network design // Location Science. 1994, vol. 3, p. 149-164.,

5. Monien В., Speckenmeyer E. Some further approximation algorithms for the vertex cover problem. Lecture Notes in Computer Science, 1990.p. .345.

6. Monma C. L., Shallcross D. F. Methods for designing communications networks with certain two-connected survivability constraints. // Operations Research vol. 37 N4, 1989. Стр. 531-541.

7. Popkov V. K., Sokolova O. D. Covering in Hypernets. // The 2nd International Workshop on Computer Science and Information Technologies", September 18-23, 2000, Ufa, Russia, c. 12-14.

8. Thompson J. Руководство no Delphi 4 для профессионалов. Borland Press, 1999.

9. Алексеев А. В. Представление знаний и формирование решений в экспертных системах при неполностью определенной исходной информации. // Сб. Методы и системы принятия решений. Интеллектуальные системы принятия решений. Рига, 1987, с. 9-14/

10. Ю.Алексеев О. Г. Алгоритм решения задачи о покрытии. // Техническая кибернетика. №5,1980. Стр. 12-22.

11. Батурина Л. Н., Лепешинский Н. А. О максимальном динамическом к-потоке в неориентированной сети. // Методы и программы решения оптимизационных задач на графах и сетях. Тезисы докладов. Новосибирск, 1989. Стр. 9-10

12. З.Батурина Л. Н., Лепешинский Н. А. Алгоритмы оптимизации параметров, обеспечивающих заданный уровень живучести сети. // Вести АН БССР, с. 26-29.

13. М.Бежаева Е. Б., Егунов М. М., Шерстнева О. Г. Проектирование ГТС на базе SDH. Учебное пособие. Новосибирск, СибГУТИ, 2002 г.

14. Букреев Е. М. О методе оптимизации структуры ГТС. // Повышение качества функционирования и надежности сетей связи и их элементов. Новосибирск, 1978, с. 19-20.

15. Букреев Е. М., Попков В. К. Методологические проблемы создания САПР сетей электросвязи Вычислительная техника и системный анализ. Новосибирск, 1979, с. 21-23.

16. Букреев Е. М., Попков В. К. Пакет прикладных программ проектирования городских телефонных сетей. // Прикладные задачи на графах и сетях. Новосибирск, 1981, с. 5-32.

17. Букреев Е. М., Попков В. К. Построение оптимальной структуры первичной сети электросвязи города. // Системное Моделирование -5, Новосибирск, 1979, с. 10-18.

18. Бурков В. Н., Гроппен В. О. Решение задачи о минимальном разрезе в бисвязном орграфе алгоритмами типа ветвей и границ. // Автоматика и телемеханика, 1974, с. 104-110.

19. Васенева Е. Л. Проблемы оптимального построения и развития сетей абонентского доступа. // Труды ИВМиМГ. Информатика, 3 Новосибирск, 1998 г., стр. 49-59.

20. Васенева Е. Л. Система автоматизации исследований при перспективном проектировании городской телефонной сети. // Труды конференции молодых ученых ВЦ СО РАН, Новосибирск, 1995, с. 2740.

21. Вороной С. М., Москалев В. Э. Интегрированные инструментальные средства приобретения, конструирования и обновления знаний интеллектуальных обучающих систем. Проблемы программирования, № 1-2, 2000, с.3-17.

22. Гимади Э. X., Глебов Н. И. Дискретные экстремальные задачи принятия решений. Новосибирск, 1991, 75 с.

23. Грундспенькис Я. А. Расширенная система структурного моделирования для автоматизации проектирования. // Сб. Методы исистемы принятия решений. Интеллектуальные системы принятия решений. Рига, 1987, с. 66-75.

24. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. Москва, Мир, 1982.

25. Давыдов Г.Б., Рогинский В. Н., Толчан А. Я. Сети электросвязи. Москва, Связь, 1977г., 360 с.

26. Данилов Ю. В., Мурдасов А. Б., Фуртиков Г. В. Применение ЭВМ при проектировании ГТС. Москва, связь, 1972 г., 112 с.

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

28. Дудник Б. Р. и др. Надежность и живучесть систем связи. Москва, Радио и связь, 1984.

29. Евстигнеев В. А., Касьянов В. Н. Теория графов. Алгоритмы обработки бесконтурных графов. Новосибирск, «Наука» Сибирское предприятие РАН, 1998.

30. Егунов М. М., Попков В. К., Прохорова Н. И. Количественная оценка структурной надежности сети с использованием графовой модели. // Информатика и проблемы телекоммуникаций тезисы докладов. Новосибирск, 1996, с. 25-26.

31. Егунов М. М., Федченко А. И. Исследование структурной надежности сети связи АСУ. // Надежность и качество функционирования информационных сетей и их элементов. Новосибирск, 1985, с.34-35.

32. Зарецкий К. А., Мейкшан В. И., Меленцова Н. А., Ноздрин В. В. К вопросу повышения надежности сетей электросвязи. // Труды ИВМиМГ СО РАН, Серия Информатика, Выпуск 3, 1998, с. 89-104.

33. Зуев Ю. А. Задача о покрытии: локальный подход и метод типа ветвей и границ. // Журнал вычислительной математики и математической физики. №6, 1979, с. 1566-1576.

34. Зулис Я. В., Кирикова М. П., Тентерис Я. К. Определение обобщенного показателя качества структуры в ходе проектирования. // Сб. Методы и системы принятия решений. Интеллектуальные системы принятия решений. Рига, 1987 г. с. 76-83.

35. Зыков М. Л., Соколова О. Д. «Разработка интерактивной системы анализа и синтеза сетей связи». Труды ИВМиМГ, Новосибирск, 2002 г.

36. Ильев В. П., Молдованов И. А. О градиентном алгоритме построения надежных коммуникационных сетей. // Труды ИВМиМГ, серия Информатика, выпуск 3, Новосибирск, 1998, с. 60-69.

37. Катулев А. Н., Михно В. Н., Виленчик Л. С. и др. Современный синтез критериев в задачах принятия решений. Москва, Радио и связь, 1992, 120с.

38. Кауль С. Б. Об одной задаче синтеза гиперсетей. И Системное Моделирование —10, Новосибирск, 1984, с. 17-34.

39. Кауль С. Б., Попков В. К. О сложности вычисления некоторых характеристик связности. // Сб. Системное Моделирование -7, Эффективная и структурная надежность информационных систем. Новосибирск, 1982, с. 99-115.

40. Кемени, Снелл. Математические методы в общественных науках // Советское радио, 1975 г.

41. Корниенко А. А., Погребной В. К., Щербанов В. А. О минимальных разрезах графа. // Кибернетика и вуз, 1971, вып. 4. С. 141-147.

42. Коршунов Д. Об одном алгоритме нахождения парасочетаний в конечных графах. // Кибернетика, № 1, Киев, 1975, с. 1-8.

43. Корячко В. П., Курейчик В. М., Норенков И. П. Теоретические основы САПР. Москва, Энергоатомиздат, 1987, 400 с.

44. Краснощеков П. С., Морозов В. В., Федоров В. В. Декомпозиция в задачах проектирования. // Техническая кибернетика, №2, 1979, с.7-17.

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

46. Крук Б. И., Попантонопуло В. Н., Шувалов В. П. Телекоммуникационные системы и сети. Наука, 1998 г.

47. Майнагашев С. М., Попков В. К. Максимальный поток в нестационарных сетях. // Системное Моделирование -10, Новосибирск, 1984 стр. 45-61.

48. Майника Э. Алгоритмы оптимизации на сетях и графах. Москва, Мир, 1981.

49. Малахов А. В., Солодов П. П. Язык программирования для разработки программ моделирования и обучения. // Информатика и проблемы телекоммуникаций тезисы докладов. Новосибирск, 1996, с. 27.

50. Малашенко Ю. Е., Новикова H. М. Многокритериальный и максиминный анализ многопродуктовых сетей. ВЦ АН СССР, Москва, 1988, 66 с.

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

52. Николаева (Соколова) О. Д., Попков В. К. Упаковка и покрытия в гиперсетях. Сб. трудов. Системное моделирование и информатика. Новосибирск, ВЦ СО РАН, 1985, с. 135 142.

53. Подиновский В. В., Гаврилов В. М. Оптимизация по последовательно применяемым критериям. // Советское радио, Москва, 1975, 190 с.

54. Полесский В. П. Об одном способе построения структурно-надежной сети связи. // Дискретные автоматы и сети связи. Наука, Москва, 1970.

55. Попков В. К. Гиперсети и структурные модели сложных систем. // Системное Моделирование -б, Новосибирск, 1981, с. 26-48.

56. Попков В. К., Бежаева Е. Б., Прохорова Н. И., Журихина Г. Ф. Алгоритмы и программы расчета нагрузки при моделировании сети электросвязи на ПЭВМ. // Информатика и проблемы телекоммуникаций тезисы докладов. Новосибирск, 1996, с. 28-29.

57. Попков В. К. Математические модели живучести сетей связи, Новосибирск, 1990 г., 235 с.

58. В. К. Попков Математические модели связности. Часть 2: Гиперграфы и гиперсети. Новосибирск, 2001,180 с.

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

60. Прангишвили И. В. Экспертные системы. // Вычислительная техника Системы Управление №2, 1990, Москва-София, стр. 3-16.

61. Рогинский В. Н. и др. Теория сетей связи. Москва, Радио и связь, 1981, 192 с.

62. Романовский И. В. Алгоритмы решения экстремальных задач. Москва, наука, 1977, 350 с.

63. Руа Б. Проблемы и методы принятия решений в задачах с многими целевыми функциями. // Вопросы анализа и процедуры принятия решений. Москва, Мир, 1976.

64. Соколов Н. А. Эволюция местных телефонных сетей. Пермь, Типография Книга, 1994, 375 с.

65. Соколова О. Д. Модели принятия решений при планировании сетей связи //Материалы III Международной конференции «Современные Информационные Технологии», Новосибирск, 1998, с. 102-105.

66. Соколова О. Д., Попков В. К. и др. Исследование и разработка инструментальных и графических средств организации диалога. Научно-технический отчет. Новосибирск, 1989 г.

67. Соколова О. Д., Попков В. К. и др. Разработка алгоритмов и методов оптимизации МСС при текущем проектировании. Научно-технический отчет. Новосибирск, 1990 г.

68. Соколова О. Д., Попков В. К. и др. Разработка математических и программных средств поддержки мультидиалогового моделирования и оптимизации информационных сетей. Научно-технический отчет. Новосибирск, 1993 г.

69. Соколова О. Д. Диалоговая система для решения задач теории графов и сетей связи. // Материалы Международной научно-практической конференции «Новые информационные технологии в университетском образовании», Новосибирск, 1999, с. 151-152.

70. Соколова О. Д. Модели принятия решений при планировании сетей связи. // Материалы III Международной конференции "Современные информационные технологии", (СИТ-98) Новосибирск, 1998, с. 102105.

71. Соколова О. Д. Диалоговая система моделирования сетей связи // Материалы Международного семинара «Перспективы развитиясовременных средств и систем телекоммуникаций», Хабаровск, 1999, с. 109-112.

72. Соколова О. Д. Критерии экспертных решений при планировании сетей связи. // Материалы IV Международной конференции «Современные информационные технологии 2000» («СИТ - 2000»), Новосибирск, 2000, с. 75-77.

73. Соколова О. Д. Экспертные оценки в задачах принятия решений с несколькими критериями // Труды XII Байкальской Международной конференции. Иркутск, 2001 г. Том 1а. с. 37-41.

74. Сухарев А. Г. Об оптимальных методах решения многокритериальных задач. // Известия АН СССР, сер. Техническая кибернетика, 1982, №3, с. 67-74.

75. Толмачева А. Ю., Раатс Ю. Ю., Оганесян С. А. Модели знаний в проектировании автоматизированных обучающих систем. // Вычислительная техника Системы Управление №2, 1990, Москва-София, с. 44-50.

76. Форд JL, Фалкерсон Д. Потоки в сетях. Москва, Мир, 1966, 276 с.

77. Фрэнк Г., Фриш И. Сети, связь и потоки. Москва, Связь, 1978, 447 с.

78. Харари Ф. Теория графов. Москва, Мир, 1973, 300 с.

79. Шахов В. В. Задачи назначения каналов в сотовой сети связи. Материалы Международной конференции «Вычислительные технологии и математическое моделирование в науке, технике и образовании», часть 4, 2002, Алматы, с.298-301.

80. Экономика связи. Под редакцией О. С. Срапионова и В. Н. Болдина. Москва, Радио и связь, 1998 г.

81. Якимов М. А. Об одном подходе к решению МР-полных задач теории графов. Труды ИВМиМГ СО РАН Серия Информатика, выпуск 4, стр. 158-164.