面向高速场景的基于路径连通概率路由协议*

尹鸿坦

(黄淮学院信息工程学院,河南 驻马店 463000)

面向高速场景的基于路径连通概率路由协议*

尹鸿坦*

(黄淮学院信息工程学院,河南 驻马店 463000)

有效地传输数据是提高车联网VANETs(Vehicular Ad Hoc Networks,)应用性能的关键。而动态的拓扑结构,给VANETs的数据传输提出了挑战。为此,提出基于路径连通概率的车联网路由算法CPR(Connected Probability-Based Routing)。首先,依据高速公路场景,建立一维车辆移动模型,然后再计算链路的连通概率,最后,计算路径的连通概率,并选择连通概率最高的路径传输数据。仿真结果表明,提出的CPB算法能够有效地提高数据包传递率、端到端传输时延以及吞吐量性能。

连通概率;路由;移动模型;车联网

目前,汽车已成为民众出行的首选交通工具,汽车便捷民众的日常出行。然而,随着汽车数量的增加,道路拥塞、交通安全问题也日益突出。据不完全统计,交通事故已成第2大杀手。世界卫生组织WMO指出每年约130万人死于交通事故,约5 000万人受伤[1]。据此,政府部门以及科研机构开始商讨、并提出利用智能交通概念,提高交通安全。作为智能交通系统的最有前景技术,车联网 VANETs(Vehicular Ad Hoc Networks)受到广泛关注。

典型的车联网结构如图1所示。装有OBU模块的车辆能够与其他车辆、路边设施进行通信。其中车与车之间的通信称为车间通信V2V(Vehicle to Vehicle),而车与路旁设备通信称为车-旁通信V2R(Vehicle to Roadside unit)。车辆间通过实时交互路状信息,实现对事故的预警以及避让,进而提高交通管理效率以及交通安全。据美国交通局统计,通过车联网技术平台,能够将交通事故率降低82%。

图1 VANET的网络模型

从技术层面而言,车联网VANETs属于移动自组织网络,但VANETs具有鲜明的特性,如动态的拓扑、受限的移动模型、车辆的高速移动。这些特性给VANETs的消息传输提出了挑战。据此,众多研究学者关注VANETs中的路由技术[2-5]。

值得注意得是,车辆移动受限于道路的拓扑结构,并且道路的拓扑结构是静态,至少在短时间内道路结构是不会变化,这一特性给车辆移动预测提供了基础。通过对车辆移动的预测,可有效地计算链路的连通特性,包括连通概率、连通持续时间等。

文献[6]提出基于链路连接概率的路由协议。先计算链路连接概率,并由此估算链路连通时间,从而选择最稳定、可靠的路径作为数据传输通道。文献[7]提出面向高速道路场景的车辆移动预测模型。此外,文献[8]也提出基于移动预测的MOPR路由协议。MOPR协议先预测车辆的下一时刻位置,然后再估算数据传输至此位置所需的时间。随后,检测链路在数据传输时间内是否一直保持连接状态。

本文基于上述文献的分析,考虑到VANETs的移动区域局限性、移动信息的可预测性,提出基于路径连通概率的VANETs路由算法CPB。CPB算法通过路径连通概率决策路由,提高路由应对动态拓扑的鲁棒性。

1 网络模型

以高速公路为研究对象,并建立相应的网络模型。依据IEEE802.p的标准,车辆的一跳通信半径为300 m,其远大于道路宽度。据此,可将高速公路场景模拟成一维的网络模型。

在高速公路的场景中,车辆驶入公路服从泊松分布[9]。假定泊松分布的参数为λ,那么在时间[0,t]范围内,有m辆车驶入道路的概率Pr:

(1)

式中:N(t)在时间[0,t]驶入公路的车辆数。

当公路上有多辆车时,车与车之间的间隔服从指数分布,且参数为α。假定第i个间隔为Ti,那么在时间[0,t]内可容纳的间隔数为M(t),且M(t)服从参数为αt的泊松分布。

对于个体车辆υk,它以vi,k速度在第i个间隔Ti,k内移动。车辆υk所移动的距离Si,k=vi,k×Ti,k。因此,在时间[0,t]内,车辆υk移动的距离Sk(t):

(2)

依据统计学知识,Sk(t)服从复合泊松过程[10]。相应地,它的均值、方差可依式(3)、(4)计算。

E[Sk(t)]=αtE[Si,k]=μt

(3)

(4)

为了简化描述,根据中心极限定理[9],将Sk(t)分布视为正态分布。在道路中,车辆间的状态可通过其观察车辆进入道路时间差进行描述。仍假定车辆υk,其观察车辆进入道路的时间为t,并且它们进入道路的时差为τ。

若τ大于零,则意味着观察车辆先进入道路,若τ小于零,则说明观察车辆后进入道路。据此,Sk(t+τ)等于在时间[0,t]内车辆υk所移动的距离,且服从正态分布,其中均值、方差分别如式(5)、式(6)所示:

E[Sk(t+τ)]=μ(t+τ)

(5)

(6)

利用车辆υk与观察车辆所移动距离差,表征它们的相对距离,即Dr=S(t+τ)-S(t)。它的均值、方差如式(7)、式(8)所示:

E[Dr]=μτ

(7)

(8)

(9)

2 CPB协议

CPB协议旨在提高网络连通率,保证数据传输传递率。为此,CPB协议先计算节点间的连通率(链路连通率),然后再计算路径连通率,最后选择路径连通率最高的路径传输数据包。整个CPB协议工作流程如图2所示。

图2 CPB协议建立数据传输路径

2.1 连通概率

当源节点(车辆)需要向目的节点传输数据时,源节点首先需要计算自己与下一跳节点间连通概率,换而言之,选择连通概率最高的节点作为下一跳转发节点。

图3 在建立链路时期内的两跳间接通信

如图3所示,源节点A与目的节点C均沿着左向右行驶。假定节点A、B和B、C间距离表示为dAB、dBC。相应地,dAC表示节点A、C间的距离。如果距离dAC小于通信范围R,则直接通信。反之,节点A需要选择下一跳节点作为转发节点。接下来,以图3为例,分析选择下一跳节点的过程。

若节点A在时刻t=0进入系统,而在时刻t=t1节点A的位置为x,且x∈[-2R,2R]。此时节点A与目的节点C构建了数据传输路径。由于它们彼此不在一跳邻居通信范围内,需要通过中间转发节点进行转发数据。转发区域如图3所示的阴影区域,即在[-R,x+R]区域为它们的转发区域[11]。若在该区域内存在节点,则这些节点可成为转发节点。

接下来,估计转发区域内的节点(车辆)进入[-R,x+R]区域的时间,与目的节点C的时间差为τ的概率Pτ1(x),即在t=t1时刻建立连通的概率。依据式(9),可计算Pτ1(x):

(10)

由于车辆驶入时刻t服从(-t1/2,t1/2)区域的均匀分布。如果τ∉(-t1/2,t1/2),则意味着车辆在时刻t=t1驶入区域[-R,x+R]的概率太小,换而言之,区域[-R,x+R]内没有节点能与目的节点C建立连通。在这种情况,源节点A只能采取存储-转发策略,直至转发区域内有节点才进行转发。

当然,或许在时刻t=t1有m辆车驶入道路。在这种情况下,任意一辆车出现在[-R,x+R]的区域的概率

(11)

依据式(11)可知,在区域[-R,x+R]内无任何车辆的概率可表示为1-Pt1(x)。

(12)

exp(-λtPt1(x))

(13)

最后,将式(13)代入(12)便可计算连通概率:

(14)

2.2 路由决策

提出的CPB算法是以选择连通概率最高的路径为原则进行路由决策。当源节点需要传输数据时,首先计算每条通往目的节点路径的连通概率[12],然后从中选择概率最高的路径作为数据传输通道。

对于每一条路径(假定为路径l),若该条路径Pathl由n条链路组成。而每条链路的连通概率表示为Ph(h=1,2,…,n)。据此,整条路径Pathl的连通概率:

(15)

最后,源节点选择连通概率最大的路径作为数据传输通道。

图4 路由发现流程

2.3 路由发现流程

当节点需要传输数据包时,节点就先邻居广播请求数据包RREQ。一旦接收了RREQ包,节点就先判断是否之前已接收了RREQ,若是,则丢弃,否则,就依据式(14)计算连通概率,并加载到RREQ,再转发。重复上述过程,直到目的节点接收了RREQ包。目的节点可能接收了来自多条路径传输的RREQ包。为此,目的节点依据式(15)计算每条路径的连通率,再选择连通率最大的路径作为数据传输通路。然后,目的节点依据所选择的路径回复ACK。当源节点接收了ACK后,再依据此路径向目的节点传输数据包。整个路由发现流程如图4所示。

以图5为例,描述CPB协议的路由决策过程。源节点A首先发送路径请求消息Mes_req。接收节点B先计算与节点A的连接概率,再将此概率值载入Mes_req,并转发。每个接收节点均重复上述过程,直到目的节点F接收到此消息Mes_req。

图5 路由选择过程

由图5可知,由{A→B→C→E→F}、{A→B→D→E→F}两条路径到节点F,并且这两条路径的连通概率PPathl分别为0.028 8、0.048 0。这表明路径{A→B→D→E→F}比路径{A→B→C→E→F}的连接时间更短,路径更趋于稳定。因此,节点F选择路径{A→B→D→E→F},并沿着该路径的反方向向源节点A回复ACK消息,如图5(b)所示。

3 性能分析

3.2 仿真场景

为了更好地分析CPB路由性能,利用NS2.35建立仿真平台。考虑长为L=4 000 m的三车道的高速场景,车辆的通信半径为300 m,如图6所示。具体的仿真参数如表1所示。

图6 高速公路仿真场景

参数数值公路长度4000m车道数3最小车速40km/h最大车速120km/h车辆通信范围250m仿真时间100s

在仿真过程中,选择VADD[13]和AODV[14]路由算法作为参考,并与CPB算法进行比较。AODV路由是经典的车联网路由协议,而VADD路由也是以提高数据传输率为目的路由协议。这两个路由与CPR路由具有可比性。此外,从吞吐量、数据传输的端到端传输时延以及数据包传递率3方面分析路由算法的性能。

3.2 数值分析

接下来,分析车辆速度对端到端传输时延(E2E)、吞吐量(Throughput)以及数据包传输率的影响。其中,端到端传输时延是指数据包从源节点传输至目的节点的平均时延;而数据包传输率是指数据包传输成功率,其等于目的节点所接收的数据包数;吞吐量是指单位时间内网络内所传输的数据量。

实验以随机方式产生数据包源节点(车辆)和目的节点(车辆),并考虑变化车速对路由协议性能的影响。

①端到端传输时延

平均速度越高,端到端时延越大。原因在于车速的提高,加剧了拓扑结构的动态变化,降低了路径的连通率,使得路由不稳定。最终,增加数据包传输时延。

从图7可知,相比于AODV和VADD路由算法,CPB算法的时延得到有效地缩减。例如,当平均车速在70 km/h时,CPB的端到端时延约为3 s,而VADD和AODV时延分别为3.5 s和4.75 s。这归功于CPB算法依据路径的连通率决策路由,避免了连通率低的路径作为数据传输,提高了路由的稳定性。而AODV和VADD发现路由时并没有从路由稳定性角度出发。对于拓扑变化的车联网而言,路由的不稳定性是制约路由性能的关键因素。

图7 平均时延随平均车速的影响

②数据包传递率

数据包传递率随车速变化情况如图8所示。平均车速越大,数据包传递率越低。原因在于,车速的提高了,加速了网络拓扑的动态变化性,最终导致路径不稳定,进而降低了数据包传输率。与AODV和VADD路由相比,CPB路由数据包传递率得到有效地提高。例如,在平均车速在80 km/h时,CPB路由的所接收的数据包数达到43,而AODV协议只有32个。

图8 数据包传输率随车平均速度的变化

③吞吐量

最后,分析了车速对吞吐量的性能影响,实验数据如图9所示。从图9可知,吞吐量随车速的增加而下降。这主要是因为车速的提高,增加传输时延,降低了传输效率,同时,又减少了数据包传递率,最终导致数据吞吐量的下降。然而,由于CPB路由算法依据路径连通率选择路由,提高了应对动态拓扑变化的能力。

图9 吞吐量随车平均速度的影响

图10 平均路由开销随车平均速度的影响

④路由开销

最后,利用路由开销反映算法复杂性。路由开销越大,说明路由算法越复杂。路由开销是每接收一个数据包所产生的控制包个数。从图10可知,CPB的路由开销低于AODV路由协议,但高于VADD协议。原因在于:CPB路由协议在发现路由时,采用了请求包和控制包,这增加了路由开销。

4 总结

本文针对车联网的数据传输问题,提出基于路径连通概率的路由算法CPB。CPB算法考虑了车辆的高速移动对路由稳定性的影响。CPB算法计算链路的连通率,并估算路径的连通概率。在决策路由时,总是选择连通概率最高的路径作为数据传输通道,进而提高数据传输效率。仿真结果验证路由算法的性能。与AODV和VADD路由算法相比,CPB路由算法的端到端传输时延、吞吐量以及数据传递率性能均得到有效地提高。

[1]Casteigts A,Nayak A,Stojmenovic I. Communication Protocolsfor Vehicular Ad Hoc Networks[J]. Wireless Communication Mobile Computer,2011,11(5):567-582.

[2]Shafiee K,Leung V C M. Connectivity-Aware Minimum-Delay Geographic Routing with Vehicle Tracking in VANETs[J]. Ad Hoc Networks,2011,9(2):131-141.

[3]Biswas S,Morris R. ExOR:Opportunistic Routing in Multi-Hop Wireless Networks[C]//Proc ACM SIGCOMM,2012:133-144.

[4]徐子豪,张腾飞. 基于语音识别和无线传感网络的智能家居系统设计[J]. 计算机测量与控制,2012,12(1):12-18.

[5]周凯,孟利民,华惊宇. 基于Grover路由策略的无线传感网络剩余容量构造与研究[J]. 传感技术学报,2015,28(2):249-253.

[6]Li Y,Chen W,Zhang Z L. Optimal Forwarder List Selection in Opportunistic Routing[C]//Proc IEEE MeshTech,2010:670-675.

[7]Namboodiri V,Gao L. Prediction-Based Routing for Vehicular Ad Hoc Networks[J]. IEEE Transactions on Vehicular Technology,2012,56(4):2332-2345.

[8]Menouar H,Lenardi M,Filali F. A Movement Prediction Based Routing Protocol for Vehicle to Vehicle Communication[C]//Proc V2VCOM,San Diego,CA,Jul. 2015:75-82.

[9]Hafeez K,Zhao L,Liao Z,et al. Impact of Mobility on VANETs’ Safety Applications[C]//Global Telecommunications Conference(GLOBECOM 2010),2010 IEEE,Dec. 2010:1-5.

[10]Zhao M,Li Y,Wang W. Modeling and Analytical Study of Link Properties in Multi-Hop Wireless Networks[J]. IEEE Transactions on Communications,2012,60(2):445-455.

[11]王佩雪,罗菁. VANETs中基于链路的可持续时间路由方案[J]. 科学技术与工程,2014,14(25):267-272.

[12]张莉华,张得生. 基于连接概率的VANETs路由协议研究[J]. 现代电子技术,2016,39(7):19-24.

[13]Zhao J,Cao G. VADD:Vehicle-Assisted Data Delivery in Vehicular Ad Hoc Networks[J]. IEEE Transactions Vehicular Technology,2011,57(3):1910-1922.

[14]Xia Zijun,Liu Chunfeng,Zhao Zenghua. Routing Algorithm in Vehicular Ad Hoc Network Based on Link Prediction[J]. Computer Engineering,2012,38(4):110-114.

Connected Probability-Based Routing for HighwayScenario Vehicular Ad Hoc Networks*

YINHongtan*

(College of Information Engineering,HuangHuai University,Zhumadian He’nan 463000,China)

To transmit effectively data is key issue of improving the application performance of Vehicular ad hoc networks(VANETs). However,dynamic topology is great challenge for transmitting data. Therefore,Connected Probability-Based routing(CPR)was proposed in this paper. Firstly,according to highway scenario,the one-dimension vehicle mobile model was established. Secondly,the connected probability of link was estimated. Finally,the connected probability of path was computed,and the path with maximum connected probability was selected to transmit data. Simulation results show that the proposed CPB algorithm has better performance in terms of packet delivery ratio,end-to-end delay and throughput.

connected probability;routing;mobility model;VANETs

尹鸿坦(1987-)，男，河南汝南人，硕士，研究方向为云计算，大数据。

项目来源:河南省科技厅项目(162102110119);国家自然科学基金项目(51406140)

2017-01-18 修改日期:2017-05-05

TP393

A

1004-1699(2017)08-1281-06

C:7230

10.3969/j.issn.1004-1699.2017.08.025