基于道路段评价机制低延时VANETs路由算法
2017-08-12吴卫祖刘利群谢冬青
吴卫祖 刘利群 谢冬青
1(广东海洋大学信息学院 广东 湛江 524088) 2(广州大学计算机科学与教育软件学院 广东 广州 510006)
基于道路段评价机制低延时VANETs路由算法
吴卫祖1刘利群1谢冬青2
1(广东海洋大学信息学院 广东 湛江 524088)2(广州大学计算机科学与教育软件学院 广东 广州 510006)
针对城市车辆自组织网络应用需求，提出一种低延时路由协议。该路由协议以城市交通网络模型为基础，首先从各道路段上寻找显著节点，然后估计显著节点之间的链路生存时间，接着从交叉口区域寻找最优的中继节点。一旦找到中继节点便开始广播道路段评价数据包，依据传输延时计算每一个道路段的权重值，最后在路由构建阶段依据道路段权重和有效期选取最优传输路径，实现数据的低延时传输。大量的仿真实验结果表明，与常用的GPSR和GPSR-R路由协议相比，该路由协议不仅端到端平均延时大幅降低，而且报文送达率高、网络开销小。
车辆自组织网络 路由协议 传输延时 链路生存时间 显著节点
0 引 言
车辆自组织网络VANETs是无线自组织网络的一种，采用携带无线通信设备的车辆作为通信节点，组建自由、灵活的无线通信网络[1]。目前城市交通环境中运行的车辆非常多，大部分车辆装配了无线通信和定位装置，为车辆自组织网络的构建提供了便利条件。通过构建车辆自组织网络，可以为车辆驾驶员或乘客提供许多便捷服务(如媒体共享)[2～4]。随着计算机网络技术的迅猛发展，车辆自组织网络的应用越来越广泛。在实际应用过程中，许多应用场合对数据传输延时提出了更高的要求，如网络接入、媒体共享和广告服务等应用场合，用户希望数据传输延时尽可能低[5]。然而，在城市交通网络中，这些需求难以得到较好满足。因为估计道路段上的车辆数量是非常复杂的，不同时段不同区域的车流密度变化很快，车辆在道路上的空间分布也不均匀，而且城市环境中障碍物也比较多，这些都会导致数据传输延时增加[6～8]。为了解决这些问题，目前也提出了有意义的路由协议，如GPSR[9]、GSR[10]、GPSR-R[11]等路由协议通过选择源节点到目的节点之间的最短传输路径来降低数据传输延时。然而，单纯依靠距离最短准则难以大幅降低数据传输延时，而且此类准则在选择最优路由时容易陷入局部最优问题。
为了进一步降低面向城市车辆自组织网络的数据传输延时，本文提出了一种基于道路段评价机制的低延时路由协议。基本思路是依据数据传输延时对每一个道路段进行评价，依据评价结果选择数据传输延时小的道路段进行数据传输，从而大幅降低数据传输的端到端延时。
1 城市交通网络模型
典型的城市交通环境常采用道路段和交叉口组成的网络模型来模拟。每两个交叉口之间存在一个道路段，每一个道路段都包含道路长度、道路宽度、车道数量、交通密度等特征。道路段上行驶的车辆组成网络的通信节点。本文假定每一台车辆都装配了GPS定位装置，可以提供车辆的位置、速度、方向以及一个包含道路段及交叉口等细节信息的数字地图。在转发数据包时，源节点可以通过查询定位服务去获取目的节点的位置。
无线自组织网络常采用无向图模型G(V,E)来描述，其中，V表示无向图模型中的顶点集合，也即网络中的车辆节点。E表示无向图模型中的边的结合，也即两台车辆之间的无线通信链路。
P=Vi→V1→…→Vn→Vj
(1)
2 本文方法
本文方法的设计目标是降低数据传输的端到端延时，以便在车辆自组织网络中快速传输数据，主要用于对延时比较敏感的场合，如网络接入、媒体共享和广告服务等。本文方法主要包括五个部分，分别是显著节点生成、链路生存时间估计、中继节点选择、道路段评价和路由构建，详细描述如下。
2.1 显著节点生成
每一条道路段可能存在很多车辆，这些车辆有些是在数据传输过程中作用重大的显著车辆，有些是对数据传输作用不大的普通车辆。那么，我们需要寻找每一条道路段的显著车辆，生成显著节点。在这一过程中，车辆通过信标服务交互信息，交互信息内容为:
M=ID,x,y,v,θ,c,f
(2)
其中，ID为车辆的唯一标识符，(x,y)表示车辆的位置坐标，v表示车辆的速度，θ表示车辆的方向，c表示车辆的显著属性，如果车辆为显著车辆，则c=1，否则c=0。f是一个稳定因子，计算方式为:
(3)
其中，vn和dn分别表示当前车辆的所有一跳邻居车辆的平均速度和平均距离，R表示车辆的通信范围。
在式(3)中，第一项反映了当前车辆的一跳邻居车辆与其相对速度值，该值越大，说明当前车辆的速度相对于其邻居车辆的速度越小，这样车辆在行驶过程中通信链路中断的可能性越小，稳定性越好。第二项反映了车辆的相对位置关系，当前车辆与一跳邻居车辆的相对距离越小，通信链路中断的可能性越小。
当车辆接收到信标消息之后，建立一个一跳邻居列表。列表的每一个入口包含了从信标中获取的信息。一旦发现一个新的邻居，就增加一个新的入口。一台车辆需要等待两个连续的信标间隔来监听其邻居。如果没有接收到消息，将删除对应的邻居入口。一旦建立了邻居列表，每一个通信节点都要计算稳定因子f，并与其邻居节点的稳定因子进行比较。然后选取稳定因子最大的节点作为显著节点，并将对应的显著属性c置为1。
2.2 链路生存时间估算
本节所述的链路生存时间是指两个显著节点之间的链路生存时间，估算该时间的目的是预测该链路发生中断的时间。
令Vi(d)和Vj(d)表示两个连续的显著节点。首先，我们比较两台车辆的行驶方向，如果它们的行驶方向相同，则链路中断会发生在两者的距离超过车辆通信范围R之后，因此，链路生存时间应为:
(4)
其中，Di,j表示节点Vi(d)和Vj(d)之间的欧氏距离，也即:
(5)
如果节点Vi(d)和Vj(d)的行驶方向不同，则需要考虑两种情况：
第一种情况是节点Vi(d)和Vj(d)相互接近。这样，链路中断发生在两台车辆相交叉且距离超过车辆通信范围，此时链路的生存时间为:
(6)
第二种情况是节点Vi(d)和Vj(d)背向行驶，越离越远。这种情况下，链路中断发生在两台车辆的相对距离超过车辆通信范围，此时链路的生存时间为:
(7)
需要说明的是，链路的生存时间也存储在车辆的邻居列表中，在每一次信标服务过程中计算和更新。
2.3 中继节点选择
前面所述的显著节点都定义在道路段上，而不同道路段上的显著节点之间无法连通。为了连通这些节点，本文在两道路段的交叉口定义一个中继节点。中继节点的选择方法是：
Step1寻找道路段交叉口区域的所有车辆，将其作为候选的中继节点；
Step2剔除那些已经驶过交叉口中心的车辆，因为这些车辆即将离开交叉口，不适合作为中继节点；
Step3从剩余节点中筛选出显著属性为1的节点，如果没有，则保留所有剩余节点；
Step4从余下的节点中选择行驶速度最慢的节点，因为速度越慢的节点在交叉口停留的时间越长。
当一个中继节点即将离开交叉口区域时，需要为其寻找一个替代者。方法是：
首先，计算每一个与当前中继节点相邻的显著节点通过交叉区域的时间t1；
然后，计算当前绿灯的剩余时间t2，表示为:
t2=tg-[tα%tC-(tC-tg)]
(8)
其中，tα表示车辆到达红绿灯的时间，tg表示绿灯持续时间，tC表示绿灯的循环间隔。“%”表示整除运算。
如果t2>t1，我们选取t1最大的节点作为中继节点。否则，我们在红灯亮时从显著节点集合中已经停止的车辆中选取一个距离交叉区域边界最近的节点作为中继节点。
2.4 道路段评价
在交叉口区域，一旦选定了中继节点，就开始进行道路段评价。道路段评价是后续路由构建的依据，用于评价该道路段作为路由路径的优先级。道路段评价的方法是：
首先，在中继节点处建立路由表，便于数据转发。
然后，中继节点生成一个道路评价数据包并在所有道路段上进行广播。道路评价数据包用于收集道路段的相关信息，如数据包延时和跳数量，数据包格式如图1所示。
图1 道路评价数据包格式
在图1中，时间戳指明了道路评价数据包的创建时间，delay表示数据包延时，具体为:
(9)
其中，n为一个道路段上的显著节点数量，delayVi表示第i个显著节点vi的数据包延时。
每一个节点的数据包延时都包含两个部分，一是数据的传输延时，二是队列延时。
当某一个显著节点接收到道路评价数据包之后，它对道路评价数据包进行修改，修改内容包括两个部分，一是在跳数量子项中加入该节点，二是更新数据包延时，即在原有延时的基础上增加该节点的数据包延时。更新之后，再将道路评价数据包转发给下一个显著节点，直至到达下一个中继节点。
中继节点在接收到道路评价数据包之后，计算道路评价数据包的传输延时t3，计算方法是用该中继节点接收到道路评价数据包的时间减去道路评价数据包上的时间戳。
记道路评价数据包的传输延时上限和下限分别为Tup和Tdown。对于一个长度为L的道路段，其可以容纳的最大显著节点数量为:
(10)
其中，Int()表示取整数运算。
那么，数据包延时下限Tdown可以表示为:
(11)
其中，Tt表示节点的传输延时。
数据包传送延时上限Tup可以表示为:
Tup=Tdown-t1
(12)
如果t3
(13)其中，t4表示该道路段的平均车辆通过时间，可以由该道路段的长度除以该道路段上所有车辆的平均速度计算。
考虑到权重与延时相关，需要为其计算一个有效期，用于描述该权重是否有效。第i个道路段权重的有效期可以由该道路段上所有链路的最小生存时间来表示，即:
Validi=min(lf1,lf2,…,lfk)
(14)
其中，k为该道路段上的链路数量。
在得到所有道路段的权重之后，每一个中继节点构建一个路由表，用于后续的路由构建。
2.5 路由构建
当源节点需要发送数据给目的节点时，它生成一个路由请求数据包，该数据包一般包含源节点ID、目的节点ID和目的节点位置。源节点转发该路由请求包给其所在道路段上的所有中继节点。对于每一个中继节点，当其接收到源节点发送的路由请求包之后，首先检查其路由表，查看该中继节点是否可以将数据送达目的节点，如果可以，它将从其路由表中选择一个从源节点到目的节点的权重最大的路径，将路由请求数据包转发给目的节点。
路由路径的权重可以表示为:
(15)
其中，m为该路径所经过的道路段数量，Wi表示第i个道路段的权重，依据式(13)计算。路径上所有道路段的权重之和越大，数据传输的端到端延时越小。
由于中继节点不止一个，因此目的节点可能接收到多个路由请求数据包，也即存在多条数据传输路径。这种情况下，目的节点将所有路径存储在路由表中，同时存储路径所对应的有效期，路径有效期的计算公式为:
(16)
其中，Validi表示第i个道路段权重的有效期，依据式(14)计算。
然后，目的节点选择权重最大的路径，将其放进路由应答数据包，回传给源节点。当源节点收到路由应答数据包之后，即可开始发送数据给目的节点。
在数据发送过程中，中继节点在数据转发过程中更新传输路径的权重，路径权重会逐渐降低，当路由的有效期结束或者路径的权重低于阈值WT时，源节点重新发起路由请求，建立新的路由。
3 实验仿真与分析
车辆自组织网络常用的仿真软件是Network Simulator[12]软件，本文在该软件上仿真本文路由协议和常用的GPSR、GPSR-R路由协议，测试常用的端到端平均延时、报文送达率和网络开销三个指标[13]，依据这三个指标评测三种路由协议的性能，仿真软件的相关参数见表1所示。下面首先分析本文路由协议的参数取值，然后再对比不同路由协议的性能指标。
表1 仿真软件相关参数
3.1 参数分析
本文路由协议涉及一个阈值参数，为权重阈值WT。当该参数取值不同时，数据传输的端到端平均延时是不同的。图2给出了本文路由协议的端到端平均延时随权重阈值WT的变化曲线，其中数据包产生速率为5个/s。
图2 端到端平均延时随权重阈值的变化曲线
由图2可见，权重阈值WT太小或者太大时都会导致端到端平均延时增加。因为权重阈值WT太大时，在数据传输过程中路由路径的权重会很快下降到权重阈值WT之下，这样就需要重新发起路由请求，尽管数据在路由路径上的传输延时较小，但由于频繁构建路由，导致整体的端到端平均延时增大。而当权重阈值WT太小时，尽管路由请求次数较少，但是，在数据传输过程中路由路径上的权重越来越小，导致数据传输延时越来越大，从而也会导致整体的端到端平均延时增大。由图2可见，当WT=120(ms)时，数据传输的端到端平均延时最小。因此，本文取权重阈值WT=120(ms)。
3.2 性能对比
本文路由协议的设计目标是尽可能降低数据传输的端到端平均延时，用于服务媒体共享、广告接入等低延时需求的应用。因此，本文路由性能最关注的性能指标是数据传输的端到端平均延时。但同时，报文送达率和网络开销也是车辆自组织网络服务质量的重要评价指标。因此，这里对这三项指标分别进行评价(如图3-图5所示)，然后给出综合评价结果。
图3 端到端平均延时随数据包产生速率的变化曲线
图3给出了数据包产生速率不同时三种路由协议的端到端平均延时指标。可见，尽管本文路由协议的端到端平均延时指标也会像其他两种方法一样随着数据包产生速率的增加而增加。但是很明显本文路由协议的端到端平均延时指标随着数据包产生速率增加的上升速率较低，而且在同等条件下的端到端平均延时都远小于其他两种路由协议。这是因为本文路由协议以路由路径的传输延时最小(也即路由路径的权重最大)为路由选择依据，因此本文路由协议的端到端传输延时要明显小于其他两种路由协议。
图4 报文送达率随数据包产生速率的变化曲线
图4给出了三种路由协议的报文送达率指标随数据包产生速率的变化曲线，可见在同等条件下本文路由协议的报文送达率指标也高于其他两种路由协议。这是因为本文路由协议在各道路段有效期结束后会重新构建路由，路由稳定性好。因此在大幅降低端到端平均延时的情况下，还能够提高报文送达率指标。
图5 路由开销随数据包产生速率的变化曲线
图5给出了三种路由协议的路由开销指标随数据包产生速率的变化曲线。同样，相同条件下本文路由协议的路由开销要小于其他两种路由协议，数据包产生速率越大，本文路由协议的优势越明显。这是因为本文路由协议在数据传输过程中路由请求次数较少，路由稳定性较好。
综合分析端到端平均延时、报文送达率和路由开销三个指标，本文路由协议在大幅降低端到端平均延时的情况下，路由开销也随之降低，报文送达率指标也有提高，优于其他两种常用的车辆自组织网络路由协议。
4 结 语
针对城市交通场景下网络接入、媒体共享和广告服务等对延时比较敏感的应用场合，本文提出了一种基于道路段评价机制的车辆自组织网络路由协议。该协议通过显著节点生成、链路生存时间估计、中继节点选择、道路段评价和路由构建五个阶段，实现低延时路由的构建。实验表明，本文提出的路由协议可以大幅降低数据传输的端到端延时，同时路由开销小、报文送达率高，是一种低延时的城市车辆自组织网络路由协议。
[1] 吴怡, 沈颖祺, 沈连丰,等. 基于协议序列的车辆自组织网络信道接入控制算法[J].电子学报, 2012, 40(4):826-831.
[2] Wang S S, Lin Y S. PassCAR: A passive clustering aided routing protocol for vehicular ad hoc networks[J]. Computer Communications, 2013, 36(2):170-179.
[3] 姚宏, 滕超, 丛磊,等. 车辆自组织网络中使用公交车辆协助的数据分发[J]. 计算机工程与科学, 2014, 36(11):2114-2118.
[4] Li Y, Boukerche A. QuGu: A Quality Guaranteed Video Dissemination Protocol Over Urban Vehicular Ad Hoc Networks[J].Acm Transactions on Multimedia Computing Communications & Applications, 2015,11(4):1-23.
[5] Campolo C, Molinaro A. Multi-channel communications in Vehicular Ad hoc NETworks: A Survey[J].IEEE Communications Magazine, 2013,51(5):158-169.
[6] Dua A, Kumar N, Bawa S. A systematic review on routing protocols for Vehicular Ad Hoc Networks[J]. Vehicular Communications, 2014,1(1):33-52.
[7] Li Y, Jin D, Hui P, et al. Revealing contact interval patterns in large scale urban vehicular ad hoc networks[J].Acm Sigcomm Computer Communication Review, 2012,42(4):299-300.
[8] Villas L A, Boukerche A, Maia G, et al. DRIVE: An efficient and robust data dissemination protocol for highway and urban vehicular ad hoc networks[J].Computer Networks, 2014,75:381-394.
[9] Ding X T, Peng X G. An energy balancing routing based on GPSR protocol[J]. Transducer & Microsystem Technologies, 2013,32(4):12-15.
[10] Behera A, Panigrahi A. Determining the network throughput and flow rate using GSR And AAL2R[J]. International Journal of Oncology, 2015, 43(2):661-669.
[11] 李超, 韩江洪, 魏振春,等. VANET 场景下的 GPSR-R 路由算法[J]. 合肥工业大学学报:自然科学版, 2015(2):181-185.
[12] The Network Simulator-ns-2[EB/OL]. 2011. http://www.isi.edu/nsnam/ns/.
[13] Daraghmi Y A, Yi C W, Stojmenovic I. Forwarding methods in data dissemination and routing protocols for vehicular Ad Hoc networks[J].IEEE Network, 2013,27(27):74-79.
ALOW-DELAYROUTINGALGORITHMFORVANETSBASEDONROAD-SECTIONEVALUATIONMECHANISM
Wu Weizu1Liu Liqun1Xie Dongqing2
1(SchoolofInformation,GuangdongOceanUniversity,Zhanjiang524088,Guangdong,China)2(SchoolofComputerScienceandEducationSoftware,GuangzhouUniversity，Guangzhou510006,Guangdong,China)
A low-delay routing protocol is proposed for application demand of city vehicle ad hoc networks. Based on the model of city traffic network, the new routing protocol look for the significant nodes on each road-section firstly, then it estimated the lifetime of links between two significant nodes, and found the optimal relay nodes on intersection. Once finding the relay node, the algorithm will begin broadcasting the road-section evaluation packet and calculate a weight value for every road-section according to transmission delay. In the end, it selects the optimal transmission path according to weight and validity of road-sections in routing building stage and achieve low-delay transmission for data. Experiments show that the new routing protocol can not only reduce the average end-to-end transmission delay significantly, but also obtain high packet delivery rate and low network overhead compared with the commonly used GPSR and GPSR-R routing protocols.
Vehicle ad hoc networks Routing protocol Transmission delay Link lifetime Significant node
2016-08-16。国家高技术研究发展计划项目(2009AA012420)；广东省科技计划项目(2014A020218016)。吴卫祖，副教授，主研领域：信息系统，网络安全，物联网，北斗通信及应用。刘利群，副教授。谢冬青，教授。
TP393
A
10.3969/j.issn.1000-386x.2017.08.048
