本文選題：Steiner樹(shù)　切入點(diǎn)：代價(jià)　出處：《西安交通大學(xué)學(xué)報(bào)》2013年08期

【摘要】：針對(duì)現(xiàn)有時(shí)延約束Steiner樹(shù)算法時(shí)間復(fù)雜度較高以及生成的組播樹(shù)代價(jià)較高的問(wèn)題,提出了一種改進(jìn)的時(shí)延約束Steiner樹(shù)算法。該算法采用Dijkstra算法路徑遞增的基本思想和鏈路共享的方法,在快速搜索階段,依次搜索到當(dāng)前樹(shù)有最小可行代價(jià)的節(jié)點(diǎn),將目的節(jié)點(diǎn)通過(guò)最小可行代價(jià)路徑加入組播樹(shù);在異常處理階段,將遺漏的目的節(jié)點(diǎn)通過(guò)最小時(shí)延路徑加入組播樹(shù),進(jìn)而生成滿足時(shí)延約束的Steiner樹(shù)。理論分析和實(shí)驗(yàn)結(jié)果表明,與同類(lèi)算法相比,該算法能夠以較低的時(shí)間復(fù)雜度,取得較好的組播樹(shù)代價(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.
【作者單位】： 中國(guó)科學(xué)院大學(xué);中國(guó)科學(xué)院聲學(xué)研究所國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心;
【基金】：國(guó)家高技術(shù)研究發(fā)展計(jì)劃資助項(xiàng)目(2011AA01A102) 國(guó)家科技支撐計(jì)劃資助項(xiàng)目(2011BAH11B04) 中國(guó)科學(xué)院戰(zhàn)略性先導(dǎo)科技專項(xiàng)子課題(XDA06010302)
【分類(lèi)號(hào)】：TP393.02

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

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

【共引文獻(xiàn)】

相關(guān)期刊論文 前5條

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

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

3 楊春德;康歡;丁亞南;;新的基于MPH的時(shí)延約束Steiner樹(shù)算法[J];計(jì)算機(jī)應(yīng)用;2010年11期

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

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

相關(guān)博士學(xué)位論文 前1條

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

相關(guān)碩士學(xué)位論文 前2條

1 楊寧;應(yīng)用層多播與Steiner算法的研究[D];大連理工大學(xué);2010年

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

【二級(jí)參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 蔣廷耀,李慶華;多播路由算法MPH的時(shí)間復(fù)雜度研究[J];電子學(xué)報(bào);2004年10期

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

3 余燕平,仇佩亮;一種改進(jìn)的Steiner樹(shù)啟發(fā)式算法[J];通信學(xué)報(bào);2002年11期

相關(guān)博士學(xué)位論文 前1條

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

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

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

2 楊春德;康歡;丁亞南;;新的基于MPH的時(shí)延約束Steiner樹(shù)算法[J];計(jì)算機(jī)應(yīng)用;2010年11期

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

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

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

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

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

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

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

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

相關(guān)會(huì)議論文 前3條

1 李陶深;陳松喬;陳燕;陳建二;馮凌凌;;一種滿足帶寬和時(shí)延約束的選播QoS路由算法[A];2006年全國(guó)開(kāi)放式分布與并行計(jì)算學(xué)術(shù)會(huì)議論文集（二）[C];2006年

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

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

相關(guān)博士學(xué)位論文 前4條

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

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

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

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

相關(guān)碩士學(xué)位論文 前10條

1 張雁楠;一種改進(jìn)的具有時(shí)延約束的組播路由算法[D];暨南大學(xué);2011年

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：1697256