网络可靠度BDD分析中2种边排序策略的性能比较  

Comparison of two ordering edge heuristics used in BDD-based network reliability analysis

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

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

出　　处：《浙江师范大学学报（自然科学版）》2013年第1期88-95,共8页Journal of Zhejiang Normal University:Natural Sciences

基　　金：国家自然科学基金资助项目(60903011);浙江省自然科学基金资助项目(Y1100689);浙江省计算机软件与理论重中之重学科开放课题资助项目(ZSDZZZZXK24)

摘　　要：网络可靠度二元决策图(BDD)分析过程包含边排序、BDD生成和可靠度评估3个步骤,其中BDD生成和可靠度评估的计算复杂度和BDD尺度线性相关,而BDD尺度取决于边排序.因此,边排序问题是研究网络可靠度BDD分析的核心.在实现广度优先和深度优先2种边排序策略的基础上,针对规则网络(N*N型和M*N型),比较了这2种策略的分析性能.实验数据表明:1)规则网络中广度优先边排序策略优于深度优先边排序策略;2)当M>N时,广度优先边排序策略在M*N型网络中的性能表现优于与之等价的N*M型网络.这些结论为设计更优的启发性边排序策略提供了重要依据.The analysis procedure of network reliability based on Binary Decision Diagram （ BDD ） consisted three steps： edge ordering, generating of BDD and calculating the reliability. In these steps, the complexity of BDD generation and the reliability assessment were linear correlated to the size of BDD, and the size of BDD was determined by the edge ordering. Thus, the edge ordering problem was the key problem in the research of BDD-based network reliability analysis. The two edge ordering heuristics was implemented by breadth-first search edge （ BFSE ） and deepth-first search edge （ DFSE ）. Then, the analysis performance of these two edge ordering heuristics for the regular networks such as N ＊ N and M ＊ N was compared. The experiment results showed that 1 ） BFSE was better than DFSE and 2 ） When M was greater than N, the performance of BFSE in the M ＊ N network was better than that in the N ＊ M network which was equivalent to the M ＊ N network. These resuhs were important for designing the better heuristic edge-ordering.

关 键 词：网络可靠度 二叉决策图 启发性边排序 香农分解 

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