資源描述：
《低代價(jià)最短路徑樹的快速算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、1000-9825/2004/15(05)0660?2004JournalofSoftware軟件學(xué)報(bào)Vol.15,No.5?低代價(jià)最短路徑樹的快速算法+王濤,李偉生(北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院,北京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)摘要:低代價(jià)最短路徑樹是一種廣泛使用的多播樹.它能夠在保證傳送時(shí)延最小的同時(shí)盡量降低帶寬消耗.在DDSP(destination-drivenshortestpath)算法的基礎(chǔ)上,通過改進(jìn)節(jié)點(diǎn)的搜索過程,提出了快速低代價(jià)最短路徑樹算法FLSPT(fastlow-costshortestpathtree).該算法構(gòu)造的最短路徑樹與DDSP算法構(gòu)造的樹具有相同的性能,但其時(shí)間復(fù)雜度低于DDSP算
6、法.隨機(jī)網(wǎng)絡(luò)模型的仿真結(jié)果表明,FLSPT算法效率更高.關(guān)鍵詞:多播;最短路徑樹;Steiner樹;最小生成樹中圖法分類號(hào):TP301文獻(xiàn)標(biāo)識(shí)碼:A多播是一種群組通信的手段,要求將信息從一個(gè)數(shù)據(jù)源同時(shí)傳送到多個(gè)目的地.為了有效地支持實(shí)時(shí)的大數(shù)據(jù)量數(shù)據(jù)傳送的應(yīng)用,一個(gè)好的多播路由算法應(yīng)該能夠控制數(shù)據(jù)傳送的延時(shí)和帶寬消耗.構(gòu)造多播樹是解決[1]多播路由問題的常用方法.有3種不同類型的多播樹:基于數(shù)據(jù)源的樹、Steiner樹和基于中心的樹.這些不同類型的樹中具有代表性的是基于源的最短路徑樹(shortestpathtree,簡稱SPT)和
7、Steiner樹.SPT最主要的優(yōu)點(diǎn)就是它使得源節(jié)點(diǎn)到每個(gè)目的節(jié)點(diǎn)的時(shí)延最小;而Steiner樹則使得所有連接的消耗總和最小,最大限度地共享帶寬,如果網(wǎng)絡(luò)中除源節(jié)點(diǎn)外的每個(gè)節(jié)點(diǎn)都是目的節(jié)點(diǎn),這棵樹就是最小生成樹(minimumspanningtree,簡稱?作者簡介:王濤(1980－),男,廣西桂林人,碩士生,主要研究領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)技術(shù),圖論算法設(shè)計(jì)于分析;李偉生(1945－),男,教授,主要研究領(lǐng)域?yàn)樗惴ǖ脑O(shè)計(jì)與分析(并行算法、圖論算法、最優(yōu)化算法),網(wǎng)絡(luò)數(shù)據(jù)庫技術(shù).王濤等:低代價(jià)最短路徑樹的快速算法661MST).在給定的網(wǎng)絡(luò)
8、中,構(gòu)造從源節(jié)點(diǎn)到其他目的節(jié)點(diǎn)的多播樹,幾乎不可能使它同時(shí)達(dá)到最小延時(shí)和最小總消[2~4]耗,因此,一些學(xué)者研究構(gòu)造滿足指定時(shí)延限制的Steiner樹.當(dāng)網(wǎng)絡(luò)變得足夠大時(shí),從源節(jié)點(diǎn)到一些目的節(jié)點(diǎn)的最短路徑常常不只一條,而由此構(gòu)成的SP
