時(shí)延受限的多播路由算法研究.pdf

1、隨著計(jì)算機(jī)和網(wǎng)絡(luò)技術(shù)的快速發(fā)展，通過(guò)網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)急劇增加，許多新的多媒體業(yè)務(wù)正成為信息傳送的重要組成部分。而傳統(tǒng)的單播通信方式滿(mǎn)足不了新業(yè)務(wù)的需求，多播技術(shù)的出現(xiàn)解決了上述問(wèn)題。多播是一種點(diǎn)到多點(diǎn)（多點(diǎn)到多點(diǎn)）的通信方式，它可以有效地利用網(wǎng)絡(luò)資源，提高效率。多播技術(shù)最有效的實(shí)現(xiàn)方法是通過(guò)一棵多播路由樹(shù)來(lái)進(jìn)行信息的傳遞。很多實(shí)時(shí)性較強(qiáng)的多媒體應(yīng)用對(duì)時(shí)延的要求越來(lái)越高，因此，時(shí)延受限的多播路由問(wèn)題成為該領(lǐng)域研究的一個(gè)重要課題。
　　

2、 本文首先介紹了多播產(chǎn)生的背景，多播路由算法的研究現(xiàn)狀，對(duì)目前多播路由算法的研究成果進(jìn)行了分類(lèi)和分析;介紹了時(shí)延約束的多播路由模型，分析了幾種經(jīng)典的算法。在此基礎(chǔ)上提出了一種改進(jìn)的時(shí)延受限Steiner樹(shù)啟發(fā)式算法DCMPH_1，該算法通過(guò)改進(jìn)節(jié)點(diǎn)的搜索路徑，進(jìn)而產(chǎn)生一棵滿(mǎn)足時(shí)延受限的最小代價(jià)多播樹(shù)。仿真結(jié)果表明DCMPH_1算法在性能、空間復(fù)雜度方面均優(yōu)于DCMPH算法。
　　 其次，在DCMPH_1算法中，從最小時(shí)延路徑集

3、合中選擇的路徑雖然滿(mǎn)足時(shí)延約束，但是代價(jià)未必是最優(yōu)的，因此會(huì)影響整棵樹(shù)的代價(jià)性能。針對(duì)此問(wèn)題，提出了改進(jìn)算法DCMPH_2。仿真結(jié)果表明DCMPH_2算法生成的多播樹(shù)的代價(jià)性能優(yōu)于DCMPH_1算法。
　　 此外，改進(jìn)了KPP算法，設(shè)計(jì)了新的代價(jià)和時(shí)延動(dòng)態(tài)優(yōu)化的鏈路選擇函數(shù)，并引入共享邊的思想，提出了一種基于共享邊和鏈路選擇優(yōu)化的時(shí)延約束多播路由算法ESOKPP。在選擇路徑時(shí)，該算法綜合考慮了代價(jià)和時(shí)延兩個(gè)參數(shù)，保證了多播村的性