ISSN 1991-3087
Рейтинг@Mail.ru Rambler's Top100
Яндекс.Метрика

НА ГЛАВНУЮ

УДК 621.395.74.

 

Метод минимизации суммарных затрат по развертыванию распределительных сетей на основе модифицированного метода Дейкстры.

 

Котов Алексей Николаевич,

соискатель Санкт-Петербургского Государственного Университета Телекоммуникаций им. Проф. М.А. Бонч-Бруевича,

вице-президент ЗАО «Корпорация Телевик».

 

Введение.

 

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

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

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

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

Оптимизация структуры распределительных сетей позволит повысить эффективность инвестиций в строительство инфокоммуникационных систем.

В данной статье описывается метод, позволяющий сократить затраты при построении распределительных сетей. Данный метод описывает:

·                     математическую модель распределительной сети систем кабельного телевидения;

·                     методику снижения стоимости построения распределительной сети СКТ на основе модифицированного алгоритма Дейкстры.

В соответствии с ГОСТ Р 52023-2003 «Сети распределительные приемных систем кабельного телевидения и радиовещания. Основные параметры. Технические требования. Методы измерений и испытаний» системы кабельного телевидения можно разделить на несколько классов в зависимости от области применения, вида сигналов и состава оборудования.

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

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

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

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

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

Вещательная функция - это доставка всем абонентам сети общего пакета вещательной информации. Данная услуга будет занимать 80-90 % от пропускной способности сети.

Функция сети доступа - это предоставление абоненту сети индивидуальных услуг по его запросу. Данная услуга будет занимать 10-20 % от пропускной способности сети.

Исходными данными при разработке метода оптимизации являются:

·                     информация о территориальном расположении объектов некоторого класса СКТ;

·                     стоимость элементов распределительной сети;

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

При решении задачи оптимизации накладываются ограничения:

·                     на количество обслуживаемых абонентов;

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

В качестве критерия оптимальности при оценке эффективности инвестиций в строительство используется критерий минимума суммарных затрат на развертывание распределительной сети СКТ.

На основании выбранного критерия оптимальности формальная постановка основной задачи исследований имеет вид:

 

при ограничениях {Nаб>Nаб тр, Nу>Nу тр, Куу тр},                   (1)

где  - суммарные затраты на развертывание распределительной сети СКТ; VARРС – множество допустимых вариантов построения распределительной сети СКТ, Varl – анализируемый вариант структуры распределительной сети СКТ; Nаб, Nаб тр, Nу, Nу тр – действующее и требуемое количество абонентов и услуг; Ку, Ку тр – качество услуг.

Метод снижения затрат на построение распределительной сети СКТ включает в себя разработку математической модели распределительной сети СКТ и методику снижения затрат на ее построение.

Математическая модель распределительной сети систем кабельного телевидения включает модель иерархической структуры СКТ, модель оборудования распределительной сети СКТ и модель варианта структуры распределительной сети СКТ.

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

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

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

 

Модифицированный метод Дейкстры.

 

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

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

·                     n – число узлов распределительной сети;

·                     D(k) - вес пути (сумма весов рёбер вдоль данного пути) от корневого узла 1 до узла k;

·                     l(m, k) - вес ребра между m-м и k-м узлами;

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

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

Таблица 1.

Сравнительная характеристика модифицированного алгоритма и алгоритма Дейкстры.

Модифицированный алгоритм

Алгоритм Дейкстры

1. Целевая функция

Определяется суммарным весом ребер всех путей, составляющих распределительную сеть

Определяется весом каждого из путей, начинающихся в корневом узле

2. Критерий оптимальности

Минимум суммарного веса ребер всех путей, составляющих распределительную сеть

Минимум веса пути из корневого узла в каждый узел распределительной сети

3. Обновление весов путей

Di(k) = Di-1(mk)+l(mk, k),  m Ì N, k Ë N,

где mk=argmin[l(m, k)] –номер узла сети, при котором функция l(m, k) принимает минимальное значение

Di(k) = min[Di-1(k), Di-1(m)+l(m, k)],   

где Di(k) – вес пути из корневого узла в k-й узел на i-ом шаге процедуры оптимизации

 

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

 

Этапы реализации методики.

 

На первом этапе формируется матрица весов ребер исходной сети, подлежащей оптимизации:

 

l11

l12

l1j

l1n

 

 

 

l21

l22

l2j

l2n

 

 

 

 

 

 

 

 

 

 

 

L=

li1

li2

lij

lin

 

(2)

 

 

 

 

 

 

 

 

 

 

ln1

ln2

lnj

lnn

 

 

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

На втором этапе непосредственно выполняется модифицированный алгоритм оптимизации.

·                     Начальный шаг. Формируется исходное множество N = {1}, D0(1) = 0. Для каждого узла k, не принадлежащего множеству N, устанавливается D0(k) = l(1, k). Формируется множество начальных путей вида Р0(k) = [1_k], где в квадратных скобках указаны номера узлов, образующих маршрут.

·                     Каждый последующий i-й шаг (i=1,2…,n-1) значения Di(k) обновляются для всех узлов, не принадлежащих множеству N. Среди обновлённых значений Di(k) выбирается минимальное, а соответствующий ему узел m включается во множество N. На основании значений Di(k) производится обновление путей Рi(k). Процедура повторяется, пока во множество N не войдут все узлы исходной сети.

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

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

 

Выводы.

 

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

Рекомендации по применению метода оптимизации структуры распределительной сети СКТ могут быть сформулированы следующим образом.

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

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

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

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

 

Поступила в редакцию 24 сентября 2007 г.

2006-2019 © Журнал научных публикаций аспирантов и докторантов.
Все материалы, размещенные на данном сайте, охраняются авторским правом. При использовании материалов сайта активная ссылка на первоисточник обязательна.