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

Breadth First Relax Algorithm for Multi-Constrained Optimal Path

作　　者：钱进[1] 陈立家[1] 贺贵明[2] 

机构地区：[1]武汉大学计算机学院,湖北武汉430079 [2]武汉大学电子信息学院,湖北武汉430079

出　　处：《计算机应用研究》2007年第1期90-93,109,共5页Application Research of Computers

基　　金：国家自然科学基金资助项目(90204008)

摘　　要：在分析单播QoS路由问题的基础上,提出了宽度优先松弛算法BFRA,其核心思想是基于改进的宽度优先搜索策略,采用特殊的松弛算法分别前向(从源节点)和后向(从目标节点)搜索网络拓扑。前向搜索预先计算路径的综合度量、约束等参数,收集路径信息;后向搜索则采用Cost-measurement策略对路径进行选择和筛选,不断搜索到新的可行路径,并选取最优路径。讨论了在路径振荡时BFRA选取次优路径,为其他QoS流的接入预留了资源。理论分析表明BFRA保存的状态信息较少,时间复杂度为线性,仿真结果表明,BFRA发现最优路径的成功率较高。Based on analysis of unique cast QoS routing,the paper proposes BFRA（ Breadth First Relax Algorithm）. And it＇s main idea based on improved BFS is adopting special relax policy, and searching the network topology seperately from forwardness（ source node） and backward （destination node）. Forward search pre-computs integrated metric, constrains and other parameters of path, gathering path info; backward search chooses and filters pathes adopting Cost-measurement policy, and chooses the optimal path on finding new pathes. And the paper points that BFRA chooses hypo-optimal path on the condition of path surge,and retains the resources for other QoS request. The theory analysis indicates that BFRA needs less status info reserved and it＇s time complexity is linearity. The experiments indicate that BFRA＇s SR of finding the optimal path is higher.

关 键 词：多约束 花费 前向搜索 后向搜索 松弛 路径振荡 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]