边排序质量影响因素研究

J4 ›› 2015, Vol. 37 ›› Issue (11): 2091-2098.

边排序质量影响因素研究

潘竹生,莫毓昌

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

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

Study on the main factors determining the quality of
edge ordering in BDDbased networks

PAN Zhusheng,MO Yuchang

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

Received:2015-08-11 Revised:2015-10-10 Online:2015-11-25 Published:2015-11-25

摘要/Abstract

摘要：

网络可靠度BDD分析方法的计算性能与BDD尺度紧密相关，而BDD尺度严重依赖边排序质量。因此，边排序问题是网络可靠度BDD分析方法的重要问题。由于求解最优边排序是一个NP问题，在实际网络可靠度分析中，通常采用启发式边排序策略如BFS和DFS，它们适用不同类型的网络。然而，对于给定网络，采用何种边排序策略更优，有哪些因素影响边排序质量，迄今没有给出评判依据。利用边界集思想，提出 “边界长度（BSL）” 概念，并用边界长度BSL表征边排序质量，揭示边界长度BSL和BDD尺度（节点数目）之间的关系。实验结果表明，边界长度BSL与BDD尺度具有正相关性，即较小BSL对应的BDD尺度较小，较大BSL对应的BDD尺度较大，多数情况下，BSL取最值时，BDD尺度能取到（或接近）最值。这为特定网络选择（或设计）高性能边排序提供了重要的参考依据。

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

Abstract:

The computational complexity of network reliability analysis based on the Binary Decision Diagram (BDD) is closely related to the size of BDD, which depends crucially on the quality of edge ordering. So it is of importance to find the best edge ordering that attempts to minimize the memory using BDD manipulation. However, it is still NPhard to find the optimal edge ordering. In practice,heuristic ordering methods such as BreadthFirstSearch (BFS ) or DepthFirstSearch (DFS )，which are suitable for different types of networks, are commonly used.Unfortunately,no formal guidelines or factors which determine the quality of edge ordering are available for choosing a better heuristic approach for the given network. In this work,characterizing the Boundary Set Length (BSL) as the quality of edge ordering, we reveal the relationship between the BSL and the size of BDD.Empirical studies show that the BSL has positive correlation with the size of BDD.This means the smaller the BSL of an edge ordering, the smaller the size of BDD model generated. In most cases, the size of the BDD can get (or be close to) the extreme value when the BSL has its extreme one. This conclusion is useful for choosing or designing high performance edge ordering for a given network.

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

潘竹生,莫毓昌. 边排序质量影响因素研究[J]. J4, 2015, 37(11): 2091-2098.

PAN Zhusheng,MO Yuchang. Study on the main factors determining the quality of
edge ordering in BDDbased networks [J]. J4, 2015, 37(11): 2091-2098.

参考文献

［1］Akers B. Binary decision diagrams［J］. IEEE Transactions on Computers,1978,C27(6):509516.
［2］Bryant R E. Symbolic boolean manipulation with ordered binarydecision diagrams［J］. ACM Computing Surveys,1992, 24(3):293318.
［3］Singh H,Vaithilingam S, Anne R K. Terminal reliability using binary decision diagrams ［J］. Microelectronics Reliability,1996,36(3):363365.
［4］Yeh F M, Kuo S Y. OBDDbased network reliability calculation［J］. Electronics Letters,1997,33(9):759760.
［5］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.
［6］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.
［7］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.
［8］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.
［9］Herrmann J U, Soh S. A space efficient algorithm for network reliability［C］∥Proc of the 15th AsiaPacific Conference on Communications (APCC2009):2009:703707.
［10］Herrmann J U. Improving reliability calculation with augmented binary decision diagrams［C］∥Proc of IEEE Advanced Information Networking and Applications (AINA2012), 2010:329333.
［11］Herrmann J U, Soh S. Comparison of binary and multivariate hybrid decision diagram algorithms for Kterminal reliability［C］∥Proc of the 34th Australasian ComputerScience Conference (ACSC2010),2010:113.
［12］Sieling D, Wegener I. Reduction of OBDDs in linear time［J］. Information Processing Letters,1993(48):139144.
［13］Garey M R, Johnson D S. Computers and Intractibility:A guide to the theory of NPcompleteness［M］. ［S.L.］W.H.Preeman&Co.Ltd,1979.
［14］Bollig B,Wegener I. Improving the variable ordering of OBDDs is NPcomplete［J］. IEEE Transactions on Computers, 1996,45(9):9931002.
［15］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.
［16］Dutuit Y,Rauzy A,Signoret J P. Computing network reliability with reseda and aralia［C］∥Proc of ESREL’96,1996:2428.
［17］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)
［18］Pan Zhusheng,Mo Yuchang,Xing Liudong, et al.New insights into breadthfirst search edge ordering of regular networks for terminalpair reliability analysis［J］. Journal of Risk and Reliability,2014,228(1):8392.
［19］Pan Zhusheng,Mo Yuchang,Zhong Farong. A novel heuristic edge ordering strategy and its performance analysis［J］.Computer Engineering & Science,2014,36(11):21192127.(in Chinese)
［20］Seluk A S,Yücemen M S. Reliability of lifeline networks with multiple sources under seismic hazard［J］. Natural Hazards,2000,21(1):118.
［21］Ching J,Hsu W C. An efficient method for evaluating origindestination connectivity reliability of realworld lifeline networks［J］. ComputerAided Civil and Infrastructure Engineering,2007,22(8):584596.
［22］Javanbarg M B,Takada S. Redundancy model for water supply systems under earthquake environments［C］∥Proc of the 5th International Conference on Seismology and Earthquake Engineering,2007:1.
附中文参考文献：
［17］潘竹生，莫毓昌，赵建民.网络可靠性分析中两种边排序策略的性能比较［J］. 浙江师范大学学报（自然科学版）,2013,36(1):8895.
［19］潘竹生，莫毓昌，钟发荣. 一种新的启发式边排序策略及其性能分析［J］. 计算机工程与科学,2014,36(11):21192127.

[1]	潘竹生,莫毓昌,钟发荣,刘轩,伍欢. 一种新的启发式边排序策略及其性能分析[J]. J4, 2014, 36(11): 2119-2127.
[2]	潘竹生,莫毓昌,钟发荣,赵建民. 网络可靠度BDD分析算法的性能改进[J]. J4, 2012, 34(9): 26-32.