多状态不交化路径可靠性分析的符号算法

李凤英，何志伟，董荣胜

(桂林电子科技大学广西可信软件重点实验室 广西 桂林 541004)

随着网络技术的不断发展，网络已融入生活的各个方面，如运输网络、移动自组网络、计算机和通信网络等[1-3]。对于上述网络系统，常借助于随机流网络(stochastic-flow network, SFN)进行刻画描述，有关随机流网络的理论和应用研究越来越受到人们关注。其中对于随机流网络的可靠性，既可通过蒙特卡洛方法[4]计算网络可靠性的近似值，也可通过空间分解[5]、多值决策图[6]、最小割集[7]或最小路集[8]等方法计算网络可靠性的精确值。在最小路集基础上，文献[8]对单条路径传输的网络可靠性进行了分析。为了缩短流量传输时间，文献[9]将随机流网络流量从单路径传输扩展到两条及多条不交化路径(separate minimalpaths, SMPs)传输的情况，并提出选择一组可靠性最高的路径作为网络备用路径，来保障工作路径失效后网络的顺利传输。在2SMPs传输流量前提下，文献[10-12]加入预算约束条件，基于最小路集的方法求解了随机流网络可靠性。文献[13-14]定义了错误率和时间约束的多状态网络可靠性，并考虑到工作路径失效后启用备用路径来保障网络传输，提出基于路集的方法对状态空间过滤获取系统最小容量向量，运用容斥原理求解随机流网络可靠性。文献[15]则认为路径还有可能一条一条地失效，通过枚举单路径失效情况，证实了单条备用路径可以提高网络传输可靠性。

对于一个包含2SMPs的复杂网络系统，一方面获取系统最小容量向量计算网络可靠性需要存储整个网络的边，并且包含了许多冗余路径容量组合，寻找一种更加有效的方式对于该类问题求解有着实际的意义；另一方面，通过枚举网络各路径最小容量向量的方式计算备用路径可靠性，运算量非常庞大，故需要一种简洁的解决方法选择网络可靠的备用路径。为此，本文首先针对算法(d, T, B, (Pi,Pj))-LBPs[15]计算2SMPs可靠性需要存储整个网络的边以及存在冗余路径容量的问题，提出基于多值决策图(multi-valued decision diagram, MDD)的可靠性分析算法MDD_2SMPs。该算法利用MDD能够双向反映组件状态与系统状态关系的特点，通过自定义MDD操作算子，实现状态空间、变量组合的隐式表示和搜索，减少路径不相关边的存储；并在组合过程中引入约束剪枝策略过滤许多不必要的路径，从而提高算法效率；同时给出了基于MDD的概率计算模型，使得可靠性计算更加直观。其次，针对工作路径失效后选择网络可靠备用路径的问题，提出算法MDD_BMPs，该算法通过将网络各路径转换为决策图多值变量形式，降低了计算的复杂性。最后，通过基准网络实例，验证了本文所提方法的正确性和有效性。

1 模型描述与假设

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

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

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

3) M= (M1,M2,…,Mn)，表示边的状态集，Mi={0,1,…,mi}表示边ei所有互斥的状态集，0表示完全失效，mi表示完全工作；

4) L=(l1, l2,…,ln)，li表示边ei的传输时延；

5) B=(b1, b2,…,bn)，bi表示边ei的传输成本。

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

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

2 方法与问题定义

2.1 多值决策图(MDD)

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

图1 边ei的MDD结构

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

2.2 逻辑操作

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

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

2.3 可靠性概率计算

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

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

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

2.4 问题定义

本文中，网络通过2SMPs传输的可靠性定义为：系统G在时间T和预算B约束条件下通过2SMPs从源点s到目标节点t传输d单位数据的概率。不失一般性，假设路径P1={e1, e2,…,ev}和P2={ev+1,ev+2,…,eu}为系统给定的2SMPs，d1和d2分别表示路径P1和P2传输的单位数据量并且满足d=d1+d2。相应的，路径P1和P2的传输时间和传输成本分别表示为LP1=le1+le2+…+lev，LP2=lev+1+lev+2+…+leu以及CP1=Ce1+Ce2+…+Cev，CP2=Cev+1+Cev+2+…+Ceu。

定义 3 任意一条路径Pe，其单位时间内传输的数据为minei∈Pewi，则路径Pe的传输能力表示为：

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

2.5 备用路径

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

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

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

2.6 预算判断

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

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

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

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

3 基于MDD的可靠性分析算法

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

3.1 算法MDD_2SMPs

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

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

Output: The reliability of (d, T, B, P1, P2), that is REL_(d, T, B, P1, P2)

Step0 Initialization MDD_P1=0, MDD_P2=0,MDD_result=0, reliability=0

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

Step2 if KP1*CP1+(d-KP1)*CP2≤B

Construct MDD_P1, MDD_P2

MDD_P1←MDD_MPSet[1][1]

MDD_P2←MDD_MPSet[2][1]

LP1←0, LP2←0

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

LP1←LP1+li, LP2←LP2+li

MDD_P1←And_Min(MDD_P1, MDD_ei)

MDD_P2←And_Min(MDD_P2, MDD_ei)

end for

Step3 Get MDD_result

MDD_result←Or_MDD(MDD_P1,MDD_P2)

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 mido

reliability←reliability+pj*Compute Reliability(MDD_result)

end for

REL_(d, T, B, P1, P2) ←reliability

return REL_(d, T, B, P1, P2)

end if

else return “over budget”

3.2 算法MDD_BMPs

算法MDD_BMPs以网络的MPs作为算法输入，输出结果为选择的备用路径。算法相关背景工作同文献[11,15]，假设网络中MPs={P1,P2,…,Pn}已知。在得到网络中各路径以不同容量传输的单位数据信息后，该算法主要由3个步骤构成：1) 执行定义的And_Min操作，按照式(1)中的合成规则得到网络各路径的决策图多值变量形式MDD_Pi；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_Pi, for i=1, 2, 3,…, n

MDD_Pi←MDD_MPSet[i]

end of for

Step2 Compute reliability

for j←3 to n do

MDD_result1←Or_MDD(MDD_P1,MDD_Pj)

MDD_result2←Or_MDD(MDD_P2,MDD_Pj)

end for

use (5) to get reliability

Step3 Return optimal minimal path

reliability=Rel_(d, T, B, (P3))

if Rel_(d, T, B, (Pj))＞probability then let Rel_(d, T, B, (Pj))=probability, and S=Pj

return S

3.3 复杂度分析

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

4 实例分析

本节以文献[11,15]使用的基准网络为例，说明可靠性分析算法MDD_2SMPs和备用路径选择算法MDD_BMPs具体执行过程。网络拓扑结构如图2所示，图中s表示源点，t表示目标节点，a1～a22表示有22条边，各边的详细信息在表1给出。实例中，网络额定传输的单位数据d为200 Gb，时间T不超过13 s，预算B不高于2000元。网络MPs已知条件下，假设工作路径分别由P1={a1, a2, a3}和P2={a4, a5, a6}组成，网络中与工作路径P1和P2都不相交的路径为：P3={a8, a9, a10}、P4={a11, a12, a13}、P5={a15, a16, a17}、P6={a18, a19, a20}、P7={a10, a11, a14}、P8={a15, a22}、P9={a18, a21, a22}及P10={a16, a17, a18, a21}。

4.1 可靠性计算

通过前文条件及表1信息，计算KP1=200、KP2=120、CP1=10、CP2=7。

1) 按照传输规则，路径(P1, P2)满足传输条件；已知CP2＜CP1，确定参照路径P2。

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

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

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

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

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

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

图2 基准网络实例

图3 路径P1的MDD结构

图4 路径P2的MDD结构

图5 MDD_result

表1 图2中各边数据信息

(续表)

表2 两种算法获取(d,T,B)下路径所需容量的操作数

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

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

表3 各路径可能传输的单位数据

4.2 备用路径选择

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

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

2) 遍历MPs中与路径(P1,P2)都不相交的路径(P3, P4, P5, P6, P7, P8, P9和P10)，计算可靠性值。

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

② 计算CP1=10、CP2=7、CP3=9，确定路径(P1,P3)和(P2, P3)变量序分别为P3＜P1和P2＜P3。

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

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

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

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

图6 路径P3的MDD结构

同理，第二条工作路径失效后，根据图8选择备用路径为P5，可靠性值Pr(P1P2,(P4P5))=0.068 328。

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

图7 第一条路径失效后各路径的可靠性取值情况

图8 第二条路径失效后各路径的可靠性取值情况

5 结 束 语

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