一種用于BDD網絡可靠性分析的啟發式排序新方法

潘竹生， 李聞白， 林飛龍

(1.浙江師范大學 數學與計算機科學學院,浙江 金華 321004;2.浙江師范大學 經濟與管理學院,浙江 金華 321004)

0 引 言

二元決策圖即BDD(binary decision diagram)及其擴展型在電路驗證[1]、緊湊馬爾可夫鏈表達式[2-4]、編程中對大型元組集的有效處理[5]、符號模型檢驗[6-8]和各種類型系統[9-11]的可靠性分析等領域有著廣泛的應用，因此，快速高效地構建BDD模型成為最近20年的一個研究熱點，內容主要包括變量排序研究和模型構建方法研究.

變量排序[12]嚴重影響BDD模型大小.在極端情況下，不同質量的變量排序對應的BDD模型大小可以跨越幾個數量級[13].所以，尋找優質排序是一個非常重要的問題.然而，尋找最優排序是一個NP完全問題[13].在實際應用中，只能采用啟發式排序[14-15]策略，如基于廣度優先搜索BFS(breadth-first-search)和深度優先搜索DFS(depth-first-search)[16-18]的排序.在網絡可靠性分析領域，文獻[19]指出，對于規則網絡,BFS策略優于DFS.文獻[15,17]指出，對于一般網絡,BFS具有較好性能；就BFS排序策略而言，排序起點對排序結果有重大影響.文獻[20]指出：1)源點(默認排序起點)一般不是最佳排序起點；2)Square Lattice網絡的最佳排序起點分布在4個角上.在考慮節點和邊都可能隨機失效的情況下，文獻[21-22]提出了新的啟發式排序策略，在規則網絡中的大量實驗表明，新的策略優于BFS和DFS.文獻[23]針對帶社區結構的物聯網，提出帶權重的BFS和DFS排序.文獻[24]結合網絡結構特征提出了一種排序策略選擇方法，用于構建精簡BDD模型.文獻[25]重點研究指標數據，用于指導設計排序策略.在模型構建方面，Kuo等[15]提出了基于邊擴展圖的自底向上的BDD構建方法;Hardy等[17]提出了基于邊界集的自頂向下的BDD構建方法.這2種方法適合處理節點完好的網絡可靠性分析.在節點和邊都可能隨機獨立失效時，Pan等[26]提出了基于依賴集的模型構建方法;Kawahara 等[27]考慮節點失效時依賴于該節點的邊都失效的實際提出了更為高效的BDD構建方法;Yeh等[28]提出二叉加法樹(binary addition tree,BAT)算法評估二元狀態網絡的可靠性.

最近20年，盡管學界在BDD模型構建方法上取得了一些進展，但在啟發式排序上鮮有成果.本文考慮節點完好的應用場景，從分析基于邊界集的BDD模型構建方法入手，分析影響BDD模型大小的因素，研究排序起點選擇方法和啟發式排序策略，建立新的啟發式排序方法.

1 可靠性網絡和BDD模型

1.1 可靠性網絡

可靠性網絡通常表示為一個無向圖G=(V,E,K)，其中V是節點集，表示網絡系統中的實體；E是邊集，表示實體之間的連接；K?V是網絡中的關鍵節點(|K|≥2)，表示網絡中的關鍵實體,|K|和|V|分別表示關鍵節點集K和節點集V的大小.所謂網絡可靠性，是指K中節點能正常通信(如存在一條連通路徑)的可能性.根據集合K大小的不同，將可靠性網絡分為3類：2-端可靠性網絡(|K|=2)、K-端可靠性網絡(2<|K|<|V|)和All-端可靠性網絡(|K|=|V|).本文考慮2-端可靠性網絡，也稱(s,t)網絡，其中稱s為源點，t為匯點，研究節點s和t之間的連通性.如圖1所示，其網絡可表示為G=({s,n1,n2,t}，{e1,e2,e3,e4,e5}，{s,t}).

圖1 橋接網絡

1.2 BDD模型

在可靠性網絡中，網絡可靠性問題可以表示為一個等價的布爾函數.BDD是一個有向無環圖，通常用來編碼布爾函數.基本編碼規則如圖2所示，其中x為函數f的一個布爾變量，表示網絡中的一個部件，fx=0是x=0時的孩子節點(記為左孩子)，表示部件失效時的布爾函數，fx=1是x=1時的孩子節點(記為右孩子)，表示部件正常工作時的布爾函數.即根據部件失效與否，函數f可以表示為f=p·fx=1+(1-p)·fx=0.其中:p表示部件x正常工作時的概率；fx=0和fx=1仍為布爾函數，可以持續向下分解，直到所有部件考慮完畢，從而得到最終的BDD模型.

圖2 BDD和布爾函數f=p·fx=1+(1-p)·fx=0

顯然，在自頂向下的分解過程中，所考慮部件的出現順序可以不同.設有布爾函數f=x1x2+x3x4+x5x6，若按部件序x1

(a)低質量排序 (b)高質量排序

2 基于邊界集的BDD模型構建方法

2.1 邊界集和分區

定義1(邊界集，boundary set) 對于網絡G=(V,E,K),假設用邊序o=e1≤e2≤…≤e|E|,ei∈E,i∈[1,|E|]來指導生成BDD模型，|E|表示邊的數目.當處理第k條邊ek時，對應的邊界集Fk可定義為

Fk={v|v是ei和ej的一個公共端點，并且ei∈Ek和ej∈E-Ek}，Ek={e1,e2,…,ek}.

集合Fi中節點的數目定義為第i層邊界集的長度，記Fmax為最大邊界集的長度，即

Fmax= max{|Fi|，i= 1,2,3，…,|E|}.

表1 排序o的各層邊界集及邊界集長度

如圖1所示的橋接網絡，設有邊序o=e1≤e2≤e3≤e4≤e5，則各層邊界集及邊界集長度如表1所示.因此，最大邊界集長度Fmax為2.

定義2(分區，partition) 在用BDD編碼網絡時，需要建立分區[15]來標記網絡特征.分區由若干塊構成，塊由邊界集中的節點構成.具體構建規則如下：

1)若邊界集中的2個節點vi和vj通過已經處理的邊能夠連接在一起，則它們在同一塊中，記為[vi，vj]，否則處在不同的塊中，記為[vi][vj]；

2)若某一塊中的節點通過已經處理的邊能夠和至少1個來自集合K的節點連通，則該塊標記為帶“*”(稱為塊加星操作),如[vi，vj]*表示塊[vi，vj]與集合K中的某點連通.

分區能有效表征網絡[15]，如圖1所示網絡，約定邊序o=e1≤e2≤e3≤e4≤e5.顯然，考慮邊e1時，分區[s,n1]*和[s]*[n1]有效區分了e1正常工作和失效這2種狀態，即表征了對應的子網，如圖4所示.另外，利用分區標識技術，還可以高效地識別出其中存在的同構，如圖4中L2所示，基于分區[n1,n2]*,[n1]*[n2] 和[n1][n2]*,在邊e3正常工作時，都得到新的分區[n1,n2]*，識別出了同構，這也符合實際.在同一邊序下，分區相同的2個子網同構.

圖4 邊界集、分區和BDD模型生成過程

2.2 BDD模型構建

引入分區后，可以通過操作分區，在指定邊序的約束下，按自上向下方式一層一層構建BDD模型.具體算法如下：

算法1

1)創建BDD模型的根節點分區root，初始化為空

2)初始化哈希表hash,用于記錄當前層的所有可能分區,初始化隊列preQueue，curQueue用于存放分區

3)preQueue.push(root)

4)fork=1 to |E| do

5) while preQueue do

6)Pk=preQueue.pop()

7)tp=genThenPartition(Pk,ek)

8)ep=genElsePartition(Pk,ek)

9) if所有關鍵點已在tp的一個塊中thenPk.getBDD().then = true

10) else if 有一個關鍵點被孤立thenPk.getBDD().then = false

11) else

12) iftp不在哈希表hash中 then

13) curQueue.push(tp)

14) hash.put(tp)

15)Pk.getBDD().then=tp.getBDD()

16) if所有關鍵點已在ep的一個塊中thenPk.getBDD().else = true

17) else if 有一個關鍵點被孤立thenPk.getBDD().else = false

18) else

19) ifep不在哈希表hash中 then

20) curQueue.push(ep)

21) hash.put(ep)

22)Pk.getBDD().else=ep.getBDD()

23) end while

24) preQueue=curQueue;

25) curQueue.clear()

26)end for

27)return root

如圖1所示的橋接網絡，約定邊序為e1

第1層，邊為e1=(s,n1)，其中“s”為關鍵點，邊界集F1={s,n1}.當邊正常工作時，節點“s”和“n1”合并到一個塊，得分區[s,n1]*；當邊失效時，節點“s”和“n1”分屬2個塊，得分區[s]*[n1].

第2層，邊為e2=(s,n2),由于關聯于節點“s”的邊即將全部處理完成，所以邊界集F2={n1,n2}.考慮第1層分區[s,n1]*,當邊e2正常工作時，得分區[n1,n2]*,失效時，得分區[n1]*[n2];考慮分區[s]*[n1],當邊e2正常工作時，得分區[n1][n2]*, 失效時，關鍵節點“s”被隔離，所以指向false.

第3層，邊為e3=(1,n2),邊界集F3={n1,n2}.當邊正常工作時，基于第2層的各分區都生成了相同的分區[n1,n2]*,所以共享之；當邊失效時，分別指向各自的分區[n1,n2]*,[n1]*[n2]和[n1][n2]*.

利用相同的規則，計算邊界集，生成分區，得到完成的BDD模型.

2.3 BDD模型大小分析

分區有效表征了網絡狀態，如圖4所示，每個網絡代表一個BDD節點.因此，計算出分區的數目，也就得到了BDD模型的大小.首先從邊界集入手，討論邊界集大小與分區數目的關系.根據定義2，在給定第i層邊界集Fi和不考慮塊加“*”操作的前提下，包含j個塊的分區數目是一個第二類斯特林數S(|Fi|,j),而包含任意塊數的分區總數是一個貝爾數B|Fi|.表2列舉了邊界集大小和貝爾數之間的關系.

(1)

(2)

表2 邊界集大小、斯特林數和貝爾數之間的關系

顯然，隨著邊界集的增大，貝爾數急劇增大，且速率遠大于成倍增長速率.若能控制住邊界集大小，就能有效控制住貝爾數.

定義3(BDD寬度W) 設用Wi表示第i層BDD節點數目的最大理論值，則BDD模型的寬度W定義為

(3)

考慮塊加“*”操作.在可靠性網絡G=(V,E,K)中，由于最多有|K|個關鍵節點，所以分區中最多包含|K|個帶“*”塊.關鍵節點單獨成塊時，取得最大值|K|.此時，第i層邊界集Fi所對應的分區數目，即第i層BDD節點數目的最大理論值Wi可以按式(4)計算.

(4)

例如，邊界集F={1,2,3}且|K|=2時的所有可能分區：[1,2,3],[1,2,3]*,[1,2][3],[1,2]*[3],[1,2][3]*,[1,2]*[3]*,[1,3][2],[1,3]*[2],[1,3][2]*,[1,3]*[2]*,[1][2,3],[1]*[2,3],[1][2,3]*,[1]*[2,3]*,[1][2][3],[1]*[2][3],[1][2]*[3],[1][2][3]*,[1]*[2]*[3],[1]*[2][3]*,[1][2]*[3]*,[1]*[2]*[3]*.

顯然，引入加“*”操作后，分區總數目大大增加.

比較式(2)和式(4)，引入帶“*”操作后，隨著邊界集的增大，BDD節點數目的最大理論值以更大的速率快速增長.從最大理論值角度看，在排序過程中，越晚引入關鍵節點到邊界集就越有利于控制最大理論值.

另一方面，深入研究本文所述BDD模型的生成過程，發現某一層實際BDD節點數目的實際值和已經處理的邊數及網絡結構特征有關.最好情況，第i層BDD節點數為1；最壞情況，第i層BDD節點數為2i，如圖5所示.由于同構子網的存在及網絡結構特征的差異，一般情況下，第i層BDD節點數目的實際值大于1而小于2i，如圖4所示.所以，如果能找到一種排序,使得每層邊界集足夠小，從而使得BDD節點數目最大理論值大大小于該層BDD數目的最壞情況，那么此排序將會是一種優秀的排序.

(a)最好情況 (b)最壞情況

3 基于邊界集的啟發式排序策略

基于邊界集的啟發式排序采用貪心策略，在排序過程中盡可能優先選擇使邊界集足夠小的邊.

3.1 排序策略設計

根據本文的BDD模型構建方法，第k層分區以第k-1層分區為基礎，結合第k條邊ek在網絡中的連接情況而建立，即由Fk-1構建Fk.為表述方便，設邊ek的2個端點分別為u和v，根據u和v在Fk-1和Fk的存在性得邊界集大小變化的所有情況，見表3.

表3 邊界集大小變化

由表3所示，新的邊界集Fk，其大小滿足式(5)，且不失一般性.所以，在設計邊選擇策略時，可以優先考慮2個端點都在當前邊界集中的邊，然后考慮有一個端點不在邊界集中的邊，這樣才能使當前邊界集最小.2個端點都不在邊界集的情形不用考慮，因為該情形下不可能得到最小的邊界集.

|Fk-1|-2≤|Fk|≤|Fk-1|+2.

(5)

策略1優先選擇2個端點u和v都在邊界集中的邊.若存在多條滿足條件的邊，則選擇節點度和小的邊.若節點度和也相同，則先選擇與先進入邊界集的節點相關聯的邊.如圖6所示，候選邊ex和ey，由于邊ex的節點度和小于邊ey，所以邊ex先排.

策略2選擇一個端點u在邊界集中的邊，且該端點度最小，另一端點v有更多的邊關聯于當前邊界集.否則，選擇邊e=(u，v)，u在邊界集中，v有最小的度.如圖7所示，節點i和w的度最小，但節點y有2條邊關聯于邊界集，所以邊ey先排.之后節點y加入新的邊界集，邊ez的選擇適用策略1.

圖6 策略1示意圖 圖7 策略2示意圖

關鍵節點的引入時機也是一個重要影響因素，所以當候選邊關聯于關鍵節點時，該邊延遲排序.

3.2 排序起點選擇

基于邊界集的啟發式排序，其最終排序結果除了和排序策略相關外，還與排序的初始條件有關.

定義4(邊界集總長度) 對于給定K-端網絡G=(V,E,K),設有一個邊序列o=e1≤e2≤e3≤…≤e|E|,ci∈E,i∈[1,|E|]，則關于序列o的邊界集總長度(記為LTBS(o))定義為

其中,|Fi|為序列o的第i層邊界集長度.在確定排序起點之前，先計算不同排序起點的邊界集總長度LTBS(O(vi)),其中O(vi)表示以vi為排序起點的一種排序結果，選取邊界集總長度值最小的那個節點作為排序起點.NS(V)表示在節點集V中取排序起點.

NS(V)=vi?LTBS(O(vi))=min{LTBS(O(vi)),vi∈V}.

3.3 基于邊界集的啟發式排序算法

基于邊界集的啟發式排序主要包含2個部分：1)排序起點選擇；2)排序過程推進.在過程推進中，采用貪心策略，確保每層生成的邊界集長度盡可能小.具體算法如下：

算法2

1)選擇一個節點v∈V，節點v擁有最小的邊界集總長度

2)初始化邊界集F0={v}

3)whileFk≠? do

//策略1：

4) for alle(u,v)∈E-Ek,u,v∈Fkdo

5) order.add(e),G.delete(e),update(Fk)

6) end for

//策略2：

7) 選擇一點u∈Fk且u的度最小，在u的鄰接點中選擇一點v，且v擁有最多的未排序邊關聯于Fk

8) order.add(e(u，v)),G.delete(e(u，v)),update(Fk)

9) 選擇一點u∈Fk且deg(u)最小，在u的鄰接點中選擇一點v，且v的度最小

10) order.add(e(u，v)),G.delete(e(u，v)),update(Fk)

11) end while

12) return order

4 實驗和結論

選擇星型網絡和De-Bruijn網絡分別驗證本文提出的啟發式排序策略和排序起點選擇方法，搜集相關文獻的樣本網絡,用來比較常用啟發式排序的性能，并在工程實際網絡中進一步驗證本文提出的啟發式排序方法.

4.1 Star網絡

Star網絡(見圖8)中的節點(除去中心節點)具有相似的結構特征，可以最大限度地降低對排序策略的影響.為了更好地說明排序策略，建立了4類排序：1)以快速最大化邊界集(MaxBS)的方式建立邊排序，即優先選擇節點不在邊界集中的邊進行排序；2)以深度優先搜索(DFS)方式建立邊排序，理論上邊界集長度每次增1，直到所有節點都加入邊界集；3)以廣度優先搜索方式(BFS)建立邊排序；4)以最小化邊界集方式(本文方法)建立邊排序.

圖8 Star網絡

實驗步驟如下，實驗結果如表4所示.

1)隨機選擇一個排序起點，根據4種不同排序策略建立邊排序；

2)隨機選擇節點對，建立BDD模型，計算BDD模型大小和BDD寬度.

表4 Star網絡的BDD模型大小和寬度

4種排序中，MaxBS的排序結果與排序起點無關，其余3種與排序起點的選擇有關.在相同的排序策略下，可以建立不同的排序結果，而不同的排序結果指導生成不同大小的BDD模型，如表4，即使求解相同的問題(計算節點對{0,7}的可靠度)，也能生成不同大小的BDD模型.比較BDD模型寬度和模型大小的關系，所得結果見圖9.由圖9可得，對于不同的排序策略，當BDD模型寬度較小時，對應的模型大小也較??；反之，當模型寬度較大時，模型大小較大.控制BDD模型寬度，有利于控制BDD模型大小.

(a)模型大小 (b)模型寬度

4.2 De-Bruijn網絡

在De-Bruijn網絡(見圖10)中，不同排序起點有不同的邊界集總長度.采用本文提出的啟發式排序策略時，各排序起點對應的邊界集總長度如表5所示，節點“0”“1”和“8”擁有最小的邊界集總長度.

圖10 De-Bruijn網絡(Order=4)

表5 各排序起點的邊界集總長度

以下實驗說明選擇排序起點的必要性，實驗過程如下，實驗數據如表6、表7所示.

表6 BDD模型大小位序分布 表7 邊界集總長度大小位序分布

1)采用本文啟發式排序策略，根據不同排序起點建立不同的邊排序(共16種)；

2)根據16種排序分別為每個節點對(共120對)生成等價的BDD模型；

3)選擇擁有最小邊界集總長度的節點作為起點時，統計對應的BDD模型大小位序的分布；

4)選定最小BDD模型時，統計邊界集總長度大小的分布.

由表6和表7看出：當選擇擁有最小邊界集總長度的節點作為排序起點時，最小BDD模型占18.6%，前4小BDD模型占比高達91.7%.對應地，當取最小BDD模型時，最小邊界集總長度占55.8%，前4小BDD模型占88.3%.由此可得，選擇擁有最小邊界集總長度的節點作為排序起點時，可以大概率提升排序質量，從而指導生成更小的BDD模型.

4.3 樣本網絡

本文在相關文獻中搜集了22個2-端可靠性網絡，如圖11所示，采用基于邊界集的BDD構建方法，結合本文提出的啟發式排序，生成等價BDD模型，計算可靠度值和模型大小，實驗結果如表8所示，其中DFS和BFS的數據來自文獻[15]，“*”表示原BDD構建方法無法生成BDD模型.

圖11 樣本網絡

表8 DFS,BFS和本文方法性能比較

表8數據表明，BFS略優于DFS，而本文提出的啟發式排序全面優于BFS和DFS.

5 結 語

BDD模型大小嚴重影響基于BDD的網絡可靠性分析方法性能，而BDD模型大小由所采用的變量大小決定，所以尋找優質排序是所有基于BDD分析方法的核心問題.本文從研究基于邊界集的BDD構建方法入手，深入分析各層BDD節點的產生過程，總結啟發式數據：BDD寬度和邊界集總長度，提出排序起點選擇方法和盡可能確保BDD寬度小的排序策略.大量實驗表明，本文提出的啟發式排序方法優于BFS，具有很好的應用價值.在今后的工作中，將進一步研究關鍵節點和網絡結構特征對排序質量的影響，尋找更為優秀的啟發式排序.