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

潘竹生，莫毓昌，趙建民

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

0 引言

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

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

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

本文在實(shí)現(xiàn)基于邊的廣度優(yōu)先遍歷和深度優(yōu)先遍歷啟發(fā)性排序策略的基礎(chǔ)上，針對(duì)規(guī)則網(wǎng)絡(luò)比較分析了這2 種啟發(fā)性邊排序策略的性能表現(xiàn)，并通過實(shí)驗(yàn)指出2 種策略的性能特性和適用環(huán)境，為不同應(yīng)用現(xiàn)場(chǎng)設(shè)計(jì)最優(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)化成對(duì)應(yīng)的BDD.因此，使用BDD 分析網(wǎng)絡(luò)可靠度時(shí)，首先需要對(duì)網(wǎng)絡(luò)中的邊(網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接)依據(jù)某種策略排序，然后將網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接路徑轉(zhuǎn)換成以BDD 形式表示的路徑函數(shù)，最后在該路徑函數(shù)上分析可靠度，具體步驟如下:

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

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

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

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

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

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

2 邊排序策略

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

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

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

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

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

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

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

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

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

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

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

3 策略性能比較

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

比較2 種不同網(wǎng)絡(luò)結(jié)構(gòu)(3* N 和N* 3)在相同邊排序策略下對(duì)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)對(duì)BDD 尺度的影響

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

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

1)對(duì)于3* N 型和N* 3 型網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)規(guī)模較小時(shí)(N ＜5)，2 種策略下，BDD 尺度相近(或深度優(yōu)先更小)，當(dāng)網(wǎng)絡(luò)規(guī)模進(jìn)一步加大，廣度優(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ù)級(jí)增長，N* 3 型網(wǎng)絡(luò)增幅較大，性能最差.

4 結(jié)語

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