張岱臣　張　紅

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

?

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

張岱臣張紅

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

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

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

Class NumberTP915

1　引言

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

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

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

2　相關(guān)工作

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

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

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

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

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

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

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

非基于狀態(tài)的廣播算法中,節(jié)點完全分布式操作,不需要交互任何信息,例如基于概率和基于位置信息的算法,這些算法受網(wǎng)絡(luò)拓撲變化的影響很小。但是非基于狀態(tài)的廣播算法在節(jié)點密度高的網(wǎng)絡(luò)中廣播冗余較大[14]。

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

3　算法及協(xié)議

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

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

3.1時延和概率初始化

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

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

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

(1)

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

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

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

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

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

(2)

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

3.2定時器和概率的更新

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

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

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

Tk+1=Tk×NR

(3)

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

在節(jié)點密度較大的網(wǎng)絡(luò)中,發(fā)送的廣播包數(shù)可能較多,為防止出現(xiàn)定時器無限等待,設(shè)置兩個參數(shù),一個是超時計數(shù)器(Timer Counter,TC),另一個是超時次數(shù)門限(Waiting Threshold,Wth)。超時計數(shù)器TC用來計量節(jié)點達到定時器的次數(shù),超時次數(shù)門限Wth用來對超時計數(shù)器進行限制,是超時計數(shù)器的最大值。當定時器多次超時到期,即超時計數(shù)器達到超時次數(shù)門限時,節(jié)點將取消定時器,并拋棄廣播包。其中Wth是一個手工預(yù)設(shè)的參數(shù),其需要依據(jù)網(wǎng)絡(luò)密度來進行設(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é)點在上一個定時器時間內(nèi)收到的重復(fù)包數(shù)?？梢?節(jié)點收到的重復(fù)包數(shù)越多其轉(zhuǎn)發(fā)變得概率越小。已被轉(zhuǎn)發(fā)的廣播越多,后邊節(jié)點轉(zhuǎn)發(fā)廣播的概率越小,減少了重復(fù)的廣播數(shù)。

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

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

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

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

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

緩存延長的時間可根據(jù)節(jié)點的移動速度進行設(shè)置。節(jié)點的移動速度越快,說明網(wǎng)絡(luò)拓撲很快,那么網(wǎng)絡(luò)分裂愈合的速度就越快,那么緩存延長的時間就越短,否則可延長緩存時間。

3.4AODV-DBB協(xié)議

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

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

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

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

4　仿真分析

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

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

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

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

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

設(shè)置兩個場景對協(xié)議進行仿真:

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

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

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

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

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

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

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

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

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

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

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

圖6是在不同負載下網(wǎng)絡(luò)中發(fā)送的廣播數(shù),可以看到,不同協(xié)議下的RREQ廣播數(shù)都隨著負載的增大而增多。當負載增大時,由網(wǎng)絡(luò)拓撲變化引起的尋路廣播顯著增多,但AODV-DBB協(xié)議的廣播冗余度都低于AODV-HPC和AODV。

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

5　結(jié)語

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

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

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

[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日

國防信息學(xué)院科研課題項目(編號:KYKT-155074)資助。

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

TP915

10.3969/j.issn.1672-9722.2016.08.024