【摘要】：在網(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ò)可靠性分析方法,通常采用深度優(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)進行測試的網(wǎng)絡(luò)模型及規(guī)模有限,策略性能的比較不夠系統(tǒng)；(2)BFS是一種基于圖廣度遍歷搜索的邊排序策略,其排序結(jié)果依賴于圖節(jié)點的編號,存在不合理性；(3)隨著網(wǎng)絡(luò)規(guī)模的增大,當以復(fù)雜網(wǎng)絡(luò)作為網(wǎng)絡(luò)模型時,已有的邊排序策略不再能滿足網(wǎng)絡(luò)的需求,需要設(shè)計性能更優(yōu)的邊排序策略。本文的工作主要圍繞基于BDD的網(wǎng)絡(luò)可靠性分析中邊排序策略主題,針對目前存在的三個問題進行深入研究,包括：(1)在規(guī)則網(wǎng)絡(luò)中對BFS和POS兩種邊排序策略進行性能分析�；诓煌幕鶞室�(guī)則網(wǎng)絡(luò)模型,采用BFS和POS策略分別進行BDD網(wǎng)絡(luò)可靠性測試,由可靠度值、BDD尺度(空間性能)、運行時間(時間性能)三個重要的性能指標分析兩種策略對網(wǎng)絡(luò)的適應(yīng)性,得出不同的策略適應(yīng)于不同的網(wǎng)絡(luò)這一結(jié)論,這將為特定的網(wǎng)絡(luò)選擇較好的邊排序策略提供依據(jù)。(2)在復(fù)雜網(wǎng)絡(luò)中對BFS策略進行改進。BFS策略是依賴于節(jié)點編號的一種排序策略,其排序質(zhì)量的好壞與節(jié)點編號順序緊密相關(guān),因此BFS排序結(jié)果不僅受網(wǎng)絡(luò)本身結(jié)構(gòu)的影響,還受人為編號的影響,存在不穩(wěn)定性。BFS策略在規(guī)則網(wǎng)絡(luò)中的性能較好,但是隨著網(wǎng)絡(luò)規(guī)模的增加,BFS的性能卻不是很理想。為避免人為因素的影響,同時使策略具有更強的適應(yīng)性,利用優(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)。實驗結(jié)果表明,DBFS策略在復(fù)雜網(wǎng)絡(luò)中較BFS性能提升了很多。(3)在邊界集的基礎(chǔ)上設(shè)計了一種新的高性能邊排序策略Snooker。邊界集是構(gòu)建BDD過程中的一個有效參數(shù),并且邊界集及邊界集的和值與邊排序策略之間緊密相關(guān)。因此,提出了一種以“邊界集和值最小”為原則,以節(jié)點度為主要排序參數(shù)的Snooker策略,并分別在規(guī)則網(wǎng)絡(luò)模型和復(fù)雜網(wǎng)絡(luò)模型中比較分析Snooker與 DBFS策略,實驗結(jié)果表明：選取的網(wǎng)絡(luò)樣本無論是規(guī)則網(wǎng)絡(luò)還是復(fù)雜網(wǎng)絡(luò),Snooker策略的性能均較DBFS更優(yōu)。
[Abstract]:......
【學(xué)位授予單位】：浙江師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP393.08

【參考文獻】

相關(guān)期刊論文 前3條

1 杜楠;王柏;吳斌;;Community Detection in Complex Networks[J];Journal of Computer Science & Technology;2008年04期

2 潘竹生;莫毓昌;趙建民;;優(yōu)先級邊排序策略及其性能分析[J];計算機科學(xué);2014年08期

3 章忠志,榮莉莉,周濤;一類無標度合作網(wǎng)絡(luò)的演化模型[J];系統(tǒng)工程理論與實踐;2005年11期

，

本文編號：2361983