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

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

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

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

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

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

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