（1.北京師范大學信息科學與技術學院，100875；2.北京大學信息科學技術學院，王天楠，100871）
摘要：作為下一代互聯網的核心問題之一，多約束的服務質量路由(QoSR)用來尋找一條同時滿足多個約束
條件的可行路徑，該問題具有NP完全的復雜度�；谀M退火啟發算法具有較高的性能，但當前研究僅適應于可加性度量。本文基于層次分析法對各種度量：可加性、可乘性及最小性度量構造判斷矩陣，求解最大特征根對應的歸一化特征向量作為參數構造新的能量函數，再將此能量函數應用到模擬退火中。分析結果表明，該算法不僅具有基于模擬退火的服務質量路由算法的高性能、對網絡規模和約束個數都具有很好的擴展性、對QoS約束的分布狀況也不敏感的優點，而且對度量類型不敏感。
關鍵詞：層次分析法 模擬退火 能量函數 QoS路由 多約束 可擴展性 QoS度量
A Qos Routing Algorithm by Applying AHP and Simulated Annealing
Wei Zhou1, Tiannan Wang2
1. College of Information Science & Technology, Beijing Normal University,100875
2. School of Electronics Engineering and Computer Science, Peking University
Abstract: As a challenging problem of the upcoming next-generation networks, multi-constrained quality-of-
service routing (QoSR) is to find a feasible path that satisfies the multiple constraints simultaneously. For the NP
complete problem, the heuristic SA_MCP by applying the simulated annealing to Dijkstra’s algorithm is proposed. It has a high performance,but the research on SA for QoSR can only be fitted for additive measure.Based on AHP， this article deal with the whole kinds of QoS mesure:additive,multiplicative and minimality, build a determination matrix and then solve the maximized eigenvalue and normalized 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.
Key words: AHP; simulated annealing; energy function; QoS routing; multiple constraints; scalability; Qos measure
參考文獻
[1] 崔勇，吳建平，徐恪，徐明偉.互聯網絡服務質量路由算法研究綜述.軟件學報，2003，13(11):2065~2075.
[2] Xiao XP， Ni LM. Internet QoS: a big picture. IEEE Network， 1999，13(2):8~18.
[3] Cui Y， Wu， JP， Xu K， Xu MW. Research on internetwork QoS routing algorithms: a survey. Journal of Software， 2002，13(11): 2065~2075 (in Chinese with English abstract).
[4] Crawley， E.， Nair， R.， Rajagopalan， B. et al. A framework for QoS-based routing in the Internet. RFC 2386， 1998.
[5] Quality of service glossary of terms. QoS Forum. 1999. http://www.qosforum.com.
[6] Garey， M.S.， Johnson， D.S. Computers and intractability: a guide to the theory of NP-completeness. Oxford: Freeman， W.H.， 1979.
[7] Hao， F.， Zegura， E.W. On scalable QoS routing: performance evaluation of topology aggregation. In: Sidi， M.， ed. Proceedings of the IEEE INFOCOM 2000. IEEE Communication Society， 2000. 147~156.
[8] Shaikh， A.， Rexford， J.， Shin， K.G. Evaluating the impact of stale link state on quality-of-service routing. IEEE/ACM Transactions on Networking， 2001，9(2):162~176.
[9] Korkmaz， T.， Krunz， M. Multi-Constrained optimal path selection. In: Sengupta， B.， ed. Proceedings of the IEEE INFOCOM 2001. Piscataway， NJ: IEEE Communication Society， 2001. 834~843.
[10] Ergun， F.， Sinha， R.， Zhang， L. QoS routing with performance-dependent costs， In: Sidi， M.， ed. Proceedings of the IEEE INFOCOM 2000. IEEE Communication Society， 2000. 137~146.
[11] 劉來福，黃海洋，曾文藝：數學模型與數學建模.北京：北京師范大學出版社（2009.2）:118~128
[12] 崔勇，吳建平，徐格.基于模擬退火的服務質量路由算法.軟件學報.2003，14(05):877-884
[13] 石為人,嚴明蒙,黃河等.基于熵權系數法的無線傳感器網絡自適應QoS路由算法[J].計算機應用,2011,31(2):298-300,319
[14] 侯麗敏,張瑞坤.基于Agent的QoS組播路由算法及仿真[J].計算機仿真,2011,28(1):140-143.
作者簡介
周偉 2010年于北京師范大學數學科學學院數學與應用數學專業獲學士學位，現為北京師范大學信息科學與技術學院計算機應用技術專業學術學位碩士研究生，研究領域為信息科學、數學學科交叉領域。
