基于城市道路的稳定车载网分簇路由策略

卫鹏伟++何加铭++曾兴斌

1 引言

车载自组网[1]（VANET，Vehicular Ad-Hoc Network）是一种特殊形式的移动自组网（MANET，Mobile Ad Hoc Networks），通过车辆装载的无线通信设备，在车辆和车辆间、车辆与路边基础设施间有效地形成一种高动态的网络系统。

VANET具有节点移动速度快且分布不均匀、无线链路不稳定、网络拓扑变化频繁等特点。根据文献[2-4]可知，由车载网络转发策略的不同，可以将车载网路由协议分为基于拓扑的路由协议（TBR）、基于地理位置的路由协议（PBR）以及分级路由协议（HRP）。基于分级的路由协议可以将整个无中心控制的高动态网络转变为一个受中心控制的高动态网络，能够有效地增强网络管理性，降低路由开销；但在分级路由协议，高速移动车辆节点的簇结构比较不稳定，需要频繁地进行簇结构的维护，而这样容易造成节点的数据传输受到严重影响。

针对上述分层路由协议存在的问题，并结合文献[5-7]的观点，本文提出了一种基于车辆运动方向和地理位置的稳定的分簇路由协议（SCR）。SCR协议继承了基于地理位置的路由协议和分级路由协议的优点，通过改善成簇算法，增强了簇结构的稳定性；利用相对速度理论，结合车辆位置服务系统，将车辆通过速度和方向估算聚集成簇，进而有效地提高整体网络的性能。通过分析文献[8]中路由策略的可行性，发现其在一定道路条件受限，通过改进其路由算法，有效地解决了岔路口路由冗余问题，使得SCR更好地适应于VANET。

2 SCR协议

假设条件：

a：车辆均装载GPS设备，可以随时准确地知道自己的地理位置坐标；

b：车辆均可快速地通过速度仪表确定当前行驶速度；

c：车辆均装载全向无线传输设备，可接受任何方向信号；

d：车辆通信半径为R。

整个SCR协议由成簇路由协议和路由转发协议这2部分构成，下面将对各部分进行具体论述。

2.1 成簇路由协议

在SCR协议中，节点包括：簇头节点、辅簇头节点、簇成员节点和网关。簇头的职责在于对簇内成员的管理、簇间路由的维护以及簇间数据的传输；辅簇头是簇内的备用簇头节点，在簇头有效期内发生突变或离簇时，主动广播自身节点成为簇头；簇成员负责簇内路由的维护；不同簇的相交节点形成网关，实现簇间互连及通信。

SCR的成簇路由协议具有2项工作：簇的构建和簇的维护。簇的构建主要负责簇头、簇成员、网关的确定和簇的形成；簇的维护工作主要负责簇成员的入簇和离簇、簇头突变时辅簇头的选取建立以及簇内成员节点信息的管理。

（1）簇的构建

在道路环境下，为了提高簇结构的稳定性，根据车辆节点的位置信息、行驶方向及速度将车辆节点分离聚合成多个簇。成簇模型如图1所示：

图1 成簇模型

由图1可知，道路车辆节点被分隔为多个簇，簇内节点数量受限于车辆地理位置及行驶速度。

在SCR协议中，临时簇头通过节点权值大小选择，节点通过周期广播节点信息得到邻居节点状态信息，若节点自身行驶速度趋于最接近邻居车辆节点的平均速度，则确认自己成为临时簇头；若同时存在多个相同状态的节点，则最靠近邻居车辆中心位置的车辆成为临时簇头（标记为CH0）。节点权值计算公式如下：

（1）

其中，vmax为车道车辆最大限速；vi为此节点速度；vj为邻居节点速度；Ni为邻居节点数量。

（2）簇头的选举与维护

选择尽量远离前进方向的岔路口节点作为簇头的节点，避免簇头的岔路口转向造成簇的重组。整个选举过程如下：

1）临时簇头CH0向邻居节点广播Lead0（c，loc，D，V，

）数据包，其中c表示簇标号，loc表示地理位置坐标，D表示行驶方向，V表示速度值，表示邻居节点平均速度。

2）时间t0内如果CH0收到来自其它邻居节点B的Reply（loc，D，V）数据包，则表示节点B更适合成为簇头，CH0自动放弃簇头竞选，并记录B信息到簇头路由表中；否则，CH0向全网广播自己成为簇头CH，向全网广播Lead（c，loc，D，V）数据包，此时簇头的同向邻居节点依据自身运动状态加入到簇内成为簇成员，簇头通过簇成员协调获取邻簇头信息并记录于簇头路由表中。

3）某节点A长时间未收到Lead数据包或Lead0数据包，则它向全网广播Apply（locA，D，V）消息，时间t内如果收到任何簇头CH的相应信息Lead（c，loc，D，V），则节点A加入到CH中，并将簇头信息记录路由表中；否则，它考虑自己成为临簇头，重复步骤1）。

4）当簇头CH离开时，如果此时路段为非交叉路段，它将通过查询路由表获取式（1）中权值最优节点ECH（辅簇头），向ECH发送路由表信息，并向全网广播Leave0（c，loc，D，V）消息。ECH收到消息后代替CH地位自动成为簇头，并将收到的路由信息记录自己路由表中；簇成员收到Leave0消息后自动更新路由信息，标记ECH为簇头。如果此路段为交叉路段，则簇头CH将直接广播Leave（c，loc）信息，簇内节点收到消息后直接进行簇的重建。

簇头选举结束后，每个簇头均拥有自己所处簇信息、簇成员信息以及邻居簇头信息，簇成员节点记忆所属簇信息及该簇内簇头信息。

2.2 路由转发协议

如果源节点S需要发送数据包到目的节点D，S首先通过路由表查询确认D是否为自己临节点，如果是则S直接发送数据包到D；否则，S向自身所在簇内簇头询问节点D是否为簇内成员，如果是则通过簇头转发数据到D；否则，S进行簇间路由发现过程，发送RREQ请求数据包到簇头，簇头根据发送数据包方向定义方向矢量DSD，并根据DSD选择最优邻簇头，进行簇间数据转发。endprint

在簇间数据转发阶段，为避免受道路周边建筑影响在路由选择中发生路由环路和路由冗余现象，簇首首先检查自己的地理位置，如果位于岔路口，则通过改进的受限贪婪转发算法进行下一跳邻簇头的选择；否则，节点将根据矢量方向通过贪婪算法转发数据。当下一跳簇头接收到数据包后，检查D是否为簇内节点，如果是则直接将数据包转发到D；否则，簇头将数据包存储路由中，并重复上述步骤寻找下一跳路由，直到TTL（路由转发有效时间）为0时丢弃。

在数据转发过程中，由于车辆节点的高速运动，造成数据包转发至目的节点所处地理位置时，目的节点可能已经离开源节点获取的原有地理位置。假设目的节点前向簇头节点（即路由最后一跳发起者）为a，此时a根据目的节点的移动方向，进行不大于2跳的小范围洪泛。通过此方法，可使数据包有效地发送至目的节点。

为了降低路由开销，减少数据转发所需时间，下一跳邻簇头的选择十分重要，可利用路段场景和交叉路口场景下的不同特点，结合矢量DSD，通过分析贪婪算法，对贪婪转发算法进行改进。具体如下：

（1）传统的贪婪转发算法

传统的贪婪转发算法在一定场景模式下，容易造成路由路径的冗余[8-9]，如图2所示。假设图中节点均代表各个簇头节点，当簇间信息转发时，节点u需要将数据发送到节点d。由贪婪算法可得，节点u将选择距离d较近的1a作为下一跳，之后1a又转发给b，此时出现局部最优现象，b发现相对邻簇头其距离目的节点更近，此时转发模式转换为周边转发，选择节点2a作为下一跳，再次通过贪婪算法选择节点c，最后转发到目的节点d。如果源节点u直接选择2a作为下一跳，将避免后续的冗余路由。

（2）改进的贪婪转发算法

新协议中提出了一种受限的贪婪转发算法，路段场景下仍采用传统的贪婪算法，而岔路口场景下节点优先选择岔路中位置节点作为下一跳，然后此节点优先决定路由转发的路段方向，再在此方向路段寻找最优下一跳节点。

下一跳节点收到转发数据包，首先判断其与目的节点的地理位置，若处于同一方向路段，则进行贪婪转发，不再刻意选择岔路口节点，如图3（a）所示。假设图中节点均代表簇头节点，簇头u向目的簇头d转发数据包，u根据位置服务可知其与d位于同一方向路段，此时直接跳过岔路口节点进行数据包转发，通过贪婪转发数据包至节点a，直到目的簇头节点d收到信息；否则，优先将数据包转发到岔路中节点，在此节点先进行支路方向选择，再选择下一跳路由。

在岔路口路由选择时，考虑到车辆运动轨迹受限、行驶速度快、运动状态可预判等因素，因此将方向作为路由选择条件来降低路由跳数，实际场景如图3（b）所示。假设图中节点均代表簇头节点，簇头u向目的簇头d转发数据包，u通过判断发现与d不在同一方向路段，其簇头路由表中存在a1、a2等节点，而a1为岔路口节点，此时即使a2距离目的簇头节点更近，也不选择其作为下一跳，而选择岔路口节点a1作为下一跳，此时a1通过与目的节点坐标结合，在不同岔路方向映射节点a1和a1，通过位置服务判断与d方向路段一致或距离更近的映射节点岔路方向为最优路段，再通过贪婪算法在此路段进行下一跳节点选择，重复上述步骤直到数据包转发至d。

新协议的完整路由策略是：当数据包转发至岔路口节点时，先检查目的节点是否存在其邻居表内，如果存在则直接转发目的节点；否则，判断目标节点是否与自己处于同一方向路段，如果处于同一方向路段，则直接通过贪婪转发寻找距离目的节点最近节点作为下一跳；如果通过位置服务判断自身节点与目的节点不在同一路段，则优先将数据包转发给岔路中节点，通过岔路中节点与目的节点的地理位置信息，在不同岔路口方向进行基于目的节点的节点位置映射，优先选择映射节点与目的节点在同一方向路段或距离最近的路段作为最优转发支路，然后在此支路方向选择适当的下一跳路由，重复上述步骤直到数据包转发至目的节点。当进行数据转发节点在其通信范围内找不到合适下一跳节点时，暂时缓存数据分组，发现合适下一跳节点后再将数据转发。这一策略不同于其它路由策略，在岔路口必须优先进行最优支路选择，再进行最近节点选择，这样可有效地避免路由冗余，缩短路由跳数，提高路由效率。

（a）直线路段转发模式 （b）交叉路段转发模式

图3 SCR路由转发模式

3 仿真结果及分析

3.1 仿真环境

该仿真由仿真软件VanetMobiSim[10]和NS-2.35[11]组成，在4条纵横交错道路场景下进行，大小为2 400m*2 400m，各道路中车辆节点随机分布，节点通信半径为250m。

3.2 仿真结果分析

为了观察SCR路由协议的性能，本仿真通过与AODV[12]、GPRS[13-14]这2种典型的车载网路由协议进行对比分析。为了评估SCR路由策略对车辆节点密度的适应性，在仿真场景分别设置30～80个节点进行仿真。同样地，为了评估SCR路由策略对节点运行速度的适应性，节点速度选取20～50m/s。所有实验数据以10次重复仿真测试后的平均值为准。

图4展现了节点数量变化和网络的分组投递率的关系。节点数量的增加导致路由控制信息的大幅增加，这势必造成大量数据分组因超时遭到丢弃，从而影响整个网络的分组投递率。在AODV协议中，受到节点周期的路由维护修复策略，一定程度可使得分组投递率提高，但同时也造成网络开销的加剧。在GPSR协议中，由于路由选择过程并不考虑路径连通性，且在岔路口容易造成环路现象，所以分组投递率较低。在SCR协议中，由于岔路口路由选择会优先进行最佳方向路段选择，再选取下一跳节点，且节点的数据暂存有效解决了网络局部优化带来的问题，所以SCR协议的网络分组投递率相对其它2种路由协议有较好的效果。

图4 节点的分组投递率（v=30m/s）

图5展现了节点速度变化与网络的分组投递率的关系。AODV协议通过修复和重新建立路由，一定程度可使得分组投递率得到提升。GPSR协议的路由策略由贪婪算法、边界转发模式来传输数据分组，不完善的路由策略使得传输路径断裂状况下，数据分组频繁被抛弃，导致网络分组投递率下降。SCR协议岔路口路段方向预测和局部优化时的数据暂存策略，增强了网络连通性，提升了分组投递率。endprint

图5 50个节点分组投递率

图6展现了节点数量变化对网络的平均时延的影响。当节点数量较小时，网络链路容易断链，导致数据延时较高；当节点数量较多时，路由控制信息的大幅增加影响数据传输效率，致使数据转发时延增加。AODV协议中，需要进行路由发现和路由维护工作，确认路径后才进行数据转发，导致网络的平均延时较高。GPSR路由协议与SCR路由协议中，节点只需要根据邻节点和目的节点位置信息进行路由决策，边发现边转发的路由策略可有效降低网络时延。但是在岔路口路段，GPSR协议容易造成路由冗余，而SCR协议优先进行方向路段选择，再进行路由下一跳选择，降低了路由冗余现象的发生概率，所以SCR路由性能更好。

图6 平均延时

图7展现了路由跳数随着传输距离增加的变化情况。在传输距离较短时，由于SCR基于簇头进行数据转发，不同簇间需要经过簇头传输后才能到达，路由跳数相对其它2种协议较高。当传输距离增加时，3种路由协议的路由跳数均相应增加。随着传输距离的增加，GPSR协议在岔路口数据转发时容易造成路由冗余，导致路由跳数大幅增加。SCR协议通过新的路由策略降低了路由冗余，使得路由跳数相应降低。AODV协议中，在数据传输时才进行路由发现，并将第一条响应链路作为数据传输路径来保证路由跳数最少，所以平均路由跳数较少。

图7 平均路由跳数

4 结束语

本文通过分析VANET一些典型路由协议存在的问题，结合城市道路特点，提出了一种新的适用于城市道路车载网的稳定分簇路由策略SCR。SCR协议通过节点的运动特征进行分簇，并通过提出的辅簇头设计理念，避免簇头在有效期内离簇后簇重组带来的数据传输问题。根据节点的地理位置服务信息和运动可预测性，提出了一种适用于车载网中岔路口数据转发的路由策略。通过实验仿真表明，SCR协议可使得簇结构的稳定性得到增强，局部优化现象带来的路由冗余问题得到有效减少，端到端平均时延得到降低，分组投递率得到提升，并有效地控制了路由跳数，能较好地适应VANET，尤其适用于城市场景中岔路口较多的道路环境。

参考文献：

[1] 王芳. 车载自织网路由算法的研究[D]. 桂林： 广西师范大学， 2012.

[2] Bijan Paul， Md Ibrahim. Md Abu Naser Bikas. VANET Routing Protocols： Pros and Cons[J]. International Journal of Computer Applications， 2011，20（3）： 28-34.

[3] 王昭然，谢显中，赵鼎新. 车载自组织网络关键技术[J]. 电信学报， 2011（1）： 44-51.

[4] Sherali Zeadally， Ray Hunt. Vehicular Ad-hoc Networks （VANETS）： Status， Results， and Challenges[J]. Tele Communication Systems， 2012，50： 217-241.

[5] Chou Chenming， Lan Kunchan. On the Formation of Vehicle Clusters[A]. 2012 12th International Conference on ITS Telecommunications[C]. Piscataway： IEEE Press， 2012： 574-578.

[6] K Naveen， Komathy Karuppanan. Mobile Cluster Assisted Routing for Urban VANET[A]. Chennai， Recent Trends in Information Technology （ICRTIT）， 2011 International Conference on[C]. Piscataway： IEEE Press， 2011： 296-300.

[7] Song TaoXia Weiwei. A Cluster-Based Directional Routing Protocol in VANET[A]. Nanjing， Communication Technology （ICCT）， 2010 12th IEEE International Conference on[C]. Piscataway： IEEE Press， 2010： 1172-1175.

[8] 陈军，徐笛，李式巨，等. 一种稳健的城市场景车载Ad Hoc路由策略[J]. 电子与信息学报， 2007，29（11）： 2555-2559.

[9] 胡淼，李剑峰. 车载自组织网络中基于贪婪算法的地理位置路由[J]. 中兴通讯技术， 2011，17（3）： 24-28.

[10] Harri J， Filali F， Bonnet C. VanetMobiSim： Generating Realistic Mobility Patterns for VANETs[A]. Proceedings of the 3rd International Workshop on Vehicular Ad Hoc Networks[C]. 2006.

[11] 于斌，孙斌，温暖，等. NS2与网络模拟[M]. 北京： 人民邮电出版社， 2007.

[12] Yu Xi， Guo Huaqun， Wong Waichoong. A Reliable Routing Protocol for VANET Communications[A]. Istanbul， Wireless Communications and Mobile Computing Conference （IWCMC）， 2011 7th International[C]. Piscataway： IEEE Press， 2011： 1748-1753.

[13] Karp B， Kung H T. GPSR： Greedy Perimeter Stateless Routing for Wireless Networks[A]. Proe of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking[C]. 2000.

[14] Hu Lili， Ding Zhizhong， Shi Huijing. An Improved GPSR Routing Strategy in VANETs[A]. Shanghai， Wireless Communications， Networking and Mobile Computing （WiCOM）， 2012 8th International Conference on[C]. Piscataway： IEEE Press， 2012： 1-4.endprint