一种多约束最优路径宽度优先松弛算法

• 作者: 贺贵明 钱进 陈立家
• 来源期刊: 计算机应用研究
• 关键词: 多约束 花费 前向搜索 后向搜索 松弛 路径振荡
• 年，卷（期）: 2007,（1）
• 所属期刊栏目: 研究探讨
• 页码范围: 90-93,109
• 页数: 5页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2007.01.028

摘要

在分析单播QoS路由问题的基础上,提出了宽度优先松弛算法BFRA,其核心思想是基于改进的宽度优先搜索策略,采用特殊的松弛算法分别前向(从源节点)和后向(从目标节点)搜索网络拓扑.前向搜索预先计算路径的综合度量、约束等参数,收集路径信息;后向搜索则采用Cost-measurement策略对路径进行选择和筛选,不断搜索到新的可行路径,并选取最优路径.讨论了在路径振荡时BFRA选取次优路径,为其他QoS流的接入预留了资源.理论分析表明BFRA保存的状态信息较少,时间复杂度为线性,仿真结果表明,BFRA发现最优路径的成功率较高.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	贺贵明	武汉大学电子信息学院	108	1405	21.0	33.0
2	钱进	武汉大学计算机学院	8	32	4.0	5.0
3	陈立家	武汉大学计算机学院	6	212	4.0	6.0