網絡可靠性分析中自頂向下的二叉決策圖構造研究

曾令國,潘竹生,莫毓昌

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

網絡可靠性分析中自頂向下的二叉決策圖構造研究

曾令國,潘竹生,莫毓昌

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

采用邊界分區標識網絡的思想,實現基于邊界分區的自頂向下K端可靠度二叉決策圖(BDD)構建算法。針對BDD構建過程中存在的節點冗余問題,提出無效邊冗余消除和K點非連通冗余消除2種處理技術。在規則網絡和實際工程中的實驗結果表明,利用無效邊冗余消除和K點非連通消除技術后的BDD改進算法,在不影響算法時間性能的情況下,可大幅縮減BDD尺度,提升K端網絡可靠度分析算法性能,適用于大規模的網絡可靠度分析。

網絡可靠度;二叉決策圖;邊界集;邊收縮;冗余

1 概述

網絡技術便捷地實現了資源共享和信息交互,人們在享受這些便捷服務的同時,逐步意識到了網絡可靠性的重要性,諸如通信網、互聯網、電力網,更甚者如物聯網、自來水供水網絡等工程網絡一旦出現故障,會影響到日常生活甚至讓工作耽誤,業務運作癱瘓。所以,對于網絡可靠度的分析成為一個倍受關注的熱點,建立高效的網絡可靠性分析方法,確保網絡可靠運行是現代工程網絡研發和管理領域亟需解決的迫切問題[1]。

基于最小路集(或割集)[2]適用于小規模網絡;文獻[3]首先將分解理論用于可靠度計算中,文獻[4]證明了當連接獨立失效時,通過旋轉和串并聯概率消減,能生成分解算法的優化二叉結構,文獻[5]表明結合消減技術如多邊形鏈消減和串并聯消減,分解算法能取得很好的性能,適用中等規模的網絡,但該類算法存在無法高效操作大規模布爾函數和無法避免網絡分解過程的同構冗余計算等問題,仍無法滿足更大規模的網絡可靠度計算需求;而文獻[6]提出的以二叉決策圖(Binary Decision Diagram,BDD)為基礎的可靠度分析方法,即先用布爾路徑函數等價刻畫網絡結構,再基于等價BDD分析路徑函數得到網絡可靠度,該方法利用了BDD操作大規模布爾函數的高效性性能上[7]。文獻[8]提出了自底向上的二端可靠度和K端可靠度BDD分析算法;文獻[9]利用邊界集基于邊收縮和邊刪除,提出了自頂向下的全端可靠度和K端可靠度BDD分析算法,并證明了這是到目前為止最為有效的BDD分析算法,但該算法沒有很好地處理BDD節點的冗余問題,很大程度上影響網絡可靠度分析性能。文獻[10]采用邊擴展技術識別了同構子圖,消除了可靠度計算中的同構冗余。文獻[9]消除了冗余節點型無效擴展路徑和ST非連通型無效擴展路徑,使整體性能提升90%以上。

本文采用邊界分區Partition標識網絡的思想,提出基于邊界分區的自頂向下K端可靠度BDD構建算法。針對BDD構建過程中存在的節點冗余問題,給出無效邊冗余消除和K點非連通冗余消除2種處理技術用于改進算法。

2 自頂向下的BDD構建

自頂向下BDD構建基于邊收縮和邊刪除的網絡分解,分解過程類似于構建一顆二叉樹。為了提升算法性能,自頂向下算法利用Partition標識網絡并用Hash實現子網共享。具體過程為:

(1)為原始網絡G建立BDD節點,構建目標BDD的第1層節點,即根節點。

(2)從邊序中按序取邊ek。

(3)依次取上層BDD節點作為新根,并進行邊收縮(生成邊界分區ThenPart)和邊刪除(生成邊界分區ElsePart)操作。分析邊界分區 Partition特征,合理裁剪后為新根建立相應的左右分支。

(4)重復步驟(2)～步驟(3),直到BDD構建完成。BDD生成過程算法描述如下。

算法1自頂向下BDD生成算法

在BDD自頂向下構建過程中,可能出現K點一定連通或者一定不連通等狀態。這些狀態可在Partition的Append操作和Reduce操作過程中發現并識別。為了提升算法性能,當出現確定狀態(連通或不連通)時,應及時裁剪并終止向下擴展。裁剪規則為:

(1)邊界分區Partition Reduce操作時,如果出現帶“?”空block且未處理的K點數目＞0,則至少有1個K點被孤立,此時標記不連通,終止向下擴展。

(2)邊界分區 Partition生成后,如果帶“?”block數目為1且未處理的K點數目==0,則所有K點在同一block中或不在block中的K點都有邊連通于該block,此時標記連通,終止向下擴展。

3 性能改進

3.1 問題分析

觀察圖1的BDD,可以發現存在大量冗余BDD節點,冗余 BDD節點存在的原因:(1)無效邊; (2)K點非連通。為了更好地說明這2種情況,設計示例網絡如圖2所示,帶陰影節點為K點。

對這2種情況的詳細說明如下:

(1)無效邊,對某邊分邊正常和邊失效2種情況進行邊界分區生成,若得到相同邊界分區,則該邊為無效邊。如圖2(a)中的邊2和邊3。無效邊的存在將導致大量冗余BDD節點生成,如圖3(a)中的節點B2,B3和B4為冗余節點,占BDD節點總數的60%,嚴重影響BDD算法的分析性能。

(2)K點非連通,所謂K點非連通指的是K點分布于不同的連通分量中,如圖3(b)所示,2個K點“0”和“5”分布于不同連通分量。對網絡6-1(b)約定邊序e1＜e2＜e3＜e4＜e5＜e6進行自頂向下BDD生成,結果如圖3(b)所示。圖中構建了4層BDD,生成了8個BDD節點,實際上在最高層構建B1節點時,2個K點“0”和“5”顯然不能連通,不再需要向下擴展,從而可以避免冗余 BDD節點 Bi(i=1, 2,…,8)的生成。

圖1 基于邊收縮和邊刪除的自頂向下網絡分解以及各層Partition

圖2 示例網絡

圖3 自頂向下BDD生成

3.2 冗余消除

冗余消除分2類:無效邊冗余消除和K點非連通消除。

(1)無效邊冗余消除,其基本思想為:分析當前part,若邊ek+1的2個端點u和v在part的同一block中,則邊ek+1無效;如果其中有一端點在block中但不在新的邊界分區中,|block|=1且該block不帶“?”,則邊ek+1同樣無效,刪除無效邊的具體算法如下。

算法2無效邊冗余消除算法

圖2(a)所示網絡消除無效邊e2和e3后,導致原本有效邊e1變成無效邊,進一步冗余消除后生成的BDD如圖3(a)中虛線框所示,它只有一個BDD節點B5。

(2)K點非連通消除,根據定義非連通冗余消除問題轉化為所有K點是否均可達問題。如果可達,則繼續往下生成,否則標記不可達,終止往下生成,算法實現如下。

算法3K點是否可達算法

圖2(b)所示網絡由于K點不可達,經過非連通消除,直接返回不連通,不再往下生成BDD。

3.3 實驗結果

為了更好地說明改進算法的性能,本文選用文獻[9,11]中的基準網絡,采用相同的廣度優先邊排序策略和邊失效概率,測試網絡可靠度Relib、算法運行時間time和BDD節點數目等指標數據。實驗結果如表1所示,其中,Algo_Kuo和Algo_Hardy列數據來自文獻[12],Algo_Original表示本文算法未帶冗余消除時實驗數據,InvalidEdgeE表示無效邊消除后的實驗數據,KNodeUnConE表示無效邊和K點非連通都消除后的實驗數據。

表1 二端可靠度實驗結果

分析比較表1中的數據,改進算法增加2種冗余消除后,時間消耗增加不多,但BDD數目縮減32%以上,經過無效邊消除,BDD數目和Kuo算法得到的實驗結果相同;相比較Hardy算法實驗結果,改進算法BDD數目減少25%以上,性能明顯提升。

為了進一步考察2種冗余消除的性能,在N× N型網絡(即每行每列都有n個節點構成的網絡)中,隨機選擇ST點對并計算其二端可靠度,實驗結果如表2所示。其中,S′為廣度優先邊排序的起點。綜合分析表1和表2,得到匯總數據如表3所示。其中,time1和BDD1分別表示無效邊冗余消除所增加的時間百分比和縮減的BDD節點數百分比;time2和BDD2分別表示在無效邊冗余消除基礎上,K點非連通冗余消除所增加的時間百分比和縮減的BDD節點數百分比。由表3得,無效邊冗余普遍存在,經過消除時間消耗增加10%左右,BDD數目縮減28%以上;K點非連通冗余的存在性與網絡結構和排序策略有關,在特定條件下如表3中6×6和7×7網絡,K點非連通冗余消除能大幅縮減BDD數目以提升算法性能。

表2 N×N型網絡二端可靠度實驗結果

表3 網絡可靠度性能指標數據

表4和表5為改進算法在K=|V|/2,K=|V|時的實驗結果,其中,Algo_Improve列為2種冗余消除后的實驗數據。

綜合表1、表4和表5,取不同K值(K=2,|V|/ 2,|V|),考察消耗時間,Kuo算法在網絡規模較大時迅速增加,Hardy算法和改進算法相對穩定;考察生成的BDD節點數目,Hardy算法普遍大于Kuo算法和改進算法,而后兩者基本相同。

表4 K端可靠度實驗結果(K=|V|/2)

表5 全端可靠度實驗結果

綜合以上實驗結果,在K端可靠度計算中,Hardy算法優于Kuo算法,改進算法優于Hardy算法。隨著無效邊和K點非連通冗余的消除,改進算法能生成更簡BDD,更適用大規模網絡的可靠度分析。

4 案例應用分析

如圖4所示為土耳其布爾薩市的配水網網絡模型[13]。

圖4 土耳其布爾薩市配水網絡

圖4中共有13個節點和18條邊。假設所有節點都正常工作,且邊失效相互獨立(假設失效概率為0.1),采用BFS邊排序策略,用改進的BDD方法來計算該網絡的相關可靠度。

實驗過程:首先隨機選擇ST點對,記錄BDD尺度和BDD生成時間,計算二端可靠度值;其次隨機選擇K個節點,記錄BDD尺度和BDD生成時間,計算K端可靠度值。實驗按原始BDD方法、冗余邊消除、K點非連通冗余消除、2種冗余同時消除4個步驟進行,實驗結果如表6所示。

實驗結果表明,改進算法應用于實際工程網絡,能有效計算二端可靠度和K端可靠度。進一步分析表6中數據得表7和圖5、圖6。由表7所示,在實際的工程網絡中,改進的算法充分識別并消除了無效邊冗余和K點非連通冗余,在基本不增加時間開銷的情況下,較大幅度地縮減了BDD尺度(15%左右),從而提升基于BDD網絡可靠性方法的分析性能。

表6 冗余消除性能比較實驗結果

表7 KeyNods可靠度性能指標數據

圖5為該工程網絡考慮二端可靠度和K端可靠度時,在冗余消除前后的BDD尺度情況。由圖5可得,2種冗余消除技術在不同程度上縮減了BDD尺度,聯合2種消除技術后,大幅縮減了BDD尺度。圖6所示為在考慮冗余消除時的時間開銷情況。由圖6可得,冗余消除前后,時間曲線交錯分布,聯合表7數據,整體而言,改進的算法時間成本有所減少。進一步分析表7中數據,一般情況下,在BDD尺度縮減上,應有3種冗余消除技術,有累加效果;在運行時間上,不會因為綜合應用多種消除技術而增加。

圖5 BDD尺度比較

5 結束語

本文利用邊界集思想,基于邊收縮和邊刪除實現了自頂向下的K端可靠度BDD分析算法,深入分析其中的冗余BDD節點問題,提出并實現了無效邊消除和K點非連通消除2種冗余消除技術。在規則網絡和工程網絡中的實驗結果表明,帶冗余消除的改進算法,在不增加時間成本的情況下,大幅縮減了BDD尺度,從而極大提升網絡可靠度算法的分析性能,因此,更適用于大規模網絡的可靠度分析。下一步研究工作為:(1)研究網絡結構特征對BDD構建的影響,尋求更為高效的BDD生成方法;(2)研究邊排序和網絡結構與最簡BDD的關系,設計更為合理的排序策略。

[1] 江光杰,李德毅.通信網可靠性評估[J].通信學報, 1997,18(8):85-89.

[2] Buzacott J A.The Ordering of Terms in Cut-based Recursive Disjoint Products[J].IEEE Transactions on Reliability,1983,32(5):472-474.

[3] Moskowitz F.The Analysis of Redundancy Networks[J]. AIEE Transactions on Communications and Electronics, 1958,77(5):627-632.

[4] Satyanarayana A,Chang M K.Network Reliability and The Factoring Theorem[J].Networks,1983,13(1): 107-120.

[5] Resende M.A Program forReliability Evaluation of Undirected Networks via Polygon-to-chain Reductions[J]. IEEE Transactions on Reliability,1986,35(1):24-29.

[6] Akers B.Binary Decision Diagrams[J].IEEE Transactions on Computers,1978,27(6):509-516.

[7] Dutuit Y,Rauzy A,Signoret J P.Computing Network Reliability with Réséda and Aralia[C]//Proceedings of European Safety and Reliability Association Conference. Berlin,Germany:Springer,1996:1947-1952.

[8] Yeh F M,Kuo S Y.OBDD-based Network Reliability Calculation[J].Electronics Letters,1997,33(9):759-760.

[9] Hardy G,Lucet C,Limnios N.Computing All-terminal Reliability of Stochastic Networks with Binary Decision Diagrams[C]//Proceedings of the 11th International Symposium on Applied Stochastic Models and Data Analysis.[S.l.]:IEEE Press,2005:1468-1472.

[10] 潘竹生,莫毓昌.網絡可靠度BDD分析算法的性能改進[J].計算機工程與科學,2012,34(9):26-32.

[11] Yeh F M,Lu S K,Kuo S Y.OBDD-based Evaluation of k-terminal Network Reliability[J].IEEE Transactions on Reliability,2002,51(4):443-451.

[12] Hardy G,LucetC,LimniosN.K-terminalNetwork Reliability Measures with Binary Decision Diagrams[J]. IEEE Transactions on Reliability,2007,56(3):506-515.

[13] Selcuk A S,Yucemen M S.Reliability of Lifeline Networks with Multiple Sources Under Seismic Hazard[J].Natural Hazards,1999,21(1):1-18.

編輯 顧逸斐

Research on Binary Decision Diagram Construction in Top-down for Network Reliability Analysis

ZENG Lingguo,PAN Zhusheng,MO Yuchang
(College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004,China)

Using the boundary partition of identification network thought,the Binary Decision Diagram(BDD) construction algorithm in top-down K-terminal reliability based on boundary partition is realized.Aiming at the problem of node redundancy existed in BDD construction process,this paper proposes two processing techniques about invalid edge redundancy elimination and K-point nonconnected redundancy elimination.Experimental results of regular network and practical engineering show that,the improved BDD algorithm with invalid edge redundancy elimination technique and K point nonconnected redundancy elimination technique,can substantially reduce the BDD scale,and enhance the K-terminal network reliability analysis of algorithm performance,without affecting the time performance,which is applied to larger scale network reliability analysis.

network reliability;Binary Decision Diagram(BDD);boundary set;edge contraction;redundancy

1000-3428(2015)01-0309-07

A

TB114

10.3969/j.issn.1000-3428.2015.01.058

浙江省教育廳基金資助項目(Y201328293,Y201328072);浙江省重中之重學科開放課基金資助項目(ZSDZZZZXK24)。

曾令國(1979-),男,講師、碩士,主研方向:系統可靠性計算;潘竹生,副教授、碩士;莫毓昌,副教授、博士。

2013-12-05

2014-03-12 E-mail:jk63@zjnu.cn

中文引用格式:曾令國,潘竹生,莫毓昌.網絡可靠性分析中自頂向下的二叉決策圖構造研究[J].計算機工程, 2015,41(1):309-315.

英文引用格式:Zeng Lingguo,Pan Zhusheng,Mo Yuchang.Research on Binary Decision Diagram Construction in Topdown Manner for Network Reliability Analysis[J].Computer Engineering,2015,41(1):309-315.