基于BDD的網(wǎng)絡(luò)可靠性分析方法研究.pdf

1、隨著人類文明的不斷發(fā)展進(jìn)步，網(wǎng)絡(luò)逐漸成為人們生產(chǎn)和生活的重要工具。大數(shù)據(jù)時(shí)代的網(wǎng)絡(luò)系統(tǒng)變得極其龐大復(fù)雜，因而亟需加強(qiáng)網(wǎng)絡(luò)可靠性的建設(shè)。
　　利用二元決策圖(BDD)技術(shù)分析網(wǎng)絡(luò)可靠性能夠大大提高分析性能和工作效率。該過程主要包含尋找一種性能較好的網(wǎng)絡(luò)變量排序、構(gòu)建與原網(wǎng)絡(luò)等價(jià)的BDD、計(jì)算網(wǎng)絡(luò)的可靠度值三個(gè)步驟。選擇一種優(yōu)秀的策略對(duì)網(wǎng)絡(luò)中的邊和節(jié)點(diǎn)進(jìn)行排序，能夠極大地提升網(wǎng)絡(luò)可靠性BDD分析算法的性能。根據(jù)既定的變量排序規(guī)則，可以

2、利用網(wǎng)絡(luò)分解原理等方法生成與原網(wǎng)絡(luò)可靠度等價(jià)的BDD。根據(jù)生成的BDD計(jì)算出每個(gè)節(jié)點(diǎn)的可靠度值，并且通過遞歸方法計(jì)算出整個(gè)BDD的可靠度值。通常對(duì)算法的評(píng)價(jià)主要以時(shí)間復(fù)雜度和空間復(fù)雜度為依據(jù)，這兩個(gè)復(fù)雜度恰好與BDD的路徑長度和節(jié)點(diǎn)數(shù)目一一對(duì)應(yīng)。因此在保證所測(cè)試信息完整和準(zhǔn)確的前提下，對(duì)算法進(jìn)行性能優(yōu)化以及研究變量排序時(shí)，應(yīng)以盡量減小BDD節(jié)點(diǎn)數(shù)目和縮短BDD路徑長度為目標(biāo)。
　　提高網(wǎng)絡(luò)可靠度BDD分析方法的性能是當(dāng)前研究領(lǐng)域的

3、一個(gè)熱點(diǎn)，本文在提高分析性能上做出一些研究，具體工作主要包括:
　　(1)依據(jù)Sy-Yen Kuo等提出的利用邊擴(kuò)展技術(shù)的自底向上BDD構(gòu)建算法，提出算法改進(jìn)工作，主要從兩個(gè)方面著手:第一，提出一種更加簡(jiǎn)潔高效的同構(gòu)子網(wǎng)判別方法——子網(wǎng)“核”方法，可用于判斷在網(wǎng)絡(luò)解構(gòu)過程中產(chǎn)生的子網(wǎng)是否同構(gòu)。第二，關(guān)于冗余消除，提出s-t非連通邊擴(kuò)展路徑和冗余節(jié)點(diǎn)型邊擴(kuò)展路徑的概念，并且實(shí)現(xiàn)了這兩類無效擴(kuò)展路徑的消除。
　　(2)依據(jù)Gar

4、y Hardy提出的基于邊收縮和邊刪除操作的自頂向下BDD構(gòu)建算法作出改進(jìn)。H鯽dy算法的核心思想是“分區(qū)劃分”，采用邊界分區(qū)Partition標(biāo)識(shí)網(wǎng)絡(luò)。Partition不僅可以判斷同構(gòu)予網(wǎng)，而且對(duì)網(wǎng)絡(luò)信息的存儲(chǔ)更加簡(jiǎn)潔準(zhǔn)確。改進(jìn)Gary Hardy算法的工作主要包括:在“相同邊界分區(qū)的兩個(gè)同層子網(wǎng)相同”這一定理的基礎(chǔ)上，實(shí)現(xiàn)一種帶冗余消除的自頂向下K端可靠度BDD構(gòu)建算法。在BDD構(gòu)建過程中使用哈希操作實(shí)現(xiàn)子網(wǎng)共享，大大提升了算法性

5、能。
　　(3)實(shí)現(xiàn)同構(gòu)識(shí)別、冗余消除以及子圖共享等技術(shù)之后，BDD構(gòu)建算法的性能得到較大提升，網(wǎng)絡(luò)生成的BDD節(jié)點(diǎn)數(shù)目有所減小，但是規(guī)模依然較大。由于邊排序的質(zhì)量極大地影響所構(gòu)建的BDD節(jié)點(diǎn)數(shù)目，并且BDD邊排序問題是一個(gè)NP難問題，因此本文第五章基于普通廣度優(yōu)先排序策略研究邊排序問題，討論規(guī)則網(wǎng)絡(luò)、最近鄰網(wǎng)絡(luò)中的性能最佳排序起點(diǎn)和最差排序起點(diǎn)。研究網(wǎng)絡(luò)排序起點(diǎn)對(duì)BDD算法的性能影響，為研究啟發(fā)式邊排序提供了重要參考依據(jù)。