摘 要： 深入研究移動(dòng)自組網(wǎng)中的多播路由問題，提出一種適用于移動(dòng)自組網(wǎng)的基于遺傳算法的QoS多播路由算法。通過引入探測時(shí)間限制，有效減少了路由結(jié)點(diǎn)和鏈路的尋找范圍，同時(shí)降低了選擇無效結(jié)點(diǎn)和鏈路的可能性。通過證明，該方法滿足帶寬、延遲、延遲抖動(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ǎng)絡(luò)。當(dāng)任何一個(gè)移動(dòng)主機(jī)加入或離開其他移動(dòng)主機(jī)的通信范圍時(shí)，無線連接也會(huì)相應(yīng)地形成或斷開。網(wǎng)絡(luò)中的任何一個(gè)節(jié)點(diǎn)既充當(dāng)主機(jī)又充當(dāng)路由器。無線網(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)性的問題[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多播路由問題是一個(gè)多約束的NP完全問題[5]。這就意味著移動(dòng)自組網(wǎng)中QoS多播路由問題不能在合理的時(shí)間范疇內(nèi)優(yōu)化解決，這對(duì)于普通的應(yīng)用主體，尤其是對(duì)延遲敏感的應(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ò)可表示為一個(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。一棵樹的根節(jié)點(diǎn)是s，s∈V，必須滿足以下各種約束。
2 探測時(shí)間限制機(jī)制
采用探測時(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)保持探測狀態(tài)，T=2D-D（e），表示從發(fā)送節(jié)點(diǎn)s到接收節(jié)點(diǎn)i的總延遲。如果在T時(shí)間內(nèi)s沒有收到來自i的回應(yīng)，則臨時(shí)路由將被刪除。網(wǎng)絡(luò)中的多播路由探測時(shí)間限制機(jī)制采用連通性和狀態(tài)發(fā)現(xiàn)機(jī)制實(shí)現(xiàn)。因此，它增加了移動(dòng)主機(jī)生成滿足約束條件路由的機(jī)率。
多播樹新成員加入的主要過程如下。其中，每個(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 采用探測時(shí)間限制機(jī)制構(gòu)造的多播樹TM能滿足帶寬、延遲、延遲抖動(dòng)、剩余能量約束的要求。
設(shè)在多播樹TM中，L（s，v）表示從s到v的路徑，V表示L（s，v）上的點(diǎn)集，t表示新加入節(jié)點(diǎn)到s的應(yīng)答時(shí)間。
證明定理1等價(jià)于：
證明：
（1）根據(jù)探測時(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）來計(jì)算delay和jitter。因此，對(duì)于L（s，v）TM，bandwidth（L（s，v））≥B。
（2）根據(jù)探測時(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的探測應(yīng)答時(shí)間t≤T，其中T=2D- D（e）。這就保證了從節(jié)點(diǎn)s到i，再從i到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)的要求。
（3）根據(jù)探測時(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ù)探測時(shí)間限制機(jī)制所構(gòu)造的多播樹必能滿足帶寬、延遲、延遲抖動(dòng)和剩余能量的約束。
定理2 根據(jù)探測時(shí)間限制機(jī)制所構(gòu)造的多播樹TM搜索的可行路徑是沒有回路的。
證明 在r.packet路由表中只存在一個(gè)輸入端，一個(gè)或多個(gè)輸出端，從輸入端到輸出端的路徑是一種樹形結(jié)構(gòu)，當(dāng)新節(jié)點(diǎn)加入時(shí)，各節(jié)點(diǎn)間仍然構(gòu)成一棵多播樹。樹是連通無回路的，所以TM搜索的可行路徑是沒有回路的。
3.2 復(fù)雜性
定理3 探測時(shí)間限制機(jī)制的時(shí)間復(fù)雜度是O（|N|2× |V|2）
證明：由于探測時(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è)成員的多播樹，其計(jì)算復(fù)雜度O（|N|2×|V|2）。
4 遺傳算法在QoS多播路由中的應(yīng)用
4.1 優(yōu)化目標(biāo)
基于上述說明，QoS路由的優(yōu)化目標(biāo)就是在探測時(shí)間限制機(jī)制構(gòu)造的多播樹中，選擇一條合適的路徑，使得：
優(yōu)化的目標(biāo)是希望找到一條路徑使得該路徑的延遲最小、抖動(dòng)最小、可用帶寬最大、剩余電池能量最大。這幾個(gè)目標(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è)每個(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）。多播樹的最大生命周期由一個(gè)帶有最低電池能量的節(jié)點(diǎn)n所限制。
綜上，通過最大化適應(yīng)度值，最小化延遲時(shí)間，最大化剩余電池能量，來選擇最好的路由。
4.2 編碼機(jī)制
在遺傳算法中最重要的步驟就是制定編碼策略，本文采用二進(jìn)制編碼，結(jié)合深度優(yōu)先遍歷樹的每個(gè)節(jié)點(diǎn)，每個(gè)染色體的解由一個(gè)二進(jìn)制串表示，每個(gè)染色體的長度都為圖中節(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]。可知該遺傳算法可以收斂于全局最優(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，無線直接通信的距離為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）是一種基于樹的組播路由協(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í)間變長，端到端的平均延時(shí)也逐漸增大。仿真結(jié)果如圖1所示。
新算法的延時(shí)性要優(yōu)于MAODV，因?yàn)樾滤惴ú捎昧颂綔y時(shí)間限制機(jī)制，避免了無限路由的生成，縮小了QoS優(yōu)化路由的范圍。
6 結(jié)論
本文設(shè)計(jì)了一種基于遺傳算法的QoS多播路由，通過引入探測時(shí)間限制有效減少路由節(jié)點(diǎn)和鏈路的尋找范圍，同時(shí)降低了選擇無效節(jié)點(diǎn)和鏈路的可能性。這使得在利用遺傳算法對(duì)路由問題優(yōu)化時(shí)，變?yōu)閷?duì)多播約束樹的優(yōu)化，優(yōu)化目標(biāo)是使得多播約束樹具有低延遲時(shí)間和高的剩余電池能量，采用基于樹結(jié)構(gòu)的編碼機(jī)制，編碼和解碼過程易于實(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ǎng)絡(luò)MAODV組播路由協(xié)議研究[J].計(jì)算機(jī)工程與設(shè)計(jì)，2010，31（1）：48-51.