车载网络中基于混合地理路由协议

黄智聪

摘 要： 车载网络（VANETs）中的多跳转发仍是一项挑战工作。现存的路由协议以高数据包传递率或以低时延为目的。为此，提出基于发送和接收节点的混合地理路由协议（SRHGR）。SRHGR协议结合了基于发送节点和接收节点转发节点的选择特性，首先利用Beacon包建立一跳邻居集，再通过距离建立候选转发节点，然后利用节点距离因子和相对速度因子计算节点的权重，最后依据权重设置节点转发消息的时延，进而选择最优的转发节点。仿真结果表明，提出的SRHGR协议既降低了传输时延，又提高了数据包传递率。

关键词： 车载网络； 地理路由； 发送节点；接收节点； 转发节点； 传递率

中图分类号： TN915.04?34； TP393 文献标识码： A 文章编号： 1004?373X（2018）17?0145?04

Abstract： The multi?hop forwarding remains a challenging task in vehicle Ad Hoc networks （VANETs）. The available routing protocol either focus on the high packet transmission ratio or low latency. Therefore， a sender?receiver based hybrid geographic routing （SRHGR） protocol is proposed in this paper， in which the selection feature of sending node， receiving node and forwarding node is combined. The beacon packet is used in SRHGR protocol to construct one?hop neighbor set， and then the candidate forwarding node is established according to the node distance. The node distance factor and relative speed factor are adopted to calculate the weight of the node. The delay of node forwarding message is set according to its weight， so as to select the optimal forwarding node. The simulation results show that the proposed SRHGR protocol can reduce the transmission delay， and also improve the data packet transmission ratio.

Keywords： vehicle Ad Hoc network； geographic routing； sending node； receiving node； forwarding node； transmission rate

0 引 言

作為智能交通系统（Intelligent Transportation System，ITS）的最有前景技术，车载网络（Vehicular Ad Hoc Networks，VANETs）[1]的相关研究受到广泛关注。VANETs中网络层的多跳协议增加了节点通信范围，为车辆间的信息交互提供了平台。然而，由于网络拓扑的动态变化、无线链路的不稳定性，发现和维护稳定转发路径仍是一项挑战工作[2?3]。

对于VANETs的多跳通信[4]，地理路由协议得到广泛应用。地理路由协议无需维护全局网络拓扑信息，降低了开销。此外，全球定位系统GPS的日益普及也为地理路由协议的使用提供了平台。目前，依据选择下一跳策略的不同，地理路由协议可分为基于发送节点和基于接收节点两类[5]。

在基于发送节点的地理路由协议中，源节点是从其一跳邻居节点中选择下一跳转发节点。多数的选择指标是依据常规状态信息的交互，如周期的Beacon包。通常是利用无线媒介的单播传输（Unicast Transmission），将数据包传输至下一跳转发节点。一般地，基于发送节点的地理路由协议具有低的时延，但是它通常遭受无线信道的高误码率，路由可靠性差。

基于接收节点协议也称为机会路由协议，它通过广播模式将数据包转发至所有邻居节点。一旦接收了数据包，节点就判断自己是否可成为候选转发节点。随后，所有候选转发节点就利用基于时延等待函数竞争转发数据包。即在数据包被转发前，节点引入时延。在等待时延过程中，一旦监听到该数据包已被转发，就取消等待，放弃对转发数据包的竞争，并丢弃数据包。

基于接收节点协议利用所有邻居节点竞争产生转发节点，提高了路由可靠性。这类协议只要有一个节点能接收到该数据包，就能完成数据包的传递工作。因此，这类协议更适合高密度网络。然而，由于基于接收节点协议在每一跳都引入了等待时延，增加了端到端传输时延。因此，此类协议的关键在于如何设置合适的时延函数，缩短总体的端到端传输时延。

本文提出发送和接收节点的混合地理路由协议（Sender?Receiver based Hybrid Geographic Routing，SRHGR）。该SRHGR协议既利用基于发送节点协议的低时延特性，又结合机会路由协议的可靠性。先利用节点位置信息产生候选转发节点集，再利用节点位置、相对速度因子计算候选转发节点集内所有节点权重，并依据权重排序，最后设置每个节点的转发时延。仿真结果表明，提出的SRHGR协议提高了数据包传递率，并降低了端到端传输时延。

1 约束条件

本文提出的SRHGR协议基于以下约束条件：

1） 车辆通信范围为[R]，下文车辆与节点概念相同；

2） 每个车辆备有GPS系统，能够获取自己的位置坐标以及道路地图信息；

3） 车辆周期地广播Beacon消息，其包含节点的位置和速度信息；

4） 欧氏距离（Euclidean distance）[D]。车辆[i]，[j]的位置分别为[xi，yi]，[xj，yj]。它们之间的欧氏距离为[Dij]：

2 SRHGR协议

提出的SRHGR协议结合基于发送节点选择候选转发节点策略和分散化协调策略。首先利用Beacon包的交互，建立一跳邻居集[N]，再依据距离信息建立候选转发集[ψ]。然后计算集[ψ]内节点的转发权重[λ]，并依据权重[λ]对集[ψ]节点排序。最后引入基于时延转发理念，计算集[ψ]内节点的时延。SRHGR协议框图如图1所示。

2.1 候选转发集

首先，所有节点周期地广播Beacon包，当节点收到来自其他邻居节点的Beacon包，说明此节点在自己的一跳通信范围内，据此，将此节点纳入为自己一跳邻居集[N]。

图2描述了建立[N]的过程。节点[A，C，D，F]各自建立[N]集。如节点[B]的一跳邻居集[NB=A，C，D，F]。由于节点[E]产生的Beacon包不能到达[B]，所以节点[B]的[N]集中并不包括节点[E]。同样，节点[E]的[N]集中也不包含节点[B]。各个节点交互各自的[N]集，致使每个节点建立完备的[N]集。

如果集[ψi]内只有一个节点，即[ψi=1]时，就选用该节点作为转发消息的节点；若[ψi>1]，说明有多个可选节点，因此，需要计算这些可选节点的权重，并据此设置转发时延。

当然，肯定也会出现[ψi=0]的情况。若[ψi=0]，说明一跳邻居集内没有节点比自己离目的节点更近。在这种情况下，需利用其他的一跳邻居节点[k∈Ni，k?ψi]采取携带存储转发策略。

2.2 权 重

节点权重反映邻居节点转发数据包是否合适。在SRHGR协议中，利用距离因子和相对速度因子估计节点权重。考虑距离因子的目的在于增加每跳距离，而相对速度因子是指当前节点和候选转发节点间的相对速度。考虑相对速度因子是为了避免行驶速度过快，而不在当前节点的一跳通信范围内。

2.3 基于权重的转发时延

一旦成功接收了数据包，节点就参与竞争转发。利用节点权重，设置不同的时延，进而实现分散化协调转发。

首先，依据各节点的权重，对集[ψi]内节点进行从小到大排序。即权重越小，排序位置越靠前。权重[ω]最大的节点在集[ψi]内的位置[pc]就是第一个，即[pc=0]。具体而言，节点[j∈ψi]在集[ψi]内的排序位置为[pj]，则它所需要等待的时延[Tj]为：

式中[tf]为集[ψi]内两个连续节点的等待时延差。该值应足够大，进而使节点有足够的信道接入时间，降低碰撞概率。然而，若[tf]过大，会增加时延。为此，引用机会路由方法。候选转发节点一旦接收了数据包，就设置自己的等待时延，并等待。在等待的同时，监听周围节点是否已转发了数据包，如果已有其他节点转发数据包，则停止等待，放弃转发数据包，否则，待时延结束后，立即转发数据包。

从上述分析可知，式（7）所计算的等待时延只考虑集[ψi]节点。换而言之，若[ψi]内没有节点（[ψi=0]），则没有转发节点。再或者集[ψi]内有节点，但它们并没有收到数据包。考虑到这两种情况，并提高传输数据包的可靠性，利用一跳邻居集内的其他节点转发数据包。

具体而言，对于在一跳邻居集[Ni]内，而不在集[ψi]内的节点[k∈Ni，k?ψi]。它所需要等待的转发时延为[Tk，CBF]：

2.4 数据包转发流程

首先，节点周期地交互Beacon包。当节点需要转发数据包（源节点[i]）时就先利用所收到的Beacon包建立一跳邻居集[Ni]和转发节点集[ψi]，然后再转发数据包，并将转发节点集[ψi]嵌入数据包的首部。源节点转发的数据包格式如图3所示。

一旦接收到数据包，节点就判断自己是否在集[ψi]。若是，则查看自己在集[ψi]的位置，并依据式（7）设置等待时延。若不是，则依据式（8）设置转发时延。各节点在等待自己的时延过程中，监听其他邻居节点是否已转发数据包，若发现已有其他节点转发数据包，则停止转发，并丢弃数据包。否则，待等待时延完毕，就立即转发数据包。整个数据包的转发流程等待如图4所示。

3 性能分析

3.1 仿真平台

为了更好地评估SRHGR协议的性能，利用NS2.34建立仿真平台。选择4 km长单方向3车道的双向高速公路作为仿真模型。車辆行驶速度范围为80～130 km/h。车辆数为270。对于每个数据包，随机选择一对节点作为源节点和目的节点。具体的仿真参数如表1所示。

为了更好地分析SRHGR协议的性能，选择典型的贪婪转发路由（记为Greedy）和CBF进行同步仿真，并与SRHGR路由进行比较。

3.2 仿真结果

3.2.1 数据包接收率

数据包接收率随节点数的变化曲线如图5所示。从图5可知，Greedy路由的数据包接收率最低，特别是在低密度区域，数据包接收率极低。例如，当节点数小于150时，数据包接收率低于0.5。原因在于：Greedy路由在选择下一跳转发节点时，只考虑了距离。而CBF路由的数据包接收率较高，高于Greedy路由。与Greedy和CBF相比，SRHGR路由的数据包接收率最高，远高于Greedy路由，略高于CBF路由。原因在于：SRHGR路由从所有一跳邻居节点中择优选择下一跳转发节点，提高了数据包接收率。

3.2.2 端到端传输時延

端到端传输时延随节点数的变化曲线如图6所示。从图6可知，SRHGR协议在节点数变化期间，具有低的端到端传输时延。而CBF的传输时延较高，这主要是因为CBF在每一跳选择转发节点，都引入了等待时延，最终增加了端到端传输时延。相比于CBF路由，Greedy路由的端到端传输时延较低。原因在于：Greedy路由总是选择离目的节点最近的节点作为下一跳转发节点，降低了传输跳数。

4 结 语

本文针对车联网的数据包传输问题，提出基于发送和接收节点的混合地理路由SRHGR。SRHGR协议结合基于发送节点路由的低时延和接收节点的高可靠性。利用节点距离和相对速度估计每个候选转发节点的权重，并据此设置转发时延。仿真结果表明，提出的SRHGR协议有效地提高了数据包传递率，并降低了端到端传输时延。

参考文献

[1] YASER P， NEDA N， KRISHNAN H. Stable and fair power control in vehicle safety networks [J]. IEEE trasactions on vehicular technology， 2016， 65（3）： 1662?1675.

[2] RAYNER P， SERGIO. Experimenting broadcast storm mitigation techniques in FANETs [C]// 2016 the 49th Hawaii International Conference on System Science. Koloa： IEEE Computer Society， 2016： 5868?5877.

[3] PRATAP K， ERIC H. BAHG： back?bone?assisted hop greedy routing for VANET′s city environments [J]. IEEE transactions on intelligent transportation systems， 2013， 14（1）： 199?213.

[4] LEE K C， LEE U， GERLA M. Survey of routing protocols in vehicular ad hoc networks [J]. Advances in vehicular Ad Hoc networks： developments and challenges， 2012（21）： 149?151.

[5] TOMATIS A， MENOUAR H， ROSCHER K. Forwarding in VANETs： Geonetworking [EB/OL]. [2015?01?23]. https：//link.springer.com/chapter/10.1007%2F978?3?319?15497?8_8.

[6] FUBLER H， WIDMER J， KASEMANN M. Contention?based forwarding for mobile Ad Hoc networks [J]. Ad Hoc networks， 2003， 1（4）： 351?369.

[7] HEISSENBUTTEL M， BRAUN T， HEISSENB M. BLR： beacon?less routing algorithm for mobile Ad Hoc networks [J]. Computer communications， 2004， 27（11）： 1076?1086.

[8] ROSCHER K， MAIERBACHER G. Reliable message forwar?ding in VANETs for delay?sensitive applications [C]// 2016 International Symposium on Wireless Communication Systems. Poznan： IEEE， 2016： 199?203.

[9] ZHAO Z L， ROSARIO D， BRAUN T， et al. Topology and link quality?aware geographical opportunistic routing in wireless Ad?Hoc networks [EB/OL]. [2014?05?26]. https：//www.researchgate.net/profile/Denis_Rosario/publication/256081798_Topology_and_Link_Quality?aware_Geographical_Opportunistic_Rou?ting_in_Wireless_Ad?hoc_Networks/links/00b7d5217c14b121? eb000000/Topology?and?Link?Quality?aware?Geographical?Opportunistic?Routing?in?Wireless?Ad?hoc?Networks.pdf.

[10] ARANITI G， CAMPOLO C， CONDOLUCI M， et al. LTE for vehicular networking： a survey [J]. IEEE communication magazine， 2013， 51（5）： 148?157.

[11] REHMAN O， MOHAMED O K， HADJ B. An adaptive relay nodes selection scheme for multi?hop broadcast in VANETs [J]. Computer communications， 2016， 87（6）： 76?90.