автореферат диссертации по радиотехнике и связи, 05.12.14, диссертация на тему:Исследование и разработка методов оптимизации структуры первичной сети связи (на примере сети связи Социалистической Республики Вьетнам)

ВВЕДЕНИЕ.

ГЛАВА I. ВЫБОР МОДЕЛИ ПЕРВИЧНОЙ СЕТИ СВЯЗИ И ИСХОДНЫХ

ДАННЫХ ПРИ ОПТИМИЗАЦИИ ЕЕ СТРУКТУРЫ.II

1.1. Теоретическая модель первичной сети связи.ц

1.2. Расчет числа междугородных каналов.

1.2.1. Общие замечания

1.2.2. Нагрузка на абонентскую линию

1.2.3. Оценка качества обслуживания вызовов.

1.2.4. Метод расчета и пример.

1.3. Прогнозирование междугородной телефонной нагрузки в условиях СРВ.

1.4. Выводы по первой главе

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

2.1. Постановка задач

2.2. Нижняя граница критерия общей длины каналов

ОДК) связующего дерева.

2.2.1. Нижняя граница ОДК в случае без фиксированных ребер.

2.2.2. Нижняя граница ОДК подмножества деревьев с фиксированными ребрами

2.3. Алгоритм нахождения оптимального связующего дерева по критерию минимальной ОДК

2.4. Алгоритм нахождения оптимального связующего дерева по критерию минимальной общей стоимости (ОС)

2.5. Пример.

2.6. Выводы по второй главе

ГЛАВА 3. РАЗРАБОТКА МЕТОДОВ ОПТИМИЗАЦИИ РАЗВИТИЯ

СТРУКТУРЫ ПЕРВИЧНОЙ СЕТИ СВЯЗИ.

ЗЛ. Постановка задачи.

3.2. Исследование целевой функции.

3.3. Верхняя граница приращения стоимости развиваемой сети.

3.4. Алгоритм решения задачи.

Пример.

3.5. Приближенный метод оптимизации структуры развиваемой сети.

Пример.

3.6. Выводы по третьей главе.

ГЛАВА 4. ОПТИМИЗАЦИЯ СТРУКТУРЫ ПЕРВИЧНОЙ СЕТИ СО СТЕПЕННОЙ АППРОКСИМАЦИЕЙ ФУНКЦИИ СТОИМОСТИ.

4.1. Постановка задачи.

4.2. Метод решения.

Пример.

4.3. Метод замены ребра

Пример

4.4. Выбор структуры первичной сети связи в условиях СРВ.

4.5. Выводы по четвертой главе

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

Задачи такого класса в их полной и общей постановке в силу их исключительной сложности теоретически и практически неразрешимы [14, 30, 58] . Это заставляет исследователей обращаться к частным задачам.

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

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

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

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

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

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

2. Многокритериальностью задачи, что приводит к трудности полного математического описания объекта исследования, а также к невозможности получения оптимального решения одновременно по нескольким критериям.

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

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

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

Критерии при выборе структуры первичной сети связи могут быть различными [з, 4, 35, 37, 59] . К их числу можно отнести стоимостные, надежностные, структурные или более обобщенные критерии (например, эффективность сети в различном ее понимании). Выбор критерия диктует конкретная задача. Чаще всего в задачах выбора структуры сети стоимостные критерии используются как целевые, а структурные, надежностные требования выступают в качестве ограничивающих факторов.

Задача оптимизации структуры первичной сети по критерию минимальной стоимости (при различной ее функциональной зависимости) к настоящему времени не имеет достаточно эффективного метода решения. Она может быть сформулирована как задача целочисленного программирования [б, 57] . Но это связано с большими вычислительными трудностями.

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

Оптимальный вариант сети по стоимости может содержать число ветвей, находящееся в интервале от (Л-I) до /2(/2-1)/2 (где - П - число узлов в сети). В [36, 58] на основании применения комбинаторных методов разработаны алгоритмы оптимизации структуры первичной сети связи по различным критериям, причем в качестве исходной рассматривается полносвязная схема сети. Однако во многих случаях, например, в сетях вытянутой формы длина обходных путей незначительно превышает длину прямых путей. Это дает основание предположить, что оптимальный вариант сети более близок по количеству ветвей к древовидной структуре, чем к полносвязной схеме. С этой точки зрения представляет интерес разработка методов оптимизации структура первичной сети связи, когда в качестве исходной рассматривается древовидная структура.

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

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

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

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

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

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

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

Во второй главе решаются две задачи:

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

2. Нахождение оптимального варианта связующего дерева по критерию минимальной общей стоимости при линейной зависимости стоимости ребра от его емкости.

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

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

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

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

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

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

Оосновные результаты, выносимые на защиту.

1. Метод расчета оптимального числа междугородных каналов.

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Автоматическая междугородная и сельская телефонная связь (Бакалейщик Ф.Б., Брунина Ю.З., Зайонковский Е.А. и другие), Под ред. Е.А. Зайовшвского. - М.: Связь, 1976. - 312 с.

2. Автоматические системы коммутации (Иванова О.Н., Копп М.Ф., Коханова З.С., Метельский Г.Б.) Под ред. О.Н. Ивановой.-2-е изд. М.: Связь, 1978.

3. Аджемов С.А. Метод анализа схем построения сети междугородных связей. Сб.трудов ЩИИС, вып. I, 1961, с. 43-61.

4. Аджемов С.А. Об оценке построения сети по надежностии стоимости. Сб,научных трудов ЦНИИС, вып. 2, 1961, с. 5-17.

5. Башарин Г.П. Таблицы вероятностей и средних квадратичных отклонений потерь на полно доступном пучке линий. М.: АН СССР, 1962.

6. Богатырев В.А. Применение целочисленного программирования для синтеза оптимальных сетей связи. В сб. Информационные сети и коммутации. М.: Наука, 1968, с. 78-81.

7. Вайнер И.И., Сральник Я.В. Об одном методе построения сети связи. В сб.: Кибернетика. М.: Наука, 1967, с. 302-312.

8. Геденидзе Г.С. и др. Проектирование первичной внутризоновой сети связи с помощью ЭВМ. Электросвязь, 1979, № 4.

9. Гильберт Э.Н., Поллак Г.О. Минимальные деревья Штейне-ра. В кн.: Кибернетический сборник, Новая серия, вып. 8. М.: Мир, 1971, с. 19-50.

10. Глинка В.И. Проблемы развития телефонной связи в СССР.-Электросвязь, 1976, № 3, с. 1-6.

11. ГОСТ 2348-77. Единая автоматизированная сеть связь. Термины и определения.- из

12. Давыдов Г.Б. Пути оптимизации развития сетей связи. -Электросвязь, 1976, с. 4-II.

13. Давыдов Г.Б»» Иванова О.Н. Основные направления научно-технического процесса телефонной связи.- М.: Связь, 1974, 64 с.

14. Давыдов Г.Б., Рогинский В.Н. Проблемы построения сетей и коммутация. М.: Наука, 1968, с. 5-29.

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

16. Давыдов Г.Б. Социально-экономические аспекты развития сети электросвязи. В кн.: Информация и информационные сети. М.: Наука, 1976.

17. Девис Д., Барбер Д. Сети связи для вычислительных машин. Пер. с англ. М.: Мир, 1976.

18. Демина Е.В. Некоторые вопросы построения сетей связис учетом динамики их развития. Автореферат диссертации на соискание ученой степени кандидата технических наук. М.: 1972.

19. Денисьева О.М. О совместном обслуживании вызовов разных категорий. В сб.: Научные труды ЦНИИС, 1979, вып. 2.

20. Зайончковский Е.А., Пшеничников А.П., Романцев В.М. Автоматическая междугородная телефонная связь. м.: Радио и связь, 1984, 296 с.

21. Кармазов М.Г., Траубенберг И.А., Петрушин И.П. Организация и планирования предприятий электрической связи. М»: Связь, 1973.

22. Корнышев Ю.Н. Повторные вызовы при междугородной связи. Электросвязь, 1974, №1, с. 35-41.

23. Коршунов Ю.М. Математические основы кибернетики. М.: Энергия, 1972.

24. Котов A.B. Система "Абонент-телефон" Инженерно-психологические и эргономические критерии в телефонии.- электросвязь,1976, № 3, с. 41-45.

25. Котов А.В. Человеческие факторы в телефонии. М.: Связь, 1980. - 80 с.

26. Лазарев В.Г., Саввин Г.Г. Сети связи. Управление и коммутации. -М.: Связь, 1973.

27. Лившиц B.C., Пшеничников А.П., Харкевич А.Д. Теория телеграфика. 2-е изд.- М.: Связь, 1979.

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

29. Матлин Г.М. Проектирование оптимальных систем производственной связи. М.: Связь, 1973, 415 с.

30. Нейман В.И, Структуры систем распределения информации. М.: Радио и связь, 1983, 216 с.

31. Организация, планирование и управление предприятиями электрической связи (Демина Е.В., Траубенберг И.А., Иодко Е.К., Майофис Л.И.) М.: Связь, 1979.

32. Ope 0. Графы и их применение. М.: Мир, 1967.

33. Основы методологии перспективного планирования потребностей в связи общего пользования. М.: Связь, 1964.

34. Поваров Г.Н. О структурной теории сетей связи. В кн.: Проблемы передачи информации. Вып. I, М.: Изд. АН СССР, 1959,с. 126-140.

35. Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения. В кн.: Кибернетический сборник. Вып.2, М.: ИИЛ, 1961, с. 95-107.

36. Пшеничников А.П., Чан Ван Шон. Метод оптимизации структуры сети по критерию минимальной суммарной протяженности каналов. Труды учебных институтов связи. Сети, узлы связи и распределения информации. 1981, с. 59-64.

37. Пяткин Е.Г. Критерий эффективности сети связи и егои его использование для синтеза структуры сети. В кн.: Построение устройств управления сетями связи. М.: Советское радио, 1974.

38. Рациональные научно-обоснованные нормы потребления услуг связи. отчет ВДИИС. М.: 1973.

39. Рейнгольд Э. Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика (Пер.с англ. Под ред. В.Б. Алексеева. -М.: Мир, 1980.

40. Решения У-го съезда Коммунистической партии Вьетнама.

41. Рощинский В.Н. К определению нагрузок в сетях связи с коммутацией каналов. Электросвязь, 1979, № 5, с. 34-39.

42. Рощинский В.Н. Денисьева О.М., Данг Динь Лам. Об одном подходе к нормированию качества обслуживания в телефонии.-Электросвязь, 1983, № б, с. 5-8.

43. РоГинский В.Н. Основы дискретной автоматики (Статика и динамика дискретных автоматов). М.: Связь, 1975. .

44. Рыбников Л.К., Гармаш В.А. Развитие электросвязи на современном этапе научно-технической революции. В кн.: Информация и информационные сети. - М.: Наука, 1977, с. 83-91.

45. Самойленко С.И., Агаян A.A. Методы поиска решений.-В кн.; Проблемы случайного поиска, Рига: Знание, 1980, вып.8, с.15-62.

46. Сачков В.Н. Введение в комбинаторные методы дискретной автоматики. М.: Наука, 1982, 384 с.

47. Сообщение телефонное. Характеристики, Термины и определения. ГОСТ 20733-75.

48. Теория сетей связи (В.Н.Рсг^нский , А.Д. Харкевич, М.А. Шнепс, Г.Б. Давыдов, А.Я. Толчан) Под ред. В.Н.Ропинского.-М.-Радио и Связь, 1981, 192 с.

49. Толчан А.Я. Об одном способе оптимизации структуры сети связи. В кн.: Проблемы передачи информации. Вып.15, М.: Изд. АН СССР, 1963, с. 42-60.

50. Траубенберг И.А. Краткосрочное планирование междугородного телефонного обмена. Труды учебных институтов связи, 1968, № 42.

51. Фарбер Ю.Д. Перспективы развития магистральной сети.-Электросвязь, 1975, Ш, с. 12-18.

52. Форд Д., фалкерсон Д. Потоки в сетях: Пер. с англ. М.; Мир, 1966.

53. Франк Г., Фриш И. Сети, связь и потоки: Пер. с англ. (под ред. Поспелова. М.: Связь, 1978.

54. Франк Г., Чжоу В. Топологическая оптимизация сетей ЭВМ. В кн.: Системы передачи данных с сети ЭВМ. ТИИЭР, М.: 1977.

55. Харкевич A.A. Информация и техника. Коммунист, 1962, № 17, с. 93-102.

56. Хауштейн Г. Метод прогнозирования в социалистической экономике. М.: Прогресс, 1971, 397 с.

57. ХУ Т. Целочисленное программирование и потоки в сетях. М.: Мир, 1974, 519 с.

58. Чан Ван Шон. Исследование и разработка методов оптимизации структуры сети электросвязи (на примере СРВ). Автореферат диссертации на соискание ученой степени к.т.н. М.: 1982.

59. Ченцов В.М. Системы распределения информации. Синтез структуры и управления. М.: Связь, 1980, 144 с.

60. Шнепс М.А. Основы расчета автоматической сети связи при наличии повторных попыток. В кн.: Методы развития теории телеграфика. - М.: Наука, 1979, с. 19-29.

61. Экономика связи (Срапионов О.С., Подгородецкий И.А., Соловейчик Л.М. и др.) Под ред. О.С.Срапионова. 2-е изд. м.: Связь, 1974, 392 с.

62. Юдин д.Б., Гольштейн Е.Г. Задачи и методы линейного программирования. -М.: Сов.радио, 1961.

63. DaL Monte G-. Analis dipassate prer/sieni alla luce deäo swiluppe fefe/onice feaSfe

64. Rerue Fl ICE, ms, Vis, №1 (43-4-8) .

65. Camerini-PM., FrattaL, Maff/ol/F. Some ri/sults on ike des/gn 0/ free sfri/cft/redcomwntcat/'on neti^o/cs . S-iA Infernat/enal Tele traff/с Congress, Torremofines > 1973.

66. Dr. Hermann Eßen ßerger. Tefephenfe/lnekmerent u/e/cfi/ng der ureff Technische Mt fei fang en i?ss} .\Гг#.

67. Karp U.M. Reduc/S/f/fy among com6/'nafort а l prüSiems — ß cf. Symp en Complex/fy о/

68. Compufaf/ons. fJodредакцией М/t/er R. Et> Thatcher J. W. Plenum Press, AfeurYark s wz .

69. Sofemajor J.M-, Mi/rr-au- Lasse M. А. D/seno de s/'sfemas de соттип/сас/м anmetüd de ingen/er/a de s/'sfemas —

70. Mundo e/ecfren/co", тз, VS9 JV° 15, с.зз-4-t.