基于拓扑连通概率的车载自组织网络路由算法

陶 军 肖 鹏 刘 莹 陈文强

(东南大学教育部计算机网络和信息集成重点实验室,南京210096)

近年来,各国学者提出了多种VANETs路由算法.其中,基于概率的路由算法从报文接收概率的角度进行分析,有效提升了路由算法报文的投递率和下一跳选择的正确性.文献[1]按照节点的接收概率选择下一跳路由,提出了REAR算法;文献[2-3]基于节点移动参数,建立了概率模型以预测连接持续时间,从而在全局情况下建立和维护路由;文献[4-5]依据节点间的距离计算彼此的连通概率,提出连通感知路由算法CAR.REAR算法能够有效传输数据包,其投递率和使用包的数量也在接受范围之内[6-7].该算法的缺点在于:① 竞争延迟函数的选取不能反映网络拓扑的变化;② 缺乏有效的广播风暴抑制机制;③ 邻居概率之和的计算方法过于繁琐.

针对REAR算法存在的不足,本文在竞争延迟函数的参数、广播报文的传播时间、数据报文的广播次数以及下一跳节点的判断依据等方面进行了修改,提出了一种基于拓扑连通概率的车载自组织网络路由算法——RPR算法.然后,从覆盖率、辅助报文数量和结束时间等3个方面对REAR算法和RPR算法进行了比较.

1 网络模型

REAR算法中,每个节点都会维护一张邻居列表,列表中的内容包括邻居的位置、速度、方向、接收概率以及该节点的生存时间等.每个节点定期通过HelloBeacon数据包向自己的邻居广播上述信息.每个节点收到其他节点的数据包之后,如果此数据包是一个HelloBeacon数据包,则将其更新到邻居列表中;否则根据自身情况进行广播.节点的初始状态是空闲状态,收到数据包之后便会进入竞争状态,随后再进行数据包转发.如果一个节点收到新数据包时正处于竞争状态,则此节点取消自己的竞争状态,并且放弃自己将要转发的数据包,重新进入竞争状态,等竞争状态结束后再转发新的数据包.具体的转发流程见图1.

图1 REAR算法状态转换图

节点处于竞争状态的时间是根据节点邻居的接收概率来确定的.如果一个节点邻居的接收概率较高,则会较早地从该节点转发数据包.因此,在REAR算法中，给出一个根据邻居接收概率之和计算竞争状态时间的函数,即

fexp=aexp(-∑Pi)

式中,Pi表示节点的单个邻居接收概率,即节点收到其他节点数据的可能性,具体的计算过程见文献[1];a表示任意常量.为了证明算法的正确性,REAR算法的提出者进行了如下假设:

∑Pi=∑Pj+1

其具体物理意义为:一个节点邻居的概率之和与另一个节点邻居的概率之和的差的绝对值等于1.然而,VANETs是一个自组织的网络,车辆之间的间距与邻居都是随机分布的,任意2个节点间不可能存在上述关联,故这个假设在物理上是没有意义的.因此,本文对REAR算法进行了改进.

2 RPR算法

针对REAR算法存在的不足,本文提出了一种新的路由算法——RPR算法.

2.1 广播风暴的抑制

对于广播风暴的抑制可从以下2个方面考虑:① 广播节点.若一个节点广播了某个数据报文,则在一段时间内它将不再对此广播报文进行传输.② 数据报文.为了防止一个广播报文在VANETs中被反复广播,本文为报文添加了一个生存时间(TTL)[8].中间节点在转发该数据包时,需要对TTL进行判定.如果TTL已经为0,则不再转发此数据包;否则,需要在转发该数据包之前将TTL减少1.

2.2 邻居概率之和的计算

由文献[1]可知,利用REAR算法计算邻居概率之和的算法过于繁琐,并且带来了一些负面效应,如计算量过大、部分数据不能够反映路由的真正走向等.此外,REAR算法需要同时考虑上一跳节点和下一跳节点的接收概率,导致不能够正确选择下一跳节点.在本文算法中,节点只计算下一跳节点的接收概率,减少了不必要的运算,从而提高了算法的效率.

2.3 延迟函数的假象条件

REAR算法提出了延迟函数的定义,但该函数的证明存在问题.本文只需要修改函数的参数,使得函数中任意2个参数值之差的绝对值大于等于1即可.令Ri,j为节点j在节点i的邻居中的排名信息,并将Ri,j作为延迟函数的参数.排名的依据是节点的接收概率之和:节点的接收概率之和越大,节点的排名越小.

对于任意一个节点vi,当其收到邻居发出的HelloBeacon数据包时,便可获得所有邻居的接收概率.将这些接收概率排序后广播出去,则vi的所有邻居便能获取自身的排名信息.任意2个节点的排名信息是不相同的,且排名信息是一个整数,故其满足延迟函数参数的要求.此外,排名信息的另一个优势在于:一个节点的邻居数量是有限的,故任意2个邻居的排名信息的差值也是有限的,从而导致任意2个节点的竞争延迟时间的差值较小,即可有效减少节点等待的时间.

3 仿真实验

对本文算法进行了覆盖率、辅助报文数量和结束时间等方面的性能分析,并将其与REAR子集算法、REAR全集算法进行了对比.此处,覆盖率是指模拟结束后收到广播报文的节点与总节点的比值;辅助报文数量是指整个广播过程中使用的报文数量[9];结束时间是指达到指定覆盖率所需的时间.

3.1 场景设置与描述

本文采用了一段直线道路场景(见图2),道路长度为6 km.为了使实验中的车辆不局限于两侧,减少边界效应的发生,本文主要研究了2～4 km范围内车辆承载算法的运行状况.因此,在运行算法的初始阶段,0～2 km和4～6 km段道路上没有车辆;随着算法的运行,车辆向两边扩散并趋于稳定.假设场景中的车辆总数为n,车辆速度在20～30 m/s内随机分布,平均速度为25 m/s.通过计算可以得到,当车辆到达2～4 km时,其分布满足泊松分布,车辆密度λ=n/80.车辆的无线信号覆盖范围为250 m.为了消除随机性,选择2 000组数据的平均值作为最终结果.节点个数分别为40,50,60,70,80,90,100,110,120,130,140,150,160.算法运行时间为50 s.

图2 模拟场景(单位：km)

3.2 结束时间与节点密度

由于实验中覆盖率很难达到100%,且当节点数量较少时,算法的覆盖率很难达到90%以上,因此下面统计数据中的辅助报文数量[9]和结束时间是覆盖率达到80%的数据.

图3为结束时间与节点数的关系曲线.由图可知,RPR算法和REAR算法的收敛速度都较快.在不到1 s的时间内,2种算法均达到了80%的覆盖率.此外,RPR算法在结束时间方面的优势是十分明显的,其原因在于:RPR算法使用的是排名信息,节点之间的竞争延迟相差不明显;而REAR算法则将邻居的概率之和作为参数,该变量的最大值和最小值之间的差距较大,在对比数据中,最大甚至达到500∶1,这一时间差距对于最终的时间延迟会产生较大的影响.通过计算可得,RPR算法的传输时间缩短至REAR算法的72%.

图3 结束时间与节点数的关系

3.3 节点覆盖率与节点密度

图4为覆盖率与节点数的关系曲线.从图中可以看出,RPR算法的覆盖率较REAR算法稍有提升,从原来的93%提升至99%.这是由于在计算邻居概率之和时,REAR算法同时计算了下一跳节点和上一跳节点的累积概率[10],故而无法准确地选择下一跳节点.此外，节点的覆盖率随着节点密度的增大而增加,这是因为节点密度的增大会使每个节点的邻居增多,从而增加了节点被覆盖到的概率.

图4 节点覆盖率与节点数的关系

3.4 辅助报文数量与节点密度

图5为是辅助报文数量与节点数的关系曲线.由于REAR全集算法和REAR子集算法都没有对广播风暴进行控制,故其使用的报文数量较RPR算法明显要多.由图可知,RPR算法使用的广播报文数量减至REAR算法的78%.此外,REAR子集算法和REAR全集算法使用的报文数量相似,因为这两者在辅助报文控制方面进行的约束是一致的.RPR算法中,辅助报文数量减少的原因主要是:① 引入了TTL和广播报文的限制;② 使用排名信息,使得延迟函数的前提条件得到满足,一些不必要的数据报文在转发之前就被取消了.

图5 辅助报文数量与节点数的关系

3.5 覆盖率与时间

节点数为100时,覆盖率随时间的变化情况见图6.由图可知,从1 s开始到模拟结束,覆盖率基本没有改变.其原因在于:车辆之间的数据传输较车辆本身的速度快很多,故在1 s内所有数据已经基本传输完毕.此外,覆盖率增加的主要原因可归结于VANETs的移动性,部分节点在模拟的初始阶段未能与其余节点进行通信,随着车辆的移动以及VANETs拓扑的变化,这些节点进入其余节点的通信范围之内,故而覆盖率得到提高.

图6 覆盖率与时间的关系

4 结语

本文提出了一种基于拓扑连通概率的车载自组织网络路由算法——RPR算法.从覆盖率、辅助报文数量和结束时间等3个方面对REAR算法和RPR算法进行了比较.结果表明,RPR算法可将广播报文数量减少至REAR算法的78%,数据通信时间缩短至原算法的72%,覆盖率则由原来的93%提升至99%.

)

[1]Hao J, Hao G, Li J C. Reliable and efficient alarm message routing in VANETs [C]//Proceedingsofthe28thInternationalConferenceonDistributedComputingSystemsWorkshops. Beijing, China, 2008:186-191.

[2]Yan G Y, Rawat D B, El-Tawab S.Ticket-based reliable routing in VANETs[C]//ProceedingsofIEEE6thInternationalConferenceonMobileAdHocandSensorSystems. Macao, China, 2009: 609-614.

[3]Naumov V, Naumov V, Gross T. Connectivity-aware routing (CAR) in vehicular ad hoc networks[C]//Proceedingsof2007IEEEInternationalConferenceonComputerCommunications. Anchorage, Alaska, USA, 2007: 1919-1927.

[4]Yan G Y, Olariu S, Salleh S. A probabilistic routing protocol in VANETs[C]//Proceedingsofthe7thInternationalConferenceonAdvancesinMobileComputingandMultimedia. Kuala Lumpur, Malaysia, 2009: 179-186.

[5]Karnadi F K, Mo Z H. Rapid generation of realistic mobility models for VANETs[C]//Proceedingsof2007WirelessCommunicationsandNetworkingConference. Washington DC, USA, 2007: 2506-2511.

[6]Abedi O, Fathy M, Taghiloo J. Enhancing AODV routing protocol using mobility parameters in VANETs[C]//Proceedingsofthe2008IEEE/ACSInternationalConferenceonComputerSystemsandApplications. Washington DC, USA, 2008: 229-235.

[7]Namboodiri V, Gao L. Prediction-based routing for vehicular ad hoc networks [J].IEEETransactionsonVehicularTechnology, 2007,56(4): 2332-2345.

[8]Lee Y, Lee H, Choi N, et al. Macro-level and micro-level routing (MMR) for urban vehicular ad hoc networks [C]//Proceedingsof2007IEEEGlobalTelecommunicationsConference. Washington DC, USA, 2007: 715-719.

[9]Korkmaz G, Ekici E, Ozguner F. Black-burst-based multihop broadcast protocols for vehicular,networks [J].IEEETransactionsonVehicularTechnology, 2007,56(5): 3159-3167.

[10]Xu Q, Mak T, Ko J, et al. Medium access control protocol design for vehicle-vehicle safety messages [J].IEEETransactionsonVehicularTechnology, 2007,56(2): 499-518.