一種適用于VANET場景的自適應KHM成簇算法

葛先雷，章功干，權循忠，高 強

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

由于VANET具有車輛節點移動速度快，網絡拓撲的快速變化等傳統MANET網絡所不具有的特性，針對傳統KHM成簇算法應用于VANET成簇時存在的缺陷，如無法確定最終成簇數目，所成簇無法完全覆蓋所有車輛，以致嚴重影響VANET性能，本文提出了一種適用于VANET場景的自適應KHM成簇算法，相對于傳統KHM成簇算法，所提算法有以下改進.

為保證所選擇出的簇頭車輛具有足夠可用資源為其簇成員車輛進行數據轉發，根據每個車輛的可用帶寬建立了候選簇頭集合.

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

考慮到VANET的高動態性，根據車輛的移動性（主要包括車輛節點的相對速度及位置）建模了加權距離，作為該算法的距離度量.

1 VANET成簇的內涵及通信方式

VANET成簇是指將位置鄰近的車輛節點通過一些規則，形成一個臨時的移動自組織網絡，為周圍的車輛提供穩定可靠的無線接入服務.典型的VANET網絡成簇場景如圖1所示.在每個簇內，選擇一個車輛作為簇頭車輛節點，該簇頭車輛為簇間的車輛提供數據轉發，并對本簇內的簇成員車輛進行統一管理.

圖1 VANET網絡成簇場景

基于成簇的網絡拓撲為分層網絡結構，為了實現車輛節點的因特網接入服務和車輛間的通信，支持簇內通信和簇間通信兩種通信方式.

1.1 簇內通信

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

1.2 簇間通信

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

相對于其他傳統路由算法，基于成簇的路由算法具有以下優點.

在VANET網絡中，成簇算法能有效地適應車輛密度及車輛的數量變化很大的場景，具有很好的可擴展性.

在成簇時，選擇相對較“閑”的車輛作為簇頭車輛，所選擇出的簇頭車輛為該簇內的簇成員車輛進行數據轉發和統一管理，減少VANET網絡中的冗余信令開銷，以達到提高資源利用效率、提升網絡性能，并實現VANET網絡的負載均衡的目的.

由于車輛的高速移動，導致VANET網絡拓撲頻繁變化，成簇可延長簇的生存時間，使VANET網絡相對穩定，從而保證VANET網絡性能的穩定性和持續性.

簇外的遠距離的車輛沒有必要知道簇內具體細節，因為簇狀態的概括性信息已經足夠讓遠處的車輛做出控制決定.

2 K-Harmonic Means成簇原理

KHM成簇算法［4］已經廣泛用于數據挖掘、統計分析、數據壓縮等領域，是一種基于質心迭代的成簇算法，通過不斷優化K個質心的位置，最終得到質心最優位置.KHM成簇算法執行步驟如下.

步驟1：確定所需要成簇數目K，且這K個簇質心的初始位置是隨機分布的.

步驟2：定義KHM成簇算法目標函數：

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

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

步驟4：當簇的K個質心的位置C={c1,c2,...cK}不再變化時，算法終止并得出所成簇的質心的最優位置.否則跳轉到步驟2繼續執行，直至算法結束.

3 自適應KHM成簇算法

3.1 候選簇頭集合建立

簇頭車輛為簇成員車輛的中繼車輛進行數據轉發，并實現對簇成員車輛的統一管理.在為簇成員車輛進行數據包轉發時，簇頭車輛會消耗一定的資源.由于車輛節點的傳輸帶寬在業務傳輸性能上起決定的作用，具有較大可用帶寬的車輛作為簇頭車輛能為該簇成員車輛提供更好的性能.

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

3.2 初始成簇數目估計

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

式中：L為該區域路段長度，R為車輛節點通信半徑，N為該區域所有車輛數目，Nmax為每個簇內所允許的最大簇成員車輛個數，為了降低所提出的自適應KHM算法的復雜度，建模Kini個初始簇質心的位置分布為均勻分布.

3.3 加權距離建模

傳統KHM成簇算法的距離度量有歐氏距離、閔可夫斯基距離［6］或曼哈頓距離.但是由于車輛節點的移動速度快，致使VANET網絡拓撲變化頻繁.僅考慮車輛間的距離，可能會導致車輛間鏈路生存時間短，網絡拓撲變化頻繁，以致影響VANET網絡的通信性能.而車輛節點的移動性主要是由車輛節點的速度及位置來表征的，故本文以車輛節點的相對速度及位置，建模了車輛節點間的加權距離Dik：

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

3.4 最優位置更新

以加權距離作為自適應KHM成簇算法的距離度量，該算法的目標函數為為了得到質心的一次迭代后更新的位置，最小化目標函數，通過對目標函數 f求偏導［7］，并令，可得第k個質心一次迭代后更新的位置.

3.5 算法流程

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

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

1.fori=1toNdo

2.if（ ?Bi≥ Bth） then

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

4.end if

5.end for

6.repeat

7.fori=1toNdo

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

9.end for

10.fork=1toKdo

11. fori=1toNdo

12. 更新簇質心ck位置

13. end for

14.end for

15.until所有質心的位置不再變化

16.fork=1toKdo

18.end for

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

2. 算法終止

21.else

22. K=K+1，goto 6

23.end if

4 仿真分析

為驗證所提算法的性能，仿真實現了所提出的自適應KHM成簇算法，并與傳統KHM成簇算法進行比較.仿真場景為矩形道路模型，其它相關參數如表1所示.

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

表1 仿真參數設置

圖2 傳統KHM成簇算法成簇場景

圖3 自適應KHM成簇算法成簇場景

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

圖4 數據包成功投遞率與車輛速度的關系

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

圖5 平均傳輸時延與車輛速度的關系

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

圖6 吞吐量與車輛速度的關系

5 結論

針對傳統KHM成簇算法應用于VANET成簇時存在的缺陷，本文提出了一種自適應VANET場景的自適應KHM成簇算法，通過對所提出適用于VANET的自適應KHM成簇算法進行仿真實現及性能評估，并和傳統KHM成簇算法進行對比.仿真結果表明，本文所提出的成簇算法能實現對車輛節點的完全覆蓋，且在數據包投遞率、平均傳輸時延及吞吐量等指標上性能更優.