刘丽萍, 裴金金

(天津大学 电气与自动化工程学院，天津 300072)

基于时延期望的车载自组织网络机会路由算法

刘丽萍, 裴金金

(天津大学电气与自动化工程学院，天津300072)

针对车载自组织网络中，车辆随机运动的环境下源节点、目的节点均为运动中的车辆时数据传输效率低下的问题，提出了一种基于时延期望的机会路由算法。算法融合了概率论和统计学知识，综合考虑目的节点轨迹预测和数据时效性两方面需求，得到时延期望参数，以该参数作为整个数据传输过程中每一次数据转发中继节点选择标准，保证数据能够及时、有效地由移动中的源节点转发至移动中的目的节点。

车载自组织网络； 时延期望； 机会路由算法

0 引 言

车载自组织(Ad Hoc)网络是以车辆上安装了智能计算机系统、无线通信设备以及车辆传感器和全球定位系统(GPS)等设备为基础构建的无线车辆通信网络[1],是移动Ad Hoc网络的一个子类。车载自组织网络中,车辆节点分布不均匀并持续运动导致网络拓扑结构变化快、链路可用时间短,且应用信息具有实时性要求,使车载自组织网络数据传输面临很大挑战。

目前,车载自组织网络路由协议主要分为三类：基于拓扑的路由协议、基于地图的路由协议、基于地理位置的路由协议[2]。基于拓扑的路由协议中,所有节点地位平等,网络拓扑结构通过节点的路由表来维护,每个节点既要参与信息的转发又要维护路由表,该协议又分为先应式路由和反应式路由两类,按需距离矢量(As Hoc on-demand distance vector,AODV)[3]路由协议是典型的反应式路由协议,源节点与目的节点通信前先建立一条可靠的路径,路由选择基于网络拓扑,但路由有效期很短。基于地图的路由协议,将车辆位置信息在地图中定位,再结合电子导航地图提供的丰富道路信息,由节点集、道路集、十字路口集作为计算最优转发路径的判据,全局状态路由(global state routing,GSR)[4]协议利用电子地图技术和Dijkstm算法来计算一跳到达目的节点的最短路径,即源节点通过电子地图计算好一个到目的节点的十字路口序列,数据将沿着这条路径传至目的节点。贪婪周边无状态路由(greedy perimeter stateless routing,GPSR)[5]协议是基于地理位置的路由协议,采用贪婪转发和周边转发的算法相结合的一种转发策略,每个节点需要在一定周期内广播自身位置信息,源节点在进行数据包转发时,需要计算邻居节点与目的节点的距离[6],选择离目的节点更近的邻居节点作为下一跳中继节点。

道路车辆密度和速度的快速变化带来的不稳定网络拓扑使得GPSR协议出现路由选择错误和路由中断问题,由于数据源和目的地均处于随机运动中的车辆,轨迹不能预设,使得网络拓扑变化更快,导致链路可用时间更短,给车辆节点之间数据转发带来更大困难。

本文提出了一种基于时延期望的机会路由协议,基于概率论和统计学中的期望原理,将数据当前所在车辆节点到目的节点将要经过的交叉路口的时延期望作为路由中继节点选择依据,根据实时的交通状况进行调整,获得较高的数据传输成功率和较低的数据传输时延。

1 系统模型

1.1 网络模型

车载自组织网络中,车辆节点间可进行通信,远距离的车辆节点间可以通过中继节点多跳转发的方式进行通信[7]。网络构架中存在3种重要的实体：车辆、路口和路段,前者处于运动中,后两者相对固定。数据转发[8]完全依靠行驶中车辆的存储、携带和转发完成,转发过程为：

1)计算携带数据车辆与其他车辆的距离。若不存在邻居节点,由该车辆继续携带数据；否则,进行下一步判断。

2)若携带数据车辆一跳通信范围内存在邻居节点,选择最优的邻居节点作为下一跳中继节点,进行数据转发。

3)数据由源节点转发至目的节点,转发过程结束。

1.2 移动模型

为了更接近真实的城市道路场景[9],准确反映车辆运动规律,包括节点位置、速度、运动时间等,并考虑到仿真模型精确性需求,设计了一种简单且符合实际的道路模型[10]。如图1所示,首先,采取方格形道路,路口分为十字路口、丁字路口和L形路口。车辆运动轨迹受拓扑结构限制,只能在定义的路段上沿道路直线行驶,每次连续运动均由路段的起始点开始,运动到路段的终止点结束,然后,随机选择下一条路段开始新的运动。车辆速度分为4个等级,每个车辆的速度和加速度随机。将整个车载网络道路地图建模成一个有向图G(J,E),J为地图上交叉路口的集合,E为连接交叉路口的道路集合。两个交叉路口间的可行路径path及路径长度D可由Dijkstra算法直接获得。在交通图G中,N和P为非常重要的2个参数,N为车辆集合,ni∈N为车辆集合中的某一个车辆,P为车辆行驶轨迹集合,pni∈P为车辆ni的行使轨迹,nsour为源车辆节点,ntar为目标车辆节点,车辆在时刻t的位置被定义为pni(t),也可用坐标(xni(t),yni(t))表示其在地图中的位置,其中x和y分别为位置的经度和纬度。对于车辆运动特点,V为各车辆行驶速度集合,vi∈V为车辆ni的速度,A为各车辆加速度集合,ai∈A表示车辆ni的加速度,道路限速为Vm。

图1 车载自组织网络构架

2 算法设计

2.1 问题分析

1)数据源和目的地均为处于运动中的车辆,网络拓扑变化更快,导致链路可用时间更短。

2)车辆沿道路随机运动,其轨迹无法预设,给车辆轨迹预测增加难度。

3)车载自组织网络的大部分应用均有实时性的要求,故数据需在其有效期(time to live,TTL)内到达目的节点。

针对以上问题,采用基于时延期望的车载自组织网络机会路由算法,实现车载自组织网络中高效率的V2V数据传输。时延期望指数据当前所在车辆节点到目的节点将要经过的交叉路口的时延期望值,为了提高链路的准确性,需要对目的节点的运动进行预测,又因为车辆节点完全沿道路随机运动,轨迹不可预设,仅根据目的节点运动速度和运动方向对其进行一步交叉路口预测。为了满足数据的实时性要求,又加入了数据时效性参数,时延期望即目的节点轨迹预测和数据时效性综合考虑得出的结果。

算法在如下假设基础上进行：1)车辆节点均配置了无线通信设备,任何2个车辆节点在其通信范围内,可彼此通信；2)车辆节点配置全球定位系统(GPS)定位设备,能实时获取自身位置信息；3)向目的节点发送数据前,源节点通过位置服务协议获取目的节点的当前位置及速度；4)所有车辆节点能获取自身当前位置所在信息,包括道路及道路长度、交叉路口及交叉路口的位置、道路的拓扑结构。

2.2 运动建模

根据车辆节点的移动特点,通过其运动速度、加速度、方向等数据,即可得出有效链路。对一个车辆节点,速度分别为v,加速度为a,道路限速为Vm,则其在[0,t]时刻运行路程为

(1)

在同一路段上,t时刻车辆节点i和j的距离为

Di,j(t)=Si(t)-Sj(t)+D0

(2)

如果Di,j≤R,则在t时刻内链路有效,两车辆节点之间可以通信；否则,链路无效,自动断开链路链接。

在图1所示的网络移动模型中,车辆节点运动轨迹受拓扑结构限制,在路段上沿道路直线行驶,某一路段的运动结束后,随机选择下一条路段开始新的运动。车辆节点在路口a选择下一条路段方向的概率为

(3)

2.3 基于时延期望的机会路由算法

算法用于将数据从移动中的源节点传递至移动的目的节点,而数据传输的过程要求完全依靠行驶中车辆的存储、携带和机会转发完成。因此,寻找每次数据转发的最佳中继节点是本文算法的最重要的组成部分。在整个数据转发过程中,时延期望即目的节点轨迹预测和数据时效性综合考虑得出的结果。

根据目的节点运动速度和运动方向对其进行一步交叉路口预测,此时得到时延期望为

(4)

式中Di,a(t)为车辆与其将要经过的路口的距离；两个路口之间的最短路径长度：Da,b(由最短路径Dijkstra算法求得)。

由于数据的传输有实时性的要求,需在其TTL内到达目的节点。故在数据转发过程中,需要对数据进行有效性判断,若数据已过期,则舍弃该数据；否则,继续进行转发。定义数据有效性为

(5)

为了保证车载自组织网络中数据能够及时、有效地由移动中的源节点转发至移动中的目的节点,需要综合目的节点轨迹预测和数据时效性两方面来考虑,此时,能够得到时延期望

EETi,b(t)=ETi,b(t)×MI(t)

(6)

本文算法框架描述如下：

1)周期性广播目的节点运动信息。

2)携带数据车辆节点寻找其邻居节点。

3)携带数据的车辆节点及其邻居节点分别计算自身与目的节点的时延期望EETi,b(t)。

4)由步骤(3)计算结果判断当前车辆节点继续携带数据前行还是将数据转发给邻居节点。

5)当前携带数据的车辆节点检查数据的有效性,若数据已经无效,则该数据将被丢弃。

6)重复上述步骤,直到数据被转发至目的节点或者数据失效为止。

采用EETi,b(t)作为选择中继节点的衡量标准,即在相同情况下,拥有更小时延期望EETi,b(t)值的车辆节点能更快地将数据携带至目的节点。在整个车载自组织网络中,将整个数据转发过程中遇到的车辆数目标记为n=|Vmet|,将数据更新的次数标记为m=|t|。在每一次相遇过程中,计算一次EETi,b(t)值的复杂度为O(m),而每个备选的中继节点均需要进行一次该的计算,在整个数据转发的过程中,会发生n次这样的相遇过程。因此,基于时延期望的路由算法复杂度为O(mn)。

3 性能分析

通过车辆数目的变化对数据传输时延、数据传输成功率、平均转发次数3方面的影响进行仿真分析。

针对每个车载自组织网络中的车辆数目,设置不同的随机种子数以进行100次实验得到算法的性能结果。每一组实验中,车辆的轨迹会随着随机运动种子的不同而不同。实验中选取3km×3km范围内矩形街区的36个路口,设置车辆节点通信距离为100m,数据有效期为500s的场景下进行实验,仿真时间为1000s,车辆数目为20,40,…,180,200,车辆最小速度为5m/s,车辆最大速度为25m/s。

3.1 数据传输时延

由图2可知,随着车辆数目N的增大,2种路由协议的平均传输时延均有一定的降低,因为当车辆数目增加时,单位面积内节点密度相应增加,有更多的邻居节点参与转发,车辆通信时出现越来越少的中断链路。同时,仿真结果表明：在不同的车辆数目下,算法较传统的GPSR路由协议具有着更低的数据传输时延,在整个数据传输过程中,每次寻找最佳中继节点时均要综合考虑目的节点轨迹预测和数据时效性两方面要求,根据时延期望对中继节点进行选择,相对于传统的GPSR协议的贪婪转发方式,有效提高了中继节点选择的正确率,从而直接降低了数据传输时延。

图2 数据传输时延

3.2 数据传输成功率

数据的成功传输率指目的节点接收到的数据包与源节点发送的数据包的比例。由图3可知,2种路由协议的数据传输成功率随车辆密度增大均有所增加,因为车辆数目增加,直接表现为能够参与数据转发的邻居节点数目增加,路由出现链路中断的现象减少。基于时延期望的机会路由算法数据传输成功率明显高于传统的GPSR协议,主要原因是新的路由协议在转发过程中充分考虑了车辆运动速度、方向等问题,对目的节点运动进行准确预测,对已经失效的数据及时舍弃,及时减轻网络负载,从而达到提高数据传输成功率的目的。

图3 数据传输成功率

3.3 平均转发次数

转发次数是数据由源节点成功传输至目的节点过程中被转发的跳数。转发次数越少,说明数据传输过程中的决策越具备针对性。由图4可知,随着车辆密度增大,2种算法的平均转发次数均在增长,因为车辆密度增加导致数据传输过程中所遇车辆数目随之增加。但本文算法有效解决了传统GPSR协议盲目转发的问题,使其平均转发次数更少,从而有效缩短了路由长度,更具针对性的完成数据传输过程。

图4 平均转发次数

4 结束语

提出了一种基于时延期望的机会路由算法。该算法融合了概率论和统计学知识,综合考虑目的节点轨迹预测和数据时效性两方面需求,得到时延期望参数,以该参数作为整个数据传输过程中每一次数据转发中继节点选择标准,保证数据能够及时、有效地由移动中的源节点转发至移动中的目的节点。仿真结果表明：与传统的GPSR相比,在不同车辆密度情况下,算法在数据传输时延、传输成功率及平均转发次数均有显著提升。

[1] 冯 勇,梁 浩.车载自组织网络中一种有效的匿名认证方法[J].计算机工程与应用,2010,46(23):126-128.

[2] 李万磊,朱梅丽,谢 波,等.高速公路环境下VANET路由性能研究[J].计算机工程与设计,2011,32(6):2163-2172.

[3] Perkins C E,Royer E M.Ad Hoc on demand distance vector routing[C]∥Proceeding of the2nd IEEE Workshop on Mobile Computing Systems and Applications,Menlo Park:IEEE,1999:90-100.

[4] Lochert C,Hartenstein H,Tian J,et al.A routing strategy for vehicular Ad Hoc networks in city environments[C]∥Proceeding of IEEE Intelligent Vehicles Symposium,IV’03,IEEE,2003:156-161.

[5] Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]∥Proceeding of the6th Annual International Conference on Mobile Computing and Networking,MOBICOM’00, IEEE,2000:243-254.

[6] 卢 颖,陈日莉.基于多描述编码和距离的车载网DSR路由技术研究[J].传感器与微系统,2011,30(10):15-18.

[7] 张国庆,慕德俊,洪 亮,等.城市场景下VANET路由协议大规模仿真研究[J].计算机仿真,2009,26(8):249-252.

[8] 王金龙,王呈贵,吴启晖,等. Ad Hoc 移动无线网络[M].北京:国防工业出版社,2004.

[9] 迈尔斯.智能交通系统手册[M].北京:人民交通出版社,2007.

[10] 刘志远,陈 晶,罗惠霞,等.城市环境下基于地理位置自适应的车载网络路由协议[J].武汉大学学报:理学版,2014,60(3):201-210.

OpportunisticroutingalgorithmforvehicularAdHocnetworksbasedondelayexpection

LIU Li-ping, PEI Jin-jin

(SchoolofElectricalEngineering&Automation,TianjinUniversity,Tianjin300072,China)

In vehicular Ad Hoc networks,when vehicles are moving randomly,aiming at problem that efficiency of data transmission is low,propose an opportunistic routing algorithm based on time delay expection to against the situation when both the source node and the destination node are moving.Our opportunistic routing algorithm combines the theory of probability and statistics knowledge,to get the time delay expection parameters, the opportunistic routing algorithm incorporates the trajectory prediction of the destination node timeliness requirements of data packet.When the delay expection parameters are regarded as the selection standard of data packet’s next relay node,can ensure that the data packet can be forwarded from the moving source node to the moving destination node timely and effectively.

vehicular Ad Hoc networks； time delay expection； opportunistic routing algorithm

10.13873/J.1000—9787(2017)10—0150—04

2016—10—31

TP 393

A

1000—9787(2017)10—0150—04

刘丽萍(1979-),女,博士,副教授,从事无线传感器网络、网络优化研究工作。裴金金(1991-),女,通讯作者,硕士研究生,研究方向为无线传感器网络、车载自组织网络,E—mail:pw1102@126.com。