0 引言

    车辆自组织网络(Vehicular Ad Hoc Networks，VANETs)是移动自组织网络(Mobile Ad Hhoc Networks，MANETs）的一种，由移动的车辆作为节点进行组网并实现无线通信，在城市交通领域得到广泛应用^[1]。由于车辆高速移动的特性，车辆自组织网络的拓扑结构变化快，路由协议的设计值得深入研究。目前，车辆自组织网络常用的路由协议可以分为三类：按需路由协议、主动路由协议和混合路由协议^[2-6]。按需路由协议是基于路由的需求来进行路由查找的路由协议，如AODV（Ad Hoc On-demand Distance Vector Routing）路由协议^[7]，这类路由协议开销较小，但是存在输出传输延迟大的问题。主动路由协议要求网络中的每一个节点都参与维护路由表，可以降低数据传输延迟，但是路由开销较大，如DSDV（Destination-Sequenced Distance Vector）路由协议^[8]。混合路由协议结合前两类路由协议的优点，在区域内使用主动路由方式选择路由，避免按需路由中的延迟问题；在区域间使用按需路由协议，降低主动路由的开销。常用的区域路由协议由三部分组成：区域内路由协议（IntrA-zone Routing Protocol，IARP）、区域间路由协议（IntErzone Routing Protocol，IERP）和边界广播协议（Bordercast Resolution Protocol，BPR），其中IARP是一个跳数受限的主动路由协议，IERP是按需路由协议，BPR负责转发IERP的路由请求到外围节点。区域路由协议通过在两种主动路由协议和按需路由协议之间进行切换，不仅可以减少控制开销，还能最大限度地减少端到端延迟^[9-13]。因此，在大型城市交通应用场合，采用区域路由协议可以更好地利用有限的网络资源和高效传输数据。文献[14]将区域路由协议和公交车骨干网相结合，采用改进的区域路由协议实现数据传输，能有效降低车辆自组织网络数据拥堵的问题。但是该路由协议在簇外路由发现部分还存在大量的冗余通信，增加了路由开销。为了降低路由开销，本文在文献[14]所述路由协议的基础上，提出了一种基于公交车骨干网的改进区域路由协议。设计思想是依据目的节点和簇头节点的位置信息，构建簇外路由发现阶段外围节点的约束方程，剔除与目的节点不在同一侧的外围节点的冗余通信，降低路由开销，改善路由性能。

1 面向公交车骨干网的区域路由协议

    文献[14]提出一种面向公交车骨干网的区域路由协议，将城市交通环境中的所有公交车节点连接成一个骨干网，以公交车节点作为簇头，其他车辆节点作为簇成员，采用改进的区域路由协议进行数据通信。首先，将分簇思想引入到区域路由协议中，以作为簇头的公交车节点生成域，构建半径为3跳的区域（即区域内外围节点到中心节点的距离不超过3跳）。在区域内采用主动路由协议构建路由，区域内的每个节点维护一个公共的路由表。在区域外使用按需路由协议构建路由，根据路由请求建立路由，主要包括路由发现、路由优化和路由维护三部分。

    （1）路由发现

    路由发现分为三个层次，分别是自身区域内发现、簇区域内发现和簇外发现。源节点想要发送数据给目的节点时，首先在自身区域（也即1跳区域）内发现是否存在目的节点，如果存在，则直接建立源节点到目的节点的路由。如果不存在，且在簇区域内发现，也即源节点将路由请求信息发送给其所在区域的簇头节点，由簇头节点检查其所在簇区域（也即以簇头节点为中心的3跳区域）内是否存在目的节点。如果存在，则将响应信息返回给源节点。否则，再进行簇外发现，具体是由簇头节点将源节点的路由请求信息发送给本区域的外围节点，再由外围节点将信息转发给相交的簇区域的簇头节点。由该簇头节点继续执行簇区域内发现过程，如果找多目标节点，则按原路向源节点返回路由响应消息。否则，继续簇外发现过程，通过重复簇区域内发现和簇外发现两个过程，直至找到目的节点，将路由响应消息返回给源节点。

    （2）路由优化

    文献[14]所述的路由优化过程实质上是一种路由筛选过程。对于路由发现阶段建立的路由，文献[14]以路径最短为选择标准，从源节点到目的节点构建的多条路由中选择最优的路由。针对路由发现阶段的三个层次，路由优化也在三个层次上进行，示例如图1所示。

    （3）路由维护

    考虑到车辆自组织网络中节点移动速度块，网络的拓扑结构变化很快，路由断裂现象频繁，因此需要对路由进行维护。文献[14]的路由维护：路由维护也与路由发现的三个层次相对应，对于源节点自身区域内构建的路由，维护时只需要从原路由中剔除失效的中继节点，更新路由表，根据新路由表重建路由即可；对于簇区域内构建的路由，除了从原路由中剔除失效的中继节点之外，还需要从簇内寻找一个新的中继节点，构建新的路由；对于簇外构建的路由，路由断裂由簇的外围节点引发，需要从原路由中剔除失效的外围节点，然后选择新的外围节点作为中继节点，构建新的路由。

2 结合位置信息的改进区域路由协议

    文献[14]提出的面向公交车骨干网的区域路由协议能有效降低车辆自组织网络数据拥堵的问题。然而，在其路由发现的三个层次中，簇外发现阶段存在较多的冗余通信，增加了路由开销。为了解决这一问题，本文提出了一种结合位置信息的改进区域路由协议。设计思想是，在路由发现的簇外发现阶段，依据目标节点和簇头节点的相对位置信息，筛选用于数据转发的簇外围节点，降低冗余数据通信。

    如图2所示，源节点为S，源节点所在簇的簇头节点为C，该簇的区域为3跳半径的一个圆。A、G、N、G为该区域的4个外围节点，D为目的节点。源节点S想要传输数据给目的节点D，目的节点D既不在源节点S的1跳自身区域内，也不在源节点S所在的以节点C为簇头的3跳簇区域内。因此，需要启动簇外路由发现，文献[14]的策略是由簇头节点C将源节点S的路由请求信息发送给簇头节点C所在簇的外围节点，也即A、G、N、G 4个节点，然后再由这些节点向相交的其他簇转发路由请求信息，直到找到目的节点D。图2的示例中外围节点只有4个，实际上可能有很多个。而且，与这些外围节点相交的簇可能有很多个，每一个簇又有许多外围节点。目的节点D与S之间又可能间隔许多簇。因此，簇外发现的路由开销有可能很大。为了降低路由开销，本文利用节点的位置信息，只朝向目的节点所在的方向进行簇外发现，而降低背对目的节点方向所进行的簇外发现产生的冗余路由开销。如图2所示，直线d将网络中的节点划分成两个部分：一侧含有目的节点D，而另一侧没有目的节点D。很明显，朝向不含有目标节点D的一侧发送数据包是冗余的。因此，当节点需要使用簇外发现来寻找目标节点D时，可以依据外围节点属于哪一侧来决定哪些外围节点需要接收和转发路由请求信息。例如，在图2中，簇头节点C的外围节点G和J与目的节点D在同一侧，需要接收和转发路由请求信息。而簇头节点C的外围节点A和N与目的节点D不在同一侧，就不需要接收和转发路由请求信息。这样，在簇外发现过程中，每一个节点簇剔除的外围节点数量越多，那么剔除的冗余通信越多，降低的路由开销越大。很明显，源节点与目标节点距离越远，路由开销的下降越大。

    通过上面的示例分析，可以看出本文改进的区域路由协议与文献[14]所使用的区域路由协议的主要区别是：在簇外路由发现阶段，文献[14]所使用的区域路由协议由簇头节点将路由请求信息转发给其所在簇的所有外围节点，而本文改进的区域路由协议由簇头节点将路由请求信息转发给其所在簇的与目的节点同侧的外围节点。在选择外围节点时增加了一个位置约束条件，即相对于簇头节点，所选外围节点应当与目的节点同侧。那么，现在需要确定分割线d，由该直线将簇头节点所在簇的外围节点分成两部分。分割线d满足两个条件：

    (1)d与直线CD垂直；

    (2)d通过簇头节点C。

    在节点C和节点D的位置已知的情况下，直线CD很容易求出，可以表示为；

    本文改进的区域路由协议在簇外路由发现阶段依据式(6)给出的位置约束方程，选择合适的外围节点用于转发路由请求信息，从而降低路由开销。为了实现改进的区域路由协议，还需要在传统区域路由协议的链路状态更新数据包中增加两个字段，用于存放簇头节点和目的节点的位置信息。修改后的链路状态更新数据包格式如图3所示。如文献[14]所述，车辆自组织网络中每一个车辆节点都装配了GPS定位模块，可以实时获取自身的位置信息。在簇区域内路由发现阶段，为每一个簇成员节点更新簇头节点和目节点的位置信息。当需要进行簇外路由发现时，可以利用簇头节点和目标节点的位置信息构建如式(6)所示的位置约束条件，依据约束条件筛选合适的外围节点进行数据的转发。

3 仿真实验与分析

    本文是对文献[14]所述的基于公交车骨干网的区域路由协议的改进，因此为了便于对比，本文的仿真实验参考文献[14]的实验参数。其中，软件平台使用Network Simulator 2(简称NS2)，硬件平台使用Intel I5 CPU、DDR3 16 GB RAM的计算机。NS2的仿真参数如表1所示。

    与文献[14]一样，本文实验通过对比丢包率、端到端平均时延和路由开销来评价不同路由协议的性能。除了对比本文改进的区域路由协议和文献[14]所述的公交车骨干网区域路由协议之外，还对比常用的AODV^[7]和DSDV^[8]两种路由协议。下面从丢包率、端到端平均时延和路由开销3个方面进行实验对比分析。

3.1 丢包率实验结果对比分析

    丢包率是指一段时间内目的节点未成功接收的数据包数量与发送节点发出的数据包数量的比值，反映了路由协议所创建路由的可靠性。丢包率越低，说明路由协议创建的路由越可靠。图4展示了4种路由协议的丢包率随节点移动速度的变化曲线。可见，随着节点移动速度的提升，4种路由协议的丢包率都呈现了上升趋势，因为节点移动速度越快，网络的拓扑结构变化越快，路由越不稳定，导致丢包率增加。通过对比，在节点移动速度相同的条件下，AODV路由协议的丢包率最小，因为该路由协议是一种单纯的按需路由协议，所创建的路由非常稳定。本文的路由协议的丢包率仅次于AODV路由协议，略高于文献[14]路由协议。主要原因是本文改进的路由协议降低了簇外路由发现阶段转发数据包的外围节点数量，从而加快了路由发现的速度，这样在节点移动速度加快的情况下可以快速转发数据或者重建路由，进而降低了丢包率。DSDV路由协议的丢包率最大，原因是该协议依据距离度量制定的路由选择策略受节点移动速度的影响较大。

3.2 端到端平均时延实验结果对比分析

    端到端平均时延是指数据包从源节点发出到目地节点接收所花费的平均时间，反映了路由协议所创建路由的传输效率。端到端平均时延越小，说明路由协议创建的路由传输效率越高。图5展示了4种路由协议的端到端平均时延随节点移动速度的变化曲线。可见，随着节点移动速度的提升，4种路由协议的端到端平均时延也都呈现了上升趋势，原因同样是由于节点的快速移动导致网络拓扑结构的快速变化，影响了路由的稳定性，当路由断裂时需要重启路由发现进程，这样就导致了端到端平均时延的增加。对比发现，在节点移动速度相同的条件下，本文改进的路由协议的端到端平均时延略高于DSDV路由协议，但低于文献[14]路由协议以及AODV路由协议。DSDV路由协议选择最短距离构建路由，端到端平均时延小。本文协议是在文献[14]路由协议的基础上进行改进的，通过减少簇外路由发现阶段存在的冗余传输，提高了路由发现的速度，从而降低了数据包传输的端到端平均延时。

3.3 路由开销实验结果对比分析

    路由开销是指成功传送一个数据分组需要生成的路由控制分组的数量，反映了路由协议所创建路由的资源占用率。路由开销越小，说明路由协议创建的路由资源占用率越低。图6展示了4种路由协议的路由开销随节点移动速度的变化曲线。可见，随着节点速度的提升，4种路由协议的路由开销也都呈现了上升趋势，这也是因为节点移动速度加快引发网络拓扑结构快速变化，导致路由发现和维护的开销增加。在节点移动速度相同的条件下，DSDV路由协议的路由开销最大，文献[14]路由协议与AODV路由协议的路由开销相近，且节点移动速度较低时文献[14]路由协议的路由开销略高于AODV路由协议，节点移动速度较高时文献[14]路由协议的路由开销略低于AODV路由协议。而在这4种路由协议中，本文改进的路由协议的路由开销是最小的，这是因为本文改进了文献[14]的簇外路由发现部分，降低了这一阶段外围节点的冗余路由发现任务，从而大幅降低了路由开销。

3.4 综合评价

    综合图4、图5和图6的实验结果以及前文实验分析，本文改进的公交车骨干网区域路由协议的丢包率、端到端平均时延和路由开销3个指标都优于文献[14]所述的公交车骨干网区域路由协议，这说明本文对簇外路由发现阶段的位置约束措施是行之有效的。另外，本文改进的路由协议的路由开销指标优于AODV和DSDV路由协议，端到端平均时延指标与DSDV路由协议接近且明显优于AODV路由协议，丢包率指标略低于AODV路由协议但明显优于DSDV路由协议。因此，综合评价本文改进的路由协议的性能指标优于所对比的3种路由协议。

4 结束语

    本文是对基于公交车骨干网的区域路由协议的改进，针对该路由协议的簇外路由发现阶段存在的大量冗余通信进行优化，改进内容包括两个方面：(1)在传统区域路由协议的链路状态更新数据包中增加两个字段，用于存放簇头节点和目的节点的位置信息；(2)在簇外路由发现阶段，依据簇头节点和目的节点的位置信息构建位置约束方程，只选择与目的节点同侧的外围节点继续进行数据转发任务，而与目标节点不在同一侧的外围节点不再进行数据转发任务，这样不仅可以减少冗余通信，降低路由开销，而且提高了路由发现效率。通过仿真实验证实，本文改进路由协议的丢包率、端到端平均时延和路由开销3个指标都优于传统的基于公交车骨干网的区域路由协议，而且从综合性能指标来看也优于常用的AODV和DSDV两种区域路由协议。然而，改进的路由协议仍然没有考虑数据的安全传输问题，这是后续需要深入研究的方向。

参考文献

[1] SHAREF B T，ALSAQOUR R A，ISMAIL M.Comparative study of variant position-based VANET routing protocols[J].Procedia Technology，2013，11(1)：532-539.

[2] 文冠祺，王忠，张少磊，等.车载自组网中基于备用副本回退机制的路由优化算法[J].计算机工程，2017，43(1)：158-161.

[3] XIANG Y，LIU Z，LIU R，et al.GeoSVR：a map-based stateless VANET routing[J].Ad Hoc Networks，2013，11(7)：2125-2135.

[4] KUMAR N，DAVE M.BIIR：a beacon information independent VANET routing algorithm with low broadcast overhead[J].Wireless Personal Communications，2016，87(3)：869-895.

[5] KAMRAN K，AFZAL S，YAQOOB M M，et al.A comparative survey on vehicular ad-hoc network(VANET) routing protocol using heuristic and optimistic techniques[J].Research Journal of Information Technology，2015，6(2)：14-24.

[6] 陶桦，冯富琴，肖鹏，等.基于运行轨迹特征分析的车辆自组织网路由算法[J].通信学报，2016，37(6)：144-153.

[7] BHATT U R，DANGARH A，KASHYAP A，et al.Performance analysis of AODV & DSR routing protocols for MANET[C].Fourth International Conference on Communication Systems and Network Technologies.IEEE Computer Society，2014：254-258.

[8] KUMARSINGH M，THAKUR S N.Comparison of DSDV，DSR and ZRP routing protocols in manets[J].International Journal of Computer Applications，2014，108(13)：10-12.

[9] RANJAN R，XAVIER DAS A，JAISWAL A K，et al.Performance evaluation of FSR，LAR1 and ZRP routing protocols in MANET based on RWP mobility model[J].International Journal of Computer Applications，2013，71(3)：27-31.

[10] MAURYA P K，PAULUS R，JAISWAL A K，et al.Performance analysis of ZRP over AODV，DSR and DYMO for MANET under various network conditions using QualNet simulator[J].International Journal of Computer Applications，2013，66(17)：31-35.

[11] RAVI G.Energy aware zone routing protocol using power save technique AFECA[J].International Review on Computers & Software，2013，8(10)：2373-2379.

[12] RAVILLA D，PUTTA C S R.Performance of secured zone routing protocol due to the effect of malicious nodes in MANETs[C].Fourth International Conference on Computing，Communications and Networking Technologies.IEEE，2013：1-8.

[13] JAIN N，CHABA Y.Simulation based performance analysis of zone routing protocol in manet[J].International Journal of Computer Applications，2014，88(4)：47-52.

[14] 陶冰，李德敏，张光林，等.基于公交车骨干网的区域路由协议研究[J].计算机工程，2016，42(3)：7-12.

作者信息:

万  航1，王学成2

(1.浙江经济职业技术学院 物流技术学院，浙江 杭州310018；2.吉林大学 计算机科学与技术学院，吉林 长春130012)