潘竹生,莫毓昌,鐘發(fā)榮,劉 軒,伍 歡

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江 金華 321004)

一種新的啟發(fā)式邊排序策略及其性能分析*

潘竹生,莫毓昌,鐘發(fā)榮,劉 軒,伍 歡

(浙江師范大學(xué)數(shù)理與信息工程學(xué)院,浙江 金華 321004)

網(wǎng)絡(luò)可靠度BDD分析方法的計(jì)算復(fù)雜度與BDD尺度線性相關(guān)，而B(niǎo)DD尺度嚴(yán)重依賴邊排序質(zhì)量。由于求解最優(yōu)邊排序是一個(gè)NP問(wèn)題，在實(shí)際應(yīng)用中，通常采用啟發(fā)式邊排序策略如BFS(Breadth-First-Search)和DFS(Depth-First-Search)。針對(duì)邊排序問(wèn)題，從分析基于邊界集(Boundary Set)的BDD構(gòu)建方法BDD-BS出發(fā)，將邊界集思想應(yīng)用于邊排序過(guò)程，提出了一種新的啟發(fā)式邊排序策略。性能分析和大量實(shí)驗(yàn)表明，新設(shè)計(jì)的邊排序策略性能優(yōu)于經(jīng)典的DFS和BFS策略，該結(jié)果為網(wǎng)絡(luò)可靠度BDD分析方法在大規(guī)模網(wǎng)絡(luò)中的應(yīng)用拓展了新的空間。

網(wǎng)絡(luò)可靠度;二叉決策圖;邊界集;邊排序

1 引言

網(wǎng)絡(luò)可靠度二叉決策圖BDD(Binary Decide Diagram)分析方法包括邊排序、等價(jià)BDD生成和指標(biāo)數(shù)據(jù)計(jì)算三個(gè)基本過(guò)程。其中，等價(jià)BDD生成是關(guān)鍵，生成的BDD越小，即BDD尺度(節(jié)點(diǎn)數(shù)目)越小，可靠度分析方法的性能就越好。Kuo S-Y等人[1～3]利用邊擴(kuò)展EP(Edge Expansion)技術(shù)來(lái)有效識(shí)別同構(gòu)子網(wǎng)，提出自底向上的緊湊BDD構(gòu)建方法；Hardy G等人[4,5]利用邊界分區(qū)(Partition-BS)有效識(shí)別同構(gòu)子網(wǎng)，提出自頂向下的緊湊BDD構(gòu)建方法，這兩種方法在構(gòu)建過(guò)程中存在冗余；Pan Zhu-sheng等人[6]通過(guò)識(shí)別冗余子網(wǎng)，消除了冗余BDD，進(jìn)一步改進(jìn)了性能。然而，BDD的緊湊程度更大程度上依賴邊排序質(zhì)量[7]，不同質(zhì)量的邊排序結(jié)果導(dǎo)致BDD尺度跨越幾個(gè)數(shù)量級(jí)[8]，高質(zhì)量的邊排序指導(dǎo)生成最為緊湊的BDD。

然而，求解最優(yōu)邊排序已被證明是一個(gè)NP完全問(wèn)題[9]，在實(shí)際的網(wǎng)絡(luò)可靠性分析中，大多采用啟發(fā)性策略[1～6,10,11]，常見(jiàn)的有廣度優(yōu)先搜索BFS(Breadth-First-Search)和深度優(yōu)先搜索DFS(Depth-First-Search)。那么是否存在更優(yōu)的啟發(fā)式邊排序策略呢？

本文嘗試從邊界集BS(Boundary Set)入手，分析基于邊界集的BDD構(gòu)建方法(BDD-BS)特征，提煉啟發(fā)性特征數(shù)據(jù)，用于高性能邊排序策略設(shè)計(jì)，完成新策略與DFS和BFS策略的性能比較，得出實(shí)驗(yàn)結(jié)論。

2 邊界集BS和BDD-BS算法

2.1 邊界集BS

定義1三元組G=(V,E,K)稱為一個(gè)K端網(wǎng)絡(luò)，其中：

(1)V={V1,V2, …,Vn}，稱為頂點(diǎn)集；

(2)E?V×V，稱為邊集;

(3)K?V，稱為K點(diǎn)集。

為了便于描述，對(duì)于E中的點(diǎn)對(duì)〈a,b〉,a,b∈V通常賦予另一個(gè)名稱ei。

圖1中的K端網(wǎng)絡(luò)G對(duì)應(yīng)的三元組為({0，1，2，3，4，5，6}，{e1，e2，e3，e4，e5，e6，e7，e8，e9，e10}，{0，3，6})。

定義2三元組G的邊排序Order是E至整數(shù)集合{1,2,…,|E|}上的一一對(duì)應(yīng)函數(shù)，Order:E→{1,2,…,|E|}。

根據(jù)定義可知，G的邊排序可以有|E|!種不同的可能。通常獲得邊排序的方法有廣度優(yōu)先遍歷BFS和深度優(yōu)先遍歷DFS。

圖1中的K端網(wǎng)絡(luò)G，以節(jié)點(diǎn)”0”為排序起點(diǎn)，則對(duì)應(yīng)的一種廣度優(yōu)先排序Order為：〈e1，e2，e3，e4，e5，e6，e7，e8，e9，e10〉。

圖1中的K端網(wǎng)絡(luò)G，以節(jié)點(diǎn)”0”為排序起點(diǎn)，則對(duì)應(yīng)的一種深度優(yōu)先排序Order為：〈e1，e4，e8，e6，e2，e5，e3，e7，e10，e9〉。

定義3給定K端網(wǎng)絡(luò)G=(V,E,K)，在邊排序Order下得到邊序e1≤e2≤…≤e|E|，則定義第k(0≤k≤|E|)層邊界集Fk為：

圖1所示網(wǎng)絡(luò)，約定邊排序?yàn)閑1

Figure 1 Network 1 and edge ordering圖1 網(wǎng)絡(luò)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端網(wǎng)絡(luò)G =(V, E, K)和邊排序Order，定義邊界長(zhǎng)度BSL為：

圖1所示網(wǎng)絡(luò)，約定邊排序?yàn)閑1

2.2 BDD-BS算法

邊界集BS首先由CarlierJ和LucetC[12]應(yīng)用到網(wǎng)絡(luò)可靠性研究中。2007年HardyG等人[5]利用邊界集分區(qū)來(lái)標(biāo)識(shí)網(wǎng)絡(luò)特征，提出了自頂向下的BDD構(gòu)建算法(記為BDD-BS)，用來(lái)高效計(jì)算全端網(wǎng)絡(luò)可靠性和K端網(wǎng)絡(luò)可靠性，具體算法如算法1所示。圖2為全連通網(wǎng)絡(luò)K4的等價(jià)BDD構(gòu)建過(guò)程，設(shè)邊序?yàn)閑1≤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是參數(shù)*/

7.elsePart=partitionGen(nodei,ekis down)/*ekis down表示ek不連通，ek是參數(shù)*/

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網(wǎng)絡(luò)BDD構(gòu)建過(guò)程

如圖2所示，記第k-1層BDD節(jié)點(diǎn)數(shù)目為BDDSizek-1，當(dāng)?shù)趉層不出現(xiàn)共享子網(wǎng)或終端BDD節(jié)點(diǎn)如“0”和“1”，則第k層節(jié)點(diǎn)數(shù)目BDDSizek等于2*BDDSizek-1，如L2和L3；當(dāng)出現(xiàn)共享子網(wǎng)或終端BDD節(jié)點(diǎn)時(shí)，BDDSizek小于2*BDDSizek-1，如L5。所以，一般情況下，BDD節(jié)點(diǎn)數(shù)目滿足如式(1)所示的遞推關(guān)系。由式(1)可得，最壞情況下BDDSizek= 2k。

BDDSizek≤2*BDDSizek-1

(1)

文獻(xiàn)[5，12]指出，第k層BDD寬度Wth與第k層邊界集Fk大小有關(guān)，記為Wth(|Fk|)，滿足關(guān)系式(2)，且BDD緊湊程度取決于各層BDD寬度Wth(|Fk|)。如果Wth(|Fk|)小于2*BDDSizek-1，那么第k層必將出現(xiàn)共享BDD，且Wth(|Fk|)越小，共享的BDD節(jié)點(diǎn)數(shù)目越多。另外，邊界集長(zhǎng)度|Fk|滿足關(guān)系式(3)。由式(1)和式(3)得表2。表中“E-Num”表示邊數(shù)，“BDDSize”表示BDD節(jié)點(diǎn)數(shù)目，“Wth”表示不考慮K點(diǎn)時(shí)BDD的寬度，“Wth-K”表示考慮K點(diǎn)影響時(shí)的BDD寬度。很明顯BDD寬度隨|Fk|呈指數(shù)級(jí)快速增長(zhǎng)，且增長(zhǎng)速度遠(yuǎn)大于最壞情況下BDD節(jié)點(diǎn)數(shù)目的增長(zhǎng)速度。當(dāng)|Fk|≥10時(shí)，Wth≥115975，若k= 9，實(shí)際BDD寬度不超過(guò)29=512。但是，如果此時(shí)|Fk|=5，查表2得Wth-K=454，即Wth(|Fk|)= 454≤29。由此可見(jiàn)，只要每層|Fk|取得足夠小，滿足Wth(|Fk|)≤2*BDDSizek-1，那么就可以構(gòu)造出相對(duì)緊湊的BDD。

(2)

(3)

Table 2 Relationship between Wth and |Fk|表2 第k層BDD寬度和邊界集長(zhǎng)度|Fk|之間的關(guān)系

對(duì)于如圖2的K4網(wǎng)絡(luò)，令邊排序Order1= e1≤e2≤e3≤e4≤e5≤e6，Order2= e1≤e2≤e5≤e6≤e4≤e3，得表3，表中“|BDDk|”表示第k層實(shí)際的BDD寬度(數(shù)目)。由于邊排序Order2較好地控制了各層邊界集Fk的大小，也就較好地控制了實(shí)際BDD寬度，最終得到較為緊湊的完整BDD。

Table 3 Relationship between |BDDk| and |Fk|表3 實(shí)際BDD寬度與|Fk|之間的關(guān)系

3 高性能邊排序策略

基于第2節(jié)分析結(jié)果，設(shè)計(jì)邊排序策略，記為MDFS(Minimum Degree First Search)。其核心思想為在排序過(guò)程中嚴(yán)格控制各層邊界集大小。具體措施為優(yōu)先排序“兩端點(diǎn)都在邊界集BS中、且其中一點(diǎn)的度在BS中最小”的未排序邊；如果不存在這樣的邊，則選擇“一端關(guān)聯(lián)于邊界集中最小度節(jié)點(diǎn)，另一端取V-BS中度最小”的未排序邊排序，其中的度指的是關(guān)聯(lián)于某節(jié)點(diǎn)的未排序邊數(shù)目。具體算法如下所示：

算法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網(wǎng)絡(luò)，設(shè)置排序初始點(diǎn)為標(biāo)號(hào)為“0”的節(jié)點(diǎn)，排序過(guò)程如表4所示，排序結(jié)果如圖3b所示。表4中“Cand_Vertices”表示候選節(jié)點(diǎn)，“Select_u”表示選中的第1節(jié)點(diǎn)u，“Nexts(u)”欄中列出所有備選節(jié)點(diǎn)，Select_v表示選中的第2節(jié)點(diǎn)v，“E(u,v)/E(u,v)_Num”欄列出被排序的邊〈u,v〉以及邊的排序序號(hào)；表中符號(hào)“nd”表示關(guān)聯(lián)于節(jié)點(diǎn)n的未排序邊數(shù)目為d。圖3c為排序初始點(diǎn)為“4”的排序結(jié)果。

4 策略性能分析和比較

為了更好地比較研究，首先在4×4 SquareLattice規(guī)則網(wǎng)絡(luò)中實(shí)驗(yàn)：隨機(jī)設(shè)定{s,t}點(diǎn)對(duì)，選擇常用的DFS和BFS邊排序策略作為比較對(duì)象，生成等價(jià)BDD，計(jì)算二端網(wǎng)絡(luò)可靠度，記錄可靠度值、邊界長(zhǎng)度BSL、BDD尺度(節(jié)點(diǎn)數(shù)目)、生成BDD的運(yùn)行時(shí)間等指標(biāo)數(shù)據(jù)，比較MDFS、DFS和BFS策略的性能優(yōu)劣，實(shí)驗(yàn)結(jié)果如表5所示。表5中“Relib”表示可靠度值，“Size”表示BDD尺度，“Time”表示生成BDD的運(yùn)行時(shí)間，“BSL”表示邊界長(zhǎng)度。設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)完好且邊失效獨(dú)立，失效概率取0.1。

Figure 3 Network 3 and the result of MDFS圖3 網(wǎng)絡(luò)3和邊排序結(jié)果

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中數(shù)據(jù)得圖4，圖4表明BDD尺度和運(yùn)行時(shí)間隨著邊界長(zhǎng)度的增大而增大，當(dāng)邊界長(zhǎng)度取最大值時(shí)如{1,4}點(diǎn)對(duì)，對(duì)應(yīng)的BDD尺度和運(yùn)行時(shí)間都最大。當(dāng)邊界長(zhǎng)度波動(dòng)較大時(shí)，BDD尺度和運(yùn)行時(shí)間跟著急劇波動(dòng)。對(duì)于MDFS策略，在不同{s,t}點(diǎn)對(duì)時(shí)，指標(biāo)數(shù)據(jù)BDD尺度與運(yùn)行時(shí)間，不僅數(shù)值較小，而且相對(duì)穩(wěn)定,如圖4a和圖4b所示，表現(xiàn)出良好的性能。

進(jìn)一步地，在Torus Lattice、DeBruijn和Nearest-Neighbor等其他規(guī)則網(wǎng)絡(luò)中繼續(xù)如上實(shí)驗(yàn)，得實(shí)驗(yàn)結(jié)果如表6、表7、表8和圖5、圖6、圖7所示。

如表6和圖5所示，BFS和MDFS策略得到相同的邊界長(zhǎng)度(BSL=173)，BDD尺度和運(yùn)行時(shí)間接近，BFS策略性能占優(yōu)。DFS策略對(duì)應(yīng)的邊界長(zhǎng)度值較大但基本穩(wěn)定，BDD尺度和運(yùn)行時(shí)間數(shù)值大且波動(dòng)明顯。

在DeBruijn網(wǎng)絡(luò)中，BDD尺度和運(yùn)行時(shí)間與邊界長(zhǎng)度有相似的變化趨勢(shì)。整體而言MDFS策略因擁有較小BSL而具有明顯的性能優(yōu)勢(shì)。對(duì)于點(diǎn)對(duì){4,10}，BFS下有最小BSL，進(jìn)而B(niǎo)DD尺度和運(yùn)行時(shí)間較小，體現(xiàn)高性能邊排序策略的設(shè)計(jì)思想。

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) 中指標(biāo)數(shù)據(jù)比較

Figure 5 Comparison of BDD Size, time and BSL in 4×4 Torus Lattice圖5 Torus Lattice network(4×4) 中指標(biāo)數(shù)據(jù)比較

Figure 6 Comparison of BDD Size, time and BSL in DeBruijn(order= 4)圖6 DeBruijn network(Order=4) 中指標(biāo)數(shù)據(jù)比較

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) 中指標(biāo)數(shù)據(jù)比較

{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三種策略性能比較

分析不同邊排序策略在不同規(guī)則網(wǎng)絡(luò)中的性能表現(xiàn)，在Square Lattice、DeBruijn和Neartest-Neighbor網(wǎng)中，MDFS性能優(yōu)勢(shì)明顯，在Torus Lattice網(wǎng)絡(luò)中，性能稍遜于BFS。整體而言，規(guī)則網(wǎng)絡(luò)中MDFS策略性能優(yōu)于DFS和BFS。分析指標(biāo)數(shù)據(jù)間的關(guān)系得出結(jié)論：

結(jié)論1BDD尺度隨著邊界長(zhǎng)度增大而增大，保持良好的正相關(guān)性。

為驗(yàn)證MDFS邊排序策略的適用性，選擇更多網(wǎng)絡(luò)類型[2,3,5]進(jìn)行比較研究，實(shí)驗(yàn)結(jié)果如表9所示，表中“*”表示未獲得結(jié)果數(shù)據(jù)。

由表9所示，當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單且規(guī)模小時(shí)(如網(wǎng)絡(luò)#1～#10，#15)，三種策略性能接近，DFS稍差，MDFS稍優(yōu)；當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)簡(jiǎn)單且規(guī)模較大時(shí)(如網(wǎng)絡(luò)#26，#28，#30)，DFS策略無(wú)法得到實(shí)驗(yàn)結(jié)果，MDFS和BFS得到實(shí)驗(yàn)結(jié)果且性能接近；網(wǎng)絡(luò)結(jié)構(gòu)稍顯復(fù)雜且規(guī)模稍大時(shí)(如網(wǎng)絡(luò)#18～#19，#22，net2-6，net2-8)，DFS策略性能差一個(gè)數(shù)量級(jí)，比較BFS和MDFS，MDFS占優(yōu)?？梢?jiàn)，比較DFS和BFS策略，性能占優(yōu)情況視不同網(wǎng)絡(luò)結(jié)構(gòu)和不同網(wǎng)絡(luò)規(guī)模而定，有時(shí)BFS占優(yōu)如網(wǎng)絡(luò)#18和#19，有時(shí)DFS占優(yōu)如網(wǎng)絡(luò)#3，#11～#12，#16-17；對(duì)于MDFS策略，面對(duì)不同網(wǎng)絡(luò)結(jié)構(gòu)和不同網(wǎng)絡(luò)規(guī)模，性能上整體而言優(yōu)于DFS和BFS，表現(xiàn)出良好的適應(yīng)性。

5 結(jié)束語(yǔ)

本文從邊界集思想入手，在具體分析基于邊界集的BDD構(gòu)建算法BDD-BS的基礎(chǔ)上，將各層邊界集長(zhǎng)度|Fk|(k=1,2,3,…,|E|)作為啟發(fā)性邊排序影響因素，提出最小度優(yōu)先的邊排序方法MDFS，并在規(guī)則網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)中完成了與經(jīng)典策略DFS和BFS的比較實(shí)驗(yàn)，得出重要結(jié)論——BDD尺度與邊界長(zhǎng)度BSL具有正相關(guān)性。大量實(shí)驗(yàn)結(jié)果表明，MDFS較DFS和BFS策略面對(duì)復(fù)雜多變的網(wǎng)絡(luò)時(shí)，具有更高性能和更強(qiáng)的適用性。下一步研究工作：

(1)在小世界和無(wú)標(biāo)度網(wǎng)絡(luò)中驗(yàn)證相關(guān)結(jié)論；

(2)進(jìn)一步完善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.

附中文參考文獻(xiàn)：

[6] 潘竹生，莫毓昌，鐘發(fā)榮，等.網(wǎng)絡(luò)可靠度BDD分析算法的性能改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，2012,34(9):26-32.

[11] 潘竹生，莫毓昌，趙建民.網(wǎng)絡(luò)可靠度BDD分析中2種邊排序策略的性能比較[J].浙江師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013，36(1):88-95.

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

莫毓昌(1980),男,浙江湖州人，博士，副教授，研究方向?yàn)榭尚庞?jì)算。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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272130);浙江省自然科學(xué)基金資助項(xiàng)目(Y1100689);浙江省重中之重學(xué)科開(kāi)放課題資助項(xiàng)目(ZSDZZZZXK24);浙江省教育廳項(xiàng)目(Y201328072)

TB114

：A

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

潘竹生(1977),男,浙江金華人，碩士，講師，研究方向?yàn)榭尚庞?jì)算。E-mail:pan@zjnu.cn

通信地址：浙江省金華市迎賓大道688號(hào)浙江師范大學(xué)103#信箱

Address:Mailbox 103#,Zhejiang Normal University,688 Yingbin Avenue,Jinhua 321004,Zhejiang,P.R.China