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

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

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

ЗАКЛЮЧЕНИЕ

.