基于BDD的帶約束的網(wǎng)絡連通可靠性分析.pdf

1、隨著信息技術(shù)的飛快發(fā)展，網(wǎng)絡逐漸成為人類生產(chǎn)、生活所必需的一種載體和工具。網(wǎng)絡一旦發(fā)生故障，將給人們帶來重大的影響，因此加強網(wǎng)絡可靠性建設迫在眉睫。
　　在分析網(wǎng)絡可靠性時，采用二元決策圖BDD(binary decision diagram)技術(shù)能夠有效地提高性能和工作效率。基于BDD的網(wǎng)絡可靠性分析主要是先尋找一種性能較好的網(wǎng)絡變量排序序列，然后利用邊擴展圖EED(edge expansion diagram)構(gòu)建與原網(wǎng)絡等價

2、的BDD，最后計算網(wǎng)絡的可靠度值。本文選定一種合適的邊排序策略，使用網(wǎng)絡分解原理等方法生成與原網(wǎng)絡可靠度等價的BDD，通過遞歸方法計算出整個網(wǎng)絡的可靠度值。
　　在生活中出現(xiàn)很多有關(guān)約束方面的問題，為了更好的解決這些問題，本文根據(jù)已有的基于BDD網(wǎng)絡可靠性分析的研究，對此做了一些研究，具體工作主要包括:
　　(1)帶路徑約束的雙端網(wǎng)絡可靠性分析算法。針對帶路徑約束的雙端網(wǎng)絡可靠性分析問題，即一個數(shù)據(jù)包從S點發(fā)送到T點，必須經(jīng)

3、過中間若干個節(jié)點，并且經(jīng)過這些節(jié)點的先后順序具有一定約束，提出了基于BDD的可靠性分析算法。該算法基于邊擴展圖實現(xiàn)路徑約束，即在邊擴展過程中只保留符合條件的約束路徑，然后構(gòu)建BDD以及進行雙端網(wǎng)絡可靠性分析。這些將有效地解決實際路徑約束的很多問題，特別是用于電子政務和電子商務中路徑約束的點對點通信問題，具有較強的實際意義。
　　(2)帶長度約束的K端網(wǎng)絡可靠性分析算法。在網(wǎng)絡視頻和實時通信應用中需要研究帶長度約束的K端網(wǎng)絡可靠性分

4、析問題，即任意兩端點之間在給定時間延遲D約束內(nèi)的K端網(wǎng)絡可靠性?；趥鹘y(tǒng)不帶路徑約束的雙端和K端網(wǎng)絡可靠性研究基礎上，提出了基于截斷的路徑約束方法;并根據(jù)該方法構(gòu)造BDD模型進行帶約束的K端網(wǎng)絡可靠性分析。該研究方法適用于視頻會議和數(shù)據(jù)傳輸?shù)绕邔c對點信息流在一定時間延遲下的完成傳輸問題，具有較強的實際意義。
　　綜上所述，本文提出基于BDD的帶約束的網(wǎng)絡連通可靠性分析的研究方法主要是針對不同的實際問題，對Kuo等提出的算法進行改