無線多跳通信網(wǎng)絡(luò)中基于貝葉斯概率模型的消息轉(zhuǎn)發(fā)機(jī)制研究

(1.中國電子科技集團(tuán)公司 第五十四研究所，石家莊 050081；2.黑龍江大學(xué) 電子工程學(xué)院，哈爾濱 150080；3.哈爾濱工業(yè)大學(xué) 電子與信息工程學(xué)院，哈爾濱 150001)

0 引言

無線多跳通信網(wǎng)絡(luò)是一種有靜態(tài)或移動終端節(jié)點(diǎn)構(gòu)成的無中心分布控制網(wǎng)絡(luò)，網(wǎng)絡(luò)中任意節(jié)點(diǎn)之間往往需要依賴中間節(jié)點(diǎn)的分組轉(zhuǎn)發(fā)來實(shí)現(xiàn)廣域環(huán)境下信息的連續(xù)傳輸[1]。如何選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)并確定轉(zhuǎn)發(fā)路徑是無線多跳通信網(wǎng)絡(luò)中最為關(guān)鍵的技術(shù)基礎(chǔ)，已有多跳路由協(xié)議從不同角度實(shí)現(xiàn)網(wǎng)絡(luò)多跳路徑的發(fā)現(xiàn)與維護(hù)，從而保證網(wǎng)絡(luò)的連通性。通常，依據(jù)消息轉(zhuǎn)發(fā)方式的不同，無線多跳網(wǎng)絡(luò)中路由算法可以分為基于泛洪策略的路由算法和基于條件轉(zhuǎn)發(fā)的路由算法[2]。前者通過全網(wǎng)廣播的泛洪方式用以提高路由構(gòu)建的成功率，然而，這種泛洪廣播所產(chǎn)生的大量冗余信息往往占用大量的帶寬，并產(chǎn)生較大的能耗，主要用于節(jié)點(diǎn)數(shù)量不太多、網(wǎng)絡(luò)規(guī)模不太大、業(yè)務(wù)量不太重的輕量級網(wǎng)絡(luò)中。為此，近年來基于條件轉(zhuǎn)發(fā)的路由算法逐漸成為研究與應(yīng)用領(lǐng)域的熱點(diǎn)，用以滿足網(wǎng)絡(luò)規(guī)模日益增大、能量受限的移動終端數(shù)量日益增多的實(shí)際需求。從降低泛洪負(fù)載開銷的角度，條件轉(zhuǎn)發(fā)思想主要體現(xiàn)在以下兩種實(shí)現(xiàn)途徑：1)直接降低泛洪分組，如Spyropoulos等人[3]提出了SAW(spray and wait)路由算法，通過復(fù)制多個消息副本數(shù)而不是泛洪的思想來降低消息傳輸成本；2)構(gòu)建條件轉(zhuǎn)發(fā)參數(shù)集來降低轉(zhuǎn)發(fā)次數(shù)，如Xia等人[4]研究了物理近似度、用戶興趣等與網(wǎng)絡(luò)信息傳播密切相關(guān)的參數(shù)模型，提供了有效的數(shù)據(jù)中繼轉(zhuǎn)發(fā)的篩選指標(biāo)。然而，相關(guān)研究表明，已有條件轉(zhuǎn)發(fā)算法大多只關(guān)注負(fù)載成本，而沒有考慮終端節(jié)點(diǎn)能量受限且全局拓?fù)洳豢芍膯栴}。為此，如何在保證網(wǎng)絡(luò)連通性的前提下減少消息的轉(zhuǎn)發(fā)次數(shù)便成為相關(guān)領(lǐng)域的研究重點(diǎn)。

本研究提出了一種先計算后轉(zhuǎn)發(fā)的方法，以貝葉斯概率估計為原型構(gòu)造了一種新的消息轉(zhuǎn)發(fā)模型。在路徑構(gòu)建過程中，先選擇同等概率條件下的部分節(jié)點(diǎn)對消息進(jìn)行轉(zhuǎn)發(fā)，通過計算后驗(yàn)概率驗(yàn)證中間節(jié)點(diǎn)將消息成功轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)的概率，據(jù)此減少中間節(jié)點(diǎn)重播次數(shù)，降低信息碰撞概率，從而降低能量消耗并有效緩解網(wǎng)絡(luò)擁塞現(xiàn)象。

1 基于貝葉斯概率的RREQ轉(zhuǎn)發(fā)模型

路由請求RREQ是構(gòu)建有效傳輸路徑的重要基礎(chǔ)，傳統(tǒng)AODV的RREQ在傳播過程中將要求所有中間節(jié)點(diǎn)參與數(shù)據(jù)分組的轉(zhuǎn)發(fā)工作[5]。本研究在傳統(tǒng)AODV協(xié)議RREQ機(jī)制的基礎(chǔ)上，提出RREQ概率轉(zhuǎn)發(fā)方法，選取具有相同數(shù)量百分比的中間節(jié)點(diǎn)，降低鄰居節(jié)點(diǎn)的轉(zhuǎn)發(fā)參與概率，從而控制轉(zhuǎn)發(fā)消息的數(shù)量，用以減少能源消耗和重發(fā)。

AODV路由協(xié)議消息轉(zhuǎn)發(fā)中，某源節(jié)點(diǎn)有數(shù)據(jù)需要轉(zhuǎn)發(fā)，那么其通信范圍內(nèi)所有的n個鄰居節(jié)點(diǎn)都會收到RREQ并嘗試轉(zhuǎn)發(fā)該消息[6]，若網(wǎng)絡(luò)節(jié)點(diǎn)初始能量為Ei，鄰居節(jié)點(diǎn)消息轉(zhuǎn)發(fā)消耗的能量為Es。當(dāng)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)控制消息時，對任意多跳路徑，鄰居節(jié)點(diǎn)的剩余能量Etotal如(1)所示：

Etotal=Ei-Es

(1)

當(dāng)采用消息概率轉(zhuǎn)發(fā)機(jī)制，例如：假設(shè)只允許鄰居節(jié)點(diǎn)以0.5的概率轉(zhuǎn)發(fā)任何消息，這意味著只有50%的中間節(jié)點(diǎn)將能夠接收和轉(zhuǎn)發(fā)消息，此時，鄰居節(jié)點(diǎn)的剩余能量如(2)所示：

Etotal=Ei-Es/2

(2)

對比式(1)和(2)可見，采用消息概率轉(zhuǎn)發(fā)的方法相比全中繼轉(zhuǎn)發(fā)能降低網(wǎng)絡(luò)能耗。盡管轉(zhuǎn)發(fā)節(jié)點(diǎn)數(shù)量越少，能量消耗越小，而網(wǎng)絡(luò)連通性也將隨之降低。本研究將在保證網(wǎng)絡(luò)連通性的條件下，構(gòu)建基于貝葉斯概率模型的轉(zhuǎn)發(fā)機(jī)制。

2 基于貝葉斯概率模型的AODV算法

2.1 AODV中RREQ的貝葉斯概率轉(zhuǎn)發(fā)

AODV是目前無線多跳通信網(wǎng)絡(luò)，特別是MANET中最為常用的路由協(xié)議之一，其RREQ/RREP的消息轉(zhuǎn)發(fā)遵循如下方式：當(dāng)信源節(jié)點(diǎn)有數(shù)據(jù)需送往目的節(jié)點(diǎn)，則廣播路由請求信息RREQ。RREQ可能通過多條路徑上的中間節(jié)點(diǎn)轉(zhuǎn)發(fā)到達(dá)目的節(jié)點(diǎn)[7]。當(dāng)目的節(jié)點(diǎn)從上游節(jié)點(diǎn)接收到RREQ分組，將回復(fù)RREP。事實(shí)上，目的節(jié)點(diǎn)收到RREQ的信息路徑和信源節(jié)點(diǎn)收到RREP的消息的路徑有可能是不同的。因此，RREQ/RREP結(jié)束時，信源節(jié)點(diǎn)可能存在不同的路徑選擇，從而引起較大的負(fù)載開銷和能量消耗[8]。

本文將基于所構(gòu)建的貝葉斯概率模型，對消息轉(zhuǎn)發(fā)機(jī)制進(jìn)行優(yōu)化。貝葉斯概率模型以條件概率為基礎(chǔ)，聯(lián)合兩個事件的概率A和B得出條件概率公式，如(3)所示[9]：

P(AB)=P(A│B)×P(B)=P(B│A)×P(A)

(3)

由于直接計算P(A)比較困難，通常可以利用全概率公式[10]計算P(A)，如(4)所示：

(4)

在條件概率的基礎(chǔ)上，貝葉斯公可用于尋找事件發(fā)生的原因，對任意事件A(P(A)>0)，其貝葉斯公式如式(5)所示[11]：

(5)

P(Di│D)=

(6)

采用經(jīng)貝葉斯模型篩選后的鄰居節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，在假設(shè)鄰居節(jié)點(diǎn)轉(zhuǎn)發(fā)概率和目的節(jié)點(diǎn)接收概率均為50%的情況下，只有20%的鄰居節(jié)點(diǎn)參與轉(zhuǎn)發(fā)并成功的將消息送往目的節(jié)點(diǎn)。因此，只需在已經(jīng)選擇的部分鄰居節(jié)點(diǎn)中進(jìn)行消息轉(zhuǎn)發(fā)即可。這里，轉(zhuǎn)發(fā)概率取決于鄰居節(jié)點(diǎn)的數(shù)量，如果附近鄰居節(jié)點(diǎn)密度高，后驗(yàn)概率將減少，說明目的節(jié)點(diǎn)在同等概率下收到消息需要較少的鄰居節(jié)點(diǎn)進(jìn)行消息轉(zhuǎn)發(fā)，因此網(wǎng)絡(luò)開銷將降低。

2.2 B_AODV的路由發(fā)現(xiàn)算法

本節(jié)將基于所設(shè)計的RREQ貝葉斯概率轉(zhuǎn)發(fā)模型在AODV的基礎(chǔ)上構(gòu)建貝葉斯概率轉(zhuǎn)發(fā)路由算法B_AODV，在保證網(wǎng)絡(luò)連通性的條件下降低網(wǎng)絡(luò)負(fù)載開銷。設(shè)網(wǎng)絡(luò)中信源節(jié)點(diǎn)S有數(shù)據(jù)需發(fā)送到目的節(jié)點(diǎn)D，在AODV的路由發(fā)現(xiàn)過程中，任意節(jié)點(diǎn)Fi(i=1,2,3,…,N)接收到RREQ分組后進(jìn)行分組處理，根據(jù)所建立的貝葉斯概率模型，計算中間節(jié)點(diǎn)轉(zhuǎn)發(fā)概率Pm。算法1給出本文所提出基于貝葉斯概率模型的B_AODV路由發(fā)現(xiàn)過程。

算法1:B_AODV路由發(fā)現(xiàn)算法

Define Objective functionPm,Pm<1; //由式(5)得到

Initialization Random valueR,R∈[0,1],Si,Dt,Fp,Ms;

//St信源節(jié)點(diǎn)，Dt目的節(jié)點(diǎn)，F(xiàn)p收到RREQ的節(jié)點(diǎn)，Ms中間節(jié)點(diǎn),?i,t,p,s∈{1,2,…,N}

Whiledo Recv(RREQ)≠? do

If RREQ(Si→Dt)≠?,?i,t∈{1,2,…,N}

Process as Normal AODV

End

IfFp==Si

Ignore and drop the RREQ message

Else IfFp==Dt

If Recv(RREQ_ID)≠?

Drop RREQ

Else Send RREP to set up the reverse route

Else IfDt∈Neighb(Fp)

Send RREP to set up the reverse route;

Else Count Num_Neighb(Fp);

CalculatePm;

IfPm

Forward the RREQ

Else

Ignore and drop the RREQ

End

End

End

End

End

本文所提出的B_AODV是基于AODV的路由機(jī)制，在路由發(fā)現(xiàn)的RREQ轉(zhuǎn)發(fā)中采用了本文所構(gòu)建的貝葉斯概率轉(zhuǎn)發(fā)模型，通過動態(tài)計算中間節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率實(shí)現(xiàn)中繼最優(yōu)選擇，既避免了全網(wǎng)泛洪的負(fù)載開銷，又緩解了普通條件轉(zhuǎn)發(fā)下的網(wǎng)絡(luò)連通性問題。

3 仿真結(jié)果與性能分析

3.1 仿真環(huán)境的構(gòu)建

本節(jié)將基于NS2網(wǎng)絡(luò)仿真器對所提出的基于貝葉斯概率模型的消息轉(zhuǎn)發(fā)機(jī)制性能進(jìn)行分析。仿真場景中，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量設(shè)置在10～100之間，用于對比不同網(wǎng)絡(luò)密度下消息轉(zhuǎn)發(fā)效率。節(jié)點(diǎn)移動速度vmax為5 m/s，表明網(wǎng)絡(luò)中節(jié)點(diǎn)以v(v∈[0,vmax])速度進(jìn)行間歇性移動。相同參數(shù)設(shè)置下仿真重復(fù)10次取性能平均。傳輸層采用用戶數(shù)據(jù)報協(xié)議(UDP)以恒比特率(CBR)發(fā)送數(shù)據(jù)分組。為了對路由性能進(jìn)行分析，仿真中采用了AODV、AODV_EXT、B_AODV、OLSR、DSDV以及DSR進(jìn)行對比。其他仿真參數(shù)如表1所示。

表1 仿真參數(shù)設(shè)置

仿真分析中主要采用以下性能指標(biāo)：

1)歸一化能量消耗：消息傳輸過程中整個網(wǎng)絡(luò)消耗的能量，反映在不同的網(wǎng)絡(luò)密度下網(wǎng)絡(luò)能量的消耗，網(wǎng)絡(luò)規(guī)模越大其消耗的能量就越多；

2)吞吐量：每秒到達(dá)的數(shù)據(jù)包數(shù)量，反映路由協(xié)議對數(shù)據(jù)的收發(fā)能力；

3)歸一化路由開銷：發(fā)送數(shù)據(jù)所需要的路由包總數(shù)與接收到的數(shù)據(jù)包的比值，該性能指標(biāo)反應(yīng)了多跳通信網(wǎng)絡(luò)擁塞程度和路由效率；

4)數(shù)據(jù)分組成功交付率：網(wǎng)絡(luò)中所有目的節(jié)點(diǎn)收到數(shù)據(jù)包的數(shù)量和源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包的數(shù)量的比值，反映網(wǎng)絡(luò)傳輸性能的可靠性，即比值越大，可靠性越好。

3.2 實(shí)驗(yàn)結(jié)果與分析

通過在實(shí)驗(yàn)場景下部署不同數(shù)量的節(jié)點(diǎn)仿真在不同網(wǎng)絡(luò)密度下的網(wǎng)絡(luò)歸一化能量消耗和網(wǎng)絡(luò)有效吞吐量，性能對比如圖1和圖2所示。

由圖1所示網(wǎng)絡(luò)歸一化能量消耗可以看出，不論采用何種路由協(xié)議，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量增加時，網(wǎng)絡(luò)總能量消耗都隨之增加。這是由于RREQ的轉(zhuǎn)發(fā)，不論是全網(wǎng)泛洪還是條件轉(zhuǎn)發(fā)，都將引起廣播數(shù)量的上升，從而增加全網(wǎng)能量消耗。

圖1 網(wǎng)絡(luò)歸一化能量消耗

然而，當(dāng)節(jié)點(diǎn)數(shù)量在10～40個之間時，采用泛洪式消息轉(zhuǎn)發(fā)的路由協(xié)議消耗的能量增加的比較緩慢。而當(dāng)節(jié)點(diǎn)數(shù)量大于50個以后，泛洪式轉(zhuǎn)發(fā)的路由協(xié)議由于在網(wǎng)絡(luò)中大規(guī)模的進(jìn)行消息轉(zhuǎn)發(fā)，在嚴(yán)重超負(fù)載的情況下能量消耗幾乎呈直線上升，而本文基于貝葉斯概率模型提出的B_AODV由于對鄰居節(jié)點(diǎn)進(jìn)行選擇性消息轉(zhuǎn)發(fā)而非泛洪式消息轉(zhuǎn)發(fā)，因此相比其他5個協(xié)議消耗能量更小，能量消耗增加的速度也更緩慢。

由此可見，在大規(guī)模網(wǎng)絡(luò)中此消息轉(zhuǎn)發(fā)模型相比于泛洪式消息轉(zhuǎn)發(fā)節(jié)省更多的能量。其中OLSR網(wǎng)絡(luò)能量消耗上升趨勢最為明顯，這是因?yàn)殡S著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量的增多，OLSR協(xié)議使用的機(jī)制中不斷地更新鄰居節(jié)點(diǎn)的信息，所有相比于其它協(xié)議，能量消耗的更快。

圖2所示網(wǎng)絡(luò)有效吞吐量的對比結(jié)果表明，傳統(tǒng)的DSR吞吐量性能最好，而采用B_AODV，AODV_EXT和AODV協(xié)議，由于網(wǎng)絡(luò)節(jié)點(diǎn)不需要保持兩個節(jié)點(diǎn)之間的路由，降低了路由所需的信號發(fā)現(xiàn)和維護(hù)的功能，導(dǎo)致網(wǎng)絡(luò)吞吐量有所降低。OLSR和DSDV與其他協(xié)議相比較性能較差，這是因?yàn)檫@類主動協(xié)議路由更新需要產(chǎn)生相對較高的消息傳遞開銷，特別是在移動網(wǎng)絡(luò)中會導(dǎo)致大型網(wǎng)絡(luò)擁塞，因此，這兩個協(xié)議更加適合于速率較低的數(shù)據(jù)傳輸。

圖2 網(wǎng)絡(luò)有效吞吐量

仿真中信源節(jié)點(diǎn)的分組發(fā)送率為4 p/s，表明業(yè)務(wù)量較大。節(jié)點(diǎn)的移動性將導(dǎo)致路由發(fā)現(xiàn)負(fù)載開銷進(jìn)一步上升。為了分析動態(tài)網(wǎng)絡(luò)環(huán)境下本文所提出B_AODV的適應(yīng)性，仿真中對動態(tài)環(huán)境下采用不同路由協(xié)議的網(wǎng)絡(luò)路由開銷和分組成功交付率進(jìn)行了測試，結(jié)果分別如圖3和圖4所示。

圖3 網(wǎng)絡(luò)歸一化路由開銷

圖3的仿真結(jié)果表明，隨著節(jié)點(diǎn)移動速度的增加，各個協(xié)議的路由開銷也隨之增大，當(dāng)節(jié)點(diǎn)移動速度較低時，各個協(xié)議的路由開銷相差較小，而當(dāng)速度增大以后，鏈路中斷的可能性變大，路由修復(fù)的次數(shù)將增多，這便需要更多的路由包，因此路由開銷變大。此外，B_AODV對消息轉(zhuǎn)發(fā)的中間節(jié)點(diǎn)進(jìn)行概率性的選擇，限制了RREQ在網(wǎng)絡(luò)中的泛洪，避免出現(xiàn)中間節(jié)點(diǎn)對消息重播的現(xiàn)象，所以表現(xiàn)出的路由開銷最低。而DSR和DSDV顯示了能夠收發(fā)較少的消息，這是因?yàn)榫W(wǎng)絡(luò)拓?fù)潆S時變化，源節(jié)點(diǎn)的RREQ很難甚至無法準(zhǔn)確找到目的節(jié)點(diǎn)所導(dǎo)致的。

圖4表明，當(dāng)節(jié)點(diǎn)移動速度較低時，B_AODV數(shù)據(jù)分組交付率明顯高于AODV_EXT和原AODV協(xié)議，由于在鏈路即將失效前B_AODV根據(jù)貝葉斯概率論已經(jīng)計算出可以成功進(jìn)行消息轉(zhuǎn)發(fā)的路徑，使得網(wǎng)絡(luò)能夠更快的適應(yīng)拓?fù)浣Y(jié)構(gòu)變化，減少因?yàn)橹匦陆范鴮?dǎo)致的數(shù)據(jù)丟失。

圖4 數(shù)據(jù)分組成功交付率

threshold 由圖4可以發(fā)現(xiàn)，當(dāng)節(jié)點(diǎn)移動速度越來越大時，各個路由協(xié)議數(shù)據(jù)分組投遞率下降，而 B-AODV數(shù)據(jù)投遞率下降緩慢，與傳統(tǒng)的AODV最大相差20%左右。DSDV與B_AODV的結(jié)果幾乎相同，因?yàn)橹皇褂孟噜徆?jié)點(diǎn)發(fā)送或者接收的數(shù)據(jù)包的機(jī)制有更好的網(wǎng)絡(luò)性能。由此可見，B_AODV具有更好的穩(wěn)定性，為網(wǎng)絡(luò)中的數(shù)據(jù)成功傳輸提供了保障。

4 結(jié)束語

本文立足于無線多跳網(wǎng)絡(luò)中路由發(fā)現(xiàn)過程中消息轉(zhuǎn)發(fā)所引起的重負(fù)載開銷和高能量消耗，基于貝葉斯概率論構(gòu)建了無線多跳網(wǎng)絡(luò)貝葉斯消息轉(zhuǎn)發(fā)模型，通過計算節(jié)點(diǎn)密度和后驗(yàn)概率在保證網(wǎng)絡(luò)連通性的條件下減少不必要的消息轉(zhuǎn)發(fā)，并據(jù)此對多跳網(wǎng)絡(luò)典型路由協(xié)議AODV進(jìn)行改進(jìn)，提出了一種動態(tài)概率轉(zhuǎn)發(fā)的路由算法B_AODV。研究結(jié)果表明，基于貝葉斯概率論的消息轉(zhuǎn)發(fā)模型的B_AODV路由算法在降低網(wǎng)絡(luò)能量消耗以及路由開銷方面具有一定優(yōu)勢，當(dāng)網(wǎng)絡(luò)規(guī)模較大時，這一優(yōu)勢更加明顯。該算法的主要優(yōu)點(diǎn)之一是在不影響傳播準(zhǔn)確度的情況下減少傳統(tǒng)AODV及同類路由算法的重播次數(shù)，與傳統(tǒng)概率條件轉(zhuǎn)發(fā)機(jī)制相比，本文所提出的貝葉斯概率方案將有效減少轉(zhuǎn)發(fā)RREQ的中間節(jié)點(diǎn)數(shù)量。此外，B_AODV路由算法能夠更好的支持動態(tài)無線多跳通信網(wǎng)絡(luò)，其分組成功交付率方面均明顯優(yōu)于其他同類路由協(xié)議。因此，B_AODV算法不僅在減少消息多次重播和節(jié)約功耗方面具有優(yōu)勢，而且可以降低信道擁塞，提高通信，從而為未來廣域大規(guī)模動態(tài)多跳網(wǎng)絡(luò)部署提供技術(shù)支撐。