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

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