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

許力文，喬麗娟，陳 杰

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

1 概 述

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

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

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

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

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

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

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

2 相關(guān)工作

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

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

3 系統(tǒng)模型

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

3.1 簇的形成

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

圖1 分簇形成及車輛節(jié)點分布結(jié)構(gòu)

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

E-αn

(1)

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

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

程序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]表示監(jiān)測區(qū)域內(nèi)任意車輛節(jié)點i到獨立分割區(qū)C1的距離，同樣distance2[i]和distance3[i]分別表示到C2和C3的距離。

3.2 簇頭的選擇

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

程序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的集中式車輛。

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

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

CSi=Aggregate(VAR(Vi)+ADVi)

(2)

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

4 性能分析與仿真

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

4.1 環(huán)境設置

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

表1 MKCR和COIN對比的參數(shù)值

4.2 簇頭開銷

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

(3)

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

4.3 適應的車輛速度置信區(qū)間

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

4.4 簇頭的穩(wěn)定性

在動態(tài)的VANET中，VH的穩(wěn)定性更為突出。而分簇優(yōu)化聚群的目的是通過構(gòu)造一致的車輛組來延長VH的壽命，本節(jié)比較了MKCR和COIN的穩(wěn)定性。該仿真是在MKCR和COIN相同車輛數(shù)量和規(guī)格下進行的。

圖2 車輛速度的置信區(qū)間

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

表2 MKCR的車輛和車頭選擇

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

5 結(jié)束語

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

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

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

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

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

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

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

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

[7] 余秀雅,劉東平,楊 軍.基于K-means++的無線傳感網(wǎng)分簇算法研究[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] 胡升澤,包衛(wèi)東,王博等.無線傳感器網(wǎng)絡基于多元簇首的分簇數(shù)據(jù)收集算法[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] 吳 怡,沈連豐,邵震洪,等.基于探測信息的車輛自組織網(wǎng)絡功率控制算法[J].東南大學學報:自然科學版,2011,41(4):659-664.