版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
1、多播是一種群組通信的手段,要求將信息從一個數(shù)據(jù)源同時傳送到多個目的地。構造多播樹是解決多播路由問題的常用方法。有3種不同類型的多播樹:基于數(shù)據(jù)源的樹、Steiner樹和基于中心的樹。這些不同類型的樹中具有代表性的是基于源的最短路徑樹(shortest path tree,簡稱SPT)和Steiner樹。SPT最主要的優(yōu)點就是它使得源結點到每個目的結點的時延最?。欢鳶teiner樹則使得所有連接的消耗總和最小,最大限度地共享帶寬,如果網(wǎng)絡
2、中除源結點外的每個結點都是目的結點,這棵樹就是最小生成樹(minimum spanning tree,簡稱MST)。 在給定的網(wǎng)絡中,構造從源結點到其他目的結點的多播樹,幾乎不可能使它同時達到最小延時和最小總消耗,因此,一些學者研究構造滿足指定時延限制的Steiner樹。當網(wǎng)絡變得足夠大時,從源結點到一些目的結點的最短路徑常常不只一條,而由此構成的SPT也就不是惟一的。在眾多的SPT中,每棵樹的總消耗也不盡相同。因而,有必要研究
3、如何降低SPT的總消耗問題。 最優(yōu)最短路徑樹算法SBPT(shortest best path tree),是通過在構造SPT的過程中采用貪心策略選擇最短路徑,使所構造的生成樹的總消耗得以降低。該算法的時間復雜度較高而不適合大型網(wǎng)絡求解。驅(qū)動多播路由算法DDMC(destination—driven multicasting),是通過使目的結點之間盡可能共享路徑來降低多播樹的總消耗。驅(qū)動最短路徑樹算法DDSP (destinat
4、ion-drivenshortest path)采用Dijkstra算法路徑遞增的基本思想,并結合DDMC算法目的結點共享路徑的方法,當源結點到某結點的最短路徑不惟一時,總是選擇一條與其他目的結點的共享路徑最長的最短路徑,從而降低所構造SPT的總消耗。它因而適合計算目的結點數(shù)較多的最短路徑樹。 低代價最短路徑樹的快速算法FLSPT(fast low—cost shortest path tree)是在DDSP算法的基礎上進行改進
5、,它構造的多播樹與DDSP算法構造的多播樹具有相同性能,但時間復雜度比DDSP算法要低。 仔細研究FLSPT算法可以發(fā)現(xiàn),在Q集合中選擇了距源點S的路徑最小的點u后,如果不把該u點從Q集合中刪除掉,就會出現(xiàn)死循環(huán);同時,如果u是目的結點,如果不把該結點從目的結點集合里刪除也會出現(xiàn)死循環(huán)。 因此,必須在算法中加兩語句:Delete u from Q和Delete u from D。 同時,F(xiàn)LSPT在分析時間復雜度
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 最短路徑樹動態(tài)算法的研究.pdf
- 確定周期序列線性復雜度的快速算法.pdf
- K最短路徑算法和PC機群最短路徑并行算法的研究.pdf
- 基于最短路徑樹的WSN拓撲控制算法研究.pdf
- 動態(tài)網(wǎng)絡中最短路徑樹算法的研究.pdf
- 動態(tài)環(huán)境下最短路徑樹算法的分析與研究.pdf
- 低復雜度CPM系統(tǒng)算法研究.pdf
- 低復雜度視頻編碼算法研究.pdf
- 低復雜度的TPC譯碼算法研究.pdf
- 最短路徑問題―――螞蟻爬行的最短路徑
- LDPC碼低復雜度譯碼算法研究.pdf
- 基于h.264的視頻編碼快速算法及復雜度—失真模型研究
- 有效低復雜度Turbo碼的算法研究.pdf
- 幾種常用的最短路徑算法
- 最短路徑畢業(yè)論文--交通咨詢系統(tǒng)的最短路徑算法與實現(xiàn)
- 必經(jīng)節(jié)點的最短路徑算法研究.pdf
- HEVC低復雜度編碼優(yōu)化算法研究.pdf
- 38573.大規(guī)模復雜網(wǎng)絡的最短路徑近似算法研究
- 最短路徑算法的研究畢業(yè)設計
- 粒子群算法解最短路徑
評論
0/150
提交評論