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

2014-09-13潘竹生莫毓昌钟发荣

计算机工程与科学 2014年11期

关键词：排序尺度边界

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

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

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

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

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

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

网络可靠度;二叉决策图;边界集;边排序

1 引言

网络可靠度二叉决策图BDD(Binary Decide Diagram)分析方法包括边排序、等价BDD生成和指标数据计算三个基本过程。其中，等价BDD生成是关键，生成的BDD越小，即BDD尺度(节点数目)越小，可靠度分析方法的性能就越好。Kuo S-Y等人[1～3]利用边扩展EP(Edge Expansion)技术来有效识别同构子网，提出自底向上的紧凑BDD构建方法；Hardy G等人[4,5]利用边界分区(Partition-BS)有效识别同构子网，提出自顶向下的紧凑BDD构建方法，这两种方法在构建过程中存在冗余；Pan Zhu-sheng等人[6]通过识别冗余子网，消除了冗余BDD，进一步改进了性能。然而，BDD的紧凑程度更大程度上依赖边排序质量[7]，不同质量的边排序结果导致BDD尺度跨越几个数量级[8]，高质量的边排序指导生成最为紧凑的BDD。

然而，求解最优边排序已被证明是一个NP完全问题[9]，在实际的网络可靠性分析中，大多采用启发性策略[1～6,10,11]，常见的有广度优先搜索BFS(Breadth-First-Search)和深度优先搜索DFS(Depth-First-Search)。那么是否存在更优的启发式边排序策略呢？

本文尝试从边界集BS(Boundary Set)入手，分析基于边界集的BDD构建方法(BDD-BS)特征，提炼启发性特征数据，用于高性能边排序策略设计，完成新策略与DFS和BFS策略的性能比较，得出实验结论。

2 边界集BS和BDD-BS算法

2.1 边界集BS

定义1三元组G=(V,E,K)称为一个K端网络，其中：

(1)V={V1,V2, …,Vn}，称为顶点集；

(2)E⊆V×V，称为边集;

(3)K⊆V，称为K点集。

为了便于描述，对于E中的点对〈a,b〉,a,b∈V通常赋予另一个名称ei。

图1中的K端网络G对应的三元组为({0，1，2，3，4，5，6}，{e1，e2，e3，e4，e5，e6，e7，e8，e9，e10}，{0，3，6})。

定义2三元组G的边排序Order是E至整数集合{1,2,…,|E|}上的一一对应函数，Order:E→{1,2,…,|E|}。

根据定义可知，G的边排序可以有|E|!种不同的可能。通常获得边排序的方法有广度优先遍历BFS和深度优先遍历DFS。

图1中的K端网络G，以节点”0”为排序起点，则对应的一种广度优先排序Order为：〈e1，e2，e3，e4，e5，e6，e7，e8，e9，e10〉。

图1中的K端网络G，以节点”0”为排序起点，则对应的一种深度优先排序Order为：〈e1，e4，e8，e6，e2，e5，e3，e7，e10，e9〉。

定义3给定K端网络G=(V,E,K)，在边排序Order下得到边序e1≤e2≤…≤e|E|，则定义第k(0≤k≤|E|)层边界集Fk为：

图1所示网络，约定边排序为e1

Figure 1 Network 1 and edge ordering图1 网络1和边排序

FkekBoundarySetFkekBoundarySetF0{}F6e6{3,4,6}F1e1{0,1}F7e7{4,5,6}F2e2{0,1,2}F8e8{4,5,6}F3e3{1,2,3}F9e9{4,5}F4e4{2,3,6}F10e10{}F5e5{2,3,6}

定义4给定K端网络G =(V, E, K)和边排序Order，定义边界长度BSL为：

图1所示网络，约定边排序为e1

2.2 BDD-BS算法

边界集BS首先由CarlierJ和LucetC[12]应用到网络可靠性研究中。2007年HardyG等人[5]利用边界集分区来标识网络特征，提出了自顶向下的BDD构建算法(记为BDD-BS)，用来高效计算全端网络可靠性和K端网络可靠性，具体算法如算法1所示。图2为全连通网络K4的等价BDD构建过程，设边序为e1≤e2≤e3≤e4≤e5≤e6。

算法1OBDD-BS算法

OBDD-BS(G，K)=

1.thenPart, elsePart:Partitions;

2.CreaterootBDDNoderoot;

3.fork=1to|E|do

4.ComputeFk+1;

5.foreachnodeiinlevelkdo

6. thenPart=partitionGen(nodei,ekisup) /*ekisup表示ek连通，ek是参数*/

7.elsePart=partitionGen(nodei,ekis down)/*ekis down表示ek不连通，ek是参数*/

8. if(allK-vertices are in the same block inthenPart) then

9. branchleftChild(nodei) to terminalnode1

10.else

11.if(thenPartisnotinhashtable)then

12.CreateBDDNodenodejinlevelk+1;

13.InsertBDDNodenodejintohashtable;

14.endif

15.branchleftChild(nodei)tonodej

16.endif

17.if(oneK-vertexisdisconnectedinelsePart)then

18. branchrightChild(nodei) to terminalnode0;

19.else

20.if(elsePartisnotinhashtable)then

21.CreateBDDNodenodejinlevelk+1;

22.InsertBDDNodenodejintohashtable;

23.endif

24.branchrightChild(nodei)tonodej

25.endif

26.endfor

27.endfor

Figure 2 BDD construction process for K4图2 K4网络BDD构建过程

如图2所示，记第k-1层BDD节点数目为BDDSizek-1，当第k层不出现共享子网或终端BDD节点如“0”和“1”，则第k层节点数目BDDSizek等于2*BDDSizek-1，如L2和L3；当出现共享子网或终端BDD节点时，BDDSizek小于2*BDDSizek-1，如L5。所以，一般情况下，BDD节点数目满足如式(1)所示的递推关系。由式(1)可得，最坏情况下BDDSizek= 2k。

BDDSizek≤2*BDDSizek-1

(1)

文献[5，12]指出，第k层BDD宽度Wth与第k层边界集Fk大小有关，记为Wth(|Fk|)，满足关系式(2)，且BDD紧凑程度取决于各层BDD宽度Wth(|Fk|)。如果Wth(|Fk|)小于2*BDDSizek-1，那么第k层必将出现共享BDD，且Wth(|Fk|)越小，共享的BDD节点数目越多。另外，边界集长度|Fk|满足关系式(3)。由式(1)和式(3)得表2。表中“E-Num”表示边数，“BDDSize”表示BDD节点数目，“Wth”表示不考虑K点时BDD的宽度，“Wth-K”表示考虑K点影响时的BDD宽度。很明显BDD宽度随|Fk|呈指数级快速增长，且增长速度远大于最坏情况下BDD节点数目的增长速度。当|Fk|≥10时，Wth≥115975，若k= 9，实际BDD宽度不超过29=512。但是，如果此时|Fk|=5，查表2得Wth-K=454，即Wth(|Fk|)= 454≤29。由此可见，只要每层|Fk|取得足够小，满足Wth(|Fk|)≤2*BDDSizek-1，那么就可以构造出相对紧凑的BDD。

(2)

(3)

Table 2 Relationship between Wth and |Fk|表2 第k层BDD宽度和边界集长度|Fk|之间的关系

对于如图2的K4网络，令边排序Order1= e1≤e2≤e3≤e4≤e5≤e6，Order2= e1≤e2≤e5≤e6≤e4≤e3，得表3，表中“|BDDk|”表示第k层实际的BDD宽度(数目)。由于边排序Order2较好地控制了各层边界集Fk的大小，也就较好地控制了实际BDD宽度，最终得到较为紧凑的完整BDD。

Table 3 Relationship between |BDDk| and |Fk|表3 实际BDD宽度与|Fk|之间的关系

3 高性能边排序策略

基于第2节分析结果，设计边排序策略，记为MDFS(Minimum Degree First Search)。其核心思想为在排序过程中严格控制各层边界集大小。具体措施为优先排序“两端点都在边界集BS中、且其中一点的度在BS中最小”的未排序边；如果不存在这样的边，则选择“一端关联于边界集中最小度节点，另一端取V-BS中度最小”的未排序边排序，其中的度指的是关联于某节点的未排序边数目。具体算法如下所示：

算法2MDFS算法

1.Initialize the boundary setBSand visited-edge setVES;

2.Set the ordering starting vertexu(e.g.u=G.source)and insertuintoBS;

3.Calculate the degree of vertices inG(V,E,K);

4.for(edgeNum=1 to |E|)

5. Find the vertexuinBSsuch thatdegree(u) is the minimum.

6. Find the vertextvinBSsuch thate(u,v)∈E-VESand degree(v) is the minimum;

7. if(visn’t founded)

8. Find the vertextvinV-BSsuch thate(u,v)∈E-VESand degree(v) is the minimum;

9. end if

10. Order the edgee(u,v), markVES(u,v),degree(u)--, degree(v)--;

11. if(degree(v)>0 &&vdosn’t exist inBS)

12.BS.offer(v);

13. end if

14.count=BS.size();

15. for(k=0 tocount)/*delete the vertices which are inBS*/

16. tmp=BS.poll() ;

17. if(degree[tmp]>0)

18.BS.offer(tmp);

19. end if

20. end for

21.end for

如图3a所示3×3 Square Lattice网络，设置排序初始点为标号为“0”的节点，排序过程如表4所示，排序结果如图3b所示。表4中“Cand_Vertices”表示候选节点，“Select_u”表示选中的第1节点u，“Nexts(u)”栏中列出所有备选节点，Select_v表示选中的第2节点v，“E(u,v)/E(u,v)_Num”栏列出被排序的边〈u,v〉以及边的排序序号；表中符号“nd”表示关联于节点n的未排序边数目为d。图3c为排序初始点为“4”的排序结果。

4 策略性能分析和比较

为了更好地比较研究，首先在4×4 SquareLattice规则网络中实验：随机设定{s,t}点对，选择常用的DFS和BFS边排序策略作为比较对象，生成等价BDD，计算二端网络可靠度，记录可靠度值、边界长度BSL、BDD尺度(节点数目)、生成BDD的运行时间等指标数据，比较MDFS、DFS和BFS策略的性能优劣，实验结果如表5所示。表5中“Relib”表示可靠度值，“Size”表示BDD尺度，“Time”表示生成BDD的运行时间，“BSL”表示边界长度。设网络节点完好且边失效独立，失效概率取0.1。

Figure 3 Network 3 and the result of MDFS图3 网络3和边排序结果

StepCand_VerticesSelect_uNexts(u)Select_vE(u,v)/E(u,v)_Num102,22,62,82013,331<0,1>/1201,120333<0,3>/2312,32122,442<1,2>/3411,21,32,441444<1,4>/4521,32,433434<3,4>/5621,31,423626<3,6>/6721,42,612535<2,5>/7842,52,614525<4,5>/8941,51,614737<4,7>/91051,61,726727<6,7>/101151,715828<5,8>/111271,817818<7,8>/12

汇总表5中数据得图4，图4表明BDD尺度和运行时间随着边界长度的增大而增大，当边界长度取最大值时如{1,4}点对，对应的BDD尺度和运行时间都最大。当边界长度波动较大时，BDD尺度和运行时间跟着急剧波动。对于MDFS策略，在不同{s,t}点对时，指标数据BDD尺度与运行时间，不仅数值较小，而且相对稳定,如图4a和图4b所示，表现出良好的性能。

进一步地，在Torus Lattice、DeBruijn和Nearest-Neighbor等其他规则网络中继续如上实验，得实验结果如表6、表7、表8和图5、图6、图7所示。

如表6和图5所示，BFS和MDFS策略得到相同的边界长度(BSL=173)，BDD尺度和运行时间接近，BFS策略性能占优。DFS策略对应的边界长度值较大但基本稳定，BDD尺度和运行时间数值大且波动明显。

在DeBruijn网络中，BDD尺度和运行时间与边界长度有相似的变化趋势。整体而言MDFS策略因拥有较小BSL而具有明显的性能优势。对于点对{4,10}，BFS下有最小BSL，进而BDD尺度和运行时间较小，体现高性能边排序策略的设计思想。

Table 5 Performance comparison between three strategies in 4×4 Square Lattice表5 4×4 Square Lattice中三种策略性能比较

Figure 4 Comparison of BDD Size, time and BSL in 4×4 Square Lattice图4 Square Lattice network(4×4) 中指标数据比较

Figure 5 Comparison of BDD Size, time and BSL in 4×4 Torus Lattice图5 Torus Lattice network(4×4) 中指标数据比较

Figure 6 Comparison of BDD Size, time and BSL in DeBruijn(order= 4)图6 DeBruijn network(Order=4) 中指标数据比较

Figure 7 Comparison of BDD Size, time and BSL in Nearest-Neighbor network(14 Nodes and 6 Degree)图7 Nearest-Neighbor network(14 Nodes and 6 Degree) 中指标数据比较

{s,t}RelibDFSSize Time BSLBFSSize Time BSLMDFSSize Time BSL{0,3}0.999794360533670215128251452173164061639173{0,15}0.99979266388615221592851312173116991436173{1,2}0.999794360533669215128251467173164061654173{1,10}0.999792445074263215124951468173145551623173{2,8}0.999792714896823215127001499173149081624173{3,6}0.99979251602509021597391342173116411452173{4,5}0.999794297653201214131671498173165851655173{7,9}0.999792663066011214125041467173144281608173{8,11}0.999794354873029207124991436173150831593173{9,14}0.99979248061404420795041327173118241436173{10,12}0.999792518674357207124541483173145551607173{11,15}0.999794338633139207118621421173156231623173

Table 7 Performance comparison among three strategies in DeBruijn(order=4)表7 DeBruijn network三种策略性能比较

Table 8 Performance comparison among three strategies in Nearest-Neighbor network表8 Nearest-Neighbor Network三种策略性能比较

分析不同边排序策略在不同规则网络中的性能表现，在Square Lattice、DeBruijn和Neartest-Neighbor网中，MDFS性能优势明显，在Torus Lattice网络中，性能稍逊于BFS。整体而言，规则网络中MDFS策略性能优于DFS和BFS。分析指标数据间的关系得出结论：

结论1BDD尺度随着边界长度增大而增大，保持良好的正相关性。

为验证MDFS边排序策略的适用性，选择更多网络类型[2,3,5]进行比较研究，实验结果如表9所示，表中“*”表示未获得结果数据。

由表9所示，当网络结构简单且规模小时(如网络#1～#10，#15)，三种策略性能接近，DFS稍差，MDFS稍优；当网络结构简单且规模较大时(如网络#26，#28，#30)，DFS策略无法得到实验结果，MDFS和BFS得到实验结果且性能接近；网络结构稍显复杂且规模稍大时(如网络#18～#19，#22，net2-6，net2-8)，DFS策略性能差一个数量级，比较BFS和MDFS，MDFS占优。可见，比较DFS和BFS策略，性能占优情况视不同网络结构和不同网络规模而定，有时BFS占优如网络#18和#19，有时DFS占优如网络#3，#11～#12，#16-17；对于MDFS策略，面对不同网络结构和不同网络规模，性能上整体而言优于DFS和BFS，表现出良好的适应性。

5 结束语

本文从边界集思想入手，在具体分析基于边界集的BDD构建算法BDD-BS的基础上，将各层边界集长度|Fk|(k=1,2,3,…,|E|)作为启发性边排序影响因素，提出最小度优先的边排序方法MDFS，并在规则网络和复杂网络中完成了与经典策略DFS和BFS的比较实验，得出重要结论——BDD尺度与边界长度BSL具有正相关性。大量实验结果表明，MDFS较DFS和BFS策略面对复杂多变的网络时，具有更高性能和更强的适用性。下一步研究工作：

(1)在小世界和无标度网络中验证相关结论；

(2)进一步完善MDFS边排序策略。

[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 ofk-terminal network reliability[J]. IEEE Transactions on Reliability, 2002, R-51(4):443-451.

Table 9 Performance comparison among three strategies in benchmark networks表9 Benchmark networks 三种策略性能比较

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

PANZhu-sheng,born in 1977,MS,lecturer,his research interest includes trusted computing.

莫毓昌(1980),男,浙江湖州人，博士，副教授，研究方向为可信计算。E-mail:myc@zjnu.cn

MOYu-chang,born in 1980,PhD,associate professor,his research interest includes trusted computing.

Anovelheuristicedgeorderingstrategyanditsperformanceanalysis

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)

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.

network reliability;binary decision diagram;boundary set;edge ordering.

1007-130X(2014)11-2119-09

2014-06-15;

：2014-08-13

国家自然科学基金资助项目(61272130);浙江省自然科学基金资助项目(Y1100689);浙江省重中之重学科开放课题资助项目(ZSDZZZZXK24);浙江省教育厅项目(Y201328072)

TB114

：A

10.3969/j.issn.1007-130X.2014.11.011