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

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

基于Ad Hoc網(wǎng)絡(luò)的QoS多播路由問題是一個(gè)多約束的NP問題[2]，傳統(tǒng)路由算法很難適應(yīng)Ad Hoc網(wǎng)絡(luò)環(huán)境。遺傳算法是模擬生物界自然進(jìn)化優(yōu)勝劣汰的過程，具有快速全局搜索的能力[3]。對此，筆者在分析Ad Hoc網(wǎng)絡(luò)的QoS多播路由問題的基礎(chǔ)上基于遺傳算法設(shè)計(jì)了有效的QoS多播路由協(xié)議(QoS Routing Protocol based on Genetic Algorithm，QoS-GA），并通過 Matlab仿真驗(yàn)證了 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é)點(diǎn)的集合；E為鏈路邊集合。對于任意鏈路e∈E，有e=(vi，vj），vi∈V，vj∈V，i≠j，vi、vj為相鄰節(jié)點(diǎn)。

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

QoS多播路由問題的目標(biāo)就是尋找一顆能滿足約束條件的多播樹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í)抖動約束。delay＿j（R（s，d））≤DJmax，DJmax為最大時(shí)延抖動；④ 包丟失率約束。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è)物理序號(ID號）。在一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路徑上，按序?qū)⑺泄?jié)點(diǎn)的ID構(gòu)成一個(gè)序列，稱為路徑序列，其編碼為（v1，v2，…，vk），長度為所經(jīng)過的節(jié)點(diǎn)數(shù)。網(wǎng)絡(luò)中存在多條符合多約束條件的路徑，根據(jù)到達(dá)目的節(jié)點(diǎn)的不同，構(gòu)成不同的子集；則一顆滿足多目標(biāo)約束條件的多播路由樹就是在上述不同子集中各選擇一條路徑編號形成的集合。所采用的遺傳算法的交叉和變異算子將對編碼的路徑進(jìn)行操作，經(jīng)過修補(bǔ)后構(gòu)成新的路徑編碼集合，代表新產(chǎn)生的多播路由樹。

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

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

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

5）交叉算子 采用隨機(jī)選擇路徑和一點(diǎn)交叉策略。首先在群體中確定進(jìn)行交叉的2個(gè)個(gè)體，再從2個(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)的路徑，故需要對新產(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)前的染色體，即多播樹由符合約束條件的路徑編號組成，隨機(jī)選擇其中的2條路徑，與路徑池中的目的節(jié)點(diǎn)相同的路徑按照概率進(jìn)行交換，等到新的滿足約束的多播路由樹。為避免變異可能破壞優(yōu)良個(gè)體，降低算法搜索效率，變異后的個(gè)體需重新評估其適應(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è)體存在回路，在滿足包含所有多播目的節(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平臺進(jìn)行仿真，并從端到端延時(shí)、分組投遞率來比較QoS-GA算法和AODV算法的性能。

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

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

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

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

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

圖4 不同移動速度下端到端的延時(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]鄔長安，邵罕，孫艷歌．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．