Содержание к диссертации
Стр.
ВВЕДЕНИЕ 4
ГЛАВА I. ВЫБОР МОДЕЛИ ПЕРВИЧНОЙ СЕТИ СВЯЗИ И ИСХОДНЫХ
ДАННЫХ ПРИ ОПТИМИЗАЦИИ ЕЕ СТРУКТУРЫ II
Теоретическая модель первичной сети СВЯЗИ Ц
Расчет числа междугородных каналов 14
Общие замечания 14
Нагрузка на абонентскую линию 15
Оценка качества обслуживания вызовов... 17
Метод расчета и пример 20
1.3. Прогнозирование междугородной телефонной на
грузки в условиях СРВ 31
1.4. Выводы по первой главе 37
ГЛАВА 2. РАЗРАБОТКА МЕТОДОВ ОПТИМИЗАЦИИ СТРУКТУРЫ ПЕРВИЧ
НОЙ СЕТИ СВЯЗИ 39
Постановка задач 39
Нижняя граница критерия общей длины каналов
(ОДК) связующего дерева 43
Нижняя граница ОДК в случае без фиксированных ребер 43
Нижняя граница ОДК подмножества деревьев с фиксированными ребрами 47
Алгоритм нахождения оптимального связующего дерева по критерию минимальной ОДК 52
Алгоритм нахождения оптимального связующего дерева по критерию минимальной общей стоимости (ОС) 56
Пример 58
Выводы по второй главе 67
Стр. ГЛАВА 3. РАЗРАБОТКА МЕТОДОВ ОПТИМИЗАЦИИ РАЗВИТИЯ
СТРУКТУРЫ ПЕРВИЧНОЙ СЕТИ СВЯЗИ 69
Постановка задачи 69
Исследование целевой функции 71
Верхняя граница приращения стоимости развиваемой сети 76
Алгоритм решения задачи 78
Пример 80
3.5. Приближенный метод оптимизации структуры раз
виваемой сети 82
Пример 85
3.6. Выводы по третьей главе 86
ГЛАВА 4. ОПТИМИЗАЦИЯ СТРУКТУРЫ ПЕРВИЧНОЙ СЕТИ СО СТЕПЕН
НОЙ АППРОКСИМАЦИЕЙ ФУНКЦИИ СТОИМОСТИ 88
Постановка задачи 88
Метод решения 89
Пример 95
4.3. Метод замены ребра , 98
Пример 104
4.4. Выбор структуры первичной сети связи в усло
виях СРВ 106
4.5. Выводы по четвертой главе 108
ЗАКЛЮЧЕНИЕ НО
Литература 112
Введение к работе
Построение сетей электросвязи включает комплекс разнообразных задач от математических и технических до экономических и общественно-политических, решение которых имеет целью обеспечить приемлемый компромисс между необходимыми характеристиками сети и затратами на ее сооружение.
Задачи такого класса в их полной и общей постановке в силу их исключительной сложности теоретически и практически неразрешимы [і4, 30, 58] . Это заставляет исследователей обращаться к частным задачам.
Важной задачей, которая должна решаться при планировании сети, является выбор структуры первичной сети связи, обеспечивающей передачу всех информационных потоков наиболее экономичным образом. Это объясняется тем, что структура сети среди других факторов оказывает существенное влияние на необходимые для реализации сети затраты, значительная часть которых приходится на линейные сооружения.
Такая задача актуальна, в частности, для социалистической Республики Вьетнам (СРВ), где сеть связи страны находится на стадии формирования. От выбора конфигурации сети зависит успешное развитие средств связи в будущем.
С учетом вышеизложенного исследование и разработка методов оптимизации структуры первичной сети связи является актуальной темой.
Первичная сеть связи представляет собой совокупность сетевых узлов, станций и линий передачи, образующих сеть типовых каналов передачи и типовых групповых трактов для удовлетворения потребностей предприятий, организаций, учреждений и населения
страны в передаче любой информации, преобразованной в сигналы электросвязи [и] . Структура первичной сети характеризуется наличием ветвей между отдельными пунктами и пропускной способностью этих ветвей, измеряемой числом каналов тональной частоты [14] .
Сложность задачи выбора, структуры первичной сети связи обусловливается, в основном, следующими факторами:
Комбинаторной природой задачи, что приводит к большим методологическим и вычислительным трудностям при решении задач реальной размерности.
Многокритериальностью задачи, что приводит к трудности полного математического описания объекта исследования, а также к невозможности получения оптимального решения одновременно по нескольким критериям.
Нелинейностью функции стоимости элементов сети, вызывающей необходимость их аппроксимации, что уменьшает точность решения.
Для преодоления этих трудностей существуют различные способы разделения общих задач на более простые. При этом задача синтеза структуры первичной сети может быть решена в несколько этапов.
Так, исходя из особенностей организации эксплуатационного процесса, а также из сложившейся структуры административно-технического управления, первичная сеть по территориальному принципу, например, в условиях СССР, может быть разделена на магистральную, зоновые и местные первичные сети [15, 48] . При рассмотрении вопросов построения первичной сети можно решать задачи выбора структуры раздельно для каждой из перечисленных сетей.
Критерии при выборе структуры первичной сети связи могут быть различными [з, 4, 35, 37, 59] . К их числу можно отнести стоимостные, надежностные, структурные или более обобщенные критерии (например, эффективность сети в различном ее понимании). Выбор критерия диктует конкретная задача. Чаще всего в задачах выбора структуры сети стоимостные критерии используются как целевые, а структурные, надежностные требования выступают в качестве ограничивающих факторов.
Задача оптимизации структуры первичной сети по критерию минимальной стоимости (при различной ее функциональной зависимости) к настоящему времени не имеет достаточно эффективного метода решения. Она может быть сформулирована как задача целочисленного программирования [б, 57] . Но это связано с большими вычислительными трудностями.
Особенность комбинаторных методов оптимизации заключается в том, что быстродействие их алгоритмов во многом зависит от направления поиска. Поэтому представляется целесообразным совместно использовать точные комбинаторные методы с приближенными эвристическими. При этом полученные с помощью приближенных методов предпочтительные варианты могут быть проверены точным алгоритмом.
Оптимальный вариант сети по стоимости может содержать число ветвей, находящееся в интервале от (Л-I) до /2(/2-1)/2 (где - П - число узлов в сети). В [36, 58] на основании применения комбинаторных методов разработаны алгоритмы оптимизации структуры первичной сети связи по различным критериям, причем в качестве исходной рассматривается полносвязная схема сети. Однако во многих случаях, например, в сетях вытянутой формы длина обходных путей незначительно превышает длину прямых путей. Это
дает основание предположить, что оптимальный вариант сети более близок по количеству ветвей к древовидной структуре, чем к полносвязной схеме. С этой точки зрения представляет интерес разработка методов оптимизации структуры первичной сети связи, когда в качестве исходной рассматривается древовидная структура.
Целью диссертационной работы является исследование и разработка методов оптимизации структуры первичной сети связи с учетом особенностей условий СРВ.
В работе использованы теория сетей связи, теория телеграфика, теория графов и комбинаторные методы оптимизации.
Первая глава диссертации посвящена выбору теоретической модели первичной сети связи и исходных данных при оптимизации ее структуры.
Наиболее удобно для исследования представить первичную сеть связи в виде связного ненаправленного графа. При этом такие понятия теории графов, как вершины, ребра, пути, потоки... можно сопоставить подобным понятиям в реальной сети. Таким образом, можно использовать результаты теории графов для исследования задачи оптимизации структуры первичной сети.
Ввиду того, что междугородная телефонная связь является доминирующим потребителем каналов первичной сети, в главе обосновывается и разрабатывается метод расчета числа междугородных телефонных каналов. При этом учитывается поведение и интересы абонентов, а за исходную величину принимается не поступающая, а обслуженная нагрузка, т.е. число разговоров с их средней продолжительностью, которые надо пропустить в рассматриваемом направлении. Это лучше отвечает требованиям задачи. Число междугородных каналов считается оптимальным при минимальных суммар-
ных затратах сети и ее пользователя.
На основании анализа особенностей условий СРВ и опубликованных результатов исследования в главе обосновывается метод прогнозирования междугородной телефонной нагрузки на планируемый период.
Метод основан на предположении о пропорциональности объема информационных потоков квадрату темпа роста национального дохода, который известен из общего плана развития народного хозяйства страны, распределение информационных потоков осуществляется по результатам статистических данных, а также по планируемым емкостям местных сетей.
Во второй главе решаются две задачи:
Нахождение оптимального варианта связующей древовидной сети по критерию минимальной общей длины каналов.
Нахождение оптимального варианта связующего дерева по критерию минимальной общей стоимости при линейной зависимости стоимости ребра от его емкости.
Обе задачи, поставленные в главе, решаются комбинаторным методом ветвей и границ. Нижней границе критерия соответствует идеальный случай, когда требуемые внешние потоки передаются по возможным кратчайшим путям, причем возможным наилучшим образом, т.е. по принципу "больший поток по меньшему пути". Возможные кратчайшие пути образуются из возможных кратчайших ребер, которые, в свою очередь, можно определить по известному алгоритму Прима [35] .
Третья глава диссертации посвящена разработке методов оптимизации развития структуры существующей сети для удовлетворения растущих потребностей, решение этой задачи основано на следующей закономерности: снижение общей длины каналов сети за счет
добавления одного и того же нового ребра имеет тем меньшее значение, чем больше количество ребер в структуре сети при этом добавлении, эта закономерность позволяет упростить задачу (некоторые ребра исключить из рассмотрения, другие заранее включить в состав оптимального варианта) и определить верхнюю границу приращения стоимости при наращивании структуры сети. Это дает возможность решать задачу комбинаторным методом ветвей и границ.
В этой главе также разрабатывается приближенный эвристический метод решения поставленной задачи, который заключается в повторяющейся процедуре добавления и исключения ребер для улучшения критерия стоимости, начиная от структуры существующей сети. Состав ребер, подлежащих добавлению или исключению все сужается и получается в конце концов вариант сети, который нельзя улучшить ни добавлением, ни исключением ребер; он принимается за субоптимальный.
Четвертая глава диссертации посвящена оптимизации структуры связующего дерева по критерию минимальной стоимости в случае степенной аппроксимирующей функции стоимости. Задача, решаемая в этой главе, может быть поставлена аналогично задаче во второй главе с той лишь разницей, что линейная зависимость стоимости заменена на степенную.
Анализ целевой функции показывает возможность решения задачи комбинаторным методом ветвей и границ, нижней оценке критерия стоимости соответствует идеальный случай, когда требуемые внешние потоки передаются с возможно меньшей стоимостью (передачи единицы потока) по принципу "больший поток по пути с меньшей стоимостью передачи единицы потока".
Предлагается приближенный метод решения поставленной за-
дачи - метод замены ребра. В результате анализа изменения прохождения потока при замене ребер, показывается целесообразность проверки возможности замены ребра только на соседнее ребро, что требует наименьшего объема вычислений при замене ребра, Серией таких последовательных проверок можно проверить возможность любой замены. Когда все возможности замены исчерпаны, алгоритм прекращается и полученный вариант является локальным оптимумом решения.
Оосновные результаты, выносимые на защиту.
Метод расчета оптимального числа междугородных каналов.
Алгоритм решения задачи оптимизации структуры древовидной сети по критерию минимальной общей длины каналов.
Алгоритмы решения задач оптимизации структуры древовидной сети по критерию минимальной общей стоимости при линейной и степенной зависимости стоимости ветви от ее емкости.
Алгоритм решения задачи оптимизации развития структуры первичной сети по критерию общей стоимости.
Приближенные алгоритмы решения поставленных задач.
- II -
