一种新的启发式边排序策略及其性能分析

J4 ›› 2014, Vol. 36 ›› Issue (11): 2119-2127.

一种新的启发式边排序策略及其性能分析

潘竹生,莫毓昌,钟发荣,刘轩,伍欢

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

收稿日期:2014-06-15 修回日期:2014-08-13 出版日期:2014-11-25 发布日期:2014-11-25
基金资助:
国家自然科学基金资助项目(61272130);浙江省自然科学基金资助项目(Y1100689);浙江省重中之重学科开放课题资助项目(ZSDZZZZXK24);浙江省教育厅项目（Y201328072）

A novel heuristic edge ordering strategy
and its performance analysis

PAN Zhusheng,MO Yuchang,ZHONG Farong,LIU Xuan,WU Huan

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

Received:2014-06-15 Revised:2014-08-13 Online:2014-11-25 Published:2014-11-25

摘要/Abstract

摘要：

网络可靠度BDD分析方法的计算复杂度与BDD尺度线性相关，而BDD尺度严重依赖边排序质量。由于求解最优边排序是一个NP问题，在实际应用中，通常采用启发式边排序策略如BFS（BreadthFirstSearch）和DFS（DepthFirstSearch）。针对边排序问题，从分析基于边界集（Boundary Set）的BDD构建方法BDDBS出发，将边界集思想应用于边排序过程，提出了一种新的启发式边排序策略。性能分析和大量实验表明，新设计的边排序策略性能优于经典的DFS和BFS策略，该结果为网络可靠度BDD分析方法在大规模网络中的应用拓展了新的空间。

关键词: 网络可靠度, 二叉决策图, 边界集, 边排序

Abstract:

The computational complexity of the BDD (Binary Decision Diagram) based network reliability method is linear correlated to the size of BDD that heavily depends on the quality of edge ordering.Because it is still NP-hard to find the optimum edge ordering, heuristic ordering methods such as BFS (BreadthFirstSearch) or DFS (DepthFirstSearch) are commonly used in practice.For the edge ordering strategy, boundary set is first used to analyze the characteristics of constructing BDD,and then a high performance edge ordering strategy based on the boundary set is proposed.Several experiments show that the new strategy outperforms the classic methods such as DFS and BFS.The results extend new space for network reliability analysis method using BDD in largescale networks.

Key words: network reliability;binary decision diagram;boundary set;edge ordering.

潘竹生,莫毓昌,钟发荣,刘轩,伍欢. 一种新的启发式边排序策略及其性能分析[J]. J4, 2014, 36(11): 2119-2127.

PAN Zhusheng,MO Yuchang,ZHONG Farong,LIU Xuan,WU Huan. A novel heuristic edge ordering strategy
and its performance analysis [J]. J4, 2014, 36(11): 2119-2127.

参考文献［11］

［1］	Yeh FM, Kuo SY. OBDDbased network reliability calculation［J］. Electronics Letters, 1997, 33(9):759760.
［2］	Kuo SY, Lu S K, Yeh F M. Determining terminalpair network reliability based on edge expansion diagrams using OBDD［J］. IEEE Transactions on Reliability, 1999, 48(3):234246.
［3］	Yeh FM, Lu SK, Kuo SY. OBDDbased evaluation of kterminal network reliability［J］. IEEE Transactions on Reliability, 2002, R51(4):443451.
	Table 9Performance comparison among three strategies in benchmark networks表9Benchmark networks 三种策略性能比较Net\|V\|\|E\|RelibBDD SizeDFSBFSMDFSNet\|V\|\|E\|RelibBDD SizeDFSBFSMDFS1450.978480 9107159140.974145 17840332680.968425 2015131610210.997962 3614072143580.997632 1826231718290.995896 4306432844690.977184 4722151813230.987428 159229212159120.964855 3450211920300.997120 113953591241477110.995665 7051212217260.998171 5886150570788130.996217 7766532414210.995447 31925014398120.975116 5636282636600.975645 49704968108120.984068 5068262848770.956266 437435119130.969112 404841302002980.304293 *5955931216300.998866 180548260net2620300.994395 97915154081421260.904577 25712672net2816240.995553 2228353294［4］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:14681474.
［5］	Hardy G, Lucet C, Limnios N. Kterminal network reliability measures with binary decision diagrams［J］. IEEE Transactions on Reliability, 2007,56 (3):506515.
［6］	Pan Zhusheng, Mo Yuchang,Zhong Farong,et al. Performance improvement of BDDbased network reliability analysis algorithm［J］.Computer Engineering & Science, 2012,34(9):2632.(in Chinese)
［7］	Sieling D, Wegener I.Reduction of OBDDs in linear time［J］. Information Processing Letters, 1993, 48（3）:139144.
［8］	Friedman S J, Supowit K J. Finding the optimal variable ordering for binary decision diagrams［J］. IEEE Transactions on Computer,1990, C39(5):710713.
［9］	Bollig B, Wegener I. Improving the variable ordering of OBDDs is NPComplete［J］. IEEE Transactions on Computers, 1996, 45(9):9931002.
［10］	Dutuit Y, Rauzy A, Signoret J P. Computing network reliability with Reseda and Aralia［C］∥Proc of ESREL’96, 1996:2428.
［11］	Pan Zhusheng, MO Yuchang, Zhao Jianmin. Comparison of two ordering edge heuristics used in BDDbased network reliability analysis［J］. Journal of Zhejiang Normal University(Natural Sciences),2013,36(1):8895.(in Chinese)
［12］	Carlier J, Lucet C. A decomposition algorithm for network reliability evaluation［J］.Discrete Applied Mathematics, 1996, 65(1):141156.
	附中文参考文献：
［6］	潘竹生，莫毓昌，钟发荣，等.网络可靠度BDD分析算法的性能改进［J］.计算机工程与科学，2012,34(9):2632.
［11］	潘竹生，莫毓昌，赵建民.网络可靠度BDD分析中2种边排序策略的性能比较［J］.浙江师范大学学报（自然科学版），2013，36(1):8895.

[1]	潘竹生,莫毓昌. 边排序质量影响因素研究[J]. J4, 2015, 37(11): 2091-2098.
[2]	潘竹生,莫毓昌,钟发荣,赵建民. 网络可靠度BDD分析算法的性能改进[J]. J4, 2012, 34(9): 26-32.