一种基于MAC层时延上限的VANET自适应分簇算法

杨　琼　邢　松　夏玮玮　沈连丰

(1东南大学移动通信国家重点实验室，南京　210096)(2加利福尼亚州立大学信息系统系，美国洛杉矶　90032)



一种基于MAC层时延上限的VANET自适应分簇算法

杨琼1邢松2夏玮玮1沈连丰1

(1东南大学移动通信国家重点实验室，南京210096)
(2加利福尼亚州立大学信息系统系，美国洛杉矶90032)

摘要:为提高车辆自组织网络(VANET)中媒体接入控制(MAC)协议在车辆密集情况下的性能，提出了一种基于MAC层时延上限的自适应(MDBA)分簇算法，该算法包括簇头选举算法和簇维护算法．在MAC层消息传输的时延上限制约下，簇头选举算法通过综合考虑车辆节点的速度、加速度、位置和目的地4种因素来选取簇头;针对网络拓扑的变化，簇维护算法对分簇进行自适应调整．利用交通流仿真软件VISSIM创建仿真场景，以考察MDBA分簇算法的性能．仿真结果表明，与传统无线传感器网络和移动自组织网络中的典型分簇算法相比，MDBA分簇算法中簇头和簇成员的生存时间较长，算法性能更优，更加适用于车辆自组织网络．

关键词:车辆自组织网络;媒体接入控制;分簇算法;簇头选举;簇维护

引用本文:杨琼，邢松，夏玮玮，等．一种基于MAC层时延上限的VANET自适应分簇算法［J］．东南大学学报(自然科学版)，2016，46(1) : 1 －6．DOI: 10．3969/j．issn．1001－0505．2016．01．001．

目前，将无线通信技术应用于车辆间通信的研究已经受到了产业界和学者们越来越广泛的关注［1］．媒体接入控制(MAC)是车辆自组织网络(VANET)的关键技术之一，它决定了车辆节点共享无线信道的方式［2］．在VANET中针对MAC协议的研究大致可以分为两大类:①以IEEE 802．11p标准为代表的基于竞争的MAC协议［3－4］;②以时分多址接入(TDMA)技术为代表的非竞争MAC协议［5－6］．研究发现，这2类MAC协议应用于VANET时均存在着固有缺陷:在基于竞争的MAC协议中，当车辆节点数不断增加时，车辆节点接入时延的增长是无限的，因而不能保证对时延敏感的安全消息的及时传输;而在非竞争MAC协议中，每个时间帧中所划分的时隙数目是有限的，因此该类协议不能应用于车流密集的场景［7－8］．

传统的分簇方法［9］在VANET中并不适用，究其原因在于:①无线传感器网络(WSN)中能量问题是节点分簇时首要考虑的因素，而VANET中车辆节点并无能量限制;②VANET中车辆节点均处于快速移动的状态，而传统的分簇方法并不能根据网络拓扑变化来快速自适应调整分簇;③传统分簇方法主要从能量和路由的角度来考虑发射功率，而在VANET中簇的大小受消息的MAC层时延上限制约，以时分多址接入机制为例，簇的大小是由每个时间帧中所划分的时隙数决定的，时间帧的长短受消息时延上限的制约．为此，本文提出了一种基于MAC层时延上限的自适应(MDBA)分簇算法．在2类传统的MAC协议中融合节点自适应分簇机制，有效克服了各自的固有缺陷，从而提高了VANET中媒体接入机制性能．

1　算法结构

本文以典型的双向六车道高速公路为研究场景．双向行驶的车辆被公路中央的隔离带分隔，故只考虑一侧单向行驶的三车道场景．假设行驶在道路上的所有车辆都配有定位设备(如GPS)以及记录车辆行驶状态的传感器．定位设备能够获取车辆当前的位置，车辆传感器能够记录车辆行驶过程中的状态(包括速度、加速度、方向等)．通过定位设备和传感器采集的信息将汇聚至车载单元(OBU)，利用无线通信设备发送给周围其他车辆，同时也能接收其他车辆发来的行驶状态信息．为解决VANET中现有MAC协议在车流量较大时的固有缺陷，拟对VANET中的车辆节点进行自适应分簇．每个簇由1个簇头(CH)和若干个簇成员(CM)共同组成，所有簇成员都在簇头的通信范围之内．

在基于分簇机制的VANET中，采用有限状态机［10］对车辆节点所处状态之间的转换关系进行描述．车辆节点存在4种状态:孤立节点状态、簇头状态、簇成员状态和伪孤立节点状态(见图1)．

1)孤立节点状态:网络初始化之后，车辆节点处于孤立节点状态;当车辆经过分簇成为簇成员之后，某簇成员在一段时间内离开簇头的通信范围，则该车辆节点又重新回到孤立节点状态．

2)簇头状态:孤立节点状态下车辆节点通过簇头选举算法可能选举为簇头;当车辆密度增大，簇内成员增多到影响安全消息及时收发时，原有的簇将会进行簇分裂以减少簇内成员，在簇分裂过程中将再次利用簇头选举算法重新选举出簇头．

3)簇成员状态:在簇头选举算法中未被选举为簇头的孤立节点将会以簇成员的状态加入簇;当暂时离开簇头通信范围的簇成员又重新回到簇头通信范围之内时，将会重新成为簇成员;当网络拓扑发生变化时，经过簇分裂或者簇融合，原先的簇头也可能转换为簇成员．

4)伪孤立节点状态:为了避免频繁地进行簇维护，该状态是簇成员状态和孤立节点状态之间的过渡状态．当簇成员离开簇头通信范围时，并不立即抛弃原簇成员的身份，如果只是暂时离开簇头的通信范围，则该节点成为伪孤立节点．

根据图1中车辆节点4种状态之间的转换关系，将自适应分簇算法分为簇头选举算法和簇维护算法2部分．其中，簇维护算法又包括簇成员的离开与加入、簇融合以及簇分裂．

图1　分簇算法结构

2　簇头选举算法

所提簇头选举算法基于消息传输的MAC层时延上限，综合考虑了车辆节点的速度、加速度、位置及目的地等因素．MDBA分簇算法中的簇头选举算法步骤如下:

①初始化．当车辆节点i进入某高速路段时，该车辆节点开启所有与VANET相关的设备(如GPS、传感器、OBU等)，并输入此次行驶的目的地信息Di，GPS开始获得车辆节点i的位置信息Pi．

②车辆节点广播Hello消息，定义传输半径为R．Hello消息中包含车辆的状态信息，包括车辆节点识别码、车辆节点的位置信息Pi、车速vi和加速度ai，所有车辆节点的传输半径相同，令初始化时的传输半径为RInit．每个车辆节点在收到邻居车辆节点的Hello消息后，将邻居车辆节点的状态信息加入自己的Hello消息中并再次广播，于是每个车辆节点将会获得2跳范围内车辆节点的状态信息．没有邻居车辆节点的车辆节点直接成为簇头．

③计算车辆的局部密度β以及此密度下一跳范围内的车辆节点数目None-hop=2Rβ．

④判断None-hop是否能满足消息传输的MAC层时延上限TD．如果不满足时延上限，则调整发射功率以改变车辆节点的传输半径R，转至步骤②．

⑤根据加权函数F(·)计算簇头指数．簇头指数最小的车辆节点当选为簇头．车辆节点i的簇头指数Q(i)体现了该车辆节点成为簇头的合适程度，该指数越小则越适合被选举为簇头．如果出现2个车辆节点的簇头指数相同，则车速越接近平均车速的车辆节点当选为簇头，未当选的车辆节点成为簇成员．

加权函数F(·)需综合考虑车速vi、加速度ai、位置Pi以及目的地Di对分簇稳定性的影响．在一组分簇中，适合担任簇头的车辆节点的车速和加速度应最接近于该分簇中所有车辆的平均值，簇头应位于该分簇的中心位置;为避免因簇头离开行驶路段而造成的分簇不稳定，离目的地较远的车辆节点适合担任簇头．基于此来设计加权函数，定义Fi(i)为根据车辆节点i的邻居节点计算出的车辆节点i的加权函数，其表达式为

式中，fv，fa，fp，fd分别为归一化的速度因子、加速度因子、位置因子和目的地因子; w1，w2，w3，w4分别为其对应的权重，w1，w2，w3，w4＞0，且w1+ w2+ w3+ w4=1．

归一化速度因子fv可表示为

归一化加速度因子fa可表示为

车辆节点获取的位置信息Pi一般采用经度纬度二维坐标来描述，由于只考虑单向行驶的车道，且车辆被限制在规则的车道上行驶，故可以将车辆节点的位置信息简化为一维坐标pi．

归一化位置因子fp可表示为

归一化的目的地因子fd可表示为

式中，di为车辆节点i到驶离高速路段出口的距离．

根据式(2)～(8)，可将加权函数表示为

车辆节点i的簇头指数Q(i)为

3　簇维护算法

3．1簇成员的加入与离开

在分簇的VANET中，最常见的拓扑结构改变是簇成员的加入与离开．如图2所示，当孤立车辆节点CHB驶入簇A的范围(即簇头CHA的通信范围)时，将会收到簇头CHA的消息．车辆节点CHB知道自己进入簇A后，首先向簇头CHA发送请求加入簇A的消息．簇头CHA收到请求消息后，根据MAC层时延上限TD判断是否允许加入新成员，若不允许则直接发送消息拒绝车辆节点CHB加入，若允许则进入等待期．等待期时长为Tw，经过Tw时间后，若车辆节点CHB仍在簇头CHA的通信范围内，则正式允许CHB加入簇A，成为簇成员CMA6．当簇成员CMA6驶离簇A，簇头CHA和CMA6均离开对方的通信范围时，簇成员CMA6就成为伪孤立节点，若在等待期Tw期间CMA6又回到簇头的通信范围内，则CMA6从伪孤立节点状态恢复为簇成员;若经过等待期Tw后，CMA6仍离开簇头的通信范围，则CMA6离开簇A，从伪孤立节点转变为孤立节点CHB．

图2　簇成员加入与离开示意图

3．2簇分裂

簇分裂可以分为2类情况:①原先的分簇经过分叉路段时，一部分车辆节点按原路线行驶，而另一部分车辆节点驶入另外一条路线，此时原先的分簇自然就被分裂为2个新的分簇;②车辆密度增大到原先的分簇不能容纳更多簇成员时，需要将原先的簇分裂为多个较小的新簇，以满足MAC层消息传输的时延上限．由道路分叉造成的簇分裂情况较简单，原先的簇头保持不变，继续担任簇头，而在分叉路段的其他车辆节点将通过MDBA分簇算法中的簇头选举算法重新选出簇头，形成分簇．下面着重分析车辆密度增加造成簇分裂的情况．当高速公路某路段上车流量逐渐增多、车辆密度逐渐增大时，簇成员的数量也会趋于饱和．在MDBA分簇算法中，消息传输的MAC层时延上限为约束簇成员数量的因素．根据MAC层时延上限TD确定簇成员数量的上限值NC，当簇A中的簇成员数量达到此上限值，且不断有新的车辆节点请求加入簇A时，原来的分簇已不适用于当前场景．此时，簇A的簇头CHA将根据当前的车辆密度β重新选择车辆节点的消息传输半径R，使新的消息传输半径R'满足2βR'＜NC．簇头CHA在原先的传输半径R内广播簇分裂消息以及新的传输半径R'，收到簇头CHA广播消息的簇成员以及申请加入簇A的车辆节点将传输半径设为R'，再通过MDBA分簇算法中的簇头选举算法重新选举簇头，从而使原先的簇A分裂为多个较小的新簇．

3．3簇融合

当2个簇的簇头移动到彼此的通信范围之内时，需要利用簇融合算法对当前的分簇进行调整．在高速公路上，该情景通常发生在有车流汇入的路口．如图3所示，当2组分簇的簇头处于彼此通信范围内时，簇A的簇头CHA和簇B的簇头CHB处于对方的通信范围内，车辆节点将自适应地调整分簇，2组分簇将会融合．

图3　簇融合示意图

双方簇头首先交换各自簇成员的数量，由簇成员较多的一组簇接纳簇成员较少的另一组簇;若簇成员数量相同，则由行驶方向上靠前的簇接纳另一组簇．如图3所示，由于簇A的簇成员少于簇B，则由簇B接纳处于簇头CHB通信范围内的簇A的所有成员．簇头CHA将处于簇头CHB通信范围内的原簇A成员的数量通知簇头CHB，簇头CHB收到申请加入的新成员数目后，根据MAC层时延上限TD判断是否能够容纳所有新成员．若不能容纳则告知簇头CHA，然后簇头CHA和CHB均广播簇分裂消息告知其簇成员需要进行簇分裂，使用3．2节中描述的簇分裂算法来调整分簇．若簇头CHB可以容纳申请加入的新成员，则簇头CHB发送消息告知簇头CHA后，簇头CHA广播告通知其簇成员解散簇A，簇头CHA不再担任簇头，簇成员需申请加入簇B;簇A的簇头CHA以及簇成员CMA1，CMA2将向簇头CHB申请加入簇B，成为簇B的簇成员，而不在簇B通信范围内的原簇A的簇成员将采用簇头选举算法重新选举出簇头，形成新簇．由于孤立节点在没有邻居节点的情况下直接成为簇头，故单个车辆节点加入已有簇的情况可以视为簇融合中最简单的一种情形．

4　仿真及结果分析

4．1仿真场景

为了获取更加贴近实际交通情况的车辆行驶数据来验证MDBA分簇算法，采用了交通仿真软件VISSIM来创建仿真场景．本文设定的仿真场景为高速公路上一侧单向行驶的三车道场景．为了模拟典型的分叉路段车流汇入与分流，场景中设置了2段支路，主路段上的车辆将在分叉口分流一部分车辆进入支路2，而另一段支路1上的车辆将会在分叉口汇入主路段．VISSIM的具体仿真参数设置如下:

1)路段设置．主路段中，车道数为3，车道宽度为3．5 m，主车道长度为10 000．445 m．支路1中，车道数为2，车道宽度为3．5 m，车道长度为1 003．682 m．支路2中，车道数为2，车道宽度为3．5 m，车道长度为855．258 m．所有路段的类型均设置为高速公路“Freeway”．

2)基础数据设置．选择小汽车“Car”、货车“HGV”以及大客车“Bus”，设置小汽车、货车、大客车的期望速度范围分别为80～120，60～100，70 ～110 km /h，其相对流量(即相应车辆类型在输入交通流中所占百分数)分别为80%，10%，10%．

3)车辆输入设置．为比较不同车辆密度情况下的分簇算法性能，为主路段和支路1分别设置不同的交通流量，主路段低、中、高的车流量Vmain分别为1 000，5 000，8 000 veh/h，支路1路段低、中、高的车流量Vbranch分别为1 000，3 000，5 000 veh/h．在某一时间间隔内，车辆进入路段的规律服从泊松分布．定义车流量V = { Vmain，Vbranch}，仿真中设置的车流量分别为V1= { 1 000，1 000} veh/h，V2= { 1 000，3 000} veh/h，V3= { 5 000，3 000} veh/h，V4= { 5 000，5 000} veh/h，V5= { 8 000，3 000} veh/h，V6= { 8 000，5 000} veh/h．

4．2仿真结果

通过VISSIM中一段高速公路的交通流仿真，可以获得每辆车在整个仿真过程中的行驶数据，包括车辆识别码、车辆在路段中的位置、车速、加速度和目的地，将这些统计数据直接用于MDBA分簇算法中．设置初始化传输半径RInit=0．5 km，MAC层传输延时要求TD＜50 ms，簇成员数量上限NC=40，等待期Tw=200 ms．权重w1，w2，w3，w4的取值是通过比较不同设置下簇头平均生存时间来决定的．不同的权重值导致仿真结果中簇头CH平均生存时间也各不相同．车流量设置为V3时权重选择对簇头平均生存时间的影响结果见1．由表可知，当(w1，w2，w3，w4)设置为(0．4，0．4，0．1，0．1)时，可以获得最大的簇头CH平均生存时间，因此选择(0．4，0．4，0．1，0．1)作为MDBA分簇算法的权重参数．选择簇头CH平均生存时间和簇成员CM平均生存时间作为评价分簇算法优劣的标准．这2项评价标准直接反应了簇的稳定性，在相同的仿真条件下，簇头和簇成员的生存时间越长说明分簇越稳定，簇维护的代价越小，分簇算法越优．

表1　权重选择对簇头平均生存时间的影响

不同车流量条件下CH平均生存时间和CM平均生存时间比较见图4．由图可知，利用MDBA分簇算法得到的CH平均生存时间和CM平均生存时间均高于Lowest-ID分簇算法［9］和MOBIC分簇算法［11］，即MDBA分簇算法性能最优，MOBIC算法次之，Lowest-ID算法的性能最差．在Lowest-ID算法中，节点广播Hello消息后，ID号最小的节点直接当选为簇头; MOBIC算法针对节点的移动性，使用相对移动量作为簇头选举的标准;而MDBA算法则通过综合考虑车辆节点的速度、加速度、位置和目的地4种因素来选举簇头．由此可见，性能最优的MDBA算法更适用于以车辆为节点的车辆自组织网络VANET．

图4　不同车流量条件下CH和CM平均生存时间比较

5　结语

针对VANET中MAC层协议在车辆密集情况下性能变差的问题，利用VANET的特点对车辆节点进行分簇，提出了一种MDBA分簇算法．该算法在MAC层消息传输的时延上限限制下，综合考虑了车速、加速度、位置和目的地4种因素，并能根据网络拓扑的变化自适应地进行簇维护．仿真结果表明，MDBA分簇算法的性能优于无线传感器网络和移动自组织网络中的传统算法，大幅度提高了CH平均生存时间和CM平均生存时间，更适用于车辆自组织网络．下一步研究着重于将MDBA分簇算法与MAC层协议相融合，设计出基于分簇算法的MAC协议．

参考文献(References)

［1］Boban M，Vinhoza T T V，Ferreira M，et al．Impact of vehicles as obstacles in vehicular ad hoc networks［J］．IEEE Journal on Selected Areas in Communications，2011，29(1) : 15－28．DOI: 10．1109/JSAC．2011．110103．

［2］Booysen M J，Zeadally S，van Rooyen G J．Survey of media access control protocols for vehicular ad hoc networks［J］．IET Communications，2011，5(11) : 1619 －1631．

［3］Yao Y，Rao L，Liu X．Performance and reliability analysis of IEEE 802．11p safety communication in a highway environment［J］．IEEE Transactions on Vehicular Technology，2013，62(9) : 4198－4212．DOI: 10．1109/TVT．2013．2284594．

［4］Miao L，Djouani K，Wyk B J V，et al．Performance evaluation of IEEE 802．11p MAC protocol in VANETs safety applications［C］/ /2013 IEEE Wireless Communications and Networking Conference．Shanghai，China，2013: 1663－1668．

［5］Rezazade L，Aghdasi H S，Ghorashi S A，et al．A novel STDMA MAC protocol for vehicular ad-hoc networks［C］/ /2011 IEEE International Symposium on Computer Networks and Distributed Systems．Tehran，Iran，2011: 148－151．

［6］Omar H A，Zhuang W H，Li L．VeMAC: A TDMA-based MAC protocol for reliable broadcast in VANETs ［J］．IEEE Transactions on Mobile Computing，2013，12(9) : 1724－1735．

［7］Sjoberg K，Uhlemann E，Strom E G．Delay and interference comparison of CSMA and self-organizing TDMA when used in VANETs［C］/ /The 7th IEEE International Wireless Communications and Mobile Computing Conference．Istanbul，Turkey，2011: 1488－1493．

［8］Stanica R，Chaput E，Beylot A L．Comparison of CSMA and TDMA for a heartbeat VANET application ［C］/ /2010 IEEE International Conference on Communications．Cape Town，South Africa，2010: 1－5．

［9］Zheng J，Jamalipour A．Wireless sensor networks: A networking perspective［M］．New Jersey: John Wiley ＆Sons，2009: 181－182．

［10］Su H，Zhang X，Chen H H．WSN12-6: Cluster-based DSRC architecture for QoS provisioning over vehicle ad hoc networks［C］/ /2006 IEEE Global Telecommunications Conference．San Francisco，CA，USA，2006: 1－5．

［11］Basu P，Khan N，Little T D C．A mobility based metric for clustering in mobile ad hoc networks［C］/ /International Conference on Distributed Computing Systems Workshop．Phoenix，AZ，USA，2001: 413－418．

MAC upper band delay based adaptive clustering algorithm for VANET

Yang Qiong1Xing Song2Xia Weiwei1Shen Lianfeng1
(1National Mobile Communications Research Laboratory，Southeast University，Nanjing 210096，China)
(2Department of Information Systems，California State University，Los Angeles 90032，USA)

Abstract:To improve the performance of media access control (MAC) protocols in vehicular ad hoc network (VANET) in the case of large vehicle density，a MAC upper band delay based adaptive (MDBA) clustering algorithm is proposed．The MDBA clustering algorithm includes the cluster head election algorithm and the cluster maintenance algorithm．Under the restriction of MAC upper bound delay，the speed，acceleration，position，and destination are comprehensively considered to select the cluster head in the cluster head election algorithm．In the cluster maintenance algorithm，clusters are adaptively adjusted according to the changes of network topology．Then，the traffic simulation software VISSIM is used to create simulation scenario to evaluate the performance of the MDBA clustering algorithm．The simulation results show that compared with the classic clustering algorithm in wireless sensor network and that in mobile ad hoc network，cluster head and cluster members in the MDBA clustering algorithm have longer life cycle，indicating that the MDBA clustering algorithm has better performance，thus it is more suitable for VANET．

Key words:vehicular ad hoc network; media access control; clustering algorithm; cluster head election;cluster maintenance

基金项目:国家自然科学基金资助项目(61171081，61201175，61471164)、国家科技重大专项资助项目(2012ZX03004005)．

收稿日期:2015-06-07．

作者简介:杨琼(1984—)，女，博士生;沈连丰(联系人)，男，博士，教授，博士生导师，lfshen@ seu．edu．cn．

DOI:10．3969/j．issn．1001－0505．2016．01．001

中图分类号:TN923

文献标志码:A

文章编号:1001－0505(2016) 01-0001-06