改进的时延约束Steiner树算法

发布时间：2018-04-01 21:01

  本文选题：Steiner树　切入点：代价　出处：《西安交通大学学报》2013年08期

【摘要】：针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题,提出了一种改进的时延约束Steiner树算法。该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法,在快速搜索阶段,依次搜索到当前树有最小可行代价的节点,将目的节点通过最小可行代价路径加入组播树;在异常处理阶段,将遗漏的目的节点通过最小时延路径加入组播树,进而生成满足时延约束的Steiner树。理论分析和实验结果表明,与同类算法相比,该算法能够以较低的时间复杂度,取得较好的组播树代价。
[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.
【作者单位】： 中国科学院大学;中国科学院声学研究所国家网络新媒体工程技术研究中心;
【基金】：国家高技术研究发展计划资助项目(2011AA01A102) 国家科技支撑计划资助项目(2011BAH11B04) 中国科学院战略性先导科技专项子课题(XDA06010302)
【分类号】：TP393.02

【参考文献】

相关期刊论文 前1条

1 周灵;孙亚民;;基于MPH的时延约束Steiner树算法[J];计算机研究与发展;2008年05期

【共引文献】

相关期刊论文 前5条

1 杨春德;秦宗伟;;一种改进的时延受限多播路由算法[J];计算机工程;2012年10期

2 李元臣;刘维群;;时延受限组播路由的最短路径加速算法求解[J];计算机应用;2010年05期

3 杨春德;康欢;丁亚南;;新的基于MPH的时延约束Steiner树算法[J];计算机应用;2010年11期

4 周贤伟;刘臻臻;林琳;刘涛;王超;;一种具有时延约束的组播路由算法研究[J];计算机应用研究;2009年09期

5 马炫;刘庆;;基于人工鱼群算法的多播树演化寻优[J];通信学报;2012年09期

相关博士学位论文 前1条

1 刘志;无线传感器网络中的能量高效覆盖与路由算法研究[D];北京交通大学;2011年

相关硕士学位论文 前2条

1 杨宁;应用层多播与Steiner算法的研究[D];大连理工大学;2010年

2 徐丽丽;全局最短路径规划的非线性优化方法研究[D];河南科技大学;2012年

【二级参考文献】

相关期刊论文 前3条

1 蒋廷耀,李庆华;多播路由算法MPH的时间复杂度研究[J];电子学报;2004年10期

2 王显雷;吴志美;;二层组播QoS最优生成树[J];计算机研究与发展;2007年05期

3 余燕平,仇佩亮;一种改进的Steiner树启发式算法[J];通信学报;2002年11期

相关博士学位论文 前1条

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

【相似文献】

相关期刊论文 前10条

1 周贤伟;刘臻臻;林琳;刘涛;王超;;一种具有时延约束的组播路由算法研究[J];计算机应用研究;2009年09期

2 杨春德;康欢;丁亚南;;新的基于MPH的时延约束Steiner树算法[J];计算机应用;2010年11期

3 马建平;孙强;;基于拉格朗日松弛法的时延约束组播路由算法[J];计算机技术与发展;2006年11期

4 陈燕;宋玲;李陶深;;一种带时延约束的选播路由算法[J];计算机工程与科学;2006年01期

5 王宝莹;邓文安;;基于遗传算法的受限时延组播路由问题的研究[J];福建电脑;2008年06期

6 王东;曾锋;闵应骅;;基于链路可共享性的多播路由算法[J];湖南大学学报(自然科学版);2006年04期

7 陆慧梅,向勇,史美林,杨敏;一种基于带宽和时延约束的分布式组播路由算法[J];电子学报;2002年S1期

8 金鑫,刘贤德,肖诗源;基于业务量工程带宽和时延约束的QoS路由算法[J];华中科技大学学报(自然科学版);2004年10期

9 郑磊,黄胜华;基于动态变异遗传算法的组播路由算法[J];计算机工程与应用;2005年31期

10 马焱炜,卢苇;遗传算法在选播路由中的应用[J];交通与计算机;2005年04期

相关会议论文 前3条

1 李陶深;陈松乔;陈燕;陈建二;冯凌凌;;一种满足带宽和时延约束的选播QoS路由算法[A];2006年全国开放式分布与并行计算学术会议论文集（二）[C];2006年

2 邹德莉;郝应光;陈晓卉;;基于禁忌搜索的负载均衡组播路由算法[A];中国系统仿真学会第五次全国会员代表大会暨2006年全国学术年会论文集[C];2006年

3 王慧;孙志刚;汤庆新;王东;;面向流媒体传输的带宽和时延限制的QoS路由选择算法[A];2011年全国通信安全学术会议论文集[C];2011年

相关博士学位论文 前4条

1 刘莹;计算机网络中的多播路由算法[D];西安电子科技大学;2000年

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

3 陈琳;基于服务质量的多播路由算法研究[D];武汉大学;2005年

4 董赞强;基于网络编码的数据通信技术研究[D];南京邮电大学;2013年

相关硕士学位论文 前10条

1 张雁楠;一种改进的具有时延约束的组播路由算法[D];暨南大学;2011年

2 曾锋;保证服务质量的多播源路由算法研究[D];湖南大学;2005年

3 章昱;基于QoS的多播路由算法研究与网络仿真[D];武汉理工大学;2005年

4 瞿赛樱;带度约束的组播路由算法研究[D];福州大学;2006年

5 陈兴华;满足QoS约束的多播路由算法[D];东北大学;2008年

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

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

8 刘昌玉;应用层网络中多约束的组播路由算法研究[D];湖南大学;2006年

9 陈品;计算机通信网中的多播路由算法[D];西安电子科技大学;2001年

10 刘金明;基于遗传模拟退火算法的QoS组播路由研究[D];燕山大学;2006年

，

本文编号：1697256