车载自组织网络中基于十字路口的地理感知路由协议

杨羽琦，章国安，吴敏

（南通大学电子信息学院，江苏 南通 226019）

车载自组织网络中基于十字路口的地理感知路由协议

杨羽琦，章国安，吴敏

（南通大学电子信息学院，江苏 南通 226019）

为了解决城市道路多十字路口，对单个车辆节点运动感知不敏感所带来的通信性能下降问题，提出一种车载自组织网络中基于十字路口的地理感知路由（IGPR）协议，通过网络网关选择道路十字路口，形成骨干路由，在保证高连通概率的同时满足时延和误比特率要求。在双向道路模型的基础上分析获得平均时延和平均跳数的数学计算式。仿真结果表明，IGPR协议与FRGR协议、VRR协议相比，传输时延小，跳数少，通信性能好。关键词：车载自组织网络；路由协议；平均时延；平均跳数

[3]提出一种保证高连通性的基于车辆密度的可变传输范围路由 （variable transmission range routing protocol based on vehicle density，VRR），但由于城市环境多十字路口且车道方向变化频繁，该协议在城市环境下表现不佳。为了解决城市环境下这些限制，本文提出了基于十字路口的地理感知路由 （intersection-based geographical perception routing，IGPR）协议，该协议通过在十字路口之间传输数据分组，降低路径对单个节点运动灵敏度感知。十字路口的选择基于最大化路径连通概率即保证路由的稳定性。

2 基于十字路口的地理感知路由

2.1 路段模型

本文所用的路段模型是城市环境下包括十字路口的双向车道模型。本文假设车辆从全球定位系统（GPS）接收器[4]或其他感知位置服务获得地理位置。车辆还可以使用车载的导航系统获得区域数字地图，以确定其相邻道路十字路口的位置。

街道地图被抽象成一个图G(V，E)[5]。其中V表示有向图顶点的集合，E表示边的集合。对于任意两个十字路口A和B，当有路段连通A和B时车辆可在该路段行驶。图1为十字路口道路模型，其中有6个十字路口，3条主路段，每条路段的路况随机分布。

图1 十字路口道路模型

2.2 模型分析

如第2.1节所述，道路模型为G(V，E)，道路交叉口v∈V和路段e∈E相互连通。本文考虑一个双向道路场景，任意两个十字路口之间的直线车道上车辆运动方向相反。为了方便研究，现将长度为L的路段按照传输半径R分成若干路段，即双车道路段根据节点传输范围划分成间隙，如图2所示。

图2 双车道路段

本地网关有本地网络拓扑的最新信息，可以更新道路图G的估计统计数据。路径y由许多十字路口{v1,v2,…, vm}组成，这些十字路口由一系列路段{e1,e2,…,en}连通，其中，n=m-1。

2.2.1 连通概率pc

为了增加连通概率，可以利用城市环境双向车道优势。这种情况下，假设车道1路段j上两个连续的车辆Ni和Ni+1之间距离X＞R，表示该段是不连通的，Ni需向Ni+1发送数据分组，如果此时车道2上有车辆Ni,i+1在Ni的传输范围内向相反方向运动，则可通过车道2上的车辆Ni,i+1将Ni连通到Ni+1。这意味着车道2上以Ni为中心的2R范围内至少存在一个车辆节点，如图3所示。

k1和k2分别表示车道1和车道2上间隔为R的长度内车辆数的随机变量（如图2所示）。假设车辆在两个车道均匀分布，γ1和 γ2分别表示车道1和车道 2车辆节点的空间密度，长为R的区域中车辆数服从泊松分布：

图3 双车道车辆通信

车道1上Ni与Ni+1间出现通信断路时，车道2上该路段2R范围内至少能够找到一个车辆节点，就可以解决车道1上该段的断路，设k表示车道2上2R范围内车辆数的随机变量，则k是服从以下概率质量函数的泊松分布：

PnK表示该路段不连通的概率：

需要注意的是，车道1断开的连通可能多于1个。设Q表示车道1上断开的连通的个数的随机变量，如果所有Q都是可以解决的，则路段j将被视为连通的。pc|Q是假设有Q个断开连通的条件连通概率。pc|Q可以写成：

其中，N表示车道1路段j车辆节点的数目，为获得路段j连通概率，还需要知道Q的概率密度函数。如果两个连续的车辆之间的距离大于R，连通就会断开。设Pb是连通断开的概率，由于任意两个连续的车辆之间的距离为指数分布，因此：

一共有N-1条链路：

因此，路段j的总的连通概率为：

图4显示了长为5 000 m的双车道上，不同的节点密度情况下，传输半径与连通概率的关系曲线。当节点密度不变时，传输半径越大，连通概率也越大。当传输半径一定时，节点密度越大，连通概率越大。即接近连通概率1，节点密度低所需要的传输半径大，节点密度高所需要的传输半径小。

图4 传输半径与连通概率的关系曲线

2.2.2 误比特率

路径质量的另一种度量方式是误比特率。由于无线通信信道衰落和噪声的存在，两个连续节点之间信息传输可能会发生错误，Pe表示传输信息发生的错误率。假设一个自由空间传播路径损失模型。每个链路上连续两个节点之间的误比特率为[6]：

其中，α1是一个常数，Pt为发射功率，Ptherm=α2Rb是热噪声功率，α2是常数，Rb是传输数据速率，2σf2是瑞利密度函数描述的信号包络的均方值[7]。X是连续两个车辆节点之间距离，当该距离大于传输范围R时通信中断，其概率密度函数（PDF）如下：

因此，连续两个车辆之间的一个链路预期误比特率可以计算为：

路段j的误比特率Pej为：

图5显示了长为5 000 m的双车道上，不同的节点密度情况下，传输半径与误比特率的关系曲线。当节点密度不变时，传输半径越大，误比特率也越大。当传输半径一定时，节点密度越大，误比特率越大。这是因为传输半径越大，信道衰落和噪声就越多，而节点密度越大，节点之间的干扰也越多，导致误比特率增加。

图5 传输半径与误比特率关系曲线

值得注意的是，不能毫无限制地增大传输范围。考虑图4和图5，可以看到，节点密度一定时，增加传输范围可以提高连通率。但另一方面，随着传输范围的增加误比特率也会增加。因此，应选择合适的传输半径来权衡连通概率和误比特率。例如，当密度为0．004 veh/m时，600 m的传输范围可以使连通概率接近1，如果此时再增加传输范围，误比特率也会增加。综合判断图4和图5中point1，当节点密度为0．004 veh/m时，最佳半径大约为600 m。

3 基于十字路口的地理感知路由协议

3.1 IGPR路由协议

在IGPR协议中，源节点需知道将数据分组转发到目的节点的路径，这个信息是由网关提供的。此时网关充当位置服务器，具有本地网络拓扑的一个实时视图，其负责保存附近所有车辆的当前位置信息。这个过程可以通过基于区域位置服务管理协议 （regional location service management protocol，RLSMP）[4]完成。具体来说，每个车辆往前移动距离当前位置一个传输范围时报告其位置信息给网关。此信息包含节点号、传输半径R、节点的坐标位置X和Y、最后更新的时间、节点运动速度和方向。根据这些位置信息，网关在源节点和目的节点之间构建一条路由。不过，因为这些路由包括中间节点，由于中间节点的移动性，这些路由是不稳定的。为了增加其稳定性，IGPR建立了包含中间节点和道路十字路口的骨干路由。如图1所示，源节点SN到目的节点DN的3个可行骨干路由：A-B-D-F、A-C-D-F和A-C-E-F。只有当网络中节点密度显著变化时，才需要重新计算骨干路由和传输半径。

基于构建的骨干路由，网关将选择有足够车流量保证网络连通性最佳的路段。选定路由将被发送到源节点并将存储在数据分组报头，以允许中间节点在十字路口之间转发数据分组。转发过程可以描述如下：当数据分组沿车道正常转发时，它基于地理转发算法选择下一跳即下一个转发节点选择最接近于当前路段十字路口的节点。当数据分组已接近当前路段十字路口时，它会选择最接近下一个十字路口的节点。“下个十字路口”信息存储在节点接收到的数据分组报头中。

该协议的优点是网关选择最连通的骨干路由，因此，找到一个朝“下一个路口”的中间节点概率很高。IGPR协议流程如图6所示。

3.2 IGPR时延性分析

骨干路由端至端时延D定义为从源节点发出去的数据分组到达目的节点所需的时间。从源节点到目的节点的路径y包括道路的总路段n和各路段j所有的估计时延Dj，那么D可以表示为：

其中，时延Dj取决于路段j上移动节点数N和路段j相邻节点Ni和Ni+1间数据分组传输所需要的时间。移动节点Ni和Ni+1间数据分组传输所需要的时间取决于Ni转发分组的策略。如果Ni使用逐跳贪婪转发，时延为处理和发送该数据分组所需时间，表示为tp，如果Ni采用的是携带与转发策略，Ni携带数据分组转发速度与 Ni的移动速度Si相同，该时延取决于Si和Ni到下一跳Ni+1之间的距离。为了估计时延D，考虑以下两种情况。定义α=(L/R)。

情况1：如果路段长度L小于或等于传输范围R，即α≤1。该段的数据分组转发策略为逐跳转发，时延为tp。为了方便处理，设tp是一个常数。因为无线干扰多发生在不同的信道，因此数据传输之间的干扰在该模型下可忽略，这种假设在许多文献中都有使用[8，9]。注意，该分析模型应确保用不同信道，就可以反映VANET真实行为。

情况2：如果段长度L大于传输范围R，即α＞1。设k12表示两个车道间隔R内车辆的数目。同样的，k12遵循以下概率密度函数的泊松分布：

计算该道路段时延，考虑节点转发数据的策略。如果数据分组一跳一跳转发，该链路上的时延就为第一种情况下的tp。如果数据分组是由车辆节点携带并转发，路段上没有任何转发数据分组的车辆节点的概率用β表示。β估计为：

图6 IGPR协议流程

其中，平均时延可以使用在路段j的节点的平均速度计算。路段j的平均时延为：

其中，S是路段j上节点的平均速度，N是路段上节点的数目：

3.3 IGPR跳数分析

对于骨干路由y，数据分组在路段j传输所需要的跳数由路段长度L和节点在该路段的传输半径R决定。如果L＜R，即α≤1时，该路段数据分组的传输只需要单跳。如果L＞R，即α＞1时，数据分组可以多跳传输，也可以携带转发。因此，路段j上平均跳数可表示为：

因此，由n个路段所形成的骨干路由y总跳数为：

4 性能仿真

本文用MATLAB仿真软件对IGPR的性能指标进行仿真，并与基于十字路口的固定传输范围地理感知路由（FRGR）[10]协议和基于车辆密度的可变传输范围路由（VRR）[3]协议进行比较。仿真参数见表1。

表1 仿真参数设置

图7显示了IGPR协议、VRR协议和FRGR协议的节点密度与连通概率的关系曲线。3种协议的连通概率都随着节点密度的增加而增加。当节点密度一定时，IGPR协议的连通概率最大，VRR协议连通概率最小。这是因为IGPR协议和FRGR协议考虑的是双车道场景，车道2上节点可以帮助解决车道1上连接断开的情况。而IGPR协议除了双车道的优势，还可以通过改变传输范围获得更高连通率，可见IGPR协议的连通性能比其他两个协议好。

图7 节点密度与连通概率的关系曲线

图8显示了3种协议的车辆数与平均时延的关系曲线。IGPR和FRGR协议平均时延随着车辆数的降低而增加，VRR协议平均时延基本保持不变，3种协议的时延受车辆数影响都较小。当车辆数一定时，IGPR协议的平均时延最小。这是因为IGPR协议和FRGR协议可以通过双车道优势来降低数据分组携带转发的次数，但FRGR协议因为传输范围固定，有时候会出现找不到下一跳节点的情况，此时采用车辆携带转发的方式转发数据分组，最终导致时延比IGPR协议大，但是时延还是比单车道情况下的VRR协议小。

图9显示了3种协议的车辆速度与平均时延的关系曲线。IGPR和FRGR协议平均时延都随着车辆速度的增加而降低，VRR协议平均时延基本保持不变。相同速度下，IGPR协议的平均时延最小，VRR协议平均时延最大。

图8 车辆数与平均时延的关系曲线

图9 车辆平均速度与平均时延的关系曲线

图10显示了3种协议的车辆数与平均跳数的关系曲线，平均跳数都随着车辆数目的增加而增加。车辆数目相同时，VRR协议所需要的跳数最多，IGPR所需要的跳数最少。因为在车辆数一定时，IGPR协议自适应传输范围，FRGR协议可以通过双车道优势增加连通，即数据分组在两个连续车辆间转发多为1跳完成，而VRR还可能需要携带转发。

5 结束语

本文提出了一种基于十字路口的地理感知路由协议，该协议通过网关对网络中车辆节点的地理感知，选择高连通率的骨干路由，并利用十字路口传输数据分组以降低路径对单个节点运动灵敏度感知。通过理论分析获得平均时延和平均跳数的数学计算式。仿真结果表明所提出来的IGPR协议与VRR协议、FRGR协议相比，降低了传输数据分组平均时延和平均跳数。

图10 车辆数与平均跳数的关系曲线

参考文献：

[1]SPAHO E,BAROLLI L,MINO G,et al.Performance evaluation of AODV,OLSR and DYMO protocols for vehicular networks using CAVENETV,DSDV and OLSR [C]//2010 IEEE International Conference on Network-Based Information Systems, Sept 14-16,2010,Gifu,Japan.New Jersey:IEEE Press,2010: 527-534.

[2]WANG M,ZHANG Y,LI C,etal.A survey on intersection-based routing protocols in city scenario of VANE[C]// 2014 IEEE International Conference on Connected Vehicles and Expo,Nov 3-7,2014,Vienna,Austria.New Jersey:IEEE Press,2014:821-826.

[3]蔡蓉,章国安,吴月波.车载网中基于车辆密度的可变传输范围路由协议[J].电信科学,2015,31(3):1-7. CAI R,ZHANG G A,WU Y B.Variable transmission range routing protocol based on vehicledensity in VANET [J]. Telecommunications Science,2015,31(3):1-7.

[4]SALEET H,BASIR O,LANGAR R,etal.Region-based location service-management protocol for VANET [J].IEEE Transactions on Vehicular Technology,2010,59(2):917-931.

[5]LI G,BOUKHATEM L.An intersection-based delay sensitive routing for VANET using ACO algorithm[C]//IEEE International Conference on Computer Communication and Networks,Aug 4-7, Shanghai,China.New Jersey:IEEE Press,2014:1-8.

[6]CHENG H,YAO Y.Power adaptation for multihop networks with end-to-end BER requirements[J].IEEE Transactions on Vehicular Technology,2010,59(7):3445-3454.

[7]PANICHPAPIBOON S,PATTARA W.Connectivity requirements for self-organizing traffic information systems [J]. IEEE Transactions on Vehicular Technology,2008,57(6):3333-3340.

[8]MAK T K,LABERTEAUX K P.Multichannel medium access control for dedicated short-range communications[J].IEEE Transactions on Vehicular Technology,2009,58(1):349-366.

[9]SU H,ZHANG X.Clustering-based multichannel MAC protocols for QoS provisioning over vehicular Ad Hoc networks[J].IEEE Transactions on Vehicular Technology, 2007, 56 (6): 3309-3323.

[10]SALEET H,LANGAR R.Intersection-based geographical routing protocol for VANET:a proposal and analysis[J].IEEE Transactions on Vehicular Technology,2011,60(9):4560-4574.

Intersection-based geographical perception routing protocol in VANET

YANG Yuqi,ZHANG Guoan,WU Min
School of Electronics and Information,Nantong University,Nantong 226019,China

In order to solve the problem of the communication performance of degradation,which caused by multi-intersections in city environment and no sensitivity to individual node movements,an intersection-based geographical perception routing protocol in vehicular Ad Hoc network was proposed.The network gateways select road intersections to form the backbone of the route,ensuring a high probability of communication and meeting delay and bit error rate requirements.Mathematical formula of the average delay and the average number of hops were obtained on the basis of a two-way road model.Simulation results show that the transmission delay of IGPR is smaller,the number of hops of IGPR is less,and the communication performance of IGPR is better compared with the FRGR protocols and VRR protocols.

vehicular Ad Hoc network,routing protocol,average delay,average number of hops

TP393

A

10.11959/j.issn.1000-0801.2017014

1 引言

杨羽琦（1993-），女，南通大学电子信息学院硕士生，主要研究方向为车辆自组织网络。

章国安（1965-），男，博士，南通大学电子信息学院教授、博士生导师，主要研究方向为无线通信网络理论与技术。

吴敏（1992-），女，南通大学电子信息学院硕士生，主要研究方向为车辆自组织网络。

2016-10-25；

2017-01-04

国家自然科学基金资助项目(No.61371113,No.61401241)

Foundation Items：The National Natural Science Foundation of China(No.61371113,No.61401241)

车载自组织网络（vehicle Ad Hoc network，VANET）是一种无约束、自组织的特殊移动自组织网络 （mobile Ad Hoc network，MANET），整个网络以车辆为通信节点而不依赖于昂贵的网络基础设施，其与MANET不同点在于网络规模大、节点分布不均匀、节点运动速度快等。VANET通信主要包括车辆与车辆之间的通信（vehicle-to-vehicle，V2V），车辆与基础设施之间的通信（vehicle-to-infrastructure，V2I）和车辆与行人间的通信（vehicle-to-pedestrian，V2P）。随着VANET的发展，近几年其应用更加广泛，如道路安全应用、查询信息服务、集中控制交通信息系统服务、网络娱乐服务、车内办公服务等。

路由协议的研究在VANET中占重要位置，路由协议的分类根据不同的标准划分也有不同。根据路由度量的不同，分为基于拓扑结构路由和基于地理位置信息路由；根据路由发现策略的不同，可分为主动路由和被动路由；根据路由协议工作原理不同，分为确定式路由和无状态路由。基于拓扑的路由协议，如链路状态路由（optimized link state routing，OLSR）[1]主要问题是路由不稳定。事实上，传统的以节点为中心的路由因VANET节点的高移动性，路由频繁断裂，路由修复开销显著增加，导致高传输时延。另一种方法是通过地理信息提供路由，使用目的节点和相邻节点的位置信息转发数据，尽管路径更加稳定，但由于城市环境比较复杂，地理转发很多时候不能找到比当前节点更靠近目的节点的下一跳，在城市环境下表现不是很好[2]。