基于锚节点的车载网地理路由算法

摘要：车载网络存在节点移动速度快、拓扑结构变化迅速等特点，直接利用全球定位系统（GPS）进行定位存在误差大和路由连通率低等问题因此现有的基于地理位置的路由算法包递率不高，无法提供可靠路由提出一种基于锚节点的车载网地理路由算法（GRAN），利用城市路灯作为锚节点，车辆通过锚节点定位自身位置，结合道路网关及中心数据，建立分层次的路由结构通过这种方式，GRAN去除了路由发现过程及全网广播，达到降低路由开销、提高路由效率和包递率的目的利用NS2软件，选取接近现实的城市场景仿真实验结果证明，与典型的基于地理位置的路由协议如贪婪转发与周边转发相结合的无状态路由（GPSR）和图形源路由（GSR）协议相比，GRAN能以较低的负荷提供较低的平均时延、较高的包递率和吞吐量

关键词：车联网； 地理位置路由； 分层； 锚节点； 定位

中图分类号： TP393 文献标志码：A

0引言

车载网通过车辆与车辆之间、车辆与道路基础设施之间交互，实现车辆与公众网络通信的动态移动通信系统，为事故预警、交通信息查询及Internet接入等提供服务[1]车载网作为智慧交通的重要组成部分，近年来已经成为许多高校和科研机构的研究热点

目前，已有大量研究人员针对车载网路由算法进行了深入的研究，其中主要分为以下几类：基于拓扑的路由协议如无线自组网按需平面距离矢量路由（Ad Hoc OnDemand Distance Vector routing，AODV） 协议[2]，动态源路由（Dynamic Source Routing，DSR） 协议[3]，目的站编号的距离矢量（Destination Sequenced Distance Vector，DSDV）路由协议[4]等；基于地理位置的路由协议如贪婪转发与周边转发相结合的无状态路由（Greedy Perimeter Stateless Routing，GPSR）协议[5]，图形源路由（Graphic Source Routing，GSR）协议[6]等；基于概率预测的路由协议如车辆辅助数据交付（Vehicle Assisted Data Delivery，VADD）协议[7]，可靠和高效的报警消息路由（Reliable and Efficient Alarm Message Routing，REAR）协议[8]等

车载网路由算法大多是基于移动自组织网络（Mobile AdHoc NETwork，MANET）中的路由机制然而车载网络不同于MANET，由于车辆节点的快速移动，拓扑变化迅速，受路边障碍物影响，车辆间的连通率低，因此基于拓扑的路由协议在车载网中的性能无法到达理想状态[9]由于无需动态维护路由表，基于地理位置的路由协议在路由效率上比较突出，目前国际上车载网路由协议的设计也主要集中在利用地理位置信息上[10]，典型的地理位置路由算法有GPSR和GSR其中GPSR是贪婪转发策略和图形算法的结合，路由开始时采用贪婪转发，当数据转发遇到通信空洞时转入周界转发继续路由然而GPSR需要全球定位系统（Global Positioning System，GPS）设备获取车辆节点位置信息，而且数据在转发至目的节点前需要知道目的节点的位置信息，这在实际应用中是受限的GSR则是利用电子地图获得道路拓扑结构，进而根据道路拓扑应用Dijkstra算法获得传输数据的最优路径但是GSR仅考虑道路拓扑结构，没有考虑网络状态，面对网络连通性低、障碍物多等情况，仍然无法提供可靠路由

对车载网进行分析，发现城市交通网存在如下特性：1）道路路灯间距50米且均匀分布，符合无线通信的要求；2）路灯的拓扑结构代表着道路的拓扑结构结合地理路由转发策略与IP地址分配思想，本文针对城市车载网环境提出了一种基于锚节点的车载网地理路由（Geographic Routing based on Anchor Nodes，GRAN）算法主要思想是：1）将路灯作为锚节点，车辆节点利用地面定位算法定位自身位置坐标2）对车载网进行分层，第一层为中心数据层，第二层为网关层，第三层为锚节点层锚节点保存车辆节点与其位置信息，网关层的网关节点保存车辆节点与其路段号信息，中心数据层的服务器保存车辆节点与其网关号信息3）车辆节点与邻居节点和锚节点周期性地发送hello消息，邻居节点及同一路段上的锚节点保存着车辆最新的位置信息车辆离开本路段进入下一个路段时，其对应的路段号信息将在网关节点得到更新；同理，车辆离开本网关，进入下一个网关时，其对应的网关号信息将在中心数据得到更新4）车辆转发数据时优先考虑邻居节点，如果邻居节点是目的节点则直接转发；否则转发至最近的锚节点，由本路段上的锚节点转发至目的节点如果锚节点无目的节点ID，则转交至网关节点转发，如果网关节点有目的节点对应的路段号信息，则转发至此路段对应的锚节点进行转发；否则交由中心数据转发至对应的网关号进行转发

与GPSR和GSR相比，GRAN算法具有以下优势：1）利用锚节点定位自身位置，去除GPS设备依赖，提高了定位速度；2）数据包进行转发时无需事先知道目的节点的位置，避免了路由寻找过程；3）对车载网进行分层，树状的分层结构减少了位置更新所需的通信量，同时有利快速路由，避免数据冗余发送，减轻网络负载，提高路由效率和吞吐量；4）锚节点的均匀分布有利于数据的无线传输，减少了障碍物和车辆密度对数据传输的影响，提高了包递率；5）算法有利于与现有的Internet网络整合，有着较好的扩展性

1GRAN算法描述

GRAN算法是一种将移动定位与分层路由结合起来的地理位置路由算法，其分层结构如图1所示

第一层为中心数据层，保存车辆节点与其所在网关的对应信息；第二层为网关层，保存着车辆节点与其所在路段的对应信息；第三层为锚节点层，保存着本路段内的车辆节点及其坐标信息

由于锚节点位置已知，且位置固定，车辆节点可根据无线信号传播中接收信号强度（Received Signal Strength Indication，RSSI）与距离的经验关系[11]粗略定位自身位置坐标通过周期性的hello消息交互，邻居节点与本路段的锚节点均保留车辆节点最新的位置信息当连接至网关的锚节点收到新增的车辆节点位置信息时，把此车辆节点与本路段号绑定上传至第二层的网关节点保存当网关节点收到新增的车辆与路段号信息时把车辆节点与网关号绑定上传至第一层中心数据层服务器保存每一层运行着一个定时器，超时未收到此车辆节点的信息时认为此车辆节点已经离开本层，并删除此车辆相关信息

当需要转发数据时，并不像GPSR需要以目的节点的位置信息为前提，例如当车辆节点S需要发送数据至节点D时首先查询邻居表，如果有D的信息则直接转发至D，否则转发至邻近的锚节点，锚节点查询路由表如果有D的位置信息则按照贪婪转发机制转发至D，无则转发到网关节点；网关节点如果有D对应的路段号信息则转发至此路段上的锚节点进行转发，无则转发至中心数据；中心数据如果有D对应的网关号则转发至此网关进行转发，无则回复源节点D未联网

GRAN并不发起路由寻找过程，不需要源节点事先知道目的节点的位置，充分利用锚节点地理信息以实现无状态路由

1.1车辆节点对自身的简单定位

在城市道路环境下的无线信号传输一般采用基线地面反射模型[12]，该模型是基于地面节点空间路径和数据发送端与接收端之间的地面反射路径建立的数据接收端收到的信号功率如式（1）所示：

其中：Ps是发送节点发送数据的信号功率，Ge是发送节点与接收节点直接传输数据的功率增益，ht和he分别是发送节点的发送部件和接收节点的接收部件的天线高度，ε为两节点之间的天线增益，d为发送节点与接收节点的一跳距离，Φ为噪声干扰造成的损耗

由此可知，接收端距发送端的距离越近，接收端收到的发送功率或者信号强度越大

由于本文算法中节点对自身定位的目的是锚节点根据目的节点的位置选取最小跳数的路径，从而缩短传输时延本文算法对目的节点的位置坐标精确度要求不高，误差范围在锚节点的无线通信范围内即可因此车辆节点对自身的定位算法并不采取精度较高的基于锚节点的无线移动定位算法[13]，从而降低了车辆节点的计算复杂度，加快处理数据速度

考虑到车辆节点的行驶限制在道路内测，车辆节点可以选取离自己最近的锚节点的位置坐标作为自身的坐标在车辆行驶的过程中根据接收到的锚节点信号强度来确定相距最近的锚节点，设定最近的锚节点坐标为车辆节点自身坐标，在周期性的hello消息中车辆节点向锚节点发送自己的坐标位置信息以更新锚节点路由表

1.2路由分层及主要数据结构

GRAN路由算法的第一层为中心数据层，保存着车辆节点与网关信息：车辆ID、网关号和时间戳，中心数据可以向本车载网的所有网关发送数据包

中心数据层路由表数据结构如下：

其中：ds_id表示目的节点的ID；ds_net_num表示目的节点所在的网关号；ds_ts表示目的节点的时间戳，作为更新路由的依据；nextds指向下一个目的节点的信息

第二层为网关层，保存车辆节点与路段信息：车辆ID、路段号和时间戳，网关可以向其所连接的锚节点发送数据包

网关层路由表的数据结构如下：

其中：ds_id表示目的节点的ID；ds_road_num表示目的节点所在的路段号；ds_ts表示目的节点的时间戳，作为更新路由的依据；nextds指向下一个目的节点的信息网关节点本身包含与其相连的所有路段信息，可以向所连接的路段上的锚节点发送数据

第三层为锚节点层，保存着本路段上的车辆坐标信息：车辆ID、坐标值和时间戳锚节点可以向其通信范围内的车辆节点发送数据包

其中：ds_id表示目的节点的ID；ds_x表示目的节点的横坐标；ds_y表示目的节点的纵坐标；ds_ts表示目的节点的时间戳，作为更新路由的依据；nextAc_id表示此目的节点对应的下一跳锚节点，其计算方法是从锚节点邻居表中根据坐标位置选择离目的节点最近的锚节点作为下一跳锚节点；nextds指向下一个目的节点的信息锚节点自身位置坐标已知，其邻居表中保存着其通信范围内的其他锚节点，锚节点根据目的节点的坐标信息选择最近的路径传输至目的节点

1.3地理路由建立过程

车辆节点首先定位自身的位置坐标，然后周期性向路边锚节点及邻居节点发送hello消息

如果邻居节点或者锚节点的路由表中没有此车辆的信息，则保存此信息如果有，则根据my_ts来判断是否是最新的信息，如果是，则更新此车辆信息；否则不更新，锚节同时转发hello消息至同一路段上的邻居锚节点以更新此车辆的位置信息

当连接在网关上的锚节点收到新增的车辆信息时，转发车辆信息与本路段号（车辆ID，路段号，时间戳）至网关节点保存

锚节点运行一个定时器，如果在规定的时间内没有收到车辆节点的更新信息，则认为节点已经离开本路段，并删除此车辆的位置信息

类似地，第二层的网关收到新增的车辆信息时，保存此信息，并转发车辆信息与本网关号（车辆ID，网关号，时间戳）至中心数据保存当收到更新的车辆信息时，比较时间戳以决定是否更新网关也运行着一个定时器（定时间隔比锚节点的定时器长）当定时器超时而未收到车辆的更新信息时，认为车辆已经离开此网关，并删除此车辆信息

第一层的中心数据收到新增的车辆信息时保存，收到更新的车辆信息时比较时间戳以决定是否更新数据中心同样运行着一个定时器，当超时未收到更新信息时，则认为此车辆已经离开此网络，并删除此车辆信息层次地理路由建立流程如图2所示

1.4路由决策过程

假设源车辆节点S要与目的车辆节点D通信，首先查询自己的邻居节点是否有节点D的信息，如果有，则根据车辆ID直接发送数据包至节点D；否则发送数据包至邻近的锚节点

锚节点查询路由表是否存在D对应的坐标位置信息，如果有，则根据D的坐标进行贪婪转发，选择离D最近的路径转发数据，直到发送至D

如果锚节点不存在D对应的坐标位置信息，则说明D不在此路段内，锚节点把数据包转发至网关节点

网关节点查询路由表是否存在D对应的路段号信息，如果有则将数据包转发至D对应的路段上的锚节点，由此锚节点转发至节点D

如果网关节点不存在D对应的路段号信息，说明目的车辆节点B不在此网关内，网关节点把数据包转发至数据中心

数据中心查询路由表是否存在D对应的网关信息，如果有则将数据包转发至该网关节点，由此网关节点转发数据包

如果数据中心不存在D对应的网关信息，则向源节点返回D未联网消息，路由决策过程结束

路由决策流程如图3所示

2模拟实验与性能分析

本文对GRAN算法进行仿真，并与已有的基于地理信息路由协议GPSR、GSR在数据包递率、平均点到点延迟和吞吐量进行比较分析为了得到更真实的仿真环境，模拟实验使用Network Simulator[14]（NS2）与交通流仿真器VanetMobiSim[15]相结合，模拟实际场景中的交通流状况运动场景模拟图如图4所示

道路仿真区域为2km×2km，仿真持续时间300s，节点个数分别为30、50、90、130、170、200；节点间传输半径为200m，车辆节点的运动速度为0～30m/s随机取值，传播模型为TwoRayWay，天线类型为OmniAntenna，发送速率为512kb/s，连接数为10；节点间数据传输使用UDP协议，发包类型为CBR数据包，包大小为512B

每次仿真过程独立进行，仿真实验共进行10次，最后取其平均值每次仿真过程中均设定10对节点进行数据传输从图5可以看出，随着节点数据的增多，数据包经过中间转发的次数增多，端到端平均延时均有所增加，其中GRAN的平均时延比GPSR和GSR分别要低38%和24%，且相对稳定

数据包递率（packet delivery ratio）是指被目的节点应用层成功地接收到的应用层数据包与源节点发送应用层数据包的比率从图6可以看出GRAN的包递率总体上高于GPAR和GSR，这是因为GRAN有大量的锚节点为其提供数据转发，依靠分层的路由结构提高了数据分发的成功率随着节点数据的增多，GPSR和GSR可供转发的中间节点增多，其包递率有所上升节点数目的增多导致GRAN的锚节点将会收到大量的hello消息，由于缓冲区不足将导致部分数据包被丢弃，从而导致包递率略有下降

吞吐量是指网络在单位时间内成功传送数据的数量从图7中可以看到随着节点数目的增多，三种协议的吞吐量均有所增加，在节点数目到达140左右时均趋于平稳，节点数据到达200时达到实验结果的较高水平，GRAN总体上优于GPSR和GSR

3结语

本文提出一种基于锚节点的车载网地理路由算法——GRAN，给出一种分层次组网策略，解决了因车载网络中连通率低、拓扑结构变化快而导致路由效率不高等问题通过仿真实验比较了车辆节点数目变化时三种路由算法的性能，在平均端到端延时、包递率和吞吐量方面，GRAN算法均表现出了较好的性能效果

本文算法也存在着以下不足：1）定位不够精确；2）过多地依赖道路基础设施，当车辆不在锚节点信号范围内时将失去网络连接本文的下一步工作集中在以下两点：1）利用定向天线的指向性及信号功率可调性提高定位精确度；2）利用同一路段车辆运动的规律性减少基础设施的过度依赖，从而适应基础设施稀少的路段

参考文献：

[1]WILLKE T L， TIENTRAKOOL P， MAXEMCHUK N F. A survey of inter vehicle communication protocols and their applications[J]. IEEE Communications Surveys & Tutorials，2009，11（2）： 3-20.

[2]GUPTA A K， SADAWARTI H， VERMA A K. Performance analysis of AODV， DSR & TORA routing protocols[J]. IACSIT International Journal of Engineering and Technology， 2010， 2（2）： 226-231.

[3]VALARMATHI A， CHANDRASEKARAN R M. Congestion aware and adaptive dynamic source routing algorithm with loadbalancing in MANETs [J]. International Journal of Computer Applications， 2010， 8（5）： 6-9.

[4]DIVECHA B， ABRAHAM A， GROSAN C， et al. Analysis of dynamic source routing and destinationsequenced distancevector protocols for different mobility models [C]// AMS07： Proceedings of the First Asia International Conference on Modelling and Simulation. Piscataway： IEEE， 2007： 224-229.

[5]RAO S A， PAI M， BOUSSEDJRA M， et al. GPSRL： Greedy perimeter stateless routing with lifetime for VANETS [C]// ITST 2008： Proceedings of the 8th International Conference on ITS Telecommunications. Piscataway： IEEE， 2008： 299-304.

[6]LOCHERT C， HARTENSTEIN H， TIAN J， et al. A routing strategy for vehicular Ad Hoc networks in city environments [C]// IVS 2003： Proceedings of the 2003 Intelligent Vehicles Symposium. Piscataway： IEEE， 2003： 156-161.

[7]ZHAO J， CAO G H. VADD： vehicleassisted data delivery in vehicular Ad Hoc networks [J]. IEEE Transactions on Vehicular Technology， 2008，57（3）： 1910-1922.

[8]JIANG H， GUO H， CHEN L. Reliable and efficient alarm message routing in VANET [C]// ICDCS08： Proceedings of the 28th International Conference on Distributed Computing Systems Workshops. Piscataway： IEEE， 2008： 186-191.

[9]CHANG C， XIANG Y， SHI M. Development and status of vehicular Ad Hoc networks [J]. Journal of Communications， 2007， 28（11）： 116-126.

[10]STEPANOV I， MARRON P J，ROTHERMEL K. Mobility modeling of outdoor scenarios for MANETs [C]// ANSS05： Proceedings of the 38th Annual Symposium on Simulation. Washington， DC： IEEE Computer Society， 2005： 312-322.

[11]AWAD A， FRUNZKE T， DRESSLER F. Adaptive distance estimation and localization in WSN using RSSI measures [C]// DSD 2007： Proceedings of the 10th Euromicro Conference on Digital System Design Architectures， Methods and Tools. Piscataway： IEEE， 2007： 471-478.

[12]LEBRUN J， CHUAH C N， GHOSAL D， et al. Knowledgebased opportunistic forwarding in vehicular wireless Ad Hoc networks [C]// VTC 2005Spring： Proceedings of the 61st IEEE Vehicular Technology Conference. Piscataway： IEEE， 2005， 4： 2289-2293.

[13]BAGGIO A， LANGENDOEN K. Monte Carlo localization for mobile wireless sensor networks [J]. Ad Hoc Networks， 2008， 6（5）： 718-733.

[14]The NS2 network simulator [EB/OL]. [2013-06-09]. http：//www.isi.edu/nsnam/ns/.

[15]VanetMobiSim_1_1_manual [EB/OL]. [2013-06-09]. http：//vanet.eurecom.fr/.