基于VANETs修改的K-means分簇路由算法

許力文，喬麗娟，陳 杰

(1.海南熱帶海洋學院 海洋信息工程學院，海南 三亞 572022；2.武漢大學 計算機學院，湖北 武漢 430072)

1 概 述

隨著機動車保有量、路網結構、城市規模的不斷增長與擴張，交通擁堵、交通安全和節能減排引起了政府、學術和工業界的高度關注[1]。車輛自組織網絡(vehicle ad-hoc networks,VANETs)是一種提高交通安全系數、提升乘車人員舒適度的網絡系統，是智能交通系統(intelligent transportation system,ITS)的重要組成部分之一[2]。

美國聯邦通信委員會(federal communications commission,FCC)在1999年10月就為專用短距離通信(dedicated short range communication,DSRC)服務在5.9 GHz頻率處為VANET分配了寬75 MHz的專用通信頻段，實現車與車(vehicle to vehicle,V2V)、車與路邊設施(vehicle to infrastructure,V2I)間的通信會話，并訂制了VANET基于IEEE802.11p協議的規定和標準[3-4]。

VANETs其信息可靠傳輸性是通信會話的重要保障。文獻[5]通過動態地更改相鄰車輛之間的傳輸速率，使得數據更易于被接收和聚合；提出的基于DSRC控制信道的分布式跨層設計方法提高了VANETs中安全信息的快速傳輸可靠性；采用了基于車輛探測消息的功率控制算法，周期性地給車輛節點發送探測信息，實時對整個網絡中的車輛數目和連通性狀態進行分析，自適地更改發射功率從而降低網絡擁塞狀況。

這些方法很好地實現了V2V和V2I間的通信會話，其優點為既定拓撲、持續能量、高效計算和車輛定位等[6]。由于車輛高速移動的特征，造成了動態網絡拓撲和多徑衰落，因此控制信道帶寬和通信距離存在受限的問題，導致了V2V通信鏈路隨機中斷，使得車間通信會話不穩定和不可靠[4]。主要存在的不足是：車輛簇頭產生時對節點的狀態考慮不夠，使得能量極少的節點擔任車輛簇頭，導致節點車輛能量快速耗盡而提前死亡，縮短了簇群生存時間；存在極大簇或極小簇不均勻的較大區別；存在簇頭在監測區域聚集分布不均勻的情況。

分簇形成的集群數過多則計算復雜度增大，集群體過大則簇間過于變化頻繁簇頭能耗過多易于更換。因此設計出優化的分簇路由算法至關重要。K-means是一種常見的均值聚類方法，優點是快速、簡單，對大數據有較高效率，時間復雜度近于線性[7]，為此提出基于K-menas均值算法對車輛節點執行分簇形成，從而有效提高VANETs車輛節點的連通性和穩定性。

文中提出一種基于VANETs修改的K-means分簇路由協議(modified K-means clustering routing，MKCR)。協議設計分三步完成。第一步是車流形成簇群，即采用修改的K-means算法將有效傳輸范圍內的車輛分簇，形成三個分簇區域；第二步是采用Floyd-Warshall算法來獲得有關獨自分簇區域內每個車輛節點的平均速度、位置和方向等信息；第三步是根據指定的集中位置和速度方差兩個參數選擇車分簇的簇頭車輛(VH)。

在該方案中，根據車輛速度的截斷正態分布，設置了車輛的速度置信區間，每輛車節點的速度在置信區間內被指定為分簇。具有中心位置和VAR的小聚集的車輛節點將選為CH(cluster head)。MKCR不僅考慮了簇的數量、簇的密度和簇的結構，構造出一致的車輛節點集群形狀，同時還考慮簇頭的壽命時間，能長時間維持簇的狀態，從而增加車輛之間的互連的壽命，并以較少的迭代重新選擇CH。

2 相關工作

近年來，為了解決VANETs應用問題中通信連接的穩定性，研究人員提出了很多解決方案。廣播算法的泛洪機制具有簡單、快速和覆蓋率廣的特點，因此應用最為廣泛，但卻會引起惡劣的廣播風暴，造成廣播信息過大的冗余、過多能耗和惡劣的資源競爭及沖突。由Tzay-Farn Shih等[8]提出的核心定位輔助集群路由協議(CLACR)，將通信區域劃分為正方形簇，然后通過使用簇頭算法為每個正方形選擇簇頭，減少了廣播風暴和路由開銷，但CLACR不適合于稀疏或復雜的VANETs場景。An Huiyao等[9]提出基于集群的多路徑動態源路由(cluster-based multipath dynamic source routing in MANET，CMDSR)是一種三級層次結構方案屬于基于鄰居的聚類集群，其中每個級別具有自己的簇頭并且其余節點是一跳遠距離的鄰居，基于鄰居的協議是混合路由協議(HRP)[10]；Bilal M等[11]提出FMHR算法，是基于貪婪算法把最后下一跳的車輛節點做為簇頭，提高了鏈路的相對穩定性，但同時考慮了車輛節點的運動速度和方向，算法增加了計算負載和額外開銷。Cross-CBRP[12]算法在物理層使用功率信號信息進行路由以增加群集的壽命，有效提高網絡吞吐量。胡升澤等[13]提出的CMCH算法能很好地降低單個簇頭的負擔，周期性地選擇簇頭，但由于節點移動頻繁而不斷更換簇頭，增加了網絡開銷。Saleet H等[14]提出的IGRP協議，Naumov V等[15]提的CAR都是基于錨點的路由算法，通過路邊錨節點進行數據分組轉發，能夠改善稀疏場景中由于網絡分離導致數據不可達的問題，但對錨節點依賴性強，在區域中若有錨節點損壞或阻塞，則將導致整個網絡癱瘓。COIN算法適應車輛間距的振蕩性質[16]，COIN的主要目的是提高簇的穩定性。

上述方法是依據簇進行節點管理和數據轉發，較好地完成分簇并選擇出簇頭，降低路由發現開銷和廣播風暴，增加網絡有效吞吐量，延長網絡生存期，提高網絡的穩定性。在VANETs基于分簇的路由算法中，簇劃分是研究方向之一，本節通過模擬測試并對比COIN算法，分析和討論在開放式車輛間通信網絡中MKCR算法的優越性及分簇車頭(VH)節點的穩定性。

3 系統模型

VANET的車輛節點具有高速移動的動態性質，所以設計出一款最優迭代算法的路由機制對研究人員提出了更高的要求。結合十字路口場景，文中提出了一種MKCR協議，可以有效地擴展車輛之間的通信會話。在十字路口場景中，所有車輛以非均勻速度行駛，由于交通管制要求在一定速度范圍內行駛，車輛可能在道路上造成持續的交通模式。設計集中式路由協議的要求是流量模式的一致性，文中為一致的分簇定義了兩個參數，即車輛速度的截斷正態分布和簇內車輛的位置。

3.1 簇的形成

簇的形成通過修改的K-mean算法進行，K-means的主要思想是識別用于車輛節點分類的質心或分割點或聚類點(cluster points,CP)。文中根據DSRC的傳輸范圍有三個分割區域，每個分割區域將定義一個獨立的分簇。在指定范圍內，三個分割點C1、C2和C3被認為是三個車輛群的中心點。C1和C3是范圍的最遠分割點，C2居于C1和C3的中間，如圖1所示。

圖1 分簇形成及車輛節點分布結構

區域中的車輛節點在分類成簇之前，首先設定了車輛速度的置信區間。截斷期間的正態分布模型N(μ,σ)用來定義速度建模分布，其中μ是車輛速度的平均值，σ是標準偏差。通過截斷分布模型定義了平均值周圍的速度的置信區間，如式(1)：

E-αn

(1)

其中，E表示車輛速度的期望值；αn表示速度間隔的百分比置信度。只要車輛節點的速度在式(1)區間內，此車輛均是分簇的考慮對象。

程序1代碼描述了用修改的K-means方法形成三個分簇，即將道路劃分為三個獨立區域，其中每個區域形成圖1所示的簇結構。

程序1：Modified K-means clustering。

Void Cluster_Formation(N)

Begin

for i<----0 to N do

if distance1[i]

then

Cluster1[C1] <----i

C1++

else if distance2[i]

distance2[i]

then

Cluster2[C2]

C2++

else

Cluster3[C3]

C3++

End

其中，distance1[i]表示監測區域內任意車輛節點i到獨立分割區C1的距離，同樣distance2[i]和distance3[i]分別表示到C2和C3的距離。

3.2 簇頭的選擇

簇頭負責本簇內部的統一管理，簇頭的選擇最為關鍵。本簇內簇成員僅上傳本地消息給簇頭，并接收簇頭的廣播消息。簇頭直接連接兩個相鄰簇或路邊設備，實現了簇頭的消息中繼。在VANET中簇的穩定性定義為簇持續生存的時間，由于VANET的隨機性質，在簇內每個車輛彼此交換HELLO消息，消息中包括速度、位置和方向等信息。設置簇頭選擇的兩個參數，即簇群內的集中位置和速度方差。

程序2：Algorithm for centralized vehicle。

void Centralize_Vehicle()

Begin

for i<----0 to C1do

for j<----0 to C1do

Distance[i][j]sqrt(pow((final_xcor1[i]-final_xcor1[j]),2)+pow((final_xcor1[i]-final_xcor1[j]),2))

count<----0

counter<----0

sum<----0.0

for i<----0 to C1do

for j<----0 to C1do

sum<----sum+Distance[i][j]

counter++

Center_Set[count] sum/counter

Center<----Center_Set[0]

for I<----0 to C1do

if Center>Center_Set[i]

then

Center<----Center_Set[i]

Cluster_Center_Vehicle<----i

End

以上算法描述了車輛集中選擇，如圖1所示，其中白色車輛分別表示簇C1、C2和C3的集中式車輛。

接著，使用動態規劃算法中的Floyd-Warshall算法來選擇集中式車輛。其計算所有車輛的最短距離，任兩車間距離為歐幾里德距離。程序2中的偽代碼表示集中車輛選擇C1簇群。

最后階段設定兩個參數來計算每個車輛節點的累積分數(cumulative score,CS)，這兩個參數是圍繞均值μ的集中位置和速度方差(Var(Vi))。CS為兩個參數的累積值，即:

CSi=Aggregate(VAR(Vi)+ADVi)

(2)

其中，Var(Vi)是車輛Vi速度的方差平均值，其與群集中的VH的壽命成反比。在VH選擇標準中給VAR(Vi)分配60%的權重。ADV(平均距離值)是每個單獨的車輛與集群內的其他車輛的平均距離。每個節點的ADV由集中式算法計算。在MKCR中，ADV的權重是40%。具有最低CS的任何節點將被選擇為CH的候選。

4 性能分析與仿真

本節通過模擬測試并對比COIN算法，分析和討論了在開放式車輛間通信網絡中MKCR算法的優越性及分簇車頭(VH)節點的穩定性。

4.1 環境設置

模擬環境根據DSRC的規范進行設置。每個車輛的運動范圍設置為1 000 m。車輛的速度被認為是非均勻的，即為60～120 km/h。車輛密度從10～100輛不等[17]。表1為MKCR和COIN[16]做模擬測試比較時所用的參數設置值。

表1 MKCR和COIN對比的參數值

4.2 簇頭開銷

如在MKCR中，有三個固定的群集，其通過修改的K均值計算。根據文中提出的方法，聚類開銷(CO)的計算為：

(3)

其中，N和n分別是分簇的數量和每個簇群的車輛數量；CP是簇類分割點，并且在傳輸區域內有三個分割點。在模擬測試中，高速公路的端點和中點被指定為分割點；V是提名為分簇部分的車輛；Min函數找到CP和正常車輛之間的最小歐氏距離。

4.3 適應的車輛速度置信區間

簇的形成是每種分簇算法的初始步驟，簇成員的穩定性趨于一致的分簇。COIN協議隨機地將該車輛節點分成兩組，稱為正常車輛和簇頭。COIN的主要焦點是選擇適當的簇頭，而不是適當的簇成員。而在MKCR中，類的穩定性從簇形成的初始階段考慮。初始設置是定義車輛在高速公路上的速度的置信區間。定義95%的集群形成的置信區間。在圖2中，陰影區域顯示車輛速度的置信區間。根據定義的置信區間，只有中等車輛將成為集群的一部分，因此集群的整體一致性將增強。

4.4 簇頭的穩定性

在動態的VANET中，VH的穩定性更為突出。而分簇優化聚群的目的是通過構造一致的車輛組來延長VH的壽命，本節比較了MKCR和COIN的穩定性。該仿真是在MKCR和COIN相同車輛數量和規格下進行的。

圖2 車輛速度的置信區間

由式(2)表明，CS越小，VH的穩定性越大。一些用于模擬的樣品，以及MKCR車頭VH選擇的結果如表2所示。

表2 MKCR的車輛和車頭選擇

表2中，車輛V_ID 4由TCRP選擇為VH，因為其CS速率大于所有其他集群成員。然而，在COIN的情況下，具有V_ID 6的車輛將被選為簇頭，因為簇內的最小ADV。選擇COIN是最差的，因為V_ID 6與其他成員的速度差異相當大，并且簇頭的存在將是非常短的時間間隔。速度差在VH的選擇中非常重要。將保留高速的集中式車輛在集群中的時間非常短。距離不是測量穩定性的唯一標準，因為速度的高方差能快速地影響平均距離。

5 結束語

基于VANETs的車輛節點具有高速移動的動態性，導致車輛節點通信會話不穩定。文中提出的MKCR分簇路由算法是把車輛節點通過形成群集的形式，分簇的持續穩定性很好地控制和管理節點，達到消除消息泛洪的目的，減少不必要的路由開銷。其中，CH負責管理其中的分簇車輛節點，同時也負責簇間互連，穩定的VH可以增加簇形狀的持續壽命時間。首先采用修改的K-means算法形成分簇，然后利用Floyd-Warshall算法選擇分簇的集中和穩定的CH。CH基于它們的相鄰距離來選擇，最佳的CH具有集中式的位置并且具有較小的速度方差。

通過分析和模擬結果表明，MKCR路由協議能夠使群集形狀一致，避免在新一輪CH重新選擇，從而形成相當穩定的車輛節點群集，使網絡具有較好的穩定性，有效提高信息傳輸。

[1] 吳黎兵,杜 錦,聶 雷,等.無線傳感器網絡動態k值簇頭選擇方法[J].華中科技大學學報：自然科學版,2015,43(10):37-41.

[2] 唐 倫,王晨夢,陳前斌.車載自組織網絡中基于時分復用的異步多信道MAC協議[J].計算機學報,2015,38(3):673-684.

[3] 邱恭安,包志華,章國安,等.高穩定被動群集車聯網連通性研究[J].通信學報,2016,37(11):42-48.

[4] HARTENSTEIN H,LABERTEAUX K P.VANET:車載網技術及應用[M].孫得民,譯.北京:清華大學出版社,2013.

[5] 默罕莫德·默森,許凱凱,夏瑋瑋,等.荒漠場景應用的車聯網及其分簇路由算法[J].通信學報,2012,33(10):166-174.

[6] 程嘉朗,倪 巍,吳維剛,等.車載自組織網絡在智能交通中的應用研究綜述[J].計算機科學,2014,41(6A):1-10.

[7] 余秀雅,劉東平,楊 軍.基于K-means++的無線傳感網分簇算法研究[J].計算機應用研究,2017,34(1):181-185.

[8] SHIH T F,YEN H C.Core location-aided cluster-based routing protocol for mobile ad hoc networks[C]//Proceedings of the 10th WSEAS international conference on communications.Stevens Point,Wisconsin,USA:World Scientific and Engineering Academy and Society,2006:223-228.

[9] AN Huiyao,ZHONG Ling,LU Xicheng,et al.A cluster-based multipath dynamic source routing in MANET[C]//IEEE international conference on wireless and mobile computing,networking and communications..[s.l.]:IEEE,2005:369-376.

[10] AHN C W,RAMAKRISHNA R S,KANG C G.Efficient clustering-based routing protocol in mobile ad-hoc networks[C]//Vehicular technology conference.[s.l.]:[s.n.],2002.

[11] BILAL M,CHAN P M L,PILLAI P.A fastest multi-hop routing scheme for information dissemination in vehicular communication systems[C]//International conference on software telecommunications and computer networks.[s.l.]:IEEE,2010:35-41.

[12] DANA A,YADEGARI A M,HAJHOSSEINI M,et al.A robust cross-layer design of clustering- based routing protocol for MANET[C]//10th international conference on advanced communication technology.[s.l.]:[s.n.],2008:1055-1059.

[13] 胡升澤,包衛東,王博等.無線傳感器網絡基于多元簇首的分簇數據收集算法[J].電子與信息學報, 2014,36(2):403-408.

[14] SALEET H,LANGAR R,NAIK K.Intersection-based geographical routing protocol for VANETs:a proposal and analysis[J].IEEE Transactions on Vehicular Technology,2011,60(9):4560-4574.

[15] NAUMOV V, GROSS T R. Connectivity-aware routing (car) in vehicular ad-hoc networks[C]//IEEE international conference on computer communications.[s.l.]:[s.n.],2007:1919-1927.

[16] BLUM J,ESKANDRIAN A,HOFFMAN L.Mobility management in IVC networks[C]//IEEE intelligent vehicles symposium.[s.l.]:IEEE,2003:150-155.

[17] 吳 怡,沈連豐,邵震洪,等.基于探測信息的車輛自組織網絡功率控制算法[J].東南大學學報:自然科學版,2011,41(4):659-664.