MANET中基于邻居度的动态广播抑制算法

张岱臣　张　红

(国防信息学院作战训练教研室　武汉　430314)



MANET中基于邻居度的动态广播抑制算法

张岱臣张红

(国防信息学院作战训练教研室武汉430314)

广播是移动自组织网络最重要的应用之一,按需路由协议一般通过广播建立路由。传统的按需路由协议中,广播存在冲突和冗余较多的问题。提出一种基于节点邻居度的动态广播抑制算法DBB(Density Based Broadcast),节点利用邻居度产生广播转发的时延和概率,并根据重复广播数动态调整;用延长缓存的方法解决网络分裂的问题。结合经典的AODV(Ad hoc on Demand Distance Vector)路由协议,设计了AODV-DBB协议。仿真结果表明,AODV-DBB协议中的广播冲突和冗余远低于其他协议,DBB算法能有效减少广播对信道资源的占用。

移动自组织网络; 广播; 路由协议; 时延; 概率; 网络分裂

Class NumberTP915

1　引言

移动自组织网络(mobile ad hoc network,MANET)具有无线广播信道、带宽受限、能量有限、多跳网络等特点,使路由协议的设计面临很大挑战,尤其要求路由协议高效可靠。广播是路由协议建立和更新路由的基本途径,按需路由协议通过广播寻找路由,主动式路由协议通过广播维护路由。

目前,大部分路由协议采用洪泛式广播,但洪泛式广播算法中节点盲目转发广播,网络中存在大量的重复数据,广播冗余度很高;而且相邻节点转发广播的时间高度相关,极易发生广播冲突。冲突不但浪费信道资源,也降低了广播的可靠性,即使在一个全连通的网络中,也可能由于冲突而使有些节点收不到广播。广播引起的冗余高和冲突多等问题统称为“广播风暴”[1～2]。“广播风暴”在节点密度较高的网络中尤其严重,由于转发的广播较多,网络中存在大量冗余和冲突,严重影响网络性能[3]。

优化广播算法,减少广播冗余,降低冲突,能节省宝贵的信道资源和终端能量,对于提高路由协议的效率,延长网络生命周期具有重要意义。本文提出一种基于邻居度的动态广播抑制算法DBB(Density Based Broadcast),节点根据邻居度来动态调整广播转发的时延和概率,并针对稀疏网络设计了广播缓存期延长策略,以解决网络分裂导致的广播失败问题。

2　相关工作

广播最简单的实现方式是“洪泛”,其缺点是广播冗余大冲突多。目前,广播算法主要从降低冗余和减少冲突两方面进行优化。主要有基于概率的算法,基于邻居信息的算法,基于计数器的算法等。

文献[4]提出一种变概率算法SPS(Smart Probabilistic Scheme),其把节点的密度分成四个等级,每个密度等级对应一个转发概率,密度越大转发的概率越小。该算法需要手工设置密度和对应的概率,设置参数不当将对算法产生致命影响,而且算法需要发送HELLO消息也占用了一定的信道资源。

文献[5]提出一种基于邻居信息的算法。算法在节点之间交互一跳邻居信息,然后节点根据邻居信息和转发RREQ所能额外覆盖的节点数来设置转发概率,额外覆盖的节点数越多转发的概率越大。当网络拓扑变化频繁时,其计算的额外覆盖节点不准确,影响算法的性能,而且传播的邻居信息也带来了额外开销,该算法不适合动态性较大的网络。

文献[6]提出基于计数器策略的HPC(Hybrid Probabilistic Counter)算法,HPC算法通过一个函数计算广播转发的概率,并且通过收到的重复广播数动态调整概率。但算法中采用的随机延迟技术在广播增加时仍然会产生较多冲突,影响算法的性能。文献[7]提出另一种基于计数器的策略,但是该算法需要维护节点之间的邻居列表,增加了额外开销,也增加了能量消耗。

文献[8～9]提出减少冲突的广播算法,但算法中使用了固定的参数,对网络的适应性不好,当网络密度较大时,算法性能下降[10]。文献[11]提出一种应用动态能量管理的广播算法,延长网络生命周期,该算法不适用于拓扑动态变化的移动自组织网络。文献[12]提出一种混合式的广播算法,算法结合了几种广播策略来解决广播风暴问题,该算法的实质还是基于节点密度的策略。

各广播算法各有特点,从是否需要保存网络状态的角度可分为两类,一类是基于状态信息的广播,另一类是非基于状态信息的。基于状态信息的广播算法需要在节点之间传递信息,比如基于邻居信息的算法,其需要在节点之间传递一跳邻居信息;非基于状态信息的算法是完全分布式操作,节点之间不需要传递任何信息,比如基于概率的算法。

基于状态信息的算法中,节点根据局部的网络状态对广播转发的计算相对精确,所以受网络流量和数据冲突的影响较小[13]。但是,节点交互的邻居信息带来额外开销;另外,算法依赖网络拓扑,当网络拓扑变化频繁时会产生较多的控制信息,甚至当网络变化很快的时候算法无法收敛。网络拓扑的变化不仅由节点移动引起,节能机制使节点休眠也将导致网络拓扑发生变化,所以基于状态的广播算法不适合应用在传感器网络和车辆网络中。

非基于状态的广播算法中,节点完全分布式操作,不需要交互任何信息,例如基于概率和基于位置信息的算法,这些算法受网络拓扑变化的影响很小。但是非基于状态的广播算法在节点密度高的网络中广播冗余较大[14]。

结合现有算法,文章提出基于邻居度的动态概率广播抑制算法——DBB。DBB是一种非基于状态信息的广播算法,该算法利用节点密度调节广播转发的概率和时延,解决传统概率算法在高密度网络中广播冗余高、性能下降的问题,针对稀疏网络设计的缓存策略解决网络分裂问题。DBB算法可以应用在各种节点密度的网络环境中。DBB是一种完全分布式的算法,不需要在节点间交互任何信息,也不需要改变路由协议的数据格式,和路由协议的松散耦合使算法应用灵活,具有很强的适用性。

3　算法及协议

AODV(Ad hoc on Demand Distance Vector)是MANET中经典的按需路由协议,协议通过广播建立路由。AODV缺少对广播的有效控制,存在广播冗余和冲突,影响了协议的性能。把DBB算法应用在AODV的路由寻找阶段,减少广播冗余和冲突。

本节先介绍DBB算法,然后设计AODV-DBB协议。

3.1时延和概率初始化

广播冗余和冲突与局部范围内的节点密度有较大关系。在节点发送半径不变的情况下,节点密度越大,一次广播所覆盖的节点越多,相应转发广播的节点就越多,广播冗余和冲突也越多。可见,局部范围内节点的密度对广播冗余和冲突影响很大。DBB算法用节点密度调节转发广播的概率和时延,通过概率和时延机制来减少冗余,降低冲突。

节点在收到广播之后并不立即转发,而是根据感知到的邻居数初始化一个随机时延定时器,此定时器到期之后再决定是否转发。为了使节点在转发广播的时间上相互避开,定时器的时间和节点感知到的邻居数正比,节点的邻居数越多,那么局部范围内转发广播的节点就越多,冲突的概率就越大,时延定时器应该设置越长。

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

(1)

式(1)设计了时延和节点密度的指数关系,使时延随网络密度平缓变化。其中,Ti是节点i的时延定时器,DL是节点i的一跳邻居数,DG是网络中节点一跳邻居数的最大值,t是区间[0,10-3]内的一个随机数,用来调节定时器的时间在一个合适的数量级。

由式(1)可见,节点的一跳邻居越多,广播的时延越长,在较长的时间内分开各节点转发的广播,从而避免碰撞。式中DL和DG是参数,节点可通过探测和感知获得参数DL的数值。而DG是一个实验数值,在具体的网络环境中可通过实验的方法获得。

为此,对几个具体网络的场景进行仿真,获得的参数值和相应的计算结果如表1所示。在一定的区域内分布的节点,节点感知到的邻居数为DL,网络中的最大一跳邻居数为DG,由式(1)计算得到时延为Ti,转发的概率为Pi,概率计算如式(2)所示。例如,当50个节点分布在500*500的区域内,节点的一跳邻居数DL为6,而网络中最大的密度值DG是8,由此计算得到节点的时延Ti为52*10-5s。

表1　不同环境下的网络参数值

DBB算法利用概率减少广播冗余。节点在转发广播之前,根据邻居数来初始化一个概率,各节点根据此概率来决定是否转发广播,从而降低广播冗余。概率初始化如式(2)所示:

(2)

式(2)设计了节点密度和转发概率的指数函数关系,使概率随接单密度值缓慢变化。其中Pi是节点i的转发概率,DL和DG如前文所述。可见,广播转发的概率反比于节点的邻居数,节点的一跳邻居越多,节点的转发概率越小,一跳邻居越少,转发概率越大。

3.2定时器和概率的更新

节点初始化得到的转发时延和概率只与节点的邻居数有关。而在等待时延定时器的过程中,节点应该根据广播转发情况动态地调整时延和概率。

在等待定时器的过程中,节点监听其他节点的广播转发情况,如果其他节点已经转发了这个广播,为降低冗余,节点应该降低转发的概率,并延长等待时延。如果很多个节点都已经转发了同一广播数据,那么节点可以考虑抛弃此广播。

节点要根据网络中其他节点的广播情况动态更新自己的概率和时延。时延定时器更新如式(3)所示:

Tk+1=Tk×NR

(3)

其中Tk+1是计时器的下一个等待时间,NR是节点在上一个等待时间Tk内收到的重复RREQ总数。可见,定时器的更新时间和节点收到的重复RREQ数有关,收到的重复包数越多则等待时间越长。

在节点密度较大的网络中,发送的广播包数可能较多,为防止出现定时器无限等待,设置两个参数,一个是超时计数器(Timer Counter,TC),另一个是超时次数门限(Waiting Threshold,Wth)。超时计数器TC用来计量节点达到定时器的次数,超时次数门限Wth用来对超时计数器进行限制,是超时计数器的最大值。当定时器多次超时到期,即超时计数器达到超时次数门限时,节点将取消定时器,并抛弃广播包。其中Wth是一个手工预设的参数,其需要依据网络密度来进行设置,在密度较大的网络中,Wth应设置为较高,在密度较小的网络中应设置为较低。

转发概率的更新如式(4)所示:

(4)

Pk+1是更新后的转发概率,Pk是更新前的转发概率,NR是节点在上一个定时器时间内收到的重复包数。可见,节点收到的重复包数越多其转发变得概率越小。已被转发的广播越多,后边节点转发广播的概率越小,减少了重复的广播数。

3.3稀疏网络的优化

在节点密度较低的稀疏网络中,由于节点的移动很容易出现网络暂时分裂的情况,此时网络不能全联通,传统的广播算法将失败。

如图1所示,节点S发起向D的路由,但是由于网络在节点1和节点2处发生分裂,节点1没有中继节点,广播将失败。广播失败尤其对按需路由协议影响更大,将使寻路失败,从而引起新的寻路广播,浪费了信道资源。

图1　网络分裂

DBB算法针对稀疏网络设计了广播延长缓存策略。如果节点1只有一个邻居节点,而且这个节点又是广播的发送节点,这说明节点1没有中继节点。此时,那么节点1将RREQ在缓存中延长一个等待时间,以防止RREQ过期。如果在等待的时间内节点1有了其他邻居作为中继,则节点以百分之百的概率转发此RREQ;否则丢弃此广播。

缓存延长的时间可根据节点的移动速度进行设置。节点的移动速度越快,说明网络拓扑很快,那么网络分裂愈合的速度就越快,那么缓存延长的时间就越短,否则可延长缓存时间。

3.4AODV-DBB协议

AODV-DBB在AODV的基础上添加了DBB广播算法,算法主要对AODV中的寻路广播进行优化。运行AODV-DBB协议的节点,收到其他节点广播的路由请求后,如果没有到目的节点的路由,根据DBB算法得到初始化的时延和概率,并且根据时延定时器期间收到的广播数动态调整。

如图2所示的网络拓扑,网络中节点运行AODV-DBB协议,节点S寻找到目的节点D的路由,它广播RREQ,其一跳邻居节点1、2、3、4和R1都第一次收到此RREQ包,然后它们开始运行DBB算法。首先各节点初始化定时器,得到一个随机转发的时延Tk。假如节点R1的定时器最先到期,这时节点R1根据初始化的概率Pi转发此广播包。节点2和节点4收到R1转发的重复RREQ,而节点5、6和节点R2第一次收到此RREQ。节点2和节点4再次执行DBB算法更新定时器和转发概率,定时器将延长,概率将减小。节点5、6和节点R2第一次收到R1转发的RREQ,初始化定时器和转发概率。同样假如节点R2的定时器先到期,其将以初始化的概率转发广播。最后,网络运行DBB算法形成源节点到目的节点的路由为S→R1→R2→D。

图2　DBB算法广播转发

网络中的节点2、4、5和6都收到了重复的广播,这些节点根据DBB的更新算法延长定时器并降低转发的概率,从而减少重复的广播数,降低广播冗余。

4　仿真分析

文献[6]中的HPC算法在目前广播算法中比较有代表性,本节在Qualnet仿真平台上分别实现HPC算法和DBB算法,对两个算法的性能进行比较和验证。鉴于AODV路由协议应用和研究的广泛性,我们在AODV的基础上,分别验证DBB算法和HPC算法的性能。

算法的性能主要通过以下两个指标反映:广播冲突数和广播重播数。AODV中的广播数据主要是路由建立阶段的RREQ,所以这里考察RREQ的冲突数和RREQ的传播数。

RREQ冲突数:表示网络中由于碰撞而发送失败的广播数。该指标验证DBB算法中的时延机制,好的广播算法应该能够通过随机时延来避免碰撞,提高广播的成功率。该指标越低越好。

RREQ传播数:表示网络中节点广播的所有广播。该指标可以验证DBB中概率算法,好的广播算法应能在保证覆盖率的前提下减少广播的传播数,降低广播冗余度。该指标越低越好。

为公平比较DBB算法和HPC算法的性能,仿真环境的设置基本与文献[6]保持一致,DBB算法的Wth参数设置为3。其他设置如表2所示。

设置两个场景对协议进行仿真:

场景一:不同节点密度下的协议仿真,考察协议在不同节点密度下的性能。本场景中,在1000*1000m2的范围内,节点数从30个增加到200个。应用层设置20对CBR流,流量为每秒8个数据包。每个数据点仿真20次取平均值,广播冲突结果如图3所示,广播传播结果如图4所示。

表2　仿真参数配置

图3　不同密度下RREQ广播冲突数

图4　不同密度下RREQ广播数

图3是不同节点密度下的RREQ冲突对比图,横坐标是网络中的几点数,纵坐标是RREQ广播的冲突数。当点数增多时,三个协议的RREQ广播冲突数都增加,但DBB最低,HPC稍好于AODV。随着节点数增多,在节点的发送半径不变的情况下,一次广播所能覆盖的节点增多,被转发的广播数增多。AODV由于缺少有效的冲突避免机制,冲突数最多;HPC的计数器和时延策略降低了冲突,其冲突数要少于AODV,DBB的广播冲突数最少。DBB算法的时延策略考虑了节点密度带来的影响,能使相邻节点转发广播的时间避开,有效减少广播的冲突数量。即使在节点密度很高时,其依然能有效避免广播冲突。在节点密度较高时,AODV-DBB比AODV减少了约35%的广播冲突,比AODV-HPC减少了约20%。

图4是不同节点密度下网络中发送的RREQ对比图,横坐标是节点数,纵坐标是RREQ传播数。随着节点密度的增大,不同协议下的RREQ广播数都增多。在节点数较少时,三个协议的RREQ传播数相差不大,DBB发送的广播最少,HPC稍好,AODV发送的广播最多。当节点数较多时,三个协议发送的广播数差异显著。AODV由于没有广播控制,其网络中发送的广播数最多;AODV-HPC的计数器策略一定程度上降低了广播冗余,其发送的广播数比AODV稍好,但当网络密度较高时,其发送的广播数依然很多;AODV-DBB根据节点密度变化调整广播发送的概率并动态调整,大幅减少了重复发送的广播数。其发送的广播数最多时比AODV和AODV-HPC分别少50%和30%。

场景二:不同网络负载下的协议仿真,考察协议在不同网络负载下的性能。通过改变应用层CBR流的连接数来调整网络负载,CBR连接数从1变化到40,CBR的源节点和目的节点随机选择。这里选择较大节点密度的网络环境,节点数设置为150。节点移动速度为20m/s,使网络拓扑变化相对频繁。其他参数设置不变。仿真结果如图5和图6所示:

图5　不同连接数下的广播冲突数

图6　不同连接数下的广播发送数

图5是不同负载下的广播冲突对比图。随着连接数的增多,网络负载加大,各协议的广播冲突数都增多,但是DBB算法其冲突数始终最少,尤其在网络负载较大时冲突数显著少于其他算法,其冲突数最多较HPC算法减少18%。

随着网络流量增大和网络拓扑变化,路由协议的寻路广播显著增多。DBB算法中,当节点在定时器期间收到重复广播数时,会根据算法动态调整广播的时延,尤其当广播增多时,节点会延长定时器的时间,有效避开了相邻节点间转发广播的时间,降低了冲突。当节点收到的重复广播数过多,定时器超时达到门限值,节点将抛弃此广播,减少了广播冲突数。

图6是在不同负载下网络中发送的广播数,可以看到,不同协议下的RREQ广播数都随着负载的增大而增多。当负载增大时,由网络拓扑变化引起的寻路广播显著增多,但AODV-DBB协议的广播冗余度都低于AODV-HPC和AODV。

在当前网络节点密度较高的情况下,DBB算法根据网络节点密度调整转发的概率,对降低广播冗余效果显著;另外,当广播增多时,其根据广播数动态调整转发概率降低了冗余度,始终把广播数控制在较低值。最优时DBB的广播冗余度比AODV和HPC分别低约35%和20%。

5　结语

广播算法的研究对改善路由协议的性能具有重要意义。本文提出一种新的基于邻居度的广播抑制算法——DBB算法。该算法利用邻居度来初始化广播转发的时延和概率,并根据收到的重复广播数动态更新,避免冲突和减少冗余。在Qualnet仿真平台上对算法进行仿真,仿真结果表明,基于DBB算法的AODV-DBB协议,其广播冲突和冗余度都显著低于其他协议,在网络密度较大和负载较高时优势尤其明显。结合针对稀疏网络设计的广播缓存策略使协议适用于各种节点密度的网络环境。

DBB算法完全分布式运算,没有占用额外的信道资源,没有对路由协议的数据格式进行修改,与路由协议的松散耦合使协议的应用更加灵活,算法具有较强的适用性

下一步期望建立理论模型,在理论上对分布式广播算法进行建模研究,为仿真研究提供理论支撑。

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

国防信息学院科研课题项目(编号:KYKT-155074)资助。

张岱臣,男,硕士,讲师,研究方向:无线自组织网络协议、负载均衡。张红,男,硕士,讲师,研究方向:无线网络、网络通信。

TP915

10.3969/j.issn.1672-9722.2016.08.024