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

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

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

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

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

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