基于OBDD及其擴(kuò)展形式ADD的網(wǎng)絡(luò)可靠性分析.pdf

1、網(wǎng)絡(luò)可靠性作為一種衡量網(wǎng)絡(luò)正常工作能力的標(biāo)準(zhǔn)，是網(wǎng)絡(luò)設(shè)計(jì)、驗(yàn)證和維護(hù)階段的核心問題。然而目前網(wǎng)絡(luò)基本可靠性分析往往存在過高估計(jì)網(wǎng)絡(luò)可靠性的缺陷，而約束條件下的網(wǎng)絡(luò)可靠性分析又存在計(jì)算較為復(fù)雜繁瑣，處理較大規(guī)模網(wǎng)絡(luò)時(shí)會受組合復(fù)雜性制約的缺陷，因而考慮用戶需求并采用符號技術(shù)或隱式描述技術(shù)是解決目前網(wǎng)絡(luò)可靠性分析中存在的問題的一種可行策略。
　　有序二叉決策圖(Ordered Binary Decision Diagram,OBDD)和

2、代數(shù)決策圖(Algebraic Decision Diagram,ADD)均是圖形化數(shù)據(jù)結(jié)構(gòu)，可以實(shí)現(xiàn)狀態(tài)空間或變量組合的隱式表示和搜索，且具有不交化、高效存儲和易操作等特性，因而可以從一定程度上緩解組合復(fù)雜性問題?；谝陨显?，本文做了基于OBDD及其擴(kuò)展形式ADD分析網(wǎng)絡(luò)可靠性的相關(guān)研究，取得的主要研究成果如下：
　?。?）針對基于OBDD分析網(wǎng)絡(luò)基本可靠性時(shí)忽略網(wǎng)絡(luò)組件的權(quán)值及用戶需求等問題，在最基本的網(wǎng)絡(luò)模型基礎(chǔ)上，結(jié)合隨

3、機(jī)加權(quán)網(wǎng)絡(luò)(Probabilistic Weighted Network,PWN)的定義，構(gòu)建了PWN的形式化模型，給出了分析隨機(jī)加權(quán)網(wǎng)絡(luò)可靠性的符號OBDD算法。通過與Yeh改進(jìn)的SDP(Sum of Disjoint Products Method,不交和法)求解隨機(jī)加權(quán)網(wǎng)絡(luò)可靠性的算法進(jìn)行實(shí)驗(yàn)對比，結(jié)果表明本文給出的符號OBDD算法具有更高的執(zhí)行效率，能更精確地計(jì)算出滿足用戶需求的網(wǎng)絡(luò)可靠性。
　?。?）在基于OBDD計(jì)算隨

4、機(jī)加權(quán)網(wǎng)絡(luò)可靠性的基礎(chǔ)上，為了更全面地分析網(wǎng)絡(luò)可靠性，了解網(wǎng)絡(luò)組件對網(wǎng)絡(luò)可靠性的影響，進(jìn)而找出網(wǎng)絡(luò)的薄弱環(huán)節(jié)及確定最可能引發(fā)網(wǎng)絡(luò)故障的組件，給出了基于OBDD單次遍歷同時(shí)計(jì)算多個(gè)組件的Birnbaum重要性測度和關(guān)鍵重要性測度的算法。該算法充分利用了OBDD結(jié)構(gòu)的特性，提高了求解效率。
　　（3）針對在網(wǎng)絡(luò)基本可靠性分析中忽略網(wǎng)絡(luò)完成用戶需求能力的問題，以及約束條件下的網(wǎng)絡(luò)可靠性分析中計(jì)算較為復(fù)雜繁瑣的問題，引入了最快路徑問題思想

5、，構(gòu)建了容量和時(shí)延約束下的網(wǎng)絡(luò)形式化模型，提出了一個(gè)用于判斷邊或路徑是否滿足約束條件的定理，并證明了其正確性，給出了分析容量和時(shí)延約束下的網(wǎng)絡(luò)可靠性的符號ADD算法。實(shí)驗(yàn)結(jié)果表明，與Yeh改進(jìn)的SDP求解容量和時(shí)延約束下的網(wǎng)絡(luò)可靠性算法及計(jì)算網(wǎng)絡(luò)基本可靠性算法相比，本文給出的符號ADD算法不僅具有更高的計(jì)算效率，能更精確地計(jì)算出網(wǎng)絡(luò)滿足用戶需求的能力，而且還能求出網(wǎng)絡(luò)單位時(shí)間內(nèi)傳輸流量的大小及其相應(yīng)的概率，從而可以更全面地分析網(wǎng)絡(luò)的可靠