用遺傳算法求解最優ＱｏＳ劃分與路由問題

摘要:未來的通信網將充分支持各種QoS業務，QoS劃分與路由問題研究針對QoS業務的最優化問題#65377;首次提出了求解最優QoS劃分和路由問題的遺傳算法#65377;該算法以K條最短路徑來代替全網最優路徑，大大加快了算法的運行速度#65377;仿真結果證明了該算法的合理性和有效性#65377;

關鍵詞:服務質量劃分; 服務質量路由; 遺傳算法

中圖分類號:TP393.01文獻標志碼:A

文章編號:1001-3695(2007)10-0286-03



0引言

未來通信網絡將支持服務質量(quality of service)的各種應用#65377;在網絡結構復雜和規模很大的情況下，提供服務質量保證是一項很有挑戰性的工作，也是當前網絡應用研究的熱點#65377;QoS路由是QoS體系中的一個重要方面#65377;QoS路由是指針對若干QoS要求和特定優化準則，找到一條路徑(對于QoS單播)或者一個組播樹(對于QoS組播)，使某個QoS指標達到最優，或者使所有QoS要求均得到滿足#65377;

最優QoS劃分(optimal partition of QoS，OPQ)問題是較新提出的一個概念#65377;它是指給定一條路徑和該路徑上的一個端到端的QoS要求D，將D最優化地分解為路徑各個鏈路上的QoS要求，使得路徑總代價最小#65377;有關最優QoS劃分問題的研究有文獻[1~3]#65377;Danny Raz等人在文獻[1]中證明最優QoS劃分問題是NP難問題#65377;

QoS路由與QoS劃分緊密相連，因此可以將兩個問題合并為一個問題求解，即最優QoS劃分與路由(optimal partition of QoS and routing，OPQR)問題#65377;文獻[4]假定路徑代價函數為整數，給出了用動態規劃求解最優QoS劃分和路由問題的精確解的方法，還給出了利用對數采樣和線性縮放方法求取該問題的ε近似解的方法#65377;文獻[5]研究了組播中的最優QoS劃分和路由問題#65377;文獻[6]首先使用文獻[4]給出的方法分別求出了所有源目的節點對之間的最優路由和最優QoS劃分#65377;若有多條最優路徑經過同一條鏈路時，鏈路時延取這多條路徑在該鏈路上的最小值，然后對所有路徑進行松弛，以減少組播的代價#65377;文獻[6]還提出了將OPQR問題轉換為線性規劃問題，用CPLEX 7.1 LP 求解器求解的方法#65377;文獻[4~6]中給出的算法均因為計算量過大而不太適合在實際中應用#65377;

本文首先提出了求解最優QoS劃分的遺傳算法，即GAOPQ算法，并在此遺傳算法的基礎上提出了求解QoS劃分和路由問題的新算法——GAOPQR算法#65377;該算法以K條最短路徑代替從全網中搜索最優路徑，大大降低了OPQR問題的求解難度#65377;同時，該算法具有較好的可擴展性和較短的運行時間，適合在線應用#65377;

5結束語

本文提出的基于遺傳算法的GAOPQR算法，使用K條最短路徑來取代全部可能的路徑，極大地簡化了問題的求解#65377;仿真結果證明，GAOPQR算法是一種求解QoS劃分和路由問題的有效方法#65377;

由于遺傳算法搜索局部最優值的能力較差，可以考慮使用混合遺傳算法求解OPQR問題，例如在每一進化代先使用模擬退火算法搜索局部最優值，再進行遺傳算子運算#65377;

參考文獻:

[1]RAZ D， SHAVITT Y. Optimal partition of QoS requirements with discrete cost functions[J]. IEEE Journal on Selected Areas in Communications， 2000，18:2593-2602.

[2]LORENZ D H， ORDA A. Optimal partition of QoS requirements on unicast paths and multicast trees[J]. IEEE/ACM Transactions on Networking，2002，2:102-114.

[3]ORDA A， SPRINTSON A. A scalable approach to the partition of QoS requirements in unicast and multicast[C]//Proc of IEEE INFOCOM 2002. New York:[s.n.]， 2002:685-694.

[4]LORENZ D H， ORDA A， RAZ D， et al. Efficient QoS partition and routing of unicast and multicast[C]//Proc of IWQoS 2000. Pittsburgh:[s.n.]， 2000:75-83.

[5]ERGüN F， SINHA R， ZHANG L. QoS routing with performance dependent costs[C]//Proc of IEEE INFOCOM. TelAviv， Israel:[s.n.]， 2000.

[6]ATOV I， TRAN H T， HARRIS R J. Efficient QoS partition and routing in multiservice IP networks[C]//Proc of IPCCC 2003. Phoenix:[s.n.]， 2003:435-441.

[7]陳國良，王煦法，莊鎮泉.遺傳算法以及應用[M].北京:人民郵電出版社，1996.

[8]MARTINS V， PASCOAL P， SANTOS D. The K shortest path problem[R]. Coimbra: CISUC， 1998.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”