%0 Journal Article
%T A QoS Routing Algorithm by Applying Simulated Annealing<br>基于模拟退火的服务质量路由算法
%A CUI Yong
%A WU Jian-Ping
%A XU Ke
%A <br>崔勇
%A 吴建平
%A 徐恪
%J 软件学报
%D 2003
%I 
%X 作为下一代互联网的核心问题之一,多约束的服务质量路由(QoSR)用来寻找一条同时满足多个约束条件的可行路径.然而,该问题具有NP完全的复杂度.将模拟退火引入多约束QoSR计算中,首先使用非线性能量函数将多个QoS度量转化成单一能量,然后基于模拟退火的方式求解最小能量路径.首先概述了模拟退火的方法,分析了在QoSR中应用模拟退火所面临的关键问题以及解决方案,然后给出了SA_MCP算法及其复杂性分析.实验结果表明,该算法具有很高的性能,同时对网络规模和约束个数都具有很好的扩展性,对QoS约束的分布状况也不敏感.此外,只要大部分QoS约束存在可行路径,算法的实际运行时间约为O(k(m+nlogn)),即传统Dijkstra算法的k倍(k为约束个数).
%K simulated annealing
%K energy function
%K QoS routing
%K multiple constraints
%K scalability<br>模拟退火
%K 能量函数
%K QoS路由
%K 多约束
%K 可扩展性
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=7735F413D429542E610B3D6AC0D5EC59&aid=ECF6A15419CC4F13&yid=D43C4A19B2EE3C0A&vid=F3583C8E78166B9E&iid=94C357A881DFC066&sid=A766A50385B9FB1F&eid=BEBF2238C7F1C1F1&journal_id=1000-9825&journal_name=软件学报&referenced_num=16&reference_num=17