改进的时延约束Steiner树算法  

An Advanced Algorithm for Delay-Constrained Steiner Tree

作　　者：徐剑[1,2] 倪宏[2] 邓浩江[2] 刘磊[2] 

机构地区：[1]中国科学院大学,北京100049 [2]中国科学院声学研究所国家网络新媒体工程技术研究中心,北京100190

出　　处：《西安交通大学学报》2013年第8期38-43,共6页Journal of Xi'an Jiaotong University

基　　金：国家高技术研究发展计划资助项目(2011AA01A102);国家科技支撑计划资助项目(2011BAH11B04);中国科学院战略性先导科技专项子课题(XDA06010302)

摘　　要：针对现有时延约束Steiner树算法时间复杂度较高以及生成的组播树代价较高的问题,提出了一种改进的时延约束Steiner树算法。该算法采用Dijkstra算法路径递增的基本思想和链路共享的方法,在快速搜索阶段,依次搜索到当前树有最小可行代价的节点,将目的节点通过最小可行代价路径加入组播树;在异常处理阶段,将遗漏的目的节点通过最小时延路径加入组播树,进而生成满足时延约束的Steiner树。理论分析和实验结果表明,与同类算法相比,该算法能够以较低的时间复杂度,取得较好的组播树代价。An advanced algorithm for delayconstrained Steiner tree is proposed to focus on the problem that the existing delayconstrained Steiner tree algorithms usually lead to high multicast cost and high time complexity. The proposed algorithm adopts the idea of path increasing in Dijkstra algorithm and the method of link sharing. It iteratively searches the node with the least feasible cost to the current tree and adds the destination node to the current tree through its feasible least cost path in the fast search stage. The missing destination nodes are added to the current tree through its least delay path in the exception handling stage of the algorithm. The delayconstrained Steiner tree is constructed through these two stages of the algorithm. Theoretical analysis, experimental results and comparisons with similar algorithms show that the proposed algorithm can construct multicast tree in lower cost and time complexity.

关 键 词：STEINER树 代价 时延约束 路径递增 链路共享 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]