一种改进WCA分簇广播路由在高速公路环境的应用研究

袁学松，　张　静，　袁　涛

(1.安徽机电职业技术学院信息工程系,安徽 芜湖　241000；2.合肥工业大学计算机与信息学院，安徽 合肥　230009)



一种改进WCA分簇广播路由在高速公路环境的应用研究

袁学松1,2，张静1，袁涛1

(1.安徽机电职业技术学院信息工程系,安徽 芜湖241000；2.合肥工业大学计算机与信息学院，安徽 合肥230009)

摘要：针对高速公路上车辆节点运动速度快，拓扑结构变化频繁，传统车载广播算法广播覆盖率低、簇结构不稳定，造成网络负载高等缺点.本文在充分研究高速公路的车载自组网络(vehicle ad hoc networks,VANETs)环境的基础上，提出了一种基于权值的HWCA(Highway Weighted Clustering Algorithm)分簇广播算法.该算法通过增加HRSU(Highway Road Side Unit)节点，有效控制了成簇规模，并通过车辆的行驶模型实时确定簇首节点和首尾网关节点，提高网络广播的可靠性.仿真结果表明，在高速公路环境下，HWCA较现有的车载广播算法有更好的广播覆盖率，更低的簇首变化频率，更稳定的簇结构，并有效地降低了网络负载，减小了系统开销.

关键词:分簇算法；HWCA；VANETS；HRSU；成簇规模；高速公路

在高速公路场景下，安装在汽车中的Vanet节点运动速度快 ，密度分布不均匀，但运动模型相对于普通公路更有规律，基本符合跟驶交通流形态.在该场景中，由于节点速度快，前车若发生意外，后车跟驶较近很可能发生连环追尾事故.相关研究表明，如果可以使用信息手段将前端突发事件及时广播给后车，则会大大减少事故发生概率.Vanet经典广播协议有洪泛法、UMB协议、ABM协议等.这些算法大多在高速公路行车模型中会产生冗余、竞争和冲突等问题，这些问题严重时会产生“广播风暴”.

1VANET分簇广播算法与问题描述

在各类车载自组网络的广播算法中最原始的为“洪泛法”,该算法为简单的MAC层多跳广播协议.协议会导致广播数据冗余、数据碰撞、“广播风暴”等问题.近年来UMB[1](Urban Multihop Broadcast)协议被广泛应用到车载自组网中，该协议使用请求和确认的广播方式避免的“隐藏终端”问题.随着节点密度增大，该协议在广播数据包时会产生高延时.AMB(Active Magnetic Bearing)协议常被应用在有众多路口的城市交通中.WCA[2]分簇广播协议经常被用在MANET中，网络利用几个影响因素对节点进行分簇.因素的权重随实际需要进行更改，簇内通过簇首节点进行广播，簇间通过网关节点进行数据交互.文献[3]提出的一种加权的分簇协议，很好解决了Vanet跟驶状态下的分簇问题.但其应用到高速公路上仍存在簇首变换频繁、网络负载较高等不足.本文通过分析Vanet中经典广播协议的优缺点，选择较适合高速场景的基于权重的分簇算法(WCA，Weighted Clustering Algorithm)，并加以改进.

2一种可靠的分簇路由算法

2.1HWCA簇首节点的推举算法

簇首节点是簇的中心节点，是根据各成员的权值比较推选出来的.当簇首节点形成后会主动地向成员广播信息，同时可以通过网关节点将成员发起的广播扩散到全网，并能在生命周期内维护簇内成员的稳定.

文献[2]中提出的经典WCA算法大多应用在MANET环境中，该环境下节点运动速度较低，网络拓扑变换不频繁，需要考虑到MENAT中各节点的能耗问题.所以算法推举簇首节点考虑了各节点之间的连通度ΔV、移动速度MV、能耗PV和节点与邻居节点的距离DV这四个因素.当自组网数据通信时，每个节点会根据公式(1)计算自己的WV，簇会推举一个WV最小且稳定的节点作为簇首节点，式中W1～W4为权重.

WV=MVW1+ΔVW2+DVW3+PVW4

(1)

HWCA簇首节点推举算法借鉴了经典算法基于权的设计.针对高速公路节点运动规律的相关问题，增加了节点的位置、节点运动规律、节点连通度等权重信息.在高速公路的场景中，HWCA算法借助车内的GPS定位系统获取车辆信息，在经过HRSU节点覆盖范围时计算前若干时间的平均速度、驾驶习惯(是否频繁变道、是否有急刹车、是否经常行驶在超车道或应急车道)等信息.节点对驾驶习惯信息进行初步评分得到一个值，其越大表明驾驶习惯越不稳定，不适合做簇首节点.在经典算法中簇首节点负责管理簇规模，HWCA算法把控制簇规模大小交给了HRSU节点.综上所述，在HWCA协议中簇首节点推选权计算公式如下：

Wh=ChW1+DhW2+VhW3+HhW4+KhW5

(2)

2.2HWCA网关节点的设计

图1　网关节点覆盖范围示意图Fig.1　Schematic diagram of the gateway node coverage

在经典的WCA算法中，簇首节点不仅需要完成簇内的通信工作，同时需要通过不同的发射功率与邻居簇进行信息交流.考虑到DSRC[4]要求，不同发射功率的簇首节点已不能满足Vanet的要求.所以在Vanet的分簇算法中大多使用标准的发射功率，这样就需要一个网关节点来完成簇间通信问题.高速公路场景中，可能出现如图1的情景.

虽然簇a和簇c还在通信范围内，a和c则不能通过处于前端的网关节点进行数据通信.导致广播不能覆盖后簇，可能会发起不必要的簇维护过程，增大了网络的负担.在HWCA网关节点设计中，为了解决上述问题，根据高速公路行车特点，为每个簇设置了前置网关节点和后置网关节点.

2.3HRSU节点的设计

在Vanet中，传统RSU通常部署在城市交通道路的两旁，汽车节点可以和RSU间进行高带宽数据传输.当没有合适的RSU和汽车节点进行通信时，汽车节点可以将要传输的信息预存在车内设备的本地缓存中，有合适机会继续进行数据传输[5].在HWCA协议中，设计了HRSU节点.它不仅能够完成普通RSU的功能，而且让它具有了簇规模控制、簇首节点、网关节点推选等特定功能.

当前RSU使用的802.11p协议支持的最大传输距离是1Km.在高速场景下，汽车节点平均速度约为100Km/h(27.7m/s)，经过HRSU的覆盖范围约为72s.在该段时间内HRSU工作过程如下：当第一辆汽车进入信号覆盖范围的时候，RSU开启计数器，每经过一辆汽车计数器加一.当簇规模达到设定的上限时会发出通知消息，让再进入覆盖范围的车辆进入下一簇.同时，HRSU强制簇内注册的汽车节点离开原簇准备建立新簇，在建立新簇之前所有的广播通信均由HRSU完成.HRSU收集覆盖范围内汽车节点自身速度、位置、驾驶习惯等信息并将其记录在内存中.当在覆盖范围内的车辆都将信息传输给HRSU时，通过HWCA的推举算法推举出簇首节点、前向网关节点、后向网关节点和成员节点并通知各节点所对应的身份信息.在高速公路环境中，安排10-20Km建立一个站点.在HRSU覆盖的两公里范围内各成员接收HRSU广播信息.当各节点离开覆盖范围则根据相关算法簇首负责对信息进行广播和对簇进行维护.

2.4各类数据包设计

为了完成簇网络中各种信息、控制和广播包的传递，协议定义了8种数据包，具体如下：

(1)广播包和紧急广播包(Broadcast Data Packet, BDP / Emergency Broadcast Data Packet, EBDP )

广播包是有簇首节点传送给成员节点，HRSU节点传给各成员节点的内容数据包.包头区中存放控制信息，数据区存放着内容信息，主要定义了包ID号、发送包的源ID、包生成时间、包中簇首节点ID、优先级等字段信息.在紧急广播包中优先级设置为最高.

(2)节点信息状态包(Node Status Packet，NSP)

用在向RSU提供节点的状态信息，同时在协议后期簇维护过程中用以节点间信息交换来推荐簇首.该包信息主要由节点的当前速度、节点的位置信息、节点的驾驶习惯评分以及节点承担簇首的次数等组成.

(3)HRSU信息传递包(HRSU Information Transfer Packet，HITP)

当RSU经过评估确定簇首、网关、成员节点后发给每个节点的身份认证包.该包定义了RSU ID号、目的节点ID号、目的节点身份信息和经过加权后的权值等信息.

(4)HRSU信息中断包(HRSU Break Packet，HBP)

该数据包是控制包.将在HRSU覆盖区域的汽车节点进行簇分离，让其强制进入组网模式.

(5)簇首声明维持包(Head Announce and Maintenance Packet，HAMP)

节点在离开RSU覆盖范围后，为了维持簇的稳定性要进行簇维护和簇重建的过程.在这个过程中簇首定期发送相关自身信息给各成员节点来声明自己身份.如果根据簇首推选方案有更小的权值的节点，则提出异议，该簇进行相关维护和重建工作.

(6)网关维持包(Gateway Maintenance Packet，GMP)

网关节点需要能够与本簇中的簇首进行通信，同时需要和邻居簇的簇首进行数据交换，所以不论是HRSU还是簇建立过程中创建的网关节点都需要告知周围的簇首自己的网关身份.在HWCA算法中，由于设置了前向网关和后向网关，所以每个网关节点最少能和两个簇首建立通信.

(7)网关退出包(Gateway Quit Packet，GQP)

在簇维护过程中，不论是前向还是后向网关发现自己不能和两个或者以上的簇首进行联系时，主动发起GQP通知簇首.簇首可以让各成员节点竞争网关节点.

(8)网关竞争通告包(Gateway Compete Packet，GCP)

只要网关发出GQP，簇首节点就会向群内广播GCP.符合条件的会获得簇首授予的网关身份，同时向周围簇首发送GMP告知其网关身份.

2.5HWCA协议原理

2.5.1HWCA簇建立过程和簇维护过程簇建立是由高速路边的HRSU装置发起.其信号覆盖范围为以其为中心的1Km的圆形区域，成簇时间为第一辆车驶入信号覆盖范围到第一辆收到HBP包车离开覆盖范围的时间差，簇规模为S，成簇过程如图2.

图2　HRSU成簇流程图　　　　　　　　　　　　　　　　　　图3　节点自发成簇流程图Fig.2　HRSU clustering flowchart　　　　　　　　　　　　　　Fig.3　Clustering chart with nodes

(1)第一辆汽车经过HRSU覆盖范围时，发送HBP包，汽车节点收到HBP包后强制脱离原簇，进入组网模式.在该模式下所有的广播信息不在由簇头发布，而是由HRSU节点接管，同时HRSU自身计数器加一.

(2)若超时，信号覆盖的节点是否达到成簇的最低要求，若达不到则转到(6)，否则转至(3).

(3)查看HRSU计数器是否超过S，若不超过转至(1)，若超过转至(4).

(4)各个汽车节点向HRSU发送NSP包，经过计算得到该簇的簇首、前向网关、后向网关、成员节点，同时向每个簇内节点发送HITP包.

(5)发送成功组组网结束，否则转至(6).

(6)成簇失败的节点将在后续行驶过程中向周围广播NSP包，通过簇维护的方式加入前簇或后簇.

在行驶过程中，始终向周围节点周期性的广播HAMP包，向周边节点告知自己的簇首身份.当周边节点认为自己有更小的权值或由于意外情况，簇首节点丢失，会进入簇重建过程.簇重建过程如图3.

图4　高速公路中网关节点的维护模型Fig.4　Gateway node maintenance model in highway

ⅰ当成员节点找不到自己的簇首或者簇首节点的权值受到质疑时，任意节点发起簇首推选.任意节点向周边邻居节点发送NSP包，用来交换各自节点的综合权值信息.

ⅱ节点通过计算认为自己的综合权值较小则向周围广播HAMP包，若无异议则成为新的簇首节点周期性的发送HAMP包，若存在异议则进入过程ⅰ.

ⅲ当各成员收到HAMP包后将各自的身份调整至成员节点或网关节点.

当成簇失败的节点经过一段时间的行驶，接受到新簇首节点的HAMP包，会向其发出自己的NSP包，若权值较大则加入簇成员，若权值较小则质疑簇首节点并发起簇重建过程.

图5　网关节点维护流程图Fig.5　Gateway node maintenance flow chart

2.5.2网关节点的维护过程在HWCA协议中，在HRSU成簇过程中通常会选择最先离开信号覆盖范围的节点作为前向网关节点(簇最前端)，最后进入信号覆盖范围的为后向网关节点(簇最后端).在簇运动过程中，网关节点位置会在簇内位置发生变化.图4中可以看出簇A后向网关节点GWA此时已不在簇C簇首节点HC的信号覆盖范围内.这就意味着簇C将不能和簇A通过GWA交互广播信息.此时，簇A就需要重新推举后向网关节点，具体过程见图5.

当A簇网关节点GWA不能收到至少2个簇首发布的周期信号HAMP包，则进入网关重选过程.GWA向HA发送GQP包，HA收到后将向簇成员广播GCP包.当收到2个或更多HAMP的节点向簇首申请网关节点后，簇首通过周期数据包HAMP授权该节点为网关节点.授权后的节点向邻居簇首周期发送GMP包.

簇首节点、网关节点和成员节点均可以发起广播包，EBDP包优先发送.簇首节点将自己的ID存入广播包的源ID中，通过网关节点对其他簇进行转发.

3仿真实验分析

3.1汽车节点运动模型与高速公路模型的构建

由于汽车在高速公路上同向高速行驶，无需考虑交通信号灯和建筑物的限制.高速运动汽车节点模型不再适合使用普通的Vanet运动模型.Bai[6-7]等人提出的基于高速公路和曼哈顿流动模型较适合本文场景.在高速公路模型的选择上，本文使用MOVE[8](Mobility Model Generator for Vehicular Networks)软件将地图数据库直接导入到软件中实现了真实场景的仿真，通过该软件搭建了某段长约10Km的高速公路.

本次实验以真实的高速公路为依据，同时使用节点运动模拟器SUMO[9]仿真运动高速运动的汽车节点.实验的目标广播区域是长约10Km宽为36m的5车道场景.为反映真实数据，节点的运动速率为80-120Km/h，且只考虑车辆单向从标记1运动至标记2，当场景中的车辆节点到100辆且保持该车流密度，对各指标进行提取.实验分别对车流密度区间为100-700每间隔50辆车做一次数据收集并分析.

在实验中，运动模型考虑了车辆变道等情况，但未考虑车辆车身长度信息.从簇结构稳定性考虑，设置协议中的权值分别为W1=0.26,W2=0.2，W3=0.21,W4=0.29，W5=0.04.仿真场景的各类参数入表1所示：

在仿真过程中，对整个网络性能主要关注广播覆盖率和端到端延时两个指标.而从簇稳定性的角度需关注分簇数目，簇首改变次数，簇生存时间等性能指标.

表1　高速公路场景参数表

3.2仿真结果与分析

本次仿真实验在真实模型下，把HWCA算法、WCA算法和针对跟驶模型设计的VWCP算法从网络性能和簇稳定性两个方面进行对比实验[10].

图6为仿真场景中分簇数目，可以看出随着节点的增加HWCA算法和VWCP算法的分簇数保持稳定，表示簇很少进行重建和分离.在整个600秒仿真时间内，由于HRSU使用计数器有效地限制了簇规模.所以HWCA中分簇个数虽比VWCP多，但成簇后簇数较两种算法更加稳定.图7-8为簇首改变次数和簇生存时间，簇首改变次数越小、簇生存时间越长表示簇首更替越少，簇生存时间越长，簇更稳定，网络负担越小.从图中可以看出，当车辆节点增多时，HWCA算法由于权重因素设计合理，簇首几乎没有改变，较其他两种算法有很好的稳定性.

图6　簇规模　　　　　　　　　　　　　　　　　　　　　　　　　　　图7　簇平均生存时间Fig.6　Cluster scale　　　　　　　　　　　　　　　　　　　　　Fig.7　Average survival time of the cluster

图8　簇首改变次数　　　　　　　　　　　　　　　　　　　　　　　图9　广播覆盖率Fig.8　Change times of cluster head　　　　　　　　　　　　　　　　　Fig.9　Coverage rate of broadcast

图10　平均端到端延时Fig.10　Average end-to-end delay of data packets

图9展示的是三个协议的广播覆盖率，广播覆盖率越高说明节点发送广播能可靠的传播给全网.从图中可以看出WCA和VWCP两种算法在车辆节点较少时广播率可达98%左右，而由于HWCA算法在节点较少时使用了HRSU对网络进行广播，所以广播覆盖率接近100%.图10显示了三种算法的端到端延时指标，该指标能反映出广播包是否能及时到达各节点.当车辆较少时，在HWCA算法中节点由于大多是由HRSU进行广播传输延时较低.随着车辆节点的增多，大多数广播发生在HRSU覆盖范围之外，和其他两种协议一样是由簇首节点负责广播，由于协议的簇较稳定，网络负载较小，所以较其他两种协议端到端的延时也更小.

4结束语

本文深入研究WCA和VWCP两种广播协议的基础上，提出了一种应用于高速公路的HWCA协议.通过仿真结果表明，新协议和经典协议在高速公路环境下均有很好的广播覆盖率，但在车辆节点较多，路况较为复杂的情况下，HWCA协议比经典协议具有有更好的网络性能，其形的成簇具有更好的稳定性，相关协议算法在真实高速公路情景下具有更好的实用价值.

参考文献:

[1]JAGRUTI sahoo, ERIC Hsiao-Kuang Wu, Pratap Kumar Sahu. Binary-Partion-Assisted MAC-Laryer Broadcast for Emergency Message Dissemination in VANETs[J]. IEEE Transactions on Intelligent Transportation System,2011,12(3):757-770.

[2]CHATTERJEE M, DAS S K, TURGUT D. WCA: a weighted clustering algorithm for mobile ad hoc networks[J]. Cluster Computing. 2002,5:193-204.

[3]周连科.基于交通流密度的VANET广播技术研究[D].哈尔滨:哈尔滨工业大学,2011:50-70.

[4]CSEH C. Architecture of the dedicated short-range communications (DSRC) protocol[C]. 48th IEEE Vehicular Technology Conference. Ottawa,Canada,1998:2095-2099.

[5]LIN Xiaodong, LU Rongxing, LIANG Xiaohui, et al.Stap:a social-tier-assisted packet forwarding prot-ocol for achieving receiver-location privacy preservation in vanets[C]∥Proceedings of IEEE INFOCOM 2011, IEEE INFOCOM．Shanghai: IEEE Press,2011:2147-2155．

[6]F Bai, SADAGOPAN N, HELMY A. The important framework for analyzing the impact of mobility on performance of routing for ad hoc networks[J]. Ad Hoc Networks, 2003,1(4):383-403.

[7]F Bai, SADAGOPAN N, HELMY A. Important:a framework to systematically analyze the impact of mobility on performance of routing protocols for ad hoc networks[C].INFOCOM 2003,the 22th Annual Joint Conference of the IEEE Computer Communications,IEEE Societies,2003,2:825-835.

[8]KARNADI F K, MO Z H, LAN K.Rapid generation of realistic mo-bility models for VANET[C]. Proc of IEEE Wireless Communications and Networking Conference 2007. Hong Kong, 2007:2506-2511.

[9]BEHRISCH M, BIEKER L, ERDMANN J, et al. SUMO-Simulation of Urban Mobility: An Overview[C]// Simul. 2011:63-68.

[10]ZHANG H, XIA J， SHEN Y. A graph clustering algorithm based on weighted shared neighbors and links[C]. Software Engineering and Service Science (ICSESS), 2015 6th IEEE International Conference on, Beijing, 2015, 828-831.

DOI：10.14182/J.cnki.1001-2443.2016.04.004

收稿日期：2016-4-14

基金项目：安徽省教育厅2016年度高校领军人才引进与培育计划项目(gxfxZD2016324)；安徽省教育厅省级教学团队(2014jxtd99)资助.

作者简介：袁学松，男，1982，硕士，研究生，副教授，研究方向为主要研究方向为网络仿真技术、无线传感网、数据挖掘.

中图分类号:TPT393

文献标志码:A

文章编号：1001-2443(2016)04-0324-07

Application of an Improved WCA Clustering Broadcast Routing in Highway Scenarios

YUAN Xue-song1,2,ZHANG Jing1，YUAN Tao1

(1.Department of Information Engineering, Anhui Technical College of Mechanical and Electrical Engineering, Wuhu 241000， China；2.School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

Abstract:Due to the fast vehicle node speed and rapid topological structure change of the highway vehicle network, the traditional vehicle broadcasting algorithms have many drawbacks, e.g. low coverage, unstable cluster structure and high network load. In this paper we study the Vehicle Ad Hoc Networks (VANETs) and propose a novel Highway Weighted Clustering Algorithm (HWCA). First, the amount of Highway Road Side Unit (HRSU) is increased and the cluster scale is controlled. Second, the first node and the gateway nodes of the network cluster are located based on the real-time vehicle driving model. The broadcasting reliability is improved. Finally, the simulation is carried out and the results show that HWCA has better coverage, lower cluster change rate, and more stable cluster structure in highway environment. The proposed algorithm may decrease the network load and cost in highway vehicle broadcasting.

Key words:clustering algorithm; HWCA；VANETS；HRSU；scale of clustering; highway

引用格式：袁学松，张静，袁涛.一种改进WCA分簇广播路由在高速公路环境的应用研究[J].安徽师范大学学报：自然科学版，2016，39(4)：324-330.