一種用于BDD模型構(gòu)建的排序起點(diǎn)選擇新方法*

潘竹生, 王 暉, 曾令國(guó)

(浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,浙江 金華 321004)

0 引 言

二元決策圖即BDD(binary decision diagram)及其擴(kuò)展形式已廣泛應(yīng)用于眾多領(lǐng)域，如電路驗(yàn)證[1]、緊湊馬爾可夫鏈表達(dá)式[2]、編程中對(duì)大型元組集的有效處理[3]、符號(hào)模型檢驗(yàn)[4]和各種類型系統(tǒng)[5]的可靠性分析等,有著出色的應(yīng)用表現(xiàn).

所有基于BDD的方法，其性能都非常依賴變量排序.不同質(zhì)量的變量排序指導(dǎo)生成不同規(guī)模的BDD模型，BDD規(guī)模大小通?？缭綆讉€(gè)數(shù)量級(jí)[6].更不幸的是，尋找最優(yōu)排序是一個(gè)NP完全問(wèn)題[6].因此，在實(shí)際應(yīng)用中多采用啟發(fā)式變量排序[7-8]策略，其中在網(wǎng)絡(luò)可靠性分析領(lǐng)域，一般采用廣度優(yōu)先搜索BFS(broad first search)和深度優(yōu)先搜索DFS(deep first search)這2種排序[9].文獻(xiàn)[10]比較了BFS和DFS兩種策略在規(guī)則網(wǎng)絡(luò)可靠性分析中的性能，得出BFS策略優(yōu)于DFS;文獻(xiàn)[11]深入研究了BFS排序策略，指出源點(diǎn)一般不是最佳排序起點(diǎn)，對(duì)于Square Lattice網(wǎng)絡(luò)，最佳排序起點(diǎn)分布在4個(gè)角上;文獻(xiàn)[12]結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)特征提出了一種啟發(fā)式策略的選擇方法，用于構(gòu)建精簡(jiǎn)BDD模型.總結(jié)現(xiàn)有研究成果，針對(duì)啟發(fā)式排序，主要研究排序策略本身，并且認(rèn)為“源點(diǎn)，即可靠性網(wǎng)絡(luò)中的一個(gè)關(guān)鍵節(jié)點(diǎn)，就是最佳排序起點(diǎn)”[7].

事實(shí)上，排序起點(diǎn)和排序策略一樣，同樣嚴(yán)重影響排序結(jié)果.本文嘗試為節(jié)點(diǎn)建立指標(biāo)數(shù)據(jù)，研究基于指標(biāo)數(shù)據(jù)的最佳排序起點(diǎn)選擇方法.

1 網(wǎng)絡(luò)模型和常用啟發(fā)式排序

1.1 網(wǎng)絡(luò)模型

研究網(wǎng)絡(luò)可靠性時(shí)，通常將網(wǎng)絡(luò)建模成一個(gè)無(wú)向圖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，k=|K|表示集合K的長(zhǎng)度)，表示網(wǎng)絡(luò)中特別重要的實(shí)體.所謂網(wǎng)絡(luò)可靠性，是指K中節(jié)點(diǎn)完全連通的可能性.根據(jù)集合K大小的不同，將可靠性問(wèn)題分為3類：2-端網(wǎng)絡(luò)可靠性(|K|=2)、k-端網(wǎng)絡(luò)可靠性(2<|K|<|V|，|V|表示集合V的長(zhǎng)度)和All-端網(wǎng)絡(luò)可靠性(|K|=|V|).本文研究2-端網(wǎng)絡(luò)可靠性，圖1所示為3×3 Square Lattice網(wǎng)絡(luò)G(V,E,K)=({n0,n1,n2,n3,n4,n5,n6,n7,n8},{e1,e2,e3,e4,e5,e6,e7,e8,e9,e10,e11,e12},{n0,n8})，|K|=2.

圖1 3×3 Square Lattice網(wǎng)絡(luò)

1.2 常用啟發(fā)式排序

最優(yōu)排序能生成最簡(jiǎn)BDD模型,然而求解最優(yōu)排序是一個(gè)NP完全問(wèn)題[6].因此，在工程應(yīng)用中多采用啟發(fā)式排序，常見(jiàn)的有BFS和DFS.

1.2.1 BFS啟發(fā)式排序

BFS即廣度優(yōu)先搜索，是圖的一種遍歷方法.遍歷從某一點(diǎn)v開(kāi)始，沿著關(guān)聯(lián)于v的邊ei(1≤i≤|E|)，分別訪問(wèn)節(jié)點(diǎn)ni(1≤i≤|E|且ni≠v).根據(jù)廣度優(yōu)先策略，再分別由節(jié)點(diǎn)ni(1≤i≤|V|且ni≠v)出發(fā)，沿著相關(guān)邊遍歷其他節(jié)點(diǎn)，直到所有邊和節(jié)點(diǎn)被訪問(wèn).按遍歷過(guò)程中出現(xiàn)的順序排列邊，即得到BFS啟發(fā)式邊排序；排列節(jié)點(diǎn)，則得到節(jié)點(diǎn)序；若考慮二者，則得到節(jié)點(diǎn)和邊的混合排序.如圖1所示網(wǎng)絡(luò)，假設(shè)排序起點(diǎn)v=n0，若按小編號(hào)優(yōu)先進(jìn)行廣度遍歷，則得到邊序?yàn)閑1≤e2≤e3≤e4≤e5≤e6≤e7≤e8≤e9≤e10≤e11≤e12，節(jié)點(diǎn)序?yàn)閚0≤n1≤n3≤n2≤n4≤n6≤n5≤n7≤n8，混合排序?yàn)閚0≤e1≤e2≤n1≤e3≤e4≤n3≤e5≤e6≤n2≤e7≤n4≤e8≤e9≤n6≤e10≤n5≤e11≤n7≤e12≤n8；改變排序起點(diǎn)v=n4，則邊序?yàn)閑4≤e5≤e8≤e9≤e1≤e3≤e2≤e6≤e7≤e11≤e10≤e12，節(jié)點(diǎn)序?yàn)閚4≤n1≤n3≤n5≤n7≤n0≤n2≤n6≤n8.

1.2.2 DFS啟發(fā)式排序

DFS即深度優(yōu)先搜索，是另一種圖遍歷方法.遍歷從某一點(diǎn)v開(kāi)始，沿著關(guān)聯(lián)于v的邊ei(1≤i≤|E|)，訪問(wèn)節(jié)點(diǎn)ni(1≤i≤|V|且ni≠v)，再?gòu)墓?jié)點(diǎn)ni出發(fā)，進(jìn)行深度優(yōu)先遍歷，直到所有的邊和節(jié)點(diǎn)被訪問(wèn).按遍歷過(guò)程中出現(xiàn)的順序排列邊，得到DFS邊排序；排列節(jié)點(diǎn)，得到節(jié)點(diǎn)序；排列邊和節(jié)點(diǎn)，得到邊和節(jié)點(diǎn)的混合排序.如圖1所示網(wǎng)絡(luò)，假設(shè)排序起點(diǎn)選擇n0，若按小編號(hào)優(yōu)先進(jìn)行深度遍歷，則得到邊序?yàn)閑1≤e3≤e7≤e8≤e4≤e5≤e2≤e6≤e10≤e9≤e12≤e11，節(jié)點(diǎn)序?yàn)閚0≤n1≤n2≤n5≤n4≤n3≤n6≤n7≤n8，混合排序?yàn)閚0≤e1≤n1≤e3≤n2≤e7≤n5≤e8≤n4≤e4≤e5≤n3≤e2≤e6≤n6≤e10≤n7≤e9≤e12≤n8≤e12；若排序起點(diǎn)選擇n4，則邊序?yàn)閑4≤e1≤e2≤e5≤e6≤e10≤e9≤e12≤e11≤e7≤e3≤e8，節(jié)點(diǎn)序?yàn)閚4≤n1≤n0≤n3≤n6≤n7≤n8≤n5≤n2.

顯然，不同的排序起點(diǎn)，有完全不同的排序結(jié)果，進(jìn)而導(dǎo)致規(guī)模大小迥異的BDD模型.

2 排序起點(diǎn)選擇方法和證明

2.1 依賴集和依賴集總長(zhǎng)度

定義1(依賴集dependency set) 對(duì)于k-端網(wǎng)絡(luò)G= (V,E,K),設(shè)有一個(gè)部件序列o=c1≤c2≤…≤c|V|+|E|,ci∈V∪E,i∈[1,|V|+|E|]，v∈V,則第i層依賴集Di定義為:Di={v|v已經(jīng)排序且至少存在一條關(guān)聯(lián)于v的未排序邊}∪{v|v未排序且至少存在一條關(guān)聯(lián)于v的已排序邊}.集合Di中節(jié)點(diǎn)的數(shù)目定義為第i層依賴集長(zhǎng)度，記為L(zhǎng)i.如圖1所示的3×3網(wǎng)絡(luò)中，設(shè)有排序o=n0≤e1≤e2≤n1≤e3≤e4≤n3≤e5≤e6≤n2≤e7≤n4≤e8≤e9≤n6≤e10≤n5≤e11≤n7≤e12≤n8，則各層依賴集及依賴集長(zhǎng)度如表1所示.

表1 排序o的各層依賴集及依賴集長(zhǎng)度(3×3 Square Lattice網(wǎng)絡(luò))

定義2(依賴集總長(zhǎng)度) 對(duì)于k-端網(wǎng)絡(luò)G=(V,E,K),設(shè)有一個(gè)部件序列o=c1≤c2≤…≤c|V|+|E|,ci∈V∪E,i∈[1,|V|+|E|]，則序列o的依賴集總長(zhǎng)度(total length of dependency set,記為T(mén)LDS(o))定義為

其中,Li為序列o的第i層依賴集長(zhǎng)度.如圖1所示網(wǎng)絡(luò)，序列o(o=n0≤e1≤e2≤n1≤e3≤e4≤n3≤e5≤e6≤n2≤e7≤n4≤e8≤e9≤n6≤e10≤n5≤e11≤n7≤e12≤n8)的依賴集總長(zhǎng)度為28.

2.2 排序起點(diǎn)選擇方法

對(duì)于網(wǎng)絡(luò)G=(V,E,K)，在確定排序策略(如BFS或DFS)的前提下，計(jì)算不同排序起點(diǎn)的依賴集總長(zhǎng)度TLDS(order(v)),其中order(v)是以v(v∈V-K)為排序起點(diǎn)的一種排序結(jié)果，選取TLDS值最小的節(jié)點(diǎn)v作為排序起點(diǎn)，即

Chosen(V)=v?TLDS(v)=min{TLDS(v),v∈V-K}.

2.3 關(guān)于排序起點(diǎn)選擇的思考和討論

為何要選擇TLDS值小的節(jié)點(diǎn)作為排序起點(diǎn)呢？這需要先來(lái)研究基于依賴集分區(qū)的子網(wǎng)特征標(biāo)識(shí)技術(shù)[9]和BDD模型構(gòu)建過(guò)程[9].

定義3(依賴集分區(qū)) 對(duì)依賴集中的節(jié)點(diǎn)按如下規(guī)則建立劃分，按某種順序排列所有劃分，得到一個(gè)分區(qū)，稱該分區(qū)為依賴集分區(qū).

1)對(duì)于第i層依賴集Di中的任意2個(gè)節(jié)點(diǎn)u

2)若節(jié)點(diǎn)v∈Di失效，則首先將節(jié)點(diǎn)v從劃分中分離出來(lái)，并給節(jié)點(diǎn)v加“#”；

3)若節(jié)點(diǎn)v∈Di和K′中的某一節(jié)點(diǎn)之間存在一條成功路徑，則給節(jié)點(diǎn)v加“*f(v,K′)”，其中K′是集合K的一個(gè)有序序列，函數(shù)f是節(jié)點(diǎn)v與K′中節(jié)點(diǎn)的連接關(guān)系，即

f:(v,K′)→Z.

其中,Z是自然數(shù)集，用Z中元素的二進(jìn)制位來(lái)表示節(jié)點(diǎn)v與K′中節(jié)點(diǎn)的連接關(guān)系.若連通，則將該位置為“1”，否則將其置為“0”.二進(jìn)制位從右向左依次對(duì)應(yīng)K′中的第1個(gè)節(jié)點(diǎn)至第|K′|個(gè)節(jié)點(diǎn).

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

圖3是圖2橋接網(wǎng)絡(luò)在排序n0

圖3 依賴集、依賴集分區(qū)和BDD生成過(guò)程

一條成功路徑，即f(n3，{n0,n3})=(11)2=1+2=3.顯然，構(gòu)建任意一層BDD節(jié)點(diǎn)時(shí)，每個(gè)依賴集分區(qū)對(duì)應(yīng)一個(gè)子網(wǎng)，而每個(gè)子網(wǎng)都可以由依賴集分區(qū)唯一標(biāo)識(shí).

進(jìn)一步研究發(fā)現(xiàn)，依賴集分區(qū)建立在“n個(gè)有區(qū)別的節(jié)點(diǎn)，分配到m(0

其中,S(n,m)為第二類斯特林?jǐn)?shù)，表示對(duì)n個(gè)數(shù)作m個(gè)劃分.當(dāng)?shù)趇層依賴集元素個(gè)數(shù)n較大時(shí)，Bn較大，即分區(qū)總數(shù)較多.所以，控制n的大小有助于控制分區(qū)數(shù)目，即BDD節(jié)點(diǎn)數(shù).若能將每層依賴集都控制到最小，就有望構(gòu)建規(guī)模最小的BDD模型.

考慮給節(jié)點(diǎn)加“*”時(shí)，依賴集中的每個(gè)節(jié)點(diǎn)都有可能加“*”，所以有n個(gè)節(jié)點(diǎn)的依賴集，其分區(qū)數(shù)目為2nBn.分區(qū)數(shù)目與n有關(guān)，n小，則分區(qū)數(shù)目就小.所以，如果每層取得最小(或較小)依賴集，那么在大概率上可以得到最小(或較小)BDD模型.

綜合以上兩方面分析可得，控制依賴集大小，能有效控制當(dāng)前層的BDD節(jié)點(diǎn)數(shù)目.控制每層依賴集的大小，就可以控制整個(gè)BDD的規(guī)模.依賴集總長(zhǎng)度TLDS由各層依賴集長(zhǎng)度累加得到，當(dāng)取最小TLDS值時(shí)，各層依賴集長(zhǎng)度最小(或較小)，所以，理論上有助于獲得規(guī)模最小(或較小)的BDD模型.值得注意的是，加“*”操作嚴(yán)重影響分區(qū)空間，對(duì)于有n個(gè)元素的依賴集，加“*”操作，將分區(qū)空間擴(kuò)展為原來(lái)空間的2n倍，這非常不利于精簡(jiǎn)BDD模型的生成.所以，一般而言，關(guān)鍵節(jié)點(diǎn)不宜用作排序起點(diǎn)[11].

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

接下來(lái)用實(shí)驗(yàn)來(lái)驗(yàn)證所提方法的有效性.選擇常用的BFS和DFS啟發(fā)式排序策略，分別在Square Lattice、De-Bruijn和Hyper Cube網(wǎng)絡(luò)中實(shí)驗(yàn).實(shí)驗(yàn)過(guò)程：首先建立以每個(gè)節(jié)點(diǎn)為排序起點(diǎn)的BFS和DFS策略下的排序，得到排序結(jié)果并計(jì)算這些排序結(jié)果的TLDS值；其次，為每個(gè)2-端可靠性問(wèn)題采用不同排序結(jié)果指導(dǎo)生成BDD模型，并統(tǒng)計(jì)BDD規(guī)模的大小情況；最后，統(tǒng)計(jì)當(dāng)TLDS值最小(較小)和最大(較大)時(shí)對(duì)應(yīng)的BDD規(guī)模大小的分布.

3.1 Square Lattice網(wǎng)絡(luò)

Square Lattice 網(wǎng)絡(luò)在分布式并行計(jì)算、分布式控制、CMOS電路、容量限制、路由優(yōu)化、無(wú)線傳感網(wǎng)絡(luò)等領(lǐng)域有著廣泛的應(yīng)用[13].圖4是一個(gè)4×4 Square Lattice網(wǎng)絡(luò).對(duì)于BFS和DFS排序策略，計(jì)算不同排序起點(diǎn)的依賴集總長(zhǎng)度TLDS值，結(jié)果如表2所示.

圖4 4×4 Square Lattice網(wǎng)絡(luò)

節(jié)點(diǎn)TLDSBFSDFS節(jié)點(diǎn)TLDSBFSDFS0123150814515411341419194179213914710206184312315011145155413914212123175517018113154158617815414165181713914115123188

在相同排序策略下，1個(gè)排序起點(diǎn)對(duì)應(yīng)1個(gè)排序結(jié)果，得到1個(gè)BDD模型.對(duì)于4×4 Square Lattice網(wǎng)絡(luò)，共有120個(gè)2-端可靠性問(wèn)題，任一可靠性問(wèn)題有16個(gè)不同的BDD模型，記錄16個(gè)不同排序起點(diǎn)所對(duì)應(yīng)的BDD模型的大小情況.統(tǒng)計(jì)所有120個(gè)2-端可靠性問(wèn)題在最小(較小)TLDS值時(shí)取得最小(較小)BDD模型的次數(shù)，和在最大(較大)TLDS值時(shí)取得最大(較大)BDD模型的次數(shù)，得表3和表4.表3和表4中1—16表示同一可靠性問(wèn)題的不同BDD模型的大小次序，“1”代表最小BDD模型，“16”代表最大BDD模型，這些符號(hào)也適用后續(xù)表格.

由表3可得，對(duì)于BFS策略，當(dāng)選擇具有最小TLDS值的節(jié)點(diǎn)作為排序起點(diǎn)時(shí)，生成的BDD模型規(guī)模普遍較小，其中最小至少占21.7%(如節(jié)點(diǎn)“0”和“3”),節(jié)點(diǎn)“12”高達(dá)24.2%；前三小至少占49.2%(如節(jié)點(diǎn)“3”)，節(jié)點(diǎn)“0”高達(dá)57.5%；當(dāng)選擇具有最大TLDS值的節(jié)點(diǎn)(如“10”)作為排序起點(diǎn)時(shí)，在120個(gè)樣本中，有86個(gè)BDD模型的規(guī)模最大，29個(gè)第二，5個(gè)第三，前三大占100%.

表3 節(jié)點(diǎn)具有最小(大)TLDS值時(shí) 最小(大)BDD模型出現(xiàn)的次數(shù)(BFS)

注：節(jié)點(diǎn)“10”的TLDS值最大，節(jié)點(diǎn)“9”次之，節(jié)點(diǎn)“6”第3大.

表4 節(jié)點(diǎn)具有最小(大)TLDS值時(shí) 最小(大)BDD模型出現(xiàn)的次數(shù)(DFS)

注：節(jié)點(diǎn)“15”具有最大TLDS值，節(jié)點(diǎn)“10”次之，節(jié)點(diǎn)“5”和“14”第3大.

分析表4可得，對(duì)于DFS，當(dāng)選擇具有最小TLDS值的節(jié)點(diǎn)作為排序起點(diǎn)時(shí)，生成的BDD模型中，有61.7%(節(jié)點(diǎn)“1”)或34.2%(節(jié)點(diǎn)“7”)為前三??；相反，當(dāng)選擇具有最大或較大TLDS的節(jié)點(diǎn)作為排序起點(diǎn)時(shí)，生成的BDD模型普遍較大.

3.2 其他網(wǎng)絡(luò)

選擇廣泛應(yīng)用于分布式計(jì)算、容錯(cuò)計(jì)算、并行路由等領(lǐng)域的De-Bruijn網(wǎng)絡(luò)[14](見(jiàn)圖5)和Hyper Cube[15]網(wǎng)絡(luò)(見(jiàn)圖6)繼續(xù)實(shí)驗(yàn)，得到的實(shí)驗(yàn)數(shù)據(jù)如表5～表10所示.

對(duì)于BFS排序策略，隨機(jī)選擇4種BDD模式，結(jié)果如表9所示.顯然，在TLDS值相同時(shí)，不同BDD模式在各個(gè)節(jié)點(diǎn)的分布相對(duì)均衡，間接說(shuō)明TLDS值和BDD規(guī)模的相關(guān)性.

表6、表7和表10都說(shuō)明：TLDS值與BDD規(guī)模之間存在相關(guān)性.TLDS值小，對(duì)應(yīng)的BDD模型較?。籘LDS值大，對(duì)應(yīng)的BDD模型較大.在選擇排序起點(diǎn)時(shí)，應(yīng)盡可能選擇TLDS值小的節(jié)點(diǎn).

圖5 4階De-Bruijn網(wǎng)絡(luò) 圖6 4-Dimensional Hyper Cube網(wǎng)絡(luò)

節(jié)點(diǎn)viTLDSBFSDFS節(jié)點(diǎn)viTLDSBFSDFS節(jié)點(diǎn)viTLDSBFSDFS節(jié)點(diǎn)viTLDSBFSDFS0196249419524781992471227526112042465233243924224213230268219922162622461022924614229268326625272482331123223715213272

表6 節(jié)點(diǎn)具有最小(大)TLDS值時(shí)，最小(大)BDD模型出現(xiàn)的次數(shù)(De-Bruijn BFS)

注：節(jié)點(diǎn)“4”的TLDS值最小，“0”次之；節(jié)點(diǎn)“12”的TLDS值最大，節(jié)點(diǎn)“3”次之.

表7 節(jié)點(diǎn)具有最小(大)TLDS值時(shí)，最小(大)BDD模型出現(xiàn)的次數(shù)(De-Bruijn DFS)

注：節(jié)點(diǎn)“2”的TLDS值最小，“7”次之；節(jié)點(diǎn)“15”的TLDS值最大，“13”“14”次之.

表8 各節(jié)點(diǎn)依賴集總長(zhǎng)度TLDS(Hyper Cube 4-D)

表9 當(dāng)TLDS值相同時(shí)，不同規(guī)模BDD模型出現(xiàn)的次數(shù)(Hyper Cube 4-D BFS)

表10 節(jié)點(diǎn)具有最小(大)TLDS值時(shí)，最小(大)BDD模型出現(xiàn)的次數(shù)(Hyper Cube 4-D DFS)

注：節(jié)點(diǎn)“4”和“5”具有最小TLDS值，節(jié)點(diǎn)“0”“1”“2”“3”次之；節(jié)點(diǎn)“14”和“15”具有最大TLDS值，節(jié)點(diǎn)“10”“11”次之.

4 結(jié) 語(yǔ)

BDD模型的大小依賴于排序質(zhì)量的高低，排序質(zhì)量受排序策略和排序起點(diǎn)的影響.在排序策略確定的情況下，排序起點(diǎn)是影響排序質(zhì)量的最重要因素.本文就排序起點(diǎn)的選擇展開(kāi)研究，提出“TLDS值小優(yōu)先”的排序起點(diǎn)選擇方法.理論和實(shí)驗(yàn)都表明：TLDS值和BDD規(guī)模之間存在相關(guān)性，即“小值TLDS節(jié)點(diǎn)通常生成較小規(guī)模的BDD模型，大值TLDS大概率產(chǎn)生較大規(guī)模的BDD模型”.在選擇排序起點(diǎn)時(shí)，TLDS值小的節(jié)點(diǎn)具有優(yōu)勢(shì)，應(yīng)該優(yōu)先考慮.除了排序起點(diǎn)影響排序質(zhì)量外，還有排序策略本身.今后將繼續(xù)研究排序策略選擇方法及排序起點(diǎn)選擇、排序策略選擇與網(wǎng)絡(luò)結(jié)構(gòu)特征的相關(guān)性.