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

    在MANET网络中，网络层次划分有拓扑管理方便、能量利用高效、数据融合简单等优点，成为当前重点研究的技术。在分级结构中，网络中的节点逻辑上被划分为簇，每个簇通常由1个簇头和多个普通节点组成，簇有利于降低路由开销、改善网络延迟。CBRP协议[1](Cluster Based Routing Protocol)是最早的Ad Hoc分簇路由协议之一，也是一种基于分簇结构的源路由按需路由协议。成簇算法是成簇路由的关键，好的成簇算法可以提高传输的投递率，减少路由的跳数。改善成簇算法、提高成簇的稳定性，是将MANET中的成簇路由引入VANET中关键技术。
1 几种典型成簇算法
    最小ID算法[2]是最早的成簇算法，即在成簇范围内选择ID最小节点作为簇头。在VANET中，节点快速移动、网络拓扑频繁变化、链路不稳定，使用最小ID算法会造成簇不稳定、簇头变化快，从而影响传输的实时性，增大了网络的丢包率。
    最高节点度分簇算法[3]借鉴了因特网中选择路由器的方法，尽可能减少路由器的数目，节点之间通过交互控制消息知道其他节点的邻居节点数目，拥有相邻节点最多的节点被选举为簇头。该算法的优点在于路由的跳数少，从而减少了网络中分组投递的平均时延。但是该算法不限制簇内的节点数，簇的资源按照轮询的方式共享，当簇内节点数量过多时，每个用户节点的吞吐量急剧下降，使得整个系统的性能也随之降低。当节点运动速度快时，簇头的更换频率也会急剧上升，导致大量的簇维护开销，不适用于高移动性的车载网路。
    节点权重分簇算法[4-6]是在考虑多个因素的基础上，根据节点适合作为簇头的程度来为每个节点分配相应的权重，算法一般描述为：
    W=a×mobility+b×degree+c×erengy+d×else  (1)
其中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。

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分簇算法时，簇的稳定性应该作为最重要的衡量标准。
  

节点个数不多的情况下，提高更为明显，非常适合于车载自组织网络的成簇路由中。
    成簇路由在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-logic-based 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.