ISSN 
-
随着网络技术的不断发展，网络已融入生活的各个方面，如运输网络、移动自组网络、计算机和通信网络等[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，该算法通过将网络各路径转换为决策图多值变量形式，降低了计算的复杂性。最后，通过基准网络实例，验证了本文所提方法的正确性和有效性。
-
本文中，网络边上存在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的传输成本。
1) 节点完全可靠；2)每条边上的容量状态相互独立，并以一定概率随机分布；3)数据通过2SMPs传输；4)网络G遵循流量守恒定律。
-
MDD是一种基于香农分解用于表示和操作多值逻辑函数的有向无环图[16]。文献[17]的结论表明，在多态网络的可靠性分析中，MDD比OBDD具有较少的变量和较高的效率。在MDD中，用圆圈表示非终节点，代表结构函数的一个变量；方框表示终节点，代表多状态系统的状态，系统有多少个可能的状态，对应的MDD就存在多少个终节点；单向箭线表示非终节点的外向分支，每个非终节点有多少种状态就存在多少条外向分支。假设网络中某条边存在m个可能的状态，则MDD终节点从左到右依次表示为最劣状态到最优状态。MDD能够表示组件与系统状态之间的关系，便于计算系统部分或整体处于某种状态的概率。
图 1给出了网络中某条边的MDD结构，可以观察到边ei存在m+1条外向分支，代表了该边存在的m+1个独立状态，分别用0, 1, …, mi表示。其中，终节点0表示该边完全失效，mi表示该边处于最优状态。
图 1 边ei的MDD结构
-
根据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结构，为：
$$ A\diamondsuit B = {\text{case}}(x,{A_0}, \cdots ,{A_{m - 1}})\diamondsuit {\text{case}}(x,{B_0}, \cdots ,{B_{m - 1}})\\ = \left\{ \begin{gathered} {\text{case}}(x,{A_0}\diamondsuit {B_0}, \cdots ,{A_{m - 1}}\diamondsuit {B_{m - 1}})\ \ \ \ \ {\text{index}}(x) = {\text{index}}(y) \hfill \\ {\text{case}}(x,{A_0}\diamondsuit B, \cdots ,{A_{m - 1}}\diamondsuit B)\ \ \ \ \ \ \ \ \ \ {\text{index}}(x) < {\text{index}}(y) \hfill \\ {\text{case}}(x,A\diamondsuit {B_0}, \cdots ,A\diamondsuit {B_{m - 1}})\ \ \ \ \ \ \ \ \ \ {\text{index}}(x) > {\text{index}}(y) \hfill \\ \end{gathered} \right. $$ (1) -
MDD中根节点到达某个终节点的所有路径概率之和表示系统处于该种状态的概率。为了降低MDD概率计算复杂度，使用布尔操作进一步简化MDD结构(根节点到达某个终节点满足需求条件时，将终节点的值由实数类型置为布尔类型)。根据MDD性质，计算系统处于非失效状态下的概率时，从MDD根节点出发，寻找终节点非0的路径，递归调用概率计算函数即可。
定义2 多状态系统G处于非失效状态下的概率P(G)通过递归调用概率计算函数，自顶向下遍历MDD结构得出，有：
$$ \begin{gathered} P(G) = \\ {P_{{y_i} = 0}}P({G_{{y_i} = 0}}) + {P_{{y_i} = 1}}P({G_{{y_i} = 1}}) + \cdots + {P_{{y_i} = {m_i}}}P({G_{{y_i} = {m_i}}}) \\ \end{gathered} $$ (2) 式中，${P_{{y_i} = j}}$表示标识变量为yi的边处于状态j时的概率。终节点取值为0时，P(G)=0；终节点取值大于0时，P(G)=1。P(G)表示系统处于非失效状态下的概率，对应可靠性的值。
-
本文中，网络通过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，其单位时间内传输的数据为${\text{mi}}{{\text{n}}_{{e_i} \in {P_e}}}{w_i}$，则路径Pe的传输能力$\bar d$表示为：
$$ \bar d = {\text{mi}}{{\text{n}}_{{e_i} \in {P_e}}}{w_i}(T - {\text{L}}{{\text{P}}_e}) $$ (3) 推论1 Pe在时间和预算约束下传输的最大数据量表达式，且A和B的逻辑表达式均为case格式：KPe，表示Pe在时间约束T下数据传输能力$\bar d$、预算约束B下数据传输能力dB和指定传输单位数据量d中的最小值。
$$ {\text{K}}{{\text{P}}_e} = {\text{min}}(d,{d_B},\overline d ) $$ (4) -
假设Pi和Pj分别为网络传输给定单位数据时预先给定的两条工作路径，备用路径定义为：工作路径Pi或Pj出现失效情况时，用来替换失效工作路径Pi或Pj后完成数据传输可靠性最高的路径。
根据文献[15]定义的传输规则，备用路径会在第一条工作路径失效后立即触发，其可靠性Pr(PiPj, Pk)(i, j, k=1, 2, …, n, i≠j≠k)计算为：
$$ {P_r}({P_i}{P_j},{P_k}) = {P_r}(\overline {{P_i}} ){P_r}(S|{P_j}{P_k}) + {P_r}(\overline {{P_j}} ){P_r}(S|{P_i}{P_k}) $$ (5) 同理，第二条工作路径失效后的可靠性Pr(PiPj, PkPkk)(i, j, k, kk=1, 2, …, m, i≠j≠k≠kk)计算为：
$$ \begin{gathered} {P_r}({P_i}{P_j},({P_k}{P_{kk}})) = \\ 2{P_r}(\overline {{P_i}} ){P_r}(\overline {{P_j}} ){P_r}({P_k}{P_{kk}}) + {P_r}(\overline {{P_k}} ){P_r}({P_i}{P_j},{P_{kk}}) \\ \end{gathered} $$ (6) 式中，Pr$(\overline {{P_w}} )$(w=1, 2, …, m)表示路径处于完全失效状态。根据定义可知，路径处于完全失效状态表示路径中至少存在一条边出现失效情况，有：
$$ {P_r}(\overline {{p_w}} ) = \left( {1 - \prod\limits_{r:e \in {p_w}} {{P_r}} ({e_r} > 0)} \right) $$ (7) -
定义4 网络中任意一条路径Pe，其传输de单位数据的预算F(de, Pe)等于路径传输代价与传输单位数据量的乘积。
$$ F({d_e},{P_e}) = {\text{C}}{{\text{P}}_e}{d_e} $$ (8) 推论2 已知P1和P2分别表示网络中传输d单位数据的两条工作路径。如果CP1=CP2，则路径P1和P2传输d单位数据的预算为固定值；如果CP1 < CP2，则路径P1和P2传输d单位数据的预算随着路径P1传输数据的增加而逐渐减小。
证明： 当CP1=CP2时，预算F(d)=CP1d1+CP2(d-d1)=CP1d；当CP1 < CP2时，预算F(d)=CP1d1+CP2(d-d1)。假设存在一个任意小的正整数θ使得路径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单位数据的预算情况。
-
利用MDD能够双向反映组件状态与系统状态关系的特点，给出算法MDD_2SMPs计算2SMPs传输的可靠性以及算法MDD_BMPs选择网络备用路径。
-
算法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 mi do
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”
-
算法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
-
对于任意一个存在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)。
-
本节以文献[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}。
图 2 基准网络实例
表 1 图2中各边数据信息
边 容量 概率 时延 成本 边 容量 概率 时延 成本 a1 50a 0.85 2 3 a12 60 0.80 2 2 30 0.05 40 0.05 10 0.05 20 0.05 0 0.05 10 0.05 a2 50 0.80 2 4 0 0.05 30 0.10 a13 60 0.75 1 3 10 0.05 40 0.10 0 0.05 20 0.05 a3 40 0.85 3 3 10 0.05 20 0.05 0 0.05 10 0.05 a14 20 0.95 2 2 0 0.05 0 0.05 a4 50 0.85 3 2 a15 70 0.80 3 2 30 0.05 50 0.05 10 0.05 30 0.05 0 0.05 10 0.05 a5 50 0.80 4 3 0 0.05 30 0.10 a16 60 0.75 2 2 10 0.05 40 0.10 0 0.05 30 0.05 a6 40 0.85 3 2 10 0.05 20 0.05 0 0.05 10 0.05 a17 50 0.85 3 3 0 0.05 30 0.05 a7 20 0.90 2 1 10 0.05 0 0.10 0 0.05 a8 50 0.85 3 3 a18 40 0.85 3 4 30 0.05 30 0.05 10 0.05 10 0.05 0 0.05 0 0.05 a9 40 0.85 4 1 a19 50 0.85 3 1 20 0.05 30 0.05 10 0.05 10 0.05 0 0.05 0 0.05 a10 40 0.80 2 2 a20 40 0.85 3 2 20 0.10 20 0.05 10 0.05 10 0.05 0 0.05 0 0.05 a11 50 0.85 3 1 a21 20 0.95 2 2 30 0.05 0 0.05 10 0.05 a22 10 0.95 4 1 0 0.05 0 0.05 注：50a表示边a1容量处于50时的概率为0.85 -
通过前文条件及表 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 路径P1的MDD结构
图 4 路径P2的MDD结构
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所示的结构。
图 5 MDD_result
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获取系统最小容量向量后，还需借助容斥原理等方法进行计算。
表 2 两种算法获取(d, T, B)下路径所需容量的操作数
不相交路径(Pi, Pj) 算法(d, T, B, (Pi, Pj))-LBPs 算法MDD_2SMPs 不相交路径(Pi, Pj) 算法(d, T, B, (Pi, Pj))-LBPs 算法MDD_2SMPs P1, P2 3 718 150 P4, P10 352 126 P3, P4 6 358 150 P5, P6 6 358 150 P3, P5 6 358 150 P5, P7 3 718 90 P3, P6 3 718 150 P5, P9 550 60 P3, P8 550 50 P6, P7 1 782 90 P3, P9 22 60 P6, P8 198 50 P3, P10 198 105 P7, P8 0 0 P4, P5 9 702 180 P7, P9 0 0 P4, P6 6 358 180 P7, P10 0 0 P4, P8 1 078 60 P8, P10 0 0 P4, P9 550 72 -
利用MDD能够双向反映组件状态与系统状态的特点，算法MDD_BMPs通过将表 3中各路径传输的单位数据转换为相应的多状态变量，大大简化了计算的复杂性，具体过程如下。
表 3 各路径可能传输的单位数据
路径 单位容量 最大容量 概率 时延 成本 路径 单位容量 最大容量 概率 时延 成本 40a 200 0.578 50 200 0.541 875 30 180 0.110 5 40 200 0.072 25 P1 20 120 0.040 5 7 10 P5 30 150 0.114 875 8 7 10 60 0.128 375 10 50 0.128 375 0 0 0.142 625 0 0 0.142 625 40 120 0.578 40 160 0.614 125 30 90 0.110 5 30 120 0.047 25 P2 20 60 0.040 5 10 7 P6 20 80 0.067 625 9 7 10 30 0.128 375 10 40 0.128 375 0 0 0.142 625 0 0 0.142 625 40 160 0.578 20 120 0.769 5 30 120 0.034 P7 10 60 0.087 875 7 5 P3 20 80 0.117 9 6 0 0 0.142 625 10 40 0.128 375 P8 10 60 0.902 5 7 3 0 0 0.142 625 0 0 0.097 5 50 200 0.51 P9 10 40 0.857 375 9 7 40 200 0.104 125 0 0 0.142 625 30 200 0.036 125 P10 20 60 0.692 55 P4 20 140 0.078 75 6 6 10 30 0.121 956 25 10 11 10 70 0.128 375 0 0 0.185 493 75 0 0 0.142 625 注：40a表示路径P1容量为40时，在(d, T, B)约束下通过的单位数据为200 Gb 1) 根据表 3信息构建各路径的决策图多值变量形式MDD_Pi。
2) 遍历MPs中与路径(P1, P2)都不相交的路径(P3, P4, P5, P6, P7, P8, P9和P10)，计算可靠性值。
① 以路径P3为例，由步骤1)得到图 6所示的决策图多值变量形式MDD_P3。
图 6 路径P3的MDD结构
② 计算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。
图 7 第一条路径失效后各路径的可靠性取值情况
同理，第二条工作路径失效后，根据图 8选择备用路径为P5，可靠性值Pr(P1P2, (P4P5))=0.068 328。
图 8 第二条路径失效后各路径的可靠性取值情况
对于图 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次。
-
2SMPs传输的随机流网络可靠性分析，通常是求取系统最小容量向量，运用容斥原理计算可靠性值。本文根据MDD能够双向反映组件状态与系统状态关系的特点，提出算法MDD_2SMPs，实例结果表明，相比获取系统最小容量向量方法，本文算法主要有以下特点：1)通过定义MDD操作算子，得到路径容量是唯一有序的，减少了路径容量的约束判断；2)在系统结构不变情况下，可用于不同参数的可靠性分析，避免了存储整个网络的边以及运用容斥原理计算的繁琐。此外，针对网络工作路径失效的问题，算法MDD_BMPs通过将网络各路径转换为决策图多值变量形式，大大降低了选择可靠备用路径的计算复杂性。
Reliability Analysis Algorithm for Multi-State Two Separate Minimal Paths Based on Multi-Valued Decision Diagram
-
摘要: 传统算法计算两条不交化路径传输的随机流网络可靠性，是通过获取系统最小容量向量的方法，需要存储整个网络的边以及移除冗余向量，运算非常复杂。因此提出基于MDD的多状态两条不交化路径可靠性分析算法MDD_2SMPs，利用MDD能够双向反映组件状态与系统状态关系的特点，通过定义MDD操作算子，在无需对路径进行流量分配的情况下获取路径容量，并在组合过程中引入约束剪枝策略对无效容量过滤，提高算法效率。针对路径失效问题，提出基于MDD的备用路径选择算法MDD_BMPs，通过将各路径转换为决策图多值变量形式，降低了计算备用路径可靠性的复杂性。实例结果表明，算法MDD_2SMPs比传统算法减少了计算可靠性的运算量，并能精确选择网络备用路径。Abstract: Traditional methods apply system minimum capacity vectors to calculate the reliability of stochastic-flow network with two separate minimal paths (2SMPs), which needs to store the arc of entire network and the process of removing redundant vectors is complex. In view of this, based on multi-valued decision diagram (MDD) for 2SMPs, we propose a reliability analysis algorithm, called MDD_2SMPs. The main idea of this algorithm is using MDD to reflect the relationship between components status and system status, by defining MDD operators, the path capacity can be obtained without the need for flow distribution. Besides, the constraint pruning strategy is introduced in the process of combination to filter many unnecessary combinations. Furthermore, aiming at the problem of path failure, all paths are converted into MDD variables by using the proposed algorithm MDD_BMPs, resulting a great reduction of the computational complexity. Example analysis shows that the proposed algorithm based on MDD has less calculation burden than traditional methods and can select the network backup paths accurately.
-
Key words:
- backup paths /
- MDD /
- network reliability /
- separate minimal paths
-
表 1 图2中各边数据信息
边 容量 概率 时延 成本 边 容量 概率 时延 成本 a1 50a 0.85 2 3 a12 60 0.80 2 2 30 0.05 40 0.05 10 0.05 20 0.05 0 0.05 10 0.05 a2 50 0.80 2 4 0 0.05 30 0.10 a13 60 0.75 1 3 10 0.05 40 0.10 0 0.05 20 0.05 a3 40 0.85 3 3 10 0.05 20 0.05 0 0.05 10 0.05 a14 20 0.95 2 2 0 0.05 0 0.05 a4 50 0.85 3 2 a15 70 0.80 3 2 30 0.05 50 0.05 10 0.05 30 0.05 0 0.05 10 0.05 a5 50 0.80 4 3 0 0.05 30 0.10 a16 60 0.75 2 2 10 0.05 40 0.10 0 0.05 30 0.05 a6 40 0.85 3 2 10 0.05 20 0.05 0 0.05 10 0.05 a17 50 0.85 3 3 0 0.05 30 0.05 a7 20 0.90 2 1 10 0.05 0 0.10 0 0.05 a8 50 0.85 3 3 a18 40 0.85 3 4 30 0.05 30 0.05 10 0.05 10 0.05 0 0.05 0 0.05 a9 40 0.85 4 1 a19 50 0.85 3 1 20 0.05 30 0.05 10 0.05 10 0.05 0 0.05 0 0.05 a10 40 0.80 2 2 a20 40 0.85 3 2 20 0.10 20 0.05 10 0.05 10 0.05 0 0.05 0 0.05 a11 50 0.85 3 1 a21 20 0.95 2 2 30 0.05 0 0.05 10 0.05 a22 10 0.95 4 1 0 0.05 0 0.05 注：50a表示边a1容量处于50时的概率为0.85 
下载: 导出CSV
表 2 两种算法获取(d, T, B)下路径所需容量的操作数
不相交路径(Pi, Pj) 算法(d, T, B, (Pi, Pj))-LBPs 算法MDD_2SMPs 不相交路径(Pi, Pj) 算法(d, T, B, (Pi, Pj))-LBPs 算法MDD_2SMPs P1, P2 3 718 150 P4, P10 352 126 P3, P4 6 358 150 P5, P6 6 358 150 P3, P5 6 358 150 P5, P7 3 718 90 P3, P6 3 718 150 P5, P9 550 60 P3, P8 550 50 P6, P7 1 782 90 P3, P9 22 60 P6, P8 198 50 P3, P10 198 105 P7, P8 0 0 P4, P5 9 702 180 P7, P9 0 0 P4, P6 6 358 180 P7, P10 0 0 P4, P8 1 078 60 P8, P10 0 0 P4, P9 550 72
下载: 导出CSV
表 3 各路径可能传输的单位数据
路径 单位容量 最大容量 概率 时延 成本 路径 单位容量 最大容量 概率 时延 成本 40a 200 0.578 50 200 0.541 875 30 180 0.110 5 40 200 0.072 25 P1 20 120 0.040 5 7 10 P5 30 150 0.114 875 8 7 10 60 0.128 375 10 50 0.128 375 0 0 0.142 625 0 0 0.142 625 40 120 0.578 40 160 0.614 125 30 90 0.110 5 30 120 0.047 25 P2 20 60 0.040 5 10 7 P6 20 80 0.067 625 9 7 10 30 0.128 375 10 40 0.128 375 0 0 0.142 625 0 0 0.142 625 40 160 0.578 20 120 0.769 5 30 120 0.034 P7 10 60 0.087 875 7 5 P3 20 80 0.117 9 6 0 0 0.142 625 10 40 0.128 375 P8 10 60 0.902 5 7 3 0 0 0.142 625 0 0 0.097 5 50 200 0.51 P9 10 40 0.857 375 9 7 40 200 0.104 125 0 0 0.142 625 30 200 0.036 125 P10 20 60 0.692 55 P4 20 140 0.078 75 6 6 10 30 0.121 956 25 10 11 10 70 0.128 375 0 0 0.185 493 75 0 0 0.142 625 注：40a表示路径P1容量为40时，在(d, T, B)约束下通过的单位数据为200 Gb
下载: 导出CSV
-
[1] CHANG S, LI L. Reliability analysis of highway and transportation network with paths failure[C]//Advanced Research and Technology in Industry Applications (WARTIA).[S.l.]: IEEE, 2014: 50-53. http://ieeexplore.ieee.org/document/6976188/ [2] VAZIFEHDAN J, PRASAD R V, NIEMEGEERS I. Energy-efficient reliable routing considering residual energy in wireless ad hoc networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(2):434-447. doi: 10.1109/TMC.2013.7 [3] 李振, 孙新利, 姬国勋, 等.计算多状态网络可靠度的不交化改进算法[J].通信学报, 2011, 21(9A):166-172. http://d.old.wanfangdata.com.cn/Conference/7851053 LI Zhen, SUN Xin-li, JI Guo-xun, et al. An improved algorithm for the non intersection of multi-state network reliability[J]. Chinese Journal of Communications, 2011, 21(9A):166-172. http://d.old.wanfangdata.com.cn/Conference/7851053 [4] RAMIREZ-MARQUEZ J E, COIT D W. A Monte-Carlo simulation approach for approximating multi-state two-terminal reliability[J]. Reliability Engineering & System Safety, 2005, 87(2):253-264. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=b533dcf546be1863e9bf7013baa99447 [5] JANE C C, LAIH Y W. Computing Multi-State Two-Terminal Reliability through critical arc states that interrupt demand[J]. IEEE Transactions on Reliability, 2010, 59(2):338-345. doi: 10.1109/TR.2010.2046805 [6] SHRESTHA A, XING L, DAI Y. Decision diagram based methods and complexity analysis for multi-state systems[J]. IEEE Transactions on Reliability, 2010, 59(1):145-161. doi: 10.1109/TR.2009.2034946 [7] YEH W C. A simple MC-based algorithm for evaluating reliability of stochastic-flow network with unreliable nodes[J]. Reliability Engineering & System Safety, 2004, 83(1):47-55. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=b3710dc2b7cbf7fa2b1286dccddde4d8 [8] LIN Y K. Extend the quickest path problem to the system reliability evaluation for a stochastic-flow network[J]. Computers & Operations Research, 2003, 30(4):567-575. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=9f1f9efb93450358f85a34561e545f9b [9] LIN Y K. A method to evaluate routing policy through p, minimal paths for stochastic case[J]. Information Sciences, 2010, 180(23):4595-4605. doi: 10.1016/j.ins.2010.07.036 [10] LIN Y K. Spare routing reliability for a stochastic flow network through two minimal paths under budget constraint[J]. IEEE Transactions on Reliability, 2010, 59(1):2-10. http://ieeexplore.ieee.org/document/5411944/ [11] LIN Y K. Spare routing reliability for a stochastic flow network through two minimal paths under budget constraint[J]. IEEE Transactions on Reliability, 2010, 59(1):2-10. doi: 10.1109/TR.2010.2040765 [12] FORGHANI-ELAHABAD M, MAHDAVI-AMIRI N. An efficient algorithm for the multi-state two separate minimal paths reliability problem with budget constraint[J]. Reliability Engineering & System Safety, 2015, 142:472-481. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=68363cc6b63e8c51cd703a2578407795 [13] LIN Y K, HUANG C F. A multi-state computer network within transmission error rate and time constraints[J]. Journal of the Chinese Institute of Industrial Engineers, 2012, 29(7):477-484. doi: 10.1080/10170669.2012.727479 [14] LIN Y K, HUANG C F. Assessing reliability within error rate and time constraint for a stochastic node-imperfect computer network[J]. Proceedings of the Institution of Mechanical Engineers, Part O:Journal of Risk and Reliability, 2013, 227(1):80-85. doi: 10.1177/1748006X12468685 [15] ZHANG Y, XU Z, WANG X, et al. Single minimal path based backup path for multi-state network[J]. Proceedings of the Institution of Mechanical Engineers Part O Journal of Risk & Reliability, 2013, 228(2):152-165. http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=23fb1116a30b79a8143c7c78ee18d78e [16] 古天龙, 徐周波.有序二叉决策图及应用[M].北京:科学出版社, 2009. GU Tian-long, XU Zhou-bo. Ordered binary decision diagram and it's application[M]. Beijing:The Science Publishing Company, 2009. [17] DONG R, ZHU Y, XU Z, Li F. Decision diagram based symbolic algorithm for evaluating the reliability of multistate flow network[J]. Mathematical Problems in Engineering, 2016, doi: 10.1155/2016/6908120. -
点击查看大图
图(8) / 表(3)
计量
- 文章访问数: 6444
- HTML全文浏览量: 2163
- PDF下载量: 96
- 被引次数: 0
