基于加权的具有相同移动特性的车载自组网分簇算法

李 雪, 南建国

(1.空军工程大学研究生院，西安，710038；2.空军工程大学航空工程学院，西安，710038)

随着机动车、无线通信的不断发展，车联网也得到了迅猛发展。车载自组织网络[1]作为车辆网的一个分支，应用于智能交通系统中的安全预警、协助驾驶中。在军事应用方面，它可以很好地提升作战车队在通信、指挥控制和安全管理等方面的性能，提高作战效率。

车载自组织网络[2](Vehicular Ad-Hoc Network, VANET)是一种无中心、自组织、结构开放的车辆间通信网络。车载自组织网络中的路由分为平面路由和分级路由[3-5]，分簇算法就是车载自组网实施分级路由采取的重要方法。目前，很多学者对分簇算法进行了改进。如文献[6]将网络中的节点分为不同等级，但簇头的选举只考虑了能量一个因素，未考虑簇头节点与簇内成员的移动性和距离因素。文献[7]选择邻居节点多、与簇内大部分成员运动方向相同且移动速度慢的节点作为簇头，簇头节点比较稳定，若簇内大多数成员移动速度较快会导致簇成员的离开非常频繁。文献[8]选举簇头时采用“相对典型节点度”来衡量节点的稳定性，但没有考虑节点之间的距离因素。文献[9～10]在考虑簇头节点与簇内节点的距离因素时采用平均距离，这样不能剔除部分极端节点。文献[11～12]选举簇头时没有考虑簇头节点与簇内成员的距离因素，可能造成簇头节点与簇内成员节点相距较远。文献[13]使用多普勒频移计算节点间的相对移动速度，但在选择簇首时只考虑了节点的链路维持时间。

针对上述问题，本研究考虑作战车辆的移动特性问题，将具有速度相似度和距离相似度的作战车辆划分为一个簇，提高了簇结构的稳定性，防止因作战车辆因速度、方向、距离等问题频繁的离开或加入簇而带来的广播开销，降低作战效率。通过对节点的速度因子、距离因子和平均链路维持时间进行加权，选举出权值最大的作战车辆作为首要簇头，权值第2大的作战车辆作为次要簇头。首要簇头处于活跃状态时，次要簇头处于休眠状态，属于簇内普通节点；当首要簇头失效时，次要簇头处于活跃状态，充当首要簇头，避免了因竞争簇头带来的时延差从而提高通信质量。

1 分簇

在传统的车载自组织网络分簇算法中，一般用节点的速度差和平均速度来体现节点的移动特性，但只考虑这2个因素对移动特性的影响不够合理。本文通过对移动节点的速度和方向进行计算，采用速度差的标准差来体现节点的移动特性。根据移动节点的速度相似度和距离相似度对区域内的节点进行分簇，选择具有相同移动特性且距离相近的节点作为一个分簇。若在一个分簇中簇成员过少，则网络中的簇头就会增加，孤立节点也会增多；若在一个分簇中簇成员过多，则簇头节点的负担会加大，且与相邻簇头进行信息传递时会增大跳数。因此，需要平衡每个分簇中簇成员的大小。本文规定每个分簇中的簇成员的最大阈值为nmax。

1.1 移动节点的速度相似度

节点i为节点j的一跳通信范围内的任意节点，则节点j与邻居节点的速度相似度可以用速度差的标准差来反映。标准差[14]是节点j与邻居节点速度平均值离散程度的一种衡量，标准差的值越大，表示大部分节点的速度和平均速度的差异越大，标准差的值越小，表示大部分节点的速度越接近速度的平均值。

目标节点的运动方向作为x轴，以x轴逆时针旋转90°作为y轴。则节点i与节点j在x轴和y轴的速度差由下面的公式表示：

ΔVjx=Vjx-Vix=Vjcosβj-Vicosθi

(1)

ΔVjy=Vjy-Viy=Vjsinβj-Visinθi

(2)

式中：βj为节点j与x轴的夹角；θi为节点i与x轴的夹角。

设节点j一跳通信范围内的邻居节点i有N个，则节点j与邻居节点i在x轴和y轴上的平均速度差表示为：

(3)

(4)

节点j速度的相似度由节点j与邻居节点i在x轴和y轴的速度差的标准差表示为：

(5)

(6)

由勾股定理可以求出节点j与邻居节点i的速度差的标准差为：

(7)

若标准差δjv的值小于速度阈值q，则节点j与其邻居节点具有运动速度和运动方向的相似性。

1.2 移动节点的距离相似度

节点i为节点j的一跳通信范围内的任意节点，则节点j与邻居节点的距离相似度用距离差的标准差来反映。

(8)

式中：dji表示节点j与邻居节点i通过GPS获取的距离值。

(9)

若标准差的值δjd小于距离阈值p，则表明节点j与其邻居节点的距离相近，即具有距离的相似性。

如果速度标准差大于速度阈值q，则需要舍弃与节点j速度差最大的邻居节点i,若还大于q，依次类推进行舍弃直到满足条件。同理，如果距离标准差大于距离阈值p,则需要舍弃与节点j距离差最大的邻居节点i，若依然大于p，依次类推进行舍弃直到距离标准差小于p。只有当节点的速度标准差和距离标准差同时满足小于速度阈值和距离阈值时，则节点j与其邻居节点i才成为相似节点。若节点j与节点i是相似节点，节点i与节点s是相似节点，那么节点j与节点s也是相似节点，即相似节点具有传递性。所有的相似节点组成一个分簇，且每个簇的簇成员小于等于nmax。若簇成员大于nmax，则需要剔除与节点j速度差和距离差之和最大的邻居节点，直到满足簇内成员节点数小于等于nmax。

2 选举簇头

在传统的分簇算法中，一般选择簇头只是片面地考虑一个因素，且只是选举一个相对最优的节点作为簇头，一旦选举的簇头因移动速度过快或其他因素离开该簇时，需要进行簇头的重新选举，这样会因为延长数据传输的时延而降低效率。文中对移动节点的速度相似度、距离相似度、平均链路维持率进行加权，选举双簇头。

2.1 速度辅助因子

选举簇头的节点不仅要考虑它与周围邻居节点的速度是否相似，还应考虑该节点的加速度，选择加速度相对较小即速度变化缓慢的节点作为簇头。很多分簇算法在选举簇头时没有考虑节点的加速度，导致簇头移动速度变化很快而离开该簇，加大路由开销。在军事作战时，簇头的选举举足轻重，因此在本文中将速度与加速度结合作为选举簇头的一个权值。节点j加速度由下式表示：

(10)

式中：Vjt1、Vjt2分别表示节点j在t1、t2时刻通过GPS获取的速度值。

移动节点j与邻居节点i的速度差体现的是速度的相似性，标准差是为了剔除极端值，加速度是为了考虑节点在下一时刻的移动大小，经过归一化处理，速度辅助因子表示为:

(11)

2.2 距离辅助因子

在军事作战时还需要考虑节点j与目标节点的距离，这样选举的簇头可以缩短时延，提高效率。经过归一化处理，距离辅助因子表示为：

H2=e-(δjd+dj-end)

(12)

式中：dj-end表示节点j与目标节点的距离。

2.3 平均链路维持率

ΔVx=Vicosα+Vj

(13)

ΔVy=Vi|sinα|

(14)

图1 某时刻节点j与节点i的运动状态

ΔVx=|Vicos|α-π|-Vj|

(15)

ΔVy=Visin|α-π|

(16)

勾股定理求得节点j与节点i的相对速度为：

(17)

假设Tji表示的是节点j与节点i的链路维持时间，则在链路维持时间内两节点在x轴和y轴方向上的相对移动距离表示为：

Δdx=ΔVxTji

(18)

Δdy=ΔVyTji

(19)

由勾股定理，可以求得2个节点的相对移动距离为：

(20)

由图1可知，节点j与邻居节点i维持在通信范围内距离差满足：

(21)

式中：r为节点j的通信半径。

因此，可求得节点j与邻居节点i的最大链路维持时间，见式(22)：

(22)

根据上述方法可以求出节点j与邻居节点的链路维持时间和最大链路维持时间，并取其平均值：

(23)

(24)

经过归一化处理，平均链路的维持率表示为：

(25)

2.4 联合度量指标

由上述过程得到了节点j与邻居节点i的速度辅助因子、距离辅助因子和平均链路维持率，对这3种因素进行加权求和。根据节点权重分簇算法(Weighted Clustering Aorithm,WCA)[15]综合考虑这3个因素得到的复合权值如下：

Mi=ω1H1+ω2H2+ω3H3

(26)

式中：ω1、ω2、ω3的取值范围在0和1之间，并且满足ω1+ω2+ω3=1，具体大小根据实际情况取值。

依次计算簇内所有节点与邻居节点的Mi，取Mi值最大的作为首要簇头，取Mi值第2大的作为次要簇头。选取次要簇头的目的是当首要簇头失效时，次要簇头立即充当首要簇头，避免了因竞争簇头带来的时延差，且频繁的簇头轮换会产生额外的广播开销。

3 分簇算法及维护

3.1 分簇算法

本文在传统分簇算法的基础上，综合考虑了作战车辆的速度辅助因子、距离辅助因子和平均链路维持时间，并进行加权，选取权值最大的节点作为首要簇头，权值第二大的作为次要簇头。分簇算法的具体步骤如下所示：

步骤1网络初始化阶段，目标节点向作战区域内的所有节点广播自己的hello(infor)包，infor是节点的基本信息，包含ID号、位置信息、方向角、速度等。所有节点周期性的向邻居节点广播自己的hello信息。节点得到邻居节点的hello包，根据式(1)～(7)计算与相邻节点的δjv值。若δjv小于阈值q，则该节点与所有邻居节点具有速度相似度；反之剔除与该节点速度差最大的邻居节点，重新计算直到满足δjv小于阈值q。

步骤2根据式(8)～(9)计算与相邻移动节点的距离相似度，若δjd小于阈值p，则该节点与所有邻居节点具有距离相似度；反之剔除与与该节点距离差最大的邻居节点，并重新计算δjd的值，直到小于阈值p。当该节点与邻居节点同时满足速度和距离的相似度时，则该节点与邻居节点是关系节点，并将邻居节点的信息存储在自己的关系列表中。所有的关系节点就形成了一个分簇。

步骤3节点收集邻居节点的hello信息，通过连续2次获得的速度信息计算出邻居节点的加速度，根据式(10)～(11)计算出节点的速度辅助因子。

步骤4节点通过接收目标节点发来的hello信息，并结合自身的位置信息计算出与目标节点的距离。通过式(12)得到该节点的距离辅助因子。

步骤5以该节点的运动方向作为x轴，并根据与邻居节点的相对位置和运行方向通过式(13)～(25)得到该节点的平均链路维持率。

步骤6通过权重函数计算该节点的权重因子Mi，并与该簇内所有节点的权重因子进行比较，选取权重因子最大的值作为PCH，权重因子第二大的值作为SCH。PCH为簇内成员分配TDMA时隙，簇内成员只在被分配的时隙内将信息发送给簇头节点，其余时间则处于休眠状态。

步骤7重复步骤1～6，直到作战区域内的所有节点都确定了自己是普通节点或是簇头节点为止。

3.2 簇维护机制

当作战区域内的所有车辆节点都完成分簇后，由于节点无规则且剧烈的运动，会造成移动节点加入新簇或离开原来的簇，甚至会使得首要簇头或次要簇头的更新，增大路由的开销。因此，采取一种合理有效的簇维护机制[16]非常重要。网络中节点的状态有6个：孤立节点(Isolater Node，IN)、首要簇头(Primary Cluster Head，PCH)、次要簇头(Secondary Cluster Head，SCH)、簇成员(Cluster Member，CM)、伪孤立节点[17](Pseudo-Isolated Node，PIN)和网关节点(Gateway Node，GN)。当车载自组网的拓扑结构发生变化时，采用下面4种规则进行重新分簇。

1)删除簇内节点。当簇内的普通节点接收不到首要簇头广播的hello信息，或是首要簇头接收不到该普通节点广播的hello信息时，说明该节点已离开该簇。节点状态由CM变为PIN，若该节点长时间未回到该簇或加入其它簇，则状态由PIN变为IN。PIN状态的设置是为了避免频繁的簇维护加大路由开销。最后首要簇头将该节点从簇成员列表中删除。

2)新节点的加入。未加入任何簇的孤立节点通过向周围的邻居节点发送自己的hello信息来获得邻居节点的hello信息，通过计算与邻居节点的速度相似度和距离相似度，建立自己的关系节点列表。并向所有的关系节点发送信息来获取关系节点所在簇的首要簇头信息，再向这些首要簇头发送信息获取该节点与首要簇头的速度差和距离差之和，选取值最小的首要簇头且该簇的簇成员个数小于nmax，则加入该簇，该节点的状态由IN变为CM。最后首要簇头将该节点加入到簇成员列表中。

3)簇头的更换。当首要簇头接收不到簇内成员广播的hello信息或是簇内成员接收不到首要簇头广播的hello信息时，首要簇头失效，状态由PCH变为CM。则次要簇头成为首要簇头，状态由SCH变为PCH，且簇内成员节点通过竞争选取次要簇头。

4)簇的合并。当2个簇的簇头因为距离很近，且在一跳通信范围内时，其中一个簇的簇成员能够联系到另一个簇的首要簇头，则该簇成员的状态由CM变为GN。首先判断2个簇头与簇内成员是否为关系节点。若是关系节点则进行簇头的竞争，选择权重因子最大的值作为首要簇头，权重因子第2大的值作为次要簇头，竞争失败的簇头作为新簇头的簇成员，状态由PCH变为CM，其余节点全部为簇成员，且簇成员的个数不得大于nmax；若不是关系节点，说明这2个簇的速度相似度差别较大，它们此时只是在距离上比较相近，很快就会远离，当没有任何一个簇成员可以同时联系2个簇的首要簇头时，则该簇成员的状态由GN变为CM。因此这2个分簇不能合并为1个簇，否则会加大路由开销。

4 仿真与性能分析

采用NS-2软件对本文的分簇算法进行性能分析，并与经典的WCA算法和WBACA算法进行比较。仿真区域设为长宽各为300 m的矩形作战区域，作战车辆的运行速度为0～20 m/s，最大可接受的通信范围为25 m，将50～300辆作战车辆随机布置在作战区域内，仿真时间为400 s，ω1、ω2、ω3的权重值分别为0.48、0.32、0.2，仿真结果见图2～3。

图2 节点数量-分簇的平均数量

图2为不同节点数量下对应的分簇数量。WCA算法和WBACA算法在节点数为50时分簇的平均数量增长较快，本文算法在节点个数为200时分簇的平均数量增长迅速。当节点数量达到250时，本文算法的分簇平均数量与其它2种算法的差距最大。纵向来看，WBACA算法的分簇数量始终最少，而本文算法的分簇数量最多，因为本文为了平衡网络减少拥塞，设置了每个分簇中簇成员的最高阈值，使得每个分簇的成员不会过高从而保证簇间的通信质量。

图3 节点数-簇头节点更新数量

图3显示的是簇头节点更新的数量。当节点数为50时，3种算法的簇头更新数量相差不大，当节点数达到300时，本文算法的簇头节点更新数量为56，WBACA算法的簇头节点更新数量为89，WCA算法的簇头节点更新数量为108。簇头节点更新的数量越大，会造成簇结构变化很快，使得信道资源被维护簇结构所占用，降低信息传输的效率。纵向来看，本文的分簇算法簇头节点更新的数量始终最少，簇结构最稳定。这是因为本文在选举簇头时，综合考虑了速度因子、距离因子和链路的平均维持率，选择与簇成员具有最大速度相似度、最大距离相似度，且与簇成员维持通信时间最长的节点作为簇头，这样的簇头非常稳定，不易失效。即使失效了，次要簇头立即充当首要簇头的角色，避免了重新选举簇头造成的时延，防止路由性能降低。

图4显示的是分组投递率随着节点密度的变化。当节点数为50时，3种算法的分组投递率都较少且相差不大。当节点数为150时，3种算法的分组投递率都达到最大，WCA算法达到78%，WBACA算法达到89%，本文算法达到90%。分组投递率越高说明通信质量越好，当节点数较少时车辆分布不均匀，运动不规律，丢包率较严重，所以分组投递率都较低。随着节点数增加，3种算法的分组投递率都在增加。节点数增加到一定程度，即节点个数大于150时，分组投递率随之降低，这是因为节点数多了，网络拓扑结构变得复杂，且受到竞争、干扰等因素的影响，网络拥塞也较严重，造成消息丢失的概率也增加，但本文算法的分组投递率下降很缓慢，因为本文限制了簇成员的最大值，且簇头给每个成员分配了TDMA时隙，降低了簇间信息的干扰。整体来看，本文提出的分簇算法的分组投递率总是最高的，说明该算法的性能比另外2种算法优越。

图4 节点数-最大速度下的分组投递率

5 结语

本文提出的基于加权的具有相同移动特性的车载自组网分簇算法通过将具有相同移动特性且距离相近的节点划分为一个簇，提高了簇结构的稳定性。再通过对速度因子、距离因子和平均链路维持率进行加权选取首要簇头和次要簇头，主要簇头给每个成员分配了TDMA时隙，提高了通信的质量。但本文对路由分簇的考虑还不够全面，比如当簇头数量和簇覆盖范围具体为多少时路由性能最优未考虑，下一步需要进行更深层次的研究。