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

(長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北 荊州434023）

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

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

1 QoS多播路由模型

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

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

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

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

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

2 QoS多播路由策略

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

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

其中：

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

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

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

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

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

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

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

3 仿真結(jié)果分析

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

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

圖1 不同節(jié)點(diǎn)移動(dòng)速度下的分組投遞率

圖2 不同停留時(shí)間下分組投遞率

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

圖3 不同停留時(shí)間下的端到端的延時(shí)

圖4 不同移動(dòng)速度下端到端的延時(shí)

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

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

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

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

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

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