求解ＱｏＳ組播路由問題的滿意優化方法

摘要：通過分析目前QoS路由優化的一些關鍵問題，提出一種基于滿意優化原理的QoS路由多目標滿意優化求解模型，使之更適合解決QoS路由優化問題。仿真結果表明，該算法能極大地縮短路由求解時間，具有很強的適用性和靈活性。

關鍵詞：服務質量路由;滿意優化;遺傳算法

中圖分類號：TP393文獻標志碼：A

文章編號：1001－3695(2007)08－0309－03



0引言

傳統的QoS路由算法大都試圖盡最大能力找到能滿足用戶要求的最優路由。然而，由于網絡模型和網絡狀態信息的非精確性使得難以獲得最優路由，甚至根本不存在傳統意義下的最優路由。

QoS路由問題是典型的多目標優化問題，其最顯著特點是優化目標之間的不可公度性和優化目標的矛盾性。不可公度性是指各個優化目標之間沒有統一的度量，如時延和時延抖動的度量單位是時間(ms)、費用是元、丟包率無量綱、帶寬的單位用bps等。從物理意義上講，不能像傳統方法那樣把多個優化目標簡單歸并為單個目標。另一個普遍存在著的問題是在進行多約束QoS路由優化時，許多文獻為了計算方便將參數大量簡化。例如去掉網絡中剩余帶寬比QoS要求帶寬小的鏈路后，在剩下的鏈路中只考慮在其他QoS度量下的最優路由，而不再考慮帶寬，對該參數的優化有一定的局限性。

滿意優化本質上是一個多目標優化方法，它擯棄了傳統的最優概念，強調的是滿意而不是最優[1，2]。本文針對QoS路由選擇的實際情況，提出一個基于滿意優化原理的QoS路由求解模型。它在難以獲取最優解的情況下，尋求滿意解以代替最優解；引入滿意度函數，簡單而合理的滿意度函數使得不必為了簡化而省略重要的QoS參數，達到同時優化多個約束參數、保證全部服務質量參數性能的目的。仿真實驗證明，采用改進遺傳算法(GA)實現多約束QoS路由問題滿意優化設計的算法，具有操作簡單、全局收斂速度快、實用性強等優點。

3滿意度函數的設計

滿意度函數是用來評價在一定性能評價準則下求得的滿意解的質量函數。在實際應用中，可以根據優化問題的不同應用背景，設計相應的滿意度函數來完成滿意解的評價。圖1為剩余帶寬占有率的滿意度函數。圖2為時延的滿意度函數。圖1中Rmin代表用戶應用對剩余帶寬的最低要求。考慮到網絡參數的非實時性和不準確性，所有的參數均應留有一定的冗余，這一點可以通過設定略高于業務最低要求的Ropt來保證。以帶寬為例，假定找到一條路徑，其剩余帶寬剛剛滿足業務對帶寬的要求Rmin，則如果簡單地把這條路徑視為可行路徑顯然是不合理的。而且，如果網絡中的部分鏈路已經負載很重，那么出于平衡流量的目的，更應該優先選擇剩余帶寬較多的路徑。滿意度函數是實現這個目的的有效手段。將Ropt點的滿意度設為0.6，而將Rmin點的滿意度設為0，即可達到提高鏈接建立成功率的目的。Rmax的值可以設定為遠大于Rmin，以使那些有很多剩余帶寬的路徑可以得到優先考慮(剩余帶寬最多的路徑帶寬滿意度最高)。其他參數的滿意度函數的設定原理與此類似。其中時延、時延抖動、丟包率和費用采用類似圖2的降折線性滿意度函數。 

給出QoS路由多目標滿意優化的一般步驟：

a)建立網絡QoS路由選擇的數學模型。

b)選擇性能指標(QoS度量)，并設計其滿意度函數。

c)設計綜合滿意度函數。

d)用遺傳算法對多約束QoS路由選擇問題進行搜索尋優計算。

e)通過仿真來驗證優化設計結果。

4QoS組播路由問題的滿意優化遺傳算法

1）編碼

6結束語

滿意優化方法將多個服務質量參數同時優化，性能指標的滿意度函數體現了對各性能指標的要求，而綜合滿意度函數則體現了決策者綜合考慮了系統各種矛盾因素后作出的一種決策要求。這種滿意優化方法融合了設計者關于性能指標要求的智能因素，更利于接近實際情況，具有很廣泛的實用性和靈活性。當許多實際優化問題難以獲得最優解或一些優化問題本身不存在最優解時，用本文的方法去尋求滿意解以代替最優解是解決這類實際問題較好的策略。仿真實驗證明了該算法的實用性、有效性、簡易性以及收斂速度快的特點。當QoS約束參數較多時，該算法也能表示出很好的性能，能滿足一定的實際需求。

參考文獻：

［1］TAN Xianhai，Jin Weidong， ZHAO Duo. The application of multicriterion satisfactory optimization in computer networks design[C]//Proc of the 4th International Conference on Parallel and Distributed Computing， Applications and Technologies.2003.

[2]JIN Weidong， ZHAO Duo. The application of multicriteria satisfactory optimization in FIR digital filter design[C]//Proc of International Workshop on Autonomous Decentralized System.[S.L.]:IEEE Computer Society，2000:227－231.

[3]SUN Baolin， LI Layuan.Research on multiple constrainedbased QoS multicast routing model and algorithms[J].Computer Engineering and Applications， 2003，39(29):41－44.

[4]ZHOU Xiawei，CHEN Changjia，ZHU Gang.A genetic algorithm for multicasting routing problem[C]//Proc of International Conference on Communication Technology. Beijing:IEEE Press，2000:12481253.

[5]王正應，石冰心.基于啟發式遺傳算法的QoS組播路由問題求解[J].計算機學報，2001，24(1):55－61.

[6]WANG Bin，HOU J C.Multicast routing and its QoS extension:problems， algorithm， and protocols[J].IEEE Network，2000，14(1):22－36.

[7]INAGAKI J，HASEYAMA M， KITAJIMA H. A genetic algorithm for determining multiple routes and its applications[C]//Proc of IEEE International Symposium on Circuits and Systems.1999:137140.

[8]Fei Xiang，LUO Junzhou，WU Jieyi，et al.QoS routing based on genetic algorithm[J].Computer Communications，1999，22(15):13941399.

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