基于遺傳算法的QoS多播路由策略研究

(長江大學(xué)計算機科學(xué)學(xué)院，湖北 荊州434023）

Ad Hoc網(wǎng)絡(luò)是一種自創(chuàng)造、自組織和自管理的無線移動網(wǎng)絡(luò)[1]，具有不需要固定基礎(chǔ)設(shè)施、節(jié)點高移動性和動態(tài)變化的拓?fù)浣Y(jié)構(gòu)等特點，被廣泛應(yīng)用于軍事信息通信、臨時緊急網(wǎng)絡(luò)會議、自然災(zāi)害的災(zāi)后恢復(fù)等領(lǐng)域。隨著人們對無線網(wǎng)絡(luò)通信的依賴度越來越高，在網(wǎng)絡(luò)使用過程中，對網(wǎng)絡(luò)的帶寬、時延、時延抖動、丟失率等性能提出了更高的要求，這就要求Ad Hoc網(wǎng)絡(luò)能夠提供更好的服務(wù)質(zhì)量（Quality of Service，QoS）保障，滿足實際應(yīng)用的需求。

基于Ad Hoc網(wǎng)絡(luò)的QoS多播路由問題是一個多約束的NP問題[2]，傳統(tǒng)路由算法很難適應(yīng)Ad Hoc網(wǎng)絡(luò)環(huán)境。遺傳算法是模擬生物界自然進化優(yōu)勝劣汰的過程，具有快速全局搜索的能力[3]。對此，筆者在分析Ad Hoc網(wǎng)絡(luò)的QoS多播路由問題的基礎(chǔ)上基于遺傳算法設(shè)計了有效的QoS多播路由協(xié)議(QoS Routing Protocol based on Genetic Algorithm，QoS-GA），并通過 Matlab仿真驗證了 QoSGA算法的性能。

1 QoS多播路由模型

Ad Hoc網(wǎng)絡(luò)QoS多播路由問題可抽象定義如下：

定義1[4]網(wǎng)絡(luò)拓?fù)淇杀硎緸榧訖?quán)圖G=（V，E），其中，V為網(wǎng)絡(luò)移動節(jié)點的集合；E為鏈路邊集合。對于任意鏈路e∈E，有e=(vi，vj），vi∈V，vj∈V，i≠j，vi、vj為相鄰節(jié)點。

定義2對任意鏈路e∈E，可用四元組（dalay（e），band＿width（e），delay＿j（e），cost（e））表示其QoS屬性值，分別為鏈路的延時、帶寬、延時抖動和費用。對于任意節(jié)點v∈V，用五元組（delay（v），packet＿loss（v），delay＿j（v），energyrequire（v），cost（v））表示其 QoS屬性值，分別為節(jié)點的延時、包丟失率、延時抖動、所需剩余量和費用。用R（s，d）表示從源節(jié)點s到目標(biāo)節(jié)點d的一條路徑，T（s，X）表示多播樹，s∈V為源節(jié)點，X?｛V-｛s｝｝為該多播樹的端點或葉節(jié)點集[5-6]。則有：

QoS多播路由問題的目標(biāo)就是尋找一顆能滿足約束條件的多播樹T（s，X），使其總費用cost（T（s，X））最小，即目標(biāo)函數(shù)為：

且有如下 5 個方面約束：① 延時約束。delay（R（s，d））≤Dmax，Dmax為最大時延；② 帶寬約束。bandwidth（R（s，d））≥Bmin，Bmin為瓶頸帶寬；③ 延時抖動約束。delay＿j（R（s，d））≤DJmax，DJmax為最大時延抖動；④ 包丟失率約束。packet＿loss（R（s，d））≤PLmax，PLmax為最大包丟失率；⑤ 能耗約束。energyrequire（n）≤energyremain（n），energyremain（n）為節(jié)點n當(dāng)前剩余能量。

2 QoS多播路由策略

1）編碼機制 每個節(jié)點賦予一個物理序號(ID號）。在一條從源節(jié)點到目的節(jié)點的路徑上，按序?qū)⑺泄?jié)點的ID構(gòu)成一個序列，稱為路徑序列，其編碼為（v1，v2，…，vk），長度為所經(jīng)過的節(jié)點數(shù)。網(wǎng)絡(luò)中存在多條符合多約束條件的路徑，根據(jù)到達目的節(jié)點的不同，構(gòu)成不同的子集；則一顆滿足多目標(biāo)約束條件的多播路由樹就是在上述不同子集中各選擇一條路徑編號形成的集合。所采用的遺傳算法的交叉和變異算子將對編碼的路徑進行操作，經(jīng)過修補后構(gòu)成新的路徑編碼集合，代表新產(chǎn)生的多播路由樹。

2）適應(yīng)度函數(shù) 適應(yīng)度函數(shù)是衡量目標(biāo)個體優(yōu)劣的尺度。適應(yīng)度值越高，表明個體越優(yōu)化，即多播費用越小。筆者采用的適應(yīng)度函數(shù)為：

其中：

式中，A、B、C、D、E分別表示延時系數(shù)、延時抖動系數(shù)、包丟失率系數(shù)、能量剩余量系數(shù)和頸瓶帶寬系數(shù)；φd（y）、φb（y）、φdj（y）、φpl（y）和φe（y）分別表示時延、帶寬、時延抖動、包丟失率和剩余能量的懲罰函數(shù)，當(dāng)路由滿足約束條件時值為1，否則值分別為λd、λb、λdj、λpl、0，其取值范圍為(0，1），它們的大小決定懲罰的程度，可以根據(jù)具體業(yè)務(wù)要求來確定其值。可見，按照此規(guī)則進行路由選擇時，盡可能選擇時延小、帶寬大、時延抖動小、包丟失率小和能量剩余量大的比較理想的路由。

3）初始化群體 采用路徑回溯方法，獲取網(wǎng)絡(luò)中符合條件的所有路徑，根據(jù)X中目的節(jié)點數(shù)目，隨機選擇相應(yīng)數(shù)量的到不同目的節(jié)點的路徑，將選擇的路徑編號組成集合，形成多播路由樹，以此來生成初始種群，種群中的每一個個體代表一顆符合約束的多播樹。

4）選擇操作 采用最佳保留選擇機制和輪盤賭選擇機制相結(jié)合的方法，即首先將當(dāng)前的解群體中適應(yīng)度最高的個體直接復(fù)制到下一代，然后按照輪盤賭選擇機制進行選擇。

5）交叉算子 采用隨機選擇路徑和一點交叉策略。首先在群體中確定進行交叉的2個個體，再從2個個體中隨機選擇2條路徑，進行交叉操作。路徑的具體交叉操作步驟如下：①隨機產(chǎn)生一個整數(shù)作為交叉點；②進行個體交叉操作；③修補交叉操作產(chǎn)生的路徑。由于交叉后產(chǎn)生的結(jié)果不一定是一條完整的從源到某個目的節(jié)點的路徑，故需要對新產(chǎn)生的路由進行修補。加入結(jié)果路徑之一為（v1，…，vi｜vj，…，vk），則需要判斷vi和vj是否為相鄰節(jié)點，若不相鄰，就需要在vi和vj建立部分路徑，將路徑（v1，…，vi｜vj，…，vk）修改為不含回路的路徑（v1，…，vi，…，vj，…，vk）。

6）變異算子 采用2點交換變異算子。當(dāng)前的染色體，即多播樹由符合約束條件的路徑編號組成，隨機選擇其中的2條路徑，與路徑池中的目的節(jié)點相同的路徑按照概率進行交換，等到新的滿足約束的多播路由樹。為避免變異可能破壞優(yōu)良個體，降低算法搜索效率，變異后的個體需重新評估其適應(yīng)度，只有當(dāng)適應(yīng)度值高于上一代群體的平均適應(yīng)度時，新產(chǎn)生的個體才進入到下一代，此操作同時也提高了群體的多樣性。當(dāng)變異產(chǎn)生的路徑不是一條完整的路徑時，則需要進行路徑修補，修補方法同交叉操作；若新的個體存在回路，在滿足包含所有多播目的節(jié)點的前提下，刪除總費用高的部分路由。

7）終止條件 當(dāng)算法趨向于搜索停止時，即后面的每次迭代所得到的費用值之差非常小的時候，可終止算法，這里用最后5次迭代值的偏差作為衡量參考，其控制參數(shù)可設(shè)置如下：

式中，xk=costk（T（s，X））為第k次迭代后得到的費用值；為后5次迭代所得費用值的期望；1≤m≤Mmax（Mmax為遺傳算法的最大迭代次數(shù)），當(dāng)在最大迭代次數(shù)范圍內(nèi)，S＜10-3時可終止。

3 仿真結(jié)果分析

設(shè)定初始種群為60，最大遺傳迭代次數(shù)為300次，交叉概率pc=0．7，變異概率pm=0．02。采用Matlab平臺進行仿真，并從端到端延時、分組投遞率來比較QoS-GA算法和AODV算法的性能。

1）分組投遞率 分組投遞率反映了網(wǎng)絡(luò)傳輸?shù)目煽啃?，也反映路由協(xié)議的有效性和適應(yīng)網(wǎng)絡(luò)變化能力，投遞率越高，網(wǎng)絡(luò)可靠性越大。節(jié)點移動會導(dǎo)致Ad Hoc網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，變化的頻度導(dǎo)致了網(wǎng)絡(luò)性能的下降。不同節(jié)點移動速度下QoS-GA算法和AODV算法的分組投遞率變化以及不同停留時間下QoS-GA算法和AODV算法的分組投遞率分別如圖1和圖2所示。由圖1可以看出，隨著節(jié)點移動速度的增加，2種算法的包投遞率都在下降，AODV算法包投遞率下降的很快，而QoS-GA算法分組投遞率下降的比較緩慢。由圖2可以看出，隨著網(wǎng)絡(luò)節(jié)點的停留時間越長，2種算法的分組投遞率都在上升，AODV算法分組投遞率上升的速率比較緩慢，而QoS-GA算法分組投遞率上升的速率要快得多。這些都符合Ad Hoc網(wǎng)絡(luò)的特性，運動速度越快，網(wǎng)絡(luò)拓?fù)渥兓驮郊ち?，路由開銷就越大，必然導(dǎo)致丟包率的增加；節(jié)點停留時越間長，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)越穩(wěn)定，路由開銷就越小，節(jié)點分組的投遞率自然會上升。這是由于QoS-GA綜合考慮了延時、延時抖動、帶寬和能量等QoS約束條件，因此具有較強的負(fù)載感知能力，傾向于選擇延時小、帶寬大和能量高的路徑進行發(fā)送數(shù)據(jù)分組，QoS-GA算法的路徑相對穩(wěn)定，分組投遞率較高。

圖1 不同節(jié)點移動速度下的分組投遞率

圖2 不同停留時間下分組投遞率

2）端到端的延時 端到端的延時即目的節(jié)點接收分組的時間與源節(jié)點分組發(fā)送時間的差。延時越小，說明節(jié)點的響應(yīng)速度越快，網(wǎng)絡(luò)質(zhì)量越好。不同停留時間和不同節(jié)點移動速度下QoS-GA算法和AODV算法的端到端的延時分別如圖3和圖4所示。圖3表明，隨著網(wǎng)絡(luò)節(jié)點的停留時間越長，2種算法的端到端延時都在下降，AODV算法端到端延時下降的速率比較緩慢，而QoS-GA算法端到端延時下降的速率要快得多。圖4表明節(jié)點移動速度的增加，2種算法的端到端延時都在上升，AODV算法端到端延時上升的很快，而QoS-GA算法端到端延時上升較緩慢。出現(xiàn)這些情況是由于在仿真初始時刻，即在初始路由請求之后且路由信息沒有建立之前，2種算法都有明顯的延遲。隨著時間的推移，AODV延時仍較大，并且延時下降的速度也比較慢，相比之下QoS-GA算法的路由時延較小，下降速度也較快，這主要是利用了遺傳算法的快速收斂特性，能快速找到滿足需求的路由，從而提高了路由算法的性能。

圖3 不同停留時間下的端到端的延時

圖4 不同移動速度下端到端的延時

[1]鄭少仁，王海濤，趙志峰，等．Ad Hoc網(wǎng)絡(luò)技術(shù) [M]．人民郵電出版社，2005．

[2]金瓊，周世紀(jì)，彭燕妮．基于改進遺傳算法的QoS路由選擇優(yōu)化 [J]．計算機應(yīng)用，2005，25（2）：256-258．

[3]王小平，曹立明．遺傳算法-理論、應(yīng)用及軟件實現(xiàn) [M]．西安：西安交通大學(xué)出版社，2002：4-50．

[4]鄔長安，邵罕，孫艷歌．AdHoc網(wǎng)絡(luò)中基于遺傳蟻群算的QoS多播路由算法 [J]．計算機工程與應(yīng)用，2008，44（20）：107-110．

[5]尹向東．基于遺傳蟻群算法的QoS路由算法研 [J]．計算機工程與應(yīng)用，2009，45（17）：113-115．

[6]黃曉雯，賀細(xì)平，唐賢英．基于遺傳算法的QoS路由選擇與仿真 [J]．計算機仿真，2003，20（6）：43-46．