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

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

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

3、合中選擇的路徑雖然滿足時(shí)延約束，但是代價(jià)未必是最優(yōu)的，因此會(huì)影響整棵樹的代價(jià)性能。針對此問題，提出了改進(jìn)算法DCMPH_2。仿真結(jié)果表明DCMPH_2算法生成的多播樹的代價(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ù)，保證了多播村的性