一種用于BDD網(wǎng)絡(luò)可靠性分析的啟發(fā)式排序新方法

潘竹生， 李聞白， 林飛龍

(1.浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,浙江 金華 321004;2.浙江師范大學(xué) 經(jīng)濟(jì)與管理學(xué)院,浙江 金華 321004)

0 引 言

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

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

最近20年，盡管學(xué)界在BDD模型構(gòu)建方法上取得了一些進(jìn)展，但在啟發(fā)式排序上鮮有成果.本文考慮節(jié)點(diǎn)完好的應(yīng)用場(chǎng)景，從分析基于邊界集的BDD模型構(gòu)建方法入手，分析影響B(tài)DD模型大小的因素，研究排序起點(diǎn)選擇方法和啟發(fā)式排序策略，建立新的啟發(fā)式排序方法.

1 可靠性網(wǎng)絡(luò)和BDD模型

1.1 可靠性網(wǎng)絡(luò)

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

圖1 橋接網(wǎng)絡(luò)

1.2 BDD模型

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

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

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

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

2 基于邊界集的BDD模型構(gòu)建方法

2.1 邊界集和分區(qū)

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

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

集合Fi中節(jié)點(diǎn)的數(shù)目定義為第i層邊界集的長度，記Fmax為最大邊界集的長度，即

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

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

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

定義2(分區(qū)，partition) 在用BDD編碼網(wǎng)絡(luò)時(shí)，需要建立分區(qū)[15]來標(biāo)記網(wǎng)絡(luò)特征.分區(qū)由若干塊構(gòu)成，塊由邊界集中的節(jié)點(diǎn)構(gòu)成.具體構(gòu)建規(guī)則如下：

1)若邊界集中的2個(gè)節(jié)點(diǎn)vi和vj通過已經(jīng)處理的邊能夠連接在一起，則它們?cè)谕粔K中，記為[vi，vj]，否則處在不同的塊中，記為[vi][vj]；

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

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

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

2.2 BDD模型構(gòu)建

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

算法1

1)創(chuàng)建BDD模型的根節(jié)點(diǎn)分區(qū)root，初始化為空

2)初始化哈希表hash,用于記錄當(dāng)前層的所有可能分區(qū),初始化隊(duì)列preQueue，curQueue用于存放分區(qū)

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所有關(guān)鍵點(diǎn)已在tp的一個(gè)塊中thenPk.getBDD().then = true

10) else if 有一個(gè)關(guān)鍵點(diǎn)被孤立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所有關(guān)鍵點(diǎn)已在ep的一個(gè)塊中thenPk.getBDD().else = true

17) else if 有一個(gè)關(guān)鍵點(diǎn)被孤立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所示的橋接網(wǎng)絡(luò)，約定邊序?yàn)閑1

第1層，邊為e1=(s,n1)，其中“s”為關(guān)鍵點(diǎn)，邊界集F1={s,n1}.當(dāng)邊正常工作時(shí)，節(jié)點(diǎn)“s”和“n1”合并到一個(gè)塊，得分區(qū)[s,n1]*；當(dāng)邊失效時(shí)，節(jié)點(diǎn)“s”和“n1”分屬2個(gè)塊，得分區(qū)[s]*[n1].

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

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

利用相同的規(guī)則，計(jì)算邊界集，生成分區(qū)，得到完成的BDD模型.

2.3 BDD模型大小分析

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

(1)

(2)

表2 邊界集大小、斯特林?jǐn)?shù)和貝爾數(shù)之間的關(guān)系

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

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

(3)

考慮塊加“*”操作.在可靠性網(wǎng)絡(luò)G=(V,E,K)中，由于最多有|K|個(gè)關(guān)鍵節(jié)點(diǎn)，所以分區(qū)中最多包含|K|個(gè)帶“*”塊.關(guān)鍵節(jié)點(diǎn)單獨(dú)成塊時(shí)，取得最大值|K|.此時(shí)，第i層邊界集Fi所對(duì)應(yīng)的分區(qū)數(shù)目，即第i層BDD節(jié)點(diǎn)數(shù)目的最大理論值Wi可以按式(4)計(jì)算.

(4)

例如，邊界集F={1,2,3}且|K|=2時(shí)的所有可能分區(qū)：[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]*.

顯然，引入加“*”操作后，分區(qū)總數(shù)目大大增加.

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

另一方面，深入研究本文所述BDD模型的生成過程，發(fā)現(xiàn)某一層實(shí)際BDD節(jié)點(diǎn)數(shù)目的實(shí)際值和已經(jīng)處理的邊數(shù)及網(wǎng)絡(luò)結(jié)構(gòu)特征有關(guān).最好情況，第i層BDD節(jié)點(diǎn)數(shù)為1；最壞情況，第i層BDD節(jié)點(diǎn)數(shù)為2i，如圖5所示.由于同構(gòu)子網(wǎng)的存在及網(wǎng)絡(luò)結(jié)構(gòu)特征的差異，一般情況下，第i層BDD節(jié)點(diǎn)數(shù)目的實(shí)際值大于1而小于2i，如圖4所示.所以，如果能找到一種排序,使得每層邊界集足夠小，從而使得BDD節(jié)點(diǎn)數(shù)目最大理論值大大小于該層BDD數(shù)目的最壞情況，那么此排序?qū)?huì)是一種優(yōu)秀的排序.

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

3 基于邊界集的啟發(fā)式排序策略

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

3.1 排序策略設(shè)計(jì)

根據(jù)本文的BDD模型構(gòu)建方法，第k層分區(qū)以第k-1層分區(qū)為基礎(chǔ)，結(jié)合第k條邊ek在網(wǎng)絡(luò)中的連接情況而建立，即由Fk-1構(gòu)建Fk.為表述方便，設(shè)邊ek的2個(gè)端點(diǎn)分別為u和v，根據(jù)u和v在Fk-1和Fk的存在性得邊界集大小變化的所有情況，見表3.

表3 邊界集大小變化

由表3所示，新的邊界集Fk，其大小滿足式(5)，且不失一般性.所以，在設(shè)計(jì)邊選擇策略時(shí)，可以優(yōu)先考慮2個(gè)端點(diǎn)都在當(dāng)前邊界集中的邊，然后考慮有一個(gè)端點(diǎn)不在邊界集中的邊，這樣才能使當(dāng)前邊界集最小.2個(gè)端點(diǎn)都不在邊界集的情形不用考慮，因?yàn)樵撉樾蜗虏豢赡艿玫阶钚〉倪吔缂?

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

(5)

策略1優(yōu)先選擇2個(gè)端點(diǎn)u和v都在邊界集中的邊.若存在多條滿足條件的邊，則選擇節(jié)點(diǎn)度和小的邊.若節(jié)點(diǎn)度和也相同，則先選擇與先進(jìn)入邊界集的節(jié)點(diǎn)相關(guān)聯(lián)的邊.如圖6所示，候選邊ex和ey，由于邊ex的節(jié)點(diǎn)度和小于邊ey，所以邊ex先排.

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

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

關(guān)鍵節(jié)點(diǎn)的引入時(shí)機(jī)也是一個(gè)重要影響因素，所以當(dāng)候選邊關(guān)聯(lián)于關(guān)鍵節(jié)點(diǎn)時(shí)，該邊延遲排序.

3.2 排序起點(diǎn)選擇

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

定義4(邊界集總長度) 對(duì)于給定K-端網(wǎng)絡(luò)G=(V,E,K),設(shè)有一個(gè)邊序列o=e1≤e2≤e3≤…≤e|E|,ci∈E,i∈[1,|E|]，則關(guān)于序列o的邊界集總長度(記為LTBS(o))定義為

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

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

3.3 基于邊界集的啟發(fā)式排序算法

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

算法2

1)選擇一個(gè)節(jié)點(diǎn)v∈V，節(jié)點(diǎn)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) 選擇一點(diǎn)u∈Fk且u的度最小，在u的鄰接點(diǎn)中選擇一點(diǎn)v，且v擁有最多的未排序邊關(guān)聯(lián)于Fk

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

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

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

11) end while

12) return order

4 實(shí)驗(yàn)和結(jié)論

選擇星型網(wǎng)絡(luò)和De-Bruijn網(wǎng)絡(luò)分別驗(yàn)證本文提出的啟發(fā)式排序策略和排序起點(diǎn)選擇方法，搜集相關(guān)文獻(xiàn)的樣本網(wǎng)絡(luò),用來比較常用啟發(fā)式排序的性能，并在工程實(shí)際網(wǎng)絡(luò)中進(jìn)一步驗(yàn)證本文提出的啟發(fā)式排序方法.

4.1 Star網(wǎng)絡(luò)

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

圖8 Star網(wǎng)絡(luò)

實(shí)驗(yàn)步驟如下，實(shí)驗(yàn)結(jié)果如表4所示.

1)隨機(jī)選擇一個(gè)排序起點(diǎn)，根據(jù)4種不同排序策略建立邊排序；

2)隨機(jī)選擇節(jié)點(diǎn)對(duì)，建立BDD模型，計(jì)算BDD模型大小和BDD寬度.

表4 Star網(wǎng)絡(luò)的BDD模型大小和寬度

4種排序中，MaxBS的排序結(jié)果與排序起點(diǎn)無關(guān)，其余3種與排序起點(diǎn)的選擇有關(guān).在相同的排序策略下，可以建立不同的排序結(jié)果，而不同的排序結(jié)果指導(dǎo)生成不同大小的BDD模型，如表4，即使求解相同的問題(計(jì)算節(jié)點(diǎn)對(duì){0,7}的可靠度)，也能生成不同大小的BDD模型.比較BDD模型寬度和模型大小的關(guān)系，所得結(jié)果見圖9.由圖9可得，對(duì)于不同的排序策略，當(dāng)BDD模型寬度較小時(shí)，對(duì)應(yīng)的模型大小也較?。环粗?，當(dāng)模型寬度較大時(shí)，模型大小較大.控制BDD模型寬度，有利于控制BDD模型大小.

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

4.2 De-Bruijn網(wǎng)絡(luò)

在De-Bruijn網(wǎng)絡(luò)(見圖10)中，不同排序起點(diǎn)有不同的邊界集總長度.采用本文提出的啟發(fā)式排序策略時(shí)，各排序起點(diǎn)對(duì)應(yīng)的邊界集總長度如表5所示，節(jié)點(diǎn)“0”“1”和“8”擁有最小的邊界集總長度.

圖10 De-Bruijn網(wǎng)絡(luò)(Order=4)

表5 各排序起點(diǎn)的邊界集總長度

以下實(shí)驗(yàn)說明選擇排序起點(diǎn)的必要性，實(shí)驗(yàn)過程如下，實(shí)驗(yàn)數(shù)據(jù)如表6、表7所示.

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

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

2)根據(jù)16種排序分別為每個(gè)節(jié)點(diǎn)對(duì)(共120對(duì))生成等價(jià)的BDD模型；

3)選擇擁有最小邊界集總長度的節(jié)點(diǎn)作為起點(diǎn)時(shí)，統(tǒng)計(jì)對(duì)應(yīng)的BDD模型大小位序的分布；

4)選定最小BDD模型時(shí)，統(tǒng)計(jì)邊界集總長度大小的分布.

由表6和表7看出：當(dāng)選擇擁有最小邊界集總長度的節(jié)點(diǎn)作為排序起點(diǎn)時(shí)，最小BDD模型占18.6%，前4小BDD模型占比高達(dá)91.7%.對(duì)應(yīng)地，當(dāng)取最小BDD模型時(shí)，最小邊界集總長度占55.8%，前4小BDD模型占88.3%.由此可得，選擇擁有最小邊界集總長度的節(jié)點(diǎn)作為排序起點(diǎn)時(shí)，可以大概率提升排序質(zhì)量，從而指導(dǎo)生成更小的BDD模型.

4.3 樣本網(wǎng)絡(luò)

本文在相關(guān)文獻(xiàn)中搜集了22個(gè)2-端可靠性網(wǎng)絡(luò)，如圖11所示，采用基于邊界集的BDD構(gòu)建方法，結(jié)合本文提出的啟發(fā)式排序，生成等價(jià)BDD模型，計(jì)算可靠度值和模型大小，實(shí)驗(yàn)結(jié)果如表8所示，其中DFS和BFS的數(shù)據(jù)來自文獻(xiàn)[15]，“*”表示原BDD構(gòu)建方法無法生成BDD模型.

圖11 樣本網(wǎng)絡(luò)

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

表8數(shù)據(jù)表明，BFS略優(yōu)于DFS，而本文提出的啟發(fā)式排序全面優(yōu)于BFS和DFS.

5 結(jié) 語

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