肖宇峰,張 華

(西南科技大學(xué)a.信息工程學(xué)院;b.特殊環(huán)境機(jī)器人技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室,四川綿陽621010)

基于二元決策圖的節(jié)點(diǎn)不可靠網(wǎng)絡(luò)可靠度計算

肖宇峰a,b,張 華a,b

(西南科技大學(xué)a.信息工程學(xué)院;b.特殊環(huán)境機(jī)器人技術(shù)四川省重點(diǎn)實(shí)驗(yàn)室,四川綿陽621010)

針對節(jié)點(diǎn)不可靠網(wǎng)絡(luò)可靠度計算效率較低的問題,提出一種基于二元決策圖的網(wǎng)絡(luò)可靠度計算方法。通過因子分解得到節(jié)點(diǎn)可靠網(wǎng)絡(luò)的有序二元決策圖(OBDD),根據(jù)節(jié)點(diǎn)和邊的關(guān)系對邊的變量節(jié)點(diǎn)執(zhí)行邊替換操作,生成節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的OBDD,并利用其高效存儲結(jié)構(gòu)提高不可靠節(jié)點(diǎn)的處理效率。在遍歷OBDD計算可靠度時,引入Hash表以避免對同一節(jié)點(diǎn)的重復(fù)訪問,從而減少冗余計算,進(jìn)一步提高計算效率。在基準(zhǔn)網(wǎng)絡(luò)中的對比實(shí)驗(yàn)結(jié)果表明,該方法不僅能正確計算網(wǎng)絡(luò)可靠度,而且能快速分析大型網(wǎng)絡(luò)。

網(wǎng)絡(luò)可靠度;二元決策圖;不可靠節(jié)點(diǎn);因子分解;布爾變量

1 概述

對于當(dāng)前通信量急劇增加的骨干網(wǎng)絡(luò)[1-2]、廣泛應(yīng)用的無線傳感器網(wǎng)絡(luò)以及災(zāi)變環(huán)境下的數(shù)據(jù)網(wǎng)絡(luò)[3],節(jié)點(diǎn)失效帶來的網(wǎng)絡(luò)可靠性問題正被工程人員和學(xué)者廣泛關(guān)注[4-5]。對節(jié)點(diǎn)不可靠網(wǎng)絡(luò)進(jìn)行可靠性分析時,需要解決2個問題:(1)如何處理不可靠節(jié)點(diǎn)[6];(2)當(dāng)網(wǎng)絡(luò)規(guī)模較大時,如何提高計算效率[7-8]。文獻(xiàn)[3]應(yīng)用因子分解來評估無線傳感器網(wǎng)絡(luò)的可靠度,該方法的計算開銷隨著網(wǎng)絡(luò)規(guī)模增大快速增長[9];文獻(xiàn)[10-11]應(yīng)用分區(qū)等價類減少同構(gòu)子網(wǎng)帶來的重復(fù)計算,大幅提高了網(wǎng)絡(luò)可靠度計算效率,但未考慮不可靠節(jié)點(diǎn)。文獻(xiàn)[12-13]提出應(yīng)用二元決策圖(Binary Decision Diagram,BDD)計算節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的可靠度,基于位向量的Hash表存儲開銷隨著網(wǎng)絡(luò)規(guī)模擴(kuò)大快速增加。本文提出一種基于二元決策圖的節(jié)點(diǎn)不可靠網(wǎng)絡(luò)可靠度計算方法。首先按確定邊序分解網(wǎng)絡(luò)并生成節(jié)點(diǎn)可靠時的有序二元決策圖(Ordered BDD,OBDD),然后對OBDD變量節(jié)點(diǎn)執(zhí)行邊替換操作,生成節(jié)點(diǎn)不可靠時網(wǎng)絡(luò)的OBDD,最后遍歷OBDD計算網(wǎng)絡(luò)可靠度。

2 符號表示

本文使用到的符號定義如下:

psrc:網(wǎng)絡(luò)的源端;

pdst:網(wǎng)絡(luò)的終端;

G(V,E):表示網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的圖,其中,V是圖的點(diǎn)集,E是圖的邊集;

frel(G):網(wǎng)絡(luò)G的可靠度計算函數(shù);

Oobdd(G):網(wǎng)絡(luò)G的OBDD結(jié)構(gòu);

fr_o(Oobdd(G)):根據(jù)網(wǎng)絡(luò)OBDD計算可靠度的函數(shù);

G+e:收縮G中e邊生成的子網(wǎng);

G-e:刪除G中e邊生成的子網(wǎng)。

此外:

(1)本文討論的可靠度是指網(wǎng)絡(luò)源端和終端之間保持連通的概率。源端和終端之間存在一條連通的路徑,則認(rèn)為網(wǎng)絡(luò)可靠;否則,網(wǎng)絡(luò)不可靠。

(2)上述收縮和刪除邊的情形可擴(kuò)展為:連續(xù)收縮邊a和b得到的子網(wǎng)表示為G+a+b;連續(xù)刪除邊a和b得到的子網(wǎng)表示為G-a-b;連續(xù)收縮邊a后刪除邊b得到的子網(wǎng)表示為G+a-b。

3 網(wǎng)絡(luò)可靠度計算方法

本文在計算效率和不可靠節(jié)點(diǎn)處理方面增強(qiáng)了基于OBDD的網(wǎng)絡(luò)可靠度計算方法:首先利用邊的因子分解創(chuàng)建節(jié)點(diǎn)可靠網(wǎng)絡(luò)的OBDD結(jié)構(gòu);其次根據(jù)邊和節(jié)點(diǎn)的邏輯聯(lián)系,對邊的OBDD變量節(jié)點(diǎn)執(zhí)行邊替換操作,創(chuàng)建節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的OBDD結(jié)構(gòu);最后遍歷OBDD來計算網(wǎng)絡(luò)可靠度,并利用Hash表減少對同一OBDD節(jié)點(diǎn)的重復(fù)訪問,進(jìn)一步提高計算效率。

3.1 基于因子分解方法的OBDD創(chuàng)建

3.1.1 因子分解的基本概念

邊的因子分解方法通常假設(shè)網(wǎng)絡(luò)邊不可靠而節(jié)點(diǎn)可靠,根據(jù)邊的2種情況進(jìn)行分解:邊可靠則收縮邊,把邊的2個端點(diǎn)合并成一個點(diǎn);邊不可靠則刪除邊,把邊的2個端點(diǎn)保留在網(wǎng)絡(luò)中?；谝蜃臃纸獾木W(wǎng)絡(luò)可靠度計算可用如下公式表示[4]:

其中,e是網(wǎng)絡(luò)的某條邊;p是該邊可靠的概率;frel(G+e)是收縮e后網(wǎng)絡(luò)的可靠度;frel(G-e)是刪除e后網(wǎng)絡(luò)的可靠度。

圖1給出了利用邊的因子分解創(chuàng)建OBDD的實(shí)例,網(wǎng)絡(luò)G及其分解得到的子網(wǎng)按邊序e0～e5進(jìn)行6次分解。其中,灰色點(diǎn)表示包含或者合并了源端(終端)的節(jié)點(diǎn),圖中省略了源端和終端分離的子網(wǎng),所有的分解過程最后聚焦為源端和終端合并為一個節(jié)點(diǎn)的子網(wǎng)。顯然,根據(jù)確定邊序執(zhí)行因子分解把網(wǎng)絡(luò)逐層分為多個子網(wǎng),每執(zhí)行一次收縮邊和刪除邊操作就得到更小的子網(wǎng)。圖1中,除了第一次外的每次分解都是在上次分解得到的子網(wǎng)之上做進(jìn)一步分解,得到更小的子網(wǎng)。圖中的實(shí)線表示收縮邊,虛線表示刪除邊,L6層的灰色點(diǎn)并為一點(diǎn),表示源端和終端之間存在連通路徑。

圖1 網(wǎng)絡(luò)的因子分解

3.1.2 節(jié)點(diǎn)可靠網(wǎng)絡(luò)的OBDD創(chuàng)建

創(chuàng)建 OBDD時,首先要確定邊序e0,e1,…,em-1,然后根據(jù)邊的邏輯(是否可靠)狀態(tài)來分析網(wǎng)絡(luò)是否連通。利用OBDD的ITE運(yùn)算可以把每次分解對應(yīng)的邏輯判斷記錄下來,最后得到描述整個網(wǎng)絡(luò)的狀態(tài)圖[7]。網(wǎng)絡(luò)G的OBDD結(jié)構(gòu)可通過下式描述:

其中,f是邊序中某條邊的OBDD表達(dá)式;g是收縮邊得到子網(wǎng)的OBDD結(jié)構(gòu);h是刪除邊得到子網(wǎng)的OBDD結(jié)構(gòu)。顯然,g和h需要對邊序中其他邊遞歸執(zhí)行相同ITE運(yùn)算得到。圖2給出了圖1中實(shí)例網(wǎng)絡(luò)的OBDD,創(chuàng)建OBDD的具體步驟可參考文獻(xiàn)[12-13]。

圖2 節(jié)點(diǎn)可靠網(wǎng)絡(luò)的OBDD

3.1.3 節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的OBDD創(chuàng)建

前述OBDD創(chuàng)建過程假設(shè)網(wǎng)絡(luò)節(jié)點(diǎn)可靠,下文介紹一種應(yīng)用邏輯運(yùn)算處理不可靠節(jié)點(diǎn)的方法。

假設(shè)網(wǎng)絡(luò)G的節(jié)點(diǎn)可靠時,OBDD布爾變量Ve表示邊e,則G的OBDD結(jié)構(gòu)可表示為:

其中,Oobdd(G)|Ve=1表示e處于可靠狀態(tài)時G的OBDD結(jié)構(gòu);Oobdd(G)|Ve=0表示e處于不可靠狀態(tài)時G的OBDD結(jié)構(gòu)。節(jié)點(diǎn)不可靠時需要考慮邊的2個端點(diǎn)的邏輯狀態(tài),用布爾變量Va和Vb分別表示e的端點(diǎn)a,b。那么,e的完整布爾表示式為Va∧Ve∧Vb。為得到節(jié)點(diǎn)不可靠網(wǎng)絡(luò)G的OBDD,需要進(jìn)行如下運(yùn)算:

其中,obdd2是Va∧Ve∧Vb的OBDD結(jié)構(gòu)。上述運(yùn)算的含義是用端點(diǎn)不可靠的e替換OBDD中原有的e,執(zhí)行了OBDD的composition運(yùn)算[10]。本文將該運(yùn)算過程稱為邊替換。

節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的OBDD創(chuàng)建算法偽碼如下:

對圖2各邊執(zhí)行下列邊替換操作后,得到圖3中節(jié)點(diǎn)不可靠時網(wǎng)絡(luò)的OBDD結(jié)構(gòu)。

圖3 節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的OBDD

(1)＜v0,e0,v1＞的布爾變量替代 ＜e0＞的變量:

(2)＜v0,e1,v2＞的布爾變量替代 ＜e1＞的變量:

(3)＜v0,e2,v3＞的布爾變量替代 ＜e2＞的變量:

(4)＜v1,e3,v2＞的布爾變量替代 ＜e3＞的變量:

(5)＜v1,e4,v3＞的布爾變量替代 ＜e4＞的變量:

(6)＜v2,e5,v3＞的布爾變量替代 ＜e5＞的變量:

3.2 可靠度計算

3.2.1 可靠度計算原理及算法

按照上述改進(jìn)方法創(chuàng)建網(wǎng)絡(luò)G的OBDD結(jié)構(gòu)后,可通過下面的遞歸公式來計算網(wǎng)絡(luò)G的可靠度:

其中,0≤k＜n;Oobdd(G)|xk=1是xk=1時網(wǎng)絡(luò)G的OBDD,即xk對應(yīng)節(jié)點(diǎn)或邊可靠時G的OBDD結(jié)構(gòu);Oobdd(G)|xk=0是xk=0時網(wǎng)絡(luò)G的OBDD結(jié)構(gòu),即xk對應(yīng)節(jié)點(diǎn)或邊不可靠時G的 OBDD結(jié)構(gòu); Pr(xk=1)是xk對應(yīng)節(jié)點(diǎn)或邊的可靠概率,Pr(xk=0)是xk對應(yīng)節(jié)點(diǎn)或邊不可靠概率;bddtrue和bddfalse分別表示OBDD結(jié)構(gòu)中的邏輯真和邏輯假;k的初始值為0。顯然,完成上述公式的計算需要沿OBDD結(jié)構(gòu)遍歷其節(jié)點(diǎn),而且某些節(jié)點(diǎn)被多次訪問。在圖4中,e2,e4和e5在計算過程中被多次訪問,從而帶來重復(fù)計算。為減少這種冗余計算,設(shè)計算法時建立一個hash表,以當(dāng)前子網(wǎng)的OBDD根節(jié)點(diǎn)標(biāo)號為索引記錄當(dāng)前子網(wǎng)的可靠度數(shù)值,當(dāng)再次訪問該節(jié)點(diǎn)時直接返回已保存的數(shù)值。

下面的NetRel_urn()給出了節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的可靠度計算偽碼。其中,G代 表 網(wǎng) 絡(luò); BDDConstruct()是因子分解創(chuàng)建節(jié)點(diǎn)可靠網(wǎng)絡(luò)OBDD的算法,詳細(xì)實(shí)現(xiàn)可參考文獻(xiàn)[4]; BDDConstruct_urn()是上文創(chuàng)建節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的OBDD算法;BDDRel()是本小節(jié)上述計算方法的實(shí)現(xiàn)。

3.2.2 算法復(fù)雜度分析

本文算法由三部分組成:BDDConstruct, BDDConstruct_urn和BDDRel。其復(fù)雜度由其計算復(fù)雜度決定。文獻(xiàn)[9]通過優(yōu)化節(jié)點(diǎn)可靠網(wǎng)絡(luò)的分解過程,給出BDDConstruct和BDDRel復(fù)雜度的上界:

其中,O1為BDDConstruct和BDDRel的算法復(fù)雜度,m為網(wǎng)絡(luò)的邊數(shù),Fmax為最大邊界集的元素個數(shù),BFmax是最大邊界集的Bell數(shù)。這個值是現(xiàn)有研究中比較實(shí)用的上界值,本文按文獻(xiàn)[9]的方法優(yōu)化網(wǎng)絡(luò)分解后,BDDConstruct_urn的復(fù)雜度就可由BDD寬度和深度計算。BDD深度由網(wǎng)絡(luò)的邊數(shù)確定,BDD寬度上界可根據(jù)文獻(xiàn)[9]確定:

其中,Wbdd是 BDD 寬度上界。由算法結(jié)構(gòu), BDDConstruct_urn的復(fù)雜度上界為:

綜上所述,整個算法復(fù)雜度的上界為:

可見,Fmax決定了算法的復(fù)雜度,數(shù)百節(jié)點(diǎn)的網(wǎng)絡(luò)一般都有較小的Fmax值。根據(jù)文獻(xiàn)[9]優(yōu)化后,本文算法的計算效率將得到進(jìn)一步改善。

4 實(shí)驗(yàn)與結(jié)果分析

本文采用Buddy版BDD實(shí)現(xiàn)本文方法,并將其C語言實(shí)現(xiàn)程序命名為NetRel_urn[14]。為方便對比分析,同時實(shí)現(xiàn)了文獻(xiàn)[3,13]的方法,并分別命名為NetRel_yz和NetRel_x。實(shí)驗(yàn)計算機(jī)的CPU工作頻率為2.4 GHz,內(nèi)存容量為2 GB,操作系統(tǒng)為2.6內(nèi)核的紅帽Linux。圖4列出的9個網(wǎng)絡(luò)被較多文獻(xiàn)使用[9-13],因此,本文將其作為基準(zhǔn)網(wǎng)絡(luò)來檢驗(yàn)計算的正確性和效率。網(wǎng)絡(luò)中的黑實(shí)點(diǎn)分別表示源端和終端,點(diǎn)和邊可靠度是0.9。

圖4 實(shí)驗(yàn)基準(zhǔn)網(wǎng)絡(luò)

實(shí)驗(yàn)結(jié)果如表1所示,其中,“-”表示開銷超過1 h。

表1 計算時間比較 s

每個程序被執(zhí)行10次后,其平均計算時間被記錄為表中的時間開銷?？梢钥闯?NetRel_yz和NetRel_ x的開銷高于NetRel_urn。從網(wǎng)絡(luò)6、網(wǎng)絡(luò)7、網(wǎng)絡(luò)8和網(wǎng)絡(luò)9的計算結(jié)果可以發(fā)現(xiàn):隨著網(wǎng)絡(luò)規(guī)模增大, NetRel_yz的計算開銷顯著上升,甚至在1 h內(nèi)也無法得到計算結(jié)果;NetRel_x也無法計算網(wǎng)絡(luò)8和網(wǎng)絡(luò)9的可靠度;相比之下,NetRel_urn完成了計算任務(wù)。實(shí)驗(yàn)結(jié)果表明,本文方法可有效評估節(jié)點(diǎn)不可靠網(wǎng)絡(luò)的可靠度,當(dāng)網(wǎng)絡(luò)規(guī)模較大時,其計算開銷較低。

5 結(jié)束語

為高效處理不可靠節(jié)點(diǎn),本文提出了一種網(wǎng)絡(luò)可靠度計算方法,利用OBDD變量節(jié)點(diǎn)的邊替換操作和OBDD高效存儲結(jié)構(gòu)提高計算效率。實(shí)驗(yàn)結(jié)果表明,該方法能以較快的速度計算規(guī)模較大網(wǎng)絡(luò)的可靠度。但本文未考慮節(jié)點(diǎn)和邊失效的統(tǒng)計相關(guān)性,下一步將對其進(jìn)行深入研究。

[1] Ball M,Thomas M.Hand Books in Operations Research andManagementScience,NetworkModels[M]. [S.l.]:Elsevier,1995.

[2] Lin Y K,Chang P C.A Novel Reliability Evaluation Technique for Stochastic-flow Manufacturing Networks with Multiple Production Lines[J].IEEE Transactions on Reliability,2013,62(1):92-104.

[3] AboElFotoh H M F,IyengarS S,Chakrabarty K. Computing Reliability and message delay for cooperative Wireless Distributed Sensor Networks Subject to Random Failures[J].IEEE Transactions on Reliability, 2005,54(1):145-155.

[4] 肖宇峰.基于離散概率模型的二端網(wǎng)絡(luò)可靠性分析[D].北京:北京郵電大學(xué),2009.

[5] 江逸楠,李瑞瑩,黃 寧,等.網(wǎng)絡(luò)可靠性評估方法綜述[J].計算機(jī)科學(xué),2012,39(5):9-13.

[6] 吳 俊,段東立,趙 娟.網(wǎng)絡(luò)系統(tǒng)可靠性研究現(xiàn)狀與展望[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué),2011,8(2):77-86.

[7] 肖宇峰,李 昕,李玉宏,等.用改進(jìn)的OBDD方法計算通信網(wǎng)可靠度[J].計算機(jī)應(yīng)用研究,2010,27(3):114-117.

[8] Huang N,Chen Y,Hou D,et al.Application Reliability for Communication Networks and Its Analysis Method[J].Journal of Systems Engineering and Electronics,2011,22(6):1030-1036.

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

[10] Imai H,Sekine K,Imai K.Computational Investigations of all-terminal Network Reliability via BDDs[J].IEICE Transactions on Fundamentals,1999,E82-A(5):714-721.

[11] Carlier J,Lucet C.A Decomposition Algorithm for Network Reliability Evaluation[J].Discrete Applied Mathematics,1996,65(1):141-156.

[12] Kuo S Y,Yeh F M,Lin H Y.Efficient and Exact Reliability Evaluation for Networks with Imperfect Vertices[J].IEEE Transactions on Reliability,2007,56 (2):198-211.

[13] Xing Liudong.An Efficient Binary Decision Diagram Based Approach for Network Reliability and Sensitivity Analysis[J].IEEE Transactions on Systems,Man,and Cybernetics——Part A:Systems and Humans,2008,38 (6):105-115.

[14] Andersen H.An Introduction to Binary Decision Diagrams[M].[S.l.]:Elsevier,1997.

編輯 金胡考

Reliability Computation of Network with Unreliable Nodes Based on Binary Decision Diagram

XIAO Yufenga,b,ZHANG Huaa,b
(a.Information Engineering School;b.Special Environment Robot Technology Key Laboratory of Sichuan Province,Southwest University of Science and Technology,Mianyang 621010,China)

According to the inefficient reliability computation of network with unreliable nodes,this paper proposes a network reliability computation method based on Binary Decision Diagram(BDD).After the Ordered Binary Decision Diagram(OBDD)construction with factoring theorem,this method executes the edge replacements to OBDD variables of edges with the relation between nodes and edges,and the OBDD of network with unreliable nodes is constructed.Based on efficient OBDD structure,the computations about unreliable nodes are improved.Furthermore,a hash table is used to avoid the repeated access to same node when the reliability is calculated with OBDD traversal.Therefore,the redundant calculations are reduced,and the reliability computation efficiency of network with unreliable nodes is enhanced. Experiments are arranged on benchmark networks,and data analysis shows that this method can accurately calculate network reliability and quickly analyze some large networks.

network reliability;Binary Decision Diagram(BDD);unreliable node;factoring;Boolean variable

1000-3428(2015)01-0087-05

A

TP393

10.3969/j.issn.1000-3428.2015.01.016

國家核能開發(fā)科研基金資助項(xiàng)目([2011]1137);四川省科技支撐計劃基金資助項(xiàng)目(2013GZX0152);四川省教育廳基金資助重點(diǎn)項(xiàng)目(14ZA0091)。

肖宇峰(1978-),男,副研究員、博士,主研方向:網(wǎng)絡(luò)通信,計算機(jī)系統(tǒng)可靠性評估;張 華,教授、博士。

2014-01-20

2014-03-20 E-mail:xiaoyf_swit1@163.com

中文引用格式:肖宇峰,張 華.基于二元決策圖的節(jié)點(diǎn)不可靠網(wǎng)絡(luò)可靠度計算[J].計算機(jī)工程,2015,41(1):87-91.

英文引用格式:Xiao Yufeng,Zhang Hua.Reliability Computation of Network with Unreliable Nodes Based on Binary Decision Diagram[J].Computer Engineering,2015,41(1):87-91.