%0 Journal Article
%T 基于模拟退火的服务质量路由算法
%A 崔勇？
%A 吴建平？
%A 徐恪？
%J 软件学报
%P 877-884
%D 2003
%X 作为下一代互联网的核心问题之一,多约束的服务质量路由(qosr)用来寻找一条同时满足多个约束条件的可行路径.然而,该问题具有np完全的复杂度.将模拟退火引入多约束qosr计算中,首先使用非线性能量函数将多个qos度量转化成单一能量,然后基于模拟退火的方式求解最小能量路径.首先概述了模拟退火的方法,分析了在qosr中应用模拟退火所面临的关键问题以及解决方案,然后给出了sa_mcp算法及其复杂性分析.实验结果表明,该算法具有很高的性能,同时对网络规模和约束个数都具有很好的扩展性,对qos约束的分布状况也不敏感.此外,只要大部分qos约束存在可行路径,算法的实际运行时间约为o(k(m+nlogn)),即传统dijkstra算法的k倍(k为约束个数).
%K 模拟退火
%K 能量函数
%K qos路由
%K 多约束
%K 可扩展性
%U http://www.jos.org.cn/ch/reader/view_abstract.aspx?file_no=20030502&flag=1