适用于车载自组织网络的稳定成簇算法*

徐 圳，黄 琼，唐 伦，陈前斌

(重庆邮电大学 移动通信技术重庆市市级重点实验室，重庆 400065)

车载自组网络(VANET)是移动自组网络(MANET)的延伸，是智能交通系统(ITS)的重要组成部分，能有效地提高道路安全性，改善交通拥塞状况，满足人们对驾驶安全性和舒适性的要求。

在MANET网络中，网络层次划分有拓扑管理方便、能量利用高效、数据融合简单等优点，成为当前重点研究的技术。在分级结构中，网络中的节点逻辑上被划分为簇，每个簇通常由1个簇头和多个普通节点组成，簇有利于降低路由开销、改善网络延迟。CBRP协议[1](Cluster Based Routing Protocol)是最早的Ad Hoc分簇路由协议之一，也是一种基于分簇结构的源路由按需路由协议。成簇算法是成簇路由的关键，好的成簇算法可以提高传输的投递率，减少路由的跳数。改善成簇算法、提高成簇的稳定性，是将MANET中的成簇路由引入VANET中关键技术。

1 几种典型成簇算法

最小ID算法[2]是最早的成簇算法，即在成簇范围内选择ID最小节点作为簇头。在VANET中，节点快速移动、网络拓扑频繁变化、链路不稳定，使用最小ID算法会造成簇不稳定、簇头变化快，从而影响传输的实时性，增大了网络的丢包率。

最高节点度分簇算法[3]借鉴了因特网中选择路由器的方法，尽可能减少路由器的数目，节点之间通过交互控制消息知道其他节点的邻居节点数目，拥有相邻节点最多的节点被选举为簇头。该算法的优点在于路由的跳数少，从而减少了网络中分组投递的平均时延。但是该算法不限制簇内的节点数，簇的资源按照轮询的方式共享，当簇内节点数量过多时，每个用户节点的吞吐量急剧下降，使得整个系统的性能也随之降低。当节点运动速度快时，簇头的更换频率也会急剧上升，导致大量的簇维护开销，不适用于高移动性的车载网路。

节点权重分簇算法[4-6]是在考虑多个因素的基础上，根据节点适合作为簇头的程度来为每个节点分配相应的权重，算法一般描述为：

其中a、b、c、d为权值系数。mobility表示节点的移动性，degree表示节点度，energy表示剩余能量，else表示其他影响因素。考虑车载网路中的独特因素，节点剩余能量可以不予考虑，重点考虑车辆的移动性。选举更稳定的节点作为簇头增加数据传输的投递率。此方法的缺点是考虑的因素多、簇头变化频率多，适合于节点移动性小的场景。

负载平衡算法[7]、最小ID算法和最高节点度分簇算法都倾向于选择某些节点作为簇头，使得这些节点的负担较重，很容易耗尽能量。为此，需要在簇头间实施负载平衡，使所有节点都可以较公平地充当簇头。这种算法簇头的负载分布特性较好，但是簇结构很不稳定，而且在车载自组织网络中的车辆有充足的能量可以不予考虑。

随着车载自组织网络的发展，越来越多的成簇算法适合在车载自组织网络场景中。参考文献[8]提出了一种新的成簇算法，专用于车载自组织网络，该算法把速度作为主要影响成簇的因素，并对速度采用模糊处理提高了成簇的稳定性。算法还选择一个权重第二优的节点作为临时簇头，当簇头突然失效时临时簇头就充当簇头直到选出新的簇头。虽然该算法用于高速移动的场景，但是当簇头速度变化较大时，簇头更换也较为频繁，由于网络拓扑变化快，临时簇头的性能不稳定会降低成簇的稳定性。

Affinity Propagation(AP)聚类算法[9]是近年来提出的较稳定的类聚算法之一。它根据N个数据点之间的相似度进行聚类，这些相似度可以是对称的，即两个数据点互相之间的相似度相同(如欧氏距离)；也可以是不对称的,即两个数据点互相之间的相似度不等。相似度是AP算法中的重要因素，数据点i和点j的相似度记为S(i，j)。一般使用欧氏距离来计算，所有点与点的相似度值全部取为负值。参考文献[10]将AP类聚算法用于车载自组织网络中，大大提高了在高速多节点下成簇的稳定性。但是AP算法本身有自己的缺陷，AP算法是基于距离的成簇算法，当速度变化大时，簇头仍然更换较快，并且它需要大量的迭代循环算法，这增加了成簇的时延,并不能提高成簇路由的吞吐量和时延。

结合AP成簇算法和节点权重成簇算法的优缺点，本文提出了一种基于节点相似度和节点度的稳定成簇算法，该算法适合速度变化较大的场景。

2 SD算法描述

假设:(1)每个车辆都装有GPS设备,可以随时准确知道自己的位置坐标，速度表提供车辆速度信息;(2)每个节点配备一个半双工全向天线。可以接收各个方向发出的信号;(3)车辆的通信范围为250 m。

2.1 节点移动性描述

车载自组织网络中节点移动性高，稳定成簇必须考虑速度和距离两个因素。引入相似度来表示节点之间的关系，将节点i与其邻居节点 j的相似度 S(i，j)表述为：

其中，Pi表示车辆i当前的位置，它是一个二维向量;Pi′表示车辆i的预测位置;预测位置根据当前的速度(vx,vy);Tf表示预测时间，预测时间越短计算越精确，但是会导致簇头的频繁变动，预测时间太长会导致位置预测不准确。为了预测公平，本文的预测时间定义为：

其中dtransmit为节点最大通信距离，vmax表示节点的最大速度。为了让相似度与后面的节点度单位归一化，把相似度除以25，因为假设车辆的最大通信距离为250 m。在车载自组织网络中传输环境恶劣，突发因素很多，会造成相似度计算值不稳定，从而导致簇头的频繁更换，引入阻尼系数，主要起收敛作用。每一次相似度的更新都与前一次计算的值和当前计算的值有关，可表示为：S=αSnew+(1-α)Sold，这里 α 取为 0.5。

MANET的成簇算法文章中，有很多算法都用速度和位置作为选择簇头的依据,类似于本文。它们描述节点的移动性M为：

其中a、b为权值系数，Pi表示车辆i当前的位置，同于式(2)。Vi是车辆i的速度，它仍然是二维向量表示当前的速度(vx,vy)。与所有邻居节点的平均移动性M越小越容易成为簇头。假设有两个节点i和j。由于两种算法都用到了当前节点距离，不考虑主要分析速度差与预测位置之间的差异。不考虑当前节点的位置情况下用两种方法算出各自的权值：

其 中vx′2、 vy′2表示节点之间的速度差 ，x′、y′表示节点之间的位置差。在车载自组织网络中车辆运动速度可能会相差很大，权重M会频繁改变，这样会导致簇头频繁地改变，如果速度大的单独成簇则会增加路由的跳数从而影响路由性能。图1所示，假设节点1为节点2的簇头，经过一段预测时间后，根据预测距离算法，发现节点1更适合作为节点2的簇头。但是它们的速度差却很大，根据速度差算法节点1并不适合作为节点2的簇头，可能会导致簇头改变。

图1 节点位置变化对比

2.2 节点度描述

相似度不能作为选择簇头的唯一依据。如图2，图中节点2只有节点1一个邻居，且相距很近所以节点2的平均相似度很大，但是如果选择节点1作为簇头，节点3、4为簇头管辖的两跳节点。这样增加了传输跳数，增加了簇的数目，这样引入了节点度。选择最高节点度的目标是尽量减少簇的数目。引入该算法的优点在于簇的数目较少，因此由簇头节点和网关所构成的上层网络具有更加精简的结构，从而减少了网络中分组投递的跳数和平均时延。

图2 节点度对比

2.3 簇头选择

每个节点都计算自己与所有邻居的相似度，并取平均值。再加上自身的节点度，算法如下：

其中，Saver为节点的平均相似度。λ、μ为设定参数，可以根据不同的场景进行修改 (本文设置为 0.5、0.5)。N为节点的邻居个数。W值最高的节点则为簇头。每个节点通过hello消息包获得邻居的信息，包中的内容包括的信息如图3所示。

图3 hello包头内容

3 SD算法流程

SD算法的具体过程如下：

(1)初始化，每个节点都处于未分配状态。邻居数目N为 0，相似度 S=0，设置权值 W 为-1 000，设置自己的状态为U(未分配)。设置综合权值W为一个很低的负数,不设置为0，这是因为选择权值W最大的作为簇头,而相似度是一个负数，这样便于新节点的加入。

(2)节点进入网络，通过GPS获取自己的位置信息,通过速度表获得自己的速度信息和权值W。因为刚进入网络都参与簇头的竞争，设置自己的状态为CH，将获得信息加入hello包中广播给邻居节点。

(3)获得邻居节点hello包，提取邻居列表信息。通过式(2)计算自己与邻居节点的相似度，将邻居节点的信息与相似度存储到邻居列表中。当节点的状态为簇头存储两跳范围内的节点信息时,CM和GM分别存储。

(4)遍历邻居列表，获得邻居节点个数即节点度，计算出自己权值W并与邻居权值对比，如果自己的权值大于所有邻居节点的权值，设置自己的状态为CH，广播自己的位置、速度、状态以及W。否则设置自己的状态为CM，广播自己的位置、速度、状态、W以及邻居列表信息。

(5)当节点感知可达范围内有2个以上的簇头即收到多个簇头广播包，设置自己的状态为GM。广播自己的位置、速度、状态、W 信息。

4 仿真结果分析

为了验证SD算法的性能,使用NS2对算法性能进行评估。

4.1 算法性能衡量标准

(1)簇的数量

在相同的范围和相同的节点数量条件下，簇的数量直接影响了分簇算法的性能。簇的数量越多，意味着在相同距离内的平均跳数越多，从而信息传输的时延更大，并且投递率也会大大降低。簇头数量少虽然路由跳数少但是每个簇管理成员增多，这样给簇头造成很大的压力，从而影响路由性能。在分簇算法研究中，簇的数量是常用来衡量分簇算法性能的标准之一。

(2)簇的稳定性

簇的稳定性是所有衡量分簇算法性能的标准中最重要的一个。簇的稳定性越好，用来维护簇的开销就越小，路由的生存时间就越长，用于路由发现的开销也就越少，因此网络的吞吐量越大。因此在考虑VANET分簇算法时，簇的稳定性应该作为最重要的衡量标准。

簇的稳定性可以从簇头服务时间衡量。簇头服务时间是指每个簇头从成为簇头到变为普通节点的平均服务时间Tlaivfe

erage，可以用式(7)来表示:

4.2 仿真结果

本文在三个场景下分析SD算法的优劣,并用minid和max-degree成簇算法进行对比。如表 1～表 3，图 4～图6所示。

表1 场景1

表2 场景2

表3 场景3

从仿真结果可以看出，min-id与max-degree成簇算法在节点运动性高的场景中，性能下降得快。簇头持续时间SD成簇算法在没有增加或减少簇头个数 (即路由跳数)的情况下，提高了成簇的稳定性；在速度变化大、节点个数不多的情况下，提高更为明显，非常适合于车载自组织网络的成簇路由中。

图4 簇头个数随通信范围的变化

图5 簇头持续时间随节点个数的变化

图6 簇头持续时间随速度变化

成簇路由在MANET网络中占有非常重要的地位，但是在VANET中网络拓扑非常不稳定，合理的成簇算法是成簇路由应用在车载自组织网络中的关键所在。本文提出的基于节点相似度和最大节点度的成簇算法，增加了车载自组织网络中成簇的稳定性，提高了成簇路由在车载自组织网络中的性能。

[1]JIANG M,LI J,TAY Y.Cluster based routing protocol(CBRP)functional specification[Z].IETF Internet-Draft,Aug 1998.

[2]LIN C R,GERLA M.Adaptive clustering for mobile wireless networks[J].IEEE J.Select.Areas Communications,1997,15(7):1265-1275.

[3]GERLA M,TSAI J T.Tsai.Multicluster,mobile,multimedia radionetwork[J].Wirel.Netw.,1995(1):255-265.

[4]WU H,ZHONG Z,HANZO L.A cluster-head selection and updatealgorithm for ad hoc networks[C].Proc.IEEE Globecomm Conf.,2010:1-5.

[5]CHATTERJEE M,DAS S K,TURGUT D.WCA:A weighted clusteringalgorithm for mobile ad hoc networks[J].Cluster Computing,2002(5):193-204.

[6]杨卫东.用于Ad Hoc网络的分簇算法[J].北京邮电大学学报，2009,32(5)：61-65.

[7]YOUNIS O,FAHMY S.Heed:a hybrid,energy-efficient,distributed clustering approach for ad-hoc sensor networks[J].IEEE Trans.on Mobile Computing,2004,3(4):660-669.

[8]HAFEEZ K A,Zhao Lian,LIAO Zaiyi.A fuzzy-logicbased cluster head selection algorithm in VANETs[C].IEEE Communications(ICC),2012:203-207.

[9]FREY B J,DUECK D.Clustering by passing messages between datapoints[J].Science,2007,315:972-976.

[10]SHEA C,HASSANABADI B,VALAEE S.Mobility-based clustering in VANETs using affinity propagation[C].IEEE"GLOBECOM"2009.