4.2. Описание алгоритма синтеза структуры сети

                Общий алгоритм синтеза структуры РВС задачи (4.1)-(4.3) включает такие этапы [22,29].

1. Синтез кратчайшего связывающего дерева (КСД) Д0 с корнем в узле Х0.

2. Синтез начальной многосвязной структуры Е0 и её  оптимизация по критерию минимума С_S при ограничении (4.2) на вероятность своевременной доставки.

3. Оптимизация структуры РВС по критерию минимума С_S  при ограничениях на показатель живучести сети.

Рассмотрим детальнее алгоритмы каждого из этапов.

Этап 1.  Синтез КСД.                                       

Находим корень сети узел Хi, такой что H_i=  

         Дальше синтезируем сеть древовидной структуры (КСД) с корнем в узле Хi  при ограничении на Т_ср. Для этого используем модифицированный алгоритм Исау-Вильямса, описанный в [79]. В результате получим начальную структуру Д0.

Этап 2. Синтез многосвязной структуры Е и её оптимизация при вероятностно-временных ограничениях. Алгоритм синтеза структуры сети при ограничениях на вероятность своевременной доставки (А2) включает начальный этап, и множество однотипных итераций (основной этап).

Перед началом (k+1)-й итерации создаём подмножество каналов, которые могут быть удалены без нарушения условий связности P_уд⁰(k), а также подмножество каналов {(i,j)}; которые надо рассматривать как претенденты на введение в сеть структуры  E_k  P_вв(k). Обозначим подмножества ещё не рассмотренных каналов из множеств P_уд(k) и P_вв(k) через  P_уд^ост(k) и  P_вв^ост(k). Приравниваем  P_уд^ост(0)= P_уд(k) ; P_вв^ост(0)=P_вв(k).

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

Ш1. Находим конечные вершины дерева Д0 и проводим через них цикл минимальной длины (стоимости), для этого используем соответствующий алгоритм решения задачи коммивояжера [16]. Полученная структура будет удовлетворять заданному ограничению на связность   k_св>=2. Обозначим её через Е0.

Ш2. Применим к структуре Е0 задачу ВПС и найдем такие ПС всех КС {d_rs⁰} (E0 и распределение потоков в каналах {f_rs⁰}, при которых

С_S ({d_rs⁰}) =min                                                                                                  (4.6)

при условии P_СД({f_rs},{d_rs})>=P_зад                                                     (4.7)

где d_{rs Î}D; и  f_rs<d_rs,    (r,s) ÎE .

Приравниваем С_S ({d_rs⁰})=С_S (0)  и переходим к первой итерации основного этапа.

Основной этап.

На каждой итерации данного этапа проводится оптимизация данной структуры Ек путём удаления неэкономичных каналов связи и введения новых (вариант метода замены каналов).

(k+1)-я итерация:

Пусть проведено k итераций в ходе которых построена сеть структуры Ек, найдены ПС всех КС (r,s) {d_rs(k)}, и распределение потоков{f_rs(k)⁰}. Обозначим соответствующее значение критерия через С_S(k)=C_S({d_rs(k)}).

Опишем (k+1)-ю итерацию.

Ш1. Выбираем наименее экономичный канал (r,s), который можно вывести при сохранении условия связности  k_св>=k_зад. В качестве критерия выбора КС для удаления используется следующий показатель неэффективности:

                  ^g_rs⁽⁰⁾=C_rs(l_rs)(d_rs-f_rs)/d_rs                        (4.8)

где C_rs(l_rs)-стоимость КС (r,s);

(d_rs-f_rs)/d_rs=1-r_rs-коэффициент простоя КС (r,s).

Ш2. Определяем такой КС (r₁,s₁), для которого g_r1s1⁽⁰⁾ =max g_rs⁽⁰⁾ и

                                                                                               ^(r,s)

выводим его из структуры Е_к. При этом проверяется, сохраняется ли условие k_св>=k_зад.

Ш3.Определяем показатель экономичности для введения новых каналов связи в сеть   G_ij⁽¹⁾.

          G_ij⁽¹⁾=(h_ij+h_ji)DE_ij=(h_ij+h_ji)[C(p_ij^(k))-C_ij(l_ij)]          (4.9)

где C(p_ij^(k))= S C_rs(d_rs^(k))h_ij/f_rs-стоимость передачи требования h_ij по

                     ^(r,s)Îpij

используемому пути п_ij  в сети Ек.

Находим тот канал(i*,j*)ÎEk, для которого  G_i*j*⁽¹⁾=maxG_ij⁽¹⁾|_Gij(1)>0.                                                                                                                                                                                                                    ^(i,j)          

Ш4. Вводим в структуру Ек\(r₁,s₁) канал (i*,j*). Обозначим полученную структуру Ек⁽¹⁾= Ек\(r₁,s₁)È(i*,j*). Решаем для структуры  Ек⁽¹⁾ задачу ВПС РП и находим   такое   новое   распределение  ПС  {d_rs^(н)}  и  потоков  {f_rs^(н)}, что                 C_S (d_rs^(н)(k))=min. .

Ш5. Сравниваем C_S^(н) (d_rs^(н)(k))<C_S (k),если да, то приравниваем Е_k+1 =Ек; d_rs(k+1)= d_rs^(н)(k); f_rs(k+1)= f_rs^(н)(k), для всех (r,s), и конец (k+1)-й итерации. Приравниваем k=k+1 и переходим к следующей итерации; иначе на Ш6.

Ш6. Обозначим через P_уд^ост(k) и  P_вв^ост(k) -множество ещё не рассмотренных каналов на данном шаге итерации k.

Ш6.1.Приравниваем P_вв^ост(1)=P_вв^ост(0)\(i*,j*).

Ш6.2. Проверка условия, все ли возможные для введения каналы просмотрены: P_вв^ост(1)= ? Если да, то на Ш6.3. Иначе на Ш3.

Ш6.3. Приравниваем P_уд^ост(k)=P_уд(k)\ (r1,s1). Проверяем условие, все ли возможные для выведения каналы просмотрены: P_уд^ост(k)=0. Если да, то конец. Иначе, на Ш1, и анализ оставшихся каналов P_уд^ост(k).

Таким образом, в результате выполнения этапа 2 мы получим оптимальную структуру Ек, которая обеспечивает решение задачи (4.6),(4.7).

Этап 3.  Оптимизация структуры сети при ограничениях на показатели живучести.

Постановка задачи.

Итак, пусть имеем структуру E_k={(r,s)} РВС, в которой найдены ПС всех КС {d_rs^(o)}   и распределение потоков в каналах [f_rs^(o)], при которых С_S({d_rs⁰})=min,

при условиях T_ср <= t_зад и/или P_СД=P{T_ср <= t_зад} >= P_зад. Обозначим H_S⁰=  h_ij - суммарный поток, передаваемый через сеть при условии, что все узлы сети и КС безотказны. Вероятность этого состояния обозначим через P_o   .

Необходимо найти такие резервные КС (i,j) ((i,j)ÎЕ_к), их ПС {d_ij⁰} при которых

                  С_S ({d_ij})=SС_ji ({d_ij})=min                 (4.10)

                                  ^(i,j)ÎЕк

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

                                                               P{H_SФ =H_S⁰}>=P₀                    (4.11.1)

                           P{H_{S Ф} =90%H_S⁰}>=P_1зад             (4.11.2)

                           P{H_S>=80%H_S⁰}>=P_2зад           (4.11.3)

                           P{H_S>=70%H_S⁰}>=P_3зад           (4.11.4)

                           P{H_S>=60%H_S⁰}>=P_4зад           (4.11.5)

                           P{H_S>=50%H_S⁰}>=P_5зад           (4.11.6)

и при этом обеспечивается ограничение на Тср. T_ср <= t_зад

Алгоритм решения этапа 3 (А3) [29].

1.Рассмотрим единичные отказы всех КС (r,s)ÎЕ_к .Обозначим z_i-состояние, когда отказал КС (r_i,s_i).Определим вероятность этого состояния                                                                                                        P(z_i)=(1-k_ri,si) _П k_гrs

                                      ^{(r,s)ОЕкИ(r,s)©(ri,si)}

2.Вычисляем максимальный передаваемый поток в сети в состоянии z_i-H_S(z_i) ; для этого используем  описанный в главе 2 алгоритм.

3. Проранжируем величины H_S(z_i)  в порядке уменьшения. Перенумеруем z_i так, что H(z₁)>=H(z₂)>=...>=H(z_i)>=H(z_i+1)>=...>= H(z_n)

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

 (4.12)      

В результате получим начальный показатель живучести сети как величину ОПС при отказах.

 P(H_SФ>=A_kH_Sзад)⁼P_k(0) где k=1,2,3,4,5;   A_0=100%;A_1=90%;A_2=80%;A_3=70%;A_4=60%;A_5=50%;

Необходимо заметить, что в силу выражения (4.12) увеличение надёжности любого из КС автоматически увеличивает показатели живучести для всех k=1..5.

Очевидно, необходимо найти такие КС, увеличение надёжности которых наиболее эффективно.

Разобьем множество отказовых состояний сети Z={z_i} на подмножества Z_k k=1..5, такие,что  z_jÎZ_k, если H(zi)< A_kH_S⁰=H_зад^(k), где k=1..5.

При этом  Z1 > Z2 > Z3 > Z4 > Z5.

Очевидно, уменьшение вероятностей состояний P(z_j) z_jÎZ_k, т.е. повышение надёжности соответствующих КС, повысит также живучесть сети в целом.

Пусть, как и выше, z_j состояние, когда отказал КС (r_i,s_i).

С учётом выражения (4.12) будем рассматривать отказовые состояния из подмножества Z₅ ; так как, если  z_jÎZ₅, то одновременно z_jÎZ_k, k=1..4.

Увеличение надёжности КС (r,s)  будем обеспечивать путём введения резервных каналов.

В качестве показателя эффективности введенного резервного канала для ЛС  (r_i,s_i) используем величину a_risi=-DP(z_j)/DC(r_j,s_j)    (4.13)

где   DP(z_j)=DP(r_j,s_j)-уменьшение (изменение)вероятности состояния z_j при введении резервного КС в ЛС (r_j,s_j);

DC(r_j,s_j)=C_rj,sj(d_rj,sj) стоимость введения такого резерва.

При этом:

                                                    _{nj+1                          nj}

                   DP(z_j)=(1-k_гrj,sj)    _П k_гrs-(1-k_гrj,sj)   _П k_гrs=

                                                     ^{(r,s)¹(rj,sj)                 (r,s)}

                                                   _nj

                      =-k_гrj,sj(1-k_гrj,sj)    _П k_гrs=-kгrj,sjP(z_j)             (4.14)

                                                 ^{(r,s)¹(rj,sj)}

Таким образом:

                     a_risi=k_гrj,sjP(z_j)/C_rj,sj(d_rj,sj)                           (4.15)

где  n_j-число параллельных каналов в КС (r_j,s_j).

Дадим формальное описание алгоритма.

Ш1.Рассмотрим отказовые состояния из подмножества Z₅ и вычислим показатель a_risi=k_гrj,sjP(z_j)/C_rj,sj(d_rj,sj,l_rj,sj)     (r_j,s_j)ÎZ₅

Ш2. Выбираем такой КС (r*,s*)ÎZ₅, для которого a_r*s*=maxa_rksk

                                                                                             ^(rk,sk)ÎZ5

Ш3. Вводим резервный канал в КС (r*,s*), пересчитываем потоки и показатели живучести. При этом увеличение значения показателя живучести DP_k будет определяться уменьшением вероятности состояния z*:

DP(z*)=-k_гr*,s*P(z*)

Поэтому P_k(1)=P_k(0)+|DP(z*)|,       k=1,..,5.

Ш4. Проверяем условие: P_k(1)>=P_kзад   k=1,..,5.

Если да,  то конец, иначе переходим к следующей итерации. Все следующие итерации проводятся аналогично, при этом в первую очередь просматриваются те отказовые состояния z_jÎZ_k, которые не рассматривались (не использовались) на предыдущих итерациях.

Замечание: если на некоторой итерации r, для некоторых k' уже обеспечено условие P_k'(r)>=P_k'зад, k'ÎK₁, а для других k оно не выполняется, т.е. P_k(r)<P_kзад, kÎK₁, то для анализа выбираются состояния из подмножеств Z_k (kÎK₁).