基于車輛移動相似性的VANETs 簇群算法*

袁小艷 許曉紅

（四川文理學院智能制造學院 達州 635000）

1 引言

車聯網（Vehicular Ad Hoc Networks，VANETs）已成為智能交通系統（Intelligent Transportation System，ITS）的重要組成部分［1~3］。通過VANETs 可實現多類應用，如車間信息傳輸、協作駕駛、緊急消息傳輸等。然而，這些應用的實現是建立于良好的通信網絡。目前，主要存在兩類通信協議標準：專用的短距離通信（Dedicated Short-range Communication，DSRC）［4］和C-V2X［5］。DSRC 只能實現短距離通信，相比下，C-V2X 通信通過借助于4G 和5G 無線通信網絡，能夠實現大范圍的通信覆蓋和高速率。

然而，車輛的高速移動以及障礙物導致網絡呈間歇性連通，增加了網絡接入的不穩定性，容易丟失數據包。簇群技術是提高數據傳輸成功率的有效策略。將道路上的車輛劃分為簇，每個簇產生一個簇頭（Cluster Header，CH），簇內其他車輛稱為本簇的簇成員（Cluster Members，CM）。CH 收集本簇內的CMs的車輛數據。

由于車輛的高速移動，構建穩定的簇群是一項具有挑戰性的任務。文獻［6］利用5G 的基站（gNB）形成簇，并利用多項指標構建CH。但是由于擁塞以及非視距環境，基站不能與多個車輛通信。文獻［7］提出基于車間距離因子的構簇算法。但是，由于車輛的高速移動，車間距離可能一直在變化，這增加了構建簇的頻率。文獻［8］提出基于Q-學習的構建簇算法，進而減少gNB 的開銷。但是該算法在每個簇內形成多個CHs，這增加了算法本身的復雜性。同時，在進行Q-學習時需要訓練數據，這增加處理時延。文獻［9］提出基于飛蛾撲火算法（Moth-Flame Optimization，MFO）為車輛構建虛擬的網格。但是該算法旨在優化簇數，沒有討論網絡的性能。

綜上所述，目前缺乏從網絡連通性角度，構建自適應的簇群技術。為此，提出基于車輛移動相似性的簇群（Compatibility of Vehicle Mobility-based Clustering，CVMC）算法。CVMC算法先通過基站接收車輛的信號強度決策一個車輛作為簇頭，再依據車輛離基站的距離、車輛間相對速度以及車輛間重疊的路段計算車輛間的移動相似性，再利用車輛間的移動相似性形成簇。仿真結果表明，提出的CVMC算法有效地提升吞吐量。

2 CVMC算法

2.1 網絡模型

車聯網主要由車輛、gNBs 構建，如圖1 所示。每輛車上安裝一個OBU［10］。每個OBU 配備了雙重收 發 器：1）基 于802.11p 的DSRC 或 者 是3GPP C-V2X；2）4G 或者5G。車輛通過OBU 與其他車輛、gNBs進行通信。

圖1 系統模型

每輛車中的OBU 具有防攻擊設備（Tamper Proof Device，TPD），存儲相關的數據。在VANETs中，車輛通過交互Beacon 包與其鄰居節點交互信息，進而獲取鄰居車輛的信息。

此外，路邊單位（Road-Side Units，RSUs）或者是5G 的eNBs 作為基站gNBs，它們能夠傳輸蜂窩信號，并且它們之間通過高速的X2鏈路連接。

假定系統中有n輛車，它們構成車輛集V={?1，?2，…，?n} 。令Dij表示車輛?i與車輛?j間的歐式距離：

式中：(xi，yi)、(xj，yj)分別表示車輛?i、?j的位置坐標。

2.2 車輛間的相似性

為了計算車輛間的相似性，對車輛連通目的節點道路進行分段劃分。令Sgi表示車輛?i所在路段的分段，假定分割成q個等間隔的路段。且如圖2 所示，車輛?k離其目的地的道路被劃分為3 段（q=3），即Sgk=

圖2 車輛路段劃分示例

將每輛車通往目的地的路段進行分段后，相鄰車的路段存在重疊。為此，將整個路段進行編號sg_id_*，其中“*”表示編號。如圖2 所示，對整個路 段 進 行 從A、B、C 至G 的 編 號，即{sg_id_A，sg_id_B，sg_id_C，sg_id_D，sg_id_E} 。

接下來，計算兩輛車在通往目的地的重疊路段，用Ni，j=Sgi∩Sgj表示車輛?i與車輛?j的重疊路段集。例如，如圖2 所示，車輛?j與車輛?k間的重 疊 路 段 為Nk，j=Sgk∩Sgj={sg_id_D，sg_id_E，sg_id_F}。

如果兩車輛間的重疊路段數超過預定閾值Sgth，則認為它們間的移動存在相似性。為此，引入布爾變量Fij。如果車輛?i與車輛?j間重疊路段數大于Sgth，則Fij=1，否則為零：

接下來，計算兩輛車間的移動相似性。令SMi，j表示車輛?i與車輛?j間的移動相似性，其定義如式（3）所示：

式中：0 ＜Dij＜R限定兩輛車在彼此的通信范圍內；Δνij表示車輛?i與車輛?j間相對速度，其定義如式（4）所示。

從式（3）的定義可知，車輛間距離越小、相對速度越小，它們間的相似性越大。

2.3 簇頭及簇形成

每個車輛周期Beacon 包，向gNB 傳輸報告它自己的位置以及速度等信息。gNB 依據接收的Beacon包消息的信號強度，選擇具有最大信號強度（Received Signal Strength，RSS）的車輛作為簇頭：

式中：RSS?1表示車輛?1的信號強度值RSS。

一旦選舉了簇頭后，簇頭就向鄰居節點傳輸通告消息Mes_CH。其他節點接收Mes_CH 消息，計算與簇頭的間移動相似值。如果與簇頭間的移動相似性低于閾值SMth，則車輛就直接與gNB 通信。若大于閾值SMth，車輛就從中選擇具有最大移動相似性車輛作為自己簇頭，并向該簇頭發送確認消息Mes_ACK，如算法1所示。

算法1：簇形成過程

if 如果車輛不是簇頭

接收到Mes_CH 后，車輛就依據式（3）計算與簇頭的移動相似性

ifSMi，j小于閾值SMththen

車輛就直接與gNB直接通信

else

車輛就從中選擇具有最大移動相似的簇頭作為自己的簇頭，并向其傳輸Mes_ACK。

end if

else

傳輸消息Mes_CH

接收消息Mes_ACK

end if

圖3 給出基于車輛移動相似性的簇群模型。依據車輛位置以及它們移動速度的相近性構建簇。圖中灰色實線范圍表示一個簇群，而不是深色實線范圍。從理論上講，考慮了車輛移動速度的相近性所構建簇群穩定性更好，由于車輛以相近的速度移動以及位置相近，它們能夠保持更好的連通性，鏈路持續時間更長。

圖3 基于車輛移動相似性的簇群示例

3 基于簇的接入信道性能分析

由于蜂窩網絡采用正交頻分多址接入技術給C-V2X 用戶分配資源，需采用隨機接入信道方式進行信道競爭。因此，gNBs 以隨機方式給用戶分配資源。

假定總共有k個車輛同時向gNBs請求M 個資源。若沒有簇群技術，車輛能夠獲取資源的概率為

采用簇群技術可以減少接入上行鏈路的資源的車輛數。假定 ||Ci表示簇群的平均車輛數，則車輛接入資源的概率提升為

4 性能分析

4.1 仿真環境

在Windows 7 操作系統、8GB 內存，core i7 CPU的PC 上進行實驗仿真。采用SUMO 軟件［11］建立城市車輛移動軌跡數據，仿真區域為300 m×1500 m，車輛數從50~500變化。

在網絡層選用按需矢量距離（Ad-Hoc On-Demand Distance Vector，AODV）［12］路由傳輸數據，并選用LENA mmWave 模塊，并考慮Friss 傳播模型［13~14］。道路參數：40 個交叉路口，最大車道數為3，每個車道寬不超過50m，如圖4所示。

圖4 SUMO道路拓撲

每輛車采用20dB 的傳輸功率，傳輸范圍為145m，具體的仿真參數如表1所示。

表1 仿真參數

4.2 閾值Sgth 對數據包傳遞率的影響

考慮兩類情況：Sgth=5 和Sgth=2 。Sgth越大，簇的穩定性以及連通性越好，而Sgth越小構建簇的頻率越高。圖5（a）顯示了車輛數和Sgth對數據包傳遞率的影響。從圖可知，CVMC 算法的數據包傳遞率在80%至91%。此外，車輛數的增加對數據包傳遞率的影響并不大。

但是，車輛速度對數據包較大影響，如圖（b）所示。當車輛隨機速度在50m/s~60m/s，CVMC 算法的數據包傳遞率達到91%。然而，車速的增加降低了數據包傳遞率。此外，從圖5 可知，Sgth的增加提升了數據包傳遞率，這符合預期。

圖5 Sgth 對數據包傳遞率的影響

4.3 性能對比分析

選擇文獻［8］提出的兩層簇算法（Two-Level Cluster Algorithm，TLCA）和文獻［6］提出的多跳移動區域算法（Multi-hop Moving Zone Clustering，MMZC）作為參照。分析車輛數和車速對CVMC 算法、TLCA 算法和MMZC 算法的吞吐量影響，如圖6、7所示。

圖6 車輛數對吞吐量的影響

如圖6 所示，當車輛數為100 時，CVMC 算法的吞吐量達到11 Mbps，而TLCA 算法的吞吐量達到約12 Mbps。但是當車輛數增加至200 時，TLCA 算法的吞吐量迅速下降。當車輛數增加至500 時，TLCA 算法的吞吐量下降至4 Mbps，而CVMC 算法的吞吐量仍達到8 Mbps。幸運的是，CVMC 算法的吞吐量隨車輛數的增加保持較穩定的性能。

相比于CVMC 算法和TLCA 算法，MMZC 算法的吞吐量最低。在車輛數為100 時，MMZC 算法的吞吐量只有8 Mbps。而當車輛數增加至500，MMZC算法的吞吐量只有1 Mbps。

圖7 給出車速對吞吐量的變化情況。從圖可知，車速的增加降低，使吞吐量呈下降趨勢。原因在于：車速越快，車間通信鏈路的持續時間越短，這不利于數據包的傳輸。此外，相比于TLCA 算法和MMZC 算法，CVMC 算法的吞吐量仍保持較高的水平。這歸功于：CVMC 算法利用車間移動相似性構建簇，提高了簇的穩定性。

圖7 車速對吞吐量的變化情況

5 結語

本文針對車聯網中的構簇算法，提出車輛移動相似性的簇群CVMC 算法。CVMC 算法充分利用車輛的移動信息，通過計算車輛在道路中移動行為，構建簇，提高簇的穩定性。仿真結果表明，相比于MMZC 和TLCA 算法，提出的CVMC 算法的吞吐量提高了近2Mbps~4Mbps。

本文考慮的仿真場景較為簡單。后期，將考慮更為復雜場景，使提出的CVMC算法能夠應用于真實場景，這將是后期的研究工作。