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

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

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

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

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

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