摘  要： 深入研究移動自組網(wǎng)中的多播路由問題，提出一種適用于移動自組網(wǎng)的基于遺傳算法的QoS多播路由算法。通過引入探測時間限制，有效減少了路由結(jié)點(diǎn)和鏈路的尋找范圍，同時降低了選擇無效結(jié)點(diǎn)和鏈路的可能性。通過證明，該方法滿足帶寬、延遲、延遲抖動、剩余能量約束的要求。在此基礎(chǔ)上，提出了一種基于遺傳算法的QoS路由選擇優(yōu)化算法。仿真試驗(yàn)表明，該算法是可行的，且延時性要優(yōu)于MAODV。

　　關(guān)鍵詞： 移動自組網(wǎng)；多播；遺傳算法；服務(wù)質(zhì)量；路由算法

0 引言

　　移動自組網(wǎng)[1]（Mobile Ad Hoc Networks，MANET）是由移動通信主機(jī)臨時組成的無線多跳網(wǎng)絡(luò)。當(dāng)任何一個移動主機(jī)加入或離開其他移動主機(jī)的通信范圍時，無線連接也會相應(yīng)地形成或斷開。網(wǎng)絡(luò)中的任何一個節(jié)點(diǎn)既充當(dāng)主機(jī)又充當(dāng)路由器。無線網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)也會隨機(jī)地發(fā)生變化。由于移動自組網(wǎng)的動態(tài)性，使得網(wǎng)絡(luò)中的多播路由成為一個具有挑戰(zhàn)性的問題[2]。

　　服務(wù)質(zhì)量（Quality-of-Service，QoS）的基本功能是基于QoS約束[3]，找到一個好的路由。QoS約束包括：端到端的延遲、帶寬保證、抖動、丟包率等。隨著移動自組網(wǎng)對數(shù)據(jù)傳輸穩(wěn)定性要求的提高，提供QoS保證已經(jīng)成為MANET網(wǎng)絡(luò)研究中的一個重要領(lǐng)域[4]。盡管多約束可以更準(zhǔn)確地模仿網(wǎng)絡(luò)和應(yīng)用，但是基于MANET網(wǎng)絡(luò)的QoS多播路由問題是一個多約束的NP完全問題[5]。這就意味著移動自組網(wǎng)中QoS多播路由問題不能在合理的時間范疇內(nèi)優(yōu)化解決，這對于普通的應(yīng)用主體，尤其是對延遲敏感的應(yīng)用是非常關(guān)鍵的。遺傳算法是仿真生物遺傳學(xué)和自然選擇機(jī)理通過人工方式所構(gòu)造的一種新型優(yōu)化算法[6]，它能夠進(jìn)行自適應(yīng)群體尋優(yōu)，并行搜索，產(chǎn)生最優(yōu)解集，已廣泛應(yīng)用于解決各種NP完全問題。本文提出了一種基于遺傳算法的多約束多播路由，達(dá)到按需優(yōu)化的目的。

1 QoS多播路由問題及改進(jìn)

　　QoS多播路由的約束有以下屬性：（1）可加性：total_metric=∑imetrici，即總度量=各節(jié)點(diǎn)度量的和，路徑延遲和跳數(shù)是這類屬性的代表。（2）凹性：min_metric=mini{metrici}，它可以表示為：最小的度量=各節(jié)點(diǎn)度量的最小值，帶寬和剩余能量是這類屬性的代表，它們可以描述成可用帶寬的最小值或路徑上所有的鏈接和結(jié)點(diǎn)的剩余能量。（3）乘性：mul_metric=∏imetrici，即復(fù)合度量=各節(jié)點(diǎn)度量的積，包傳送率是這類屬性的代表。

　　尋找多播路由可以表示為尋找一棵從根節(jié)點(diǎn)到一系列接收節(jié)點(diǎn)的樹。假定網(wǎng)絡(luò)可表示為一個帶權(quán)圖G=（V，E），V是點(diǎn)集，表示一系列移動主機(jī)，E是邊集，表示連接移動主機(jī)間的鏈路，連接節(jié)點(diǎn)u和v的邊e∈E，e也可以表示為（u，v），其中u，v∈V。一棵樹的根節(jié)點(diǎn)是s，s∈V，必須滿足以下各種約束。

2 探測時間限制機(jī)制

　　采用探測時間限制機(jī)制建立路由，當(dāng)建立一條新路由時，接收節(jié)點(diǎn)不在發(fā)送節(jié)點(diǎn)的鄰居節(jié)點(diǎn)列表中，發(fā)送節(jié)點(diǎn)發(fā)送一個路由請求包，該請求包包括請求的延遲抖動最大值、可用帶寬的最小值、剩余電池能量的最小值以及端到端的延遲最大值。當(dāng)收到該請求包時，各接收節(jié)點(diǎn)對照自己和發(fā)送節(jié)點(diǎn)間的約束關(guān)系，判斷是否滿足，如果接收節(jié)點(diǎn)i滿足約束關(guān)系，主機(jī)i將在自己的路由表中添加一條臨時路由，并且再次向下一跳節(jié)點(diǎn)發(fā)送路由請求包。主機(jī)i將在T內(nèi)保持探測狀態(tài)，T=2D-D（e），表示從發(fā)送節(jié)點(diǎn)s到接收節(jié)點(diǎn)i的總延遲。如果在T時間內(nèi)s沒有收到來自i的回應(yīng)，則臨時路由將被刪除。網(wǎng)絡(luò)中的多播路由探測時間限制機(jī)制采用連通性和狀態(tài)發(fā)現(xiàn)機(jī)制實(shí)現(xiàn)。因此，它增加了移動主機(jī)生成滿足約束條件路由的機(jī)率。

　　多播樹新成員加入的主要過程如下。其中，每個節(jié)點(diǎn)的請求信息由search.request，build.request，reply組成。鏈路e的帶寬、延遲、延遲抖動和剩余電池能量分別表示為B（e）、D（e）、J（e）和P（e）。

　　switch（請求信息）

　　case search.request（i）

　　if（節(jié)點(diǎn)i不在發(fā)送節(jié)點(diǎn)的鄰居節(jié)點(diǎn)列表中and min{P（e）}>P）then發(fā)送

　　search.request給網(wǎng)絡(luò)中的所有節(jié)點(diǎn)

　　if（r.packet[i].b≥B and r.packet[i].d≤D and r.packet[i].j≤J）

　　then send build.request（）to next；

　　break

　　case build.request（B，D，J，P）

　　if（b（e）≥B and d（e）≤D and j（e）≤J and min{P（e）}>P）then

　　path.temp=r.packet[i].path；

　　send build（B，D，J，P，path.temp）to next；

　　break

　　case reply（新加入節(jié)點(diǎn)i的應(yīng)答時間t）

　　if（t≤T）then

　　path.permanent=path.temp；

　　else刪除path.temp

　　break

3 性能分析

　　3.1 正確性

　　定理1 采用探測時間限制機(jī)制構(gòu)造的多播樹TM能滿足帶寬、延遲、延遲抖動、剩余能量約束的要求。

　　設(shè)在多播樹TM中，L（s，v）表示從s到v的路徑，V表示L（s，v）上的點(diǎn)集，t表示新加入節(jié)點(diǎn)到s的應(yīng)答時間。

　　證明定理1等價于：

　　證明：

　?。?）根據(jù)探測時間限制機(jī)制，協(xié)議是依據(jù)（delay（L）=（delay（v0，*）+delay（vm，vn）≤D）∧（jitter（L）=（jitter（v0，*）+jitter（vm，vn）≤（J）∧bandwidth（v0，vn）≥B）∧（t≤T）來計算delay和jitter。因此，對于L（s，v）TM，bandwidth（L（s，v））≥B。

　　（2）根據(jù)探測時間限制機(jī)制，當(dāng)且僅當(dāng)delay（L（s，v））≤D且jitter（L（s，v））≤J時，節(jié)點(diǎn)才發(fā)出加入請求，新加入節(jié)點(diǎn)i的探測應(yīng)答時間t≤T，其中T=2D- D（e）。這就保證了從節(jié)點(diǎn)s到i，再從i到s的總延遲時間2×delay（s，i）≤D（e）+T=2D，也即從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的延遲時間小于延遲上限D(zhuǎn)。所以，對于L（s，v）TM，有L（s，v）必滿足延遲和延遲抖動的要求。

　?。?）根據(jù)探測時間限制機(jī)制，當(dāng)min{P（e）}>P時，節(jié)點(diǎn)才發(fā)出加入請求，所以對于?坌L（s，v）TM，有minP（u）＞P。

　　結(jié)合上述（1），（2），（3）的證明可知，依據(jù)探測時間限制機(jī)制所構(gòu)造的多播樹必能滿足帶寬、延遲、延遲抖動和剩余能量的約束。

　　定理2 根據(jù)探測時間限制機(jī)制所構(gòu)造的多播樹TM搜索的可行路徑是沒有回路的。

　　證明 在r.packet路由表中只存在一個輸入端，一個或多個輸出端，從輸入端到輸出端的路徑是一種樹形結(jié)構(gòu)，當(dāng)新節(jié)點(diǎn)加入時，各節(jié)點(diǎn)間仍然構(gòu)成一棵多播樹。樹是連通無回路的，所以TM搜索的可行路徑是沒有回路的。

　　3.2 復(fù)雜性

　　定理3 探測時間限制機(jī)制的時間復(fù)雜度是O（|N|2×  |V|2）

　　證明：由于探測時間限制機(jī)制的計算復(fù)雜度由加入請求、加入和退出操作3部分組成，如果QoS的特征值是延遲、帶寬和剩余能量，則其復(fù)雜度是O（|V|×|E|×   |V|），其中|V|是網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)，|E|是網(wǎng)絡(luò)鏈路數(shù)，其復(fù)雜度記為O（|V|2）。對于一個具有|N|個成員的多播樹，其計算復(fù)雜度O（|N|2×|V|2）。

　　4 遺傳算法在QoS多播路由中的應(yīng)用

　　4.1 優(yōu)化目標(biāo)

　　基于上述說明，QoS路由的優(yōu)化目標(biāo)就是在探測時間限制機(jī)制構(gòu)造的多播樹中，選擇一條合適的路徑，使得：

　　優(yōu)化的目標(biāo)是希望找到一條路徑使得該路徑的延遲最小、抖動最小、可用帶寬最大、剩余電池能量最大。這幾個目標(biāo)的優(yōu)化中，找到最優(yōu)解或次優(yōu)解。采用改進(jìn)的遺傳算法實(shí)現(xiàn)QoS路由問題。為此，構(gòu)造目標(biāo)函數(shù)F：

　接收器到發(fā)射器距離為S[7]，則從發(fā)射器發(fā)送的每比特的能量消耗為Eelec+EampS2。假設(shè)每個發(fā)射器的發(fā)送功率相同，發(fā)送距離同為S，設(shè)節(jié)點(diǎn)的最大能量為Efull（n），節(jié)點(diǎn)消耗的能量為Econsume（n），則節(jié)點(diǎn)的剩余能量量化百分比為E（n）=[Efull（n）-Econsume（n）]/Efull（n）。多播樹的最大生命周期由一個帶有最低電池能量的節(jié)點(diǎn)n所限制。

　　綜上，通過最大化適應(yīng)度值，最小化延遲時間，最大化剩余電池能量，來選擇最好的路由。

　　4.2 編碼機(jī)制

　　在遺傳算法中最重要的步驟就是制定編碼策略，本文采用二進(jìn)制編碼，結(jié)合深度優(yōu)先遍歷樹的每個節(jié)點(diǎn)，每個染色體的解由一個二進(jìn)制串表示，每個染色體的長度都為圖中節(jié)點(diǎn)的個數(shù)n，用G（V，E）代表染色體的解s，設(shè)函數(shù)b（s，i）代表s的第i位。

　　如果b（s，i）=1，則vi∈V；

　　如果b（s，i）=0，則viV；

　　如果vi∈V，vj∈V，且（vi，vj）∈E，則eij∈E。

　　4.3 選擇操作

　　本文中的遺傳算法采用賭輪選擇機(jī)制，將當(dāng)前代的解群中適應(yīng)度最高的兩個個體結(jié)構(gòu)完整地復(fù)制到下一代群體中。若變異概率為Pm∈（0，1），交叉概率Pc∈（0，1），且在選擇前保留當(dāng)前最優(yōu)解的遺傳算法可收斂于全局最優(yōu)解[8]?？芍撨z傳算法可以收斂于全局最優(yōu)解。

　　4.4交叉和變異操作

　　在遺傳算法中的交叉算子使用單點(diǎn)交叉算法，變異算子使用位變異算法，交叉概率為Pc，變異概率為Pm，交叉時隨機(jī)選定一個交叉點(diǎn)，對該點(diǎn)前或后的兩個個體的結(jié)構(gòu)進(jìn)行互換，生成兩個新個體，位變異算法中低能量節(jié)點(diǎn)被高能量節(jié)點(diǎn)所代替。

5 仿真與實(shí)驗(yàn)

　　本實(shí)驗(yàn)基于NS-2仿真工具，在仿真中，使100個節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m的矩形區(qū)域內(nèi)，每個節(jié)點(diǎn)的接口帶寬為2 Mb/s，無線直接通信的距離為250 m，數(shù)據(jù)包大小為512 B，在實(shí)驗(yàn)中指定一個節(jié)點(diǎn)為源節(jié)點(diǎn)，向其他節(jié)點(diǎn)發(fā)送數(shù)據(jù)，每次實(shí)驗(yàn)執(zhí)行300 s，模擬結(jié)果為多次實(shí)驗(yàn)的平均值。

　　組播自組網(wǎng)按需距離矢量路由協(xié)議MAODV（Multicast Adhoc On-demand Distance VectorRouting Protocol）是一種基于樹的組播路由協(xié)議，這種按需的路由技術(shù)有效地減輕了網(wǎng)絡(luò)信道中協(xié)議控制包的負(fù)載，提高了信道利用率[9]。將新算法與MAODV進(jìn)行比較，結(jié)果如下。

　　隨著節(jié)點(diǎn)移動速度的提高，路由更新次數(shù)增多，網(wǎng)絡(luò)拓?fù)渥兓l繁，分組轉(zhuǎn)發(fā)時間變長，端到端的平均延時也逐漸增大。仿真結(jié)果如圖1所示。

　　新算法的延時性要優(yōu)于MAODV，因?yàn)樾滤惴ú捎昧颂綔y時間限制機(jī)制，避免了無限路由的生成，縮小了QoS優(yōu)化路由的范圍。

6 結(jié)論

　　本文設(shè)計了一種基于遺傳算法的QoS多播路由，通過引入探測時間限制有效減少路由節(jié)點(diǎn)和鏈路的尋找范圍，同時降低了選擇無效節(jié)點(diǎn)和鏈路的可能性。這使得在利用遺傳算法對路由問題優(yōu)化時，變?yōu)閷Χ嗖ゼs束樹的優(yōu)化，優(yōu)化目標(biāo)是使得多播約束樹具有低延遲時間和高的剩余電池能量，采用基于樹結(jié)構(gòu)的編碼機(jī)制，編碼和解碼過程易于實(shí)現(xiàn)。仿真結(jié)果表明，本方法是可行和有效的，且延時性要優(yōu)于MAODV。

參考文獻(xiàn)

　　[1] SUZUKI H， KOYAMA A， Implementation and evaluation of a real object-oriented communication method for ad-hoc networks[C]. Proc. of 26th IEEE International Conference on Advanced Information Networking and Application （AINA 2012）， 2012：906-911.

　　[2] BIRADAR R C， MANVI S S. Neighbor supported reliable multipath multicast routing in MANETs[J]. Journal of Network and Computer Applications， 2012，35（3）： 1074-1085.

　　[3] VALLS M G， ALONSO A， ANTONIO J. A dual-band priority assignment algorithm for dynamic QoS resource management[J]. Future Generation Computer Systems， 2012， 28（6）：902-912.

　　[4] SRIDHAR S， BASKARAN R， CHANDRASEKAR P. Energy supported AODV（EN-AODV） for QoS routing in MANET[J]. Procedia-Social and Behavioral Sciences， 2013，73（2）：294-301.

　　[5] 倪云竹，李志蜀，劉一靜.基于蟻群遺傳算法的QoS多播路由研究[J].計算機(jī)應(yīng)用研究，2011，28（10）：3865-3868.

　　[6] ONETY R E， TADEI R， NETO O M， et al. Multiobjective optimization of MPLS-IP networks with a variable neighborhood genetic algorithm[J]. Applied Soft Computing， 2013， 13（11）：4403-4412.

　　[7] 張毅，張秀梅，陳煒，等.移動自組織網(wǎng)絡(luò)中基于移動Agent的多約束QoS多播路由算法[J].信息與控制，2010，39（1）：47-53.

　　[8] Huang Jun， Liu Yanbing. MOEAQ： a QoS-aware multicast routing algorithm for MANET[J]. Expert Systems with Applications， 2010， 37（2）：1391-1399.

　　[9] 樊彪，施榮華.基于移動Ad-Hoc無線網(wǎng)絡(luò)MAODV組播路由協(xié)議研究[J].計算機(jī)工程與設(shè)計，2010，31（1）：48-51.