一種適用于VANET場景的自適應(yīng)KHM成簇算法

葛先雷，章功干，權(quán)循忠，高 強

車輛自組織網(wǎng)絡(luò)［1］（Vehicle Ad hoc NETwork，VANET）是一種特殊的移動通信自組織網(wǎng)絡(luò)（Mobile Ad hoc NETwork，MANET），VANET以車輛作為其移動節(jié)點，通過車輛與車輛、車輛與基礎(chǔ)設(shè)施等通信方式，構(gòu)成人—車—路協(xié)同的無線移動通信網(wǎng)絡(luò).VANET中，車輛的快速移動特性以及接入點覆蓋范圍有限等因素導(dǎo)致部分車輛無法與AP進(jìn)行直接通信，可通過采用中繼車輛（Relay Vehicle，RV）協(xié)作轉(zhuǎn)發(fā)實現(xiàn)源車輛（Source Vehicle，SV）與AP之間的數(shù)據(jù)傳輸［2］.針對特定應(yīng)用場景，如密集分布車輛區(qū)域，可由地理距離較近的車輛構(gòu)成簇［3］，通過在各簇內(nèi)選擇出簇頭車輛，簇頭車輛支持簇內(nèi)車輛直接通信，簇間車輛通過簇頭車輛進(jìn)行中繼轉(zhuǎn)發(fā)，可有效降低路由控制信息開銷、提高用戶數(shù)據(jù)傳輸效率，并實現(xiàn)網(wǎng)絡(luò)資源高效利用.

由于VANET具有車輛節(jié)點移動速度快，網(wǎng)絡(luò)拓?fù)涞目焖僮兓葌鹘y(tǒng)MANET網(wǎng)絡(luò)所不具有的特性，針對傳統(tǒng)KHM成簇算法應(yīng)用于VANET成簇時存在的缺陷，如無法確定最終成簇數(shù)目，所成簇?zé)o法完全覆蓋所有車輛，以致嚴(yán)重影響VANET性能，本文提出了一種適用于VANET場景的自適應(yīng)KHM成簇算法，相對于傳統(tǒng)KHM成簇算法，所提算法有以下改進(jìn).

為保證所選擇出的簇頭車輛具有足夠可用資源為其簇成員車輛進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，根據(jù)每個車輛的可用帶寬建立了候選簇頭集合.

傳統(tǒng)KHM成簇算法中，K需要事先給定，而實際上，K是非常難以估計的，因為很多時候，并不知道應(yīng)該分成多少個簇才最合適，即無法確定所成簇的個數(shù).本文給出了簇頭數(shù)量的估計方法，并通過迭代，從而自適應(yīng)地確定最終成簇的個數(shù).

考慮到VANET的高動態(tài)性，根據(jù)車輛的移動性（主要包括車輛節(jié)點的相對速度及位置）建模了加權(quán)距離，作為該算法的距離度量.

1 VANET成簇的內(nèi)涵及通信方式

VANET成簇是指將位置鄰近的車輛節(jié)點通過一些規(guī)則，形成一個臨時的移動自組織網(wǎng)絡(luò)，為周圍的車輛提供穩(wěn)定可靠的無線接入服務(wù).典型的VANET網(wǎng)絡(luò)成簇場景如圖1所示.在每個簇內(nèi)，選擇一個車輛作為簇頭車輛節(jié)點，該簇頭車輛為簇間的車輛提供數(shù)據(jù)轉(zhuǎn)發(fā)，并對本簇內(nèi)的簇成員車輛進(jìn)行統(tǒng)一管理.

圖1 VANET網(wǎng)絡(luò)成簇場景

基于成簇的網(wǎng)絡(luò)拓?fù)錇榉謱泳W(wǎng)絡(luò)結(jié)構(gòu)，為了實現(xiàn)車輛節(jié)點的因特網(wǎng)接入服務(wù)和車輛間的通信，支持簇內(nèi)通信和簇間通信兩種通信方式.

1.1 簇內(nèi)通信

如圖1所示，在簇內(nèi)通信場景下，車輛A和車輛B屬于同一個簇.若車輛A擬與車輛B進(jìn)行通信，首先車輛A將會判斷車輛B是否在其通信半徑范圍內(nèi)，若車輛B在車輛A的通信半徑范圍內(nèi)，則車輛A與車輛B建立直接鏈路進(jìn)行通信.而車輛A和車輛D雖然同屬于一個簇，但若車輛A需與車輛D進(jìn)行通信時，車輛D不在車輛A的通信半徑范圍內(nèi)，則車輛A將以本簇的簇頭車輛節(jié)點CHa作為中繼車輛，與車輛D建立間接鏈路進(jìn)行通信.

1.2 簇間通信

在簇間通信場景下，車輛A和車輛C屬于兩個不同的簇，對應(yīng)簇頭車輛分別為CHa和CHb.若車輛A和車輛C需進(jìn)行通信，兩車輛的簇頭車輛節(jié)點CHa和CHb將作為中繼車輛.車輛A首先將數(shù)據(jù)包發(fā)送到其簇頭車輛節(jié)點CHa，CHb以直接或者多跳的方式將數(shù)據(jù)包轉(zhuǎn)發(fā)到車輛B的簇頭車輛節(jié)點CHa，最后CHb將數(shù)據(jù)包轉(zhuǎn)發(fā)到簇成員車輛B.

相對于其他傳統(tǒng)路由算法，基于成簇的路由算法具有以下優(yōu)點.

在VANET網(wǎng)絡(luò)中，成簇算法能有效地適應(yīng)車輛密度及車輛的數(shù)量變化很大的場景，具有很好的可擴(kuò)展性.

在成簇時，選擇相對較“閑”的車輛作為簇頭車輛，所選擇出的簇頭車輛為該簇內(nèi)的簇成員車輛進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)和統(tǒng)一管理，減少VANET網(wǎng)絡(luò)中的冗余信令開銷，以達(dá)到提高資源利用效率、提升網(wǎng)絡(luò)性能，并實現(xiàn)VANET網(wǎng)絡(luò)的負(fù)載均衡的目的.

由于車輛的高速移動，導(dǎo)致VANET網(wǎng)絡(luò)拓?fù)漕l繁變化，成簇可延長簇的生存時間，使VANET網(wǎng)絡(luò)相對穩(wěn)定，從而保證VANET網(wǎng)絡(luò)性能的穩(wěn)定性和持續(xù)性.

簇外的遠(yuǎn)距離的車輛沒有必要知道簇內(nèi)具體細(xì)節(jié)，因為簇狀態(tài)的概括性信息已經(jīng)足夠讓遠(yuǎn)處的車輛做出控制決定.

2 K-Harmonic Means成簇原理

KHM成簇算法［4］已經(jīng)廣泛用于數(shù)據(jù)挖掘、統(tǒng)計分析、數(shù)據(jù)壓縮等領(lǐng)域，是一種基于質(zhì)心迭代的成簇算法，通過不斷優(yōu)化K個質(zhì)心的位置，最終得到質(zhì)心最優(yōu)位置.KHM成簇算法執(zhí)行步驟如下.

步驟1：確定所需要成簇數(shù)目K，且這K個簇質(zhì)心的初始位置是隨機(jī)分布的.

步驟2：定義KHM成簇算法目標(biāo)函數(shù)：

式中：X為給定的N個數(shù)據(jù)點位置，C為K個質(zhì)心位置，初始分布為隨機(jī)分布，‖xi-x為第i個數(shù)據(jù)的位置xi與第k簇個質(zhì)心的距離度量.

步驟3：fKHM(X ,C )對質(zhì)心求偏導(dǎo)，更新第k個簇的質(zhì)心最優(yōu)位置←，經(jīng)過一次迭代，更新所有K個質(zhì)心的位置C={c1,c2,...cK}.

步驟4：當(dāng)簇的K個質(zhì)心的位置C={c1,c2,...cK}不再變化時，算法終止并得出所成簇的質(zhì)心的最優(yōu)位置.否則跳轉(zhuǎn)到步驟2繼續(xù)執(zhí)行，直至算法結(jié)束.

3 自適應(yīng)KHM成簇算法

3.1 候選簇頭集合建立

簇頭車輛為簇成員車輛的中繼車輛進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，并實現(xiàn)對簇成員車輛的統(tǒng)一管理.在為簇成員車輛進(jìn)行數(shù)據(jù)包轉(zhuǎn)發(fā)時，簇頭車輛會消耗一定的資源.由于車輛節(jié)點的傳輸帶寬在業(yè)務(wù)傳輸性能上起決定的作用，具有較大可用帶寬的車輛作為簇頭車輛能為該簇成員車輛提供更好的性能.

在成簇過程中，只有車輛節(jié)點的可用帶寬大于給點的門限，才允許被選擇為簇頭車輛［5］.建立候選簇頭車輛集合S，該集合中所有車輛節(jié)點的可用帶寬均大于給定帶寬門限Bth，候選簇頭集合為

3.2 初始成簇數(shù)目估計

應(yīng)用傳統(tǒng)KHM成簇算法時，需要事先對所成簇的數(shù)目進(jìn)行確定，而對于車輛密度高的大規(guī)模VANET網(wǎng)絡(luò)，很難確定所成簇的數(shù)目，本文提出了一種估計初始成簇數(shù)目的方法.在VANET網(wǎng)絡(luò)場景中，因為道路長度遠(yuǎn)遠(yuǎn)大于其寬度，故忽略道路寬度.Kini為初始成簇數(shù)目，可由道路長度、車輛總數(shù)及車輛的通信半徑共同決定，Kini可由式（3）得到：

式中：L為該區(qū)域路段長度，R為車輛節(jié)點通信半徑，N為該區(qū)域所有車輛數(shù)目，Nmax為每個簇內(nèi)所允許的最大簇成員車輛個數(shù)，為了降低所提出的自適應(yīng)KHM算法的復(fù)雜度，建模Kini個初始簇質(zhì)心的位置分布為均勻分布.

3.3 加權(quán)距離建模

傳統(tǒng)KHM成簇算法的距離度量有歐氏距離、閔可夫斯基距離［6］或曼哈頓距離.但是由于車輛節(jié)點的移動速度快，致使VANET網(wǎng)絡(luò)拓?fù)渥兓l繁.僅考慮車輛間的距離，可能會導(dǎo)致車輛間鏈路生存時間短，網(wǎng)絡(luò)拓?fù)渥兓l繁，以致影響VANET網(wǎng)絡(luò)的通信性能.而車輛節(jié)點的移動性主要是由車輛節(jié)點的速度及位置來表征的，故本文以車輛節(jié)點的相對速度及位置，建模了車輛節(jié)點間的加權(quán)距離Dik：

式中：xik= ||xi-，vik=|vi-v，xi、vi為第i個車輛節(jié)點的位置和速度，、為第k個簇的質(zhì)心的位置和速度，α為相對速度的權(quán)重.

3.4 最優(yōu)位置更新

以加權(quán)距離作為自適應(yīng)KHM成簇算法的距離度量，該算法的目標(biāo)函數(shù)為為了得到質(zhì)心的一次迭代后更新的位置，最小化目標(biāo)函數(shù)，通過對目標(biāo)函數(shù) f求偏導(dǎo)［7］，并令，可得第k個質(zhì)心一次迭代后更新的位置.

3.5 算法流程

本節(jié)詳細(xì)描述了提出的自適應(yīng)KHM成簇算法流程，與傳統(tǒng)KHM成簇算法不同，所提的自適應(yīng)KHM成簇算法會由所估計出的初始成簇數(shù)目開始，對成簇數(shù)目進(jìn)行自動迭代.所提算法首先根據(jù)所有車輛節(jié)點的可用帶寬信息，建立候選簇頭車輛集合S，該集合中所有車輛都有一定可用帶寬資源.其次，由式（3）令成簇數(shù)目 K=Kini，通過最小化自適應(yīng)KHM成簇算法目標(biāo)函數(shù)，得到每輪迭代的簇頭車輛更新后的最優(yōu)位置，當(dāng)簇頭車輛節(jié)點集合中所有簇頭車輛的的位置均不再變化時，停止迭代，得到每個簇的簇頭車輛節(jié)點的最優(yōu)位置.最后，將簇頭車輛節(jié)點通信半徑范圍內(nèi)的車輛節(jié)點聲明為該簇的簇成員車輛，并判斷所有車輛是否都已成簇，若所有車輛都已加入簇，則算法終止，否則，K=K+1，重復(fù)執(zhí)行上述步驟.自適應(yīng)K-Harmonic Means成簇算法的詳細(xì)描述如下.

//車輛節(jié)點數(shù)為N，候選簇頭集合為S，初始成簇數(shù)目K=Kini，且K個質(zhì)心為均勻分布.

1.fori=1toNdo

2.if（ ?Bi≥ Bth） then

3. 第i個車輛加入候選簇頭集合S

4.end if

5.end for

6.repeat

7.fori=1toNdo

8.將第i個車輛歸屬到離其最近的質(zhì)心ck

9.end for

10.fork=1toKdo

11. fori=1toNdo

12. 更新簇質(zhì)心ck位置

13. end for

14.end for

15.until所有質(zhì)心的位置不再變化

16.fork=1toKdo

18.end for

19.i（f所有車輛均已加入簇）then

2. 算法終止

21.else

22. K=K+1，goto 6

23.end if

4 仿真分析

為驗證所提算法的性能，仿真實現(xiàn)了所提出的自適應(yīng)KHM成簇算法，并與傳統(tǒng)KHM成簇算法進(jìn)行比較.仿真場景為矩形道路模型，其它相關(guān)參數(shù)如表1所示.

圖2和圖3分別為在矩形道路場景下，車輛數(shù)為400時，傳統(tǒng)KHM成簇算法和所提出的自適應(yīng)KHM成簇算法的成簇場景.對于這兩種成簇算法，由式（3），可計算出最初的成簇數(shù)目Kini=8.同樣地，在圖2中，傳統(tǒng)KHM成簇算法不能實現(xiàn)對成簇數(shù)目的更新，所成簇數(shù)目為8，并且存在簇成員車輛在簇頭車輛的通信半徑范圍以外，導(dǎo)致簇頭車輛節(jié)點不能與簇成員車輛節(jié)點進(jìn)行直接通信，將會嚴(yán)重影響VANET網(wǎng)絡(luò)的通信性能.而在圖3中，自適應(yīng)KHM成簇算法能實現(xiàn)對所成簇數(shù)目的自適應(yīng)更新，所成簇數(shù)目最終為10，并且所有的簇成員車輛均在其簇頭車輛的通信半徑范圍內(nèi)，能保證VANET網(wǎng)絡(luò)的通信性能.

表1 仿真參數(shù)設(shè)置

圖2 傳統(tǒng)KHM成簇算法成簇場景

圖3 自適應(yīng)KHM成簇算法成簇場景

圖4顯示了在矩形道路場景下，數(shù)據(jù)包成功投遞率與車輛速度的變化關(guān)系.通過圖4可以看出本文所提出的自適應(yīng)KHM成簇算法的數(shù)據(jù)包成功投遞率高于傳統(tǒng)KHM成簇算法（成簇數(shù)目分別為8、9、10、11），數(shù)據(jù)包成功投遞率提高了約10%.這是由于本文所提出自適應(yīng)KHM成簇算法在選擇簇頭車輛節(jié)點時，建立了候選簇頭集合，保證了所選擇的簇頭車輛有足夠的帶寬為其簇成員車輛進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，并且通過建模車輛的加權(quán)距離，使所成的簇較為穩(wěn)定.從圖4中還可以看出，隨著車輛速度的增加，兩種算法的數(shù)據(jù)包成功投遞率呈下降趨勢.

圖4 數(shù)據(jù)包成功投遞率與車輛速度的關(guān)系

圖5顯示了在矩形道路場景下，VANET網(wǎng)絡(luò)的平均傳輸時延隨著車輛速度的變化關(guān)系，從圖中可以看出本文所提出自適應(yīng)KHM成簇算法較傳統(tǒng)KHM成簇算法，平均傳輸時延縮短了30ms.這是由于在選擇簇頭車輛節(jié)點時，本文所提出的自適應(yīng)KHM成簇算法所選擇出的簇頭車輛具有足夠的帶寬資源為其簇成員車輛進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā).從圖5中也可以看出，隨著車輛速度的增加，兩種算法的平均傳輸時延基本保持不變.

圖5 平均傳輸時延與車輛速度的關(guān)系

圖6為矩形道路場景下，吞吐量隨著車輛速度的變化關(guān)系.從圖6中可以看出本文所提出的自適應(yīng)KHM成簇算法較傳統(tǒng)KHM成簇算法，吞吐量較高.主要原因是本文所提出的自適應(yīng)KHM成簇算法所形成的簇能實現(xiàn)對該區(qū)域內(nèi)的所有車輛實現(xiàn)100%覆蓋（比較圖2與圖3），而且所選擇出的簇頭車輛具有較大的帶寬資源.

圖6 吞吐量與車輛速度的關(guān)系

5 結(jié)論

針對傳統(tǒng)KHM成簇算法應(yīng)用于VANET成簇時存在的缺陷，本文提出了一種自適應(yīng)VANET場景的自適應(yīng)KHM成簇算法，通過對所提出適用于VANET的自適應(yīng)KHM成簇算法進(jìn)行仿真實現(xiàn)及性能評估，并和傳統(tǒng)KHM成簇算法進(jìn)行對比.仿真結(jié)果表明，本文所提出的成簇算法能實現(xiàn)對車輛節(jié)點的完全覆蓋，且在數(shù)據(jù)包投遞率、平均傳輸時延及吞吐量等指標(biāo)上性能更優(yōu).