基于层次分析法和模拟退火的服务质量路由算法  

A Qos Routing Algorithm by Applying AHP and Simulated Annealing

作　　者：周伟[1] 王天楠[2] 

机构地区：[1]北京师范大学信息科学与技术学院,100875 [2]北京大学信息科学技术学院,100871

出　　处：《中国电子商情（通信市场）》2013年第1期34-39,共6页

摘　　要：作为下一代互联网的核心问题之一，多约束的服务质量路由（QoSR）用来寻找一条同时满足多个约束条件的可行路径，该问题具有NP完全的复杂度。基于模拟退火启发算法具有较高的性能，但当前研究仅适应于可加性度量。本文基于层次分析法对各种度量：可加性、可乘性及最小性度量构造判断矩阵，求解最大特征根对应的归一化特征向量作为参数构造新的能量函数，再将此能量函数应用到模拟退火中。分析结果表明，该算法不仅具有基于模拟退火的服务质量路由算法的高性能、对网络规模和约束个数都具有很好的扩展性、对QoS约束的分布状况也不敏感的优点，而且对度量类型不敏感。As a challenging problem of the upcoming next-generation networks, multi-con strained quality-of- service routing （QoSR） is to find a feasible path that satisfies the mult iple constraints simultaneously. For the NP complete problem, the heuristic SA_MCP by a pplying the simulated annealing to Dijkstra＇s algorithm is proposed. It has a high performa nce,but the research on SA for QoSR can only be fitted for additive measure.Based on A HP, this article deal with the whole kinds of QoS mesure：additive,multiplicative and mini mality, build a determination matrix and then solve the maximized eigenvalue and normali zed feature vector to get the energy function for SA.The analysis shows that not only the algorithm has the advantages of current SA, but also is insensitive for QoS measure kind.

关 键 词：层次分析法 模拟退火 能量函数 QOS路由 多约束 可扩展性 QOS度量 

分 类 号：O225[理学—运筹学与控制论]