用改進的OBDD方法計算通信網可靠度

摘 要:提出一種改進的OBDD(ordered binary decision diagram)方法來計算通信網可靠度。該方法考慮了網絡共因失效帶來的部件故障，使得計算更加準確。在創建原始網絡的OBDD結構后，根據共因變量集來計算網絡可靠度。由于只創建并保存一個OBDD結構，可節省大量的計算時間和存儲空間。實驗證明，該方法能有效計算網絡可靠度，其計算時間和存儲空間要低于一般的OBDD方法。

關鍵詞:通信網;網絡可靠度;共因失效;有序二叉判定圖

中圖分類號:TN915 文獻標志碼:A

文章編號:1001-3695(2010)03-1114-04

doi:10.3969/j.issn.1001-3695.2010.03.085

Reliability computation of communication network with enhanced OBDD method

XIAO Yu-feng1，LI Xin2，LI Yu-hong2，JIANG Hong1

(1.School of Information Engineering， Southwestern University of Science Technology， Mianyang Sichuan 621010， China; 2.State Key Laboratory of Networking Switching， Beijing University of Posts Telecommunications， Beijing 100876， China)Abstract:This paper proposed an enhanced OBDD method to compute the reliability of communication network. Taking into account the component failures from CCF (common cause failure)， this new method could calculate the reliability value more accurately.After constructing the OBDD of the original network， it executed computations with common cause variable set.Because only one OBDD was created and stored， much computation time and storage space was saved.The experiments show this method can efficiently evaluate the network reliability， and it costs less time and storage than ordinary OBDD method.

Key words:communication network; network reliability; common cause failure; ordered binary decision diagram

0 引言

通過分析可靠性，工程人員能設計出可靠的通信網，減少網絡的故障概率。現有的網絡可靠度計算方法可分為兩類:精確計算和近似計算[1，2]。精確計算方法有狀態枚舉法、容斥原理法和因子分解法等。而近似計算方法通過計算可靠度邊界值來逼近精確值。這些傳統方法一般假設部件故障統計獨立，其成果不適用于自然災害或戰爭環境下的可靠度評估[3，4]。譬如，地震發生時，通信網的多條鏈路可能同時中斷，假設鏈路故障統計獨立就會過高估計網絡可靠度。為準確評估自然災害或戰爭條件下的網絡可靠度，必須考慮部件故障的相關性，即部件故障并非統計獨立。這種故障的一類典型情況就是某外界因素導致多個部件失效，即共因失效。引發共因失效的因素稱為共因因素，發生故障的部件稱為共因組，導致故障的事件稱為共因事件[3~6]。

考慮共因失效的網絡可靠性研究并不多見，有代表性的成果有Page和Xing的算法。Page應用組合方法分析共因失效網絡，提出用factoring算法分析網絡可靠性，該算法只適合分析小規模網絡[4];Xing改進OBDD算法來分析共因失效網絡，根據共因事件發生時的網絡結構遞歸地創建OBDD結構，再利用遞歸算法沿OBDD計算其可靠度[3，5]。當網絡規模較大或者共因事件較多時，遞歸過程將帶來大量的計算開銷，導致執行效率低下。關于提高OBDD方法的計算效率，Kuo等人[7，8]作了深入研究，但其方法不能直接用于共因失效網絡。

本文提出的COBDD算法是一種精確計算方法，它充分利用OBDD結構來計算共因失效網絡的可靠度。對于存在L個共因因素的網絡，Xing的方法需要創建并保存2L個OBDD。與此不同，COBDD創建無共因失效網絡(本文也稱之為原始網絡)的OBDD結構后，根據共因事件的共因變量集來計算網絡可靠度。只需要創建并保存一個OBDD結構，當網絡規模較大或者共因事件較多時，可節省大量的計算時間和存儲空間。實驗證明，COBDD算法能有效評估共因失效網絡的可靠度，其計算時間和存儲空間要低于一般的OBDD方法。

1 OBDD與網絡可靠度

1.1 OBDD結構

BDD(二叉判定圖)可用來表示布爾函數，它描述了布爾變量的各種取值情況，同時減少冗余的等價狀態。該結構在計算機內的存儲形式很簡單，能方便地執行各種邏輯運算[5~8]。圖1是用BDD表示函數f(x，y，z)=(x∨y)∧z的過程。圖1(a)是三個變量的BDD表達形式;(b)是變量x和y“或”運算表達式(x∨y)的BDD表達形式;(c)是(x∨y)∧z的BDD表達形式。BDD是一種層次邏輯結構，圈節點表示布爾變量，矩形節點表示邏輯真或假。最上層的圈節點是根節點，從根節點往下到底層矩形節點存在多條路徑，對應布爾變量的不同取值。譬如，圖1 (c)中BDD的根節點對應變量x。同層的圈節點表示同一布爾變量，節點向下的兩條邊表示對應變量的0或1取值。沿實線邊得到變量取1時的子BDD，本文稱為1-孩子;沿虛線邊得到對應變量取0時的子BDD，本文稱為0-孩子。譬如，圖1 (c)中BDD的x取0得到0-孩子，如圖1 (d)所示，x取1得到1-孩子，如圖1 (e)所示。在BDD結構中，優化變量順序可以減少節點數量，降低計算復雜度。為函數按照確定的變量順序創建BDD，就得到了有序BDD，即OBDD。圖1(c)的變量順序是x、y、z。廣度優先搜索是一個比較有效的OBDD排序原則[7，8]，本文也選擇該原則。

1.2 網絡可靠度布爾函數

根據網絡節點是否保持連通，網絡可靠度可分為二端可靠度、全端可靠度和K端可靠度。本文討論的是二端可靠度，即網絡中兩個端點之間保持連通的概率，這兩個端點分別稱為源節點和目的節點[1，2]。二端可靠度的研究成果可以推廣到K端可靠度和全端可靠度。另外，全文的可靠度計算基于兩個條件:a)節點可靠，假設網絡為節點提供了保護措施，能保證節點一直可靠工作;b)存在共因失效，假設由于外界因素導致網絡多條鏈路同時發生故障。條件a)是為降低計算復雜度，可以采用一些替代原則來處理不可靠節點[2]。

n條鏈路的網絡G可以用一個布爾函數f表示為

f(x0，…，xn-1)=1 如果源節點和目的節點連通0 否則

其中:xi是表示鏈路ei的布爾變量(0≤i≤n-1)。如果ei正常工作，xi=1;如果ei故障，xi=0。這樣，網絡的可靠度就是該函數值為1的概率值。這個函數被稱為網絡可靠度布爾函數，如果能用OBDD 表示，就可利用OBDD結構來計算網絡可靠度[5~8]。

2 算法設計

2.1 符號表示

G(V，E) 網絡拓撲結構圖，網絡中的節點用點集V表示，鏈路用邊集E表示

s，t源節點，目的節點

OBDD(G)網絡G的OBDD構造函數

REL(G)網絡的可靠度函數

RELo(r)計算OBDD對象r的可靠度函數

Ci第i個共因因素

CGi第i個共因組，由Ci影響的所有部件組成

CEi第i個共因事件

CESi第i個共因事件的部件集合，即受CEi影響的部件組成的集合

CEOSiCESi中各部件對應的布爾變量集合，稱為共因變量集

GiCEi發生時的網絡結構

Pr(CEi)第i個共因事件發生概率

2.2 一般的OBDD方法

Xing提出用一般的OBDD方法來計算共因失效網絡的可靠度，計算公式如下[3，5]:

RELo(OBDD(G))=2L-1j=0RELo(OBDD(Gj))×Pr(CEj)

其中:L是網絡G的共因因素數目;Gj是共因事件CEj發生時的網絡;OBDD(Gj)是Gj對應的OBDD結構(0≤j≤2L-1)。該方法表明:首先為每個共因事件發生時的網絡創建OBDD結構，然后遍歷每個OBDD結構計算每個網絡的可靠度。由于這樣的網絡有2L個，對這些網絡執行全概率求和即可計算出網絡的可靠度。如果共因因素統計獨立，以如下方法分析CEj:

CE0=C0∩C1∩…∩CL-1，CE1=C0∩C1∩…∩CL-1，

…，CE2L-1=C0∩C1∩…∩CL-1

其中:Ci是第i個共因因素(0≤i≤L-1)，CEj是第j個共因事件。共因事件概率可計算如下:

Pr(CE0)=(1-PC0)×(1-PC1)×…×(1-PCL-1)，Pr(CE1)=PC0×(1-PC1)×…×(1-PCL-1)，…，Pr(CE2L-1)=PC0×PC1×…×PCL-1

如果共因因素非統計獨立，可參考文獻[5]分析共因事件。這是一般的OBDD方法，需要創建并保存2L個OBDD。為網絡創建OBDD是一個開銷很大的遞歸過程[7，8]，當L值很大時，可靠度計算會消耗大量的計算時間和存儲空間。

2.3 改進的OBDD方法——COBDD

本文提出了COBDD方法，對一般的OBDD方法進行改進，只需要創建并存儲一個OBDD結構，即原始網絡OBDD(Gor)。這樣不僅減少了計算時間，而且節省了存儲空間，尤其是在網絡規模很大時可節省大量計算時間和存儲空間。COBDD算法計算共因失效網絡可靠度的步驟如下:

a)創建原始網絡G0的OBDD結構OBDD(G0)。利用邊擴張方法分解原始網絡的拓撲結構，創建一個表示網絡可靠度布爾函數的OBDD結構[7]。

b)為共因事件CEj計算共因變量集CEOSj，方法如下:

(a)計算CEj發生時的故障邊集合CESj。令CGi為Ci影響的邊集，那么有CESj :

CES0=，CES1=CG0，…，CES2L-1=CG0∪CG1∪…∪CGL-1

(b)CEOSj={x|x是e邊對應的布爾變量，e∈CESj}

c)為每一個共因事件下的網絡計算可靠度。遞歸遍歷OBDD(G0)，節點屬于CEOSj時只訪問節點的0-孩子，用遞歸公式可描述為

RELo(OBDD(G))=1.0，如果OBDD(G)=bddtrue

0.0，如果OBDD(G)=bdd1

RELo(OBDD(G)|x=0)，如果x∈CEOSj

Pr(x=1)×RELo(OBDD(G)|x=1)+

Pr(x=0)×RELo(OBDD(G)|x=0)，其他

其中:OBDD(G)|x=1是x節點的1-孩子;OBDD(G)|x=0是x節點的0-孩子;bddtrue和bdd1分別表示OBDD結構中的邏輯真和假。計算OBDD時的遍歷路徑由CEOSj決定，該公式的實現步驟如下:

(a)訪問OBDD(G)根節點變量x，得到對應邊e的工作概率p。

(b)判定OBDD(G)的值:如果是bddtrue，返回可靠度值1.0;如果是bdd1，返回可靠度值0.0;否則，繼續下一步。

(c)判斷hash表中是否存在該OBDD的可靠度。如果存在，直接返回該可靠度值;否則，繼續下一步。

(d)如果x∈CEOSj，執行下面三步;否則，轉(e)。

#8226;OBDD(G)|x=0= low(OBDD(G));

#8226;轉(a)計算RELo(OBDD(G)|x=0);

#8226;把RELo(OBDD(G)|x=0)插入hash表中，同時返回該數值。

(e)如果xCEOSj ，執行下面三步。

#8226;OBDD(G)|x=0=low(OBDD(G))和OBDD(G)|x=1= high(OBDD(G));

#8226;轉(a)計算RELo(OBDD(G)|x=0)和RELo(OBDD(G)|x=0)

#8226;執行計算:RELo(OBDD(G))=p×RELo(OBDD(G)|x=1)+(1-p)×RELo(OBDD(G)|x=0)

然后，把計算得到的可靠度值插入hash表中，同時返回G的可靠度。

d)利用如下公式計算整個網絡的可靠度

RELo(OBDD(G))=2L-1i=0RELo(OBDD(Gi))×Pr(CEi)

2.4 算法偽碼

COBDD的算法偽碼如下所示。其中，COBDD函數是算法的框架，OBDDRelCEOS函數根據共因變量集來計算共因事件下的網絡可靠度。

/* LookupRELHash: 查詢可靠度hash*/

/* InsertintoRELHash: 把可靠度插入hash */

/*CEOSj:共因變量集*/

/*CalculateCEOS: 計算共因變量集 */

double OBDDRelCEOS(bdd bdd_graph)

{p=operation probability of edge e;

if(bdd_graph is bddtrue)return 1.0;

else if(bdd_graph is bdd1)return 0.0;

if (bdd_graph exists in the bdd_hash)

{r=LookupRELHash(bdd_graph);

return r;/*return the reliability in hash*/

}

n_var=bdd_var(bdd_graph);

if(n_var exists in CEOSj)

{bdd bdd_low = low(bdd_graph);

reliability = OBDDRelCEOS(bdd_low);

InsertintoRELHash(bdd_graph， reliability);

return reliability;

}

else

{bdd bdd_high = high(bdd_graph);

bdd bdd_low = low(bdd_graph);

reliability = p*OBDDRel(bdd_high)+(1-p)* OBDDRel(bdd_low);

InsertintoRELHash(bdd_graph， reliability);

return reliability;

}

}

COBDD(G)

{ bdd bdd_G=OBDDConstruct(G);/*創建OBDD(Gor)*/

for(each E(j))

{/*計算共因變量集 */

CEOSj=CalculateCEOS();

reliability=reliability+OBDDRelCEOS (bdd_G)*Pr(E(j));

}

return reliability;

}

2.5 算例分析

本節通過一個實際網絡的可靠度計算過程來解釋COBDD的工作原理。圖2中，節點0是源端，節點8是終端，(a)是原始網絡結構，存在兩個共因因素:C0——洪水，C1——地震。受C0影響的共因組CG0 ={e3，e4，e5，e6}，受C1影響的共因組CG1={e6，e7，e9，e11}。這兩個共因組把共因事件空間劃分成四個子集:

CE0=C0∩C1，CE1=C0∩C1，CE2=C0∩C1，CE3=C0∩C1

分別對應四個共因事件邊集:

CES0=，CES1=CG0，CES2=CG1，CES3=CG0∪CG1

CE0發生時，不存在邊的共因失效，此時的網絡結構與原始網絡結構一樣，如圖2(a)所示;CE1發生時，集合{e3，e4，e5，e6}中的邊共因失效，此時的網絡結構如圖2(b)所示，CEOS1={x3，x4，x5，x6};CE2發生時，集合{e6，e7，e9，e11}中的邊共因失效，此時的網絡結構如圖2(c)所示，CEOS2={x6，x7，x9，x11};CE3發生時，集合{e3，e4，e5，e6，e7，e9，e11}中的邊共因失效，此時的網絡結構如圖2(d)所示，源節點和目的節點不連通，網絡的可靠度是0。

執行算法步驟a)，得到原始網絡的OBDD結構，如圖3所示;執行算法步驟b)，令xi是邊ei對應的變量，從而有共因變量集如下:

CEOS0=，CEOS1={x3，x4，x5，x6}，CEOS2={x6，x7，x9，x11}

執行算法步驟c)，根據共因變量集遍歷OBDD(G0)，計算網絡可靠度。計算G0可靠度時遍歷了所有邊，計算G1可靠度時遍歷了圖4(a)中粗線邊，計算G2可靠度時遍歷了圖4(b)中粗線邊。

執行算法步驟d)，按如下公式計算網絡可靠度:

RELo(OBDD(G))=RELo(OBDD(G0))×Pr(CE0)+

RELo(OBDD(G0)|CEOS1={x3，x4，x5，x6})×Pr(CE1)+

RELo(OBDD(G0)|CEOS2={x6，x9，x10，x11})×Pr(CE2)

COBDD計算可靠度時只需要創建并保存一個OBDD，當共因事件較多和網絡規模較大時，可以節省大量的計算時間和存儲空間。在本例中，COBDD要比一般OBDD節省三個OBDD創建時間和存儲空間。

3 實驗

本文用C語言實現了COBDD算法，所用到的BDD函數庫是Nielsen課題組開發的Buddy版BDD[9]。實驗計算機的CPU工作頻率為1.8 GHz，內存容量為512 MB。操作系統是Linux，內核2.4。圖5是實驗基準網絡，在很多網絡可靠度論文中出現過，常被用來檢驗算法的正確性和效率[3~8]，網絡中的黑點分別是源節點和目的節點。本實驗通過對比Xing的OBDD和COBDD算法來評估COBDD的效率。該實驗評估圖5中9個實驗網絡的可靠度，邊的工作概率是0.9，其中受洪水影響的邊用“|”標志，受地震影響的邊用“||”標志，同時受洪水和地震影響的邊用“|||”標志，地震發生的概率為0.002，洪水發生的概率為0.003。

實驗結果被記錄在表1中，可靠度欄包括兩個子欄:無共因失效子欄是不考慮共因失效的網絡可靠度;有共因失效子欄是考慮共因失效的網絡可靠度。計算時間欄包括兩個子欄:XO欄是Xing的OBDD算法計算可靠度的時間，CO欄是COBDD算法計算可靠度的時間。存儲空間欄包括兩個子欄:XO欄是Xing的OBDD算法存儲OBDD節點數，CO欄是COBDD算法存儲OBDD節點數。實驗中，每個算法被執行20次后，其平均計算時間被記錄為表中的可靠度計算時間。可靠度中的數值是現有可靠度評估算法的計算結果，被可靠性文獻用來校驗新算法的正確性。COBDD計算出來的可靠度數值與其吻合，表明COBDD算法是正確的。顯然，無共因失效欄的可靠度要比有共因失效欄的可靠度高，其原因是計算無共因失效的可靠度未考慮共因失效。對比9個實驗網絡的計算開銷可以發現，COBDD的計算時間要比XOBDD短，特別是當網絡規模較大時，COBDD的計算開銷比XOBDD低很多，如網絡6和9。另外，XOBDD所用的存儲空間要明顯少于COBDD，特別是規模較大的網絡9，COBDD可以節省數倍的存儲空間。實驗表明，COBDD有效地改進了一般OBDD算法的計算效率和存儲效率。

表1 計算時間與存儲空間比較

網絡

可靠度

無共因失效有共因失效

計算時間

XO/sCO/s

存儲空間

XO/個CO/個

10.978 480.977 390.001 290.000 82138

20.968 430.965 170.001 690.001 042419

30.964 860.963 560.004 640.001 466728

40.987 390.987 320.236 980.106 18638371

50.998 060.997 980.204 470.093 423 6351 680

60.904 580.904 040.177 380.086 43311100

70.987 830.987 550.201 890.094 53444293

80.971 350.971 050.190 320.085 84342106

90.304 290.303 910.821 930.566 742 344594

4 結束語

本文考慮部件故障的相關性，提出用COBDD算法來計算共因失效網絡的可靠度。與一般的OBDD方法不同，COBDD創建原始網絡OBDD結構后，根據共因事件發生時的共因變量集來計算網絡可靠度。只需要創建并保存一個OBDD結構，可節省大量的計算時間和存儲空間。實驗證明，COBDD算法能有效評估共因失效網絡的可靠度，與一般的OBDD方法相比，其計算速度較快、存儲開銷較低。本文下一步工作將考慮節點不可靠網絡的可靠度計算。

參考文獻:[1]BALL M O.Computational complexity of network reliability analysis an overview[J].IEEE Trans on Reliability，1986，35(3):230-239.

[2]COLBOURN C J.The combinatorics of network reliability[M].Oxford:Oxford University Press，1987:1-11.

[3]XING L D.Reliability evaluation of phased-mission systems with imperfect fault coverage and common-cause failures[J].IEEE Trans on Reliability，2007，56(1):58-68.

[4] PAGE L B，PERRY J E.A model for system reliability with common-cause failures[J].IEEE Trans on Reliability，1989，38(4):406-410.

[5] XING L D.An efficient binary-decision-diagram-based approach for network reliability and sensitivity analysis[J].IEEE Trans on Systems， Man， and Cybernetics-Part A:Systems and Humans，2008，38(6):105-115.

[6]XIAO Yu-feng，CHEN Shan-zhi， LI Xin，et al.Evaluate reliability of wireless sensor networks with OBDD[C]//Proc of IEEE International Conference on Communications.Dresden:IEEE Press， 2009:1011-1015.

[7]KUO S Y，YEH F M，LIN H Y.Efficient and exact reliability evaluation for networks with imperfect vertices[J].IEEE Trans on Reliability，2007，56(2):288-300.

[8]HARDY G，LUCET C，LIMNIOS N.K-terminal network reliability measures with binary decision diagrams[J].IEEE Trans on Reliability，2007，56(3):506-515.

[9]Online BDD Library[EB/OL].http://sourceforge.net/projects/buddy.