時延約束的最小費用多播路由算法研究.pdf

1、多播通信,首先建立一棵滿足QoS的多播樹,信源發(fā)出的數(shù)據(jù)包沿著多播樹進行轉發(fā).該多播樹由QoS多播路由算法決定,因此研究構造多播樹的QoS多播路由算法非常重要.該文對時延約束時延約束的最小費用多播路由進行深入研究,具體內容如下:首先,在分析BSMA算法的基礎上,以改進K最短路徑算法降低BSMA算法時間復雜度.與其他時延約束最小費用路由算法相比,BSMA費用性能最優(yōu),但是運算復雜度最高.BSMA算法先是構造了一棵最小時延樹,然后利用超級邊

2、的方法進行費用優(yōu)化.其中,對超級邊的優(yōu)化過程中,使用K最短路徑算法.BSMA計算時間集中在K最短路徑計算,我們引入分支結構和路徑替換方法,在多播成員相對網絡規(guī)模較小的情況下,有效降低BSMA算法的計算時間,使得BSMA算法更具有實用性.改進后的BSMA算法的時間復雜度從O(kn<'3>log(n))降為O(knlog(n)(m+nlog(n))),有Ω(n)因子的優(yōu)化.其次,通過對約束條件下最短路徑問題研究,給出全多項式近似解法(FPA

3、S)的多播路由算法.FPAS多播路由算法是一種低復雜度的、時延約束費用最小多播路由算法.約束條件下最短路徑問題是NP完全的,不存在多項式時間精確算法.我們首先運用取整和縮放方法得到全多項式近似解法.然后,利用動態(tài)規(guī)劃過程給出受限最短路徑問題的兩個偽多項式精確算法,并給出保證多項式時間近似解法的檢驗過程.在近似算法中給出的FPAS的時間復雜度為O(loglog(UB/LB)<'*>(|E|n/ε+loglog(UB/LB))).我們將FP