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

彭璐，何加銘

（1.寧波大學(xué)信息科學(xué)與工程學(xué)院，浙江 寧波 315211；2.寧波大學(xué)通信技術(shù)研究所，浙江 寧波 315211；3.浙江省移動(dòng)網(wǎng)應(yīng)用技術(shù)重點(diǎn)實(shí)驗(yàn)室，浙江 寧波 315211）

1 引言

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

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

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

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

2 網(wǎng)絡(luò)模型與問(wèn)題描述

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

3 基于改進(jìn)遺傳算法的QoS路由算法

3.1 編碼

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

3.2 初始種群

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

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

3.3 適應(yīng)度函數(shù)計(jì)算

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

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

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

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

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

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

3.4 選擇

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

3.5 交叉

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

3.6 變異

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

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

（2）如果是無(wú)效鏈路，則使用上述選擇出直接進(jìn)行遺傳的“最佳路徑”來(lái)替換這條無(wú)效路徑。

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

4 算法分析與仿真結(jié)果

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

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

圖1 節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)模型

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

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

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

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

圖3 算法運(yùn)行時(shí)間對(duì)比圖

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

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

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

5 結(jié)束語(yǔ)

本文針對(duì)QoS單播路由問(wèn)題，設(shè)計(jì)了一種改進(jìn)遺傳算法滿足多QoS約束的單播路由算法。該算法具有以下特點(diǎn)：

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

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

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

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

[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服務(wù)組合QoS最優(yōu)化問(wèn)題研究[J]. 計(jì)算機(jī)科學(xué)與應(yīng)用, 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] 陳國(guó)良,王煦法,莊鎮(zhèn)泉,等. 遺傳算法及其應(yīng)用[M]. 北京: 人民郵電出版社, 1996: 3-5.

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

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

[9] 崔遜學(xué),林闖. 一種帶約束的多目標(biāo)服務(wù)質(zhì)量路由算法[J]. 計(jì)算機(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)先搜索遍歷算法分析及其應(yīng)用[J]. 青海師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 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.★