網(wǎng)絡(luò)可靠度BDD 分析中2 種邊排序策略的性能比較＊

潘竹生，莫毓昌，趙建民

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

0 引言

隨著人類對交通網(wǎng)、通信網(wǎng)、互聯(lián)網(wǎng)、電力網(wǎng)等網(wǎng)絡(luò)依賴度的日漸增加，網(wǎng)絡(luò)可靠度分析已成為一個倍受關(guān)注的熱點.各種分析方法應(yīng)運而生，其中以基于二元決策圖(BDD，Binary Decision Diagram)［1］的可靠度分析方法最為著名，典型的有Aralia［2］和Metaprime［3］.與普通方法相比，使用這些工具進行可靠度分析時，其精度更高、速度更快.

BDD 作為一種全新的數(shù)據(jù)結(jié)構(gòu)，通常用來定義、分析、測試和操縱大型布爾函數(shù)［4］，其因操縱布爾函數(shù)的高效性被廣泛應(yīng)用于網(wǎng)絡(luò)可靠度分析中，具體包含邊排序、BDD 生成［5-8］和可靠度評估3 個步驟.其中，BDD 生成和可靠度評估的計算復(fù)雜度和BDD 尺度線性相關(guān)，而BDD 尺度取決于邊排序.在不同的邊排序下，BDD 尺度在n 和2n-1 之間發(fā)生變化，跨越幾個數(shù)量級［9］.因此，設(shè)計合理的邊排序策略，解決最佳邊排序問題，是BDD 分析方法研究的核心問題.

通常情況下，尋找最佳排序是一個NP 完全問題［10］.在已有研究中，以Friedman 等［11］提出的最優(yōu)變量排序算法性能最佳，其時間復(fù)雜度為O(n2·3n)，n 為變量的數(shù)目.在網(wǎng)絡(luò)可靠度分析中，n 是指網(wǎng)絡(luò)的邊數(shù).由于隨著n 的增大，排序時間呈指數(shù)級增長，因此，在實際的基于BDD 的故障樹分析［12-13］中，往往采用樹遍歷啟發(fā)性策略快速獲得(近似)最優(yōu)變量排序;在基于BDD 的網(wǎng)絡(luò)可靠度分析［6-8，14］中，多以廣度(或深度)優(yōu)先遍歷來生成邊排序.但在已有研究中沒有比較不同排序策略之間的性能差別和不同排序策略的適用環(huán)境.

本文在實現(xiàn)基于邊的廣度優(yōu)先遍歷和深度優(yōu)先遍歷啟發(fā)性排序策略的基礎(chǔ)上，針對規(guī)則網(wǎng)絡(luò)比較分析了這2 種啟發(fā)性邊排序策略的性能表現(xiàn)，并通過實驗指出2 種策略的性能特性和適用環(huán)境，為不同應(yīng)用現(xiàn)場設(shè)計最優(yōu)啟發(fā)性邊排序策略提供重要參考依據(jù).

1 網(wǎng)絡(luò)可靠度的BDD 分析

BDD 基于香農(nóng)分解，設(shè)f(x1，x2，…，xn)是布爾變量集合X 上的布爾函數(shù)，xi是X 上的變量，則依據(jù)香農(nóng)分解，函數(shù)f(x1，x2，…，xn)可以寫成

式(1)中:f1(x1，x2，…，xn)≡fxi=1(x1，x2，…，xn);f0(x1，x2，…，xn)≡fxi=0(x1，x2，…，xn);f1和f0不依賴變量xi.在給定的變量排序下，遞歸使用香農(nóng)分解，布爾函數(shù)就可轉(zhuǎn)化成對應(yīng)的BDD.因此，使用BDD 分析網(wǎng)絡(luò)可靠度時，首先需要對網(wǎng)絡(luò)中的邊(網(wǎng)絡(luò)節(jié)點之間的連接)依據(jù)某種策略排序，然后將網(wǎng)絡(luò)節(jié)點之間的連接路徑轉(zhuǎn)換成以BDD 形式表示的路徑函數(shù)，最后在該路徑函數(shù)上分析可靠度，具體步驟如下:

1)選擇合適的邊排序，邊排序的質(zhì)量將嚴(yán)重影響B(tài)DD 尺度，進而影響算法分析性能.

2)使用BDD 構(gòu)建路徑函數(shù)，其主要思想為:從源點S 開始遞歸遍歷整個網(wǎng)絡(luò)，遍歷的同時構(gòu)造相應(yīng)子網(wǎng)，直到到達匯點T.具體構(gòu)建過程為:設(shè)邊xi(i=1，2，…，k)為給定網(wǎng)絡(luò)G 中與源點S 相連的第i 條邊，分別沿著k 條邊遍歷網(wǎng)絡(luò)G，并構(gòu)造對應(yīng)子網(wǎng)G* xi(i=1，2，…，k).子網(wǎng)G* xi的構(gòu)造規(guī)則是網(wǎng)絡(luò)G從源點S 沿邊xi(i=1，2，…，k)收縮成一個節(jié)點，并作為新的源點，同時刪除所有與原先源點S 連接的邊，得到k 個子網(wǎng)G* xi(i=1，2，…，k).將得到的k 個子網(wǎng)分別作為網(wǎng)絡(luò)G 沿邊xi(i=1，2，…，k)的孩子節(jié)點，構(gòu)成圍繞S 節(jié)點的邊擴展圖.此時，網(wǎng)絡(luò)G 的路徑函數(shù)可以表示為

式(2)中:PF(X)表示網(wǎng)絡(luò)G 的路徑函數(shù);X 為網(wǎng)絡(luò)G 的邊集合.

對于每一個已構(gòu)造的子網(wǎng)G* xi，重復(fù)執(zhí)行步驟1)，直到源點S 和匯點T 合并，此時返回邏輯真值.通過遞歸地復(fù)合中間路徑函數(shù)的結(jié)果，得到給定網(wǎng)絡(luò)G 的最終路徑函數(shù).

3)從BDD 表示的路徑函數(shù)中，依據(jù)以下公式遞歸地計算網(wǎng)絡(luò)可靠度:

式(3)中:xi為邊排序中的最先邊;PF 根據(jù)xi分解成2 個不相交的子集PF(xi=1)和PF(xi=0);p(xi)為邊xi有效工作的概率.

2 邊排序策略

2.1 廣度優(yōu)先邊排序策略

基于邊的廣度優(yōu)先邊排序策略的基本思想為:對于給定的網(wǎng)絡(luò)G(邊的序列值index 初始化為0)，將連接到源點S 的邊xi(i=1，2，3，…，k)依次插入隊列，設(shè)xi依附的2 個端點為S 和V.取出隊頭元素邊(U，V)并修改其序列值為index++，做好“已訪問”標(biāo)志后，從隊列中刪除該邊(U，V).刪除元素后，如果隊列為空，則遍歷完成，得到基于廣度優(yōu)先策略的邊排序;否則，將連接到端點V 且尚未被訪問的所有邊(V，Wi)(i=1，2，…，h)插入隊尾.重復(fù)入隊和出隊操作，直到隊列為空.

廣度優(yōu)先邊排序的實現(xiàn)算法如下:

由以上算法可知，廣度優(yōu)先邊排序策略和圖論中經(jīng)典的節(jié)點廣度優(yōu)先遍歷算法相比，前者排序的是邊且遍歷起點為與源點S 連接的第1 條邊，而后者排序的是節(jié)點且排序起點為圖中的任意節(jié)點.

對于圖1 中的網(wǎng)絡(luò)G，假設(shè)最頂層節(jié)點為S，則其對應(yīng)的廣度優(yōu)先邊排序可以為x1，x2，x3，x4，x5，x6，x7，x9，x10，x8，與之對應(yīng)的廣度優(yōu)先節(jié)點排序為S，n1，n2，n3，T，n4，n5.

圖1 網(wǎng)絡(luò)G

2.2 深度優(yōu)先邊排序策略

基于邊的深度優(yōu)先邊排序策略的基本思想為:對于給定的網(wǎng)絡(luò)G(邊的序列值index 初始化為0)，將源點S 進棧并作好進棧標(biāo)志，重復(fù)下列操作直到棧為空:1)取棧頂元素U;2)棧頂元素U 存在鄰接點V，且邊(U，V)未被訪問，則修改邊(U，V)的序列值為index++，并設(shè)“已訪問”標(biāo)志，如果V 是匯點或V 已在棧中，則繼續(xù)檢查與U 鄰接且尚未訪問的邊(U，W)，直到所有邊標(biāo)記為訪問;否則將V 進棧;如果與U 鄰接的邊都已訪問則退棧.

深度優(yōu)先邊排序的實現(xiàn)算法如下:

由以上算法可知，深度優(yōu)先邊排序策略和圖論中經(jīng)典的節(jié)點深度優(yōu)先遍歷算法相比，前者對邊進行深度優(yōu)先遍歷，后者則是對節(jié)點進行深度優(yōu)先遍歷;前者在深度優(yōu)先遍歷邊時，邊只被訪問1 次，但被邊所依附的節(jié)點可能被訪問多次(當(dāng)節(jié)點有多條邊相連時)，后者其節(jié)點卻只被訪問1 次;前者遍歷的起點為與源點S 連接的第1 條邊，后者是網(wǎng)絡(luò)中的任意節(jié)點.

對于圖1 中的網(wǎng)絡(luò)G，假設(shè)最頂層節(jié)點為S，則深度優(yōu)先邊排序的結(jié)果為x1，x4，x9，x5，x2，x3，x6，x7，x8，x10，對應(yīng)的深度優(yōu)先節(jié)點排序為S，n1，T，n4，n2，n3，n5.

3 策略性能比較

為了方便地比較2 種策略下的算法性能，本文選用N* N 型和M* N 型2 種網(wǎng)絡(luò)，求解兩端網(wǎng)絡(luò)可靠度，且假設(shè)源點S 和匯點T 在規(guī)則網(wǎng)絡(luò)的對角線端點上.其中，N 和M 分別代表規(guī)則網(wǎng)絡(luò)中行和列的節(jié)點數(shù).N* N 表示橫向和縱向都有N 個節(jié)點構(gòu)成的規(guī)則網(wǎng)絡(luò)，M* N 表示該規(guī)則網(wǎng)絡(luò)有M 行N 列，每行有N 個網(wǎng)絡(luò)節(jié)點，每列有M 個網(wǎng)絡(luò)節(jié)點.并假設(shè)網(wǎng)絡(luò)節(jié)點完好(即節(jié)點不失效)，邊失效隨機獨立且失效概率取值為0.1.

3.1 N* N 型網(wǎng)絡(luò)性能分析

針對N* N 型網(wǎng)絡(luò)，分別采用BFS 和DFS 邊排序進行可靠度測試，統(tǒng)計它們生成的可靠度、運行時間、BDD 尺度、BDD 操作和最小路集等算法性能指標(biāo).實驗結(jié)果如表1 所示，其中:Time 表示執(zhí)行1 次CPU 所花費的時間(多次執(zhí)行有相似的多個值);BDDsize 表示BDD 尺度，即BDD 節(jié)點數(shù)目;BDDOp 表示BDD 操作(and 或or)數(shù)目，即BDD_and 和BDD_or 操作數(shù)目之和;MP 表示最小路徑數(shù)目;overflow 表示程序運行溢出.表2 為主要性能指標(biāo)的加速比，計算辦法為相鄰網(wǎng)絡(luò)中的高階網(wǎng)絡(luò)指標(biāo)數(shù)據(jù)除以低階網(wǎng)絡(luò)對應(yīng)的指標(biāo)數(shù)據(jù)，如運行時間加速比為Time(n +1)/Time(n)，其中，n 為網(wǎng)絡(luò)的階，代表規(guī)則網(wǎng)絡(luò)行(或列)的節(jié)點數(shù)目.

表1 N* N 型網(wǎng)絡(luò)可靠度性能指標(biāo)數(shù)據(jù)

通過對表1 及表2 中數(shù)據(jù)的分析，針對2 種策略的性能比較，可以總結(jié)出如下結(jié)論:

1)小規(guī)模網(wǎng)絡(luò)(如2* 2，3* 3)中，深度優(yōu)先策略具有較好性能，但隨著網(wǎng)絡(luò)規(guī)模的增大，BDD 尺度急劇膨脹，BDD 操作呈爆炸式增長，時空性能較差.

2)廣度優(yōu)先遍歷策略下，隨著N 值的增大，運行時間增速超過10 倍，BDD 節(jié)點數(shù)呈線性增長且增速遞減，BDD 操作與運行時間有相似的變化趨勢;在深度優(yōu)先策略下，隨著N 的增大，運行時間接近(N+1)2倍增長，BDD 節(jié)點數(shù)呈N2倍增長，BDD 操作增速比運行時間的增速還快.

表2 N* N 型網(wǎng)絡(luò)主要性能指標(biāo)比較

3.2 M* N 型網(wǎng)絡(luò)性能分析

對于3* N 型和N* 3 型網(wǎng)絡(luò)，同樣采用廣度優(yōu)先策略和深度優(yōu)先策略邊排序?qū)λ惴ㄖ饕阅苤笜?biāo)進行測試，實驗結(jié)果如表3、表4 所示.其中，比較重要的2 類性能指標(biāo)數(shù)據(jù)，即運行時間和BDD 尺度的圖形化描述如圖2 和圖3 所示.

根據(jù)表3 和圖2 中數(shù)據(jù)的變化趨勢，發(fā)現(xiàn):對于3* N 型網(wǎng)絡(luò)，隨著列數(shù)N 的增大，在廣度優(yōu)先策略下，運行時間呈2.1 倍增長，BDD 尺度均勻增加(N 增1，BDD 節(jié)點數(shù)增加68)，BDD 操作呈線性增加，增速按約1%遞減;在深度優(yōu)先策略下，運行時間呈3 倍增長，BDD 尺度呈3 倍增加，BDD 操作近似3 倍增長.當(dāng)N=18 時，采用廣度優(yōu)先邊排序策略，成功生成BDD 并得到解，而采用深度優(yōu)先邊排序策略，BDD生成算法運行溢出.

圖2 3* N 型網(wǎng)絡(luò)CPU 運行時間和BDD 尺度比較

圖3 N* 3 型網(wǎng)絡(luò)CPU 運行時間和BDD 尺度比較

表3 3* N 型網(wǎng)絡(luò)可靠度性能指標(biāo)數(shù)據(jù)

分析表4 和圖3 得到:對于N* 3 型網(wǎng)絡(luò)，隨著行數(shù)N 的增大，在廣度優(yōu)先策略下，運行時間呈2.1倍增長，BDD 尺度均勻增加(M 增1，BDD 節(jié)點數(shù)增加30)，BDD 操作數(shù)目呈線性增加，但增速按約1%遞減;在深度優(yōu)先策略下，運行時間呈4 倍增長，BDD 尺度成呈4 倍增加，BDD 操作數(shù)目近似4 倍增長，但增速有微弱遞減的趨勢.當(dāng)N=10 時，采用廣度優(yōu)先邊排序策略，成功生成BDD 并得到解，而采用深度優(yōu)先邊排序策略，BDD 生成算法運行溢出.

比較2 種不同網(wǎng)絡(luò)結(jié)構(gòu)(3* N 和N* 3)在相同邊排序策略下對BDD 尺度的影響，由表3、表4 中的數(shù)據(jù)可得圖4 所示結(jié)果和表5 所示結(jié)論.

表4 N* 3 型網(wǎng)絡(luò)可靠度性能指標(biāo)數(shù)據(jù)

圖4 網(wǎng)絡(luò)結(jié)構(gòu)對BDD 尺度的影響

表5 不同策略在規(guī)則網(wǎng)絡(luò)中的定性描述

分析圖4 得到如下重要結(jié)論，可為設(shè)計更優(yōu)的邊排序策略提供重要參考依據(jù).

1)對于3* N 型和N* 3 型網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(N ＜5)，2 種策略下，BDD 尺度相近(或深度優(yōu)先更小)，當(dāng)網(wǎng)絡(luò)規(guī)模進一步加大，廣度優(yōu)先下的BDD 尺度明顯小于深度優(yōu)先，表現(xiàn)良好性能;

2)廣度優(yōu)先下，BDD 尺度隨網(wǎng)絡(luò)規(guī)模呈模線性增加，N* 3 型網(wǎng)絡(luò)增速較慢，性能最優(yōu);深度優(yōu)先下，BDD 尺度隨網(wǎng)絡(luò)規(guī)模呈指數(shù)級增長，N* 3 型網(wǎng)絡(luò)增幅較大，性能最差.

4 結(jié)語

本文從網(wǎng)絡(luò)可靠度BDD 分析入手，在實現(xiàn)廣度優(yōu)先遍歷和深度優(yōu)先遍歷2 種邊排序策略的基礎(chǔ)上，基于規(guī)則網(wǎng)絡(luò)比較了2 種策略的分析性能.實驗數(shù)據(jù)表明:規(guī)則網(wǎng)絡(luò)中廣度優(yōu)先遍歷策略性能優(yōu)于深度優(yōu)先遍歷策略;當(dāng)M ＞N 時，網(wǎng)絡(luò)M* N 較N* M 具有更優(yōu)性能.該結(jié)果為設(shè)計最優(yōu)的啟發(fā)性邊排序策略提供重要依據(jù).

［1］Akers B.Binary decision diagrams［J］.IEEE Transactions on Computers，1978，C-27(6):509-516.

［2］Groupe Aralia.Computation of prime implicants of a fault tree within Aralia［C］//Proceedings of the european safety and reliability association conference.Bournemouth:European Safety and Reliability Association，1995:190-202.

［3］Coudert O，Madre J C.Fault tree analysis:1020prime implicants and beyond［C］//Proceedings of the annual reliability and maintainability symposium.Atlanta:IEEE，1993:240-245.

［4］Bryant R E.Symbolic boolean manipulation with ordered binary-decision diagrams［J］.ACMComputing Surveys，1992，24(3):293-318.

［5］Kuo S Y，Lu S K，Yeh F M.Determining terminal-pair network reliability based on edge expansion diagrams using OBDD［J］.IEEE Transactions on Reliability，1999，48(3):234-246.

［6］Yeh F M，Lu S K，Kuo S Y.OBDD-based evaluation of k-terminal network reliability［J］.IEEE Transactions Reliability，2002，51(4):443-451.

［7］Kuo S Y，Yeh F M，Lin H Y.Efficient and exact reliabilityevaluation for networks with imperfect vertices［J］.IEEE Transactions 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 Transactions on Reliability，2007，56(3):506-515.

［9］Bryant R E.Graph-based algorithms for boolean function manipulation［J］.IEEE Transactions on Computers，1986，C-35(8):677-691.

［10］Bollig B，Wegener I.Improving the variable ordering of OBDDs is NP-complete［J］.IEEE Transactions on Computers，1996，45(9):993-1002.

［11］Friedman S J，Supowit K J.Finding the optimal variable ordering for binary decision diagrams［J］.IEEE Transactions on Computer，1990，C-39(5):710-713.

［12］Mo Yuchang.Variable ordering to improve BDD analysis of phased mission systems with multimode failures［J］.IEEE Transactions on Reliability，2009，58(1):53-57.

［13］Mo Yuchang.New insights into the BDD-based reliability analysis of phased mission systems［J］.IEEE Transactions on Reliability，2009，58(4):667-678.

［14］Pan Z S，Mo Y C，Zhong F R.Performance improvement of BDD-based network reliability［J］.Computer Engineering ＆ Science，2012，34(9):50-56.