一種基于有序二元決策圖和布爾函數(shù)性質(zhì)計算網(wǎng)絡(luò)可靠性的算法

熊 飛 喬 迪 王宏祥 趙子巖 楊 洪 沈 亮

?

一種基于有序二元決策圖和布爾函數(shù)性質(zhì)計算網(wǎng)絡(luò)可靠性的算法

熊 飛*①喬 迪②王宏祥②趙子巖①楊 洪①沈 亮①

①(國家電網(wǎng)公司信息通信分公司 北京 100761)②(北京郵電大學信息與通信工程學院 北京 100876)

有序二元決策圖(OBDD)被廣泛用到網(wǎng)絡(luò)可靠度的計算中，在基于OBDD計算網(wǎng)絡(luò)可靠度時，其計算時間主要取決于參與操作的OBDD的大小，而OBDD的大小嚴重依賴于OBDD的變量序。該文根據(jù)布爾函數(shù)的性質(zhì)和OBDD原理提出一種優(yōu)化計算網(wǎng)絡(luò)可靠性的算法(BF-OBDD)，提高計算網(wǎng)絡(luò)可靠性的效率。實驗結(jié)果表明改進的算法有較少的OBDD節(jié)點數(shù)量，在計算網(wǎng)絡(luò)可靠性時，花費的時間較少。

計算機網(wǎng)絡(luò)；可靠性；網(wǎng)絡(luò)拓撲圖；有序二元決策圖；變量序；布爾函數(shù)

1 引言

隨著網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)絡(luò)的可靠性在網(wǎng)絡(luò)分析和設(shè)計中越來越重要，成為定量計算和定性分析中非常重要的性能指標。復雜網(wǎng)絡(luò)一旦出現(xiàn)故障就會導致災難性的后果。在IEEE90標準中把網(wǎng)絡(luò)可靠性定義為“網(wǎng)絡(luò)在規(guī)定時間和規(guī)定條件下完成它所需要完成功能的能力”。本文基于有序二元決策圖(Ordered Binary Decision Diagram, OBDD)算法對網(wǎng)絡(luò)連通可靠性進行了分析。

目前國內(nèi)外學者對網(wǎng)絡(luò)可靠性計算進行了大量的研究，主要分為兩種類型，第1種是枚舉最小路徑集或最小割集[1]。最小路徑集是包含所有最小路徑的集合。當最小路徑集中至少有一條最小路徑是正常工作的，則表示網(wǎng)絡(luò)是正常工作的。將網(wǎng)絡(luò)可靠度表示為全部最小路徑集的并，然后采用容斥原理法或不交化算法對其進行處理。這種方法在計算復雜網(wǎng)絡(luò)的可靠度時，效率很低。第2種是基于網(wǎng)絡(luò)拓撲圖[2]，通過對網(wǎng)絡(luò)拓撲圖中的邊進行逐一分析，當邊正常工作時，則壓縮與該邊相連的兩端為一個節(jié)點，當邊故障時，則刪除該邊。以此原則來分析網(wǎng)絡(luò)的可靠性。當網(wǎng)絡(luò)復雜，該算法需要分析很多條邊，計算效率低。

自文獻[3]于1978年提出全新的數(shù)據(jù)結(jié)構(gòu)二元決策圖(Binary Decision Diagram, BDD)以來，BDD被廣泛用于網(wǎng)絡(luò)可靠度的計算中[4]?；贐DD計算網(wǎng)絡(luò)可靠度的算法具有節(jié)省數(shù)據(jù)結(jié)構(gòu)空間和時間計算效率高的優(yōu)點。在基于OBDD計算網(wǎng)絡(luò)可靠度時，其計算時間主要取決于參與操作的OBDD的大小，而OBDD的大小嚴重依賴于OBDD的變量序[5]。文獻[6]提出基于網(wǎng)絡(luò)拓撲圖得到變量序來計算網(wǎng)絡(luò)可靠性。本文根據(jù)網(wǎng)絡(luò)拓撲圖和布爾函數(shù)的性質(zhì)提出一種優(yōu)化的基于網(wǎng)絡(luò)拓撲圖的變量排序算法(Boolean Function-OBDD, BF-OBDD)，并與文獻[6]提出的算法和基于網(wǎng)絡(luò)拓撲圖的深度優(yōu)先算法進行比較，結(jié)果表明本算法產(chǎn)生的節(jié)點數(shù)較少，花費的時間較低。

2 OBDD原理

2.1 BDD

BDD是布爾函數(shù)的圖形表示形式，BDD采用二叉樹形式表示一個布爾函數(shù)。

由上述定義1可看出，BDD是一個有根節(jié)點的有序二叉樹，每個分支代表節(jié)點變量的一次取值(左支取1，右支取0)。從根節(jié)點出發(fā)到葉結(jié)點的每條路徑都表示布爾函數(shù)中各變量的一次賦值。

2.2 OBDD

在有序二元決策圖(OBDD)中，若節(jié)點滿足以下兩種性質(zhì)，則稱節(jié)點是相等的[9]：

(1)兩個葉節(jié)點的值對應相等。

對于滿足上述條件的OBDD節(jié)點，可以應用如下簡化規(guī)則，有效地簡化OBDD結(jié)構(gòu)[10]：

(1)將葉節(jié)點為1的節(jié)點合并成一個節(jié)點，將葉節(jié)點為0的節(jié)點合并成一個節(jié)點。

3 最小路徑集及布爾函數(shù)性質(zhì)

3.1 最小路徑集基本原理

網(wǎng)絡(luò)是由一些節(jié)點以及連接某些節(jié)點對之間的邊組成的一個圖形。從指定的節(jié)點，經(jīng)過一邊序列(或其中的一部分邊)可以到達節(jié)點，則稱這個邊序列為從到的一條路徑。從節(jié)點到節(jié)點的邊序列稱為一條最小路徑，則滿足：(1)它是一條路徑；(2)最小性。即從這個邊序列中除去任意一條邊后它即不是從到的路徑，最小路徑中包含的邊數(shù)稱為它的長度[11]。

3.2 布爾函數(shù)性質(zhì)

4 基于OBDD計算網(wǎng)絡(luò)可靠性算法

4.1 基于網(wǎng)絡(luò)拓撲圖得到OBDD變量序

由第3.2小節(jié)提到布爾函數(shù)吸收律的性質(zhì)，本文提出基于網(wǎng)絡(luò)拓撲圖得到OBDD變量序的算法，算法步驟如下：

步驟1 從網(wǎng)絡(luò)拓撲圖中找出從源點到目的節(jié)點的最長最小路徑，并將其邊依次排在變量排序的最后；

步驟2 從網(wǎng)絡(luò)拓撲圖中找出從源點到目的節(jié)點的最短最小路徑，將最短最小路徑中未出現(xiàn)在變量排序中的邊依次排在變量排序的最前面；

步驟3 繼續(xù)搜索網(wǎng)絡(luò)拓撲圖中的最短最小路徑，將該最小路徑中未出現(xiàn)在變量序的邊排在已存變量序之后。若無最短最小路徑則轉(zhuǎn)到步驟4；

步驟4 從網(wǎng)絡(luò)拓撲圖中找出從源點到目的節(jié)點的次短最小路徑，將最短最小路徑中未出現(xiàn)在變量排序中的邊，放在已存變量序的后面；

步驟5 繼續(xù)搜索網(wǎng)絡(luò)拓撲圖中的次短最小路徑，將該最小路徑中未出現(xiàn)在變量序的邊排在已存變量序之后。若無次短最小路徑則轉(zhuǎn)到步驟6；

步驟6 按照最小路徑的長度從短到長對最小路徑依次進行選擇，直到網(wǎng)絡(luò)中所有的邊都放進變量序中。

其中若有相同長度的最小路徑，則根據(jù)最小路徑中邊的排序依次比較邊的編號，先選擇邊的編號大的最小路徑。

4.2 計算網(wǎng)絡(luò)可靠性的步驟

步驟2 由網(wǎng)絡(luò)拓撲圖，結(jié)合本文提出的算法得到OBDD變量序；

步驟3 依據(jù)得到的OBDD變量序?qū)⑦壿嫿Y(jié)構(gòu)函數(shù)用OBDD表示，本文在仿真中用哈希表來存儲OBDD節(jié)點[13]。用哈希表來存儲OBDD節(jié)點能保證生成的BDD節(jié)點是唯一的，并且能提高查找速度；

步驟4 從OBDD的根節(jié)點搜索到葉節(jié)點1的路徑，可得到邏輯結(jié)構(gòu)函數(shù)的不交化結(jié)果；

5 算法示例和仿真

以圖1所示的網(wǎng)絡(luò)拓撲圖為例進行說明，其中節(jié)點1為源節(jié)點，節(jié)點6為目的節(jié)點。

圖1 網(wǎng)絡(luò)拓撲圖

5.1 OBDD變量序

5.2 計算網(wǎng)絡(luò)可靠性

(2)按照OBDD的變量序?qū)壿嫿Y(jié)構(gòu)函數(shù)進行不交化處理得到OBDD，如圖2所示。

圖2 OBDD圖形

(3)在OBDD圖中搜索從根節(jié)點到葉節(jié)點1的路徑，得到不交化的邏輯結(jié)構(gòu)函數(shù)為

(4)網(wǎng)絡(luò)可靠性計算符號表達式為

5.3 仿真

圖3 實驗網(wǎng)絡(luò)

實驗結(jié)果分別用圖4、圖5和圖6表示，橫坐標表示的是對應的網(wǎng)絡(luò)拓撲圖，縱坐標數(shù)值用指數(shù)形式表示。其中排序2和排序3為文獻[6]提出的OBDD變量排序算法2和算法3。其中圖4記錄的是OBDD的節(jié)點數(shù)量，如在分析第8個網(wǎng)絡(luò)可靠性時，基于本算法得到的OBDD節(jié)點數(shù)量為1795個，其它3種算法得到的節(jié)點數(shù)分別為2959個、3063個和9084個；圖5記錄的是創(chuàng)建OBDD圖形所花費的時間；圖6表示的是計算網(wǎng)絡(luò)可靠性所花費的時間，當計算第8個網(wǎng)絡(luò)可靠性時，BF-OBDD所花費的時間為16.5 s，其余3種算法所花費的時間分別為30.2 s, 233.0 s和25.2 s。根據(jù)圖4可知，基于BF-OBDD算法計算網(wǎng)絡(luò)可靠性時可以產(chǎn)生較少的OBDD節(jié)點數(shù)量。根據(jù)圖5可知根據(jù)BF-OBDD算法在創(chuàng)建OBDD圖形時花費的時間較少，由圖6可以得到BF-OBDD算法在進行網(wǎng)絡(luò)可靠性計算時，花費的時間較少。

6 結(jié)束語

在基于OBDD計算網(wǎng)絡(luò)可靠性時，其計算時間主要取決于參與操作的OBDD的大小，而OBDD的大小嚴重依賴于OBDD的變量序。本文從網(wǎng)絡(luò)拓撲圖得到OBDD的變量序，由布爾函數(shù)的性質(zhì)和OBDD原理提出了BF-OBDD算法，在計算網(wǎng)絡(luò)可靠性時根據(jù)本算法能得到較少的OBDD節(jié)點數(shù)量，計算運行的時間較少。

圖4 OBDD節(jié)點數(shù)量

圖5 OBDD節(jié)點創(chuàng)建時間

圖6 可靠性計算時間

[1] 史玉芳, 陸寧, 李慧民. 基于改進的不交化最小路集的網(wǎng)絡(luò)系統(tǒng)可靠性算法[J]. 計算機工程與科學, 2011, 33(1): 31-35.

Shi Yu-fang, Lu Ning, and Li Hui-min. An algorithm of network system reliability based on an improved disjointed minimal path set[J]., 2011, 33(1): 31-35.

[2] Wood R. Factoring algorithm for computing k-terminal network reliability[J]., 1986, 35(3): 269-278.

[3] Akers S. Binary decision diagrams[J]., 1978, 27(6): 509-516.

[4] LüGuan-feng, Chen Yao, Feng Ya-chao,A succinct and efficient implementation of 232bdd package[C]. IEEE Sixth International Symposium on Theoretical Aspects of Software Engineering, Beijing, China, 2012: 241-244.

[5] 陳瑤, 李峭, 趙長嘯, 等. 基于OBDD的航空電子網(wǎng)絡(luò)可靠性分析[J]. 系統(tǒng)工程與電子技術(shù), 2013, 35(1): 230-236.

Chen Yao, Li Qiao, Zhao Chang-xiao,OBDD-based reliability analysis for avionics networks[J]., 2013, 35(1): 230-236.

[6] Zang X, Sun H, and Trivedi K. A bdd-based algorithm for reliability graph analysis[OL]. http://www.ee.duke.edu/~ hairong/workinduke/relgrap. 2000.

[7] Tatsuhiro Tsuchiya. A bdd-based approach to reliability optimal module allocation in networks[C]. IEEE 18th Pacific Rim International Symposium on Dependable Computing, Niigata, Japan, 2012: 121-126.

[8] Zhao Bo, Liu Yan, and Xiao Yu-feng. OBDD-based algorithm for reliability evaluation of wireless sensor networks[C]. Prognostics and Systems Health Management Conference, Beijing, China, 2012: 1-4.

[9] Friedman S and Supowit K. Finding the optimal variable ordering for binary decision diagrams[J]., 1990, 39(5): 710-713.

[10] Mahdi I and Nadji B. Application of the binary decision diagram(BDD) in the analysis of the reliability of the inverters[C]. Proceedings of 4th International Conference on Power Engineering, Energy and Electrical Drives, Istanbul, Turkey, 2013: 1265-1271.

[11] 曹晉華, 程侃. 可靠性數(shù)學引論[M]. 北京: 科學出版社, 1986: 89-90.

Cao Jin-hua and Cheng Kan. Reliability Mathematics Introduction[M]. Beijing: Science Press, 1986: 86-90.

[12] 古天龍, 徐周波. 有序二叉決策圖及應用[M]. 北京: 科學出版社, 2009: 18-19.

Gu Tian-long and Xu Zhou-bo. Ordered Binary Decision Diagram and Its Application[M]. Beijing: Science Press, 2009: 18-19.

[13] Brance K, Rudell R, and Bryant R. Efficient implementation of a bdd package[C]. Proceedings of 27th ACM/IEEE DAC, New York, USA, 1990: 40-45.

[14] 趙勃, 肖宇峰, 劉巖. 基于OBDD的通信網(wǎng)鏈路重要性評估[J]. 系統(tǒng)工程與電子技術(shù), 2011, 33(10): 2348-2352.

Zhao Bo, Xiao Yu-feng, and Liu Yan. Importance evaluation of communication network links based on OBDD[J]., 2011, 33(10): 2348-2352.

[15] Xing L. An efficient binary-decision-diagram -based approach for network reliability and sensitivity analysis[J].,,--:, 2008, 38(6): 105-115.

[16] Xiao Y, Lin X, Li Y,Evaluate reliability of wireless sensor network with obdd[C]. Proceedings of IEEE International Conference on Communications, Dresden, 2008: 105-115.

熊 飛： 男，1983年生，博士，工程師，研究方向為移動通信技術(shù)、通信網(wǎng)鏈路可靠性研究.

喬 迪： 男，1990年生，碩士，研究方向為網(wǎng)絡(luò)可靠性研究.

王宏祥： 男，1973年生，博士，副教授，研究方向為網(wǎng)絡(luò)可靠性研究.

趙子巖： 男，1975年生，博士，高級工程師，研究方向為網(wǎng)絡(luò)流量、通信網(wǎng)絡(luò)關(guān)鍵技術(shù)研究.

楊 洪： 男，1959年生，教授級高級工程師，研究方向為應急通信、軟交換、網(wǎng)絡(luò)安全研究.

沈 亮： 男，1969年生，教授級高級工程師，研究方向為信息通信網(wǎng)絡(luò)架構(gòu)和安全運維研究.

A Novel Network Reliability Evaluating Algorithm with Ordered Binary Decision Diagram Based on Boolean Function

Xiong Fei①Q(mào)iao Di②Wang Hong-xiang②Zhao Zi-yan①Yang Hong①Shen Liang①

①(&.,,100761,)②(,,100876,)

Ordered Binary Decision Diagram (OBDD) is commonly used in network reliability calculation. When evaluating the network reliability based on OBDD, computation time mainly depends on the size of the operating OBDD, which mostly relies on the variable ordering of OBDD. An algorithm is called BF-OBDD which is considered as the Boolean Function-OBDD, and it is the optimization algorithm for computing the reliability of the network. This paper shows that the reliability of network can be improved considerably by using of the proposed BF-OBDD algorithm. The experimental results demonstrate that the improved algorithm has less OBDD node numbers which cost less time when calculating the network reliability.

Computer networks; Reliability; Network topology; Ordered Binary Decision Diagram (OBDD); Variable order; Boolean function

TN915

A

1009-5896(2014)11-2786-05

10.3724/SP.J.1146.2014.00176

熊飛 xiongfei@sgcc.com.cn

2014-01-26收到，2014-05-15改回

國家863計劃項目(2012AA011302)，國家科技重大專項(2012ZX 03003007)和國家電網(wǎng)公司科技項目(SGIT2012335)資助課題