基于模拟退火的服务质量路由算法

• 作者: 吴建平 崔勇 徐恪
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 模拟退火 能量函数 QoS路由 多约束 可扩展性
• 年，卷（期）: 2003,（5）
• 所属期刊栏目: 算法设计与分析
• 页码范围: 877-884
• 页数: 8页
• 分类号: TP301
• 字数: 7270字
• 语种: 中文

摘要

作为下一代互联网的核心问题之一,多约束的服务质量路由(QoSR)用来寻找一条同时满足多个约束条件的可行路径.然而,该问题具有NP完全的复杂度.将模拟退火引入多约束QoSR计算中,首先使用非线性能量函数将多个QoS度量转化成单一能量,然后基于模拟退火的方式求解最小能量路径.首先概述了模拟退火的方法,分析了在QoSR中应用模拟退火所面临的关键问题以及解决方案,然后给出了SA_MCP算法及其复杂性分析.实验结果表明,该算法具有很高的性能,同时对网络规模和约束个数都具有很好的扩展性,对QoS约束的分布状况也不敏感.此外,只要大部分QoS约束存在可行路径,算法的实际运行时间约为O(k(m+nlogn)),即传统Dijkstra算法的k倍(k为约束个数).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐恪	清华大学计算机科学与技术系	154	2232	24.0	42.0
2	吴建平	清华大学计算机科学与技术系	298	5155	36.0	63.0
3	崔勇	清华大学计算机科学与技术系	60	1585	18.0	39.0