方向和位置泛洪的车联网区域路由协议

孙友伟，孙小田，王 楠

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)



方向和位置泛洪的车联网区域路由协议

孙友伟，孙小田，王 楠

(西安邮电大学 通信与信息工程学院，陕西 西安 710121)

为提高车载自组网路由发现、数据传输效率，对区域路由协议进行改进。考虑到车载自组网(VANET)通信环境(道路布局、方向、位置等)多样性，通过判断节点间位置关系缩小泛洪区域，下一跳优先选择该区域内与源或目的节点移动方向相同的节点，进一步减少转发节点数目，以此精细化限制泛洪。为适应VANET拓扑频繁变化链路脆弱特性，目的节点优先选择相同移动方向节点数最多，且平均邻居节点数最多的链路，保证数据可靠传输。仿真结果显示:改进方案较好地克服了原协议全向洪泛引起的网络开销大、单一跳数路由选择导致的丢包率、重传率较高等缺点，能够较好地适应VANET网络通信。

车载自组网;区域路由协议;位置信息;移动方向;平均邻居节点数目

0 引 言

车载自组网[1，2](vehicle Ad Hoc network,VANET)是指车和车或车和路边单元之间自发建立的一个多跳网络，更好地适应道路、车辆引起的交通变化，确保人们能够畅通出行、安全出行、快乐出行。VANET因其拓扑频繁变化、节点移动性强、链路脆弱、运动轨迹受限于道路布局等特点，路由技术要求严苛[3]。

目前可用在VANET中的路由协议分为先应式、反应式和混合式路由协议[4,5]。由于网络拓扑变化信息只在局部范围内、短期时间内产生影响，因此,采用分区机制的混合路由协议更加适用于VANET[6,7]。目前对典型混合式路由—区域路由协议[8](zone routing protocol,ZRP)的研究主要集中在优化区域半径，引入位置辅助等方面[9,10]。

VANET中车辆行驶轨迹受道路布局、交通规则等限制，数据传输只能沿着道路布局传播，路由方向可能需要随着道路布局发生“拐弯”。传统ZRP未考虑到VANET实际通信环境，不太适用于VANET[11]。因此，本文根据VANET特性提出ZRP改进方案(DL-ZRP)。提出一种基于移动方向和位置泛洪机制，并利用节点的邻居节点数和相同方向节点数共同进行路由选择，从而提高ZRP协议各项性能参数，以满足VANET需求。

1 改进方案DL-ZRP

1.1 路由发现

VANET中，汽车移动轨迹受道路布局、时速、红绿灯等条件约束，行驶路线及移动信息具有可预测性。基于定向区域的泛洪机制[12]因未考虑到道路限制、节点方向、位置关系等因素，不适用于VANET。如图1，当源、目的节点不在同一道路上且相距较远时，确定的定向路由请求区域内节点较少，路由成功概率较低。

图1 定向区域限制泛洪局限性例图Fig 1 Example of restricted flooding area

考虑到道路限制因素，提出基于方向和位置泛洪机制。利用GPS设备可获取汽车位置坐标、速度、方向等信息，结合电子地图，可判断两节点是否处在同一道路，继而可利用移动方向关系、位置关系精细化限制泛洪。

1.1.1 汽车节点方向定义

根据道路布局多样性，汽车移动方向可大致分为4个区域，如图2。例如，汽车移动方向属于“北”区域，即认为方向为北。两汽车节点间移动方向关系共有10种。

图2 汽车移动方向分类Fig 2 Classification of automobile movement direction

1.1.2 两汽车节点位置关系

曼哈顿模型中，根据目的节点D在源节点S的具体方位，可得出两者处在同一条道路上时，位置关系为正北、正南、正西、正东；不在同一道路上，位置关系为东北、西北、西南、东南。如图3，D正北位于S的正北方位，D东北位于S的东北方位。

图3 汽车节点位置关系分类Fig 3 Classification of location relationship of automobile

1.1.3 基于移动方向和位置泛洪机制

当源节点S、目的节点D不在同一道路时，路由方向可能需要随着道路布局发生“拐弯”。为有效限制泛洪，通过详细列举分析S,D间的方向关系、位置关系，考虑两节点间链路持续时间(移动方向相关)，可利用位置判断(缩小泛洪区域)、方向判断(减少转发个数)来限制泛洪。

1)位置判断

VANET中，最佳路由请求区域既要尽可能覆盖S,D的有效活动区域和寻路所必须的中间节点，又要充分限制无效泛洪，还要考虑道路、位置、方向等。基于此，位置判断限制泛洪过程如下(把道路抽象为二维平面)：

中间节点I接收到源节点S广播的路由请求(routing request,RREQ)，首先判断S,D是否处在同一道路上。

①S和D处在同一道路，位置关系为正北、正南、正西、正东。此种单一位置关系将二维平面分为2个区域，此时无论S,D方向关系如何，S只需朝着D所在区域(1/2区域)泛洪即可有效缩小泛洪区域。如图4，D正北位于S的正北位置，有效中间节点区域为位于S北部区域(含东北和西北区域以及坐标边界)。因此，只需在该区域内(阴影部分)泛洪，即I判断自己是否处在S北部区域内，是,则转发RREQ;否则,丢弃。

②S和D不在同一道路，位置关系为东北、西北、西南、东南。此种双重位置关系将二维平面分为4个区域，此时无论S,D方向关系如何，S只需朝着D所在区域(1/4区域)泛洪即可有效缩小泛洪区域。如图4，D东北位于S的东北位置，有效中间节点区域为S东北区域(含坐标边界)。因此，只需在该区域内(阴影部分)泛洪，即I判断自己是否处在S东北区域，是,则转发RREQ;否则,丢弃。

图4 位置判断举例Fig 4 Example of location judgment

2)方向判断

汽车移动受道路限制，同一道路上节点移动方向并不相同(单双车道、十字路口等)，仅位置判断并不能很好地限制泛洪。VANET中，两节点移动方向相同，链路持续时间可能较长，因此，还可依据节点移动方向关系限制泛洪。根据移动方向的不同，源节点S的邻居节点分为：同向邻节点、反向邻节点、垂直邻节点。路由转发应选择同向或反向的节点转发。这是因为互为垂直关系的两节点链路持续时间短，随时都有断裂可能；互为同向关系的两节点链路较为稳定；互为反向关系的两节点链路脆弱，但如果源节点周围没有同向邻节点，通过位置判断，反方向的前方邻节点也可作为补充路由传递数据。

①S和D处于同一道路(方向关系为同向或反向)，位置判断后泛洪区域较大，则处在1/2区域内的中间节点I需要继续进行方向判断来减小转发节点个数。I接收RREQ后，判断自己与S移动方向关系。同向和反向邻节点转发RREQ，垂直方向邻节点丢弃。

②S和D不在同一道路(方向关系同向、反向、垂直均有可能)。路由方向可能需要随着道路布局发生“拐弯”。处在1/4区域内的中间节点I此时无需再进行方向判断。因为此时泛洪区域为最佳泛洪区域，继续缩小区域可能导致找不到路由；S，D方向关系存在多种可能，继续进行方向判断可能导致有效中间节点数目变少，不利于路由发现。

综上，基于方向和位置泛洪机制的中间节点I路由发现流程如图5。

图5 基于移动方向和位置泛洪机制Fig 5 Flooding mechanism based on moving direction and location

1.2 路由选择

VANET中，汽车节点频繁加入或退出，以及速度、方向变化等因素，使得链路脆弱，路由维持时间较短，单纯依据最小跳数选择路由可行性低。一个节点的邻居节点数目一定程度上反映了网络局部拓扑信息，若该节点周围邻居节点较多，则节点所在链路断裂修复成功可能性较大，所用时间也较短。因此，路由应优先选择平均邻居节点数较多的链路。

路由转发阶段，规定与S/D同向或反向中间节点均转发RREQ。但互为反向关系的两节点链路较脆弱，路由应优先选择链路上与S/D相同方向节点数目较多的链路。仅当中间节点周围没有同向邻节点时，才选择反向邻节点传递数据。

综合考虑，最优路径选择由二者共同决定(定义组合判据L，详见下文)。当目的节点首次接收RREQ后，并不立刻回复路由应答(routing reply,RREP)，等待Δt，对比此时间内建立的j条链路的L值，优先选择L值最大的链路传输数据。具体如下：

1)RREQ中增加neighbor_number、sd_number字段。中间节点I通过泛洪机制判定后，还需进行如下操作：

①I查询自身邻居列表，获取邻节点个数后累加至neighbor_number字段，最终的RREQ中neighbor_number字段(该数值记为Nsum_number)就记录了整条链路上所有节点的邻居节点数目和。

②I判断自己是否和S/D为同方向(S/D任一即可)，是,则sd_number字段加1;否则,不操作。最终的RREQ的sd_number(该数值记为Nsd_number)字段就记录了该条链路中与S/D同方向的节点个数。

2)ZRP允许目的节点所在区域内的节点应答RREQ。为根据链路状况更好地选择路由，规定只有目的节点才可回复RREP。目的节点允许重复接收同一源节点发送的RREQ。

3)目的节点接收RREQ后，计算链路平均邻居节点数(k为跳数，Ni为该链路第i个节点的邻居节点数目)

4)路由选择以整条链路平均邻居节点数Navg_neighbor和与S/D同向节点数Nsd_number作为计算权值的参数，根据节点密度的不同，选取适当的加权系数a，第i条链路权值计算方法如下

Li=aNavg_neighb or+(1-a)Nsd_number

Lopt=max{L1,L2,L3,…，Li}

目的节点通过计算选取Lopt的链路回送RREP给前驱节点。

2 性能评估

城市道路场景中，车辆运动轨迹受道路布局和交通规则限制，节点数目较多，且城区限速0～60 km/h。因此，仿真主要考虑车辆密度因素。

本次使用Network Simulator version 2，结合VanetMobosim软件生成的trace信息进行仿真，参数见表1。

表1 仿真参数

2.1 分组投递率

图6反映了车辆密度与分组投递率关系。车辆较少时，网络吞吐率较好，分组投递率较高；车辆达到80个时，吞吐率较低，大量分组丢失、重传，再丢失、再重传，网络逐渐堵塞严重，分组投递率急剧下降。DL-ZRP较之ZRP，分组投递率变化平缓，且相同车辆密度下，分组投递率较小。这是因为DL-ZRP中分组包括位置分组(ZRP不存在)、路由分组、数据分组，无形中占用了一小部分带宽；但DL-ZRP基于方向和位置泛洪机制，RREQ较少，带宽占用小，同时路由选择最优组合判据，分组传输成功率较高，缓解了网络拥塞，分组投递率高于ZRP。

图6 分组投递率Fig 6 Packet delivery rate

2.2 控制开销

图7中，ZRP与DL-ZRP控制开销随车辆增多均呈上升趋势。车辆较少(小于60)时，虽然DL-ZRP存在额外位置分组，增加了一部分开销，但其采用基于方向和位置泛洪机制，RREQ较少，相较于ZRP广播泛洪，控制开销相差不大。当车辆数目达到70个，通信量大幅增加，ZRP由于区域内、外均采用广播，控制开销激增。而DL-ZRP基于方向和位置泛洪机制，总控制开销较少，且组合判据选择的链路可靠性高，避免了链路修复、消息重传产生的额外开销，较于ZRP，DL-ZRP控制开销更小。

图7 控制开销Fig 7 Control overhead

2.3 平均端到端时延

图8反映了平均端到端时延随密度变化情况。车辆数目小于60个，网络相对稀疏，路由发现较快，相应平均端到端时延较小。当车辆数目大于80个，吞吐量降低，大量分组重传造成拥塞恶化，端到端时延激增。DL-ZRP平均端到端时延优于ZRP，虽然DL-ZRP计算量较大、位置处理增加了网络时延，但其基于方向和位置泛洪机制、以及组合判据的路由选择，网络开销减少，分组传输成功率较高，同向邻节点转发使得分组快速传播至目的节点，正确的传播方向大大缩短了传输时间，优势大于劣势，从而平均端到端时延小于ZRP。

图8 平均端到端时延Fig 8 Average end-to-end delay

3 结 论

本文针对VANET关键技术的路由算法，结合实际通信环境，提出适用于VANET的ZRP改进方案(DL-ZRP)。改进方案仅针对网格型道路布局进行了改进。下一步需考虑各地道路布局多样性，结合实际通信环境，优化完善并实地验证。

[1] 许富龙,刘志建.车载自组织网络路由协议研究进展与比较[J].电讯技术,2013,53(10):1393-1400.

[2] 张瑞锋.车载自组网通信技术研究综述[J].汽车研究与开发,2014,4(2):79-85.

[3] 周美丽,余 敏.基于车流密度的VANETs路由协议[J].传感器与微系统,2014,33(4):118-121.

[4] Gavin Holland,Nitin Vaidya.Analysis of TCP performance over mobile Ad Hoc networks[J].Wireless Networks,2002,8(2):275-288.

[5] 黄 欣,余思东,万荣泽.面向城市环境VANETS的基于Beacon控制的路由协议[J].计算机测量与控制,2014,22(12):4078-4080.

[6] 陈耀华,彭凌西.关于VANETs路由协议的研究现状与进展[J].传感器与微系统,2014,33(3):1-4.

[7] Pomenka P.Wireless local area networks:A comprehensive guid-e[J].Radioengineering,2002,11(4):30-33.

[8] 马明辉,武晓庆,武穆清.ZRP路由协议的NDP优化与仿真分析[J].无线电工程,2007,37(7):4-6,43.

[9] 李 琳,武穆清.ZRP区域路由协议分析[J].数字通信世界,2007(11):52-55.

[10] 邱朋义,王洪玉.基于位置信息的AODV路由协议[D].大连:大连理工大学,2008.

[11] 施荣华,罗棋峰.一种MANET中基于位置信息的ZRP路由协议[J].湖南大学学报:自然科学版,2009,36(8):38-42.

[12] 张棋飞,刘 威,杨宗凯,等.基于位置信息的自适应Ad Hoc路由协议[J].计算机科学,2007,34(5):20-24.

Zone routing protocol based on direction and location flooding for VANET

SUN You-wei,SUN Xiao-tian,WANG Nan

(School of Communication and Information Engineering,Xi’an University of Posts and Telecommunications,Xi’an 710121,China)

In order to improve efficiency of data transmission and routing discovery in VANET,zone routing protocol is improved.Considering the diversity of VANET communication environment,including road layout,moving direction,location,etc,restricted flooding mechanism is to reduce the flooding area by judging the position relationship between nodes,to further reduce the forwarding node number,the next hop select the nodes that has the same movement direction with source node.In order to adapt to frequent changes in the VANET,the destination node select preferentially the link that has the maximum of average number of neighbor nodes and number of nodes in the same direction of movement.Simulation results show that the improved protocol overcome some downside of original protocol,such as the large overhead caused by omnidirectional flooding,high packet loss rate and high retransmission rate caused by the way of simple routing selection etc,and the improved ZRP scheme is proved better adapt to vehicles communication in VANET.

VANET;zone routing protocol;location information;direction of movement;average number of neighbor nodes

10.13873/J.1000—9787(2016)11—0136—04

2016—01—21

TN 913.6

A

1000—9787(2016)11—0136—04

孙友伟(1956-),男，陕西西安人,教授,从事通信网络研究工作。