VANETs 中基于分簇算法的广播协议

黄 琼，卫新新，唐 伦，唐廷烨，辛赞洋

(1.重庆邮电大学移动通信技术重庆市市级重点实验室 重庆 400065，2.重庆大唐科技股份有限公司 重庆 400700)

0 引言

车载自组织网络(vehicle ad hoc networks，VANETs)是一种大规模网络，通常具有车辆节点移动性强的特点。与ad hoc网络不同，车载自组织网络具有很多优势，例如，车辆节点能量的消耗可以不予考虑、车辆可以配备有定位装置。但是车载自组织网络也有一些自身的缺点，例如，由于车辆的高速移动，信息在传输过程中容易产生衰落。

车辆之间在进行信息传递的时候，如果都采用广播或者单播，将会引起大量的不必要的开销和洪泛［1］。分簇的网络结构具有良好的扩展性，能够提供方便的信息管理机制和广播信息传输机制［2］。文献［3-4］分析表明，Lowest-ID算法和 Highest-Degree算法在分簇的时候，并没有很好地考虑无线信道的不稳定性。在这种情况下所形成的簇结构，并不能够很好地维护簇的稳定性，容易造成严重的数据衰落。文献［5］分析表明，簇头选举和簇结构变化时的维护开销很大。因此，分簇算法要尽量减少簇结构的变化，即减少成员节点的重关联和簇头的重新选举。

在基于分簇算法的基础上，根据802.11p协议的退避机制，可以得出每种接入类型的信息都有自己固定的竞争窗口。在文献［6］中，提出利用相对速度和相对位置来调整初始化竞争窗口的值，以达到系统吞吐量的提升。在文献［7］中，提出根据碰撞概率来估计网络的负载状况，并动态调整竞争窗口，以达到更加有效的共享信道。上述方法在进行竞争窗口调整的时候，只是动态地改变了竞争窗口的大小，并不能够很好地保证紧急消息的及时发送。

基于上述问题，本文首先针对现有分簇算法稳定性不足的问题，提出了一种基于多权值的分簇算法，其次，进一步对现有802.11p协议中的退避算法进行改进，以达到减小簇头广播消息传输时延的效果。

1 基于多权值的分簇算法

车辆在高速行驶的情况下，为了维护簇的稳定性、减小簇的开销和达到簇头广播消息的及时传输，本文在进行簇头选举的时候，综合考虑了以下3种因素:①车辆节点度数;②链路剩余时间;③信道的信噪比，并且，各因素的权重因子可以根据系统的要求进行动态的调整。

1.1 簇的形成

道路上的所有车辆广播HELLO消息，HELLO消息中包含车辆自身的ID号、速度、自身的位置信息等。车辆节点n收到其周围一跳邻居车辆广播的HELLO消息之后，计算自己的权值，下面是权值计算的具体过程。

1)车辆节点n确定自己的邻居车辆节点数N，并将其作为车辆节点n的度数dn(本文所考虑的邻居节点为车辆n周围的一跳车辆节点)。

2)对于车辆节点n，计算其理想度数与其度数差值的比值Δv=δ/|dn－δ|，其中，δ定义为理想度数，表示一个节点所能处理的最高车辆节点数。

3)对于车辆节点n，计算其与所有邻居车辆节点的总链路剩余时间Tn=，其中，ti=，表示车辆节点n与其邻居车辆节点i的链路剩余时间，其中，vn，vi分别为车辆n和邻居车辆i当前的速度;800 m为车辆的最大通信范围;dn，i为当前车辆n和其邻居车辆i之间的距离。

5)计算车辆节点n的综合权值，Wv=w1Δv+w2Tn+w3Ψ(n)，其中，w1，w2，w3为系统参数的权值因子，并且w1+w2+w3=1。

车辆节点n在计算完自己的权值之后，与其周围邻居车辆节点进行权值的比较，选取具有最大Wv值的车辆作为簇头，如果Wv相等，则选取具有较小ID的车辆作为簇头。同时簇头广播其状态的变化，并以簇头(初始化化后ID号为1)为核心，按照距离簇头的远近，先初始化簇头后面的车辆，再初始化簇头前面的车辆。该簇头的一跳邻居节点成为该簇头的成员节点，并且簇头的邻居节点不再参与簇头的选举。如果其一跳邻居节点为空，则其自己成为独立簇头。

1.2 簇的维护

车辆在分簇之后，由于车辆在不断的移动，所以随时会导致簇的拓扑发生变化，因此，需要对簇进行必要的维护。在对簇进行维护的时候，通常考虑以下3种情况。

1)簇形成之后，簇头会自动维护一个邻居列表，如果一定周期内，簇头没有收到其成员节点发来的数据消息，簇头自动会将从其邻居表中删除。

2)当一个簇成员节点移出当前簇的传输范围，其会广播一个Find-CH消息，Find-CH消息中包含自身的ID号。如果有簇头收到Find-CH消息，其将会回复一个CH-ACK消息，CH-ACK消息中包含自身的ID号和权值。簇成员节点选择具有最大权值的簇头作为其新的簇头。这时，簇成员节点将会成为这个簇头的成员节点。如果簇成员节点在一定的周期内没有收到来自簇头的CH-ACK消息，它自己就会成为簇头节点。

3)当2个簇头进入彼此的传输范围时，如果其中一个为独立簇头，则该独立簇头将会成为另外一个簇的成员节点。如果2个簇头都为独立簇头，则权值较大的簇头成为新的簇头，另外一个簇头成为其成员节点。如果2个簇头都非独立簇头，则重新进行分簇。

2 基于分簇算法的广播协议

2.1 现有802.11p协议中的消息分类机制

在VANETs中，为了更加有效地传输消息，IEEE标准化组织于2010年7月正式颁布了IEEE 802.11p协议。在802.11p协议中，根据消息的紧急级别和时延的需要，802.11p协议定义了8个不同级别的用户优先级和4个不同的接入级别，8个不同级别的用户优先级映射到4个不同的接入级别的队列中。4个不同的接入级别分别是AC_VO，AC_VI，AC_BE和AC_BK，他们使用不同的仲裁帧间间隔(AIFS)，最小竞争窗口(CWmin)和最大竞争窗口(CWmax)［8-9］。如表1和图1所示。

表1 4类消息的竞争窗口Tab.1 Contention windows of different application categories

图1 各种IFS之间的关系Fig.1 Some IFS relationships

从表1和图1可以看出，传输的消息越紧急，其优先权越高，其拥有的竞争窗口和AIFS也越小，其信道接入和信息传输机会也就越大。例如:AC_VO的接入类型值最高，这也就意味着AC_VO将会取得最高的信道接入和信息传输机会。因此，在进行信道接入和信息传输时，也将会优先对待高优先级的接入类型，而不是低优先级的接入类型。

2.2 消息的紧急程度

在VANETs中，簇头往往需要及时地向簇成员广播紧急消息、路况消息等一系列紧急消息。在现有的802.11p协议和分簇机制中，虽然簇头所传输的广播消息(紧急消息)的优先级都比较高，但在高速行驶的公路上，并不能很好地保证广播消息的及时传输。为了保证广播消息得到及时有效地传输，本文在基于多权值的分簇算法的基础上，提出了一个反映车辆传输信息紧急程度的公式，其具体的定义如下:(1)式中:Ωi为每个车辆所发消息的紧急程度;i为簇头传输范围内每个车辆的ID号;K为当前簇头传输范围内的车辆密度，其计算公式为K=AN/TN，其中，AN为当前簇头传输范围内道路上实际车辆的数目;TN为当前簇头传输范围内道路上所能容纳的最大车辆数。例如，当前簇头的传输范围 TR为800 m，同一车道的车辆之间的安全距离为100 m。在双车道的高速路上，TN=［800/100］×2=16，AN的值是簇头通过获取其传输范围车辆的信息而得到。假设AN的值为10，则 K=AN/TN=10/16=0.625。公式(1)所反映的每辆车所发消息的紧急程度如图2所示。

图2 车辆消息的紧急程度Fig.2 Emergency level of the vehicle news

由于簇头的ID号为1，从图2可以看出，在车辆密度较小的时候，簇头所传输的广播消息的紧急程度较大，其它ID号的车辆所发消息的紧急程度则很小，几乎为零且相同，说明此公式能够很好地反应广播消息的紧急程度，有利于广播消息的及时传输。在高速公路上，车辆往往比较稀疏，且簇头(ID号为1)承担着广播消息的任务，采用消息紧急程度机制来初始化二进制退避算法的竞争窗口，有利于减小广播消息的接入时延，从而达到广播消息快速传输的效果。

2.3 改进的退避算法

在IEEE 802.11p协议中，每辆车在发送消息前，先检测信道是否空闲，如果信道空闲，则在等待一段时间AIFS［i］后(如果这段时间内信道一直是空闲的)就发送整个数据帧，并等待确认。如果检测到信道忙或者车辆发送的消息因竞争信道而发生冲突，则进入退避过程，从 0和初始竞争窗口CW［AC］随机选择一个数作为退避计时器的初始值，即:CW［AC］的初始值设为 CWmin［AC］，当检测到信道持续空闲时，每经过一个空闲时隙，就将其退避计数器的值减1，当退避计数器的值为零时，这辆车才开始发送消息。若在退避计数器退避的过程中，信道变为忙的状态，则冻结退避计数器，等到信道空闲后，再次启动退避计数器，直到其值退避到0，这辆车才开始发送消息。当再次检测到信道忙或者车辆发送的消息因竞争信道而发生冲突，CW［AC］×(1－Ωi)的值就倍乘，即:(CW［AC］×(1－Ωi)+1)×2－1，当 CW［AC］×(1－Ωi)增加到 CWmax［AC］时，就维持CWmax［AC］的值不变，不再增加，直到数据被正确接收或者因重传次数超过了最大值而被丢弃。当消息发送成功后，竞争窗口恢复到初始化状态—CW［AC］×(1－Ωi)。若多个退避计数器同时减为0，则高优先级消息优先接入信道。

3 仿真结果和性能分析

3.1 仿真模型

本文使用NCTUns 6.0仿真软件进行仿真。在500 m×500 m一维区域内布置一个单向双车道(每个车道宽5 m)道路。车辆的速度在(15 m/s，30 m/s)随机选择。在道路上，随机进行车辆的布置，选举出的簇头向其邻居车辆广播消息，同时其邻居车辆也向簇头传输消息。车辆节点的行驶路线在仿真的过程中自动生成。权值因子w1=0.2，w2=w3=0.4。其具体的仿真参数设置如表2所示。为了评估本协议的性能，在同一仿真场景下仿真5次，对其取平均值。

3.2 仿真结果

图3是簇头广播消息的吞吐量在2种机制之间的比较。从图3中可以看出，改进的退避算法能够在一定程度上提高广播消息的吞吐量。这主要是由于降低了广播消息的竞争窗口，减小了其他车辆接入信道的概率所致。

图4比较了2种机制的广播消息的传输时延情况。从图4中可以看出，改进的退避算法在车辆密度稀疏的环境中，能够明显地减小广播消息的传输时延，这主要是由于在车辆稀疏的环境中，广播消息的紧急级别明显高于其他消息的紧急级别所致。

表2 仿真参数设置Tab.2 Simulation parameters

图3 广播消息的吞吐量Fig.3 Throughput of broadcast messages

图4 广播消息的时延Fig.4 Delay of broadcast messages

图5是广播消息的时隙利用率在2种机制方面的比较，由图5可见，在车辆密度较高的环境中，改进的退避算法并没有太多的优势，主要是因为在车辆密度高的环境中，信道负载较重，同时由于广播消息的紧急级别不是很高，所以，随着车辆密度的增大，广播消息的时隙利用率就随之减小。

因此，改进的退避算法在车辆密度稀疏的情况下，能够有效地进行广播消息的传输，有利于避免交通事故的发生。

图5 广播消息的时隙利用率Fig.5 Slot utilization of broadcast messages

4 结束语

本文所提出的簇机制，综合考虑了车辆节点度数、链路剩余时间和信道的信噪比等因素，使得对簇头的选取更为合理，能够在最大的程度上提升簇的稳定性，减小簇维护的开销。基于此簇机制的改进的退避算法，能够进一步减小广播消息的传输时延。通过最后的仿真说明，基于此分簇机制的优化的退避算法，能够有效地减小广播消息的传输时延、提高广播消息的吞吐量和时隙利用率。但改进的退避算法，在信道接入方面，会对其他的车辆节点产生影响，以至影响其他车辆节点的公平性和传输效率。

［1］YUJI K，SASASE I.A stable clustering scheme by prediction of the staying time in a cluster for mobile Ad hoc networks［C］//IEEE.Asia-Pacific Conference on Communication(APCC).Tokyo:IEEE Press，2008:1-5.

［2］DROR E，AVIN C，LOTKER Z.Fast randomized algorithm for hierarchical clustering in Vehicular Ad-Hoc Networks［C］//IEEE.The 10th IFIP Annual Mediterranean.Sicily:IEEE Press，2011:1-8.

［3］MEHTA S，SHARMA P，KOTECHA K.A survey on various cluster head election algorithms for MANET［C］//IEEE.Nirma University International Conference on Engineering(NUiCONE).Gujarat:IEEE Press，2011:1-6.

［4］AKBARI A，KHOSROZADEH A，LASEMI N.Clustering algorithms in mobile ad hoc networks［C］//IEEE.Fourth International Conference on Computer Sciences and Convergence Information Technology(ICCIT).Seoul:IEEE Press，2009:1509-1513.

［5］NI Minming，ZHONG Zhangdui，WU Hao，et al.A new stable clustering scheme forhighly mobile ad hoc networks［C］//IEEE. Wireless Communications and Networking Conference(WCNC).Sydney:IEEE Press，2010:1-6.

［6］ALASMARY W，ZHUANG Weihua.The Mobility impact in IEEE 802.11p Infrastructureless vehicular networks［C］//IEEE.Vehicular Technology Conference(VTC).Ottawa:IEEE Press，2010:1-5.

［7］ROMDHANI L，NI Qiang，TURLETTI T.Adaptive EDCF:enhanced service differentiation for IEEE 802.11 wireless ad-hoc networks［C］//IEEE.Wireless Communications and Networking Conference(WCNC).New Orleans:IEEE Press，2003:1373-1378.

［8］IEEE Std 1609.11-2010，IEEE Standard for wireless access in vehicular environments(WAVE)-over-the-air electronic payment data exchange protocol for intelligent transportation systems(ITS)［S］.2011:1-62

［9］WANG Y，AHMED A，KRISHNAMACHARI B，et al.IEEE 802.11p performance evaluation and protocol enhancement［C］//IEEE.IEEE International Conference on Vehicular Electronics and Safety(ICVES).Columbus:IEEE Press，2008:317-322.