基于QoS的VANETs网络分布式协作路由算法

郑洪江，王会鲜，鲍 娟，陈 伟

(1.武汉理工大学 信息工程学院，湖北 武汉 430070；2.武汉理工大学 自动化学院，湖北 武汉 430070)



基于QoS的VANETs网络分布式协作路由算法

郑洪江1，王会鲜2，鲍 娟2，陈 伟2

(1.武汉理工大学 信息工程学院，湖北 武汉 430070；2.武汉理工大学 自动化学院，湖北 武汉 430070)

针对VANETs中车辆节点的高速移动性导致网络的拓扑结构频繁变化、通信链路频繁断裂，严重破坏了数据传输的可靠性和稳定性，极大降低了网络性能的情况，提出一种适用于VANETs的QoS分布式协作路由算法(LETB-AODV算法)。该算法在AODV路由协议的基础上进行扩展，用链路连接失效时间(LET)和有效带宽来建立双重约束，通过选用最大 LET的链路构建最优通信路由路径。仿真结果表明，LETB-AODV协议比AODV协议能够更有效地降低链路断链率、丢包率和路由开销，从而提高通信链路的稳定性，增强网络可靠性。

协作通信；QoS路由；链路连接失效时间；有效带宽；分布式算法

车载网(vehicular ad hoc networks，VANETs)是一种特殊的移动自组织网络(mobile ad hoc networks，MANETs)，具有自身独特的特性，如车辆节点的高速移动性和运行轨迹的有限性等。这些特性导致了网络的拓扑结构频繁变化、通信链路稳定性差，限制了车辆间的直接通信距离及网络信息传输的有效性。近年来，随着车载应用需求的不断升级和车载应用业务的不断拓展，人们对车载网络的通信性能也提出了更高的要求。现有VANETs性能研究多是针对节点间单跳通信性能展开，如考虑通信信道性能损失、节点间信道竞争机制，对基于WAVE协议的VANETs网络通信性能研究等。为进一步提高网络性能，人们提出在车载网络中采用多跳传输方式增加网络连通度，提高通信容量。在多跳VANETs中，数据经多跳传递到达目的节点，而随着多跳通信数目的增加，网络的性能快速下降。因此，需要提供稳定、可靠的路由机制作为前提条件来实现VANETs中车辆的高效、实时通信。

不失一般性，自组织网络中节点的高速移动，增加了网络链路断裂的机率，也导致控制开销的剧增。控制开销消息主要有RREQ(route request)和RERR(route error)。在高速的VANETs中，频繁的链路断裂导致路由请求消息剧增，给网络添加额外流量负担，极大降低了网络性能，严重破坏了数据传输的可靠性和稳定性。因此，传统的路由算法不适用于VANETs。为此，研究者提出了不同的方案对现有路由协议算法进行补充、完善和改进，以适应VANETs网络的性能需求，如基于链路预测移动模型的路由算法[1-2]，基于车辆的位置、方向、速度和交通状况等参数选择的高速环境下的路由算法[3-4]，基于链路稳定度的路由算法[5-7]，基于QoS的路由算法[8]，基于协作跨层协议的路由算法[9-10]。上述方案在一定条件下表现出了较好的路由性能，然而都是基于某些特定的假设条件，如车辆速度的正态分布、车辆节点间等距分布，与真实的VANETs环境不符，且链路的信息交换与预测使控制开销加大，降低了网络吞吐量，普适性较差。

因此，为有效增强VANETs网络车载终端间通信的可靠性和稳定性，笔者提出一种适用于VANETs的QoS分布式协作路由方案。该方案在AODV路由协议基础上进行扩展，构建基于LET和有效带宽双重约束的最佳路径选择策略(简称为LETB-AODV路由协议)，为VANETs网络车载终端间通信选择稳定、可用持续时间长的路径建立路由，有效降低了路径的断裂率，提高了网络性能。

1 网络模型及问题描述

笔者将VANETs网络用网络图G(V,E)表示，其中V={v1,v2,…,vn}表示网络中n个移动车辆节点集合，E={e1,e2,…,em}表示网络中m条链路集合，V和E随着网络拓扑的动态变化而变化。笔者假定每个车辆节点具有相同的传输距离，当节点i位于节点j的传输范围内时，i与j成为一对邻居节点并且它们之间存在一条传输链路eij(i,j∈V,eij∈E)。

将VANETs网中的QoS路由问题定义为：给定一个网络G(V,E)和一个QoS 路由请求R=(S,D,Bmin,LETmin)，在节点S与节点D之间寻找一个可行路径集P*，使得BP(S,D)≥Bmin，LETP(S,D)≥LETmin。其中S为QoS 路由请求R的源节点；D为QoS 路由请求R的目的节点；Bmin、LETmin分别为QoS有效带宽、LET的约束条件；BP(S,D)、LETP(S,D)分别为路径P(S,D)上的可用带宽、链路连接持续时间，且P(S,D)∈P*。

笔者的目的是在VANETs协作通信网络中，设计路由机制进行路径选择，保证网络节点之间的数据通信。具体做法是首先寻找满足BP(S,D)≥Bmin的可行路径；其次计算各条可行路径的LET，由大到小排序；最后选择LET最大的链路组建为主要路由，并得到备用路由，便于主路由中断时进行最快速度的路径替换和路由恢复，从而提高路由的稳定性及通信容量。

2 LETB-AODV协议

路由路径与场景示意图如图1所示，在双向四车道的十字路口，车辆S欲将数据包传送给目标车辆D。在S、D之间有若干辆车，如{A,B,C,E,F}。若S、D的间距大于彼此的通信距离，或S、D之间可通信但通信性能较差时，需要在S、D之间选择辅助节点建立可靠的链路以有效传递数据，如路径(S,A,D)、(S,B,D)、(S,A,C,D)等。考虑到网络拓扑的复杂性，每条链路只通过一个辅助节点帮助传输。因此，选择合适的辅助节点以获得具有较好的可用带宽、LET的最佳通信路径，成为组建具有QoS保障路由协议的关键。

图1 路由路径与场景示意图

2.1 有效带宽

协作通信方式可有效降低系统中断概率、增加分集增益和系统容量。研究表明，DF协作模式可以获得比直接传输模式更高的带宽[11]。如图1所示，当S、B、D在彼此的通信范围内，车辆B作为S、D间所选择的辅助节点(Helper)，辅助节点组成的节点集记为H={H1,H2,…,Hn}。若通过解码转发(DF)协作机制来实现数据的协作传输，即假设每帧通过两个时隙传输：第一时隙中，源节点S广播消息至节点H和D，称为数据包的广播阶段(如链路eSB、eSD)；第二时隙中，节点H将收到的信息重新编码后传输到目标节点D，称为数据包的协作传输阶段(如链路eBD)。双时隙DF协作传输和直接传输的信道容量分别为[12]：

Ccoop(S,H,D)=W×Icoop(S,H,D)

(1)

lb(1+SINRSD+SINRHD)}

(2)

Cdir(S,D)=W×lb(1+SINRSD)

(3)

(4)

式中：W为信号带宽；N0为白噪声；α为路径损耗因子；dij为节点i与j之间的距离。

路径P(S,D)的可用带宽计算如下：

BP(S,D)=Ccoop(S,Hi,D)×ATF(S,Hi,D,R),

i∈F

(5)

式中：R为QoS路由请求；BP(S,D)为路径P(S,D)的可用带宽；Ccoop(S,Hi,D)为协作模式下将节点Hi作为辅助节点传输的链路eiD的信道容量；ATF(S,Hi,D,R)为相同条件下链路eiD的可用时隙(available time fraction，ATF)，其中节点Hi可以为空，表明对应链路为直接传输模式。

2.2 链路连接可持续时间(LET)

(6)

假定从t0到t这段时间内，车辆保持匀加速运动，则B与S、D与B间在时刻t的距离可表示为[13]：

dBS(t)=dB(t)-dS(t)=(vB(t0)-vS(t0))t+

0.5(aB(t0)-aS(t0))t2+d0

dDB(t)=dD(t)-dB(t)=(vD(t0)-vB(t0))t+

(7)

当dBS(t)<0或dDB(t)<0，则表示车辆S超越B，或B超越D，此时B已没必要作为辅助节点参与S与D之间的协作通信，eSB、eBD链路断裂；当dBS(t)>300或dDB(t)>300，则S与B或B与D之间因距离过远，超出彼此的通信范围，导致eSB、eBD链路断裂。因此，eSB、eBD链路的可用持续时间LETtBS、tDB分别为方程dBS(t)=300和dDB(t)=300的解，这里假设在时刻t时车辆B仍能作为车辆S和D的辅助节点参与通信。令ΔvBS=vB(t0)-vS(t0)，ΔvDB=vD(t0)-vB(t0)，ΔaBS=aB(t0)-aS(t0)，ΔaDB=aD(t0)-aB(t0)，则可得：

(8)

其解即为eSB、eBD链路的可用持续时间：

(9)

(10)

则可得车辆S与D之间协作通路的可持续时间为：

LET(S,B,D)=min{tBS,tDB}

(11)

2.3 协作节点的选择

采用协作方式来提高链路传输能力时，需要在多个节点中选择最优的辅助节点，在源节点与目标节点间建立一条通路。在笔者提出的协作式路由算法中，最优辅助节点的选取基于以下3个条件：

(1)路径P(S,D)的有效可用带宽BP(S,D)满足如下QoS约束条件：

BP(S,D)≥Bmin

(12)

(2)所选节点与源节点和目标节点属同一个行驶方向，并在源节点和目标节点的通信范围内，这样的节点称为逻辑辅助节点。

(3)源节点、目标节点与逻辑辅助节点可能形成的链路称为逻辑链路，用LET(S,Hi,D)值的大小表示这条逻辑链路的可持续时间，Hi∈Log(S,D)。如图1所示，节点S和D的逻辑链路有LET(S,A,D)和LET(S,B,D)等。具有最长的逻辑链路持续时间LET的节点成为辅助节点：

Hi∈Log(S,D) and max{LET(S,Hi,D)}

(13)

其中，Hi为节点S和D所选择的辅助节点；{LET(S,Hi,D)}为节点S和D的逻辑链路的可持续时间。

依据上述原则选择辅助节点，从逻辑链路中选用LET最长的链路，构成最稳定的传输路径。但是，具有最长的LET并不一定具有最大的有效带宽，即不一定具有最大的信道容量。具有最大信道容量的路由路径可通过式(14)计算：

(14)

2.4 算法设计与实现

在协作路由算法设计中，通常有集中式和分布式两种方案。集中式方案虽可选出最优协作式路由，但在实际网络中的可行性却很低，因此，笔者提出了分布式路由算法来解决协作式通信问题。根据网络部署的实际情况，协作节点同时从源节点和目标节点的一跳邻居节点间选取。

基于QoS的VANETs分布式协作路由算法具体描述如下：

输入：网络G(V,E)，每条链路的SINR和ATF，路由请求R=(S,D,Bmin,LETmin)及相应的带宽和LET要求Bmin和LETmin。

输出：协作路由路径P(S,D)，发现路由带宽BP(S,D)，链路可持续时间LET(S,D)。

(1)每个节点和一跳邻居通过HELLO报文交换链路信息，HELLO报文帧格式如图2所示，包括SINR和ATF；

(2)每个节点建立本地数据库以存储相邻链路的信息；

(3)源节点S检查路由表中是否有到达目的节点D的可用路由。若有，则直接发送；若无，则广播RREQ消息，RREQ消息帧格式如图3所示；

(4)如果节点Hi收到节点S发送过来的RREQ消息。则判断节点Hi是否在S相同方向上，若不在同一方向，则丢弃该消息；若在，则节点Hi计算从S到Hi的最大可用带宽BP(S,Hi)；

(5)若存在P(S,Hi)使得BP(S,Hi)≥Bmin，则Hi根据式(9)计算LET(S,Hi)=tSHi，若LET(S,Hi)≥LETmin，则继续广播RREQ消息，否则S将Hi从可选辅助节点列表中移除；

图2 HELLO报文帧格式

图3 RREQ消息帧格式示意图

(6)如果目的节点D收到多份RREQ满足BP(Hi,D)≥Bmin、LET(S,Hi)≥LETmin，则根据式(10)计算LET(Hi,D)=tHiD；

(7)如果LET(Hi,D)≥LETmin，则根据式(11)计算LET(S,Hi,D)，再根据条件(3)计算LET(S,D)=max{LET(S,Hi,D)}，并选取具有最大LET的路径作为最终路由，同时返回RREP消息，RREP消息帧格式如图4所示；否则拒绝该路由请求；

图4 RREP消息帧格式示意图

(8)节点S收到RREP，邀请节点Hi加入路由，更新路由表。

可用时间信息ATF根据MAC协议通过CSMA机制周期性地监听信道忙闲程度的历史数据记录统计值来计算，表示如下：

(15)

其中，信道忙的情况包括该节点及周围邻居在收、发数据的情况。

笔者参考了文献[12]中新的HELLO报文帧格式，如图2所示。报文携带了额外的链路信息：SINR和ATF，且只与一跳邻居进行交互，即TTL为1。

其中，报文携带了额外的链路信息，如SINR和ATF；HELLO报文只与一跳邻居进行交互，因此其TTL为1。

在当前路由表中没有满足需求或对应路由的路由时，当前节点需要发起一个RREQ。发送RREQ后在Life time时间内，若收到RREP，则表示路由发起成功；若在Life time内没有收到任何RREP，则发送一个路由失败消息给高层。为发现满足带宽和链路可持续时间的路径，笔者对AODV中的RREQ和RREP进行了修改。在RREQ中增加了5个新的字段，在RREP中增加了一个新的字段。RREQ和RREP的帧格式分别如图3和图4所示。

在图3中，RREQID为发送RREQ的节点序号；Speed、Location、Acceleration、Direction分别为节点在发送RREQ时的速度、位置、加速度和行驶方向；Life time为回复该RREQ的有效时间。节点S在一定时间Life time内接收来自多个逻辑节点发送的RREP消息；之后不再接收。这里LET表示上一跳链路的可持续时间，对于源节点来说，其值为链路构造初始值，设为0。这些信息随着RREQ在每一跳节点的转发而更新。在图4中，RREPID为发送RREP的节点序号；这里LET为已选择的与发送RREQ节点所形成的链路的可持续时间。

3 仿真和性能分析

3.1 实验环境设置

笔者通过QualNet 7.0对所提出的QoS跨层协作式路由协议的性能进行评估，具体仿真场景参数设置如表1所示。为了更好地研究LETB-AODV算法的性能，笔者分别从丢包率(应用层目的节点未成功接收的数据包与源节点发送的所有数据包之比)、控制开销(在仿真时间内，发送的路由控制报文总数)和链路可持续时间LET进行分析验证。实验结果分析中采用LETB-AODV协议与AODV路由协议对性能进行比较。

表1 仿真场景参数设置

3.2 仿真结果及分析

实验仿真主要用来验证车辆速度对QoS路由协议LETB-AODV的影响，仿真结果如图5～图7所示。

图5 路由路径可持续时间随车辆速度变化情况

图6 控制开销随车辆速度变化情况

图7 丢包率随车辆速度变化情况

图5描述了AODV和LETB-AODV两种路由方案路径可持续时间的变化情况。由此可知，随着车辆行驶速度的增加，两者的链路路径LET都随之缩短。这是因为车辆速度的增加，导致车距扩大的机率提高，会使原本有效链路因断裂而失效，从而引起整个路由路径的断裂，相应地缩短了路径的持续时间，这与之前的理论分析吻合。LETB-AODV路由协议基于这一原理，充分考虑了车辆移动性，并选择满足带宽需求且具有最大LET的链路组建路由路径，提高路由路径的稳定性。由图5可知，随着车辆速度的增加，LETB-AODV路由协议所选择的路由其链路的持续时间明显高于AODV路由协议，提高幅度最低为3.16%(车辆速度为15 m/s)，最高可达40.9%(车辆速度为30 m/s)。

图6描绘了控制开销随车辆速度变化情况。通常节点数目越多，移动速度越快，链路越容易发生断裂，需要不断重启路由请求，导致控制报文拥堵，路由开销增大。从图6可知，LETB-AODV路由协议的控制开销远小于AODV协议。这主要是因为LETB-AODV路由协议中辅助节点的选择是从同一个方向的车辆中选取，且该协议有QoS保障机制，基于满足QoS带宽要求和最长LET链路构建路由，这些均降低路径的断裂率，路由请求的次数相应减少，从而大大减少了控制开销，保证了其优于AODV路由协议的路由开销性能。

图7描述了丢包率随车辆速度的变化情况。可以看出，LETB-AODV和AODV协议的丢包率均随节点速度的增大而增大。这是因为车辆速度的增加，会使链路上节点因自身较快脱离邻近节点的通信范围而导致稳定链路断裂，丢包率上升。然而由于LETB-AODV协议的QoS保障机制，建立的多路径路由稳定性更高，丢包率随着车辆速度的增大而上升得比较缓慢。该结果直观地验证了LETB-AODV协议的有效性。

4 结论

笔者充分考虑VANETs网络中车辆高速移动、网络拓扑不断变化、路径的稳定性差和运行轨迹有限等属性，提出一种适用于VANETs的QoS分布式协作路由算法(LETB-AODV算法)。该算法在AODV路由协议基础上进行扩展，选取链路连接失效时间(LET)和有效带宽这两个最重要的通信指标作为服务质量度量参数来建立双重约束，进行最优路由路径选择。通过QualNet 7.0仿真模拟VANETs中传统的AODV协议和LETB-AODV协议路由决策情况，验证了LETB-AODV相比AODV 更能够有效地降低链路断链率、丢包率和路由开销，从而提高通信链路的稳定性，增强网络的可靠性。

[1] NAMBOODIRI V, GAO L. Prediction-based routing for vehicular ad hoc networks[J]. IEEE Transactions on Vehicular Technology,2007,56(4):2332-2345.

[2] 夏梓峻,刘春凤,赵增华,等.基于链路预测的VANET路由算法[J].计算机工程,2012,38(4):110-114.

[3] WEDDE H F, LEHNHOFF S, BONN B V. Highly dynamic and scalable VANET routing for avoiding traffic congestions[C]∥Proc. of the 4th ACM International Workshop on Vehicular Ad Hoc Networks. New York: ACM Press,2007:81-82.

[4] ABEDI O, FATHY M, TAGHILOO J. Enhancing aodv routing protocol using mobility parameters in vanet[C]∥Proc. of 2008 IEEE/ACS International Conference on Computer Systems and Applications. Washington: IEEE Computer Society,2008:229-235.

[5] PASSCOE-CHALKE M, GOMEZ J, RANGEL V, et al. Route duration modeling for mobile ad-hoc networks[J]. Wireless Networks,2010,16(3):743-757.

[6] EIZA M H, NI Q. A reliability-based routing scheme for vehicular ad hoc networks (VANETs) on highways[C]∥ Proc. of 2012 IEEE 11th International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom). Liverpool :IEEE,2012:1578-1585.

[7] NIU Z Y, YAO W B, NI Q, et al. Dereq: a QoS routing algorithm for multimedia communications in vehicular ad hoc networks[C]∥Proc. of 2007 International Conference on Wireless Communications and Mobile Computing. New York: ACM Press,2007:393-398.

[8] MANE U, KULKARNI S A. QoS realization for routing protocol on VANETs using combinatorial optimization[C]∥ Proc. of 2013 Fourth International Conference on Computing, Communications and Networking Technologies (ICCCNT). Tiruchengode:IEEE,2013:1-5.

[9] DING Z, LEUNG K K. Cross-layer routing using cooperative transmission in vehicular ad hoc networks[J]. IEEE Journal on Selected Areas in Communications,2011,29(3):571-581.

[10] KATSAROS K, DIANATI M, TAFAZOLLI R, et al. CLWPR:a novel cross-layer optimized position based routing protocol for VANETs[C]∥ 2011 IEEE Vehicular Networking Conference (VNC). Amsterdam: IEEE,2011:139-146.

[11] ZHANG J, JIA J, ZHANG Q, et al. Implementation and evaluation of cooperative communication schemes in software-defined radio testbed[C]∥ 2010 Proceedings of IEEE INFOCOM.San Diego:IEEE,2010:1-9.

[12] 费宁,冯伟,陈春玲,等.多跳无线网络跨层协作式路由协议实现和性能分析[J].计算机应用研究,2013, 30(9):2839-2842

[13] 徐会彬,夏超.车辆自组织网络中基于稳定路径的路由协议[J].计算机工程,2013,39(12):60-64.

ZHENG Hongjiang:Doctorial Candidate; School of Information Engineering, WUT, Wuhan 430070, China.

[编辑：王志全]

Distributed Cooperative Routing Algorithm Based on QoS in VANETs

ZHENGHongjiang,WANGHuixian,BAOJuan,CHENWei

In VANETs, high-speed mobility of vehicles always lead the network topology to change dynamically and communication link to fracture frequently, which severely damaged the reliability and stability of data transmission and greatly reduced the network performance. In this paper, a kind of distributed cooperative routing algorithm based on QoS (LETB-AODV routing algorithm) for VANETs was proposed. This protocol, extended from AODV routing protocol, used link expiration time (LET) and available bandwidth to establish the double constraints, and chose the maximum LET link as the optimal routing path of communication. The simulation results show that the performances of LETB-AODV protocol are better than AODV protocol in packet loss rate, routing overhead, LET, consequently demonstrating the enhancement of path-routing link stability and network reliability with distinct superiority.

cooperative communications; QoS routing; link expiration time (LET); available bandwidth; distributed algorithm

2015-03-30.

郑洪江(1980-)，男，湖北武汉人，武汉理工大学信息工程学院博士研究生.

国家自然科学基金资助项目(51268051)；国家高技术研究发展计划基金资助项目 (2013AA122403).

2095-3852(2015)05-0542-06

A

TP393

10.3963/j.issn.2095-3852.2015.05.004