ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (11): 2421-2433.doi: 10.7544/issn1000-1239.2017.20170359

所属专题: 2017车联网关键技术与应用研究专题

• 网络技术 • 上一篇    下一篇

面向车载自组织网络路由的轨迹预测算法

黎阳,王哲,张楚文,戴惠辰,徐文佺,姬雪枫,万颖,刘斌   

  1. (清华大学计算机科学与技术系 北京 100084) (liyang-12@mails.tsinghua.edu.cn)
  • 出版日期: 2017-11-01
  • 基金资助: 
    华为公司创新研究计划项目;国家自然科学基金项目(61602271,61373143,61432009);中国博士后科学基金项目(2016M591182)

Trajectory Prediction Algorithm in VANET Routing

Li Yang, Wang Zhe, Zhang Chuwen, Dai Huichen, Xu Wenquan, Ji Xuefeng, Wan Ying, Liu Bin   

  1. (Department of Computer Science and Technology, Tsinghua University, Beijing 100084)
  • Online: 2017-11-01

摘要: 在车载自组织网络(vehicular ad hoc network, VANET)(也称车联网)中,基于地理位置的路由协议能够较好地适应网络拓扑的动态性变化和链路质量的不稳定性.由于位置信息需要在邻居节点间采用信标分组进行交互,信标分组间隔内的转发决策可能因车辆节点位置的移动而不准确,需要进行位置预测来修正车辆节点的位置.已有的位置预测算法存在普适性差或预测误差大的问题.针对上述问题,提出了一种新的预测算法,首次通过测量得到车辆加速度服从正态分布的结论,利用线性回归进行预测,并采用反馈机制进行结果修正.利用真实车辆轨迹进行测试,新的预测算法的预测精度大为提高.然后,提出了一种新的基于位置的即时路由协议.在该协议中,发送节点利用邻居节点位置和目的节点位置计算出转发下一跳.将新的位置预测算法加入到即时路由协议中,实时预测和更新车辆的位置.利用SUMO软件生成了基于真实地图道路轨迹的车辆运动模型,结合NS3网络仿真平台进行了仿真实验.实验结果表明:采用新的预测算法后,相比传统的GPSR协议和不带预测的即时路由协议,新方法的收包率提高、延迟下降,并且协议开销显著降低.

关键词: 车载自组织网络, 即时路由, 轨迹预测, 地理位置路由协议, 命名数据网络

Abstract: In vehicular ad hoc network (VANET), geographic routing protocols can preferably adapt to frequent topology changes and unstable link quality. Beacon messages are needed to share the positions of neighboring nodes, so forwarding decisions in the interval of successive beacon messages may be inaccurate due to the movement of the vehicle nodes. In this situation, trajectory prediction is needed to amend the positions of the vehicle nodes. Existing prediction algorithms are either lack of universality or suffered from large prediction errors. To solve the problems above, this paper proposes a new trajectory prediction algorithm, which is based on the measurement result that the vehicle accelerations obey normal distribution. The new algorithm uses linear regression to do the prediction and applies a feedback mechanism to amend error. The new trajectory prediction algorithm can greatly improve the prediction accuracy in several real trajectory trace tests. Then this paper proposes a new position based instant routing protocol. In instant routing protocol, a forwarder uses the predicted position of neighboring nodes and destination node to calculate the next hop. We apply our new trajectory prediction algorithm in instant routing to predict and update vehicle positions in real time. We use SUMO to generate real maps and vehicle trajectory traces, and use NS3 to do the simulation. Experimental results show that instant routing with the new trajectory prediction algorithm outperforms the traditional GPSR protocol and instant routing without trajectory prediction in terms of packet delivery ratio and network latency, while reducing protocol processing overhead remarkably.

Key words: vehicular ad hoc network (VANET), instant routing (IR), trajectory prediction, geographic routing protocol, named data networking (NDN)

中图分类号: