基于车联网WAVE的多跳路由连接中断预测算法

王　博，哈力木拉提·买买提

(新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046)

摘　要：当信息源车辆与信息目标车辆之间不能通过一跳来完成信息交互时，车辆间多跳路由连接的建立是保证车联网WAVE中信息源车辆和信息目标车辆之间能够进行信息传递的关键。通过研究和分析快速多跳路由算法FMHR得知，车联网中各节点车辆之间建立起来的多跳路由连接会因各节点车辆之间的速度不匹配而时常发生通信中断，针对这一问题，试着在原有算法中增加路由连接中断的预测方法，并使用支持IEEE 802.11p的开源软件NCTUns-6.0建立相关仿真实验，结果表明，增加路由连接中断的预测方法可改善车辆之间信息传递的效率。

关键词：车联网WAVE；多跳路由；路由连接

doi:10.3969/j.issn.1002-0802.2015.06.015

基于车联网WAVE的多跳路由连接中断预测算法

王博，哈力木拉提·买买提

(新疆大学 信息科学与工程学院，新疆 乌鲁木齐 830046)

摘要：当信息源车辆与信息目标车辆之间不能通过一跳来完成信息交互时，车辆间多跳路由连接的建立是保证车联网WAVE中信息源车辆和信息目标车辆之间能够进行信息传递的关键。通过研究和分析快速多跳路由算法FMHR得知，车联网中各节点车辆之间建立起来的多跳路由连接会因各节点车辆之间的速度不匹配而时常发生通信中断，针对这一问题，试着在原有算法中增加路由连接中断的预测方法，并使用支持IEEE 802.11p的开源软件NCTUns-6.0建立相关仿真实验，结果表明，增加路由连接中断的预测方法可改善车辆之间信息传递的效率。

关键词：车联网WAVE；多跳路由；路由连接

doi:10.3969/j.issn.1002-0802.2015.06.015

收稿日期：2015-02-01；修回日期：2015-05-05Received date:2015-02-01；Revised date：2015-05-05

中图分类号：TP316.8

文献标志码：码：A

文章编号：号：1002-0802(2015)06-0705-05

Abstract：When information source vehicle and target vehicle could not implement direct message exchange, the establishment of inter-vehicle multi-hop routing would become the key to ensuring information exchange of between source vehicle and target vehicle. Research and analysis on HMHR(Fast Multi-Hop Routing) algorithm shows that frequent communication interrupt would usually happen between these vehicles due to their mismatching velocities. In order to solve this problem, the prediction method is tried to add in the original algorithm, and the related simulation experiment with open source tool NCTUns-6.0 which supports IEEE 802.11p,indicates that this prediction method could effectively improve the information transfer of between the vehicles.

作者简介：

Interrupt Prediction of Routing Connection based on

Wireless Access in Vehicular Environment

WANG Bo, Halmuratm

(School of Information Science and Engineering, Xinjiang University, Urumchi Xinjiang 830046, China)

Key words：WAVE (Wireless Access in the Vehicular Environment)；multi-hop routing; routing connection

0引言

由于交通事故导致的逐年上升，世界各国越来越关注交通事故，研究智能交通以达到减少交通事故的目的。车联网作为智能交通的核心，已经成为世界上研究智能交通领域的热点。与车联网有关的新一代无线通信标准IEEE 802.11-2012[1]也亦2012年发布。从美国美国国家航空航天局官方网站得知[2]，世界各大汽车厂商和各国政府也正在积极投入到智能交通各个领域的研究和开发当中。作为新标准的车联网WAVE网络自然成为智能交通中研究的热点问题，而作为车联网核心功能的路由算法也备受到人们的极大关注。

1研究背景

车辆是车联网WAVE的基本单元，具体分为车载单元(OBU)和路边单元(RSU)[3]，车辆在行驶的过程中因某些需求而进行信息数据的交互，由于发送信息的车辆和接收对应信息的车辆间距离较远，发送信息的车辆不能直接把信息数据直接发送到接收该信息的目标车辆，也就是发送信息的车辆与接收信息的车辆之间不能通过一跳直接完成所需信息的交互。此时，发送信息的车辆就需要其他的中间车辆作为传递信息的下一跳来进行信息的传递，从而把需要发送的信息数据发送到接收该信息的目标车辆，即发送信息的信息源车辆与接收该信息的目标车辆之间是通过建立起来的路由连接进行信息交互的。通过研究和分析发现，路由连接中相互通信的节点车辆之间因时常发生中断而影响到信息数据的传递效率。这一问题也存在于快速多跳路由算法FMHR[4-5]中，FMHR是针对802.11p的快速多跳路由算法，FMHR是通过减少信息传递过程中所需下一跳的个数来达到整体减少信息传递开销和提高信息效率的目的。针对这一问题，文章试着给出一种预测路由中断的方法，为了区分于FMHR算法，以FMHR-V表示在原有FMHR算法中加入预测路由中断方法之后的算法名称。

2FMHR算法要点

文献[4-5]通过对Fastest Ferry Routing in DTN enabled VANET(FFRDV)算法的研究，假设①所有车辆上均带有GPS定位系统②目标车辆提前得知③仿真高速公路行车场景，且没有设置障碍物等干扰因素。基于以上假设，作者提出一种新的FMHR算法，结合文献[6]对FMHR的理解，FMHR算法在选择发送信息车辆的时，以时间和距离策略来决定选择信息发送范围内哪个车辆来传递信息，即在发送信息范围内选择速度最大和距离最短的那个车辆来传递信息，直到该信息被传递到目标车辆为止。总体来看，FMHR算法思想有三大步骤，具体如下。

2.1路由创建与保持

信息源车辆IV要向目标车辆DV发送信息数据，首先IV需要定位DV的位置，IV需要通过广播形式向其信息发送范围内的所有周围车辆发送信息传递的请求，每个中间传递信息的车辆都会通过其各自周围车辆来传递信息，直到DV接收到IV发来的信息。当DV接收到由IV发来的定位请求时，DV就利用中间车辆进行应答，直到把该应答信息传递到IV为止。

作为中间车辆，其需要定期通过发送和接收信息数据与其通信的下一个中间车辆之间进行信息交互，保持并不断更新与其相邻的下一个中间车辆的相关信息，比如中间车辆的ID号，只有这样才能保证信息数据成功的在每一个中间车辆之间完成发送与接收。从而，才能保证信息数据从IV到DV。

当车辆间的通信路由发生中断时，都有前一跳的车辆负责路由创建与保持，并不断实时更新路由信息，以此来确保信息数据在每个环节的发送与接收。

2.2下一跳车辆的选择

FMHR通过式(1)来完成下一跳车辆的选择，选择的策略以时间和速度共同决定，式(1)中SNHV表示两个车辆之间的实时距离，VNHV表示车辆之间的实时速度之差，即考虑距离与速度、时间三者之间的关系。比如IV在选择其下一跳车辆NHV时，IV通过各个NHV发回来的ACK信息，提取位置和速度信息，计算出各个时间，如B= {TNHV1,TNHV2…,TNHVn}，然后，比较各个时间值的大小，只选择并保存与最小时间值对应的那个车辆作为IV的下一跳车辆。以此类推，其它中间车辆计算出来的时间也是最小的，这样信息数据从IV到DV的总体时间就可以达到最小。从这个角度讲，信息从IV到DV减小了中间不必要的跳数。

TNHV=SNHV/VNHV

(1)

2.3与下一跳车辆的通信

选择完下一跳NHV之后，接下来的任务就是和NHV之间进行信息数据的交互。IV以最短的时间向NHV发送信息数据，并接收返回信息数据。一旦被选择的NHV接收到信息数据后，该NHV也将执行相同的过程，选择自己的NHV，并把信息数据传递出去，直到信息数据传递到目标车辆DV为止。在与下一跳NHV进行通信的时候，有以下情况需要考虑：

(a)：如果DV在IV的发送信息范围内，那么IV将不再执行选择下一跳的程序，直接把信息数据发送目标车辆DV。当DV接收到信息数据之后，会向IV发送ACK应答信息。

(b)： 如果IV在其发送信息范围内找不到DV，IV将向其所有周围车辆发送得到它们位置和车辆速度的请求信息，然后，根据式(1)计算各自的时间T出来，并存放到IV的缓冲区中，进而通过比较各个T大小，来选择与对应T值最小的那个车辆作为IV的NHV，IV把所要传递的信息数据传递给该NHV。由该HHV根据(a)(b)规则来进行信息数据的传递，直到把信息数据传递到DV为止。

3路由连接中断预测

3.1路由连接中断预测的意义

车辆在实际的行车过程中，对于随机分布在车道上任意两个节点车辆的速度彼此相等的概率是很小的，当两个节点车辆的速度不一致时，路由连接中相互连接的两个节点车辆之间的通信就有发生连接中断的可能，研究路由连接中断的可能性不仅可以提高两个节点车辆之间信息传递的效率，而且对整个信息传递过程中涉及到路由选择有重要作用，通过在路由选择算法中增加路由连接中断的预测策略可改善路由选择算法的性能。

3.2路由连接中断预测算法

路由连接中断发生在各节点车辆之间进行信息传递的过程中，车联网中节点车辆之间进行信息传递的模型如图1所示。

图1　WAVE中节点车辆之间的信息传递模型

图1中t1，t2，t3分别表示三个连续发生且不同的时间点，D(t1)，D(t2)，D(t3)，分别表示t1，t2，t3时间点处任意节点车辆A和车辆B之间的距离，且假定Va< Vb，意在说明车辆A和车辆B的速度不一样，因此，车辆A和车辆B之间的距离将越来越大，即D(t1)

T(21)=t2-t1

(2)

T(32)=t3-t2

(3)

(4)

Rest(d)=R-D

(5)

T=Rest(d)/Vx-y

(6)

Vx-y=Vx-Vy

(7)

通过对以上分析，结合FMHR算法思想，分别在信息源车辆A和其下一跳车辆B两端增加路由连接中断的预测，车辆A的伪代码：

利用getcurrentposition函数分别获取车辆A和车辆B的当前坐标(Xat3,Yat3)、(Xbt3,Ybt3)。

根据式(4)计算此时车辆A与车辆B之间的距离。

根据式(5)、式(6)、式(7)估算车辆B在其信息发送半径R内活动的剩余时间Tt3。

if T(32) > Tt3 //说明车辆B已经不在R的范围内活动了，车辆A需要重新启动选择新的下一跳。

启动选择下一跳的程序。

else if Tt3/T(32) < 2 //车辆A计算得知，车辆B可以接收到自己所发送的信息，而自己将接收不到车辆B返回来的信息，此时，车辆A启动选择下一跳的程序。

启动选择下一跳的程序

else //认为路由连接正常，正常接收和发送信息

sendWSM(mysockfd,send_wsmp, wsm_data);

当车辆B接收到数据信息时，车辆B依然使用T(21)来估算数据在t2时间点时从车辆B发出到车辆A所需要的时间，通过车辆B的估算，如果这个时间满足某些条件，车辆B认为其发送的数据在没有被车辆A接收到的情况下，车辆B本身已经驶离了车辆发送半径R的覆盖范围，因此，车辆B的伪代码：

if根据式(6)计算出来的时间T比值T(21)的值小于1

{

sendWSM(mysockfd,send_wsmp,wsm_data);//车辆B将作为车辆A的下一跳向前发送信息数据。注意，此时，车辆B把时间T发送给车辆A作为参考，同时车辆B将尽其最大的努力以广播形式告之车辆A，车辆A接收到这一信息之后将重新选择新的下一跳来传递信息

}

else if ( 1 <时间T/T(21)的值 < 2)

{//此时，车辆B认为其发送的应答信息可以被车辆A所接收到，但是，车辆A再次发送的数据将不会被自己接收到

sendWSM(mysockfd,send_wsmp,wsm_data);

Broadcast();

}

else

{//此时，车辆B对路由中断不做任何预测，正常接收数据和发送数据

sendWSM(mysockfd,send_wsmp,wsm_data);

}

4实验及结果分析

仿真过程中，信息从IV到DV的传输策略选择FMHR算法，而预测路由中断方法作用于选择传输策略后路由节点车辆间通信的路由连接情况，可看作是对FMHR算法的补充。为了更好地验证预测路由中断方法有效，分别采用对802.11p支持较好的NCTUns-6.0[7-8]对FMHR和FMHR-V进行仿真，仿真参数如下：车道长度为2.6 km×2.6 km，车辆个数150，发送范围550 m、650 m、750 m，数据发送速率6 Mb/s，仿真时间100 s，包的大小为1 000 bytes，车辆类型CarAgent，车辆速度在15～45 m/s，由配置文件profile来随意分配车辆速度。仅ID为1的路口有SignalAgent控制。通过AWK提取仿真的相关数据信息[9-10]，并通过MATLAB绘制图形以进行实验分析，见图1，图2。

图1数据包延时与仿真时间关系

图2　数据包丢失个数与仿真时间关系

通过分析可知，当车辆的信息发送范围设置在550 m时，算法在修改前和修改后的数据包丢失个数和数据包延时上区别幅度不是太大，当车辆的信息发送范围设置在650 m和750 m时，FMHR-V性能相对于原有算法FMHR的性能有所改善，经分析得知，随着发送半径的范围增大，当发送信息的车辆和接收信息的车辆之间的速度不一致的时候，FMHR算法中发送信息的车辆无法提前得知其下一跳在未来某段时间内已经不在其信息的发送半径范围内，只有经过某一段时间才会认为通信中断，这样就造成无谓的等待时间；而在FMHR-V算法中，当作为下一跳的车辆一旦离开或者将要离开发送信息车辆的发送信息半径范围时，作为下一跳的车辆和发送信息的车辆都可以尽自己最大努力对这一事件进行预测。当发送信息的车辆通过FMHR-V预测到这一事件时，即可选择新的下一跳，一方面节省了无谓的等待时间，某种程度上增强了整个信息传输过程的实时性；另一方面也减少了不可能被接收到的数据包的发送，进而，也减少了数据包被下一跳或者终端接收时丢失的可能性。

5结语

通过理论研究和相关实验数据分析，在车联网的各节点车辆快速移动过程中，各节点车辆与车辆之间通过建立起来的路由连接进行通信，当处在路由连接中的某两个节点车辆之间的速度不一致时，节点车辆之间建立起来的路由连接会因此而处于不稳定状态，发生路由连接中断，通过预测该中断发生的可能性，并在预测的基础上采取相应措施，可在一定程度上改善信息传递的性能。

参考文献：

[1]IEEE Standards Association. 802.11-2012-IEEE Standard for Information technology-Telecommunications and Information Exchange Between Systems Local and Metropolitan Area Networks-Specific Requirements Part 11:Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications[S].USA:IEEE,2012.

[2]Nathan Naylor. U.S. Department of Transportation Announces Decision to Move Forward with Vehicle-to-Vehicle Communication Technology for Light Vehicles[EB/OL].USA:NHTSA, 2014(2014-02-03)[2015-04-20]. http://www.nhtsa.gov/About+NHTSA/Press+Releases/2014/USDOT+to+Move+Forward+with+Vehicle-to-Vehicle+Communication+Technology+for+Light+Vehicles.

[3]IEEE Draft Guide for Wireless Access in Vehicular Environments (WAVE) - Architecture[S].USA:IEEE P1609.0/D5, September 2012, pp. 1-74, 2012.

[4]Bilal M, Chan P M L, Pillai P Pillai. Fastest-Vehicle Multi-hop Routing in Vehicular Ad hoc Networks [C]//Computer and Information Technology (CIT), 2010 IEEE 10th International Conference on. IEEE,2010:773-778.

[5]Bilal M, Chan P M L, Pillai P Pillai. A Fastest Multi-Hop Routing Scheme for Information Dissemination in Vehicular Communication Systems [C]//Software, Telecommunications and Computer Networks (SoftCOM), 2010 International Conference on. IEEE, 2010: 35-41.

[6]张继永,杨斌. 无线车联网WAVE车-车通信中的一种路由算法实现[J].通信技术,2013,46(09):55-57.

ZHANG Ji-yong, YANG Bin. A Routing Algorithm for Car-to-Car Communication in Wireless Access Vehicular Environment[J]. Communications Technology, 2013,46(09):55-57.

[7]陈思洋,朱西平,文红.基于NCTUns的IEEE 802.11p MAC协议性能仿真[J].计算机应用,2014,34(04):945-949.

CHEN Si-yang,ZHU Xi-ping,WEN Hong. Performance evaluation of IEEE 802.11p MACprotocol based on NCTUns[J].Journal of Computer Applications, 2014,34(04):945-949.

[8]WANG Shie-Yuan. The Protocol Developer Manual for the NCTUns 6.0 Network Simulator and Emulator[J].National Chiao Tung University,2010.

[9]Xavier Campos Ríos / Diego Pastor Pérez. Performance Evaluation of Manhattan Downtown Scenarios for Vehicular AD HOC Networks with Citymob and Nctuns[D]. Spain:UPC, Juny 2011.

[10]Adrien Daunou. Design of A Privacy-Aware Routing Protocol for Vehichlar AD HOC Networks[D]. Spain:UPC,febrer,2012.

王博(1984—)，女，硕士，主要研究方向为计算机网络、自然语言处理;

哈力木拉提·买买提(1959—)，男，教授，硕士生导师,主要研究方向为图像处理、模式识别等。