適用于車載自組織網(wǎng)絡(luò)的穩(wěn)定成簇算法*

徐 圳，黃 瓊，唐 倫，陳前斌

(重慶郵電大學(xué) 移動(dòng)通信技術(shù)重慶市市級重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

在MANET網(wǎng)絡(luò)中，網(wǎng)絡(luò)層次劃分有拓?fù)涔芾矸奖?、能量利用高效、?shù)據(jù)融合簡單等優(yōu)點(diǎn)，成為當(dāng)前重點(diǎn)研究的技術(shù)。在分級結(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)重，算法一般描述為：

其中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)性小的場景。

負(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ò)場景中。參考文獻(xiàn)[8]提出了一種新的成簇算法，專用于車載自組織網(wǎng)絡(luò)，該算法把速度作為主要影響成簇的因素，并對速度采用模糊處理提高了成簇的穩(wěn)定性。算法還選擇一個(gè)權(quán)重第二優(yōu)的節(jié)點(diǎn)作為臨時(shí)簇頭，當(dāng)簇頭突然失效時(shí)臨時(shí)簇頭就充當(dāng)簇頭直到選出新的簇頭。雖然該算法用于高速移動(dòng)的場景，但是當(dāng)簇頭速度變化較大時(shí)，簇頭更換也較為頻繁，由于網(wǎng)絡(luò)拓?fù)渥兓?，臨時(shí)簇頭的性能不穩(wěn)定會(huì)降低成簇的穩(wěn)定性。

Affinity Propagation(AP)聚類算法[9]是近年來提出的較穩(wěn)定的類聚算法之一。它根據(jù)N個(gè)數(shù)據(jù)點(diǎn)之間的相似度進(jìn)行聚類，這些相似度可以是對稱的，即兩個(gè)數(shù)據(jù)點(diǎn)互相之間的相似度相同(如歐氏距離)；也可以是不對稱的,即兩個(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)定成簇算法，該算法適合速度變化較大的場景。

2 SD算法描述

假設(shè):(1)每個(gè)車輛都裝有GPS設(shè)備,可以隨時(shí)準(zhǔn)確知道自己的位置坐標(biāo)，速度表提供車輛速度信息;(2)每個(gè)節(jié)點(diǎn)配備一個(gè)半雙工全向天線?？梢越邮崭鱾€(gè)方向發(fā)出的信號;(3)車輛的通信范圍為250 m。

2.1 節(jié)點(diǎn)移動(dòng)性描述

車載自組織網(wǎng)絡(luò)中節(jié)點(diǎn)移動(dòng)性高，穩(wěn)定成簇必須考慮速度和距離兩個(gè)因素。引入相似度來表示節(jié)點(diǎn)之間的關(guān)系，將節(jié)點(diǎn)i與其鄰居節(jié)點(diǎn) j的相似度 S(i，j)表述為：

其中，Pi表示車輛i當(dāng)前的位置，它是一個(gè)二維向量;Pi′表示車輛i的預(yù)測位置;預(yù)測位置根據(jù)當(dāng)前的速度(vx,vy);Tf表示預(yù)測時(shí)間，預(yù)測時(shí)間越短計(jì)算越精確，但是會(huì)導(dǎo)致簇頭的頻繁變動(dòng)，預(yù)測時(shí)間太長會(huì)導(dǎo)致位置預(yù)測不準(zhǔn)確。為了預(yù)測公平，本文的預(yù)測時(shí)間定義為：

其中dtransmit為節(jié)點(diǎn)最大通信距離，vmax表示節(jié)點(diǎn)的最大速度。為了讓相似度與后面的節(jié)點(diǎn)度單位歸一化，把相似度除以25，因?yàn)榧僭O(shè)車輛的最大通信距離為250 m。在車載自組織網(wǎng)絡(luò)中傳輸環(huán)境惡劣，突發(fā)因素很多，會(huì)造成相似度計(jì)算值不穩(wěn)定，從而導(dǎo)致簇頭的頻繁更換，引入阻尼系數(shù)，主要起收斂作用。每一次相似度的更新都與前一次計(jì)算的值和當(dāng)前計(jì)算的值有關(guān)，可表示為：S=αSnew+(1-α)Sold，這里 α 取為 0.5。

MANET的成簇算法文章中，有很多算法都用速度和位置作為選擇簇頭的依據(jù),類似于本文。它們描述節(jié)點(diǎn)的移動(dòng)性M為：

其中a、b為權(quán)值系數(shù)，Pi表示車輛i當(dāng)前的位置，同于式(2)。Vi是車輛i的速度，它仍然是二維向量表示當(dāng)前的速度(vx,vy)。與所有鄰居節(jié)點(diǎn)的平均移動(dòng)性M越小越容易成為簇頭。假設(shè)有兩個(gè)節(jié)點(diǎn)i和j。由于兩種算法都用到了當(dāng)前節(jié)點(diǎn)距離，不考慮主要分析速度差與預(yù)測位置之間的差異。不考慮當(dāng)前節(jié)點(diǎn)的位置情況下用兩種方法算出各自的權(quán)值：

其 中vx′2、 vy′2表示節(jié)點(diǎn)之間的速度差 ，x′、y′表示節(jié)點(diǎn)之間的位置差。在車載自組織網(wǎng)絡(luò)中車輛運(yùn)動(dòng)速度可能會(huì)相差很大，權(quán)重M會(huì)頻繁改變，這樣會(huì)導(dǎo)致簇頭頻繁地改變，如果速度大的單獨(dú)成簇則會(huì)增加路由的跳數(shù)從而影響路由性能。圖1所示，假設(shè)節(jié)點(diǎn)1為節(jié)點(diǎn)2的簇頭，經(jīng)過一段預(yù)測時(shí)間后，根據(jù)預(yù)測距離算法，發(fā)現(xiàn)節(jié)點(diǎn)1更適合作為節(jié)點(diǎn)2的簇頭。但是它們的速度差卻很大，根據(jù)速度差算法節(jié)點(diǎn)1并不適合作為節(jié)點(diǎn)2的簇頭，可能會(huì)導(dǎo)致簇頭改變。

圖1 節(jié)點(diǎn)位置變化對比

2.2 節(jié)點(diǎn)度描述

相似度不能作為選擇簇頭的唯一依據(jù)。如圖2，圖中節(jié)點(diǎn)2只有節(jié)點(diǎn)1一個(gè)鄰居，且相距很近所以節(jié)點(diǎn)2的平均相似度很大，但是如果選擇節(jié)點(diǎn)1作為簇頭，節(jié)點(diǎn)3、4為簇頭管轄的兩跳節(jié)點(diǎn)。這樣增加了傳輸跳數(shù)，增加了簇的數(shù)目，這樣引入了節(jié)點(diǎn)度。選擇最高節(jié)點(diǎn)度的目標(biāo)是盡量減少簇的數(shù)目。引入該算法的優(yōu)點(diǎn)在于簇的數(shù)目較少，因此由簇頭節(jié)點(diǎn)和網(wǎng)關(guān)所構(gòu)成的上層網(wǎng)絡(luò)具有更加精簡的結(jié)構(gòu)，從而減少了網(wǎng)絡(luò)中分組投遞的跳數(shù)和平均時(shí)延。

圖2 節(jié)點(diǎn)度對比

2.3 簇頭選擇

每個(gè)節(jié)點(diǎn)都計(jì)算自己與所有鄰居的相似度，并取平均值。再加上自身的節(jié)點(diǎn)度，算法如下：

其中，Saver為節(jié)點(diǎn)的平均相似度。λ、μ為設(shè)定參數(shù)，可以根據(jù)不同的場景進(jìn)行修改 (本文設(shè)置為 0.5、0.5)。N為節(jié)點(diǎn)的鄰居個(gè)數(shù)。W值最高的節(jié)點(diǎn)則為簇頭。每個(gè)節(jié)點(diǎn)通過hello消息包獲得鄰居的信息，包中的內(nèi)容包括的信息如圖3所示。

圖3 hello包頭內(nèi)容

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ò)都參與簇頭的競爭，設(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)值對比，如果自己的權(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對算法性能進(jìn)行評估。

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)。

簇的穩(wěn)定性可以從簇頭服務(wù)時(shí)間衡量。簇頭服務(wù)時(shí)間是指每個(gè)簇頭從成為簇頭到變?yōu)槠胀ü?jié)點(diǎn)的平均服務(wù)時(shí)間Tlaivfe

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

4.2 仿真結(jié)果

本文在三個(gè)場景下分析SD算法的優(yōu)劣,并用minid和max-degree成簇算法進(jìn)行對比。如表 1～表 3，圖 4～圖6所示。

表1 場景1

表2 場景2

表3 場景3

從仿真結(jié)果可以看出，min-id與max-degree成簇算法在節(jié)點(diǎn)運(yùn)動(dòng)性高的場景中，性能下降得快。簇頭持續(xù)時(shí)間SD成簇算法在沒有增加或減少簇頭個(gè)數(shù) (即路由跳數(shù))的情況下，提高了成簇的穩(wěn)定性；在速度變化大、節(jié)點(diǎn)個(gè)數(shù)不多的情況下，提高更為明顯，非常適合于車載自組織網(wǎng)絡(luò)的成簇路由中。

圖4 簇頭個(gè)數(shù)隨通信范圍的變化

圖5 簇頭持續(xù)時(shí)間隨節(jié)點(diǎn)個(gè)數(shù)的變化

圖6 簇頭持續(xù)時(shí)間隨速度變化

成簇路由在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ò)中的性能。

[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-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.