一种适用于VANET场景的自适应KHM成簇算法

葛先雷，章功干，权循忠，高 强

车辆自组织网络［1］（Vehicle Ad hoc NETwork，VANET）是一种特殊的移动通信自组织网络（Mobile Ad hoc NETwork，MANET），VANET以车辆作为其移动节点，通过车辆与车辆、车辆与基础设施等通信方式，构成人—车—路协同的无线移动通信网络.VANET中，车辆的快速移动特性以及接入点覆盖范围有限等因素导致部分车辆无法与AP进行直接通信，可通过采用中继车辆（Relay Vehicle，RV）协作转发实现源车辆（Source Vehicle，SV）与AP之间的数据传输［2］.针对特定应用场景，如密集分布车辆区域，可由地理距离较近的车辆构成簇［3］，通过在各簇内选择出簇头车辆，簇头车辆支持簇内车辆直接通信，簇间车辆通过簇头车辆进行中继转发，可有效降低路由控制信息开销、提高用户数据传输效率，并实现网络资源高效利用.

由于VANET具有车辆节点移动速度快，网络拓扑的快速变化等传统MANET网络所不具有的特性，针对传统KHM成簇算法应用于VANET成簇时存在的缺陷，如无法确定最终成簇数目，所成簇无法完全覆盖所有车辆，以致严重影响VANET性能，本文提出了一种适用于VANET场景的自适应KHM成簇算法，相对于传统KHM成簇算法，所提算法有以下改进.

为保证所选择出的簇头车辆具有足够可用资源为其簇成员车辆进行数据转发，根据每个车辆的可用带宽建立了候选簇头集合.

传统KHM成簇算法中，K需要事先给定，而实际上，K是非常难以估计的，因为很多时候，并不知道应该分成多少个簇才最合适，即无法确定所成簇的个数.本文给出了簇头数量的估计方法，并通过迭代，从而自适应地确定最终成簇的个数.

考虑到VANET的高动态性，根据车辆的移动性（主要包括车辆节点的相对速度及位置）建模了加权距离，作为该算法的距离度量.

1 VANET成簇的内涵及通信方式

VANET成簇是指将位置邻近的车辆节点通过一些规则，形成一个临时的移动自组织网络，为周围的车辆提供稳定可靠的无线接入服务.典型的VANET网络成簇场景如图1所示.在每个簇内，选择一个车辆作为簇头车辆节点，该簇头车辆为簇间的车辆提供数据转发，并对本簇内的簇成员车辆进行统一管理.

图1 VANET网络成簇场景

基于成簇的网络拓扑为分层网络结构，为了实现车辆节点的因特网接入服务和车辆间的通信，支持簇内通信和簇间通信两种通信方式.

1.1 簇内通信

如图1所示，在簇内通信场景下，车辆A和车辆B属于同一个簇.若车辆A拟与车辆B进行通信，首先车辆A将会判断车辆B是否在其通信半径范围内，若车辆B在车辆A的通信半径范围内，则车辆A与车辆B建立直接链路进行通信.而车辆A和车辆D虽然同属于一个簇，但若车辆A需与车辆D进行通信时，车辆D不在车辆A的通信半径范围内，则车辆A将以本簇的簇头车辆节点CHa作为中继车辆，与车辆D建立间接链路进行通信.

1.2 簇间通信

在簇间通信场景下，车辆A和车辆C属于两个不同的簇，对应簇头车辆分别为CHa和CHb.若车辆A和车辆C需进行通信，两车辆的簇头车辆节点CHa和CHb将作为中继车辆.车辆A首先将数据包发送到其簇头车辆节点CHa，CHb以直接或者多跳的方式将数据包转发到车辆B的簇头车辆节点CHa，最后CHb将数据包转发到簇成员车辆B.

相对于其他传统路由算法，基于成簇的路由算法具有以下优点.

在VANET网络中，成簇算法能有效地适应车辆密度及车辆的数量变化很大的场景，具有很好的可扩展性.

在成簇时，选择相对较“闲”的车辆作为簇头车辆，所选择出的簇头车辆为该簇内的簇成员车辆进行数据转发和统一管理，减少VANET网络中的冗余信令开销，以达到提高资源利用效率、提升网络性能，并实现VANET网络的负载均衡的目的.

由于车辆的高速移动，导致VANET网络拓扑频繁变化，成簇可延长簇的生存时间，使VANET网络相对稳定，从而保证VANET网络性能的稳定性和持续性.

簇外的远距离的车辆没有必要知道簇内具体细节，因为簇状态的概括性信息已经足够让远处的车辆做出控制决定.

2 K-Harmonic Means成簇原理

KHM成簇算法［4］已经广泛用于数据挖掘、统计分析、数据压缩等领域，是一种基于质心迭代的成簇算法，通过不断优化K个质心的位置，最终得到质心最优位置.KHM成簇算法执行步骤如下.

步骤1：确定所需要成簇数目K，且这K个簇质心的初始位置是随机分布的.

步骤2：定义KHM成簇算法目标函数：

式中：X为给定的N个数据点位置，C为K个质心位置，初始分布为随机分布，‖xi-x为第i个数据的位置xi与第k簇个质心的距离度量.

步骤3：fKHM(X ,C )对质心求偏导，更新第k个簇的质心最优位置←，经过一次迭代，更新所有K个质心的位置C={c1,c2,...cK}.

步骤4：当簇的K个质心的位置C={c1,c2,...cK}不再变化时，算法终止并得出所成簇的质心的最优位置.否则跳转到步骤2继续执行，直至算法结束.

3 自适应KHM成簇算法

3.1 候选簇头集合建立

簇头车辆为簇成员车辆的中继车辆进行数据转发，并实现对簇成员车辆的统一管理.在为簇成员车辆进行数据包转发时，簇头车辆会消耗一定的资源.由于车辆节点的传输带宽在业务传输性能上起决定的作用，具有较大可用带宽的车辆作为簇头车辆能为该簇成员车辆提供更好的性能.

在成簇过程中，只有车辆节点的可用带宽大于给点的门限，才允许被选择为簇头车辆［5］.建立候选簇头车辆集合S，该集合中所有车辆节点的可用带宽均大于给定带宽门限Bth，候选簇头集合为

3.2 初始成簇数目估计

应用传统KHM成簇算法时，需要事先对所成簇的数目进行确定，而对于车辆密度高的大规模VANET网络，很难确定所成簇的数目，本文提出了一种估计初始成簇数目的方法.在VANET网络场景中，因为道路长度远远大于其宽度，故忽略道路宽度.Kini为初始成簇数目，可由道路长度、车辆总数及车辆的通信半径共同决定，Kini可由式（3）得到：

式中：L为该区域路段长度，R为车辆节点通信半径，N为该区域所有车辆数目，Nmax为每个簇内所允许的最大簇成员车辆个数，为了降低所提出的自适应KHM算法的复杂度，建模Kini个初始簇质心的位置分布为均匀分布.

3.3 加权距离建模

传统KHM成簇算法的距离度量有欧氏距离、闵可夫斯基距离［6］或曼哈顿距离.但是由于车辆节点的移动速度快，致使VANET网络拓扑变化频繁.仅考虑车辆间的距离，可能会导致车辆间链路生存时间短，网络拓扑变化频繁，以致影响VANET网络的通信性能.而车辆节点的移动性主要是由车辆节点的速度及位置来表征的，故本文以车辆节点的相对速度及位置，建模了车辆节点间的加权距离Dik：

式中：xik= ||xi-，vik=|vi-v，xi、vi为第i个车辆节点的位置和速度，、为第k个簇的质心的位置和速度，α为相对速度的权重.

3.4 最优位置更新

以加权距离作为自适应KHM成簇算法的距离度量，该算法的目标函数为为了得到质心的一次迭代后更新的位置，最小化目标函数，通过对目标函数 f求偏导［7］，并令，可得第k个质心一次迭代后更新的位置.

3.5 算法流程

本节详细描述了提出的自适应KHM成簇算法流程，与传统KHM成簇算法不同，所提的自适应KHM成簇算法会由所估计出的初始成簇数目开始，对成簇数目进行自动迭代.所提算法首先根据所有车辆节点的可用带宽信息，建立候选簇头车辆集合S，该集合中所有车辆都有一定可用带宽资源.其次，由式（3）令成簇数目 K=Kini，通过最小化自适应KHM成簇算法目标函数，得到每轮迭代的簇头车辆更新后的最优位置，当簇头车辆节点集合中所有簇头车辆的的位置均不再变化时，停止迭代，得到每个簇的簇头车辆节点的最优位置.最后，将簇头车辆节点通信半径范围内的车辆节点声明为该簇的簇成员车辆，并判断所有车辆是否都已成簇，若所有车辆都已加入簇，则算法终止，否则，K=K+1，重复执行上述步骤.自适应K-Harmonic Means成簇算法的详细描述如下.

//车辆节点数为N，候选簇头集合为S，初始成簇数目K=Kini，且K个质心为均匀分布.

1.fori=1toNdo

2.if（  Bi≥ Bth） then

3. 第i个车辆加入候选簇头集合S

4.end if

5.end for

6.repeat

7.fori=1toNdo

8.将第i个车辆归属到离其最近的质心ck

9.end for

10.fork=1toKdo

11. fori=1toNdo

12. 更新簇质心ck位置

13. end for

14.end for

15.until所有质心的位置不再变化

16.fork=1toKdo

18.end for

19.i（f所有车辆均已加入簇）then

2. 算法终止

21.else

22. K=K+1，goto 6

23.end if

4 仿真分析

为验证所提算法的性能，仿真实现了所提出的自适应KHM成簇算法，并与传统KHM成簇算法进行比较.仿真场景为矩形道路模型，其它相关参数如表1所示.

图2和图3分别为在矩形道路场景下，车辆数为400时，传统KHM成簇算法和所提出的自适应KHM成簇算法的成簇场景.对于这两种成簇算法，由式（3），可计算出最初的成簇数目Kini=8.同样地，在图2中，传统KHM成簇算法不能实现对成簇数目的更新，所成簇数目为8，并且存在簇成员车辆在簇头车辆的通信半径范围以外，导致簇头车辆节点不能与簇成员车辆节点进行直接通信，将会严重影响VANET网络的通信性能.而在图3中，自适应KHM成簇算法能实现对所成簇数目的自适应更新，所成簇数目最终为10，并且所有的簇成员车辆均在其簇头车辆的通信半径范围内，能保证VANET网络的通信性能.

表1 仿真参数设置

图2 传统KHM成簇算法成簇场景

图3 自适应KHM成簇算法成簇场景

图4显示了在矩形道路场景下，数据包成功投递率与车辆速度的变化关系.通过图4可以看出本文所提出的自适应KHM成簇算法的数据包成功投递率高于传统KHM成簇算法（成簇数目分别为8、9、10、11），数据包成功投递率提高了约10%.这是由于本文所提出自适应KHM成簇算法在选择簇头车辆节点时，建立了候选簇头集合，保证了所选择的簇头车辆有足够的带宽为其簇成员车辆进行数据转发，并且通过建模车辆的加权距离，使所成的簇较为稳定.从图4中还可以看出，随着车辆速度的增加，两种算法的数据包成功投递率呈下降趋势.

图4 数据包成功投递率与车辆速度的关系

图5显示了在矩形道路场景下，VANET网络的平均传输时延随着车辆速度的变化关系，从图中可以看出本文所提出自适应KHM成簇算法较传统KHM成簇算法，平均传输时延缩短了30ms.这是由于在选择簇头车辆节点时，本文所提出的自适应KHM成簇算法所选择出的簇头车辆具有足够的带宽资源为其簇成员车辆进行数据转发.从图5中也可以看出，随着车辆速度的增加，两种算法的平均传输时延基本保持不变.

图5 平均传输时延与车辆速度的关系

图6为矩形道路场景下，吞吐量随着车辆速度的变化关系.从图6中可以看出本文所提出的自适应KHM成簇算法较传统KHM成簇算法，吞吐量较高.主要原因是本文所提出的自适应KHM成簇算法所形成的簇能实现对该区域内的所有车辆实现100%覆盖（比较图2与图3），而且所选择出的簇头车辆具有较大的带宽资源.

图6 吞吐量与车辆速度的关系

5 结论

针对传统KHM成簇算法应用于VANET成簇时存在的缺陷，本文提出了一种自适应VANET场景的自适应KHM成簇算法，通过对所提出适用于VANET的自适应KHM成簇算法进行仿真实现及性能评估，并和传统KHM成簇算法进行对比.仿真结果表明，本文所提出的成簇算法能实现对车辆节点的完全覆盖，且在数据包投递率、平均传输时延及吞吐量等指标上性能更优.