В рубрику "Multiplay" | К списку рубрик | К списку авторов | К списку публикаций
А.Н. Котов, вице-президент ЗАО "Корпорация Телевик"
В связи с бурным ростом сектора ИКТ огромную роль играют сети распределения данных.
Перспективным направлением теоретических и практических исследований в области построения сетей является разработка методов построения и оптимизации структуры распределительных сетей. Сложность решения данной задачи обусловливается большим количеством параметров исходных данных и широким разбросом их значений, а также большим числом различных типов используемого оборудования.
В статье описывается метод, основанный на модифицированном алгоритме Дейкстры, позволяющий сократить затраты при построении распределительных сетей. При разработке метода оптимизации в качестве объекта исследований рассматривались магистральные распределительные сети 2-го (районный уровень) и 3-го (окружной уровень) классов. Разработанный метод оптимизации структуры распределительной сети апробирован при проектировании сетей в ряде районов новостроек в Москве.
В качестве критерия оптимальности при оценке эффективности инвестиций в строительство используется критерий минимума суммарных затрат на развертывание распределительной сети.
Задача минимизации заключается в том, чтобы из всей совокупности распределительных сетей выбрать одну, минимизированную по стоимости, то есть нахождение минимума суммарного веса ребер распределительной сети, соответствующий минимуму затрат на развертывание распределительной сети.
Сущность методики заключается в модификации алгоритма Дейкстры выбора кратчайшего пути в сетях с коммутацией пакетов.
Модификация состоит в изменении целевой функции и выражений для вычисления обновляемых весов путей. Сравнительная характеристика модифицированного и оригинального алгоритмов представлена в таблице.
Отличие этих двух методик при вычислении обновляемых весов путей заключается в следующем. Выбор минимальных путей при их обновлении производится не только от корневого узла, но и от уже построенного (к данному шагу процедуры оптимизации) сегмента распределительной сети, то есть от произвольного узла, уже включенного в распределительную сеть. В общем случае данные алгоритмы дают различные варианты сетей, хотя при некоторых наборах значений исходных данных (весов ребер) результирующие сети могут совпадать.
На первом этапе формируется матрица весов ребер исходной сети, подлежащей оптимизации. Данная операция выполняется на этапе проектно-изыс-кательских работ с учетом топологических особенностей района развертывания распределительной сети и элементов применяемого оборудования.
На втором этапе выполняется модифицированный алгоритм Дейкстры. Процедура оптимизации заключается в следующем. На каждом шаге определяется совокупность путей с минимальным весом от уже построенного сегмента сети, обязательно включающего первый узел (головную станцию), до всех остальных узлов сети. В результате получается структура распределительной сети с минимальным суммарным весом входящих в нее ребер, то есть с минимальными затратами на ее построение. В общем случае структура является радиально-узло-вой. В результате выполнения алгоритма формируются массив путей из корневого узла во все узлы сети и соответствующий массив весов путей.
На третьем этапе полученные массивы используются для формирования минимальной по стоимости построения схемы распределительной сети с учетом привязки к местности.
После проведения ряда сравнений двух алгоритмов было получено среднее значение выигрыша в стоимости, который составляет около 10% в случаях, когда данные алгоритмы дают различные результаты.
Рекомендации по применению метода оптимизации могут быть сформулированы следующим образом.
Опубликовано: Журнал "Технологии и средства связи" #4, 2007
Посещений: 9560
Автор
| |||
В рубрику "Multiplay" | К списку рубрик | К списку авторов | К списку публикаций
