Reliability Analysis Algorithm for Multi-State Two Separate Minimal Paths Based on Multi-Valued Decision Diagram

本文中，网络边上存在3种属性：容量、时延和成本。容量表示单位时间内边上通过的最大数据量；时延表示数据在边上传输花费的固定时间；成本表示数据在边上传输需要的费用。综上，SFN模型可以形式化为G=(N, E, M, L, B)，其中：

1) N表示网络节点的集合，用节点s表示源点，t表示目标节点；

2) E={e_i|1≤i≤n}表示网络边的集合；

3) M= (M₁, M₂, …, M_n)，表示边的状态集，M_i= {0, 1, …, m_i}表示边e_i所有互斥的状态集，0表示完全失效，m_i表示完全工作；

4) L=(l₁, l₂, …, l_n)，l_i表示边e_i的传输时延；

5) B=(b₁, b₂, …, b_n)，b_i表示边e_i的传输成本。

本文分析过程基于如下假设^{[11, 15]}：

1) 节点完全可靠；2)每条边上的容量状态相互独立，并以一定概率随机分布；3)数据通过2SMPs传输；4)网络G遵循流量守恒定律。

MDD是一种基于香农分解用于表示和操作多值逻辑函数的有向无环图^[16]。文献[17]的结论表明，在多态网络的可靠性分析中，MDD比OBDD具有较少的变量和较高的效率。在MDD中，用圆圈表示非终节点，代表结构函数的一个变量；方框表示终节点，代表多状态系统的状态，系统有多少个可能的状态，对应的MDD就存在多少个终节点；单向箭线表示非终节点的外向分支，每个非终节点有多少种状态就存在多少条外向分支。假设网络中某条边存在m个可能的状态，则MDD终节点从左到右依次表示为最劣状态到最优状态。MDD能够表示组件与系统状态之间的关系，便于计算系统部分或整体处于某种状态的概率。

图 1给出了网络中某条边的MDD结构，可以观察到边e_i存在m+1条外向分支，代表了该边存在的m+1个独立状态，分别用0, 1, …, m_i表示。其中，终节点0表示该边完全失效，m_i表示该边处于最优状态。

根据MDD变量排序，按照顺序将路径中每条边转换为决策图的多值变量X_i，该路径中各边的MDD结构同图 1。

定义1  假设A和B分别代表了两个子MDD的逻辑表达式，并且A和B的逻辑表达式均为case格式：A=case(x, A₀, …, A_m-1)和B=case(x, B₀, …, B_m-1)。通过定义相应MDD操作算子可以得到连接A和B两个子MDD的结构，按照相同规则递归所有的边或路径则可以得到相应路径或系统的MDD结构，为：

MDD中根节点到达某个终节点的所有路径概率之和表示系统处于该种状态的概率。为了降低MDD概率计算复杂度，使用布尔操作进一步简化MDD结构(根节点到达某个终节点满足需求条件时，将终节点的值由实数类型置为布尔类型)。根据MDD性质，计算系统处于非失效状态下的概率时，从MDD根节点出发，寻找终节点非0的路径，递归调用概率计算函数即可。

定义2  多状态系统G处于非失效状态下的概率P(G)通过递归调用概率计算函数，自顶向下遍历MDD结构得出，有：

式中，${P_{{y_i} = j}}$表示标识变量为y_i的边处于状态j时的概率。终节点取值为0时，P(G)=0；终节点取值大于0时，P(G)=1。P(G)表示系统处于非失效状态下的概率，对应可靠性的值。

本文中，网络通过2SMPs传输的可靠性定义为：系统G在时间T和预算B约束条件下通过2SMPs从源点s到目标节点t传输d单位数据的概率。不失一般性，假设路径P₁={e₁, e₂, …, e_v}和P₂={e_v+1, e_v+2, …, e_u}为系统给定的2SMPs，d₁和d₂分别表示路径P₁和P₂传输的单位数据量并且满足d=d₁+d₂。相应的，路径P₁和P₂的传输时间和传输成本分别表示为LP₁=le₁+le₂+…+le_v，LP₂=le_v+1+le_v+2+…+le_u以及CP₁=Ce₁+Ce₂+…+Ce_v，CP₂=Ce_v+1+Ce_v+2+…+Ce_u。

定义3  任意一条路径P_e，其单位时间内传输的数据为${\text{mi}}{{\text{n}}_{{e_i} \in {P_e}}}{w_i}$，则路径P_e的传输能力$\bar d$表示为：

推论1  P_e在时间和预算约束下传输的最大数据量表达式，且A和B的逻辑表达式均为case格式：KP_e，表示P_e在时间约束T下数据传输能力$\bar d$、预算约束B下数据传输能力d_B和指定传输单位数据量d中的最小值。

假设P_i和P_j分别为网络传输给定单位数据时预先给定的两条工作路径，备用路径定义为：工作路径P_i或P_j出现失效情况时，用来替换失效工作路径P_i或P_j后完成数据传输可靠性最高的路径。

根据文献[15]定义的传输规则，备用路径会在第一条工作路径失效后立即触发，其可靠性P_r(P_iP_j, P_k)(i, j, k=1, 2, …, n, i≠j≠k)计算为：

同理，第二条工作路径失效后的可靠性P_r(P_iP_j, P_kP_kk)(i, j, k, kk=1, 2, …, m, i≠j≠k≠kk)计算为：

式中，P_r$(\overline {{P_w}} )$(w=1, 2, …, m)表示路径处于完全失效状态。根据定义可知，路径处于完全失效状态表示路径中至少存在一条边出现失效情况，有：

定义4  网络中任意一条路径P_e，其传输d_e单位数据的预算F(d_e, P_e)等于路径传输代价与传输单位数据量的乘积。

推论2  已知P₁和P₂分别表示网络中传输d单位数据的两条工作路径。如果CP₁=CP₂，则路径P₁和P₂传输d单位数据的预算为固定值；如果CP₁ < CP₂，则路径P₁和P₂传输d单位数据的预算随着路径P₁传输数据的增加而逐渐减小。

证明：  当CP₁=CP₂时，预算F(d)=CP₁d₁+CP₂(d-d₁)=CP₁d；当CP₁ < CP₂时，预算F(d)=CP₁d₁+CP₂(d-d₁)。假设存在一个任意小的正整数θ使得路径P₁传输的单位数据为d₁+θ，则路径P₂传输的单位数据为d-d₁-θ，使得预算满足F_θ(d)≥F(d)，而F_θ(d)=CP₁(d₁+ θ)+CP₂(d-d₁θ)=F(d)-(CP₂-CP₁)θ，根据CP₁ < CP₂可知，(CP₂-CP₁)θ＞0，推出F_θ(d)＜F(d)，故假设不成立。

推论2说明网络通过2SMPs传输d单位数据的预算情况。

利用MDD能够双向反映组件状态与系统状态关系的特点，给出算法MDD_2SMPs计算2SMPs传输的可靠性以及算法MDD_BMPs选择网络备用路径。

算法MDD_2SMPs以网络的2SMPs作为算法输入，输出结果表示网络满足传输需求的概率，对应可靠性的值。该算法主要由4个步骤构成：1)判断2SMPs是否满足传输需求并计算传输成本CP₁和CP₂；2)通过定义的And_Min操作，按照式(1)中的合成规则得到2SMPs的MDD结构(MDD_P₁和MDD_P₂)；3)根据MDD结构中终节点值有序表示的路径容量进行相应约束剪枝，通过执行定义的Or_MDD操作合并MDD_P₁和MDD_P₂得到结构MDD_result；4)遍历MDD_result中终节点非0的路径，递归调用概率计算函数得到随机流网络(d, T, B, P₁, P₂)的可靠性REL_(d, T, B, P₁, P₂)。算法伪代码如下：

Input: A stochastic-flow network (d, T, B, P₁, P₂) with two separate minimal paths, demand level d, time limitation T, and budget constraint B.

Output: The reliability of (d, T, B, P₁, P₂), that is REL_(d, T, B, P₁, P₂)

Step0 Initialization MDD_P₁=0, MDD_P₂=0, MDD_result=0, reliability=0

Step1 for j=1, 2, Compute KP_j(M), CP_j. Sort the two given SMPs in an ascending order

Step2 if KP₁^*CP₁+(d-KP₁)^*CP₂ ≤B

  Construct MDD_P₁, MDD_P₂

  MDD_P₁←MDD_MPSet[1][1]

  MDD_P₂←MDD_MPSet[2][1]

  LP₁←0, LP₂←0

  for i←2 to length[MPSet[1]], length[MPSet [2]] do

    LP₁←LP₁+l_i, LP₂←LP₂+l_i

    MDD_P₁←And_Min(MDD_P₁, MDD_e_i)

    MDD_P₂←And_Min(MDD_P₂, MDD_e_i)

  end for

Step3 Get MDD_result

    MDD_result←Or_MDD(MDD_P₁, MDD_P₂)

Step4 Compute Reliability (MDD_result)

    if (MDD_result =0) then

      return 0

    else if (MDD_result is terminal node) then

      if (MDD_result =1) then

        return 1

      else return 0

    else (MDD_result is not terminal node)

        for j←0 to m_i do

        reliability←reliability+p_j^*Compute Reliability(MDD_result)

        end for

          REL_(d, T, B, P₁, P₂) ←reliability

        return REL_(d, T, B, P₁, P₂)

end if

else return “over budget”

算法MDD_BMPs以网络的MPs作为算法输入，输出结果为选择的备用路径。算法相关背景工作同文献[11, 15]，假设网络中MPs={P₁, P₂, …, P_n}已知。在得到网络中各路径以不同容量传输的单位数据信息后，该算法主要由3个步骤构成：1)执行定义的And_Min操作，按照式(1)中的合成规则得到网络各路径的决策图多值变量形式MDD_P_i；2)遍历MPs中所有与工作路径都不相交的路径，计算概率值；3)选择概率值最高的路径作为网络备用路径。算法伪代码表示如下：

Input: A stochastic flow network with all the minimal paths, demand level d, time limitation T, and budget constraint B.

Output: The optimal minimal path

Step0 Initialization MDD_P=0, reliability=0, MDD_result1=0, MDD_result2=0, S=0

Step1 Construct MDD_P_i, for i=1, 2, 3, …, n

    MDD_P_i←MDD_MPSet[i]

    end of for

Step2 Compute reliability

    for j←3 to n do

    MDD_result1←Or_MDD(MDD_P₁, MDD_P_j)

    MDD_result2←Or_MDD(MDD_P₂, MDD_P_j)

    end for

    use (5) to get reliability

Step3 Return optimal minimal path

    reliability=Rel_(d, T, B, (P₃))

    if Rel_(d, T, B, (P_j)) > probability then let Rel_(d, T, B, (P_j))=probability, and S=P_j

    return S

对于任意一个存在2SMPs的随机流网络，算法MDD_2SMPs的时间复杂度分析过程如下：1)确定KP₁和KP₂花费的时间最多为O(n)，因为每条路径所含边的数量不会超过n条。2)假设m表示路径边上存在的最大状态数，则生成MDD_e_i的耗时最多为O(m)；已知MDD执行逻辑与和逻辑或操作的耗时为O(n₁n₂)(n₁和n₂分别表示参与操作的两个MDD的节点数)，得到构建MDD_P_i和MDD_P_j过程的耗时为O(nm)。3)对路径容量进行约束剪枝耗时为O(nR₁R₂) (R₁和R₂分别表示参与操作的两个MDD的终节点数量)，因为MDD_P_i和MDD_P_j终节点表示的路径容量是唯一有序的，故只需访问对应的终节点值；在工作路径合并过程中，定义的Or_MDD操作同样是一种逻辑或操作，该过程耗时为O(n₁n₂)。4)文献[6]定理1关于MDD概率计算的复杂度分析过程可知，遍历MDD_result计算可靠性的耗时为O(mⁿ/n)。综合以上分析，算法MDD_2SMPs复杂度可以表示为O(n²+nC+mⁿ)。

本节以文献[11, 15]使用的基准网络为例，说明可靠性分析算法MDD_2SMPs和备用路径选择算法MDD_BMPs具体执行过程。网络拓扑结构如图 2所示，图中s表示源点，t表示目标节点，a₁~a₂₂表示有22条边，各边的详细信息在表 1给出。实例中，网络额定传输的单位数据d为200 Gb，时间T不超过13 s，预算B不高于2000元。网络MPs已知条件下，假设工作路径分别由P₁={a₁, a₂, a₃}和P₂={a₄, a₅, a₆}组成，网络中与工作路径P₁和P₂都不相交的路径为：P₃={a₈, a₉, a₁₀}、P₄={a₁₁, a₁₂, a₁₃}、P₅={a₁₅, a₁₆, a₁₇}、P₆={a₁₈, a₁₉, a₂₀}、P₇={a₁₀, a₁₁, a₁₄}、P₈={a₁₅, a₂₂}、P₉={a₁₈, a₂₁, a₂₂}及P₁₀={a₁₆, a₁₇, a₁₈, a₂₁}。

通过前文条件及表 1信息，计算KP₁=200、KP₂=120、CP₁=10、CP₂=7。

1) 按照传输规则，路径(P₁, P₂)满足传输条件；已知CP₂ < CP₁，确定参照路径P₂。

2) 根据给出的变量顺序，将路径(P₁, P₂)中每条边转换为图 1所示的决策图多值变量形式，并按照公式(1)中的合成规则，执行定义的And_Min操作，分别得到图 3所示路径P₁的MDD结构MDD_P₁和图 4所示路径P₂的MDD结构MDD_P₂。

3) 利用MDD_P₁和MDD_P₂结构中终节点值有序表示的路径容量进行约束剪枝，执行Or_MDD操作合并路径(P₁, P₂)。

① 已知步骤1)选取的参照路径为P₂，观察其终节点值从左至右依次为0、10、20、30、40，对应路径P₂的5种容量情况。终节点值为0表示路径P₂完全失效，按照传输规则，计算P₁满足传输条件的路径容量为40；并根据推论2可知预算取得最大值，终止预算判断过程。

② 路径P₂容量为10时，其传输的单位数据最多不超过30 Gb，按照传输规则，计算P₁满足传输条件的路径容量至少为30。

同理，可以分别得到路径P₂容量为20、30和40时，P₁上满足传输条件的路径容量。

③ 根据MDD原理及运算规则，规约化简得到图 5所示的结构。

4) 自顶向下遍历生成的结构MDD_result，递归调用Compute Reliability函数，计算网络可靠性值为REL_(200, 13, 2000, P₁, P₂)=0.700 624。

针对该网络，表 2给出了算法MDD_2SMPs与算法(d, T, B, (P_i, P_j))-LBPs计算2SMPs可靠性时，获取(d, T, B)下路径所需容量的操作数情况。以工作路径P₁={a₁, a₂, a₃}和P₂={a₄, a₅, a₆}为例，本文算法通过定义And_Min操作算子，直接得到唯一且有序的路径容量，只需根据MDD中终节点的值进行约束剪枝，并且只需存储工作路径所含边的信息(6条)。因此，算法MDD_2SMPs获取(d, T, B)下工作路径所需容量的操作数为6×5×5=150次。而文献[15]中算法(d, T, B, (P_i, P_j))-LBPs根据路径P₁和P₂存在的流量分配情况计算，通常会得到相同的路径容量，如路径(P₁, P₂)通过的流量为(80, 120)、(90, 110)或(100, 100)时，得到的路径容量均为(20, 40)。为便于计算可靠性的值，还需构建系统状态空间向量(即文献[15]中X向量)过滤重复的以及非最小的解，这些系统状态空间向量存储了整个网络的边(22条)，合计需要22×13+22×(13×12)=3 718次移除操作。对于网络可靠性概率值，本文算法基于节点概率迭代计算；算法(d, T, B, (P_i, P_j))-LBPs获取系统最小容量向量后，还需借助容斥原理等方法进行计算。

利用MDD能够双向反映组件状态与系统状态的特点，算法MDD_BMPs通过将表 3中各路径传输的单位数据转换为相应的多状态变量，大大简化了计算的复杂性，具体过程如下。

1) 根据表 3信息构建各路径的决策图多值变量形式MDD_P_i。

2) 遍历MPs中与路径(P₁, P₂)都不相交的路径(P₃, P₄, P₅, P₆, P₇, P₈, P₉和P₁₀)，计算可靠性值。

① 以路径P₃为例，由步骤1)得到图 6所示的决策图多值变量形式MDD_P₃。

② 计算CP₁=10、CP₂=7、CP₃=9，确定路径(P₁, P₃)和(P₂, P₃)变量序分别为P₃ < P₁和P₂ < P₃。

③ 由得到的变量序选取参照路径，运用推论2获取对应路径的终节点状态。

④ 最后，根据MDD概率计算函数及式(5)定义的传输规则，计算备用路径为P₃时的可靠性值P_r(P₁P₂, P₃)=0.183 823 96。

3) 根据各路径取值情况返回可靠性最高的路径。

图 7为第一条工作路径失效后，各路径的可靠性取值情况，由此选择备用路径为P₄，可靠性值P_r(P₁P₂, P₄)=0.227 665。

同理，第二条工作路径失效后，根据图 8选择备用路径为P₅，可靠性值P_r(P₁P₂, (P₄P₅))=0.068 328。

对于图 2所示网络，算法MDD_BMPs的计算结果与文献[15]算法(d, T, B, (P_k))-LBPs的计算结果一致。不同的是，算法MDD_BMPs通过将网络各路径转换为决策图多值变量形式，大大降低了计算的复杂性。以路径P₃执行过程为例，算法MDD_BMPs判断路径(P₁, P₃)和(P₂, P₃)终节点状态需要的操作数为50+50=100次；算法(d, T, B, (P_k))-LBPs则将路径(P₁, P₂)分别与路径P₃组合获取系统最小容量向量，该过程所需操作数为6 358+3 718=10 076次。

2SMPs传输的随机流网络可靠性分析，通常是求取系统最小容量向量，运用容斥原理计算可靠性值。本文根据MDD能够双向反映组件状态与系统状态关系的特点，提出算法MDD_2SMPs，实例结果表明，相比获取系统最小容量向量方法，本文算法主要有以下特点：1)通过定义MDD操作算子，得到路径容量是唯一有序的，减少了路径容量的约束判断；2)在系统结构不变情况下，可用于不同参数的可靠性分析，避免了存储整个网络的边以及运用容斥原理计算的繁琐。此外，针对网络工作路径失效的问题，算法MDD_BMPs通过将网络各路径转换为决策图多值变量形式，大大降低了选择可靠备用路径的计算复杂性。