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

摘要：

为了在时延约束务件下进一步优化组播树代价,并降低算法计算复杂度,研究了时延受限的Steiner树问题.分析了MPH(minimum path heuristic)算法的计算复杂度;在此基础上设计了一个时延约束Steiner树算法DCMPH(delay-constrained MPH)用于构造时延约束最小代价组播树.该算法中每个目的结点通过与当前组播树有最小代价的路径加入组播树;若时延不满足要求,则通过合并最小时延SPT(shortest path tree)树进而产生一个满足时延约束的最小代价组播树.仿真实验表明,DCMPH算法生成的组播树在保证时延要求的情况下,与同类算法相比取得了很好的代价性能和较低的计算复杂度.

关键词：组播路由、Steiner树、MPH算法、时延约束、NP-complete

所属期刊栏目：45

分类号：TP393.02(计算技术、计算机技术)

资助基金：国家教育部博士点专项基金项目20050288015

在线出版日期：2008-07-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：810-816