時(shí)延約束的最小費(fèi)用多播路由算法研究.pdf

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

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

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