本文選題：Steiner樹　切入點：代價　出處：《西安交通大學學報》2013年08期

【摘要】：針對現(xiàn)有時延約束Steiner樹算法時間復雜度較高以及生成的組播樹代價較高的問題,提出了一種改進的時延約束Steiner樹算法。該算法采用Dijkstra算法路徑遞增的基本思想和鏈路共享的方法,在快速搜索階段,依次搜索到當前樹有最小可行代價的節(jié)點,將目的節(jié)點通過最小可行代價路徑加入組播樹;在異常處理階段,將遺漏的目的節(jié)點通過最小時延路徑加入組播樹,進而生成滿足時延約束的Steiner樹。理論分析和實驗結(jié)果表明,與同類算法相比,該算法能夠以較低的時間復雜度,取得較好的組播樹代價。
[Abstract]:Due to the high time complexity of the existing delay constrained Steiner tree algorithm and the high cost of the multicast tree, An improved delay-constrained Steiner tree algorithm is proposed, which uses the basic idea of path increment of Dijkstra algorithm and the method of link sharing. In the stage of fast searching, the nodes with the least feasible cost of the current tree are searched in turn. The destination node is added to the multicast tree through the minimum feasible cost path, and the missing destination node is added to the multicast tree through the minimum delay path in the exception processing stage, and then the Steiner tree satisfying the delay constraint is generated. The theoretical analysis and experimental results show that, Compared with similar algorithms, this algorithm can achieve better multicast tree cost with lower time complexity.
【作者單位】： 中國科學院大學;中國科學院聲學研究所國家網(wǎng)絡新媒體工程技術研究中心;
【基金】：國家高技術研究發(fā)展計劃資助項目(2011AA01A102) 國家科技支撐計劃資助項目(2011BAH11B04) 中國科學院戰(zhàn)略性先導科技專項子課題(XDA06010302)
【分類號】：TP393.02

【參考文獻】

相關期刊論文 前1條

1 周靈;孫亞民;;基于MPH的時延約束Steiner樹算法[J];計算機研究與發(fā)展;2008年05期

【共引文獻】

相關期刊論文 前5條

1 楊春德;秦宗偉;;一種改進的時延受限多播路由算法[J];計算機工程;2012年10期

2 李元臣;劉維群;;時延受限組播路由的最短路徑加速算法求解[J];計算機應用;2010年05期

3 楊春德;康歡;丁亞南;;新的基于MPH的時延約束Steiner樹算法[J];計算機應用;2010年11期

4 周賢偉;劉臻臻;林琳;劉濤;王超;;一種具有時延約束的組播路由算法研究[J];計算機應用研究;2009年09期

5 馬炫;劉慶;;基于人工魚群算法的多播樹演化尋優(yōu)[J];通信學報;2012年09期

相關博士學位論文 前1條

1 劉志;無線傳感器網(wǎng)絡中的能量高效覆蓋與路由算法研究[D];北京交通大學;2011年

相關碩士學位論文 前2條

1 楊寧;應用層多播與Steiner算法的研究[D];大連理工大學;2010年

2 徐麗麗;全局最短路徑規(guī)劃的非線性優(yōu)化方法研究[D];河南科技大學;2012年

【二級參考文獻】

相關期刊論文 前3條

1 蔣廷耀,李慶華;多播路由算法MPH的時間復雜度研究[J];電子學報;2004年10期

2 王顯雷;吳志美;;二層組播QoS最優(yōu)生成樹[J];計算機研究與發(fā)展;2007年05期

3 余燕平,仇佩亮;一種改進的Steiner樹啟發(fā)式算法[J];通信學報;2002年11期

相關博士學位論文 前1條

1 周靈;高性能IP組播路由算法研究[D];南京理工大學;2007年

【相似文獻】

相關期刊論文 前10條

1 周賢偉;劉臻臻;林琳;劉濤;王超;;一種具有時延約束的組播路由算法研究[J];計算機應用研究;2009年09期

2 楊春德;康歡;丁亞南;;新的基于MPH的時延約束Steiner樹算法[J];計算機應用;2010年11期

3 馬建平;孫強;;基于拉格朗日松弛法的時延約束組播路由算法[J];計算機技術與發(fā)展;2006年11期

4 陳燕;宋玲;李陶深;;一種帶時延約束的選播路由算法[J];計算機工程與科學;2006年01期

5 王寶瑩;鄧文安;;基于遺傳算法的受限時延組播路由問題的研究[J];福建電腦;2008年06期

6 王東;曾鋒;閔應驊;;基于鏈路可共享性的多播路由算法[J];湖南大學學報(自然科學版);2006年04期

7 陸慧梅,向勇,史美林,楊敏;一種基于帶寬和時延約束的分布式組播路由算法[J];電子學報;2002年S1期

8 金鑫,劉賢德,肖詩源;基于業(yè)務量工程帶寬和時延約束的QoS路由算法[J];華中科技大學學報(自然科學版);2004年10期

9 鄭磊,黃勝華;基于動態(tài)變異遺傳算法的組播路由算法[J];計算機工程與應用;2005年31期

10 馬焱煒,盧葦;遺傳算法在選播路由中的應用[J];交通與計算機;2005年04期

相關會議論文 前3條

1 李陶深;陳松喬;陳燕;陳建二;馮凌凌;;一種滿足帶寬和時延約束的選播QoS路由算法[A];2006年全國開放式分布與并行計算學術會議論文集（二）[C];2006年

2 鄒德莉;郝應光;陳曉卉;;基于禁忌搜索的負載均衡組播路由算法[A];中國系統(tǒng)仿真學會第五次全國會員代表大會暨2006年全國學術年會論文集[C];2006年

3 王慧;孫志剛;湯慶新;王東;;面向流媒體傳輸?shù)膸捄蜁r延限制的QoS路由選擇算法[A];2011年全國通信安全學術會議論文集[C];2011年

相關博士學位論文 前4條

1 劉瑩;計算機網(wǎng)絡中的多播路由算法[D];西安電子科技大學;2000年

2 王珩;基于QoS約束的組播路由算法研究[D];南京理工大學;2004年

3 陳琳;基于服務質(zhì)量的多播路由算法研究[D];武漢大學;2005年

4 董贊強;基于網(wǎng)絡編碼的數(shù)據(jù)通信技術研究[D];南京郵電大學;2013年

相關碩士學位論文 前10條

1 張雁楠;一種改進的具有時延約束的組播路由算法[D];暨南大學;2011年

2 曾鋒;保證服務質(zhì)量的多播源路由算法研究[D];湖南大學;2005年

3 章昱;基于QoS的多播路由算法研究與網(wǎng)絡仿真[D];武漢理工大學;2005年

4 瞿賽櫻;帶度約束的組播路由算法研究[D];福州大學;2006年

5 陳興華;滿足QoS約束的多播路由算法[D];東北大學;2008年

6 丁建;多播路由算法和容錯多播的研究[D];南京理工大學;2004年

7 屈建偉;QoS多播路由算法及仿真研究[D];武漢理工大學;2005年

8 劉昌玉;應用層網(wǎng)絡中多約束的組播路由算法研究[D];湖南大學;2006年

9 陳品;計算機通信網(wǎng)中的多播路由算法[D];西安電子科技大學;2001年

10 劉金明;基于遺傳模擬退火算法的QoS組播路由研究[D];燕山大學;2006年

，

本文編號：1697256