无线多跳通信网络中基于贝叶斯概率模型的消息转发机制研究

(1.中国电子科技集团公司 第五十四研究所，石家庄 050081；2.黑龙江大学 电子工程学院，哈尔滨 150080；3.哈尔滨工业大学 电子与信息工程学院，哈尔滨 150001)

0 引言

无线多跳通信网络是一种有静态或移动终端节点构成的无中心分布控制网络，网络中任意节点之间往往需要依赖中间节点的分组转发来实现广域环境下信息的连续传输[1]。如何选择转发节点并确定转发路径是无线多跳通信网络中最为关键的技术基础，已有多跳路由协议从不同角度实现网络多跳路径的发现与维护，从而保证网络的连通性。通常，依据消息转发方式的不同，无线多跳网络中路由算法可以分为基于泛洪策略的路由算法和基于条件转发的路由算法[2]。前者通过全网广播的泛洪方式用以提高路由构建的成功率，然而，这种泛洪广播所产生的大量冗余信息往往占用大量的带宽，并产生较大的能耗，主要用于节点数量不太多、网络规模不太大、业务量不太重的轻量级网络中。为此，近年来基于条件转发的路由算法逐渐成为研究与应用领域的热点，用以满足网络规模日益增大、能量受限的移动终端数量日益增多的实际需求。从降低泛洪负载开销的角度，条件转发思想主要体现在以下两种实现途径：1)直接降低泛洪分组，如Spyropoulos等人[3]提出了SAW(spray and wait)路由算法，通过复制多个消息副本数而不是泛洪的思想来降低消息传输成本；2)构建条件转发参数集来降低转发次数，如Xia等人[4]研究了物理近似度、用户兴趣等与网络信息传播密切相关的参数模型，提供了有效的数据中继转发的筛选指标。然而，相关研究表明，已有条件转发算法大多只关注负载成本，而没有考虑终端节点能量受限且全局拓扑不可知的问题。为此，如何在保证网络连通性的前提下减少消息的转发次数便成为相关领域的研究重点。

本研究提出了一种先计算后转发的方法，以贝叶斯概率估计为原型构造了一种新的消息转发模型。在路径构建过程中，先选择同等概率条件下的部分节点对消息进行转发，通过计算后验概率验证中间节点将消息成功转发到目的节点的概率，据此减少中间节点重播次数，降低信息碰撞概率，从而降低能量消耗并有效缓解网络拥塞现象。

1 基于贝叶斯概率的RREQ转发模型

路由请求RREQ是构建有效传输路径的重要基础，传统AODV的RREQ在传播过程中将要求所有中间节点参与数据分组的转发工作[5]。本研究在传统AODV协议RREQ机制的基础上，提出RREQ概率转发方法，选取具有相同数量百分比的中间节点，降低邻居节点的转发参与概率，从而控制转发消息的数量，用以减少能源消耗和重发。

AODV路由协议消息转发中，某源节点有数据需要转发，那么其通信范围内所有的n个邻居节点都会收到RREQ并尝试转发该消息[6]，若网络节点初始能量为Ei，邻居节点消息转发消耗的能量为Es。当邻居节点转发控制消息时，对任意多跳路径，邻居节点的剩余能量Etotal如(1)所示：

Etotal=Ei-Es

(1)

当采用消息概率转发机制，例如：假设只允许邻居节点以0.5的概率转发任何消息，这意味着只有50%的中间节点将能够接收和转发消息，此时，邻居节点的剩余能量如(2)所示：

Etotal=Ei-Es/2

(2)

对比式(1)和(2)可见，采用消息概率转发的方法相比全中继转发能降低网络能耗。尽管转发节点数量越少，能量消耗越小，而网络连通性也将随之降低。本研究将在保证网络连通性的条件下，构建基于贝叶斯概率模型的转发机制。

2 基于贝叶斯概率模型的AODV算法

2.1 AODV中RREQ的贝叶斯概率转发

AODV是目前无线多跳通信网络，特别是MANET中最为常用的路由协议之一，其RREQ/RREP的消息转发遵循如下方式：当信源节点有数据需送往目的节点，则广播路由请求信息RREQ。RREQ可能通过多条路径上的中间节点转发到达目的节点[7]。当目的节点从上游节点接收到RREQ分组，将回复RREP。事实上，目的节点收到RREQ的信息路径和信源节点收到RREP的消息的路径有可能是不同的。因此，RREQ/RREP结束时，信源节点可能存在不同的路径选择，从而引起较大的负载开销和能量消耗[8]。

本文将基于所构建的贝叶斯概率模型，对消息转发机制进行优化。贝叶斯概率模型以条件概率为基础，联合两个事件的概率A和B得出条件概率公式，如(3)所示[9]：

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

(3)

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

(4)

在条件概率的基础上，贝叶斯公可用于寻找事件发生的原因，对任意事件A(P(A)>0)，其贝叶斯公式如式(5)所示[11]：

(5)

P(Di│D)=

(6)

采用经贝叶斯模型筛选后的邻居节点进行消息转发，在假设邻居节点转发概率和目的节点接收概率均为50%的情况下，只有20%的邻居节点参与转发并成功的将消息送往目的节点。因此，只需在已经选择的部分邻居节点中进行消息转发即可。这里，转发概率取决于邻居节点的数量，如果附近邻居节点密度高，后验概率将减少，说明目的节点在同等概率下收到消息需要较少的邻居节点进行消息转发，因此网络开销将降低。

2.2 B_AODV的路由发现算法

本节将基于所设计的RREQ贝叶斯概率转发模型在AODV的基础上构建贝叶斯概率转发路由算法B_AODV，在保证网络连通性的条件下降低网络负载开销。设网络中信源节点S有数据需发送到目的节点D，在AODV的路由发现过程中，任意节点Fi(i=1,2,3,…,N)接收到RREQ分组后进行分组处理，根据所建立的贝叶斯概率模型，计算中间节点转发概率Pm。算法1给出本文所提出基于贝叶斯概率模型的B_AODV路由发现过程。

算法1:B_AODV路由发现算法

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

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

//St信源节点，Dt目的节点，Fp收到RREQ的节点，Ms中间节点,∀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的路由机制，在路由发现的RREQ转发中采用了本文所构建的贝叶斯概率转发模型，通过动态计算中间节点的转发概率实现中继最优选择，既避免了全网泛洪的负载开销，又缓解了普通条件转发下的网络连通性问题。

3 仿真结果与性能分析

3.1 仿真环境的构建

本节将基于NS2网络仿真器对所提出的基于贝叶斯概率模型的消息转发机制性能进行分析。仿真场景中，网络节点数量设置在10～100之间，用于对比不同网络密度下消息转发效率。节点移动速度vmax为5 m/s，表明网络中节点以v(v∈[0,vmax])速度进行间歇性移动。相同参数设置下仿真重复10次取性能平均。传输层采用用户数据报协议(UDP)以恒比特率(CBR)发送数据分组。为了对路由性能进行分析，仿真中采用了AODV、AODV_EXT、B_AODV、OLSR、DSDV以及DSR进行对比。其他仿真参数如表1所示。

表1 仿真参数设置

仿真分析中主要采用以下性能指标：

1)归一化能量消耗：消息传输过程中整个网络消耗的能量，反映在不同的网络密度下网络能量的消耗，网络规模越大其消耗的能量就越多；

2)吞吐量：每秒到达的数据包数量，反映路由协议对数据的收发能力；

3)归一化路由开销：发送数据所需要的路由包总数与接收到的数据包的比值，该性能指标反应了多跳通信网络拥塞程度和路由效率；

4)数据分组成功交付率：网络中所有目的节点收到数据包的数量和源节点发送数据包的数量的比值，反映网络传输性能的可靠性，即比值越大，可靠性越好。

3.2 实验结果与分析

通过在实验场景下部署不同数量的节点仿真在不同网络密度下的网络归一化能量消耗和网络有效吞吐量，性能对比如图1和图2所示。

由图1所示网络归一化能量消耗可以看出，不论采用何种路由协议，当网络节点数量增加时，网络总能量消耗都随之增加。这是由于RREQ的转发，不论是全网泛洪还是条件转发，都将引起广播数量的上升，从而增加全网能量消耗。

图1 网络归一化能量消耗

然而，当节点数量在10～40个之间时，采用泛洪式消息转发的路由协议消耗的能量增加的比较缓慢。而当节点数量大于50个以后，泛洪式转发的路由协议由于在网络中大规模的进行消息转发，在严重超负载的情况下能量消耗几乎呈直线上升，而本文基于贝叶斯概率模型提出的B_AODV由于对邻居节点进行选择性消息转发而非泛洪式消息转发，因此相比其他5个协议消耗能量更小，能量消耗增加的速度也更缓慢。

由此可见，在大规模网络中此消息转发模型相比于泛洪式消息转发节省更多的能量。其中OLSR网络能量消耗上升趋势最为明显，这是因为随着网络节点数量的增多，OLSR协议使用的机制中不断地更新邻居节点的信息，所有相比于其它协议，能量消耗的更快。

图2所示网络有效吞吐量的对比结果表明，传统的DSR吞吐量性能最好，而采用B_AODV，AODV_EXT和AODV协议，由于网络节点不需要保持两个节点之间的路由，降低了路由所需的信号发现和维护的功能，导致网络吞吐量有所降低。OLSR和DSDV与其他协议相比较性能较差，这是因为这类主动协议路由更新需要产生相对较高的消息传递开销，特别是在移动网络中会导致大型网络拥塞，因此，这两个协议更加适合于速率较低的数据传输。

图2 网络有效吞吐量

仿真中信源节点的分组发送率为4 p/s，表明业务量较大。节点的移动性将导致路由发现负载开销进一步上升。为了分析动态网络环境下本文所提出B_AODV的适应性，仿真中对动态环境下采用不同路由协议的网络路由开销和分组成功交付率进行了测试，结果分别如图3和图4所示。

图3 网络归一化路由开销

图3的仿真结果表明，随着节点移动速度的增加，各个协议的路由开销也随之增大，当节点移动速度较低时，各个协议的路由开销相差较小，而当速度增大以后，链路中断的可能性变大，路由修复的次数将增多，这便需要更多的路由包，因此路由开销变大。此外，B_AODV对消息转发的中间节点进行概率性的选择，限制了RREQ在网络中的泛洪，避免出现中间节点对消息重播的现象，所以表现出的路由开销最低。而DSR和DSDV显示了能够收发较少的消息，这是因为网络拓扑随时变化，源节点的RREQ很难甚至无法准确找到目的节点所导致的。

图4表明，当节点移动速度较低时，B_AODV数据分组交付率明显高于AODV_EXT和原AODV协议，由于在链路即将失效前B_AODV根据贝叶斯概率论已经计算出可以成功进行消息转发的路径，使得网络能够更快的适应拓扑结构变化，减少因为重新建路而导致的数据丢失。

图4 数据分组成功交付率

threshold 由图4可以发现，当节点移动速度越来越大时，各个路由协议数据分组投递率下降，而 B-AODV数据投递率下降缓慢，与传统的AODV最大相差20%左右。DSDV与B_AODV的结果几乎相同，因为只使用相邻节点发送或者接收的数据包的机制有更好的网络性能。由此可见，B_AODV具有更好的稳定性，为网络中的数据成功传输提供了保障。

4 结束语

本文立足于无线多跳网络中路由发现过程中消息转发所引起的重负载开销和高能量消耗，基于贝叶斯概率论构建了无线多跳网络贝叶斯消息转发模型，通过计算节点密度和后验概率在保证网络连通性的条件下减少不必要的消息转发，并据此对多跳网络典型路由协议AODV进行改进，提出了一种动态概率转发的路由算法B_AODV。研究结果表明，基于贝叶斯概率论的消息转发模型的B_AODV路由算法在降低网络能量消耗以及路由开销方面具有一定优势，当网络规模较大时，这一优势更加明显。该算法的主要优点之一是在不影响传播准确度的情况下减少传统AODV及同类路由算法的重播次数，与传统概率条件转发机制相比，本文所提出的贝叶斯概率方案将有效减少转发RREQ的中间节点数量。此外，B_AODV路由算法能够更好的支持动态无线多跳通信网络，其分组成功交付率方面均明显优于其他同类路由协议。因此，B_AODV算法不仅在减少消息多次重播和节约功耗方面具有优势，而且可以降低信道拥塞，提高通信，从而为未来广域大规模动态多跳网络部署提供技术支撑。