移動(dòng)自組網(wǎng)多路徑優(yōu)化路由算法的研究

王勇智,譚用秋,石炎生

(湖南理工學(xué)院 計(jì)算機(jī)學(xué)院,湖南 岳陽 414006)

移動(dòng)自組網(wǎng)絡(luò)(Mobile Ad Hoc Network,簡稱MANET)是一種由多個(gè)可同時(shí)扮演終端和路由器的移動(dòng)節(jié)點(diǎn)組成的分布式多跳網(wǎng)絡(luò),網(wǎng)絡(luò)拓?fù)渥兓l繁,節(jié)點(diǎn)一般由電池供電,容易因?yàn)槟承┕?jié)點(diǎn)負(fù)載過重、能量迅速消耗而造成鏈路斷裂.因此,在設(shè)計(jì)MANET路由算法時(shí)要充分考慮各節(jié)點(diǎn)的負(fù)載均衡[1].近年來,多路徑路由技術(shù)已經(jīng)成為MANET的熱點(diǎn)研究問題之一[2].

AOMDV (Ad Hoc On-demand Multi-path Distance Vector)[3]是一種目前被廣為研究的按需多路徑單播路由協(xié)議.AOMDV協(xié)議的中間節(jié)點(diǎn)只轉(zhuǎn)發(fā)第一次收到的路由請(qǐng)求RREQ,限制了在全網(wǎng)范圍的路由泛洪,減少了網(wǎng)絡(luò)開銷,同時(shí)源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間擁有多條可用的完整路徑,能有效地提高網(wǎng)絡(luò)性能.然而,AOMDV的路由發(fā)現(xiàn)機(jī)制,在于選取多條跳數(shù)最少的鏈路不相交路徑,沒有考慮節(jié)點(diǎn)的流量均衡,會(huì)將流量主要分布在主路徑中,僅當(dāng)主路徑中斷時(shí),才會(huì)轉(zhuǎn)移到備用路徑,難以達(dá)到負(fù)載均衡的目的[4].在拓?fù)渥兓l繁、帶寬受限且連接中斷率高的MANET中,這種選路機(jī)制易引起局部節(jié)點(diǎn)的擁塞,造成路由信息丟失、路由請(qǐng)求頻繁、鏈路過早斷裂等問題.

基于以上的考慮,我們從負(fù)載均衡出發(fā),對(duì)AOMDV算法的路徑進(jìn)行優(yōu)化,提出一種基于帶寬和擁塞度約束的移動(dòng)自組網(wǎng)多路徑優(yōu)化路由算法,以帶寬和節(jié)點(diǎn)擁塞度作為兩個(gè)路由約束條件,在路由尋找和路由選擇上對(duì)多路徑進(jìn)行分步優(yōu)化.

1 基于帶寬和擁塞度約束的多路徑優(yōu)化路由算法

1.1 多約束QoS參數(shù)模型的建立

無線自組網(wǎng)絡(luò)的拓?fù)淇沙橄蟪蓭?quán)有向圖 G ( V,E),其中V 為節(jié)點(diǎn)集合,E 為單跳通信鏈路集合.對(duì)于一條可行路徑 p = { v1,v2,…,vn},路徑跳數(shù)為n,假設(shè)路徑p的QoS參數(shù)取路徑時(shí)延、帶寬以及鏈路的擁塞度.根據(jù)文獻(xiàn)[5]提出的QoS參數(shù)凹性特征,路徑帶寬和時(shí)延可分別定義為:

鏈路擁塞度可以定義為:

其中Fk(p)表示路徑p上優(yōu)先級(jí)為k的業(yè)務(wù)流擁塞度;C( p)表示路徑p上被占用的通道數(shù);Ek(p)表示k優(yōu)先級(jí)業(yè)務(wù)在鏈路p中所占緩存比率.

我們通過更改AOMDV的路由表項(xiàng),在緩沖區(qū)中加入不同業(yè)務(wù)的優(yōu)先級(jí)隊(duì)列(如圖1所示),在緩沖區(qū)中嚴(yán)格按照優(yōu)先級(jí)排列.

圖1 業(yè)務(wù)流在路由緩沖區(qū)中的優(yōu)先級(jí)隊(duì)列

對(duì)于新到達(dá)的k優(yōu)先級(jí)流,只能占用優(yōu)先級(jí)比其低的分組緩沖區(qū).有:

而對(duì)于可行路徑p中所有的業(yè)務(wù)優(yōu)先級(jí),則有:

引入優(yōu)先級(jí)的目的是為了保證不同類型業(yè)務(wù)流的優(yōu)先等級(jí),既能提供高等級(jí)業(yè)務(wù)的優(yōu)先服務(wù),又能使網(wǎng)絡(luò)擁塞得到緩解.

1.2 多路徑路由下的多目標(biāo)優(yōu)化建模

參照文獻(xiàn)[6]提出的路徑優(yōu)先函數(shù),綜合考慮本算法的路徑時(shí)延、帶寬以及鏈路的擁塞度約束,建立路徑優(yōu)先函數(shù):

其中Bmin為算法提供的能容忍的最小帶寬;Delaymax為路徑允許的最大時(shí)延;F( p)為鏈路的擁塞度;Congestion為擁塞度閾值;α、β、γ 分別是上述3種QoS約束的權(quán)重因子,滿足α+β+γ= 1 .

為了節(jié)省路徑計(jì)算帶來的網(wǎng)絡(luò)開銷,AOMDV一般只選擇兩條獨(dú)立無環(huán)路由來交替發(fā)送數(shù)據(jù).在建立反向路由和前向多路徑路由的基礎(chǔ)上,首先通過 AOMDV在一次路由發(fā)現(xiàn)中獲取多條獨(dú)立無環(huán)路徑,然后由算法根據(jù)多約束路由進(jìn)行路徑優(yōu)化,從中選擇兩條滿足約束條件的路徑進(jìn)行通信.多約束優(yōu)化的路徑集P的目標(biāo)函數(shù)可以定義為:

其中vsn為源節(jié)點(diǎn),sink為目標(biāo)節(jié)點(diǎn).對(duì)于任一條路徑,必須保證路徑帶寬不小于Bmin,時(shí)延不大于Delaymax,擁塞度不大于Congestion.通過多約束優(yōu)化,可以求得二條最優(yōu)路徑,使其路徑優(yōu)先級(jí)的函數(shù)值之和最大,并且路徑集相似度最小.

1.3 路由的發(fā)現(xiàn)、維護(hù)與更新

當(dāng)一個(gè)優(yōu)先級(jí)為k的業(yè)務(wù)流到達(dá)時(shí),源節(jié)點(diǎn)首先將數(shù)據(jù)包存入緩存,生成路由請(qǐng)求RREQ,RREQ中包含節(jié)點(diǎn)ID以及剩余帶寬、鏈路擁塞度等信息,RREQ被廣播到鄰居節(jié)點(diǎn),并由中間節(jié)點(diǎn)記錄多條到源節(jié)點(diǎn)的反向路由.當(dāng)目的節(jié)點(diǎn)收到RREQ包后,在其路由表中先記錄下到源節(jié)點(diǎn)的反向路由,然后由目的節(jié)點(diǎn)向源節(jié)點(diǎn)發(fā)送路由回復(fù)RREP,生成的RREP中包含有RREQ包中的完整路由信息.當(dāng)RREP包到達(dá)源節(jié)點(diǎn),源節(jié)點(diǎn)將根據(jù)路由表項(xiàng)中多徑路由列表選擇一條路由(主路由)來發(fā)送數(shù)據(jù).路徑上的各個(gè)節(jié)點(diǎn)通過發(fā)送Hello包(未被請(qǐng)求的RREP包)來維護(hù)與其相鄰節(jié)點(diǎn)間的連通,并根據(jù)生存時(shí)間和序列號(hào)來保證最新的路由信息.這樣生成的多條路徑滿足多約束優(yōu)化的路徑集目標(biāo)函數(shù),雖然不一定是跳數(shù)最少的最短路徑,但是能夠主動(dòng)避開擁塞度較大的節(jié)點(diǎn),將部分流量映射到其它負(fù)荷較輕的鏈路,有利于網(wǎng)絡(luò)資源的優(yōu)化.

當(dāng)?shù)竭_(dá)目的節(jié)點(diǎn)的主路由失效后,由目的節(jié)點(diǎn)通過反向路由單播出錯(cuò)信息包RERR給各中間節(jié)點(diǎn)和源節(jié)點(diǎn),源節(jié)點(diǎn)在發(fā)送下一分組時(shí),并不將失效的主路由刪除,而是將當(dāng)前主路徑變?yōu)閭溆寐窂?另選一條備用路徑作為主路由交替發(fā)送數(shù)據(jù).只有當(dāng)兩條路徑都失效時(shí),才發(fā)起新一輪路由請(qǐng)求重新搜索路徑.這樣,較好地繼承AOMDV的多路徑路由的優(yōu)點(diǎn),又能進(jìn)一步降低路由泛洪帶來的控制開銷,從而能在一定程度上實(shí)現(xiàn)負(fù)載均衡.

2 仿真實(shí)驗(yàn)與比較

我們?cè)贜S2下創(chuàng)建如表1所示仿真環(huán)境,從網(wǎng)絡(luò)生存期與歸一化路由開銷二個(gè)方面分別對(duì)本文算法與 AOMDV算法進(jìn)行仿真測試.仿真創(chuàng)建30個(gè)CBR數(shù)據(jù)源,每個(gè)CBR源每秒產(chǎn)生2個(gè)512B的CBR分組,仿真時(shí)間500s,仿真性能指標(biāo)的結(jié)果取5次模擬的平均值.

表1 仿真參數(shù)

2.1 網(wǎng)絡(luò)生存期測試

網(wǎng)絡(luò)生存期反映網(wǎng)絡(luò)節(jié)點(diǎn)的存活率以及鏈路的穩(wěn)定性.從圖2可以看出,改進(jìn)算法由于采取了多約束的QoS路由,能根據(jù)節(jié)點(diǎn)的擁塞程度分配流量,減少了控制和數(shù)據(jù)重傳所帶來的開銷,能緩解網(wǎng)絡(luò)擁塞,網(wǎng)絡(luò)出現(xiàn)死亡節(jié)點(diǎn)的時(shí)間明顯滯后于AOMDV,并且相同的輪次(Round)下,有更多的存活節(jié)點(diǎn).但是,隨著輪次的增大,網(wǎng)絡(luò)負(fù)載越來越重,失效的節(jié)點(diǎn)大大增多,導(dǎo)致可選路徑越來越少,備用路徑不可靠幾率變大,兩種方法的路由請(qǐng)求RREQ次數(shù)會(huì)越來越接近,相差的輪次也在逐漸減少.

圖2 不同負(fù)載下的網(wǎng)絡(luò)生存期比較

2.2 歸一化路由開銷測試

歸一化路由開銷即每發(fā)送一個(gè)數(shù)據(jù)分組所需要的用于路由發(fā)現(xiàn)和路由維護(hù)的控制分組數(shù),其值越大則意味著擁塞的概率也越高.圖 3表示了在不同節(jié)點(diǎn)速率下的歸一化路由開銷.可以看出,在節(jié)點(diǎn)速率較低(停留時(shí)間長)的情況下,改進(jìn)算法的歸一化路由開銷略低于AOMDV 算法.因?yàn)樵趥溆面溌繁容^穩(wěn)定的情況下,由于采用了能量均衡策略緩解了鏈路擁塞,并且通過改進(jìn)的主備路由切換機(jī)制能進(jìn)一步減少全網(wǎng)路由發(fā)現(xiàn)次數(shù),從而能降低路由發(fā)現(xiàn)所帶來的控制開銷.

圖3 不同速率下歸一化路由開銷的比較

3 結(jié)論

我們針對(duì) AOMDV多路徑路由協(xié)議沒考慮路徑流量平衡的不足,提出了一種基于帶寬與鏈路擁塞度約束的多路徑優(yōu)化路由策略.仿真實(shí)驗(yàn)結(jié)果表明,能在特定的移動(dòng)自組網(wǎng)絡(luò)環(huán)境中起到延長節(jié)點(diǎn)壽命、降低路由開銷的作用.

[1] 夏皓偉,王國軍,謝永明.移動(dòng)自組網(wǎng)中的分段式負(fù)載均衡路由協(xié)議[J].計(jì)算機(jī)工程,2010,36(4):93～96

[2] 安輝耀,盧錫城.移動(dòng)自主網(wǎng)絡(luò)多路徑路由技術(shù)研究進(jìn)展[J].計(jì)算機(jī)工程與科學(xué),2006,28(2):4～9

[3] Yuan Yuhua,Chen Huimin,Jia Min.An optimized Ad hoc on-demand multipath distance vector (AOMDV)routing protocol[C].Asia-Pacific Conference on Communications,2005:569～573

[4] 胡 平,張金鐘.基于能量均衡的AOMDV路由協(xié)議的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì),2011,32(9):2976～2979

[5] Wang Z,Crowcroft J.Quality-of-Service routing for supporting multimedia applications [J].IEEE Journal on Selected Areas in Communications,1996,14(7):1228～1234

[6] 曹 嘯,王汝傳,黃海平,等.無線多媒體傳感器網(wǎng)絡(luò)視頻流多路徑路由算法[J].軟件學(xué)報(bào),2012,23(1):108～121