基于最小生成树的时延约束多播路由算法

• 作者: 姚兰
• 来源期刊: 湖南城市学院学报（自然科学版）
• 学科: 工学
• 关键词: 多播路由算法 时延约束 Steiner树
• 年，卷（期）: 2005,（1）
• 所属期刊栏目: 数理科学
• 页码范围: 43-45,49
• 页数: 4页
• 分类号: TP301.6
• 字数: 2682字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-7304.2005.01.014

摘要

多播路由已有广泛的应用,但满足时延约束而代价最小的多播路由算法复杂性很高.提出一种快速有效的基于最小生成树满足端到端时延限制的多播路由算法STBMR.STBMR试图建立原图的满足时延约束的最小生成树,如果这样的最小生成树不存在,则用已找到的树与时延最小路径一起组成满足时延约束的多播树.此算法简单易实现,时间复杂度为O(n2),与KPP[6]算法的时间复杂度O(Δn3)相比,具有更大的应用价值.当然,这是以多播树的费用增大为代价的.实验模拟表明STBMR算法构造的多播树费用比KPP算法构造的约大4%,但STBMR算法执行所耗CPU时间比KPP算法约少54%.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姚兰	湖南大学数学与计量经济学院	5	18	3.0	4.0