橋網(wǎng)絡(luò)及無線通信網(wǎng)絡(luò)的可靠性研究.pdf

1、該文主要對普通網(wǎng)絡(luò)系統(tǒng)和無線通信網(wǎng)絡(luò)的可靠性問題進行了研究.按照網(wǎng)絡(luò)的拓撲結(jié)構(gòu)可分為兩部分.1.一般計算機通信網(wǎng)絡(luò)的可靠性,首先我們定義了一類網(wǎng)絡(luò)—橋網(wǎng)絡(luò),給出了無圈有向網(wǎng)絡(luò)的拓撲性質(zhì),提出了簡化網(wǎng)絡(luò)可靠性計算的一類新的可靠性保護縮減(Reliabilty-preserving Reduction)—源橋縮減,給出了計算無圈有向橋網(wǎng)絡(luò)可靠性的算法,并且證明了該算法是一多項式時間算法.其次給出了無向橋網(wǎng)絡(luò)的拓撲性質(zhì),提出了簡化網(wǎng)絡(luò)可靠性計

2、算的一類新的可靠性保護縮減(Reliability-preserving Reduction)—橋縮減,給出了計算橋網(wǎng)絡(luò)可靠性的算法,并且證明了該算法也是一多項式時間算法.2.無線通信網(wǎng)絡(luò)的可靠性,我們在現(xiàn)有的概率無向圖的基礎(chǔ)上,定義了最簡路(S P)和有序根樹(S P R T),給出了最簡路的性質(zhì),使用深度優(yōu)法(first-depth-search)按照生成最簡路(S P)的順序生成網(wǎng)絡(luò)的有序根樹,利用網(wǎng)絡(luò)的拓撲結(jié)構(gòu)和不交和方法提出了

3、2個計算無線網(wǎng)絡(luò)的ST可靠性的遞歸Ⅱ公式,這2個公式能生成非常簡潔的可靠性表達式,這2個算法對有向、無向圖都適用,實現(xiàn)簡單有效.在概率有向圖的基礎(chǔ)上,定義了極大P子圖,根據(jù)容斥原理給出了類似著名的Satyanarayanna公式的拓撲公式,在此基礎(chǔ)上提供了一個計算無線網(wǎng)絡(luò)的ST可靠性算法;結(jié)合不交和方法改進了上面的拓撲公式,使新的拓撲公式含有更少的項,也提供了一個計算無線網(wǎng)絡(luò)的ST可靠性算法;最后給出了計算無線網(wǎng)絡(luò)的K—終點可靠性計算的