城市环境下的一种车辆自组织网络机会路由协议

黄德玲，邱忠权，彭大芹

(1.西南交通大学 信息科学与技术学院，成都 610031; 2.重庆邮电大学 软件工程学院，重庆 400065；3.西南交通大学 交通运输与物流学院，成都 610031)

0 引 言

21世纪以来，车辆自组织网络(vehicular ad-hoc networks,VANET)区别于普通的移动自组织网络，开始受到广泛的关注[1]。随着VANET的日益成熟，网络的接入层已形成802.11p等国际标准，然而相关的路由协议却因其网络拓扑的快速变化，面临很大的挑战。

文献[2]采用了基于地理位置的众包方式来转发数据分组，采用合作众包的方式获取信息外包任务，该算法需要建设路边单元来辅助完成任务。文献[3]采用偏爱组播的方式广播数据包，在组播过程发现的路径中选择代价最小的一条作为算法所确定的路由，该算法采用改进的贪婪转发方式转发数据分组。Shukla[4]利用GPS反馈的交通实时信息建立基于道路的包转发路径，并筛选出最优的转发节点。Bilal[5]对基于地理位置的VANET路由协议进行了分析比较研究。现有城市环境下基于地理位置的车联网路由协议多是基于GPSR(greedy perimeter stateless routing)协议的贪婪转发思想来实现的。贪婪转发算法选择的转发节点是距离发送点最远的节点，这些节点往往处于无线传输半径的边缘。由于无线传输衰减和车辆高速移动，这种节点在转发过程中与源节点之间的连接断开的可能性较大，从而导致路由中断，降低路由性能。本文提出一种能感知交通密度的机会转发路由协议(traffic aware opportunistic routing protocol,TAO)，该协议将机会转发的思想引入到车载自组织网络中，根据节点的实时地理位置等信息，动态地确定收到数据包的节点作为下一跳中继节点的优先权，能在较少增加数据通信量的前提下，选拔出优秀的中继节点。在提出的算法中，结合车辆的运动特征预估车辆节点的位置信息，同时也考虑了道路上的车流量密度对数据转发可靠性的影响，结合交通流量密度来选择数据传输路径，并在此基础上实时地机会地选择中继节点。实验验证过程中，我们采用TIGER地图作为背景，选择真实的道路进行仿真实验，并随机选择网络中多对节点同时进行通信，研究TAO在传输时延、包投递成功率和路由开销等方面相对于其他几种主流路由协议的性能。

1 问题分析与系统环境

1.1 问题分析

1.1.1 建立静态路径不适合动态的拓扑变换

得益于车载电子地图，车辆自组织网络的路由协议可以依据地图信息计算出地图上2个通信节点之间沿道路形态的最短路径。传统的车载自组织网络的路由协议在产生数据包时，利用诸如Dijkstra之类的最短路径算法，计算出从数据包源节点到目的节点的最短路径[6]。因为车联网络中，车辆的行驶路线是受限的，必须按照道路的形态来移动，这种利用电子地图来计算最短路径的策略广为研究路由协议的学者们所用。然而，在车联网络中一个不可忽略的特点是，车辆并非是均匀分布在地图范围内的，一些道路上分布的车辆密度较小，不足以形成无线传输的通路，使得这类协议具有理论路由实际并不可用的风险。

1.1.2 贪婪转发限制包投递率

依据无线通信的特点，信号随着传输距离的增加会发生衰减，其衰减率取决于衰减参数的值。研究发现在通信范围内的节点不一定都能成功地收到数据包，而在通信范围之外的节点也不一定都不能收到数据包。然而，在采用贪婪转发的路由算法中，每一次转发，节点总是选择最远却具有较高传输失败率的邻居，这直接导致了丢包率增加。改进的贪婪转发算法中，一般会考虑速度与方向等因素，避免选择距离最远的邻居来确保较高的转发成功率，而那些能带来更长单跳步进长度的节点却也因此失去了转发的可能性，进而转发次数与时延随之增加。因此，在路口节点之间，采用何种方式传递数据包才能有效提高数据包的投递成功率，是急需解决的一个问题。

1.1.3 路由控制信息开销过大

在选择路口节点时候，动态的选择算法可以考虑交通密度在内的多种实时交通状态，但交通密度感知的准确度和计算开销有待严格控制。现有的很多路由算法在实现过程中，需要大量的附加信息辅以计算，这些信息均需要通过选择周期性地网络广播来实现共享，产生较大的路由开销[7]。同时，这些由于路由策略的计算需求而产生的路由控制开销，会大量消耗有限的无线网络资源，路由性能也受较大影响。因此，合理控制路由协议开销，是本方案要解决的又一个关键问题。

1.2 系统环境

本文讨论的VANET路由协议主要适用于城市环境，随着GPS系统和电子地图的普及，加之车辆节点几乎不受限的能源供给和充足的计算处理能力，我们为本文讨论的路由协议采用如下假设。

1)网络中的每一个车辆节点均配有短距离通信模块(DSRC设备)，并能通过GPS车载设备获取到自己的地理位置信息

2)每个节点能通过诸如网格位置服务(grid location service，GLS)[8]的位置服务获取其通信目的节点的位置。

3)每个节点可以通过预先植入的电子地图获取到街道的详细信息，包括与其所在路段邻接的路口的地理位置等信息。(目前许多车辆都预置了这样的信息，市面上也存在很多商用的电子地图。)

4)每个节点可以通过分布式部署的无需基础设施的交通信息系统(infrastructure-free traffic information system，IFTIS)[9]获取到实时的交通密度信息(2个相邻路口之间的车辆节点个数)。或者也可以通过车辆节点或部署在路口的传感器节点实现一个简单的分布式机制以提供此类交通密度信息，并随路由数据包一同扩散。

2 协议设计

在城市环境中进行路由选择的2个关键问题是：①如何在路口或数据包最初的产生源为数据包选择合适的转发方向，即确定途经路口序列；②如何在确定路口后为数据包选择最优的下一跳中继节点。以下从这2方面来介绍本文提出的TAO算法的基本设计思路。

2.1 密度感知的路口选择策略

把路口选择设计成动态的决策过程，而非预先静态计算，以此适应VANET变化的动态拓扑结构。动态的路口选择发生在产生数据包的源节点和位于路口的转发节点。设D是目标节点，Jc是当前交叉路口，需要选择路口的节点对相邻的所有路口Ji,i=1,2,3,…按公式(1)进行计算得分。

(1)

(1)式中：Dcd是当前计算节点与D之间的欧几里得距离；Dci是从Jc到Ji的沿道路形态的路径长度；Navg是平均车辆密度；Did是从Ji到D的沿道路形态的路径长度；Ncon是能提供节点之间良好连接度的理想车辆密度；α是路口位置离最终目的节点距离的权重因子；β是所选道路密度的权重因子，且α+β=1。通过公式(1)计算的路口得分由2个部分组成：①由待选路口与目标节点间基于道路形态的距离确定；②由连接待选路口的道路车辆密度确定，通过调节α与β的值，可以控制距离和车辆密度对路口判分过程的影响。通过公式(1)计算出的得分最高路口，被选为下一个数据包必经的交叉路口。

通过计算评估，使数据包的预置传输路径最短，同时考虑到了该路段的交通密度，路口的选择随数据包的传输动态地逐次确定，确保所选路段有足够多的车辆以形成无线通信通路。这种兼顾距离和实时交通密度的方法，使得路口选择更合理，算法也具有更好的鲁棒性。

2.2 直路数据转发策略

2.2.1 确定候选转发集

当确定了数据包的下一个必经路口之后，TAO采用机会转发的方式来完成数据包从当前节点到下一个路口的转发工作。

机会转发的第一个任务是确定转发集。现有的机会路由协议，转发集的计算都是由当前执行转发任务的节点确定，并将该集合中的转发节点按优先顺序排好形成列表，然后把该列表附加在待发送数据包中，一起发送出去。收到该数据包的节点，从数据包头部查看列表，确定自己是否处于转发集列表中，从而确定是否参与数据包转发。

TAO去掉了会带来较大路由开销的转发集字段。当前节点只需要查询自己的邻居节点表，把其中离最终目的节点最近的一个邻居选做最佳转发节点BestFor，将其ID附加于数据包的首部转发出去即可，TAO的数据包的头部如图1所示。

图1 TAO数据分组头部结构Fig.1 Packet Header of TAO

图1中，Dest是数据的最终目的ID，TarJun是通过公式(1)计算出来的最佳下一路口ID，BestFor是距离目的节点最近的邻居节点，Tag标志了节点的位置特性，如果是路口节点，该域被置为 1，否则被置为 0，Source是产生数据包的始源节点，ThisHop是当前节点，PayloadLen是数据部分的长度，SerNum是当前数据包的序列号。

设消息是从源点S到目的节点D，每个节点与D的近似度用ω(i)表示，可以通过测量i和D之间的距离来确定。则每个节点可以增加阶整数索引，且ω(1)<ω(2)<…<ω(n)，其中，n是节点数。设i的邻居节点集由Bi表示，节点i的候选转发集由Fi表示，则Fi中的节点必须满足以下2个条件：①Fi⊆Bi;②∀j∈Fi，ω(j)<ω(i)。

在直路段上收到数据包的节点，首先使用公式(2)，通过BestFor的位置信息和自己的位置信息计算自己是否位于节点i的转发集Fi中。

(2)

(2)式中：long和lat是节点自己的经度和纬度;long_B和lat_B分别是离目标节点最近的邻居节点BestFor的经纬度;r是无线传输的信号覆盖范围。通过公式(2)确定的候选节点转发集为图2所示的阴影部分，图2为候选转发集的确定，其中，C是当前节点；B是其邻居节点中离目标节点D最近的节点。

图2 候选转发集的确定Fig.2 Constructing the candidate forward list

在候选转发集中，TAO仅允许一个节点成为下一跳中继节点，转发集中的所有节点都会暂存收到的数据包，直到发现有其它节点转发了该数据包，或转发定时器触发其转发该数据包。因为只有优先权最高的节点会转发数据包，所以，设Pdi,j为节点j转发所接收到的来自i的数据包的概率，则有

(3)

(3)式中，Pti,j是数据包直接从i成功转发到j的概率。这是该时隙中的唯一转发节点，我们用具有单一吸收态的马尔科夫链描述这个过程，如图3所示。

图3 具有单一吸收态的马尔科夫链Fig.3 Markov chain with single absorbed states

在状态转换图中，每个状态表示当前接收节点，每2个状态之间的转换指的是这2个节点之间的成功传输，而吸收态指的是目的节点。如果数据包成功传输，则状态转移到下一个状态，否则，将保持在当前状态。如此循环，直至到达状态N(即目标节点)为止。因此，停留在当前状态的概率可以表示为

(4)

为之建立了一个N×N的上三角矩阵，其中元素为所有节点i到下一跳转发节点j的转移概率Pdi,j。

(5)

方便起见，把DS,D表示为

(6)

(6)式中：Q是到达目的节点之前的传输概率；R=[Pd1,NPd2,N…PdN-1,N]T表示从节点1,2，…，N-1直接发送数据包到N的概率。通过这个矩阵，我们给出在有N个节点参与转发的VANET中，确定传输次数期望值的方法如定理1，在具体应用中予以预估路由性能。

定理1在一次具有N个节点参与的转发中，从源节点到目的节点的转发次数的期望值是向量F1的第一个元素的值。其中，F=(I+Q+Q2+…)=(I-Q)-1,I是单位矩阵，l是长度为N-1的列向量，其中元素值为1。

(7)

(7)式中，从节点i经k步转移传输到节点j的概率是Qk的第i行第j列的元素值。

(8)

如此，矩阵F的第i行第j列的元素便是从状态i到状态j时的转发次数期望值。令e=FI，则e的第一个元素值便是从源节点到目的节点的转发次数期望值。

2.2.2 确定转发优先权

在机会转发方式中，转发集的构成是影响路由性能的一个重要因素。持有数据包的节点在转发时广播数据包，仅有处于当前节点转发集中的车辆节点才有可能成为下一跳中继节点，因此，一个较大的转发集可以增加转发的成功率。然而为了扩大转发集，将部分转发成功率虽高但单跳步进长度短的节点选入是得不偿失的。因此，为了最优化路由协议，需要对转发集中的节点进一步设置竞争机制，确保在增加转发成功率的同时获取更大的单跳步进长度。TAO为此设置了一个转发定时器，这个定时器使得离目标节点越近的邻居，具有越高的转发优先权，转发集中的节点按优先级的高低来启动转发，只有在优先权较高的节点未成功转发的前提下，优先级较低的节点才启动转发。为此，图2中的转发集中节点N在收到数据包时启动一个按公式(9)设定的发送定时器。

(9)

(9)式中：CB是节点C和最佳转发节点B之间的距离；CN是节点C和邻居N之间的距离；BN是节点B和邻居N之间的距离，max{BNi+CNi}表示BNi与CNi距离之和的最大值；Ni表示候选节点集中的任意一个节点；Tr是重传定时器，设置为2×Prop+D，其中，Prop是广播数据包到达目的节点并返回的传输时延,D是媒体接入层采用的随传输速率和处理时间变化的最大转发时延。节点只有在定时器时间结束但仍未收到重复数据包时，才需启动转发。通过(9)式设置的延迟转发定时器，使得B在成功收到数据包后能立刻转发，获得最高转发优先权；同时使得其他节点的定时器时间随距离最佳转发节点之间距离的递增而递增，相应的转发优先权逐次递减，以此控制转发集中的节点转发数据包的优先顺序。与此同时，每个转发集中的节点在转发数据包之前，还需要判断自己是否处于路口范围内，如果是路口节点，则设置Tag域为1，否则为0。当数据包的Tag域是由0变为1的时候，说明数据包从直路段抵达路口，此时需要启动2.1节的路口选择算法来选择数据包的下一个最佳路口，并将计算结果用于更新TarJun字段。

2.2.3 转发性能

虽然设置了转发优先权，但转发集中的节点彼此都在对方的传输范围内，且无法排除某些相距甚短的节点因存在定时器值相同或相差无几而同时发送数据包的情况。

假设车辆节点按泊松分布于道路上，网络密度为β，也即是在长度为l的道路上有k辆车的概率P(k,l)为

(10)

设无线传输范围为R，则道路上一个车辆节点传输范围内邻居节点期望个数为2βR，每个车辆节点收到数据包服从到达率为γ的泊松过程。用p0表示每个车辆节点至少有一个数据包准备发送的概率，则车辆在一个时隙内会发送数据包的概率可表示为

(11)

因此，一个即将发送数据包的节点探测到信道被占用的概率可表示为

(12)

假设转发集中的节点S和U均同时探测到系统信道是空闲的，S与U之间的距离为x，若S发送数据包给U，为了不影响U接收，则当前时隙在[-(R-x),R]都不能有数据传输。当前时隙在[0,R]的平均节点个数为βRγ，设节点V离S的距离为z，-(R-x)

Ps(z,x)=τ(1-βzγT(1-(1-e-βRτ)/2))

(13)

如此，在该时隙内发送数据包从而与节点S发出的数据包发生冲突的平均节点数为

则

(14)

因此，在泊松分布下节点U的接收范围内无节点在该时隙发送数据导致与S节点发送的数据冲突的概率可表示为

(15)

2.3 恢复策略

数据包在遭遇链接中断，即候选转发集为空的时候，立刻启动恢复策略，采用公式(16)为当前节点的邻居节点评分，包括其自身。

score(N)=m×[γ(1-d/L)+λ(v/vmax)]

(16)

(16)式中：d是被评分的节点与目标路口之间的距离；v是被评分节点的行驶速度；L是当前路段的长度，vmax是当前路段的限速；γ是长度权重因子；λ是速度权重因子，且γ+λ=1；m是方向因子，朝向目标路口行驶时设置为1，反之设置为-1。如果通过计算发现自己得分最高，则放弃该数据包的投递。

3 实验与分析

3.1 实验环境

仿真实验将TAO与GSR[10]，GyTAR[11]和E-GyTAR[12]3种针对VANET设计的路由协议对比研究。选择GSR和GyTAR是因为其较为广泛地被作为研究基于地理位置的VANET路由协议的基准参考，特别是稳定性较好的GyTAR，许多研究者都对其进行了改进和完善[13]，以设计出更可靠的高效的车载自组织网络路由协议，E-GyTAR便是其中一个对其进行改进的路由协议，而本文的工作也有部分是建立在GyTAR提出的思想理念的基础上的。

实验采用NS-2仿真器来仿真网络协议，选用VANetMobiSim的移动模型IDM_IM来产生车辆的运动轨迹，媒体控制协议采用802.11p，同时在其中实现了概率性信道衰减模型Nakagami。每一次仿真运行都随机选择网络中20%的节点作为发送和接收的通信节点对。仿真参数设置如表1所示。

表1 仿真参数设置

实验评测的性能指标包括包投递率、平均传输延迟和归一化路由开销，分别定义如下。

1)包投递率。成功到达目的节点的数据包个数和源节点产生的数据包个数的比值。

2)平均传输延迟。从源节点成功到达目的节点的数据包的平均端到端延迟。这个延迟包括在路由发现时的计算处理时延、接口队列排队时延、MAC层重传的时延、传播时延和发送时延。

3)归一化路由开销。控制分组的总流量和成功到达目的节点的数据分组的总流量的比值。对于经过多跳的控制分组，每一跳传输计算一次。

3.2 实验分析

3.2.1 包投递率的影响

在实验环境下，针对每一种协议，改变网络中车辆节点的个数，记录了每一次通信的包投递结果，计算出包投递成功率如图4所示。在所比较的4种路由机制下，包投递成功率都会随节点密度的增加而增加，这是因为密度越大，网络的联通性越好，节点之间的连接断开的可能性越小。因为TAO采用了机会的数据包转发方式，较好地利用了所有连接可能性，增大了包投递成功率，用实现数据验证了2.2小节分析的转发效率。TAO的包投递成功率明显优于GSR，是因为其摒弃了GSR的静态地路径选择机制，采用动态选择机制在包转发过程中，依据实时的网络情况来动态地逐次地确定数据包即将经历的下一条道路，确保所选路段的交通密度足以完成数据包的转发，从而大大降低了丢包率。

另外，虽然GyTAR和E-GyTAR采用了改进的贪婪转发机制，包投递成功率相比GSR有显著提高，但仍低于本文提出的TAO协议。这是因为TAO不要求所有数据包均要在交叉路口转发，交叉路口的通信流量不会随数据包总量增加而显著增加，转发冲突和因此带来的丢包率都得以有效控制。

图4 包投递成功率vs车辆节点数Fig.4 PDR vs number of vehicles

3.2.2 平均传输延迟的影响

在实验过程中，我们同时记录了4种协议运作下的平均传输时延。由于GSR对变化拓扑的适应性较差，每一次拓扑变化都会导致触发一次新的路由发现与计算过程，耗费大量计算时间。同时GSR没有考虑交通密度的因素，选路结果不能确保连接成功建立，而连接断开时导致的携带转发过程也增加了端到端时延。相比之下，GyTAR和E-GyTAR采用了改进的贪婪转发机制，能够较好地适应动态变化的拓扑，及时修正路由，减少端到端传输时延。然而数据包转发选择机制设置不当，使数据包容易陷入局部最优，之后不启用适当的恢复策略，盲目采用DTN的“携带-伺机转发”恢复机制使得大量数据包经历不适宜的携带，大大增加了端到端时延。TAO基于交通密度，精确计算转发节点，改进机会转发机制，虽然在转发过程中的计算开销较大，但是在路径选择上的优势弥补了这块时间开销。实验结果证实，在包投递率大大增加的情况下，端到端时延仍与GyTAR和E-GyTAR保持基本相当的水平，如图5所示。

图5 端到端时延vs车辆节点个数Fig.5 End-to-end delay vs number of vehicles

3.2.3 路由开销的影响

实验过程中记录了每一种协议的路由开销随网络密度的变化，并计算出相应的归一化路由开销，结果如图6所示。由图6可见，TAO虽然使用了机会转发的方式，但是由于将转发集的计算交由接收到数据包的节点自己去完成，而非由数据包携带整个转发集，其路由开销比SRPMT小许多。GSR对变化拓扑的适应性较差，每一次拓扑变化都会导致触发一次新的路由发现与计算过程，因此带来相应的路由开销。GyTAR表现出较好的归一化路由开销，是因为其仅使用基于地理位置的路由信息做转发选择，不涉及转发集合的确定。

图6 归一化路由开销vs车辆节点Fig.6 Normalized routing overhead vs number of vehicles

4 结 论

针对地理位置路由协议采用的贪婪转发方式，在高动态拓扑的VANET中丢包率较高的问题，本文提出采用机会转发方式来转发数据，采用机会转发适合无线传输介质的特性，有效利用数据成功接收的每一个机会，在大多数情况下，数据包投递成功率增幅超过10%。文章证明了所提出的转发集的构成方案，分析了通信过程中冲突发生的概率，证实了转发集选择和转发定时器设置的数学依据。针对传统的数据包携带转发集的做法，TAO重新设计了转发集形成机制，重构了数据包头部，在大多数情况下，归一化路由开销较传统机会转发方式降低幅度超过5%，进一步提高了路由协议的性能。

基于车辆节点固有的性质，本文没有对能量消耗进行专门的讨论，在今后的工作中，可以在能量消耗上做进一步的分析研究，改进算法不仅适应于车辆自组织网络，也可以用于其他一些能量受限的自组织网络，增加路由协议的可扩展性。