基于遺傳算法的多約束QoS單播路由算法*

彭璐，何加銘

（1.寧波大學信息科學與工程學院，浙江 寧波 315211；2.寧波大學通信技術研究所，浙江 寧波 315211；3.浙江省移動網(wǎng)應用技術重點實驗室，浙江 寧波 315211）

1 引言

目前，互聯(lián)網(wǎng)的本質(zhì)是一種無連接的網(wǎng)絡[1-2]，傳統(tǒng)的網(wǎng)絡只提供一種盡力而為的服務。然而，一方面隨著網(wǎng)絡的急劇發(fā)展，人們對網(wǎng)絡傳輸容量、質(zhì)量、實時性的要求越來越高，傳統(tǒng)的網(wǎng)絡已經(jīng)不能滿足用戶的需求；另一方面，網(wǎng)絡帶寬資源日益趨緊，目前的網(wǎng)絡很難同時滿足多種應用要求，尤其是數(shù)據(jù)傳輸容量與實時性的要求。如此有限的網(wǎng)絡帶寬資源如何適當?shù)乇痪W(wǎng)絡系統(tǒng)使用，確保得到最大數(shù)據(jù)傳輸量的同時不以丟失傳輸速率為代價成了一項重要的任務。

為了解決上述問題，QoS機制[3-4]應運而生。它旨在保證服務質(zhì)量，在網(wǎng)絡多媒體等方面有著廣泛的應用。該機制主要涉及多約束路由選擇問題，而該問題為NP-完備問題[5]，這種問題難以用傳統(tǒng)的算法解決。GA（Genetic Algorithm，遺傳算法）[6]是一種模仿自然選擇的過程（優(yōu)勝劣淘、適者生存）和遺傳的機理（交叉和變異）來尋找最優(yōu)解的啟發(fā)式搜索，它具有收斂性好、魯棒性強、潛在并行性等特點，使得節(jié)點QoS路由選擇問題簡單、有效。

對于QoS路由問題，文獻[7]針對多點投遞和單點投遞情況提出一種基于遺傳算法的QoS路由選擇策略，但是該算法采用一種二進制編碼方案，需要對解空間和編碼空間進行轉(zhuǎn)換，增加了算法的復雜度，而且伴隨著網(wǎng)絡節(jié)點增多，解空間迅速增大，這也增加了搜索空間，使得算法效率急劇降低。文獻[8]提出一種基于帶寬時延約束的QoS單播路由算法，但是只考慮一種單一的QoS參數(shù)即時延。文獻[9]提出一種帶約束的多目標服務質(zhì)量路由算法，通過對QoS參數(shù)的限制條件進行闡述，找到了一條滿足QoS的路由，但是該算法通過適應度函數(shù)計算適值，同時約束了帶寬和丟包率，把時延和代價同時作為目標函數(shù)，且沒有經(jīng)過預處理，這不僅使得計算過程過于復雜，而且還增加了算法運行時間。文獻[10]提出一種單播多約束的遺傳算法，但是算法的交叉和變異操作由于沒有經(jīng)過修復，容易產(chǎn)生無效路徑即不存在解。

針對以上問題，本文提出一種基于改進遺傳算法滿足多約束QoS單播路由的算法，在滿足帶寬、時延、丟包率和延時抖動的約束條件下，尋找出一條花費最小的路徑。該算法具有較好的收斂速度，并且通過實驗證明得到的解（最優(yōu)路徑）是全局最優(yōu)的，較好地提高了QoS滿意率。

2 網(wǎng)絡模型與問題描述

網(wǎng)絡模型定義為圖G(N,E)。用N={n1,n2,...,nn}表示節(jié)點集合，用E 表示鏈路集合，每條鏈路記作(u,v)∈E，包含參數(shù)：網(wǎng)絡鏈路帶寬B(u,v)、鏈路時延d(u,v)、鏈路費用c(u,v)、丟包率l(u,v)、延時抖動j(u,v)，給定源節(jié)點s和目的節(jié)點d，網(wǎng)絡帶寬約束Band、時延約束Delay、丟包率約束Loss、延時抖動約束Jitter。多約束QoS單播路由就是尋找滿足給定約束的從源節(jié)點到目的節(jié)點代價最小的路徑。對于從源節(jié)點s 到目的節(jié)點d 的路徑記作P(s,d)（由多條鏈路(u,v)組成），則問題可轉(zhuǎn)化為以下優(yōu)化問題：

3 基于改進遺傳算法的QoS路由算法

3.1 編碼

本算法采用一種可以直接被用于遺傳操作的編碼方案，即路徑序號編碼，它對于網(wǎng)絡節(jié)點以數(shù)字順序編號，按照路徑中節(jié)點出現(xiàn)的順序，依次記錄節(jié)點編號作為群體中的一條染色體。該算法直接用解空間作為編碼空間，無需進行編碼空間轉(zhuǎn)換，簡化了算法操作步驟，節(jié)省了運行時間，提高了運行效率。

3.2 初始種群

在種群初始化時，加入一個預處理環(huán)節(jié)，對給定網(wǎng)絡拓撲結構進行遍歷，把鏈路帶寬與給定限制帶寬對比，將小于給定約束的鏈路作為不可達鏈路，同時從拓撲結構中去除這段鏈路，獲得一個新的拓撲結構圖，經(jīng)過篩選的拓撲圖可能不是連通的。如果得到的拓撲圖是非連通的，且源節(jié)點和目的節(jié)點不在同一連通子圖里，則無法提供服務。假設篩選后得到的滿足帶寬約束的網(wǎng)絡拓撲結構是連通的，那么以下研究將不再考慮帶寬約束條件。帶寬約束篩選的過程，通過保留符合帶寬限制的路徑，不僅減少Q(mào)oS參數(shù)中帶寬這一限制條件，大大方便了算法設計，而且對原有的網(wǎng)絡空間進行縮減，減少編碼空間，使算法性能得到了進一步優(yōu)化。

采用隨機深度優(yōu)先搜索算法進行種群初始化，該算法的基本思想是：以源節(jié)點為起始節(jié)點，隨機選擇1個鄰接節(jié)點作為下一節(jié)點，連接這2個節(jié)點，判斷下一節(jié)點是否為目的節(jié)點，如果不是則把下一節(jié)點作為起始節(jié)點重復上述操作，直至下一節(jié)點是目的節(jié)點，在重復上述操作的過程中要確保網(wǎng)絡中的每個節(jié)點最多在路徑中出現(xiàn)一次，這樣才能保證得到的路徑是無環(huán)且有效的[11-12]。通過完成上述操作將得到所有可能解集即初始種群，但是該種群是不滿足約束條件的。

3.3 適應度函數(shù)計算

遺傳算法通過對每一代個體評估來決定該個體是被拋棄還是遺傳到下一代種群，而這個評估過程的實現(xiàn)是通過使用適值函數(shù)計算一個適應值來確定的。這樣適應度函數(shù)的設計將直接影響到該遺傳算法的收斂速度及是否會陷入局部最優(yōu)解，設計的函數(shù)應能體現(xiàn)個體性能，滿足多QoS約束且花費較小的個體性能好，則其對應的適應值應該大；反之，不滿足約束或者花費較大的個體則適應值應該盡可能小。在自然選擇過程中，適應度指的是生物對當前環(huán)境適應能力的大小，一般適應度高的其生存能力強，反之則容易被自然選擇所淘汰，這就是常說的優(yōu)勝劣淘機制。而遺傳算法是對自然機制的模擬，同理適應度高的個體被選中的概率就大，反之則容易被淘汰。

本算法的適應度函數(shù)定義為：

其中，α 為正實系數(shù)，F(xiàn)d、Fl、Fj分別為fd、fl、fj的正加權系數(shù)（Fd+Fl+Fj=1），分別表示延時、包丟失率和延時抖動在約束函數(shù)中所占的比重，即該性能的限制條件。取值如下：

Φ(Z)是定義的一個懲罰函數(shù)，用來度量QoS參數(shù)的滿足程度。當在約束范圍之內(nèi)時，r 值為1，否則值為r ∈(0,1)。r 是定義的一個懲罰因子，如果r 選取太小，則會造成過重懲罰，使得那些適值小的個體直接被淘汰，永久不會被選擇，這樣將導致算法解陷入局部最優(yōu)；如果選取太大，則懲罰太輕，起不到加快收斂的作用。因此，考慮到實際情況，根據(jù)違反的程度進行懲罰，即違反程度越大則懲罰力度就越大。r取值公式如下：

其中，constraint 表示給定約束值，reality 表示實際值（每條路徑時延、延時抖動、丟包率的值）。

這是本文提出的一種新懲罰制度，通過加強對不滿足約束條件個體的懲罰力度，加快優(yōu)勝劣淘的速度，快速尋到最優(yōu)解。

3.4 選擇

選擇算子的優(yōu)劣是影響算法收斂性的直接因素，本遺傳算法采用結合最佳個體保存法和賭輪法的選擇算法，即首先選出N 個精英（適應度最高）個體作為最佳個體（本算法中N 取1），選中的個體將無需直接參與形成下代群體的交叉和變異操作，這就使得每代的最優(yōu)解在進化的過程中不會被破壞。種群中余下的其他個體則使用賭輪法執(zhí)行選擇。

3.5 交叉

現(xiàn)在常用的交叉方法之一就是單點交叉，本算法將其進行改進之后再使用，主要過程是：對于完成選擇得到的染色體（種群個體），首先分別在其上面選擇2個點，并判斷這2個點是否是起始或者目的節(jié)點序號，如果是則重新選擇，直到選中的節(jié)點非源和目的節(jié)點；然后確定交換位置（交叉點前或者交叉點后），本文選取交叉點之后；最后將2個染色體以1的概率互相替換交叉點之后的鏈路，得到2個新的染色體，即下一代個體（新源到目的節(jié)點的路徑）。

3.6 變異

依據(jù)優(yōu)勝劣淘的思想，通過上述適值計算、選擇、交叉過程得到最優(yōu)個體即最優(yōu)解可能是局部最優(yōu)而不是全局最優(yōu)，這將導致“早熟”現(xiàn)象的產(chǎn)生。使用變異操作通過隨機改變?nèi)旧w中點（路徑中節(jié)點序號）可以避免這種現(xiàn)象的產(chǎn)生，確保了種群的多樣性。對于交叉完成得到的新子女個體以概率進行變異，若變異概率太大則會影響種群的真實性，若太小則不能達到目的，因此變異概率通常是0.1或者更小，這樣可以使算法很快跳出局部最優(yōu)解靠向全局最優(yōu)解。變異方式如下：

（1）判斷當前路徑是否是無效路徑（不存在鏈路或者循環(huán)鏈路）。

（2）如果是無效鏈路，則使用上述選擇出直接進行遺傳的“最佳路徑”來替換這條無效路徑。

本變異算法通過替換不僅避免了“早熟”現(xiàn)象，而且通過路徑替換確保了路徑的有效性，使得種群變得有效，提高了種群質(zhì)量，從而加快了算法的收斂速度。

4 算法分析與仿真結果

該算法仿真工具選取MATLAB，采用Waxman提出的方法[13]來進行實驗網(wǎng)絡的生成，這個方法能夠產(chǎn)生一個具有實際性能的隨機網(wǎng)絡圖，它的中心思想是：在一個確定區(qū)域隨機產(chǎn)生N 個節(jié)點，通過使用歐拉公式來計算2個節(jié)點間距離，任意2個節(jié)點i 和j 之間的連接依照一定概率實現(xiàn)，公式如下：

其中，dis(i,j)表示節(jié)點i 和節(jié)點j之間的距離，Lmax是任意兩點間的最大距離。α 和β 是介于(0,1)之間的參數(shù)，在實驗中分別取0.3和0.4，則得到如圖1所示的節(jié)點網(wǎng)絡結構模型。圖中鏈路的帶寬約束、時延約束、丟包率約束、延時抖動約束分別為20、100、0.05、25，鏈路的度量參數(shù)帶寬、時延、丟包率和延時抖動、費用分別在[10,100]、[0,50]、[0,0.01]、[0,15]、[5,25]內(nèi)隨機產(chǎn)生，源點和終點在網(wǎng)絡拓撲圖中隨機產(chǎn)生。對仿真結果的評價主要分析算法的可行性和收斂性。為了保證數(shù)據(jù)的準確性和穩(wěn)定性，每個數(shù)據(jù)點都是經(jīng)過100次隨機實驗后統(tǒng)計平均得出的。

圖1 節(jié)點網(wǎng)絡結構模型

以上面生成的網(wǎng)絡模型為例進行實驗。設定進化代數(shù)generation為20，交叉率為1，變異率為0.1，源節(jié)點為1，目的節(jié)點為12，種群規(guī)模由初始遍歷的路徑個數(shù)而定。在實驗中，網(wǎng)絡節(jié)點數(shù)分別取13、33、53、73、93，而目的節(jié)點數(shù)始終固定為12，得到如圖2所示的結果。

圖2 不同規(guī)模收斂時參數(shù)變化對比圖

由圖2可知，QoS參數(shù)曲線都在限制曲線（粗線）的下方，因此每代收斂得到的最優(yōu)解都滿足QoS約束，證明了本算法的可行性。為了進一步驗證算法的有效性，本文又做了擴展性實驗，比較該算法和傳統(tǒng)遺傳算法。對每種算法都重復執(zhí)行100次，得到如圖3所示的算法運行時間對比圖。

由圖3可知，在運行時間上，本算法明顯優(yōu)于傳統(tǒng)遺傳算法。在93個節(jié)點網(wǎng)絡中執(zhí)行遺傳算法操作，得到如圖4所示的結果。

圖3 算法運行時間對比圖

由圖4 可知，本遺傳算法在第二代收斂，傳統(tǒng)遺傳算法在第四代收斂。本算法具有較好的收斂性，并且在收斂時，本遺傳算法的QoS參數(shù)值曲線在傳統(tǒng)遺傳算法的上方，這說明本算法的最優(yōu)解優(yōu)于傳統(tǒng)遺傳算法的最優(yōu)解。

圖4 2種算法QoS參數(shù)變化圖

綜合以上分析可知，本算法是可行的，并且較傳統(tǒng)遺傳算法有更好的性能。

5 結束語

本文針對QoS單播路由問題，設計了一種改進遺傳算法滿足多QoS約束的單播路由算法。該算法具有以下特點：

（1）初始種群時引入帶寬約束，淘汰不滿足帶寬約束的路徑，減少搜索空間，提高搜索效率；基于路徑編碼，簡化了編碼操作，去掉了復雜的解碼過程。

（2）計算適值時，引入新的動態(tài)懲罰機制，依據(jù)違反程度來進行懲罰，更好地保證了優(yōu)勝劣淘的思想。

（3）變異算子使用一種新的“最佳路徑”變異方式，更好地保證了種群的有效性。

實驗表明，該單播路由算法是可行有效的且適用于大規(guī)模網(wǎng)絡，并在時間性能和收斂性上都優(yōu)于傳統(tǒng)遺傳算法。目前本算法只對單播路由進行研究，接下來將在組播路由優(yōu)化中進行進一步研究。

[1] S Andrew Tanenbaum. Computer Networks[M]. 4th ed. Prentice & Hall, 1996: 85-86.

[2] C Baransel, W Dobosiewicz, P Gburzynski. Routing in Multihop Packet Switching Networks: Gbps Challenge[J]. IEEE Network, 1995(2): 38-61.

[3] 李香善,蘇子義. Web服務組合QoS最優(yōu)化問題研究[J]. 計算機科學與應用, 2014,4(3): 50-58.

[4] Baolin Sun, Shangchao Pi, Chao Gui, et al. Multiple Constraints QoS Multicast Routing Optimization Algorithm in MANET Based on GA[J]. Progress in Natural Science, 2008,18(3): 331-336.

[5] Zheng Wang, Jon Crowcroft. Quality-of-Service Routing for Supporting Multimedia Applications[J]. IEEE Journal on Selected Areas in Communications, 1996,14(7): 1228-1234.

[6] 陳國良,王煦法,莊鎮(zhèn)泉,等. 遺傳算法及其應用[M]. 北京: 人民郵電出版社, 1996: 3-5.

[7] 何小燕,費翔,羅軍舟,等. Internet中一種基于遺傳算法的QoS路由選擇策略[J]. 計算機學報, 2000,23(11): 1171-1178.

[8] 李勇. 基于帶寬時延約束的QoS單播路由算法[J]. 計算機技術與發(fā)展, 2011,21(3): 128-131.

[9] 崔遜學,林闖. 一種帶約束的多目標服務質(zhì)量路由算法[J]. 計算機研究與發(fā)展, 2004,41(8): 1368-1375.

[10] R Leela, N Thanulekshmi, S Selvakumar. Multi-Constraint Qos Unicast Routing Using Genetic Algorithm (MURUGA)[J]. Applied Soft Computing Journal, 2011,11(2): 1753-1761.

[11] 劉萍,馮桂蓮. 圖的深度優(yōu)先搜索遍歷算法分析及其應用[J]. 青海師范大學學報: 自然科學版, 2007(3): 41-44.

[12] Pranay Chaudhuri. A Self-Stabilizing Algorithm for Minimum-Depth Search of Graphs[J]. Information Sciences, 1999,118(1-4): 241-249.

[13] Bernard M Waxman. Routing of Multipoint Connections[J]. IEEE Journal on Selected Areas in Communications, 1988,6(9): 1617-1622.★