KOD多播技術(shù)與Steiner樹啟發(fā)式算法.pdf

1、隨著多播技術(shù)的日漸成熟，多播技術(shù)的應(yīng)用也受到廣泛關(guān)注。由于KOD系統(tǒng)具有在單位時間內(nèi)曲目被重復(fù)點(diǎn)播的頻率較高、終端相互之間的網(wǎng)絡(luò)帶寬比較充裕等特點(diǎn)，因此應(yīng)用多播技術(shù)比較適合?；诙嗖ヂ酚膳cSteiner樹之問存在的對應(yīng)關(guān)系，本文確定了KOD視頻多播和Steiner樹啟發(fā)式算法作為本文的研究重點(diǎn)。文中介紹了多播視頻路由技術(shù)；給出了Steiner樹問題定義，并簡要敘述了其精確求解算法、典型的啟發(fā)式算法和貪心算法。 本文將Chaini

2、ng多播技術(shù)應(yīng)用到KOD系統(tǒng)中，設(shè)計實(shí)現(xiàn)了相應(yīng)的多播路由啟發(fā)式算法?；贙OD系統(tǒng)的特點(diǎn)，分析了流服務(wù)器和客戶端中各個模塊的作用，以及內(nèi)容制作中的碼率控制。分析了應(yīng)用層多播在KOD系統(tǒng)中的優(yōu)勢，并較為詳細(xì)地敘述了流服務(wù)器直接提供客戶端流服務(wù)和通過RTSP重定向技術(shù)實(shí)現(xiàn)間接服務(wù)兩種情況下的通信流程。介紹了Chaining多播技術(shù)及其與P2P技術(shù)的關(guān)系，設(shè)計了基于Chaining多播思想的路由啟發(fā)式算法，并將該算法和RTSP重定向技術(shù)相結(jié)合

3、應(yīng)用于KOD系統(tǒng)，試驗(yàn)證明取得了較好的效果。 本文概括了典型啟發(fā)式算法的框架，并在此基礎(chǔ)上分別設(shè)計了基于路徑中跳數(shù)和頂點(diǎn)度數(shù)的Steiner樹的肩發(fā)式算法，使每次添加的路徑盡可能得到了重用。并針對每種算法，均舉出圖例說明了所設(shè)計的算法能求出最優(yōu)解(最小Steiner樹)，而原來的算法得不到最優(yōu)解，證明了所設(shè)計算法的正確性和優(yōu)越性。并還簡單分析了這些算法的最壞性能比的上界。 本文完成了幾種組合啟發(fā)式算法的最壞性能比的分析。

4、常用的啟發(fā)式算法運(yùn)行時間少、易于實(shí)現(xiàn)、求解質(zhì)量較高，但不同啟發(fā)式算法之間又具有不可比較性的特點(diǎn)，因此研究它們相互組合起來的性能具有一定的理論和實(shí)踐意義。通過研究我們發(fā)現(xiàn)組合后啟發(fā)式算法的性能上界是各個算法性能上界中最小的一個；組合啟發(fā)式算法的上界是緊的：并且組合肩發(fā)式算法確保了所求得的解是各個算法中最優(yōu)的一個，保證了解的質(zhì)量，彌補(bǔ)了僅用單個啟發(fā)式算法求得的解的質(zhì)量無法保證的不足。 本文分別研究分析了相對貪心算法(RGA)和k-損

5、失收縮貪心算法(k-LCA)的下界。目前Steiner樹問題的最新研究進(jìn)展都是基于一個簡單的貪心算法框架。由于已知的相對貪心算法最壞性能比的下界1.333和1.385的圖例非常復(fù)雜，本文構(gòu)造了一個算法下界為1.333的更加簡單直觀的圖例證明。本文還設(shè)計了一個新圖例，分析證明了該算法下界至少為1.226，提高了當(dāng)前k-損失收縮貪心算法最壞性能比的下界1.2。 本文最后設(shè)計了改進(jìn)的相對貪心算法，該算法將相對貪心算法和k-損失收縮貪心