4.6. ВЫБОР ПАРАМЕТРОВ НАДЕЖНОСТИ ЭЛЕМЕНТОВ СЕТИ

Оптимизация надежности линий связи сети

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

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

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

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

и выполняется ограничение — имеющиеся суммарные средства на резервирование линий связи сети.

Анализ соотношений, определяющих вероятность связности сети [48], позволяет сделать следующие выводы:

1. Непосредственное решение задачи оптимизации в данном случае затруднено ввиду несепарабельного характера критериальной функции.

2. Выражение для представляет собой сумму определенного числа произведений, сомножителями в которых являются различных наборов линий связи сети.

3. Только один член этой суммы не содержит в качестве сомножителя и этот член определяет вероятность существования связного дерева.

4. Все остальные члены содержат один или несколько сомножителей вида , по крайней мере, один из них соответствует линии связи, принадлежащей дереву, о котором шла речь в

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

Последовательно для каждого дерева решается задача оптимального выделения одного резервного канала. После решения вычисляется для сети. Окончательно канал выделяется той линии связи, в (которой он был выделен на эташе, давшем максимальное значение

Алгоритм, реализующий изложенный метод, включает следующую последовательность шагов.

Шаг 1. При Вычислить

Шаг 2. Выбрать остовное связное дерево из множества деревьев сети.

Шаг 3. Присвоить начальные значения числа каналов в линиях связи:

Шаг 4. Решить задачу оптимизации надежности дерева

Шаг 5. Вычислить надежность линий связи и сети Если то

Шаг 6. Вывести рассмотренное дерево из множества деревьев сети. Если множество деревьев сети пусто, то перейти к шагу 2, иначе значения «соответствуют оптимальному решению.

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

Алгоритм включает следующую последовательность шагов.

Шаг 1. Для всех линий связи, принадлежащих дереву, вычислить относительные затраты

Максимум в знаменателе берется по всем линиям связи дерева.

Шаг 2. Вычислить относительную эффективность выделения ресурса линиям связи

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

Шаг 4. Проверить ограничение. При этом:

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

если ограничение выполнено точно, то полученные значения оптимальны решение окончено;

если ограничение не выполнено и не нарушено, то переход к шагу 1.

Точность изложенного метода возрастает с увеличением размеров сети, однако в данном случае трудно осуществить перебор деревьев. Последнего можно избежать, если использовать метод Монте-Карло.

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

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

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

В простейшем случае линия связи (Моделируется одноканальной системой обслуживания, а ограничение вводится по среднему времени задержки Тогда после подстановки в (3.8) ограничение будет иметь следующий вид:

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

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

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

Шаг 0. Ввод исходных данных: — единица затрат; — ограничение по среднему времени задержки; — функции затрат.

Присвоить начальные значения переменным:

значение мощности, выбранное без учета надежности;

значение интенсивности потока отказов для исходного варианта;

значение среднего времени восстановления для исходного варианта.

Шаг 1. а) Определить среднее время задержки при выделении единицы затрат на повышение мощности линии связи:

вычислить затраты на повышение мощности наптп значение как решение уравнения вычислить при

б) Определить среднее время задержки при выделении единицы затрат на сокращение

вычислить затраты на сокращение найти значение как решение уравнения вычислить

в) Определить среднее время задержки при выделении единицы затрат на сокращение

вычислить затраты на сокращение

найти значение как решение уравнения вычислить при

шаг 2.

Шаг 3. Определить направление внесения очередной единицы затрат, если:

Шаг 4. Проверить ограничение. Если то перейти к шагу 5, иначе перейти к шагу 1.

Шаг 5. Вывод значений

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

Учитывая, что, как правило, размерность задачи невелика, решение можно получить без применения ЭВМ. При этом функции затрат предварительно целесообразно представить графически.