网络可靠度BDD分析算法的性能改进  

Performance Improvement of BDD-based Network Reliability Analysis Algorithm

作　　者：潘竹生[1] 莫毓昌[1] 钟发荣[1] 赵建民[1] 

机构地区：[1]浙江师范大学数理与信息工程学院,浙江金华321004

出　　处：《计算机工程与科学》2012年第9期26-32,共7页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(60903011);浙江省自然科学基金资助项目(Y1100689);浙江省科技厅项目(2010C31122);浙江省重中之重学科项目(ZSDZZZZXK24)

摘　　要：BDD是布尔函数的图形表示形式,被广泛应用到网络可靠度的分析计算中。为了提升网络可靠度BDD分析算法的性能,本文根据边扩展图实例,识别两类无效边扩展路径:冗余节点型无效扩展路径和ST非连通型无效扩展路径,然后基于基本的网络可靠度BDD分析算法,实现了两类无效扩展路径的消除技术。实验结果表明,两种无效扩展路径消除技术能够提前识别无效扩展路径,避免无效扩展,有效减少中间子网的数量,缩减分析时间;通过把两种技术结合起来,可以有效地消除边扩展图中的这两类无效扩展路径,从而极大提升可靠度分析的性能。BDD is a diagrammatic representation of the Boolean function and has been widely applied to the network reliability analysis. In order to enhance the performance of network reliability analysis algorithm based on BDD,this paper first puts forward two kinds of invalid edge expansion paths according to the edge expansion diagram instance., invalid edge expansion with redundant nodes and invalid edge ex pansion with ST unconnectedness. Then, useful techniques are provided to successfully eliminate those invalid edge expansion paths. Experimental results show that these techniques can identify the invalid paths in advance, avoid invalid extension, reduce the number of intermediate subnetworks and shorten the analysis time. With these two techniques, both of the invalid expansion paths can be eliminated, and hence great performance improvement of network reliability analysis is achieved.

关 键 词：二进制决策图 网络可靠度 边扩展路径 

分 类 号：TB114[理学—概率论与数理统计]