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

J4 ›› 2012, Vol. 34 ›› Issue (9): 26-32.

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

潘竹生,莫毓昌,钟发荣,赵建民

( 浙江师范大学数理与信息工程学院，浙江金华 321004)

收稿日期:2012-04-13 修回日期:2012-06-28 出版日期:2012-09-25 发布日期:2012-09-25
基金资助:
国家自然科学基金资助项目(60903011);浙江省自然科学基金资助项目(Y1100689),浙江省科技厅项目(2010C31122);浙江省重中之重学科项目(ZSDZZZZXK24)

Performance Improvement of BDDbased Network Reliability Analysis Algorithm

PAN Zhusheng,MO Yuchang,ZHONG Farong,ZHAO Jianmin

(School of Mathematics,Physics and Information Engineering,
Zhejiang Normal University,Jinhua 321004,China)

Received:2012-04-13 Revised:2012-06-28 Online:2012-09-25 Published:2012-09-25

摘要/Abstract

摘要：

BDD是布尔函数的图形表示形式，被广泛应用到网络可靠度的分析计算中。为了提升网络可靠度BDD分析算法的性能，本文根据边扩展图实例，识别两类无效边扩展路径：冗余节点型无效扩展路径和ST非连通型无效扩展路径，然后基于基本的网络可靠度BDD分析算法，实现了两类无效扩展路径的消除技术。实验结果表明，两种无效扩展路径消除技术能够提前识别无效扩展路径，避免无效扩展，有效减少中间子网的数量，缩减分析时间；通过把两种技术结合起来，可以有效地消除边扩展图中的这两类无效扩展路径，从而极大提升可靠度分析的性能。

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

Abstract:

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 expansion 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.

Key words: binary decision diagram(BDD);network reliability;edge expansion paths

潘竹生,莫毓昌,钟发荣,赵建民. 网络可靠度BDD分析算法的性能改进[J]. J4, 2012, 34(9): 26-32.

PAN Zhusheng,MO Yuchang,ZHONG Farong,ZHAO Jianmin. Performance Improvement of BDDbased Network Reliability Analysis Algorithm[J]. J4, 2012, 34(9): 26-32.

参考文献

［1］Soh S,Rai S.Experimental Results on Preprocessing of Path/Cut Term in the Sum of Disjoint Products Technique［J］. IEEE Transaction on Reliability,1993,42:2433.
［2］Kuo S Y,Lu S K,Yeh F M.Determining Terminalpair Network Reliability Based on Edge Expansion Diagrams Using OBDD［J］. IEEE Transaction on Reliability, 1999, 48(3):234246.
［3］Akers B. Binary Decision Diagrams［J］. IEEE Transaction on Computers, 1978, 27(6):509516.
［4］Dutuit Y, Rauzy A, Signoret J P. Computing Network Reliability with Réséda and Aralia ［C］∥Proc of European Safety and Reliability Association Conference, 1996:19471952.
［5］Page L B, Perry J E. A Practical Implementation of the Factoring Theorem for Newtork Reliability［J］. IEEE Transaction on Reliability, 1988,37(3):259267.
［6］Yeh FM,Kuo SY. OBDDBased Network Reliability Calculation［J］. Electronics Letters, 1997,33(9):759760.
［7］Yeh FM, Lu SK, Kuo SY.OBDDBased Evaluation of kterminal Network Reliability［J］.IEEE Transaction on Reliability, 2002,51(4):443451.
［8］Hardy G, Lucet C, Limnios N. Computing Allterminal Reliability of Stochastic Networks with Binary Decision Diagrams［C］∥Proc of the 11th International Symposium on Applied Stochastic Models and Data Analysis, 2005:14691474.
［9］Hardy G, Lucet C, Limnios N. KTerminal Network Reliability Measures With Binary Decision Diagrams［J］. IEEE Transaction on Reliability, 2007, 56(3):506515.
［10］Herrmann J U,Soh S. A Space Efficient Algorithm for Network Reliability［C］∥Proc of the 15th AsiaPacific Conference on Communications, 2009:703707.
［11］Herrmann J U. Improving Reliability Calculation with Augmented Binary Decision Diagrams［C］∥Proc of IEEE Advanced Information Networking and Applications, 2010:329333.
［12］Herrmann J U, Soh S. Comparison of Binary and MultiVariate Hybrid Decision Diagram Algorithms for KTerminal Reliability［C］∥Proc of the ThirtyFourth Australasian ComputerScience Conference, 2010.
［13］Sekine K, Imai H. Computation of the Network Reliability (Extended Abstract)［R］.Technical Report, Department of Information Science，University of Tokyo, 1998.
［14］Imai H, Sekine K, Imai K. Computational Investigations of All Termina Network Reliability via BDDs［J］.IEICE Transactions on Fundamentals, 1999,82(5):714721.
［15］Bryant R E. Symbolic Boolean Manipulation with Ordered BinaryDecision Diagrams［J］. ACM Computing Surveys, 1992,24(3):293318.
［16］Friedman S J,Supowit K J. Finding the Optimal Variable Ordering for Binary Decision Diagrams［C］∥Proc of the 24th ACM/IEEE Conference on Design Automation, 1987:348356.
［17］Carlier J, Lucet C. A Decomposition Algorithm for Network Reliability Evaluation［J］. Journal of Discrete Applied Mathematics, 1996, 65(13):141156.

[1]	潘竹生,莫毓昌. 边排序质量影响因素研究[J]. J4, 2015, 37(11): 2091-2098.
[2]	潘竹生,莫毓昌,钟发荣,刘轩,伍欢. 一种新的启发式边排序策略及其性能分析[J]. J4, 2014, 36(11): 2119-2127.