# 5. Основы проектирования сети доступа

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

Оптимальная структура САД выбирается на этапе расчета различных вариантов. Абоненты могут включаться в цифровую коммутационную станцию (ЦКС) одним их приведенных ниже способов:

- посредством индивидуальных двухпроводных физических абонентских линий (АЛ), включаемых в кросс ЦКС;
- через концентраторы или мультиплексоры, которые посредством ИКМ-трактов соединяются прямо с ЦКС;
- через концентраторы или мультиплексоры, которые, и свою очередь, подключаются к другому концентратору или мультиплексору;
- посредством индивидуальных АЛ, образованных так называемыми радиоудлинителями;
- с помощью цифровых систем с множественным доступом, сопрягаемым с ЦКС по ИКМ-трактам и так далее.

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

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

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

## Задача оптимизации размещения оборудования.

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

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

## Математическая модель.

Пусть требуется обеспечить связью n потребителей, характеризующихся подводимой емкостью Vj. Через множество X={1,2,…n} обозначим множество потребителей, а индекс j будем использовать для обозначения вида потребителя.

Пусть совокупность устройств (типов устройств), каждое из которых может в принципе обслуживать каждого потребителя из множества X, включает в себя m типов. Дадим устройству каждого типа номер i=1...m, и пусть множество U={1...m} соответствует совокупности устройств (СУ). Здесь пока не будем вводить значения параметров устройств, а учтем порядковый номер единственной характеристикой, по которой можно восстановить значения всех параметров (тип, емкость, стоимость и др.),

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

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

Введем переменные хij Î {0, 1},i Î U, jÎX , указывающие на то, какие потребители могут обслуживаться какими устройствами. Переменная величина xij принимает значение 1, если потребитель j может обслуживаться устройством i, и равна 0 в противном случае.

Для того чтобы быть допустимым, решение xij должно удовлетворять ограничениям S iÎU xij=1, j Î X

означающим, что каждый потребитель из X должен быть обслужен. Другими словами, для любого потребителя jÎ X должно быть назначено некоторое устройство I(j), для которого xij=1.

С каждым допустимым решением хij будем связывать множество {I(j)|iÎ X} и называть его совокупностью устройств u={i1…ir}, соответствующих данному решению.

С решением хij, помимо СУ, будем связывать также множества X(i), iÎ U. Для всякого iÎ U множество X(i) определим как {j|I=I(j)} и назовем областью подключения потребителей к устройству i.

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

S iÎU g i(vi)+S jÎ XS iÎ Ugijxij ® min; S IÎ Uxij=1, jÎ X;

xij Î {0,1}, iÎ U, jÎ X

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

Введем переменные хi = {0,1}, iÎ U. Если хi=1, то устройство i может войти в совокупность обслуживающих устройств. Тогда:

xi ³ xij, iÎ U, jÎ X;

S IÎ Uxi ≤ M;

xij Î {0,1}, iÎ U.

## Методы решения.

Как правило, потребители распределены по некоторой территории города, района или квартала. Рассмотрим частные случаи.

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

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

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

## Задачи оптимизации структуры сети.

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

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

Математическая модель. Задан граф G=(X,U) ; Х- множество вершин, в которых заканчиваются ССТ; U -множество ребер, соответствующих участкам ССТ; X¢ Í X- подмножество вершин, в которых расположены выносные модули: lij- длина участка трассы uij,. Требуется найти цикл С а графе G, проходящий по всем вершинам множества X΄ и имеющий минимальную длину

Σi,jÎ Clij—min

## Методы решения.

1. Рассмотрим задачу при X' = X. В этом случае требуется построить кольцо, проходящее по всем вершинам, т.е. предполагаем, что в них расположены выносные модули. Эта задача известна в теории графов как "задача коммивояжера". Она принадлежит к классу NP-трудных задач, для которых не существует точных непереборных эффективных алгоритмов. Поэтому задачу решают приближенными или эвристическими алгоритмами с вычислением нижней и верхней оценок решения.

2. В случае, когда X'ÌX, задача может быть сведена к "задаче коммивояжера" следующим методом.

## Построение аппроксимирующего графа.

Шаг 1. Вычислить по алгоритму Дейкстры кратчайшие пути между всеми парами вершин из множества X'.

Шаг 2. Построить полный граф G*=(X', U*), у которого множество вершин совпадает с множеством вершин X', а множество ребер соединяет все пары вершин. Для каждого ребра uij положить его вес равным длине кратчайшего пути из xi и xj в исходном графе G.

Шаг 3. На полученном графе можно решать "задачу коммивояжера", т.е. найти цикл минимального веса, проходящий по всем вершинам X'.

Шаг 4. Построив структуру цикла в графе G* выделить кратчайшие пути в графе G, соответствующие ребрам полученного цикла.

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

## Применение программной обьектно-ориентированной технологии для представления и структурного анализа САД.

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

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

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

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

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

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

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

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

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

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