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

• 作者: 周灵 孙亚民
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 组播路由 Steiner树 MPH算法 时延约束 NP-complete
• 年，卷（期）: 2008,（5）
• 所属期刊栏目: 计算机网络
• 页码范围: 810-816
• 页数: 7页
• 分类号: TP393.02
• 字数: 4684字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孙亚民	南京理工大学计算机科学与技术学院	117	1149	19.0	28.0
2	周灵	南京理工大学计算机科学与技术学院	28	219	7.0	14.0