基于BDD的網(wǎng)絡(luò)可靠性分析中邊排序策略研究.pdf

1、在網(wǎng)絡(luò)可靠性分析中，使用二元決策圖(binary decision diagram，BDD)技術(shù)能夠在很大程度上提高性能和效率。基于BDD的網(wǎng)絡(luò)可靠性分析方法主要包含尋找一種較好的網(wǎng)絡(luò)變量（本文僅考慮邊失效，節(jié)點(diǎn)均是可靠的）排序序列、生成與原網(wǎng)絡(luò)等價(jià)的BDD、計(jì)算網(wǎng)絡(luò)的可靠度值三個(gè)方面。其中的關(guān)鍵性基礎(chǔ)，就是選取一種高效的對(duì)網(wǎng)絡(luò)中的邊進(jìn)行排序的策略，從而顯著地提升基于BDD的網(wǎng)絡(luò)可靠性分析算法的性能。
　　已有的基于BDD的網(wǎng)絡(luò)可

2、靠性分析方法，通常采用深度優(yōu)先排序策略(depth-first search，DFS)和廣度優(yōu)先排序策略(breadth-first search，BFS)兩種啟發(fā)式排序策略，并有研究者對(duì)這兩種策略進(jìn)行了性能比較，得出了BFS性能普遍優(yōu)于DFS這一結(jié)論，也有研究者提出了新的邊排序策略——優(yōu)先級(jí)排序策略(priority ordering strategy，POS)。通過(guò)分析這些策略及其研究方法，我們發(fā)現(xiàn)主要存在這樣三個(gè)方面的問(wèn)題:(1)

3、進(jìn)行測(cè)試的網(wǎng)絡(luò)模型及規(guī)模有限，策略性能的比較不夠系統(tǒng);(2)BFS是一種基于圖廣度遍歷搜索的邊排序策略，其排序結(jié)果依賴(lài)于圖節(jié)點(diǎn)的編號(hào)，存在不合理性;(3)隨著網(wǎng)絡(luò)規(guī)模的增大，當(dāng)以復(fù)雜網(wǎng)絡(luò)作為網(wǎng)絡(luò)模型時(shí)，已有的邊排序策略不再能滿(mǎn)足網(wǎng)絡(luò)的需求，需要設(shè)計(jì)性能更優(yōu)的邊排序策略。
　　本文的工作主要圍繞基于BDD的網(wǎng)絡(luò)可靠性分析中邊排序策略主題，針對(duì)目前存在的三個(gè)問(wèn)題進(jìn)行深入研究，包括:
　　(1)在規(guī)則網(wǎng)絡(luò)中對(duì)BFS和POS兩種邊排

4、序策略進(jìn)行性能分析?；诓煌幕鶞?zhǔn)規(guī)則網(wǎng)絡(luò)模型，采用BFS和POS策略分別進(jìn)行BDD網(wǎng)絡(luò)可靠性測(cè)試，由可靠度值、BDD尺度（空間性能）、運(yùn)行時(shí)間（時(shí)間性能）三個(gè)重要的性能指標(biāo)分析兩種策略對(duì)網(wǎng)絡(luò)的適應(yīng)性，得出不同的策略適應(yīng)于不同的網(wǎng)絡(luò)這一結(jié)論，這將為特定的網(wǎng)絡(luò)選擇較好的邊排序策略提供依據(jù)。
　　(2)在復(fù)雜網(wǎng)絡(luò)中對(duì)BFS策略進(jìn)行改進(jìn)。BFS策略是依賴(lài)于節(jié)點(diǎn)編號(hào)的一種排序策略，其排序質(zhì)量的好壞與節(jié)點(diǎn)編號(hào)順序緊密相關(guān)，因此BFS排序結(jié)果

5、不僅受網(wǎng)絡(luò)本身結(jié)構(gòu)的影響，還受人為編號(hào)的影響，存在不穩(wěn)定性。BFS策略在規(guī)則網(wǎng)絡(luò)中的性能較好，但是隨著網(wǎng)絡(luò)規(guī)模的增加，BFS的性能卻不是很理想。為避免人為因素的影響，同時(shí)使策略具有更強(qiáng)的適應(yīng)性，利用優(yōu)先隊(duì)列改進(jìn)BFS策略:以網(wǎng)絡(luò)的節(jié)點(diǎn)度作為排序參數(shù)，用優(yōu)先隊(duì)列替代BFS策略中的普通隊(duì)列，節(jié)點(diǎn)的未排序關(guān)聯(lián)邊數(shù)定義為該節(jié)點(diǎn)的優(yōu)先級(jí)，設(shè)計(jì)了一種基于節(jié)點(diǎn)度的最好優(yōu)先排序策略(degree-based best first search，DBFS

6、)。實(shí)驗(yàn)結(jié)果表明，DBFS策略在復(fù)雜網(wǎng)絡(luò)中較BFS性能提升了很多。
　　(3)在邊界集的基礎(chǔ)上設(shè)計(jì)了一種新的高性能邊排序策略Snooker。邊界集是構(gòu)建BDD過(guò)程中的一個(gè)有效參數(shù)，并且邊界集及邊界集的和值與邊排序策略之間緊密相關(guān)。因此，提出了一種以“邊界集和值最小”為原則，以節(jié)點(diǎn)度為主要排序參數(shù)的Snooker策略，并分別在規(guī)則網(wǎng)絡(luò)模型和復(fù)雜網(wǎng)絡(luò)模型中比較分析Snooker與DBFS策略，實(shí)驗(yàn)結(jié)果表明:選取的網(wǎng)絡(luò)樣本無(wú)論是規(guī)則網(wǎng)絡(luò)