城市场景车用自组织网络有效路由

谭文虎，周宝定，范绿蓉

（1.华中师范大学物理科学与技术学院，湖北武汉430079；2.武汉大学测绘遥感信息工程国家重点实验室，湖北武汉430079）

0 引 言

由于车辆移动性和网络高动态性，数据的有效传输一直是车用自组织网络（vehicular Ad hoc networks，VANETs）研究的重要主题之一［1］。稳定可靠的路由是保证VANETs有效通信的重要前提。由于VANETs的特殊性，传统应用于MANETs路由协议并不能有效的适合于VANETs［2］。相对于高速公路场景来说，城市交通环境由于道路网络复杂，干扰因素多且车辆行驶状态多变，其路由设计面临更大的挑战。

针对以上出现的问题，本文提出应用于城市环境的基于交叉路口地理路由协议。协议基于道路网络连通概率模型为源节点与目的节点选择最优连续交叉道路段，数据包沿着这些道路段传输；道路段内采用地理转发策略的数据包到达交叉路口附近后，选择车辆队列的最佳队列头负责数据包在拐角处的转发。通过仿真实验验证了所提出路由协议的稳定性和可靠性。

1 城市车载网路由研究的现状

可靠路由是网络有效通信的先决条件，其相关的研究是VANETs中的热点。Tarik Taleb将交叉路口附近的车辆基于移动信息进行分组，选择同一组的节点建立路由，同时引入路由失效周期（LET）概念［3，4］。Moez Jerbi等研究城市环境基于交通路口的可靠路由协议［2，5，6］，采用优化的存储转发策略转发交叉路口数据。当前针对城市环境车载网的路由协议通常利用交叉路口车辆速度矢量和位置等移动信息，预测车辆运行状态［7－9］，评估车辆连通周期建立地理路由。一方面这些路由很少考虑交通流对道路连通性的影响；另一方面忽略数据包在经过交叉路口拐角处时，由于无线信号功率的急剧衰减引起大量数据包丢失。

2 城市环境道路网络模型

城市道路交通网络的道路段通过交叉路口实现连接。车辆通过GPS接收器或位置服务（location service，LS）［10，11］获取地理位置信息；通过车载导航系统数字地图，车辆获取由交叉路口和道路组成的城市环境交通网络拓扑结构。并且当前能够提供道路密度、车辆速度等实时交通信息的数字地图已经得到应用［12］。

将道路网路抽象成是由边和点组成的图G＝（V，E）。其中V表示交通路口集合，E表示道路段集合。若Ia∈V，Ib∈V，且Ia、Ib之间存在车辆能够行驶的道路段，则道路段（Ia，Ib）∈E。交通路口安装交通控制设施，车辆根据交通规则行驶。定义行驶于道路网络的车辆为节点，并且节点双向行驶。

3 路由协议

所提出路由协议IRPU（intersection－based routing proto－col for urban）基于本节提出的交通道路网络连通概率模型选择最优路由；当数据包到达交叉路口附近时，当前节点选择合适的队列头，负责数据包在交叉路口拐角处的有效转发。

3.1 最优路径选择

图1所示li为道路网络任意一条双向车道道路i长度，通信半径为的r车辆在交通路口排队长度分别为li1、li2；道路段li－li1－li2自由流范围车辆密度为λi且服从泊松分布。随机变量xi表示自由流范围车辆出现的数目，则概率质量函数

于是车辆通信范围内至少存在一个邻居的概率为Pr（xi＞0）＝1－f（xi＝0）＝1－e－λir。处于车辆队列状况（如li1、li2范围）的车辆由于节点之间的距离皆小于通信范围，物理上是完全连通的，于是道路段i连通概率即

令源节点与目的节点所在道路分别为rds、rdd，两条道路通过（rd00，rd01，…）、（rd10，rd11，…）、（rd20，rd21，…）等连接，则rds与rdd连通概率为

最佳路由具有最大的连通概率Psd，Psd＝max（Psdm）。如图1所示，rds＝（I5，I6），rdd＝（I3，I4）源节点s与目的节点d可能的路由为I6→I1→I2→I3→I4，I6→I5→I2→I3→I4，I6→I5→I4→I3和I6→I1→I2→I5→I4→I3。从式（2）可知有（I1，I6）、（I4，I5）车辆数据几乎为零，因此连通概率趋于0，通过图1和式（3）看出I6→I5→I2→I3→I4为s、d的导向路由，数据包沿着该导向路由传输，道路段内数据采用地理转发策略。

图1 城市场景道路交通网络

3.2 道路段内数据转发

节点离开交通路口行驶于道路段内，定义该节点为段内节点。段内节点采用基于生命周期的地理转发策略转发数据包。令Dm表示当前转发节点，Dn是Dm通信范围内的任意一个节点，d（Dm，Iν）与d（Dn，Iv）分别表示Dm、Dn与下一跳交通路口Iν的距离。

Dm，n＝表示两节点间距离。其中（xm，ym）与（xn，yn）分别为Dm、Dn当前坐标。节点Dm与Dn的路径生命周期

当两节点互相接近时δ＝1；节点相对离开则δ＝－1。节点同向行驶η＝1，节点反方向行驶则η＝－1。珗vm、珗vn表示Dm、Dn速度矢量。a和b是影响因子，当a＝0，b＝0时，表示忽略道路宽度等影响因素。Dm所选择的下一跳转发节点需要满足以下两个条件:

例图1的转发节点D1选择接近于下一跳交通路口I2即满足条件（a），并满足条件（b）的节点D2为下一跳转发节点。

3.3 交叉路口数据转发

研究表明［13］无线电磁波信号在通过交叉路口角落后，信号功率强度急剧衰减约40dB左右。这意味着数据包在经过十字路口拐角处后，在很短的通信距离范围内，由于无线通信信号的急剧衰减引起通信链路的断裂，从而引起数据包的大量丢失，进一步影响网络的通信性能。

当车辆在交叉路口遇到红灯时，将以队列的形式依次排队等待放行。IRPU选择辆队列中距离十字交叉路口中心最近的车辆为队列头负责拐角处数据的投递，一方面该车辆节点具有最佳的数据传递性能，其次处于静止等待的时间最长，因此运动状态最稳定。假设交叉路口红灯维持的时间为tr，从图2中可以看出节点A4相对于十字路口队列的节点A1，A2，A3，A5和A6来说，距离交叉路口Iα中心最近，具有最佳的网络通信质量，并且由于A4排队等待而处于静止稳定状态的时间最长为tr。并且A4具有最佳的信息传递位置和最长的稳定状态，于是节点A4被选举为队列头，用来转发经过十字路口拐角处的数据包，从而避免由于信号强度的迅速衰减而引起数据包的大量丢失。

车辆与车辆间的相对位置可以分为视距（line－of－sight，LOS）和非视距（nonline－of－sight，NLOS）两种情况。为了减轻队列头的通信负载，当接收节点处于发送节点的通信范围并且相对位置为LOS，当数据包跨过交叉路口到达节点，两节点的通信不必需要队列头的参与数据转发。例图2车辆节点A2在交叉路口Iα直接向节点A5发送数据包而不需要队列头A4的参与。若发送节点和接收节点在物理上处理通信范围内，但处于NLOS状态，数据包通过队列头中继实现交叉路口的顺利转发。例图2的车辆节点A8物理上处于A7的通信范围内，由于A8位于交叉路口的拐角处，A7如果直接向A8发送数据包，由于无线信号绕过拐角处会急剧衰减，很容易引起数据包的丢失。A7首先把数据包转寄给队列头A4，然后A4中继数据包给A8。由于节点A4良好的通信性能，保证了数据包经过交叉路口拐角处能够被顺利接收。

图2 交叉路口数据转发

3.4 IRPU描述

（1）节点通过周期性广播hello信息建立邻居表，通过周期接收到的hello包，记录和更新邻居节点的ID、位置、速度、时间戳等交通信息；

（2）源节点通过LS和电子地图获取道路交通信息，IRPU采用3.1节道路连通概率模型建立数据包最优路径，数据包存储连续交通路口组成的导向路由信息；

（3）节点当前所在的道路由交通路口Iα和Iβ决定；节点收到数据包后，检测数据包的导向路由；若数据包下一跳交通路口为Iα或Iβ，则节点查询邻居表，使用3.2节方法选择下一跳转发节点；若不存在合适下一跳节点，该节点暂时存储该数据包；若Id｛Iα，Iβ｝，节点直接丢弃该数据包。

（4）协议采用存储转发的方式，节点在没有邻居的情况下，缓存不能转发的数据；节点周期查询缓存区的数据，并选择合适的邻居转发这些数据；当节点从当前道路段移动到其它道路段后，若数据包的下一跳交通路口与节点的下一跳交通路口不一致，意味着节点的行驶路径偏离了数据包的导向路由，节点使用3.1节方法为这些数据包重新建立导向路由，并基于3.2节选择合适的邻居转发数据包。

（5）当数据包到达交叉路口附近，基于3.3节利用队列头可靠的数据包投递性能，实现数据包在交叉路口的有效顺利转发。

4 仿真与分析

4.1 场景设置

本节对IRPU与GSR、ROMSGP、Gy TAR协议进行性能仿真比较。在每个路口附近对称合理位置设置障碍物，用以模拟真实交通场景高大建筑等障碍物对通信影响。节点使用全向天线通信，通信半径为r＝200m；地图大小2500×2500m2，仿真时间为60min，交通网络公设置22条道路段，8个交叉路口；数据包尺寸设置为512bytes，车辆平均速度为24－88km/h；采用交通信号灯控制交通路口车流的通行；采用仿真软件Vanet Mobisim［14］生成NS2［15］模拟器的节点移动轨迹场景输入文件，实现模拟仿真分析。CBR流的取值范围为1包/s－10包/s，分别分析100、150、200、250和300车辆的网络数据包投递率和端到端平均延迟。

4.2 仿真结果及性能分析

由图3可以看出随着数据包速率的增加，4种协议的数据包投递率皆随之降低。这主要是由于较高的数据发送速率，需要网络对数据包做出更迅速的反应。IRPU相比较其它3种协议而言，具有最高的数据包投递率。这主要是因为IRPU通过选择最优导向路径，保证数据包沿着连通性最佳的路径转发；当数据包在交叉路口拐角处附近时，队列头保证他们的顺利转发。

图3 数据投递率对比

Gy TAR协议虽然在路由过程中，考虑了通信路径连通性对数据包投递性能的影响，但由于没有充分考虑交叉路口数据包投递的有效性，因此数据包投递率相对于IRPU协议性能要差。并且IRPU随着数据包速率的增加，数据投递率保持比较稳定，表明IRPU协议能够维持更为稳定的路由路径。

图4 平均延迟对比

图4显示不同协议的端到端平均延迟。随着节点数目的增加，协议网络的端到端延迟逐渐减小。足够的节点数目保证网络具有较好的连通性，从而使得数据包能够较及时的被目的节点接收。其中IRPU延迟小于GSR、ROMSGP和Gy TAR。这是由于一方面IRPU道路段内的优化地理转发减少数据包投递的节点跳数，另一方面最优连通性的导向路由和队列头参与交叉路口数据的转发，避免数据包发送过程中的通信阻塞。

5 结束语

本文提出了应用于城市环境的车用自组织网络的路由协议IRPU。该协议基于道路连通概率模型为源和目的节点选择连续道路段交叉路口组成最佳路径，数据包沿着这条导向路径传输。为了应对交叉路口拐角处无线信号功率的急剧衰减引起的链路突然断裂，进而引起数据包的大量丢失，IRPU通过选择最优的队列头负责交叉路口拐角处数据包的有效转发。仿真实验通过比较验证所设计路由协议性能的优越性。

［1］Jaehoon（Paul）Jeong，Shuo Guo.Trajectory－based data forwarding for light－traffic vehicular Ad Hoc networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22（5）:743－757.

［2］Moez Jerbi，Sidi－Mohammed Senouci.Towards efficient geographic routing in urban vehicular networks［J］.IEEE Transactions on Vehicular Technology，2009，58（9）:5048－5059.

［3］Tarik Taleb，Ehssan Sakhaee.A stable routing protocol to support its services in VANET networks［J］.IEEE Transactions on Vehicular Technology，2007，56（6）:3337－3347.

［4］Vinod Namboodiri，Lixin Gao.Prediction－based routing for vehicular Ad Hoc networks［J］.IEEE Transactions on Vehicular Technology，2007，56（4）:2332－2345.

［5］TEE C A T H，LEE A.A novel routing protocol－junction based adaptive reactive routing（JARR）for VANET in city environments［C］//European Wireless Conference，2010:1－3.

［6］Pham Thi Hong，Hyunhee Park.A road and traffic－aware routing protocol in vehicular ad hoc networks［C］//The 13th International Conference on Advanced Communication Technology，2011:24－28.

［7］Qing Yang，Alvin Lim.Connectivity aware routing in vehicular networks［C］//WCNC Proceedings，2008:2218－2223.

［8］Wang Wenjing，Xie Fei.Small－scale and large－scale routing in vehicular Ad Hoc networks［J］.IEEE Transactions on Vehicular Technology，2009，58（9）:5200－5213.

［9］Kaveh Shafiee，Victor C M Leung.Connectivity－aware minimum－delay geographic routing with vehicle tracking in VANETs［J］.Ad Hoc Networks，2011（9）:131－141.

［10］Zhang Guoqing，Mu Dejun，Xu Zhong，et al.A survey on the routing schemes of urban vehicular Ad Hoc networks［C］//Proceedings of the 27th Chinese Control Conference，2008.

［11］Saleet H，BASIR O，Langar R.Region－based location servicemanagement protocol for VANETs［J］.IEEE Trans Veh Technol，2010，9（2）:917－931.

［12］Smart view［EB/OL］.http:www.yahoo.com.

［13］Eugenio Giordano，Raphael Frank.CORNER:A radio propagation model for VANETs in urban scenarios［J］.Proceedings of the IEEE，2011，99（7）:1280－1294.

［14］Vanet MobiSim［DB/OL］.http://vanet.eurecom.fr，2012.

［15］The network simulator－ns2［DB/OL］.http://www.isi.edu/nsnam/ns，2011.