基于卡尔曼预测的VANET 混合路由算法

王广彧，刘春凤，2，赵增华，舒炎泰

(1.天津大学计算机科学与技术学院，天津 300072;2.天津市认知计算与应用重点实验室，天津 300072)

1 概述

车载自组织网络(Vehicular Ad Hoc Network，VANET)依靠安装无线通信设备的车辆进行数据传输，能够提供互联网移动接入、辅助驾驶、事故预警等应用［1-2］，是智能交通系统的重要组成部分，近年来受到工业界和国内外科研院所的普遍关注。作为一种特殊的移动自组织网络(Mobile Ad Hoc Networks，MANET)，VANET 节点受道路状况、交通机制的影响，具有高速移动、分布不均等特征［3-5］，造成通信时间短、链路频繁断裂、链路容量受限，使得车辆之间的高效数据传输面临极大的挑战。

现有的VANET 路由算法大致分为2 类:地理位置路由和容迟网络(Delay Tolerant Network，DTN)路由。GPSR (Greedy Perimeter Stateless Routing)［6］是一种典型的地理位置路由算法，将分组转发给在地理位置上更靠近目的节点的邻居。在连通性较好的网络中，地理位置路由的分组投递率较高且时延较低，但在连通性较差的网络中，分组在多跳之后往往找不到合适的转发节点而被丢弃，网络的整体投递率很低。另一类路由算法，如文献［3］算法，借助于DTN 网络存储-携带-转发的思想，来实现非连通区域的数据传输，解决车载网络在间歇连通和低密度情况下的数据传输问题。这类算法在稀疏网络中可以提升分组投递率，但分组的端到端时延一般较高。混合路由算法如Geo+DTN［7］结合了地理位置路由在连通性较好网络中低时延和DTN 路由在连通性较差网络中高投递率的特点。但Geo+DTN 完全依赖导航系统提供车辆位置或轨迹信息，灵活性较差，其DTN 模式只是简单的存储-携带，直到可以转回贪婪转发模式，未充分利用位置信息做出更优的转发决策。

本文针对城市车载自组织网络场景中地理位置路由和DTN 路由的不足，及车载网络路由算法在获取车辆位置信息方面的局限性，提出一种适用于城市场景的、基于卡尔曼预测的混合路由算法KPHR。该算法利用卡尔曼滤波对车辆位置进行实时预测来辅助路由计算。在GPSR 算法的基础上，结合容迟网络(DTN)路由存储-携带-转发的思想，在贪婪模式或边缘模式中，当无转发节点时，切换至DTN 模式存储携带分组;在DTN 模式中，利用位置信息选择合适的转发节点，当网络连通时，切换至贪婪转发模式。

2 基于卡尔曼滤波的车辆实时位置预测

车辆实时位置在VANET 数据传输协议设计中扮演着重要角色。地理位置路由通常面临转发决策所使用的位置信息时效性较低的问题［8］。如图1 所示(白色节点表示节点S 记录的邻居节点的历史位置，黑色节点表示节点的实际位置)，S 根据历史位置信息选择A 节点作为目的为D 的下一跳节点，但A 此时已离开S 的通信范围移动至A'。S 将选择B 作为下一跳，但实际上C 为当前距离D 最近的节点。

图1 地理位置路由中位置信息示意图

目前在VANET 路由算法中，常用2 种方法获取车辆位置信息:(1)利用导航系统获知一条预先设定好的车辆运行轨迹，如Geo +DTN 和GeOpps［9］。这种方法的缺陷是，导航系统给出的行进路线通常不是最优路线，而且司机必须沿着该固定线路行驶。另外，GPS 的可用性和精度问题往往被忽视［10］。(2)基于一定的运动模型进行假设或推测，如AGF［11］。由于运动模型的固有缺陷，这种方法得到的预测精度往往很低，对路由决策的帮助有限，因此使用卡尔曼预测器进行高精度车辆位置预测的方法辅助路由协议。

卡尔曼预测器是Kalman 提出的递归预测器［12］，用于从一系列噪声中递归地估计线性离散系统的状态［13］。卡尔曼预测器无需考虑多个过去的输出信号，其原理是通过现时状态观测值Yk修正现时状态预测值，根据修正结果来预测下一时刻状态预测值Xk+1，保证其同下一时刻状态实际值的均方误差最小。

考虑一个给定初始状态为X0的离散时间动态系统:

其中，wk和vk是独立白噪声过程，在k 时刻对应的协方差矩阵为Qk和Rk。

递归的卡尔曼预测方程为:

预测修正系数为:

预测均方误差为:

为预测车辆位置，假设网络中的每一辆车都装备了GPS 接收器，从而可知自身当前的位置。车辆运动可以描述为由二维位置Pos=［x y］T和速度向量Vel=［vxvy］T组成的状态向量X=［x y vxvy］T。可以看出，动态状态方程即是一个航位推演过程，预测器用同一时刻GPS 接收值即观测值来对推演结果进行修正。在实际计算中，由于动态模型不够精确描述真实运动过程、随时间累积增加的取整误差等原因，状态预测误差可能会变得很大。卡尔曼预测的结果可以认为是观测模型新测量值和基于先前所有旧测量值的预测之间的权重调节值。为提高预测精度，达到降低旧信息的权重、提高新测量值的权重，采用记忆衰减法，给预测均方差矩阵P 乘以一个衰减因子S ＞1。

为验证卡尔曼预测车辆位置的精度，利用真实车辆轨迹计算其预测位置，并衡量预测位置与真实位置的误差。实验结果如表1 所示。约有99%的预测误差小于30 m，远小于车辆的通信范围距离，这保证了基于卡尔曼预测的位置信息的可用性。

表1 卡尔曼预测精确度测试结果

3 基于卡尔曼预测的混合路由

在地理位置路由GPSR 的基础上，结合DTN 路由在稀疏网络中数据传输的优点，提出一种基于位置预测的混合路由算法KPHR。KPHR 是一种地理位置路由和DTN 路由的混合路由算法，可以在城市场景中高效的工作。KPHR 有和GPSR 类似的贪婪模式和边缘模式。除此之外，基于卡尔曼预测器的车辆位置预测和链路调度感知缓存保证了KPHR 在城市场景中具有高效性。

3.1 假设

假设每一个节点都装备了导航系统来获取自己的位置和速度，发送节点可以通过位置服务获知目的节点的位置和速度，节点会周期性广播HELLO 分组发现邻居节点。

3.2 车辆实时位置预测

网络中每个节点设置如第2 节所述的卡尔曼预测器。源节点通过位置发现服务获得目的节点的位置信息Pos 和速度信息Vel。节点发送的数据分组和HELLO 分组中带有本节点的位置信息、速度信息以及发送时间。每个节点上的卡尔曼预测器利用这些信息，周期性地计算其目标节点和邻居节点在当前时刻的预测位置和速度向量。在接下来的转发决策中，任何要求位置和速度信息的计算，都使用卡尔曼预测器计算结果，这样可以有效解决节点运动信息在路由决策中时效性低的问题。

3.3 链路调度感知的分组缓存

城市场景中节点分布极其不均，发送节点和目的节点常处于不同网络划分中，造成数据不可达，可以借助于DTN 网络存储-携带-转发的概念克服该问题。在每个节点设置一个FIFO 队列来缓存那些由于缺乏合适转发邻居而将要被丢弃的分组。每个分组维护一个计时器来标明在队列中的生存时间。缓存队列会周期性检查分组计时器并丢弃超时分组。

每当节点遇见一个新邻居节点，就计算从该邻居到目的节点的距离distnb和角度θnb，以及从本节点到目的节点的距离distn和角度θn。定义传输增益为θn与θnb之间的差和distn与distnb之间的差权重之后的和。较高的传输增益表明该分组有更高的概率传输至目的节点。节点按照传输增益将缓存中的分组按降序排序，并依次发送给邻居节点直至传输增益为负。节点邻居发现过程的伪代码具体如下:

3.4 KPHR 转发策略

当节点收到一个分组时，首先检查该分组的目的节点是否在自己的邻居表中。这会大大减轻目的节点离开初始位置的影响。然后节点会采用与GPSR 算法的贪婪模式和边缘模式类似的规则处理该分组。该步骤所使用的节点位置和速度的计算都使用预测值，具体转发策略如下:

(1)节点检查自身是否是目的节点。如果是，则节点接收该分组。

(2)否则节点检查该分组的目的节点是否是当前节点的一个邻居。如果是，当前节点发送该分组至目的节点。

(3)否则节点检查该分组的转发模式(贪婪模式或边缘模式)，并依照相应的转发策略计算下一跳节点。如果下一跳节点存在，当前节点发送该分组至下一跳节点。

(4)否则将该分组存入缓存队列。当遇见一个新的邻居节点时，按照3.3 节所述的节点发现过程进行转发。

4 性能分析

本节将KPHR 的性能和GPSR、带缓存的GPSR(GPSR+buffer)进行比较，使用分组投递率和平均端到端时延作为算法性能评价指标。GPSR 是一种典型的地理位置路由。GPSR+buffer 是在GPSR 的边缘模式下加入缓存，在贪婪模式或边缘模式下无法计算出下一跳节点时将分组存入缓存，直到能够使用贪婪模式进行转发为止，是一种简单的混合路由算法。本文使用开源的真实车辆交通生成器VanetMobiSim 生成真实车辆移动轨迹。利用TIGER (U.S.Census Bureau's Topologically Integrated Geographic Encoding and Referencing)数据库中的真实地图拓扑，选取蒙哥马利郡的一块2 000 m ×1 000 m 的街区，使该拓扑可以在NS-2中使用。设置20 条CBR 流并随机选取发送节点和目的节点。发送节点在仿真开始30 s 后开始持续发送60 s 数据。在所有分组发送后，仿真仍将运行一段时间避免出现因仿真时间结束而分组未达的状况。对任一特定的网络场景设置，均采用5 个不同的随机种子进行仿真，最终结果取平均值，具体仿真参数设置如表2 所示。

表2 仿真参数设置

图2 对比了节点移动速度为20 km/h～50 km/h时，不同节点数目下GPSR，GPSR +buffer 和KPHR的分组投递率。3 种算法各自的分组投递率开始都随着节点数目的增加而增长，直到节点数目为150时出现下降。这是因为网络的链路容量有限，节点之间的控制分组开销过大，造成网络拥塞。因为有分组缓存的存在，任意节点数目下KPHR 和GPSR+buffer 的分组投递率都高于GPSR。但GPSR +buffer 在DTN 阶段时只是简单地按贪婪条件选取转发节点;而KPHR 充分利用了节点位置信息计算投递增益，可以选择更合适的节点进行转发，从而提升网络整体效率，因而投递率远高于只有简单缓存功能的GPSR+buffer。另外，KPHR 在每跳中都会判断目的节点是否在当前节点的邻居表内，从而减轻因目的节点移动远离初始位置造成不可达的影响，也可以提升分组投递率。

图2 不同节点数量下的分组投递率

图3、图4 分别对比了节点数目为100 时，不同节点运动速度下3 种算法的平均端到端时延和分组投递率。可以看出随着节点运动速度的增加，3 种算法各自的平均端到端时延都有所增加，而分组投递率都有所降低。与GPSR+buffer 相比，KPHR 的平均端到端时延相差不大，但增长更缓慢。而任意节点运动速度下，KPHR 的分组投递率远高于GPSR 和GPSR+buffer。

图3 不同节点运动速度下的平均端到端时延

图4 不同节点运动速度下的分组投递率

5 结束语

本文针对VANET 城市场景中，道路拓扑限制和车辆高速移动导致的网络间歇连通性给路由设计带来的巨大挑战，综合考虑了地理位置路由在连通网络中端到端时延较低、DTN 路由在稀疏网络中投递率较高的优点，结合卡尔曼预测器的位置预测，充分利用车辆地理位置辅助转发决策，在GPSR 的基础上提出基于卡尔曼预测的混合路由算法KPHR。仿真结果表明，与GPSR 和GPSR +buffer 相比，KPHR在分组投递率和端到端时延方面性能较好。下一步工作将考虑网络连通性的影响，对网络连通性进行建模研究分析，优化地理位置路由模式和DTN 模式之间的切换点，进一步改善VANET 的传输性能。

［1］徐会彬，夏 超.VANETs 路由综述［J］.计算机应用研究，2013，30(1):1-6.

［2］Gerla M，Kleinrock L.Vehicular Networks and the Future of the Mobile Internet［J］.Computer Networks，2011，55(2):457-469.

［3］Wu Yuchen，Zhu Yanmin，Li Bo.Trajectory Improves Data Delivery in Vehicular Networks［C］//Proceedings of INFOCOM'11.Shanghai，China:［s.n.］，2011:2183-2191.

［4］Lee K，Yi Yung，Jeong J，et al.Max-contribution:On Optimal Resource Allocation in Delay Tolerant Networks［C］// Proceedings of INFOCOM'10.［S.l.］:IEEE Press，2010:1-9.

［5］Zhu Hongzi，Chang Shan，Li Minglu，et al.Exploiting Temporal Dependency for Opportunistic Forwarding in Urban Vehicular Networks［C］//Proceedings of INFOCOM'11.［S.l.］:IEEE Press，2011:2192-2200.

［6］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.

［7］Cheng P C，Weng J T，Tung L C，et al.GeoDTN +Nav:A Hybrid Geographic and DTN Routing with Navigation Assistance in Urban Vehicular Networks［J］.Mobile Networks and Applications，2010，15(1):61-82.

［8］Kim Y，Lee J J，Helmy A.Impact of Location Inconsistencies on Geographic Routing in Wireless Networks［C］//Proceedings of the 6th ACM International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems.San Diego，USA:ACM Press，2003:124-127.

［9］Leontiadis I，Mascolo C.Geopps:Geographical Opportunistic Routing for Vehicular Networks［C］//Proceedings of IEEE International Symposium on World of Wireless，Mobile and Multimedia Networks.［S.l.］:IEEE Press，2007:1-6.

［10］Leontiadis I，Costa P，Mascolo C.Extending Access Point Connectivity Through Opportunistic Routing in Vehicular Networks［C］//Proceedings of INFOCOM'10.［S.l.］:IEEE Press，2010:1-5.

［11］Naumov V，Baumann R，Gross T.An Evaluation of Intervehicle Ad Hoc Networks Based on Realistic Vehicular Traces［C］//Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing.Florence，Italy:ACM Press，2006:108-119.

［12］Kalman R E.A New Approach to Linear Filtering and Prediction Problems［J］.Journal of Basic Engineering，1960，82(1):35-45.

［13］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:［s.n.］，2011:119-123.