基于二元决策图的节点不可靠网络可靠度计算

肖宇峰,张 华

(西南科技大学a.信息工程学院;b.特殊环境机器人技术四川省重点实验室,四川绵阳621010)

基于二元决策图的节点不可靠网络可靠度计算

肖宇峰a,b,张 华a,b

(西南科技大学a.信息工程学院;b.特殊环境机器人技术四川省重点实验室,四川绵阳621010)

针对节点不可靠网络可靠度计算效率较低的问题,提出一种基于二元决策图的网络可靠度计算方法。通过因子分解得到节点可靠网络的有序二元决策图(OBDD),根据节点和边的关系对边的变量节点执行边替换操作,生成节点不可靠网络的OBDD,并利用其高效存储结构提高不可靠节点的处理效率。在遍历OBDD计算可靠度时,引入Hash表以避免对同一节点的重复访问,从而减少冗余计算,进一步提高计算效率。在基准网络中的对比实验结果表明,该方法不仅能正确计算网络可靠度,而且能快速分析大型网络。

网络可靠度;二元决策图;不可靠节点;因子分解;布尔变量

1 概述

对于当前通信量急剧增加的骨干网络[1-2]、广泛应用的无线传感器网络以及灾变环境下的数据网络[3],节点失效带来的网络可靠性问题正被工程人员和学者广泛关注[4-5]。对节点不可靠网络进行可靠性分析时,需要解决2个问题:(1)如何处理不可靠节点[6];(2)当网络规模较大时,如何提高计算效率[7-8]。文献[3]应用因子分解来评估无线传感器网络的可靠度,该方法的计算开销随着网络规模增大快速增长[9];文献[10-11]应用分区等价类减少同构子网带来的重复计算,大幅提高了网络可靠度计算效率,但未考虑不可靠节点。文献[12-13]提出应用二元决策图(Binary Decision Diagram,BDD)计算节点不可靠网络的可靠度,基于位向量的Hash表存储开销随着网络规模扩大快速增加。本文提出一种基于二元决策图的节点不可靠网络可靠度计算方法。首先按确定边序分解网络并生成节点可靠时的有序二元决策图(Ordered BDD,OBDD),然后对OBDD变量节点执行边替换操作,生成节点不可靠时网络的OBDD,最后遍历OBDD计算网络可靠度。

2 符号表示

本文使用到的符号定义如下:

psrc:网络的源端;

pdst:网络的终端;

G(V,E):表示网络拓扑结构的图,其中,V是图的点集,E是图的边集;

frel(G):网络G的可靠度计算函数;

Oobdd(G):网络G的OBDD结构;

fr_o(Oobdd(G)):根据网络OBDD计算可靠度的函数;

G+e:收缩G中e边生成的子网;

G-e:删除G中e边生成的子网。

此外:

(1)本文讨论的可靠度是指网络源端和终端之间保持连通的概率。源端和终端之间存在一条连通的路径,则认为网络可靠;否则,网络不可靠。

(2)上述收缩和删除边的情形可扩展为:连续收缩边a和b得到的子网表示为G+a+b;连续删除边a和b得到的子网表示为G-a-b;连续收缩边a后删除边b得到的子网表示为G+a-b。

3 网络可靠度计算方法

本文在计算效率和不可靠节点处理方面增强了基于OBDD的网络可靠度计算方法:首先利用边的因子分解创建节点可靠网络的OBDD结构;其次根据边和节点的逻辑联系,对边的OBDD变量节点执行边替换操作,创建节点不可靠网络的OBDD结构;最后遍历OBDD来计算网络可靠度,并利用Hash表减少对同一OBDD节点的重复访问,进一步提高计算效率。

3.1 基于因子分解方法的OBDD创建

3.1.1 因子分解的基本概念

边的因子分解方法通常假设网络边不可靠而节点可靠,根据边的2种情况进行分解:边可靠则收缩边,把边的2个端点合并成一个点;边不可靠则删除边,把边的2个端点保留在网络中。基于因子分解的网络可靠度计算可用如下公式表示[4]:

其中,e是网络的某条边;p是该边可靠的概率;frel(G+e)是收缩e后网络的可靠度;frel(G-e)是删除e后网络的可靠度。

图1给出了利用边的因子分解创建OBDD的实例,网络G及其分解得到的子网按边序e0～e5进行6次分解。其中,灰色点表示包含或者合并了源端(终端)的节点,图中省略了源端和终端分离的子网,所有的分解过程最后聚焦为源端和终端合并为一个节点的子网。显然,根据确定边序执行因子分解把网络逐层分为多个子网,每执行一次收缩边和删除边操作就得到更小的子网。图1中,除了第一次外的每次分解都是在上次分解得到的子网之上做进一步分解,得到更小的子网。图中的实线表示收缩边,虚线表示删除边,L6层的灰色点并为一点,表示源端和终端之间存在连通路径。

图1 网络的因子分解

3.1.2 节点可靠网络的OBDD创建

创建 OBDD时,首先要确定边序e0,e1,…,em-1,然后根据边的逻辑(是否可靠)状态来分析网络是否连通。利用OBDD的ITE运算可以把每次分解对应的逻辑判断记录下来,最后得到描述整个网络的状态图[7]。网络G的OBDD结构可通过下式描述:

其中,f是边序中某条边的OBDD表达式;g是收缩边得到子网的OBDD结构;h是删除边得到子网的OBDD结构。显然,g和h需要对边序中其他边递归执行相同ITE运算得到。图2给出了图1中实例网络的OBDD,创建OBDD的具体步骤可参考文献[12-13]。

图2 节点可靠网络的OBDD

3.1.3 节点不可靠网络的OBDD创建

前述OBDD创建过程假设网络节点可靠,下文介绍一种应用逻辑运算处理不可靠节点的方法。

假设网络G的节点可靠时,OBDD布尔变量Ve表示边e,则G的OBDD结构可表示为:

其中,Oobdd(G)|Ve=1表示e处于可靠状态时G的OBDD结构;Oobdd(G)|Ve=0表示e处于不可靠状态时G的OBDD结构。节点不可靠时需要考虑边的2个端点的逻辑状态,用布尔变量Va和Vb分别表示e的端点a,b。那么,e的完整布尔表示式为Va∧Ve∧Vb。为得到节点不可靠网络G的OBDD,需要进行如下运算:

其中,obdd2是Va∧Ve∧Vb的OBDD结构。上述运算的含义是用端点不可靠的e替换OBDD中原有的e,执行了OBDD的composition运算[10]。本文将该运算过程称为边替换。

节点不可靠网络的OBDD创建算法伪码如下:

对图2各边执行下列边替换操作后,得到图3中节点不可靠时网络的OBDD结构。

图3 节点不可靠网络的OBDD

(1)＜v0,e0,v1＞的布尔变量替代 ＜e0＞的变量:

(2)＜v0,e1,v2＞的布尔变量替代 ＜e1＞的变量:

(3)＜v0,e2,v3＞的布尔变量替代 ＜e2＞的变量:

(4)＜v1,e3,v2＞的布尔变量替代 ＜e3＞的变量:

(5)＜v1,e4,v3＞的布尔变量替代 ＜e4＞的变量:

(6)＜v2,e5,v3＞的布尔变量替代 ＜e5＞的变量:

3.2 可靠度计算

3.2.1 可靠度计算原理及算法

按照上述改进方法创建网络G的OBDD结构后,可通过下面的递归公式来计算网络G的可靠度:

其中,0≤k＜n;Oobdd(G)|xk=1是xk=1时网络G的OBDD,即xk对应节点或边可靠时G的OBDD结构;Oobdd(G)|xk=0是xk=0时网络G的OBDD结构,即xk对应节点或边不可靠时G的 OBDD结构; Pr(xk=1)是xk对应节点或边的可靠概率,Pr(xk=0)是xk对应节点或边不可靠概率;bddtrue和bddfalse分别表示OBDD结构中的逻辑真和逻辑假;k的初始值为0。显然,完成上述公式的计算需要沿OBDD结构遍历其节点,而且某些节点被多次访问。在图4中,e2,e4和e5在计算过程中被多次访问,从而带来重复计算。为减少这种冗余计算,设计算法时建立一个hash表,以当前子网的OBDD根节点标号为索引记录当前子网的可靠度数值,当再次访问该节点时直接返回已保存的数值。

下面的NetRel_urn()给出了节点不可靠网络的可靠度计算伪码。其中,G代 表 网 络; BDDConstruct()是因子分解创建节点可靠网络OBDD的算法,详细实现可参考文献[4]; BDDConstruct_urn()是上文创建节点不可靠网络的OBDD算法;BDDRel()是本小节上述计算方法的实现。

3.2.2 算法复杂度分析

本文算法由三部分组成:BDDConstruct, BDDConstruct_urn和BDDRel。其复杂度由其计算复杂度决定。文献[9]通过优化节点可靠网络的分解过程,给出BDDConstruct和BDDRel复杂度的上界:

其中,O1为BDDConstruct和BDDRel的算法复杂度,m为网络的边数,Fmax为最大边界集的元素个数,BFmax是最大边界集的Bell数。这个值是现有研究中比较实用的上界值,本文按文献[9]的方法优化网络分解后,BDDConstruct_urn的复杂度就可由BDD宽度和深度计算。BDD深度由网络的边数确定,BDD宽度上界可根据文献[9]确定:

其中,Wbdd是 BDD 宽度上界。由算法结构, BDDConstruct_urn的复杂度上界为:

综上所述,整个算法复杂度的上界为:

可见,Fmax决定了算法的复杂度,数百节点的网络一般都有较小的Fmax值。根据文献[9]优化后,本文算法的计算效率将得到进一步改善。

4 实验与结果分析

本文采用Buddy版BDD实现本文方法,并将其C语言实现程序命名为NetRel_urn[14]。为方便对比分析,同时实现了文献[3,13]的方法,并分别命名为NetRel_yz和NetRel_x。实验计算机的CPU工作频率为2.4 GHz,内存容量为2 GB,操作系统为2.6内核的红帽Linux。图4列出的9个网络被较多文献使用[9-13],因此,本文将其作为基准网络来检验计算的正确性和效率。网络中的黑实点分别表示源端和终端,点和边可靠度是0.9。

图4 实验基准网络

实验结果如表1所示,其中,“-”表示开销超过1 h。

表1 计算时间比较 s

每个程序被执行10次后,其平均计算时间被记录为表中的时间开销。可以看出,NetRel_yz和NetRel_ x的开销高于NetRel_urn。从网络6、网络7、网络8和网络9的计算结果可以发现:随着网络规模增大, NetRel_yz的计算开销显著上升,甚至在1 h内也无法得到计算结果;NetRel_x也无法计算网络8和网络9的可靠度;相比之下,NetRel_urn完成了计算任务。实验结果表明,本文方法可有效评估节点不可靠网络的可靠度,当网络规模较大时,其计算开销较低。

5 结束语

为高效处理不可靠节点,本文提出了一种网络可靠度计算方法,利用OBDD变量节点的边替换操作和OBDD高效存储结构提高计算效率。实验结果表明,该方法能以较快的速度计算规模较大网络的可靠度。但本文未考虑节点和边失效的统计相关性,下一步将对其进行深入研究。

[1] Ball M,Thomas M.Hand Books in Operations Research andManagementScience,NetworkModels[M]. [S.l.]:Elsevier,1995.

[2] Lin Y K,Chang P C.A Novel Reliability Evaluation Technique for Stochastic-flow Manufacturing Networks with Multiple Production Lines[J].IEEE Transactions on Reliability,2013,62(1):92-104.

[3] AboElFotoh H M F,IyengarS S,Chakrabarty K. Computing Reliability and message delay for cooperative Wireless Distributed Sensor Networks Subject to Random Failures[J].IEEE Transactions on Reliability, 2005,54(1):145-155.

[4] 肖宇峰.基于离散概率模型的二端网络可靠性分析[D].北京:北京邮电大学,2009.

[5] 江逸楠,李瑞莹,黄 宁,等.网络可靠性评估方法综述[J].计算机科学,2012,39(5):9-13.

[6] 吴 俊,段东立,赵 娟.网络系统可靠性研究现状与展望[J].复杂系统与复杂性科学,2011,8(2):77-86.

[7] 肖宇峰,李 昕,李玉宏,等.用改进的OBDD方法计算通信网可靠度[J].计算机应用研究,2010,27(3):114-117.

[8] Huang N,Chen Y,Hou D,et al.Application Reliability for Communication Networks and Its Analysis Method[J].Journal of Systems Engineering and Electronics,2011,22(6):1030-1036.

[9] Hardy G,LucetC,LimniosN.K-terminalNetwork Reliability Measures with Binary Decision Diagrams[J]. IEEE Transactions on Reliability,2007,56(3):506-515.

[10] Imai H,Sekine K,Imai K.Computational Investigations of all-terminal Network Reliability via BDDs[J].IEICE Transactions on Fundamentals,1999,E82-A(5):714-721.

[11] Carlier J,Lucet C.A Decomposition Algorithm for Network Reliability Evaluation[J].Discrete Applied Mathematics,1996,65(1):141-156.

[12] Kuo S Y,Yeh F M,Lin H Y.Efficient and Exact Reliability Evaluation for Networks with Imperfect Vertices[J].IEEE Transactions on Reliability,2007,56 (2):198-211.

[13] Xing Liudong.An Efficient Binary Decision Diagram Based Approach for Network Reliability and Sensitivity Analysis[J].IEEE Transactions on Systems,Man,and Cybernetics——Part A:Systems and Humans,2008,38 (6):105-115.

[14] Andersen H.An Introduction to Binary Decision Diagrams[M].[S.l.]:Elsevier,1997.

编辑 金胡考

Reliability Computation of Network with Unreliable Nodes Based on Binary Decision Diagram

XIAO Yufenga,b,ZHANG Huaa,b
(a.Information Engineering School;b.Special Environment Robot Technology Key Laboratory of Sichuan Province,Southwest University of Science and Technology,Mianyang 621010,China)

According to the inefficient reliability computation of network with unreliable nodes,this paper proposes a network reliability computation method based on Binary Decision Diagram(BDD).After the Ordered Binary Decision Diagram(OBDD)construction with factoring theorem,this method executes the edge replacements to OBDD variables of edges with the relation between nodes and edges,and the OBDD of network with unreliable nodes is constructed.Based on efficient OBDD structure,the computations about unreliable nodes are improved.Furthermore,a hash table is used to avoid the repeated access to same node when the reliability is calculated with OBDD traversal.Therefore,the redundant calculations are reduced,and the reliability computation efficiency of network with unreliable nodes is enhanced. Experiments are arranged on benchmark networks,and data analysis shows that this method can accurately calculate network reliability and quickly analyze some large networks.

network reliability;Binary Decision Diagram(BDD);unreliable node;factoring;Boolean variable

1000-3428(2015)01-0087-05

A

TP393

10.3969/j.issn.1000-3428.2015.01.016

国家核能开发科研基金资助项目([2011]1137);四川省科技支撑计划基金资助项目(2013GZX0152);四川省教育厅基金资助重点项目(14ZA0091)。

肖宇峰(1978-),男,副研究员、博士,主研方向:网络通信,计算机系统可靠性评估;张 华,教授、博士。

2014-01-20

2014-03-20 E-mail:xiaoyf_swit1@163.com

中文引用格式:肖宇峰,张 华.基于二元决策图的节点不可靠网络可靠度计算[J].计算机工程,2015,41(1):87-91.

英文引用格式:Xiao Yufeng,Zhang Hua.Reliability Computation of Network with Unreliable Nodes Based on Binary Decision Diagram[J].Computer Engineering,2015,41(1):87-91.