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

摘要：

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

关键词：模拟退火、能量函数、QoS路由、多约束、可扩展性

所属期刊栏目：14

分类号：TP301(计算技术、计算机技术)

资助基金：国家自然科学基金90104002,60203025;国家高技术研究发展计划863计划2002AA103067,2001AA121013

在线出版日期：2004-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：877-884