Пусть заданы

1) координаты и виртуальный канал (ВК)

2) матрица расстояний между узлами коммутации

3) матрица трафика между ВК

4) набор типов линий связи с соответствующими параметрами надежности и пропускной способности

5) набор типов ВК с характеристиками надежности и интенсивности обслуживания

где –коэффициент готовности; – интенсивность возобновления работоспособности; – интенсивность обслуживания;

6) набор типичных центров ТО (ЦТО) средств тестового диагностирования, которые различаются составом, и тому подобное.

Нужно определить:

1) топологию базовой сети ;

2) распределение потоков в линиях сети ;

3) распределение пропускных способностей линий

;

4) производительность ВК

;

5) число и места размещения ЦТО

;

6) типы ЦТО

;

7) разбивка множества ВК на зоны ТО

с тем, чтобы минимизировать приведенные расходы на сеть в целом:

,

где – приведенные расходы на базовую сеть; – приведенные расходы на СТО.

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

Последовательность действий такова.

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

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

Для оптимизации топологии сети используются так называемые MST -алгоритмы или алгоритмы, построенные на основе MST-алгоритмов (например, метод размытых эвристик – МРЭ).

В качестве методов локальной оптимизации могут быть использованы наиболее распространенные и универсальные методы трансформации – методы замены линий.

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

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

Подход, основанный на локальной оптимизации, содержит две возможности:

• после каждой коррекции структуры сети оптимизировать структуру СТО;

• проводить оптимизацию структуры СТО только после нахождения локального минимума в задании оптимизации структуры сети.

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

Поиск по сайту: