新的基于MPH的时延约束Steiner树算法  

New MPH-based delay-constrained Steiner tree algorithm

作　　者：杨春德[1] 康欢[2] 丁亚南[2] 

机构地区：[1]重庆邮电大学数理学院,重庆400065 [2]重庆邮电大学计算机科学与技术学院,重庆400065

出　　处：《计算机应用》2010年第11期3056-3058,共3页journal of Computer Applications

基　　金：2009年重庆市教委科学技术研究项目(KJ090509)

摘　　要：为了在时延约束条件下进一步优化多播树代价并降低算法的复杂度,研究了时延受限的Steiner树问题。在DCMPH算法的基础上,通过改进节点的搜索路径,提出了一种新的基于MPH的时延约束Steiner树算法。该算法中每个目的节点通过最小代价路径加入当前多播树;若时延不满足要求,则通过合并最小时延树进而产生一个满足时延约束的最小代价多播树。仿真实验表明,新算法在性能、空间复杂度方面均优于DCMPH算法。In order to optimize cost and decrease complexity with a delay upper bound, the delay-constrained Steiner tree problem was studied. Based on the Delay-Constrained Minimum Path Heuristic （DCMPH） algorithm and through improvement on the search path, a new MPH-based delay-constrained Steiner tree algorithm was presented in this paper. With the new algorithm, a destination node could join the existing multicast tree by selecting the path whose cost was the least; if the path＇s delay destroyed the delay upper bound, the least-delay path computed by shortest path tree algorithm was used to take the place of the least-cost path to join the current multicast tree. By the way, a low-cost multicast spanning tree could be constructed and the delay upper bound would not be destroyed. The simulation results show that the new algorithm is superior to DCMPH algorithm in the performance of spanning tree and space complexity.

关 键 词：多播树 时延约束 STEINER树 

分 类 号：TP393[自动化与计算机技术—计算机应用技术] TP301.6[自动化与计算机技术—计算机科学与技术]