摘 要: 深入研究移動(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à)于:
證明:
?。?)根據(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。
?。?)根據(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)的要求。
?。?)根據(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.