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

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

0 引言

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

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

1 QoS多播路由問(wèn)題及改進(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)的樹(shù),。假定網(wǎng)絡(luò)可表示為一個(gè)帶權(quán)圖G=（V,，E），V是點(diǎn)集,，表示一系列移動(dòng)主機(jī),，E是邊集，表示連接移動(dòng)主機(jī)間的鏈路,，連接節(jié)點(diǎn)u和v的邊e∈E,，e也可以表示為（u，v）,，其中u,，v∈V。一棵樹(shù)的根節(jié)點(diǎn)是s,，s∈V,，必須滿足以下各種約束。

2 探測(cè)時(shí)間限制機(jī)制

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

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

　　switch（請(qǐng)求信息）

　　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)答時(shí)間t）

　　if（t≤T）then

　　path.permanent=path.temp,；

　　else刪除path.temp

　　break

3 性能分析

　　3.1 正確性

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

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

　　證明定理1等價(jià)于：

　　證明：

　?。?）根據(jù)探測(cè)時(shí)間限制機(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）來(lái)計(jì)算delay和jitter,。因此，對(duì)于L（s,，v）TM,，bandwidth（L（s，v））≥B,。

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

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

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

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

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

　　3.2 復(fù)雜性

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

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

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

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

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

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

　接收器到發(fā)射器距離為S[7]，則從發(fā)射器發(fā)送的每比特的能量消耗為Eelec+EampS2,。假設(shè)每個(gè)發(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）。多播樹(shù)的最大生命周期由一個(gè)帶有最低電池能量的節(jié)點(diǎn)n所限制,。

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

　　4.2 編碼機(jī)制

　　在遺傳算法中最重要的步驟就是制定編碼策略，本文采用二進(jìn)制編碼,，結(jié)合深度優(yōu)先遍歷樹(shù)的每個(gè)節(jié)點(diǎn),，每個(gè)染色體的解由一個(gè)二進(jìn)制串表示，每個(gè)染色體的長(zhǎng)度都為圖中節(jié)點(diǎn)的個(gè)數(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)度最高的兩個(gè)個(gè)體結(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，交叉時(shí)隨機(jī)選定一個(gè)交叉點(diǎn),，對(duì)該點(diǎn)前或后的兩個(gè)個(gè)體的結(jié)構(gòu)進(jìn)行互換,，生成兩個(gè)新個(gè)體，位變異算法中低能量節(jié)點(diǎn)被高能量節(jié)點(diǎn)所代替,。

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

　　本實(shí)驗(yàn)基于NS-2仿真工具,，在仿真中，使100個(gè)節(jié)點(diǎn)隨機(jī)分布在1 000 m×1 000 m的矩形區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)的接口帶寬為2 Mb/s,，無(wú)線直接通信的距離為250 m,，數(shù)據(jù)包大小為512 B，在實(shí)驗(yàn)中指定一個(gè)節(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）是一種基于樹(shù)的組播路由協(xié)議,，這種按需的路由技術(shù)有效地減輕了網(wǎng)絡(luò)信道中協(xié)議控制包的負(fù)載，提高了信道利用率[9],。將新算法與MAODV進(jìn)行比較,，結(jié)果如下。

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

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

6 結(jié)論

　　本文設(shè)計(jì)了一種基于遺傳算法的QoS多播路由,，通過(guò)引入探測(cè)時(shí)間限制有效減少路由節(jié)點(diǎn)和鏈路的尋找范圍，同時(shí)降低了選擇無(wú)效節(jié)點(diǎn)和鏈路的可能性,。這使得在利用遺傳算法對(duì)路由問(wèn)題優(yōu)化時(shí),，變?yōu)閷?duì)多播約束樹(shù)的優(yōu)化，優(yōu)化目標(biāo)是使得多播約束樹(shù)具有低延遲時(shí)間和高的剩余電池能量,，采用基于樹(shù)結(jié)構(gòu)的編碼機(jī)制,，編碼和解碼過(guò)程易于實(shí)現(xiàn)。仿真結(jié)果表明,，本方法是可行和有效的,，且延時(shí)性要優(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ì)算機(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] 張毅，張秀梅,，陳煒,，等.移動(dòng)自組織網(wǎng)絡(luò)中基于移動(dòng)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] 樊彪,，施榮華.基于移動(dòng)Ad-Hoc無(wú)線網(wǎng)絡(luò)MAODV組播路由協(xié)議研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010,，31（1）：48-51.