曾令國,潘竹生,莫毓昌

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

網(wǎng)絡可靠性分析中自頂向下的二叉決策圖構(gòu)造研究

曾令國,潘竹生,莫毓昌

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

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

網(wǎng)絡可靠度;二叉決策圖;邊界集;邊收縮;冗余

1 概述

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

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

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

2 自頂向下的BDD構(gòu)建

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

(1)為原始網(wǎng)絡G建立BDD節(jié)點,構(gòu)建目標BDD的第1層節(jié)點,即根節(jié)點。

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

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

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

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

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

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

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

3 性能改進

3.1 問題分析

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

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

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

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

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

圖2 示例網(wǎng)絡

圖3 自頂向下BDD生成

3.2 冗余消除

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

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

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

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

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

算法3K點是否可達算法

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

3.3 實驗結(jié)果

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

表1 二端可靠度實驗結(jié)果

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

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

表2 N×N型網(wǎng)絡二端可靠度實驗結(jié)果

表3 網(wǎng)絡可靠度性能指標數(shù)據(jù)

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

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

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

表5 全端可靠度實驗結(jié)果

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

4 案例應用分析

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

圖4 土耳其布爾薩市配水網(wǎng)絡

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

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

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

表6 冗余消除性能比較實驗結(jié)果

表7 KeyNods可靠度性能指標數(shù)據(jù)

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

圖5 BDD尺度比較

5 結(jié)束語

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

[1] 江光杰,李德毅.通信網(wǎng)可靠性評估[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] 潘竹生,莫毓昌.網(wǎng)絡可靠度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-),男,講師、碩士,主研方向:系統(tǒng)可靠性計算;潘竹生,副教授、碩士;莫毓昌,副教授、博士。

2013-12-05

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

中文引用格式:曾令國,潘竹生,莫毓昌.網(wǎng)絡可靠性分析中自頂向下的二叉決策圖構(gòu)造研究[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.