張岱臣　張　紅

(國(guó)防信息學(xué)院作戰(zhàn)訓(xùn)練教研室　武漢　430314)

?

MANET中基于鄰居度的動(dòng)態(tài)廣播抑制算法

張岱臣張紅

(國(guó)防信息學(xué)院作戰(zhàn)訓(xùn)練教研室武漢430314)

廣播是移動(dòng)自組織網(wǎng)絡(luò)最重要的應(yīng)用之一,按需路由協(xié)議一般通過(guò)廣播建立路由。傳統(tǒng)的按需路由協(xié)議中,廣播存在沖突和冗余較多的問(wèn)題。提出一種基于節(jié)點(diǎn)鄰居度的動(dòng)態(tài)廣播抑制算法DBB(Density Based Broadcast),節(jié)點(diǎn)利用鄰居度產(chǎn)生廣播轉(zhuǎn)發(fā)的時(shí)延和概率,并根據(jù)重復(fù)廣播數(shù)動(dòng)態(tài)調(diào)整;用延長(zhǎng)緩存的方法解決網(wǎng)絡(luò)分裂的問(wèn)題。結(jié)合經(jīng)典的AODV(Ad hoc on Demand Distance Vector)路由協(xié)議,設(shè)計(jì)了AODV-DBB協(xié)議。仿真結(jié)果表明,AODV-DBB協(xié)議中的廣播沖突和冗余遠(yuǎn)低于其他協(xié)議,DBB算法能有效減少?gòu)V播對(duì)信道資源的占用。

移動(dòng)自組織網(wǎng)絡(luò); 廣播; 路由協(xié)議; 時(shí)延; 概率; 網(wǎng)絡(luò)分裂

Class NumberTP915

1　引言

移動(dòng)自組織網(wǎng)絡(luò)(mobile ad hoc network,MANET)具有無(wú)線廣播信道、帶寬受限、能量有限、多跳網(wǎng)絡(luò)等特點(diǎn),使路由協(xié)議的設(shè)計(jì)面臨很大挑戰(zhàn),尤其要求路由協(xié)議高效可靠。廣播是路由協(xié)議建立和更新路由的基本途徑,按需路由協(xié)議通過(guò)廣播尋找路由,主動(dòng)式路由協(xié)議通過(guò)廣播維護(hù)路由。

目前,大部分路由協(xié)議采用洪泛式廣播,但洪泛式廣播算法中節(jié)點(diǎn)盲目轉(zhuǎn)發(fā)廣播,網(wǎng)絡(luò)中存在大量的重復(fù)數(shù)據(jù),廣播冗余度很高;而且相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播的時(shí)間高度相關(guān),極易發(fā)生廣播沖突。沖突不但浪費(fèi)信道資源,也降低了廣播的可靠性,即使在一個(gè)全連通的網(wǎng)絡(luò)中,也可能由于沖突而使有些節(jié)點(diǎn)收不到廣播。廣播引起的冗余高和沖突多等問(wèn)題統(tǒng)稱為“廣播風(fēng)暴”[1～2]。“廣播風(fēng)暴”在節(jié)點(diǎn)密度較高的網(wǎng)絡(luò)中尤其嚴(yán)重,由于轉(zhuǎn)發(fā)的廣播較多,網(wǎng)絡(luò)中存在大量冗余和沖突,嚴(yán)重影響網(wǎng)絡(luò)性能[3]。

優(yōu)化廣播算法,減少?gòu)V播冗余,降低沖突,能節(jié)省寶貴的信道資源和終端能量,對(duì)于提高路由協(xié)議的效率,延長(zhǎng)網(wǎng)絡(luò)生命周期具有重要意義。本文提出一種基于鄰居度的動(dòng)態(tài)廣播抑制算法DBB(Density Based Broadcast),節(jié)點(diǎn)根據(jù)鄰居度來(lái)動(dòng)態(tài)調(diào)整廣播轉(zhuǎn)發(fā)的時(shí)延和概率,并針對(duì)稀疏網(wǎng)絡(luò)設(shè)計(jì)了廣播緩存期延長(zhǎng)策略,以解決網(wǎng)絡(luò)分裂導(dǎo)致的廣播失敗問(wèn)題。

2　相關(guān)工作

廣播最簡(jiǎn)單的實(shí)現(xiàn)方式是“洪泛”,其缺點(diǎn)是廣播冗余大沖突多。目前,廣播算法主要從降低冗余和減少?zèng)_突兩方面進(jìn)行優(yōu)化。主要有基于概率的算法,基于鄰居信息的算法,基于計(jì)數(shù)器的算法等。

文獻(xiàn)[4]提出一種變概率算法SPS(Smart Probabilistic Scheme),其把節(jié)點(diǎn)的密度分成四個(gè)等級(jí),每個(gè)密度等級(jí)對(duì)應(yīng)一個(gè)轉(zhuǎn)發(fā)概率,密度越大轉(zhuǎn)發(fā)的概率越小。該算法需要手工設(shè)置密度和對(duì)應(yīng)的概率,設(shè)置參數(shù)不當(dāng)將對(duì)算法產(chǎn)生致命影響,而且算法需要發(fā)送HELLO消息也占用了一定的信道資源。

文獻(xiàn)[5]提出一種基于鄰居信息的算法。算法在節(jié)點(diǎn)之間交互一跳鄰居信息,然后節(jié)點(diǎn)根據(jù)鄰居信息和轉(zhuǎn)發(fā)RREQ所能額外覆蓋的節(jié)點(diǎn)數(shù)來(lái)設(shè)置轉(zhuǎn)發(fā)概率,額外覆蓋的節(jié)點(diǎn)數(shù)越多轉(zhuǎn)發(fā)的概率越大。當(dāng)網(wǎng)絡(luò)拓?fù)渥兓l繁時(shí),其計(jì)算的額外覆蓋節(jié)點(diǎn)不準(zhǔn)確,影響算法的性能,而且傳播的鄰居信息也帶來(lái)了額外開銷,該算法不適合動(dòng)態(tài)性較大的網(wǎng)絡(luò)。

文獻(xiàn)[6]提出基于計(jì)數(shù)器策略的HPC(Hybrid Probabilistic Counter)算法,HPC算法通過(guò)一個(gè)函數(shù)計(jì)算廣播轉(zhuǎn)發(fā)的概率,并且通過(guò)收到的重復(fù)廣播數(shù)動(dòng)態(tài)調(diào)整概率。但算法中采用的隨機(jī)延遲技術(shù)在廣播增加時(shí)仍然會(huì)產(chǎn)生較多沖突,影響算法的性能。文獻(xiàn)[7]提出另一種基于計(jì)數(shù)器的策略,但是該算法需要維護(hù)節(jié)點(diǎn)之間的鄰居列表,增加了額外開銷,也增加了能量消耗。

文獻(xiàn)[8～9]提出減少?zèng)_突的廣播算法,但算法中使用了固定的參數(shù),對(duì)網(wǎng)絡(luò)的適應(yīng)性不好,當(dāng)網(wǎng)絡(luò)密度較大時(shí),算法性能下降[10]。文獻(xiàn)[11]提出一種應(yīng)用動(dòng)態(tài)能量管理的廣播算法,延長(zhǎng)網(wǎng)絡(luò)生命周期,該算法不適用于拓?fù)鋭?dòng)態(tài)變化的移動(dòng)自組織網(wǎng)絡(luò)。文獻(xiàn)[12]提出一種混合式的廣播算法,算法結(jié)合了幾種廣播策略來(lái)解決廣播風(fēng)暴問(wèn)題,該算法的實(shí)質(zhì)還是基于節(jié)點(diǎn)密度的策略。

各廣播算法各有特點(diǎn),從是否需要保存網(wǎng)絡(luò)狀態(tài)的角度可分為兩類,一類是基于狀態(tài)信息的廣播,另一類是非基于狀態(tài)信息的?；跔顟B(tài)信息的廣播算法需要在節(jié)點(diǎn)之間傳遞信息,比如基于鄰居信息的算法,其需要在節(jié)點(diǎn)之間傳遞一跳鄰居信息;非基于狀態(tài)信息的算法是完全分布式操作,節(jié)點(diǎn)之間不需要傳遞任何信息,比如基于概率的算法。

基于狀態(tài)信息的算法中,節(jié)點(diǎn)根據(jù)局部的網(wǎng)絡(luò)狀態(tài)對(duì)廣播轉(zhuǎn)發(fā)的計(jì)算相對(duì)精確,所以受網(wǎng)絡(luò)流量和數(shù)據(jù)沖突的影響較小[13]。但是,節(jié)點(diǎn)交互的鄰居信息帶來(lái)額外開銷;另外,算法依賴網(wǎng)絡(luò)拓?fù)?當(dāng)網(wǎng)絡(luò)拓?fù)渥兓l繁時(shí)會(huì)產(chǎn)生較多的控制信息,甚至當(dāng)網(wǎng)絡(luò)變化很快的時(shí)候算法無(wú)法收斂。網(wǎng)絡(luò)拓?fù)涞淖兓粌H由節(jié)點(diǎn)移動(dòng)引起,節(jié)能機(jī)制使節(jié)點(diǎn)休眠也將導(dǎo)致網(wǎng)絡(luò)拓?fù)浒l(fā)生變化,所以基于狀態(tài)的廣播算法不適合應(yīng)用在傳感器網(wǎng)絡(luò)和車輛網(wǎng)絡(luò)中。

非基于狀態(tài)的廣播算法中,節(jié)點(diǎn)完全分布式操作,不需要交互任何信息,例如基于概率和基于位置信息的算法,這些算法受網(wǎng)絡(luò)拓?fù)渥兓挠绊懞苄?。但是非基于狀態(tài)的廣播算法在節(jié)點(diǎn)密度高的網(wǎng)絡(luò)中廣播冗余較大[14]。

結(jié)合現(xiàn)有算法,文章提出基于鄰居度的動(dòng)態(tài)概率廣播抑制算法——DBB。DBB是一種非基于狀態(tài)信息的廣播算法,該算法利用節(jié)點(diǎn)密度調(diào)節(jié)廣播轉(zhuǎn)發(fā)的概率和時(shí)延,解決傳統(tǒng)概率算法在高密度網(wǎng)絡(luò)中廣播冗余高、性能下降的問(wèn)題,針對(duì)稀疏網(wǎng)絡(luò)設(shè)計(jì)的緩存策略解決網(wǎng)絡(luò)分裂問(wèn)題。DBB算法可以應(yīng)用在各種節(jié)點(diǎn)密度的網(wǎng)絡(luò)環(huán)境中。DBB是一種完全分布式的算法,不需要在節(jié)點(diǎn)間交互任何信息,也不需要改變路由協(xié)議的數(shù)據(jù)格式,和路由協(xié)議的松散耦合使算法應(yīng)用靈活,具有很強(qiáng)的適用性。

3　算法及協(xié)議

AODV(Ad hoc on Demand Distance Vector)是MANET中經(jīng)典的按需路由協(xié)議,協(xié)議通過(guò)廣播建立路由。AODV缺少對(duì)廣播的有效控制,存在廣播冗余和沖突,影響了協(xié)議的性能。把DBB算法應(yīng)用在AODV的路由尋找階段,減少?gòu)V播冗余和沖突。

本節(jié)先介紹DBB算法,然后設(shè)計(jì)AODV-DBB協(xié)議。

3.1時(shí)延和概率初始化

廣播冗余和沖突與局部范圍內(nèi)的節(jié)點(diǎn)密度有較大關(guān)系。在節(jié)點(diǎn)發(fā)送半徑不變的情況下,節(jié)點(diǎn)密度越大,一次廣播所覆蓋的節(jié)點(diǎn)越多,相應(yīng)轉(zhuǎn)發(fā)廣播的節(jié)點(diǎn)就越多,廣播冗余和沖突也越多。可見(jiàn),局部范圍內(nèi)節(jié)點(diǎn)的密度對(duì)廣播冗余和沖突影響很大。DBB算法用節(jié)點(diǎn)密度調(diào)節(jié)轉(zhuǎn)發(fā)廣播的概率和時(shí)延,通過(guò)概率和時(shí)延機(jī)制來(lái)減少冗余,降低沖突。

節(jié)點(diǎn)在收到廣播之后并不立即轉(zhuǎn)發(fā),而是根據(jù)感知到的鄰居數(shù)初始化一個(gè)隨機(jī)時(shí)延定時(shí)器,此定時(shí)器到期之后再?zèng)Q定是否轉(zhuǎn)發(fā)。為了使節(jié)點(diǎn)在轉(zhuǎn)發(fā)廣播的時(shí)間上相互避開,定時(shí)器的時(shí)間和節(jié)點(diǎn)感知到的鄰居數(shù)正比,節(jié)點(diǎn)的鄰居數(shù)越多,那么局部范圍內(nèi)轉(zhuǎn)發(fā)廣播的節(jié)點(diǎn)就越多,沖突的概率就越大,時(shí)延定時(shí)器應(yīng)該設(shè)置越長(zhǎng)。

時(shí)延的初始化如式(1)所示:

(1)

式(1)設(shè)計(jì)了時(shí)延和節(jié)點(diǎn)密度的指數(shù)關(guān)系,使時(shí)延隨網(wǎng)絡(luò)密度平緩變化。其中,Ti是節(jié)點(diǎn)i的時(shí)延定時(shí)器,DL是節(jié)點(diǎn)i的一跳鄰居數(shù),DG是網(wǎng)絡(luò)中節(jié)點(diǎn)一跳鄰居數(shù)的最大值,t是區(qū)間[0,10-3]內(nèi)的一個(gè)隨機(jī)數(shù),用來(lái)調(diào)節(jié)定時(shí)器的時(shí)間在一個(gè)合適的數(shù)量級(jí)。

由式(1)可見(jiàn),節(jié)點(diǎn)的一跳鄰居越多,廣播的時(shí)延越長(zhǎng),在較長(zhǎng)的時(shí)間內(nèi)分開各節(jié)點(diǎn)轉(zhuǎn)發(fā)的廣播,從而避免碰撞。式中DL和DG是參數(shù),節(jié)點(diǎn)可通過(guò)探測(cè)和感知獲得參數(shù)DL的數(shù)值。而DG是一個(gè)實(shí)驗(yàn)數(shù)值,在具體的網(wǎng)絡(luò)環(huán)境中可通過(guò)實(shí)驗(yàn)的方法獲得。

為此,對(duì)幾個(gè)具體網(wǎng)絡(luò)的場(chǎng)景進(jìn)行仿真,獲得的參數(shù)值和相應(yīng)的計(jì)算結(jié)果如表1所示。在一定的區(qū)域內(nèi)分布的節(jié)點(diǎn),節(jié)點(diǎn)感知到的鄰居數(shù)為DL,網(wǎng)絡(luò)中的最大一跳鄰居數(shù)為DG,由式(1)計(jì)算得到時(shí)延為Ti,轉(zhuǎn)發(fā)的概率為Pi,概率計(jì)算如式(2)所示。例如,當(dāng)50個(gè)節(jié)點(diǎn)分布在500*500的區(qū)域內(nèi),節(jié)點(diǎn)的一跳鄰居數(shù)DL為6,而網(wǎng)絡(luò)中最大的密度值DG是8,由此計(jì)算得到節(jié)點(diǎn)的時(shí)延Ti為52*10-5s。

表1　不同環(huán)境下的網(wǎng)絡(luò)參數(shù)值

DBB算法利用概率減少?gòu)V播冗余。節(jié)點(diǎn)在轉(zhuǎn)發(fā)廣播之前,根據(jù)鄰居數(shù)來(lái)初始化一個(gè)概率,各節(jié)點(diǎn)根據(jù)此概率來(lái)決定是否轉(zhuǎn)發(fā)廣播,從而降低廣播冗余。概率初始化如式(2)所示:

(2)

式(2)設(shè)計(jì)了節(jié)點(diǎn)密度和轉(zhuǎn)發(fā)概率的指數(shù)函數(shù)關(guān)系,使概率隨接單密度值緩慢變化。其中Pi是節(jié)點(diǎn)i的轉(zhuǎn)發(fā)概率,DL和DG如前文所述?？梢?jiàn),廣播轉(zhuǎn)發(fā)的概率反比于節(jié)點(diǎn)的鄰居數(shù),節(jié)點(diǎn)的一跳鄰居越多,節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率越小,一跳鄰居越少,轉(zhuǎn)發(fā)概率越大。

3.2定時(shí)器和概率的更新

節(jié)點(diǎn)初始化得到的轉(zhuǎn)發(fā)時(shí)延和概率只與節(jié)點(diǎn)的鄰居數(shù)有關(guān)。而在等待時(shí)延定時(shí)器的過(guò)程中,節(jié)點(diǎn)應(yīng)該根據(jù)廣播轉(zhuǎn)發(fā)情況動(dòng)態(tài)地調(diào)整時(shí)延和概率。

在等待定時(shí)器的過(guò)程中,節(jié)點(diǎn)監(jiān)聽(tīng)其他節(jié)點(diǎn)的廣播轉(zhuǎn)發(fā)情況,如果其他節(jié)點(diǎn)已經(jīng)轉(zhuǎn)發(fā)了這個(gè)廣播,為降低冗余,節(jié)點(diǎn)應(yīng)該降低轉(zhuǎn)發(fā)的概率,并延長(zhǎng)等待時(shí)延。如果很多個(gè)節(jié)點(diǎn)都已經(jīng)轉(zhuǎn)發(fā)了同一廣播數(shù)據(jù),那么節(jié)點(diǎn)可以考慮拋棄此廣播。

節(jié)點(diǎn)要根據(jù)網(wǎng)絡(luò)中其他節(jié)點(diǎn)的廣播情況動(dòng)態(tài)更新自己的概率和時(shí)延。時(shí)延定時(shí)器更新如式(3)所示:

Tk+1=Tk×NR

(3)

其中Tk+1是計(jì)時(shí)器的下一個(gè)等待時(shí)間,NR是節(jié)點(diǎn)在上一個(gè)等待時(shí)間Tk內(nèi)收到的重復(fù)RREQ總數(shù)?？梢?jiàn),定時(shí)器的更新時(shí)間和節(jié)點(diǎn)收到的重復(fù)RREQ數(shù)有關(guān),收到的重復(fù)包數(shù)越多則等待時(shí)間越長(zhǎng)。

在節(jié)點(diǎn)密度較大的網(wǎng)絡(luò)中,發(fā)送的廣播包數(shù)可能較多,為防止出現(xiàn)定時(shí)器無(wú)限等待,設(shè)置兩個(gè)參數(shù),一個(gè)是超時(shí)計(jì)數(shù)器(Timer Counter,TC),另一個(gè)是超時(shí)次數(shù)門限(Waiting Threshold,Wth)。超時(shí)計(jì)數(shù)器TC用來(lái)計(jì)量節(jié)點(diǎn)達(dá)到定時(shí)器的次數(shù),超時(shí)次數(shù)門限Wth用來(lái)對(duì)超時(shí)計(jì)數(shù)器進(jìn)行限制,是超時(shí)計(jì)數(shù)器的最大值。當(dāng)定時(shí)器多次超時(shí)到期,即超時(shí)計(jì)數(shù)器達(dá)到超時(shí)次數(shù)門限時(shí),節(jié)點(diǎn)將取消定時(shí)器,并拋棄廣播包。其中Wth是一個(gè)手工預(yù)設(shè)的參數(shù),其需要依據(jù)網(wǎng)絡(luò)密度來(lái)進(jìn)行設(shè)置,在密度較大的網(wǎng)絡(luò)中,Wth應(yīng)設(shè)置為較高,在密度較小的網(wǎng)絡(luò)中應(yīng)設(shè)置為較低。

轉(zhuǎn)發(fā)概率的更新如式(4)所示:

(4)

Pk+1是更新后的轉(zhuǎn)發(fā)概率,Pk是更新前的轉(zhuǎn)發(fā)概率,NR是節(jié)點(diǎn)在上一個(gè)定時(shí)器時(shí)間內(nèi)收到的重復(fù)包數(shù)?？梢?jiàn),節(jié)點(diǎn)收到的重復(fù)包數(shù)越多其轉(zhuǎn)發(fā)變得概率越小。已被轉(zhuǎn)發(fā)的廣播越多,后邊節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播的概率越小,減少了重復(fù)的廣播數(shù)。

3.3稀疏網(wǎng)絡(luò)的優(yōu)化

在節(jié)點(diǎn)密度較低的稀疏網(wǎng)絡(luò)中,由于節(jié)點(diǎn)的移動(dòng)很容易出現(xiàn)網(wǎng)絡(luò)暫時(shí)分裂的情況,此時(shí)網(wǎng)絡(luò)不能全聯(lián)通,傳統(tǒng)的廣播算法將失敗。

如圖1所示,節(jié)點(diǎn)S發(fā)起向D的路由,但是由于網(wǎng)絡(luò)在節(jié)點(diǎn)1和節(jié)點(diǎn)2處發(fā)生分裂,節(jié)點(diǎn)1沒(méi)有中繼節(jié)點(diǎn),廣播將失敗。廣播失敗尤其對(duì)按需路由協(xié)議影響更大,將使尋路失敗,從而引起新的尋路廣播,浪費(fèi)了信道資源。

圖1　網(wǎng)絡(luò)分裂

DBB算法針對(duì)稀疏網(wǎng)絡(luò)設(shè)計(jì)了廣播延長(zhǎng)緩存策略。如果節(jié)點(diǎn)1只有一個(gè)鄰居節(jié)點(diǎn),而且這個(gè)節(jié)點(diǎn)又是廣播的發(fā)送節(jié)點(diǎn),這說(shuō)明節(jié)點(diǎn)1沒(méi)有中繼節(jié)點(diǎn)。此時(shí),那么節(jié)點(diǎn)1將RREQ在緩存中延長(zhǎng)一個(gè)等待時(shí)間,以防止RREQ過(guò)期。如果在等待的時(shí)間內(nèi)節(jié)點(diǎn)1有了其他鄰居作為中繼,則節(jié)點(diǎn)以百分之百的概率轉(zhuǎn)發(fā)此RREQ;否則丟棄此廣播。

緩存延長(zhǎng)的時(shí)間可根據(jù)節(jié)點(diǎn)的移動(dòng)速度進(jìn)行設(shè)置。節(jié)點(diǎn)的移動(dòng)速度越快,說(shuō)明網(wǎng)絡(luò)拓?fù)浜芸?那么網(wǎng)絡(luò)分裂愈合的速度就越快,那么緩存延長(zhǎng)的時(shí)間就越短,否則可延長(zhǎng)緩存時(shí)間。

3.4AODV-DBB協(xié)議

AODV-DBB在AODV的基礎(chǔ)上添加了DBB廣播算法,算法主要對(duì)AODV中的尋路廣播進(jìn)行優(yōu)化。運(yùn)行AODV-DBB協(xié)議的節(jié)點(diǎn),收到其他節(jié)點(diǎn)廣播的路由請(qǐng)求后,如果沒(méi)有到目的節(jié)點(diǎn)的路由,根據(jù)DBB算法得到初始化的時(shí)延和概率,并且根據(jù)時(shí)延定時(shí)器期間收到的廣播數(shù)動(dòng)態(tài)調(diào)整。

如圖2所示的網(wǎng)絡(luò)拓?fù)?網(wǎng)絡(luò)中節(jié)點(diǎn)運(yùn)行AODV-DBB協(xié)議,節(jié)點(diǎn)S尋找到目的節(jié)點(diǎn)D的路由,它廣播RREQ,其一跳鄰居節(jié)點(diǎn)1、2、3、4和R1都第一次收到此RREQ包,然后它們開始運(yùn)行DBB算法。首先各節(jié)點(diǎn)初始化定時(shí)器,得到一個(gè)隨機(jī)轉(zhuǎn)發(fā)的時(shí)延Tk。假如節(jié)點(diǎn)R1的定時(shí)器最先到期,這時(shí)節(jié)點(diǎn)R1根據(jù)初始化的概率Pi轉(zhuǎn)發(fā)此廣播包。節(jié)點(diǎn)2和節(jié)點(diǎn)4收到R1轉(zhuǎn)發(fā)的重復(fù)RREQ,而節(jié)點(diǎn)5、6和節(jié)點(diǎn)R2第一次收到此RREQ。節(jié)點(diǎn)2和節(jié)點(diǎn)4再次執(zhí)行DBB算法更新定時(shí)器和轉(zhuǎn)發(fā)概率,定時(shí)器將延長(zhǎng),概率將減小。節(jié)點(diǎn)5、6和節(jié)點(diǎn)R2第一次收到R1轉(zhuǎn)發(fā)的RREQ,初始化定時(shí)器和轉(zhuǎn)發(fā)概率。同樣假如節(jié)點(diǎn)R2的定時(shí)器先到期,其將以初始化的概率轉(zhuǎn)發(fā)廣播。最后,網(wǎng)絡(luò)運(yùn)行DBB算法形成源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由為S→R1→R2→D。

圖2　DBB算法廣播轉(zhuǎn)發(fā)

網(wǎng)絡(luò)中的節(jié)點(diǎn)2、4、5和6都收到了重復(fù)的廣播,這些節(jié)點(diǎn)根據(jù)DBB的更新算法延長(zhǎng)定時(shí)器并降低轉(zhuǎn)發(fā)的概率,從而減少重復(fù)的廣播數(shù),降低廣播冗余。

4　仿真分析

文獻(xiàn)[6]中的HPC算法在目前廣播算法中比較有代表性,本節(jié)在Qualnet仿真平臺(tái)上分別實(shí)現(xiàn)HPC算法和DBB算法,對(duì)兩個(gè)算法的性能進(jìn)行比較和驗(yàn)證。鑒于AODV路由協(xié)議應(yīng)用和研究的廣泛性,我們?cè)贏ODV的基礎(chǔ)上,分別驗(yàn)證DBB算法和HPC算法的性能。

算法的性能主要通過(guò)以下兩個(gè)指標(biāo)反映:廣播沖突數(shù)和廣播重播數(shù)。AODV中的廣播數(shù)據(jù)主要是路由建立階段的RREQ,所以這里考察RREQ的沖突數(shù)和RREQ的傳播數(shù)。

RREQ沖突數(shù):表示網(wǎng)絡(luò)中由于碰撞而發(fā)送失敗的廣播數(shù)。該指標(biāo)驗(yàn)證DBB算法中的時(shí)延機(jī)制,好的廣播算法應(yīng)該能夠通過(guò)隨機(jī)時(shí)延來(lái)避免碰撞,提高廣播的成功率。該指標(biāo)越低越好。

RREQ傳播數(shù):表示網(wǎng)絡(luò)中節(jié)點(diǎn)廣播的所有廣播。該指標(biāo)可以驗(yàn)證DBB中概率算法,好的廣播算法應(yīng)能在保證覆蓋率的前提下減少?gòu)V播的傳播數(shù),降低廣播冗余度。該指標(biāo)越低越好。

為公平比較DBB算法和HPC算法的性能,仿真環(huán)境的設(shè)置基本與文獻(xiàn)[6]保持一致,DBB算法的Wth參數(shù)設(shè)置為3。其他設(shè)置如表2所示。

設(shè)置兩個(gè)場(chǎng)景對(duì)協(xié)議進(jìn)行仿真:

場(chǎng)景一:不同節(jié)點(diǎn)密度下的協(xié)議仿真,考察協(xié)議在不同節(jié)點(diǎn)密度下的性能。本場(chǎng)景中,在1000*1000m2的范圍內(nèi),節(jié)點(diǎn)數(shù)從30個(gè)增加到200個(gè)。應(yīng)用層設(shè)置20對(duì)CBR流,流量為每秒8個(gè)數(shù)據(jù)包。每個(gè)數(shù)據(jù)點(diǎn)仿真20次取平均值,廣播沖突結(jié)果如圖3所示,廣播傳播結(jié)果如圖4所示。

表2　仿真參數(shù)配置

圖3　不同密度下RREQ廣播沖突數(shù)

圖4　不同密度下RREQ廣播數(shù)

圖3是不同節(jié)點(diǎn)密度下的RREQ沖突對(duì)比圖,橫坐標(biāo)是網(wǎng)絡(luò)中的幾點(diǎn)數(shù),縱坐標(biāo)是RREQ廣播的沖突數(shù)。當(dāng)點(diǎn)數(shù)增多時(shí),三個(gè)協(xié)議的RREQ廣播沖突數(shù)都增加,但DBB最低,HPC稍好于AODV。隨著節(jié)點(diǎn)數(shù)增多,在節(jié)點(diǎn)的發(fā)送半徑不變的情況下,一次廣播所能覆蓋的節(jié)點(diǎn)增多,被轉(zhuǎn)發(fā)的廣播數(shù)增多。AODV由于缺少有效的沖突避免機(jī)制,沖突數(shù)最多;HPC的計(jì)數(shù)器和時(shí)延策略降低了沖突,其沖突數(shù)要少于AODV,DBB的廣播沖突數(shù)最少。DBB算法的時(shí)延策略考慮了節(jié)點(diǎn)密度帶來(lái)的影響,能使相鄰節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播的時(shí)間避開,有效減少?gòu)V播的沖突數(shù)量。即使在節(jié)點(diǎn)密度很高時(shí),其依然能有效避免廣播沖突。在節(jié)點(diǎn)密度較高時(shí),AODV-DBB比AODV減少了約35%的廣播沖突,比AODV-HPC減少了約20%。

圖4是不同節(jié)點(diǎn)密度下網(wǎng)絡(luò)中發(fā)送的RREQ對(duì)比圖,橫坐標(biāo)是節(jié)點(diǎn)數(shù),縱坐標(biāo)是RREQ傳播數(shù)。隨著節(jié)點(diǎn)密度的增大,不同協(xié)議下的RREQ廣播數(shù)都增多。在節(jié)點(diǎn)數(shù)較少時(shí),三個(gè)協(xié)議的RREQ傳播數(shù)相差不大,DBB發(fā)送的廣播最少,HPC稍好,AODV發(fā)送的廣播最多。當(dāng)節(jié)點(diǎn)數(shù)較多時(shí),三個(gè)協(xié)議發(fā)送的廣播數(shù)差異顯著。AODV由于沒(méi)有廣播控制,其網(wǎng)絡(luò)中發(fā)送的廣播數(shù)最多;AODV-HPC的計(jì)數(shù)器策略一定程度上降低了廣播冗余,其發(fā)送的廣播數(shù)比AODV稍好,但當(dāng)網(wǎng)絡(luò)密度較高時(shí),其發(fā)送的廣播數(shù)依然很多;AODV-DBB根據(jù)節(jié)點(diǎn)密度變化調(diào)整廣播發(fā)送的概率并動(dòng)態(tài)調(diào)整,大幅減少了重復(fù)發(fā)送的廣播數(shù)。其發(fā)送的廣播數(shù)最多時(shí)比AODV和AODV-HPC分別少50%和30%。

場(chǎng)景二:不同網(wǎng)絡(luò)負(fù)載下的協(xié)議仿真,考察協(xié)議在不同網(wǎng)絡(luò)負(fù)載下的性能。通過(guò)改變應(yīng)用層CBR流的連接數(shù)來(lái)調(diào)整網(wǎng)絡(luò)負(fù)載,CBR連接數(shù)從1變化到40,CBR的源節(jié)點(diǎn)和目的節(jié)點(diǎn)隨機(jī)選擇。這里選擇較大節(jié)點(diǎn)密度的網(wǎng)絡(luò)環(huán)境,節(jié)點(diǎn)數(shù)設(shè)置為150。節(jié)點(diǎn)移動(dòng)速度為20m/s,使網(wǎng)絡(luò)拓?fù)渥兓鄬?duì)頻繁。其他參數(shù)設(shè)置不變。仿真結(jié)果如圖5和圖6所示:

圖5　不同連接數(shù)下的廣播沖突數(shù)

圖6　不同連接數(shù)下的廣播發(fā)送數(shù)

圖5是不同負(fù)載下的廣播沖突對(duì)比圖。隨著連接數(shù)的增多,網(wǎng)絡(luò)負(fù)載加大,各協(xié)議的廣播沖突數(shù)都增多,但是DBB算法其沖突數(shù)始終最少,尤其在網(wǎng)絡(luò)負(fù)載較大時(shí)沖突數(shù)顯著少于其他算法,其沖突數(shù)最多較HPC算法減少18%。

隨著網(wǎng)絡(luò)流量增大和網(wǎng)絡(luò)拓?fù)渥兓?路由協(xié)議的尋路廣播顯著增多。DBB算法中,當(dāng)節(jié)點(diǎn)在定時(shí)器期間收到重復(fù)廣播數(shù)時(shí),會(huì)根據(jù)算法動(dòng)態(tài)調(diào)整廣播的時(shí)延,尤其當(dāng)廣播增多時(shí),節(jié)點(diǎn)會(huì)延長(zhǎng)定時(shí)器的時(shí)間,有效避開了相鄰節(jié)點(diǎn)間轉(zhuǎn)發(fā)廣播的時(shí)間,降低了沖突。當(dāng)節(jié)點(diǎn)收到的重復(fù)廣播數(shù)過(guò)多,定時(shí)器超時(shí)達(dá)到門限值,節(jié)點(diǎn)將拋棄此廣播,減少了廣播沖突數(shù)。

圖6是在不同負(fù)載下網(wǎng)絡(luò)中發(fā)送的廣播數(shù),可以看到,不同協(xié)議下的RREQ廣播數(shù)都隨著負(fù)載的增大而增多。當(dāng)負(fù)載增大時(shí),由網(wǎng)絡(luò)拓?fù)渥兓鸬膶ぢ窂V播顯著增多,但AODV-DBB協(xié)議的廣播冗余度都低于AODV-HPC和AODV。

在當(dāng)前網(wǎng)絡(luò)節(jié)點(diǎn)密度較高的情況下,DBB算法根據(jù)網(wǎng)絡(luò)節(jié)點(diǎn)密度調(diào)整轉(zhuǎn)發(fā)的概率,對(duì)降低廣播冗余效果顯著;另外,當(dāng)廣播增多時(shí),其根據(jù)廣播數(shù)動(dòng)態(tài)調(diào)整轉(zhuǎn)發(fā)概率降低了冗余度,始終把廣播數(shù)控制在較低值。最優(yōu)時(shí)DBB的廣播冗余度比AODV和HPC分別低約35%和20%。

5　結(jié)語(yǔ)

廣播算法的研究對(duì)改善路由協(xié)議的性能具有重要意義。本文提出一種新的基于鄰居度的廣播抑制算法——DBB算法。該算法利用鄰居度來(lái)初始化廣播轉(zhuǎn)發(fā)的時(shí)延和概率,并根據(jù)收到的重復(fù)廣播數(shù)動(dòng)態(tài)更新,避免沖突和減少冗余。在Qualnet仿真平臺(tái)上對(duì)算法進(jìn)行仿真,仿真結(jié)果表明,基于DBB算法的AODV-DBB協(xié)議,其廣播沖突和冗余度都顯著低于其他協(xié)議,在網(wǎng)絡(luò)密度較大和負(fù)載較高時(shí)優(yōu)勢(shì)尤其明顯。結(jié)合針對(duì)稀疏網(wǎng)絡(luò)設(shè)計(jì)的廣播緩存策略使協(xié)議適用于各種節(jié)點(diǎn)密度的網(wǎng)絡(luò)環(huán)境。

DBB算法完全分布式運(yùn)算,沒(méi)有占用額外的信道資源,沒(méi)有對(duì)路由協(xié)議的數(shù)據(jù)格式進(jìn)行修改,與路由協(xié)議的松散耦合使協(xié)議的應(yīng)用更加靈活,算法具有較強(qiáng)的適用性

下一步期望建立理論模型,在理論上對(duì)分布式廣播算法進(jìn)行建模研究,為仿真研究提供理論支撐。

[1] M. Meshbahi, M. Egerstedt. Graph Theoretic Methods for Multiagent Networks[M]. Princeton: Princeton University Press,2010.

[2] P. Ruiz, P. Bouvry. Enhanced distance based broadcasting protocol with reduced energy consumption[C]//International Conference on High Performance Computing and Simulation(HPCS),2010:249-25828.

[3] P. Y. Taifei Zhao, Xizheng Ke, Position and velocity aided routing protocol in mobile ad-hoc networks[J]. International Journal of Digital Content Technology and its application,2010,4:101-109.

[4] M. Bani Yassein, M. Bani Khalaf, A. Al-Dubai. A new probabilistic broadcasting scheme for mobile ad hoc on demand distance vector(aodv) routed networks[J]. The Journal of Supercomputing,2010,53:196-211.

[5] J.-D. Abdulai, M. Ould-Khaoua, L. Mackenzie, et al. Neighbour coverage: A dynamic probabilistic route discovery for mobile ad hoc networks[C]//International Symposium on Performance Evaluation of Computer and Telecommunication Systems(SPECTS),2008:165-172.

[6] A. Mohammed, M. Ould-Khaoua, L. Mackenzie. An Efficient Counter-Based Broadcast Scheme for Mobile Ad Hoc Networks[C]//Proceedings of the 4thEuropean Performance Engineering Workshop(EPEW 2007),2007,4748:275-283.

[7] M.B. Yasseing, S.F. Nimer, A.Y. Al-dubai. A new dynamic counter-based broadcasting scheme for mobile ad hoc networks[J]. Simulation Modelling Practice and Theory,2011,19(1):553-563.

[8] A. Mohammed, M. Ould-Khaoua, L. Mackenzie, et al. Dynamic probabilistic counter-based broadcasting in mobile ad hoc networks[C]//2ndinternational Confereence on Adaptive Science Technology(ICAST),2009:1120-127.

[9] Q. Zhang, D.P. Agrawal. Dynamic probabilistic broadcasting in manets[J]. Journal of Parallel and Distributed Computing,2005,65(2):220-233.

[10] D. hyeon Lee, S. Braun, M. Walchli, et al. Enchanced selective forwarding scheme for alert message propagation in vanets[J]. International Journal of Automotive Technology,2011,12(2):1-9.

[11] Sausen P S, Spohn M A, Perkusich A. Broadcast routing in wireless wensor networks with dynamic power management and multi-coverage backbones[J]. Inofrmation Sciences,2010,180(5):653-663.

[12] D. G. Reina, S. L. Toral, P. Jonhson, et al. Hybrid flooding scheme for mobile ad hoc networks[C]//IEEE Communications Letters,2013(3):592-595.

[13] B. Williams, T. Camp. Comparison of broadcasting techniques for mobile ad hoc networks[C]//Proceedings of the 3rdACM International Symposium on Mobile and Ad Hoc Networking and Computing(MobiHoc’02), Lausanne, Switzerland,2002:194-202.

[14] Z. J. Hass, J. Y. Halpem, L. Li. Gossip-based ad hoc routing[C]//Proceedings of the 21stAnnual Joint Conference of the IEEE Computer and Communications Societies, New York, USA,2002:1707-1716.

A Dynamic Broadcast Restrain Algorithm Based on Neighbors in MANET

ZHANG DaichenZHANG Hong

(Combat Teaching and Research Section, PLA Academy of National Defense Information, Wuhan430314)

Broadcast is one of the most important communication means in mobile ad hoc networks. Reactive routing protocols establish routes by broadcast. Conventional on-demand routing protocols suffer in terms of several issues such as rebroadcast redundancy and collisions. This paper proposes an algorithm called DBB(Density Based Algorithm). DBB calculates sending delay and forwarding probability based on neighbors of nodes and adjusts them dynamically according to the broadcasting situation. The strategy of extending cache is adopted to solve the problem of network division. Combining with the classic AODV routing protocol, the AODV-DBB protocol is designed. Computer simulation results confirm that AODV-DBB performs perfect in terms of redundancy and collisions compared with the other protocols, and the DBB algorithm can effectively reduce the cost of channel resource occupied by broadcast.

MANET, broadcast, routing protocols, delay, probability, network division

2016年2月8日,

2016年3月26日

國(guó)防信息學(xué)院科研課題項(xiàng)目(編號(hào):KYKT-155074)資助。

張岱臣,男,碩士,講師,研究方向:無(wú)線自組織網(wǎng)絡(luò)協(xié)議、負(fù)載均衡。張紅,男,碩士,講師,研究方向:無(wú)線網(wǎng)絡(luò)、網(wǎng)絡(luò)通信。

TP915

10.3969/j.issn.1672-9722.2016.08.024