車載自組網(wǎng)絡(luò)(VANET)是移動(dòng)自組網(wǎng)絡(luò)(MANET)的延伸,，是智能交通系統(tǒng)(ITS)的重要組成部分,，能有效地提高道路安全性，改善交通擁塞狀況,，滿足人們對(duì)駕駛安全性和舒適性的要求,。

    在MANET網(wǎng)絡(luò)中，網(wǎng)絡(luò)層次劃分有拓?fù)涔芾矸奖?、能量利用高效,、?shù)據(jù)融合簡(jiǎn)單等優(yōu)點(diǎn)，成為當(dāng)前重點(diǎn)研究的技術(shù),。在分級(jí)結(jié)構(gòu)中,，網(wǎng)絡(luò)中的節(jié)點(diǎn)邏輯上被劃分為簇，每個(gè)簇通常由1個(gè)簇頭和多個(gè)普通節(jié)點(diǎn)組成,，簇有利于降低路由開銷,、改善網(wǎng)絡(luò)延遲。CBRP協(xié)議[1](Cluster Based Routing Protocol)是最早的Ad Hoc分簇路由協(xié)議之一,，也是一種基于分簇結(jié)構(gòu)的源路由按需路由協(xié)議,。成簇算法是成簇路由的關(guān)鍵，好的成簇算法可以提高傳輸?shù)耐哆f率,，減少路由的跳數(shù),。改善成簇算法、提高成簇的穩(wěn)定性,，是將MANET中的成簇路由引入VANET中關(guān)鍵技術(shù)。
1 幾種典型成簇算法
    最小ID算法[2]是最早的成簇算法,，即在成簇范圍內(nèi)選擇ID最小節(jié)點(diǎn)作為簇頭,。在VANET中,，節(jié)點(diǎn)快速移動(dòng)、網(wǎng)絡(luò)拓?fù)漕l繁變化,、鏈路不穩(wěn)定,，使用最小ID算法會(huì)造成簇不穩(wěn)定、簇頭變化快,，從而影響傳輸?shù)膶?shí)時(shí)性,，增大了網(wǎng)絡(luò)的丟包率。
    最高節(jié)點(diǎn)度分簇算法[3]借鑒了因特網(wǎng)中選擇路由器的方法,，盡可能減少路由器的數(shù)目,，節(jié)點(diǎn)之間通過交互控制消息知道其他節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)目，擁有相鄰節(jié)點(diǎn)最多的節(jié)點(diǎn)被選舉為簇頭,。該算法的優(yōu)點(diǎn)在于路由的跳數(shù)少,，從而減少了網(wǎng)絡(luò)中分組投遞的平均時(shí)延。但是該算法不限制簇內(nèi)的節(jié)點(diǎn)數(shù),，簇的資源按照輪詢的方式共享,，當(dāng)簇內(nèi)節(jié)點(diǎn)數(shù)量過多時(shí)，每個(gè)用戶節(jié)點(diǎn)的吞吐量急劇下降,，使得整個(gè)系統(tǒng)的性能也隨之降低,。當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)速度快時(shí)，簇頭的更換頻率也會(huì)急劇上升,，導(dǎo)致大量的簇維護(hù)開銷,，不適用于高移動(dòng)性的車載網(wǎng)路。
    節(jié)點(diǎn)權(quán)重分簇算法[4-6]是在考慮多個(gè)因素的基礎(chǔ)上,，根據(jù)節(jié)點(diǎn)適合作為簇頭的程度來為每個(gè)節(jié)點(diǎn)分配相應(yīng)的權(quán)重,，算法一般描述為：
    W=a×mobility+b×degree+c×erengy+d×else  (1)
其中a、b,、c,、d為權(quán)值系數(shù)。mobility表示節(jié)點(diǎn)的移動(dòng)性,，degree表示節(jié)點(diǎn)度,，energy表示剩余能量，else表示其他影響因素,?？紤]車載網(wǎng)路中的獨(dú)特因素，節(jié)點(diǎn)剩余能量可以不予考慮,，重點(diǎn)考慮車輛的移動(dòng)性,。選舉更穩(wěn)定的節(jié)點(diǎn)作為簇頭增加數(shù)據(jù)傳輸?shù)耐哆f率。此方法的缺點(diǎn)是考慮的因素多,、簇頭變化頻率多,，適合于節(jié)點(diǎn)移動(dòng)性小的場(chǎng)景,。
    負(fù)載平衡算法[7]、最小ID算法和最高節(jié)點(diǎn)度分簇算法都傾向于選擇某些節(jié)點(diǎn)作為簇頭,，使得這些節(jié)點(diǎn)的負(fù)擔(dān)較重,，很容易耗盡能量。為此,，需要在簇頭間實(shí)施負(fù)載平衡,，使所有節(jié)點(diǎn)都可以較公平地充當(dāng)簇頭。這種算法簇頭的負(fù)載分布特性較好,，但是簇結(jié)構(gòu)很不穩(wěn)定,，而且在車載自組織網(wǎng)絡(luò)中的車輛有充足的能量可以不予考慮。
     隨著車載自組織網(wǎng)絡(luò)的發(fā)展,，越來越多的成簇算法適合在車載自組織網(wǎng)絡(luò)場(chǎng)景中,。參考文獻(xiàn)[8]提出了一種新的成簇算法，專用于車載自組織網(wǎng)絡(luò),，該算法把速度作為主要影響成簇的因素,，并對(duì)速度采用模糊處理提高了成簇的穩(wěn)定性。算法還選擇一個(gè)權(quán)重第二優(yōu)的節(jié)點(diǎn)作為臨時(shí)簇頭,，當(dāng)簇頭突然失效時(shí)臨時(shí)簇頭就充當(dāng)簇頭直到選出新的簇頭,。雖然該算法用于高速移動(dòng)的場(chǎng)景，但是當(dāng)簇頭速度變化較大時(shí),，簇頭更換也較為頻繁,，由于網(wǎng)絡(luò)拓?fù)渥兓欤R時(shí)簇頭的性能不穩(wěn)定會(huì)降低成簇的穩(wěn)定性,。
    Affinity Propagation(AP)聚類算法[9]是近年來提出的較穩(wěn)定的類聚算法之一,。它根據(jù)N個(gè)數(shù)據(jù)點(diǎn)之間的相似度進(jìn)行聚類，這些相似度可以是對(duì)稱的,，即兩個(gè)數(shù)據(jù)點(diǎn)互相之間的相似度相同(如歐氏距離),；也可以是不對(duì)稱的,即兩個(gè)數(shù)據(jù)點(diǎn)互相之間的相似度不等。相似度是AP算法中的重要因素,，數(shù)據(jù)點(diǎn)i和點(diǎn)j的相似度記為S(i,，j)。一般使用歐氏距離來計(jì)算,，所有點(diǎn)與點(diǎn)的相似度值全部取為負(fù)值,。參考文獻(xiàn)[10]將AP類聚算法用于車載自組織網(wǎng)絡(luò)中，大大提高了在高速多節(jié)點(diǎn)下成簇的穩(wěn)定性,。但是AP算法本身有自己的缺陷,，AP算法是基于距離的成簇算法，當(dāng)速度變化大時(shí),，簇頭仍然更換較快,，并且它需要大量的迭代循環(huán)算法,，這增加了成簇的時(shí)延,并不能提高成簇路由的吞吐量和時(shí)延,。
    結(jié)合AP成簇算法和節(jié)點(diǎn)權(quán)重成簇算法的優(yōu)缺點(diǎn),，本文提出了一種基于節(jié)點(diǎn)相似度和節(jié)點(diǎn)度的穩(wěn)定成簇算法，該算法適合速度變化較大的場(chǎng)景,。
2 SD算法描述
    假設(shè): (1)每個(gè)車輛都裝有GPS設(shè)備,可以隨時(shí)準(zhǔn)確知道自己的位置坐標(biāo),，速度表提供車輛速度信息;(2)每個(gè)節(jié)點(diǎn)配備一個(gè)半雙工全向天線?？梢越邮崭鱾€(gè)方向發(fā)出的信號(hào);(3)車輛的通信范圍為250 m,。

3 SD算法流程
     SD算法的具體過程如下：
    (1)初始化，每個(gè)節(jié)點(diǎn)都處于未分配狀態(tài),。鄰居數(shù)目N為0,，相似度S=0，設(shè)置權(quán)值W為-1 000,，設(shè)置自己的狀態(tài)為U(未分配),。設(shè)置綜合權(quán)值W為一個(gè)很低的負(fù)數(shù),不設(shè)置為0，這是因?yàn)檫x擇權(quán)值W最大的作為簇頭,而相似度是一個(gè)負(fù)數(shù),，這樣便于新節(jié)點(diǎn)的加入,。
    (2)節(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)，通過GPS獲取自己的位置信息,通過速度表獲得自己的速度信息和權(quán)值W,。因?yàn)閯傔M(jìn)入網(wǎng)絡(luò)都參與簇頭的競(jìng)爭(zhēng),，設(shè)置自己的狀態(tài)為CH，將獲得信息加入hello包中廣播給鄰居節(jié)點(diǎn),。
    (3)獲得鄰居節(jié)點(diǎn)hello包,，提取鄰居列表信息。通過式(2)計(jì)算自己與鄰居節(jié)點(diǎn)的相似度,，將鄰居節(jié)點(diǎn)的信息與相似度存儲(chǔ)到鄰居列表中,。當(dāng)節(jié)點(diǎn)的狀態(tài)為簇頭存儲(chǔ)兩跳范圍內(nèi)的節(jié)點(diǎn)信息時(shí),CM和GM分別存儲(chǔ)。
    (4)遍歷鄰居列表,，獲得鄰居節(jié)點(diǎn)個(gè)數(shù)即節(jié)點(diǎn)度,，計(jì)算出自己權(quán)值W并與鄰居權(quán)值對(duì)比，如果自己的權(quán)值大于所有鄰居節(jié)點(diǎn)的權(quán)值,，設(shè)置自己的狀態(tài)為CH,，廣播自己的位置、速度,、狀態(tài)以及W,。否則設(shè)置自己的狀態(tài)為CM，廣播自己的位置,、速度,、狀態(tài),、W以及鄰居列表信息。
    (5)當(dāng)節(jié)點(diǎn)感知可達(dá)范圍內(nèi)有2個(gè)以上的簇頭即收到多個(gè)簇頭廣播包,，設(shè)置自己的狀態(tài)為GM,。廣播自己的位置、速度,、狀態(tài),、W信息。
4 仿真結(jié)果分析
　　為了驗(yàn)證SD算法的性能,使用NS2對(duì)算法性能進(jìn)行評(píng)估,。
4.1 算法性能衡量標(biāo)準(zhǔn)
    (1)簇的數(shù)量
    在相同的范圍和相同的節(jié)點(diǎn)數(shù)量條件下,，簇的數(shù)量直接影響了分簇算法的性能。簇的數(shù)量越多,，意味著在相同距離內(nèi)的平均跳數(shù)越多,，從而信息傳輸?shù)臅r(shí)延更大，并且投遞率也會(huì)大大降低,。簇頭數(shù)量少雖然路由跳數(shù)少但是每個(gè)簇管理成員增多,，這樣給簇頭造成很大的壓力，從而影響路由性能,。在分簇算法研究中,，簇的數(shù)量是常用來衡量分簇算法性能的標(biāo)準(zhǔn)之一。
    (2)簇的穩(wěn)定性
    簇的穩(wěn)定性是所有衡量分簇算法性能的標(biāo)準(zhǔn)中最重要的一個(gè),。簇的穩(wěn)定性越好,，用來維護(hù)簇的開銷就越小，路由的生存時(shí)間就越長,，用于路由發(fā)現(xiàn)的開銷也就越少,，因此網(wǎng)絡(luò)的吞吐量越大。因此在考慮VANET分簇算法時(shí),，簇的穩(wěn)定性應(yīng)該作為最重要的衡量標(biāo)準(zhǔn),。
  

節(jié)點(diǎn)個(gè)數(shù)不多的情況下，提高更為明顯,，非常適合于車載自組織網(wǎng)絡(luò)的成簇路由中,。
    成簇路由在MANET網(wǎng)絡(luò)中占有非常重要的地位，但是在VANET中網(wǎng)絡(luò)拓?fù)浞浅２环€(wěn)定,，合理的成簇算法是成簇路由應(yīng)用在車載自組織網(wǎng)絡(luò)中的關(guān)鍵所在,。本文提出的基于節(jié)點(diǎn)相似度和最大節(jié)點(diǎn)度的成簇算法，增加了車載自組織網(wǎng)絡(luò)中成簇的穩(wěn)定性,，提高了成簇路由在車載自組織網(wǎng)絡(luò)中的性能,。
參考文獻(xiàn)
[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] 楊衛(wèi)東. 用于Ad Hoc 網(wǎng)絡(luò)的分簇算法[J]. 北京郵電大學(xué)學(xué)報(bào)，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.