資源描述：
《低代價最短路徑樹的快速算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在行業(yè)資料-天天文庫。
1、1000-9825/2004/15(05)0660?2004JournalofSoftware軟件學報Vol.15,No.5?低代價最短路徑樹的快速算法+王濤,李偉生(北京交通大學計算機與信息技術學院,北京100044)AFastLow-CostShortestPathTreeAlgorithm+WANGTao,LIWei-Sheng(SchoolofComputerandInformationTechnology,BeijingJiaotongUniversity,Beijing100044,China)+Correspondin
2、gauthor:E-mail:wtzyb4446@163.com,http://www.njtu.edu.cnReceived2003-06-09;Accepted2003-09-05WangT,LiWS.Afastlow-costshortestpathtreealgorithm.JournalofSoftware,2004,15(5):660~665.http://www.jos.org.cn/1000-9825/15/660.htmAbstract:Low-CostShortestPathTreeisacommonly-use
3、dmulticasttreetype,whichcanminimizetheend-to-enddelayandatthesametimereducethebandwidthrequirementifpossible.Basedonthelow-costshortestpathtreealgorithmDDSP(destination-drivenshortestpath)andthroughimprovingonthesearchprocedure,aFastLow-costShortestPathTree(FLSPT)algor
4、ithmispresentedinthispaper.TheShortestPathTreeconstructedbytheFLSPTalgorithmisthesameasthatconstructedbytheDDSPalgorithm,butitscomputationcomplexityislowerthanthatoftheDDSPalgorithm.ThesimulationresultswithrandomnetworkmodelsshowthatFLSPTalgorithmismoreeffective.Keywor
5、ds:multicast;SPT(shortestpathtree);steinertree;MST(minimumspanningtree)摘要:低代價最短路徑樹是一種廣泛使用的多播樹.它能夠在保證傳送時延最小的同時盡量降低帶寬消耗.在DDSP(destination-drivenshortestpath)算法的基礎上,通過改進節(jié)點的搜索過程,提出了快速低代價最短路徑樹算法FLSPT(fastlow-costshortestpathtree).該算法構(gòu)造的最短路徑樹與DDSP算法構(gòu)造的樹具有相同的性能,但其時間復雜度低于DDSP算
6、法.隨機網(wǎng)絡模型的仿真結(jié)果表明,FLSPT算法效率更高.關鍵詞:多播;最短路徑樹;Steiner樹;最小生成樹中圖法分類號:TP301文獻標識碼:A多播是一種群組通信的手段,要求將信息從一個數(shù)據(jù)源同時傳送到多個目的地.為了有效地支持實時的大數(shù)據(jù)量數(shù)據(jù)傳送的應用,一個好的多播路由算法應該能夠控制數(shù)據(jù)傳送的延時和帶寬消耗.構(gòu)造多播樹是解決[1]多播路由問題的常用方法.有3種不同類型的多播樹:基于數(shù)據(jù)源的樹、Steiner樹和基于中心的樹.這些不同類型的樹中具有代表性的是基于源的最短路徑樹(shortestpathtree,簡稱SPT)和
7、Steiner樹.SPT最主要的優(yōu)點就是它使得源節(jié)點到每個目的節(jié)點的時延最小;而Steiner樹則使得所有連接的消耗總和最小,最大限度地共享帶寬,如果網(wǎng)絡中除源節(jié)點外的每個節(jié)點都是目的節(jié)點,這棵樹就是最小生成樹(minimumspanningtree,簡稱?作者簡介:王濤(1980－),男,廣西桂林人,碩士生,主要研究領域為計算機網(wǎng)絡技術,圖論算法設計于分析;李偉生(1945－),男,教授,主要研究領域為算法的設計與分析(并行算法、圖論算法、最優(yōu)化算法),網(wǎng)絡數(shù)據(jù)庫技術.王濤等:低代價最短路徑樹的快速算法661MST).在給定的網(wǎng)絡
8、中,構(gòu)造從源節(jié)點到其他目的節(jié)點的多播樹,幾乎不可能使它同時達到最小延時和最小總消[2~4]耗,因此,一些學者研究構(gòu)造滿足指定時延限制的Steiner樹.當網(wǎng)絡變得足夠大時,從源節(jié)點到一些目的節(jié)點的最短路徑常常不只一條,而由此構(gòu)成的SP
