文章快速检索     高级检索
  重庆大学学报  2018, Vol. 41 Issue (8): 100-110  DOI: 10.11835/j.issn.1000-582X.2018.08.011 RIS(文献管理工具)
0

引用本文 

袁学松. 路侧装置修正位置预测模型在Vanet混合路由算法中的应用[J]. 重庆大学学报, 2018, 41(8): 100-110. DOI: 10.11835/j.issn.1000-582X.2018.08.011.
YUAN Xuesong. The application of modified roadside device position prediction model in Vanet hybrid routing algorithm[J]. Journal of Chongqing University, 2018, 41(8): 100-110. DOI: 10.11835/j.issn.1000-582X.2018.08.011.

基金项目

2017年度安徽高校重点自然科学研究项目(KJ2017A757)

作者简介

袁学松(1982-), 男, 副教授, 主要从事网络仿真技术、无线传感网、数据挖掘、图像处理技术研究, (E-mail)ahjdyxs@126.com

文章历史

收稿日期: 2018-03-01
路侧装置修正位置预测模型在Vanet混合路由算法中的应用
袁学松1,2     
1. 安徽机电职业技术学院 信息工程系, 安徽 芜湖 241000;
2. 合肥工业大学 计算机信息学院, 合肥 230001
摘要: 在Vanet应用场景中,由于车辆高速运动导致车辆节点构成的网络拓扑不断变化,多数路由协议需要及时维护自己的邻居表来选择路由。邻居选择出错会出现数据频繁重发,导致传输时延高且不可靠等现象。为此本文提出了一种基于高速公路应用场景的高效的邻居发现方法NDK(Vanet Neighbor Discovery method By Kalman filter)。该方法利用经典的地理位置路由算法GPSR思想,借助于卡尔曼滤波(Kalman filter)预测模型来预测节点的邻居表,同时周期性的使用路侧装置(RSU,Road Side Unit)修正预测值。通过NS-3的仿真实验表明,该算法较经典的GPSR算法和其他基于时间、移动预测邻居表的算法能更好判断节点的加入和离开,并有更好的邻居正确率和更轻的网络负载。
关键词: Vanet    GPSR    卡尔曼滤波    路侧装置    分组到达率    传输时延    
The application of modified roadside device position prediction model in Vanet hybrid routing algorithm
YUAN Xuesong1,2     
1. Department of Information Engineering, Anhui Technical College of Mechanical and Electrical Engineering, Wuhu 241000, Anhui, P. R. China;
2. School of Computer and Information, Hefei University of Technology, Hefei 230009, P. R. China
Supported by Key Natural Science Research Project of Anhui University in 2017(KJ2017A757)
Abstract: In the Vanet application scenario, due to the high speed motion of the vehicle, the topology of the network keep changing, and most routing protocols need to maintain their neighbor table in time for routing select. Frequent retransmission of data caused by neighbor selection error will result in high time delay and unreliability. Many Vanet classic protocols cannot be applied to all scenarios. For this reason, this paper proposes a hybrid Vannet routing algorithm based on the highway application scenario NDK (Vanet Neighbor Discovery Method By Kalman Filter). The algorithm uses the GPSR (Greedy Perimeter Stateless Routing) idea of the classic geographic location routing algorithm, with the help of Kalman filter prediction model to predict the neighbor node table, and at the same time, the predicted values are periodically modified by roadside device (RSU, Road Side Unit). The result of NS-3 simulation experiments show that, compared with the classical GPSR algorithm and other algorithms based on time and motion, the algorithm has better packet arrival rate and lower transmission delay.
Key Words: Vanet    GPSR    Kalman filtering    roadside device    packet arrival rate    transmission delay    

车载自组织网(vehicular ad hoc network, Vanet)[1]近年来发展很快,它使用车载相关电子设备如:全球定位装置(GPS、北斗导航装置等)、电子地图、车内各种控制传感器和无线通信装置等来实现车辆间、车辆与路侧装置相互数据通信。Vanet的主要业务分为实时性要求较高的交通安全类业务(如交通事故预警、道路危险信息通告等)和非安全类业务(如Internet接入、车载多媒体等)[2-3]。如何针对各种业务需求设计出安全可靠且高效的路由协议一直是研究的热点。

在Vanet场景中,传统的路由协议(如DSR[4]、AODV[5]等)会随车辆的增多、网络拓扑的频繁变换出现节点传输失效,重发次数增多等现象。多次的重复数据包重发会加重网络的负载,使整个网络的冗余度增加,严重的会导致广播风暴的产生。该类协议在特殊场景中不仅不能及时的传输数据信息,还会造成网络的瘫痪。Korkmaz等[6]和Kalinin等[7]分别提出的适用于城市场景的UMB协议和AMB协议,由于它们使用RTS/CTS的握手机制,在一定程度上提高了车辆广播路由的可靠性,所以得到了广泛的应用。随着全球定位系统的精度逐步提高、GIS(地理位置信息系统)的普及,基于地理位置的Vanet路由协议近年来不断发展,该类协议以广泛应用于城市复杂场景和高速公路等特殊场景。GPSR协议[8]是最典型的基于地理位置的路由协议,该协议是将数据分组尽量转发给最靠近目的节点的邻居节点,这样可以减少转发数量,从而提高转发效率。但由于车辆节点大多处于高速运动状态下,如果分组未能找到合适的转发邻居或转发邻居在转发过程中已经失效。这样就会导致多次重发,加大网络负载,使安全类消息得不到及时传输。所以一些学者通过携带转发、周边转发等模式来提高网络拓扑的联通性。例如文献[9-10]就利用车辆节点来存储消息并携带消息进行转发来解决城市交通中低密度节点的问题。这类协议虽然能够解决分组重复转发的问题,但是由于需要节点携带消息转发,造成转发时延较高,不适用于安全消息的传输。文献[11]通过在车辆节点上安装了卡尔曼滤波预测器,用来预测每个车辆节点和其邻居节点的下一时刻位置。这样就避免了节点周期性交流位置信息,这种方法大大减轻了网络的负载。但是由于预测的精度不高,错误的预测会直接影响到节点的路由决策,造成路由失效。文献[12]同样使用了卡尔曼滤波器来预测自己的邻居节点和其位置,与文献[11]不同的是它通过车载定位系统来判断预测值与实测值之差是否在一定的范围内。如果超过一定阈值则通过Hello包对邻居信息进行修正。这样只需要少量的Hello分组就可以完成邻居表的预测和修正。但该协议依然未解决低密度场景携带转发问题,和邻居到达判断问题。

许多针对城市交通公路和高速公路环境下Vanet的研究指出[13]:使用车辆节点作为中继,虽可减少路侧装置(RSU)的成本投入,也可提升Vanet的网络覆盖范围。但由于车流密度等因素的影响,其并不具备稳定的吞吐量。RSU装置作为可靠的、稳定的网络传输中继节点,在紧急消息传输等要求高分组到达率、低时延的场景中能发挥很大的作用。当前大多RSU作用是将车辆接入Internet等基础设施网络[14],近年来许多学者将其应用在紧急消息发送和替代位置路由算法的节点携带转发上。文献[15]使用软件定义网络(software-definednetworking,SDN)[16]配合RSU进行紧急消息的广播,虽然在城市场景中取得了很好的性能,但并不适用于RSU部署稀疏的高速公路场景。文献[17]提出了一种车辆主动受限多跳广播算法,提出最大传输距离的概念,区分了车辆节点和RSU节点传输范围。仿真实验证明其在某些场景可以很好的利用无线带宽资源。但由于其主动限制了传输距离,同样也不适合高速公路场景。文献[18]基于RSU辅助GPSR算法,对节点沿已有路径进行贪婪转发发生偏移进行修正,能有效减少控制包开销。但各节点未预测下一时刻的运动轨迹,导致偏移修正可能不够精确,重发数据包会导致网络负担加重。

针对高速公路场景建立了卡尔曼滤波模型,笔者通过建立车辆在高速公路上运动模型,对其运动规律进行分析,使用自身的卡尔曼预测器预测出自己所有邻居节点的运动位置,并首次更新自身邻居表。同时,针对预测可能出现的误差使用RSU,周期性的对覆盖范围内的车辆节点进行邻居节点位置信息进行修正,并在此更新节点自身邻居表。RSU设备的加入也保证了在低密度环境中安全信息的传输,当算法在特定情况下失效时候,仍然使用贪婪转发和周边转发机制对数据进行传输。

1 高速公路场景中通过卡尔曼滤波算法对车辆位置预测

本预测算法默认所有车辆节点均安装有GPS或其他类似定位装置。同时,车辆节点可以通过车内各种电子传感器和最新的电子地图获取车辆精确的位置信息、实时速度、加速度、运动方向等信息。

1.1 路由节点丢失问题

在高速公路场景中,使用GPSR等地理位置路由算法时经常会出现路由节点丢失情况。如图 1所示节点A在t时刻想与节点F进行数据通信。根据GPSR协议,分组将被转发至离自己最远且在通信范围之内的节点B。而当在t+1时刻,节点A获得信道进行数据传输(如图 2)。此时,B节点已超出A节点的通信范围,A是不可能将分组直接传输给B的,这样就会造成了路由节点的丢失。这种节点的丢失会使节点A要重新进行邻居节点的发现操作,同时进行分组的重传,加重了网络的负载。

图 1 t时刻高速公路场景图 Figure 1 Highway scene graph for time t
图 2 t+1时刻高速公路场景图 Figure 2 Highway scene graph for time t+1

为了避免节点丢失情况的发生,实时预测A节点所有邻居节点下一时刻的位置信息是路由算法设计的关键点。笔者将使用卡尔曼滤波模型对各节点的位置进行相关预测,减少节点丢失情况的发生。

1.2 卡尔曼滤波模型对节点位置预测

卡尔曼递归预测器的工作原理是通过一系列实测观测值,同时参考高斯噪声和其他一系列误差值来递归预测下一时刻的状态值[19-20]。适合对存在噪声的线性动态系统的状态空间进行建模, 主要是计算各变量之间的协方差,提高变量估计的精度。对于一个状态空间模型,各状态均在离散时间内进行预测,其通过现实观测值修正当前状态预测值,再根据修正结果继续预测下一个状态的值。假设在k时刻有k-1时刻的预测向量$ \mathit{\boldsymbol{\hat X}}\left( k \right) = {\left[ {\mathit{\boldsymbol{\hat x}}\left( k \right), {{\mathit{\boldsymbol{\hat V}}}_x}\left( k \right), \mathit{\boldsymbol{\hat y}}\left( k \right), {{\mathit{\boldsymbol{\hat V}}}_y}\left( k \right), \mathit{\boldsymbol{\hat \omega }}\left( k \right)} \right]^{\rm{T}}} $和通过车内各传感器得到当前车辆的一个实际测量的向量X(k),$ \mathit{\boldsymbol{X}}\left( k \right) = {\left[ {\mathit{\boldsymbol{x}}\left( k \right), {\mathit{\boldsymbol{V}}_x}\left( k \right), \mathit{\boldsymbol{y}}\left( k \right), {\mathit{\boldsymbol{V}}_y}\left( k \right), \mathit{\boldsymbol{\omega }}\left( k \right)} \right]^{\rm{T}}} $x(k)和y(k)为位置坐标信息,Vx(k)和Vy(k)为速度向量,ω(k)为方向向量。则在k+1时刻车辆位置通过卡尔曼滤波递归预测(通过车辆当前的实际测量值X(k)和其在k-1时刻的预测值$ \left. {\mathit{\boldsymbol{\hat X}}\left( k \right)} \right) $k+1时刻车辆节点位置向量为$ \mathit{\boldsymbol{\hat X}} $$ \mathit{\boldsymbol{\hat X}}\left( {k + 1} \right) = {\left[ {\mathit{\boldsymbol{\hat x}}\left( {k + 1} \right), {{\mathit{\boldsymbol{\hat V}}}_x}\left( {k + 1} \right), \mathit{\boldsymbol{\hat y}}\left( {k + 1} \right), {{\mathit{\boldsymbol{\hat V}}}_y}\left( {k + 1} \right), \mathit{\boldsymbol{\hat \omega }}\left( {k + 1} \right)} \right]^{\rm{T}}} $,(k时刻与k+1时刻的时间差为ΔT)具体各参数的预测方法见式(1)(上标^表示此项为预测值):

$ \left. \begin{array}{l} \mathit{\boldsymbol{\hat x}}\left( {k + 1} \right) = \hat x\left( k \right) + {\mathit{\boldsymbol{V}}_{\hat x}}\left( k \right) \times \Delta T, \\ \mathit{\boldsymbol{\hat y}}\left( {k + 1} \right) = \hat y\left( k \right) + {\mathit{\boldsymbol{V}}_{\hat y}}\left( k \right) \times \Delta T, \\ {\mathit{\boldsymbol{V}}_{\hat x}}\left( {k + 1} \right) = {\mathit{\boldsymbol{V}}_{\hat x}}\left( k \right) \times \cos \left( {\mathit{\boldsymbol{\hat \omega }}\left( k \right)} \right), \\ {\mathit{\boldsymbol{V}}_{\hat y}}\left( {k + 1} \right) = {\mathit{\boldsymbol{V}}_{\hat y}}\left( k \right) \times \sin \left( {\mathit{\boldsymbol{\hat \omega }}\left( k \right)} \right), \\ \mathit{\boldsymbol{\hat \omega }}\left( {k + 1} \right) = \mathit{\boldsymbol{\hat \omega }}\left( k \right) + \mathit{\boldsymbol{\hat \omega }}\left( k \right) \times \Delta T。\end{array} \right\} $ (1)

在此阶段拓扑中的每个节点均使用该方法迭代预测下一时刻的位置估计向量。在k时刻引入一个离散控制过程的系统,可用一个线性随机微分方程(2)来描述,系统实际测量值用式(3)来表示。

$ {\mathit{\boldsymbol{X}}_k} = \mathit{\boldsymbol{A}}{\mathit{\boldsymbol{X}}_{k - 1}} + \mathit{\boldsymbol{B}}{\mathit{\boldsymbol{U}}_k} + {\mathit{\boldsymbol{W}}_k} $ (2)
$ {\mathit{\boldsymbol{Z}}_k} = \mathit{\boldsymbol{C}}{\mathit{\boldsymbol{X}}_k} + {\mathit{\boldsymbol{V}}_k}。$ (3)

Xk-1k-1时刻的系统状态,Ukk时刻对系统的控制量,AB是系统参数,在多模型系统中他们均为矩阵。WkVk是相对独立的白噪声过程,它们的协方差矩阵分别为QRZkk时刻的实际测量值,C是测量系统的参数,在多测量系统中C为矩阵。

具体卡尔曼滤波方法及相关公式如下所示(以车辆节点在水平位置上的位移卡尔曼滤波预测$ \mathit{\boldsymbol{\hat x}}\left( k \right) $为例):假设现在系统实测状态为xk,根据相关模型可以基于系统上一状态预测出该状态的值$ {{\mathit{\boldsymbol{\hat x}}}_{k|k - 1}} $

$ {{\mathit{\boldsymbol{\hat x}}}_{k|k - 1}} = \mathit{\boldsymbol{A}}{\mathit{\boldsymbol{x}}_{k - 1|k - 1}} + \mathit{\boldsymbol{B}}{\mathit{\boldsymbol{U}}_k}。$ (4)

其中$ {{\mathit{\boldsymbol{\hat x}}}_{k|k - 1}} $为利用上一个状态预测k时刻的结果($ {{\mathit{\boldsymbol{\hat x}}}_{k|k - 1}} $就是式(1)中的$ \mathit{\boldsymbol{\hat x}}\left( k \right) $),$ \mathit{\boldsymbol{A}}{\mathit{\boldsymbol{x}}_{k - 1|k - 1}} $为上一个状态最优结果(后文说明),Uk为现状态的控制量。$ {{\mathit{\boldsymbol{\hat x}}}_{k|k - 1}} $的协方差为Pk|k-1,该值由(5)求得。

$ {\mathit{\boldsymbol{P}}_{k|k - 1}} + \mathit{\boldsymbol{A}}{\mathit{\boldsymbol{P}}_{k - 1|k - 1}}\mathit{\boldsymbol{A'}} + \mathit{\boldsymbol{Q}} $ (5)

其中Pk-1|k-1xk-1|k-1的协方差,A'表示A的转置矩阵,而Q则是系统过程的协方差。式(4)~(5)对于系统的相关预测。

系统同时通过车内各种传感器收集在k时刻的车辆实际x坐标,通过预测值和实测值,可以得到现在k时刻的最优化估算值xk|k,如式(6)所示:

$ {\mathit{\boldsymbol{x}}_{k|k}} = {\mathit{\boldsymbol{\hat x}}_{k|k - 1}} + K{g_k}\left( {{\mathit{\boldsymbol{Z}}_k} - \mathit{\boldsymbol{C}}{{\mathit{\boldsymbol{\hat x}}}_{k|k - 1}}} \right)。$ (6)

Kgk为卡尔曼增益,如式(7)所示:

$ \mathit{\boldsymbol{K}}{\mathit{\boldsymbol{g}}_k} = \frac{{{\mathit{\boldsymbol{P}}_{k|k - 1}}\;\;\mathit{\boldsymbol{C'}}}}{{\left( {\mathit{\boldsymbol{C}}{\mathit{\boldsymbol{P}}_{k|k - 1}}\;\;\mathit{\boldsymbol{C'}} + \mathit{\boldsymbol{R}}} \right)}}, $ (7)

其中C'为C的转置矩阵,R为系统协方差,在这里得到了在k时刻系统最优估算值xk|k。在该时刻系统的协方差为Pk|k,如式(8)所示:

$ {\mathit{\boldsymbol{P}}_{k|k}} = \left( {\mathit{\boldsymbol{L}} - \mathit{\boldsymbol{K}}{\mathit{\boldsymbol{g}}_k}\mathit{\boldsymbol{C}}} \right){\mathit{\boldsymbol{P}}_{k|k - 1}}, $ (8)

其中L为系统矩阵,对于单模型(只预测车辆X方向位置)L=1,当系统进入k+1状态时,将式(8)带入式(5),这样系统就可以递归的运行下去。使用同样的方法预测得到$ {{\mathit{\boldsymbol{\hat y}}}}\left( k \right) $$ {{\mathit{\boldsymbol{\hat V}}}_x}\left( k \right) $$ {{\mathit{\boldsymbol{\hat V}}}_y}\left( k \right) $$ \mathit{\boldsymbol{\hat \omega }}\left( k \right) $,然后通过式(1)得到$ \mathit{\boldsymbol{\hat X}}\left( {k + 1} \right) $

1.3 邻居节点的维护

许多现有的改进地理位置路由算法中,邻居节点的预测大多使用相对位移或者导航路径来判断其是否在源节点的通信范围内。在本算法中,设计了含有预测位置权值的邻居表。该邻居表并非利用Hello包进行邻居信息的交换,而是利用卡尔曼滤波算法对每个邻居节点具体位置进行预测,根据预测的结果首次更新自身邻居表信息。下面将着重介绍本算法邻居节点的维护方法,包括邻居节点离开和加入过程。

图 1t时刻,若A节点需发送数据分组给F,首先A会查找自己的邻居表(如表 1所示)。邻居表中包括节点的邻居节点、t时刻节点与邻居节点的权值信息、同时卡尔曼滤波器预测的下一时隙节点与邻居节点的权值信息、下一时隙邻居节点的运动方向等结构。当发现F节点并非邻居表中的邻居节点,算法会将分组传输给邻居表中下一时隙、同方向、邻居节点权值最大的节点D,而非t时刻节点B。因为通过卡尔曼滤波预测B将在下一个时隙离开A的通信范围。

表 1 NDK算法中A节点的邻居表格式 Table 1 Neighbor table format of A node in NDK algorithm

NDK算法中A节点与邻居节点间的距离均用权值来表示,权值的计算方法如式(9)所示:其中$ {{\mathit{\boldsymbol{\hat x}}}_i}\left( {t + 1} \right) $$ {{\mathit{\boldsymbol{\hat y}}}_i}\left( {t + 1} \right) $为使用卡尔曼滤波算法估计的t+1时刻节点i(i为A的其他邻居节点)的值。$ {{\mathit{\boldsymbol{\hat x}}}_{\rm{a}}}\left( {t + 1} \right) $为和$ {{\mathit{\boldsymbol{\hat y}}}_{\rm{a}}}\left( {t + 1} \right) $是A节点t+1时刻的预测值。得到的Δd′即为邻居节点间估计的权值大小。如果Δd′>R(R为节点的通信半径),表示节点在下一时隙失效,即节点离开了A的通信范围。同时使用预测的方向向量判断邻居节点时再A节点的前向还是反向。所以当A要在下一时隙与F进行数据通信时,会选择离自己最远且前向的D作为下一跳转发节点。

$ \Delta \mathit{\boldsymbol{d'}} = \sqrt {{{\left| {{{\mathit{\boldsymbol{\hat x}}}_i}\left( {t + 1} \right) - {{\mathit{\boldsymbol{\hat x}}}_{\rm{a}}}\left( {t + 1} \right)} \right|}^2} + {{\left| {{{\mathit{\boldsymbol{\hat y}}}_i}\left( {t + 1} \right) - {{\mathit{\boldsymbol{\hat y}}}_{\rm{a}}}\left( {t + 1} \right)} \right|}^2}} 。$ (9)

通过这种方法,每个节点均使用卡尔曼滤波预测器计算当前和下一个时隙的邻居节点以及相应的权值,并首次更新其邻居表。这样就不用像传统的邻居发现方法一样使用Hello包来交换信息更新邻居表,大大减轻了网络的负担。但是在卡尔曼递归预测过程中难免会出现误差,由文献[9]分析说明了如果不及时对其修正误差,预测误差会越来越大,导致整个预测算法失效。

为了解决预测修正问题,算法引入路侧单元(RSU,road side unit)。如图 3所示RSU放置在高速公路隔离带中,由于RSU功率较大,覆盖的范围也较广,可以覆盖较多的车辆节点。所有在RSU覆盖范围内的车辆周期性的向该路侧装置发送位置信标。信标格式如图 4所示:该信标格式主要有节点i传感器所得到的该节点实时的位置信息xiyi、运动方向信息ωi、加速度信息ai等。当RSU收到覆盖范围内所有节点的信标后,通过RSU的计算,得到各节点邻居表中t时刻的真实权值,将以图 5中的信标格式发送回相关节点。其中NNI1(neighbor node information 1)表示第一个邻居节点和其与i节点之间的权值,有多少个邻居节点,信标将会包含多少个节点字段。当各节点收到RUS回复的信标后,各节点将在下一个时隙使用修正过的权值对邻居表进行预测和更新。

图 3 RSU工作场景 Figure 3 RSU working scene
图 4 节点i发送给RSU的信标格式 Figure 4 Beacon format for node i sent to RSU
图 5 RSU发送给节点i的信标格式 Figure 5 RSU beacon format sent to node i

上文算法对节点的失效(退出)进行了描述。节点如何加入邻居表也是NDK算法中重要的一部分。如图 6所示当节点P与节点A同向行驶,t时刻,P不在A的邻居表中,但P和A均在RSU的覆盖范围内。当RSU获取所有节点的位置信息后,通过A和P的加速度计算发现在下一个时隙P可能成为A的邻居节点(运动趋势一致且P的加速度大于A的加速度,经Δt时间后,P可能进入A的通信范围)。所以在RSU发送给A的信标中会把P节点的NNI信息提供给A节点。A节点在收到RSU发来的信标后,更新邻居节点时也会将P节点作为自己的邻居节点。当然这些只是RSU预测的可能加入邻居表的节点。也可能在Δt时间内P由于紧急制动,进过Δt时间P仍然未进入A的通信范围内。这时当A需要发送给P信息,会查找邻居节点直接发送,但在实际发送过程中A找不到这个节点P,这时算法会根据GPRS协议相关贪婪转发和周边转发的方法来找到P节点。

图 6 节点加入邻居表示意图 Figure 6 Sketch map of node joins neighbor table
2 具体邻居发现方法和相关路由算法的描述

各车辆节点转发数据分组工作流程如图 7所示,路测装置RSU的工作流程如图 8所示。

图 7 节点工作流程图 Figure 7 Node workflow diagram
图 8 RSU工作流程图 Figure 8 RSU work flow chart

节点的路由算法步骤如下:

1) 每个节点根据自己的当前邻居表,通过卡尔曼滤波预测算法计算下一个时隙的邻居节点和对应的权值。同时通过RSU得到相关信息修正邻居表(具体见RSU工作流程);

2) 源节点需发送数据包给目的节点,首先查找自己的邻居表,判断目的节点是否在邻居节点表内; 如果在该表内,则在获得信道后直接转发该分组。否则进入3);

3) 使用相关贪婪转发方式找到在节点通信范围内,最远的节点进行转发。同时通过预测算法判断该转发节点下一时隙是否失效,如果不失效则在获得信道后直接转发该分组给最远的节点。否则进入4);

4) 在邻居表中的下一时隙权值列找到不失效的最优节点进行分组转发。如果在转发中找不到该节点,说明可能是RSU预测节点加入错误继续回到3)操作,否则进入5);

5) 在转发至该节点后,再次使用HKR算法直至数据分组转发至目的节点。

RSU和节点进行预测值修正和节点加入邻居表具体步骤如下:

1) 节点周期性的发送信标给当前RSU,RSU则收集覆盖范围内所有节点的参数(位置、方向、加速度等信息)。

2) RSU通过计算得到每个车辆节点该时刻的邻居节点和相对权值信息,并将其发送给每个节点用于修正各节点邻居表信息。

3 仿真实验分析

将本文中所述邻居发现方法应用在高速公路场景中,默认车辆节点可以通过车内各种电子传感器和最新的电子地图获取车辆精确的位置信息、实时速度、加速度、运动方向等信息,并将该协议的各种性能与经典的GPSR协议、通过卡尔曼滤波预测的KPHR协议进行比较。把不同密度车流下网络拓扑中端到端的传输时延、网络负载、分组到达率作为考察协议有效性的重要指标,同时引入平均邻居发现错误率(average neighbor discovery error rate,ANDER)作为评价邻居发现方法的指标。

邻居发现错误率指在仿真时间内,拓扑中的所有节点的错误邻居个数与所有节点的邻居节点个数的比值。如式(10)所示,Mn为仿真过程中节点n的所有邻居节点个数,$ \sum\limits_{i = 1}^n {{M_n}} $表示拓扑内所有节点在整个仿真过程中真实邻居节点的个数之和。En表示节点n在真个仿真过程中邻居节点错误的个数(错误的邻居节点包括节点不在n的通信范围内,仍然在n的邻居表中、RSU判断下时隙在节点n的邻居表中,但实际未能加入n邻居表的节点)。$ \sum\limits_{i = 1}^n {{E_n}} $表示在仿真过程中,所有节点产生的错误邻居节点之和。

$ {\rm{ANDER}} = \frac{{\sum\limits_{i = 1}^n {{E_n}} }}{{\sum\limits_{i = 1}^n {{M_n}} }}。$ (10)

仿真使用车辆节点生成器VanetMobiSim[21-22](vehicular ad hoc networks mobility simulator)来生成不同密度的车辆节点运动模型。选取一段长5 km,宽约40 m的双向8车道高速公路车道模型,每2 km在路中间设置一个通信半径为1 km的RSU。实验在NS-3仿真平台下进行。具体参数见表 2

表 2 实验仿真参数设置 Table 2 Experimental simulation parameter setting

具体仿真结果如图 9~12所示。图 9展示的为车辆密度在10~60 vehicles/km时各节点平均端到端的传输时延。由于NDK算法使用卡尔曼滤波预测器准确的预测了邻居节点的位置信息,分组转发的次数减少,平均端到端的传输时延较经典协议有所降低。KPHR算法未进行邻居节点的修正,车辆密度较大的情况下,即使未找到正确的转发节点,也可立刻通过自身的邻居表找到其他转发节点进行转发操作,对该性能影响不大。如果在稀疏交通流的场景下,当分组未能找到正确的转发节点时,需要重新开启Hello包邻居发现机制,会对时延产生较大影响。

图 9 不同车流密度下节点平均端到端时延 Figure 9 Average end-to-end delay of nodes under different traffic density
图 10 不同车流密度下的网络负载 Figure 10 Network load under different traffic densities
图 11 不同车流密度下的分组到达率 Figure 11 Packet arrival rate under different traffic density
图 12 不同车流密度下的平均邻居发现错误率 Figure 12 Average neighbor discovery error rateunder different traffic density

图 10展示的是网络拓扑的负载情况。由于GPSR协议是通过周期性的广播Hello包信标的方法得到邻居节点的具体位置的。周期性的发送该信标会大大占用网络资源。KPHR算法和NDK算法均采用卡尔曼滤波来完成邻居节点的预测,减少了Hello包发送的频次,实验可以看出这两种协议的网络负载较经典GPSR协议有很大改进,但是由于NDK算法需要周期性的与RSU交换信标,在高密度车流场景下,网络负载略大于KPHR算法。

图 11展示的是3种算法在不同密度车流场景下的有效分组到达率,从数据可以看出使用NDK算法后,包到达率在98%左右。在低密度车流场景下由于转发节点较少,可能需要进行携带转发操作,分组到达率稍低。由于KPHR算法为对邻居节点进行修正,可能造成节点路由的错误选择,造成多次数据重传,降低了分组到达率。而经典的GPSR协议在该场景下的分组到达率只有90%左右。

图 12展示的是3种算法的节点平均邻居错误率,由于采用了二次更新邻居表的方法,随着节点密度的增加NDK算法的ANDER指标约在4%之内,且非常稳定。而其他2种算法随着车辆节点密度的增加ANDER指标上升的很明显,会造成更多的分组重发,加重网络负担。

通过对在高速公路不同车流密度场景进行仿真实验可以看出:1)NDK算法在平均邻居发现错误率上要远优于经典算法和相关改进算法,表明在RSU周期性修正预测值可明显提高邻居发现的正确率。特别是在低密度车流环境中表现的更加明显。2)由于邻居被正确的发现,提高了路由正确率,减少了由于错误判断邻居造成的数据包重发,从而减轻了网络的负载。但周期发送和接收RSU信标也会导致一定的网络负载,这些情况在高密度车流中表现的尤为明显,也是本算法不可避免的问题。总体来看,NDK算法在不同车流密度高速公路场景中表现优于其他算法。

4 结语

针对高速公路场景中Vanet安全分组传输,提出了一种基于RSU修正卡尔曼滤波位置预测模型的高效的邻居发现方法并将其应用到混合式Vanet路由算法。该方法利用车载卡尔曼滤波器,估算下一时刻自己与各邻居节点的位置,并首次更新自身邻居表。同时利用RSU对各节点邻居表中的权值进行修正,再次更新邻居表,提高路由选择的准确性。经仿真实验证明,该算法较同类协议有较好的分组到达率、较轻的网络负载、较低的端到端时延,平均邻居发现错误率明显低于其他算法。由于本算法要求高速公路场景均需RSU信号覆盖,在当前实现起来较为困难,随着部署成本的降低,可以在易发事故的路段或者交通密集区域进行RSU的均匀部署。同时,算法在高密度场景中的表现和其他改进算法相当,甚至会由于RSU定期广播造成网络负载加重,因此,下一步研究重点将放在如何在高密度场景下对整个网络进行相关协议的切换。同时将对该算法进行相应改进应用到复杂的城市交通环境中,考虑各种噪声对卡尔曼滤波预测算法的影响,进一步改进算法性能。

参考文献
[1] Liu H Q, Yang L C, Ding S J, et al. Logical connectivity prediction models for VANET based on nonlinear regression and ELM:An example of the AODV protocol[J]. International Journal of Future Generation Communication and Networking, 2014, 17(6): 217–230.
[2] 徐会彬, 夏超. VANETs路由综述[J]. 计算机应用研究, 2013, 30(1): 1–6.
XU Huibin, XIA Chao. Survey on routing in vehicular ad hoc networks[J]. Application Research of Computers, 2013, 30(1): 1–6. (in Chinese)
[3] Gerla M, Kleinrock L. Vehicular networks and the future of the mobile Internet[J]. Computer Networks, 2011, 55(2): 457–469. DOI:10.1016/j.comnet.2010.10.015
[4] 杨志伟, 陈昊亮, 张波, 等. 软件定义车联网的数据转发机制[J]. 计算机应用, 2017, 37(1): 84–89.
YANG Zhiwei, CHEN Haoliang, ZHANG Bo, et al. Data forwarding mechanism in software-defined vehicular ad hoc network[J]. Journal of Computer Applications, 2017, 37(1): 84–89. DOI:10.11772/j.issn.1001-9081.2017.01.0084 (in Chinese)
[5] 何绵禄, 褚伟, 刘辉舟. AODV路由协议的研究和改进[J]. 计算机工程, 2015, 41(1): 110–114, 120.
HE Mianlu, CHU Wei, LIU Huizhou. Research and improvement of AODV routing protocol[J]. Computer Engineering, 2015, 41(1): 110–114, 120. (in Chinese)
[6] Korkmaz G, Ekici E, Ozguner F, et al. Urban multi-hop broadcast protocol for inter-vehicle communication systems[C]//Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks, October 1, 2004, Philadelphia, USA. New York: ACM, 2004: 76-85.
[7] Kalinin M, Zegzhda P, Zegzhda D, et al. Software defined security for vehicular ad hoc networks[C]//2016 International Conference on Information and Communication Technology Convergence (ICTC), October 19-21, 2016, Jeju, South Korea. [S. l. ]: IEEE, 2016: 533-537.
[8] Karp B, Kung H T. GPSR: Greedy perimeter stateless routing for wireless networks[C]//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking. New York, USA: ACM Press, 2000: 243-254.
[9] Sabri M H, Mohannad M K, Tat C W. Density-aware directional forwarding strategy for vehicular ad hoc networks[C]//2015 IEEE 12th Malaysia International Conference on Communications(MICC), October 31, 2016, Kuching, Malaysia. [S. l. ]: IEEE, 2015: 139-144.
[10] Chung M H, Shih Y L. Timer-based greedy forwarding algorithm in vehicular ad hoc networks[J]. Intelligent Transport System, 2014, 8(4): 333–334. DOI:10.1049/iet-its.2013.0014
[11] 王广彧, 刘春凤, 赵增华, 等. 基于卡尔曼预测的VANET混合路由算法[J]. 计算机工程, 2014, 40(8): 91–95.
WANG Guangyu, LIU Chunfeng, ZHAO Zenghua, et al. Hybrid routing algorithm in vehicular ad hoc network based on Kalman prediction[J]. Computer Engineering, 2014, 40(8): 91–95. (in Chinese)
[12] 贺然, 张钢, 刘春凤, 等. 车载网络中基于移动轨迹预测的快速邻居发现算法[J]. 计算机应用研究, 2015, 32(9): 2737–2741.
HE Ran, ZHANG Gang, LIU Chunfeng, et al. Fast neighbor discovery scheme based on mobility prediction in vehicular networks[J]. Application Research of Computers, 2015, 32(9): 2737–2741. (in Chinese)
[13] Boban M, Meireles R, Barros J, et al. TVR:Tall vehicle relaying in vehicular networks[J]. IEEE Transactions on Mobile Computing, 2014, 13(5): 1118–1131. DOI:10.1109/TMC.2013.70
[14] Li Y, Zhu X, Jin D, et al. Multiple content dissemination in roadside-unit-aided vehicular opportunistic networks[J]. IEEE Transactions on Vehicular Technology, 2014, 63(6): 2794–2806. DOI:10.1109/TVT.2013.2292519
[15] 朱婉婷. 面向城市道路的车联网紧急消息可靠传输机制研究[D]. 北京: 北京交通大学, 2017.
ZHU Wanting. Research on reliable transmission of emergency messages in Internet-of-Vehicles for urban road[D]. BeiJing: Beijing Jiaotong University, 2017. (in Chinese)
[16] Masoudi R, Ghaffari A. Software defined networks:A survey[J]. Journal of Network and Computer Applications, 2016, 67: 1–25. DOI:10.1016/j.jnca.2016.03.016
[17] 许昱玮. VANETs中面向交通状态的车辆主动探测方法研究[D]. 天津: 南开大学, 2012.
XU Yiwei. Research on vehicle-active methods for traffic status detection in VANETs[D]. Tianjin: Nankai University, 2012. (in Chinese)
[18] 任智, 张勇, 王中永, 等. 车载自组网中基于消息聚合的高效路由算法[J]. 光通信研究, 2017(3): 48–51.
REN Zhi, ZHANG Yong, WANG Zhongyong, et al. Efficient routing with message aggregation in vehicular ad hoc networks[J]. Study on Optical Communications, 2017(3): 48–51. (in Chinese)
[19] Kalman R E. A new approach to linear filtering and prediction problems[J]. Journal of Basic Engineering, 1960, 82(1): 35–45. DOI:10.1115/1.3662552
[20] Moghaddam B A, Haleh H, Ebrahimijam S. Forecasting trend and stock price with adaptive extended Kalman filter data fusion[C]//Proceedings of IEEE International Conference on Economics and Finance Research. Singapore: IEEE, 2011: 119-123.
[21] Ashtaiwi A, Altayesh A, Belghet K. IEEE 802. 11p performance evaluation at different driving environments[C]//2015 World Symposium on Computer Networks and Information Security (WSCNIS), September 19-21, 2015, Hammamet, Tunisia. [S. l. ]: IEEE, 2016: 1-8.
[22] Perdana D, Sari R F. Performance evaluation of corrupted signal caused by random way point and Gauss Markov mobility model on IEEE 1609. 4 standards[C]//2015 International Symposium on Next-Generation Electronics (ISNE), May 4-6, 2015, Taipei, Taiwan. [S. l. ]: IEEE, 2015: 1-4.