一種車載自組織網絡連通性維護方法

曹 樂，胡曉輝，喬 鈺

（蘭州交通大學電子與信息工程學院，蘭州 730070）

0 概述

車載自組織網絡（Vehicular Ad Hoc Network，VANET）是在交通環境中車輛與車輛、車輛與固定接入點、車輛與基礎設施之間相互通信組成的開放式移動自組織網絡（Mobile Ad Hoc Network，MANET）［1］。VANET 通信包括車輛當前位置及移動速度信息、實時路況信息、車輛故障信息等［2］。VANET 利用MANET技術可以快速地建立一個臨時的車輛間無線通信網絡。車輛間無線通信主要是源車輛將自身的車輛信息以及行駛過程中收集到的道路交通信息發送給目標車輛，從而方便目標車輛的司機對接收到的交通信息和可能出現的安全問題做出及時反應［3］。如何尋找和維護從源車輛到目標車輛的路由以保證數據傳輸的實時性、完整性和有效性是VANET 路由協議研究的重點［4］。因此，設計一種基于分簇技術延長簇頭（Cluster Head，CH）節點生存周期，降低VANET 全局拓撲動態性的路由協議，是提高網絡穩定性的有效方式，對實現高效穩定的車輛間通信具有十分重要意義［5］。

文獻［6］結合基于位置路由和基于簇路由協議的特點，提出一種基于簇頭生存期的路由協議，簇頭的選取主要取決于車輛的當前速度和到預定向簇邊緣的距離，并未考慮簇內節點間的相對移動性。文獻［7］將聚類問題轉化為切割圖問題，設計了一種基于譜聚類和力導向算法的新方法，選擇鄰居數最多的節點作為簇頭，但在簇頭節點移動速度較快時，導致簇成員離開過于頻繁，從而影響網絡穩定性。文獻［8］提出一種基于軟件定義網絡（Software Defined Network，SDN）的社會感知分簇方法，基于車輛間距離、相對速度和車輛屬性選擇簇頭，但未考慮因競爭簇頭造成的時延對通信質量的影響。文獻［9］設計了一種基于移動區域的體系結構，提出一種基于移動對象建模和索引技術的新方法。該方法根據車輛的運動模式進行分簇，提升了消息傳遞率，但在復雜多變的VANET 環境中，當簇頭車輛的運動模式發生改變時，都需要進行重選簇頭，導致產生過多的開銷。文獻［10］提出一種基于簇的無監督VANET 演進圖（CVoEG）模型，選擇簇內具有最大的特征中心度分數作為簇頭節點。該模型在靜態或車輛拓撲結構變化較小的情況下表現不佳，更適合于具有高速變化和間距變化的情況。文獻［11］提出一種基于粒子群優化的分簇路由算法，根據節點的方向、速度和鄰居節點個數來確定簇頭，有效減少了端到端時延，但簇頭生存時間較短。文獻［12］提出一種基于多目標元啟發式的VANET 分簇算法，使用雙簇頭進行轉發，有效延長了簇的生存時間，但無法保證傳輸時延。

VANET 環境下接入網車輛的高速移動性使得車與車、車與基站之間的通信大多基于無線鏈路，節點在一段時間內頻繁地進入和離開其他節點的通信范圍，導致簇頭生存時間較短、傳輸時延較大、網絡穩定性不佳等問題，從而影響通信質量。本文依據最大化簇頭生存時間原則選取簇頭，將節點的相對移動度和相對速度作為節點穩定度的主要參考指標，選出每個簇內穩定度最佳的節點作為簇頭，負責簇間數據交換。同時結合雙簇頭設計思想選取輔助簇頭，有效避免因競爭簇頭帶來的時延差，從而保證VANET 消息傳輸的有效性和完整性。

1 雙簇頭的改進路由協議設計

由于道路上車輛速度及方向是不斷變化的，且車輛的速度及位置與車輛通信密切相關，因此同一簇內的車輛應當具有更相似的運動模式。簇的劃分主要采用以下2 種方式：1）適合具有路標或車輛以中等速度行駛的預分割道路，物理上將道路重新分割成相等的路段，同一路段內的節點屬于同一簇，選取距離道路分段中間最近的節點作為簇頭（Cluster Head，CH）；2）適用于道路上車輛高速移動的情況，同一簇內車輛移動方向相同并且具有相近的移動速度［13］，當車輛在道路上高速移動時，車輛頻繁地加入或離開所在簇，使CH重選過程變得頻繁，從而對網絡的穩定性產生不利影響［14］。本文提出一種基于最佳穩定度的雙簇頭選擇算法，選取每個簇內穩定度最佳的節點作為CH，穩定度次佳的節點作為輔助簇頭（Auxiliary Cluster Head，ACH），降低了重選CH 造成的影響，從而達到車載無線自組織網絡連通性維護的目的。

1.1 雙簇頭的VANET 網絡結構

將車輛按一定規則劃分為簇，并選擇CH 和ACH 負責其簇的協調任務。當CH 處于活躍狀態，ACH 處于休眠狀態，記錄來自同一簇內CH 的數據副本；當CH 發生錯誤或不可預知的緊急情況，ACH將做好準備，負責CH 的工作任務。不屬于CH 鄰居節點的車輛必須獲取另一個簇，一跳以內的車輛會在其路由表中檢查其通信的CH 數量，同一簇內既不是CH 也不是ACH 的節點為成員節點（Member Node，MN）。VANET 結構中的簇如圖1 所示。

圖1 VANET 結構中的簇Fig.1 Clusters of VANET structure

從圖1 可以看出，簇中的車輛通過CH 從基站（Base Station，BS）獲得服務，減少了通信過程中的信令開銷。簇中的車輛使用IEEE 802.11p 接口通過CH 發送和接收數據，車載用戶可以無縫訪問運營商的服務，降低了成本，減輕了蜂窩負擔并節省了許可頻譜資源。ACH記錄來自CH 的消息副本，并隨時準備應對緊急情況。當CH 移動速度過快或其他原因離開該簇，ACH 立即作為CH 開始工作，并選取新的ACH，以降低因競爭簇頭造成的時延影響。

1.2 簇的劃分

簇的劃分主要是基于BS 和具有無線網絡接口的車輛以及到達角度（θ）、接收信號強度（RS）和車輛間距離（Vehicle Distance，VD）3 個因素。

1）BS 初始分組

在BS 側，根據相似的θ和RS，將車輛大致分為幾個分組，然后將分組信息發送給該區域中的車輛。根據文獻［15］，在MAC 協議中，車輛的傳輸面被分成α個等度(360/α)的傳輸角(C1，C2，…，Cα)，通過將每個傳輸角賦給唯一的一個車輛組，形成α個方向群。在笛卡爾空間中，每個分組的特征是向量F=(cosθF，sinθF)，其 中θF為傾斜角。車輛先使用GPS設備確定其傾斜角θF，從而確定其在笛卡爾空間中的矢量坐標；然后通過不同的傳輸角和RS來定義不同的車輛組，每個車輛組的RS特征滿足公式：

2）簇的細分

在依據行車方向和信號強度對車輛初始分組后，根據IEEE 802.11p 無線傳輸范圍對車輛進行分簇。在從基站接收到車輛分組列表之后，車輛使用VD 來細化該組并形成簇。由于BS 預測的車輛位置信息可能不準確，文獻［16］中車輛采用IEEE 802.11p 廣播消息驗證VD，并更新分組列表，最后根據傳輸范圍形成簇，車輛的傳輸范圍L如式（2）所示：

其 中：Hmax為最大IEEE 802.11p 傳輸范圍；ε為當前位置的無線信道衰落情況。將城市道路以車輛傳輸范圍作為依據劃分為簇。為保證相鄰兩個簇間的正常通信，本文以車輛傳輸范圍的劃分為簇，那么相鄰兩簇的簇頭一定存在于對方的傳輸范圍內［4］。

根據文獻［17］，用dB表示從CH 到BS 的平均距離，簇內成員與其CH 之間的平均距離用表示。dB如式（3）所示：

其中：ρ(x，y)是節點分布；假設CH 選擇標準滿足預期條件，A為場景面積，單位為m2，有N個節點均勻分布，節點在該場景中成為CH 的最佳概率Pb如式（5）所示：

其中：Kb為最佳簇數，取決于場景和節點數N的大小，且主要與CH 與BS 之間的距離相關［17］。構造的最佳簇數如式（6）所示：

其中：設μ為0.01，將m的長度設置為100 m，節點個數N設置為100，那么當75 m

2 雙簇頭的改進AODV 路由協議算法

在分簇之后，需要選取CH，以便有效將消息傳輸到BS。本文提出一種雙簇頭的AODV-CMIRP 路由協議用于VANET 環境，根據節點相對移動度和相對速度對CH 進行選取。

2.1 系統模型

假設專用短程通信（Dedicated Short Range Communication，DSRC）是用于交換數據包的無線技術，DSRC 在PHY 層和MAC 層上使用802.11p 標 準。本文還有以下5 個假設：1）每輛車都配有GPS 接收器，且具有相同的無線電范圍，車輛可通過GPS 了解其自身的位置，并使用導航系統繪制其在道路上的位置圖，通過特定的位置服務獲得目的節點的當前位置；2）簇的大小受其簇頭無線電范圍的限制；3）車輛行駛速度介于5～20 m/s；4）同一簇內的車輛向同一方向行駛；5）車輛的時鐘都是同步，車輛配有足夠的計算資源，并且車輛節點的緩沖區足夠大，能夠存儲大量數據。

2.2 簇頭選擇算法

針對VANET 中節點速度快、網絡拓撲變化頻繁的特點，本文提出一種雙簇頭的路由改進算法，選出簇內穩定性最好的節點作為CH，確保在最長時間內CH 與簇內其他節點的距離不會過大，從而降低通信鏈路發生斷裂的概率。

根據節點連續兩次接收到鄰居節點數據包的發射功率之比來計算節點的相對移動度［18］，節點Vi相對節點Vj的相對移動度如式（7）所示：

其中：Mi(j)為節點Vi相對節點Vj的相對移動度；與分別為節點Vi在當前時間間隔與上一時間間隔內接收到節點Vj的發射功率。若<，則Mi(j)<0，表示兩者之間的距離正在變大；若>，則Mi(j)>0，表示兩者之間的距離正在變小。

對于任意節點Vi，如果其周圍存在NL個鄰居節點，需要計算NL個Mi(j)值，通過計算節點Vi對其所有鄰居節點的相對移動度總和，得到節點Vi相對其所有鄰居節點的平均相對移動度：

其中：Mi為節點Vi的平均相對移動度；Mi(jk)為節點Vi相對于其第k個鄰居節點的相對移動度；NL為節點Vi的鄰居節點總數。Mi的值越小代表節點Vi相對于其鄰居節點的移動性越低，節點越穩定；反之，Mi越大表示其相對鄰居節點的移動性越高，節點穩定度越低。

節點Vi的相對速度［13］如式（9）所示：

其中：Qi為節點Vi相對于其周圍NL個相鄰節點的平均相對速度；xi為節點Vi的當前速度；xk為節點Vi的第k個鄰居節點的速度。Qi越大，表示Vi節點相對于鄰居節點的相對速度越大，節點穩定度越低。

在選擇簇頭的過程中，節點Vi通過與其相鄰節點進行節點間的信息交換計算出自身的穩定度，如式（10）所示：

其中：Si為自身穩定度的大小。Si值最大的節點將被選擇為CH，即平均相對移動度和相對速度的減小節點被選為CH 的概率越大。

簇內車輛主要通過CH 與BS 通信，如果簇內存在CH，且CH 工作正常，那么CH 負責簇間數據的轉發，并將車輛數據的副本周期性發送到ACH；如果CH 發生錯誤，那么ACH 作為新的CH，承擔CH 的工作任務，然后選擇新的ACH 并將車輛數據傳到新的ACH。一旦發現簇內沒有CH 和ACH 則需要根據CH 選擇算法，選出新的CH和ACH。根據參數Mi以及Fi來確定選出接近于最佳穩定度的車輛節點作為CH 和ACH。CH 和ACH 選擇流程如圖2 所示。

圖2 CH 和ACH 選擇流程Fig.2 Selection procedure of CH and ACH

在進行周期性檢測時，如果發現簇內沒有CH 或ACH，需要及時選擇CH 及ACH。若被選為CH，將節點狀態更改為CH，向其鄰居CH 發送CH 包并且向其ACH 發送備份數據；若沒有被選為CH 而被選為ACH，將其狀態更改為ACH，其鄰居列表中有且僅有一個CH；若沒有被選為CH 或ACH，節點狀態即為MN。雙簇頭選擇算法如下：

2.3 轉發策略

在所提出的AODV-CMIRP 路由協議中，車輛節點會周期性地向CH 發送當前的位置和速度信息。本文使用的特殊控制有Hello 包、CH 數據包、ACH數據包。

1）Hello 包。一個四字段的數據包，包含車輛Vi的序號（Vi_ID）、狀態（Vi_Status）、該節點自身的穩定度（Si）和鄰居列表（Vi_NL）。其中狀態字段獲取3 個可能值之一，分別是CH、ACH 和MN。

2）CH 數據包。構成該數據包的字段分別為包ID（P_ID）、簇頭ID（CH_ID）、源車輛節點ID（S_ID）、目的車輛節點ID（D_ID）和目的簇頭的ID（DC_ID）。

3）ACH 數據包。構成該包的字段分別為包ID（P_ID）、所在簇的簇頭ID（CH_ID）和CH 備份數據（CH_DT）。

開始時將道路上所有車輛的初始狀態均設置為MN。所有的車輛相互之間交換Hello 包，每輛車都會在Hello 包中發送其鄰居節點的信息，并完成CH選擇。當源節點S需要向目的節點D發送數據包時，其主要步驟如下：

1）令源節點為當前節點。

2）首先當前節點檢測是否與目的節點D在同一簇內。若在同一簇內，當前節點以最多2 跳的方式將數據轉發至目的節點D，并結束本次通信；若不在同一簇內，則啟動路由決策過程。

3）根據CH 提供的位置信息，建立包含當前節點、當前節點所在簇的CH、目的節點所在簇的CH 和目的節點的骨干路由。當前節點先將請求消息RREQ 發送給所在簇的CH，接收到RREQ 的CH 根據當前的位置信息，選擇距離最近且簇內有足夠車流量來保證連通性的鄰居CH 轉發RREQ。鄰居CH接收到RREQ 后，根據該策略轉發RREQ，直至消息轉發至目的節點。

4）在轉發RREQ 消息的過程中，每個CH 都記錄RREQ 的轉發路徑。目的節點在接收了RREQ 消息后，按RREQ 的轉發路徑，回復RREP 消息至當前節點。若當前節點在規定時間內沒有收到RREP 消息，則默認為傳輸失敗，并返回RRER 消息；否則，當前節點開始向目的節點傳輸數據包。

3 仿真實驗與分析

3.1 仿真環境

本文采用NS2 網絡模擬軟件，在Ubuntu 18.04 的環境下，對AODV-CMIRP 協議進行仿真實驗。為了能夠模擬接近真實的城市環境道路交通場景及車輛運動行為，采用微觀交通仿真軟件SUMO 生成街道模型和節點運動模型，AODV 參數設置如表1 所示。

表1 AODV 參數設置Table 1 AODV parameters setting

3.2 仿真結果及分析

實驗選取原AODV 協議與CBDRP 協議［19］進行仿真模擬和對比分析。

3.2.1 簇頭生存時間

簇頭生存時間定義為車輛節點充當CH 的持續時間，一個動態簇的生存時間很大程度上取決于簇頭生存時間，簇頭生存時間越長，該簇穩定性越高［20］。傳輸范圍與簇頭生存時間的關系如圖3 所示。從圖3 可以看出，當道路上的車輛個數為100，最大移動速度為20 m/s 時，傳輸范圍從100 m 增大到400 m 的簇頭壽命變化情況。隨著車輛傳輸范圍增大，兩種協議簇的規模均增加，因此簇頭生存時間增加。在傳輸范圍相同時，AODV-CMIRP 協議的簇頭生存時間較長。CBDRP 協議選取簇頭主要根據簇內節點的位置信息和速度矢量，并未考慮節點穩定度，而AODV-CMIRP 協議將每個節點的相對速度和相對移動度作為節點穩定度的評價指標，選出簇內穩定度最佳的節點作為簇頭，從而有效地延長了簇頭生存時間。因此，在簇頭生存時間上AODVCMIRP 協議表現更佳。

圖3 CBDRP、AODV-CMIRP 協議簇頭生存時間的對比Fig.3 Cluster head lifetime comparison of CBDRP and AODV-CMIRP protocols

3.2.2 平均跳數

平均跳數定義為網絡中所有節點投遞數據分組路由跳數的平均值，平均跳數越少，說明路由協議所消耗的網絡帶寬和時間越少，路由性能也更好［21］。CBDRP、AODV-CMIRP 協議平均跳數對比如圖4 所示。兩種協議傳輸范圍與數據分組從源節點到目的節點經過路徑跳數平均值之間的關系。在傳輸范圍相同時，CBDRP 協議在分簇時并未考慮車輛的傳輸范圍對分簇的影響，而AODV-CMIRP 協議簇的劃分與車輛的傳輸范圍相關，且考慮到最佳分簇數量的上下限。因此，在平均跳數方面AODV-CMIRP 協議表現更好。

圖4 CBDRP、AODV-CMIRP 協議平均跳數對比Fig.4 Average hops comparison of CBDRP and AODV-CMIRP protocols

3.2.3 平均端到端時延

平均端到端時延為節點間投遞數據分組耗費時間的平均值，用來衡量路由協議的實時性。平均端到端時延越小，說明路由協議投遞數據分組的時間越短。AODV、CBDRP、AODV-CMIRP 協議平均端到端時延對比如圖5 所示，可以看出3 種協議的平均端到端時延均隨著節點數量的增加而逐漸降低。隨著節點總數的增加，參與路由轉發的節點也會增加，從而增加了滿足路由轉發條件的節點個數，降低了平均端到端時延。AODV-CMIRP 協議采用雙簇頭傳輸數據分組，在計算相對穩定度的過程中考慮簇內節點數量對簇頭選擇的影響，所以平均端到端時延較小。CBDRP 協議并未考慮節點數量變化對分簇后協議性能的影響，因此AODVCMIRP 協議的平均端到端時延更低。

圖5 AODV、CBDRP、AODV-CMIRP 協議平均端到端時延對比Fig.5 Average end-to-end delay comparison of AODV，CBDRP，AODV-CMIRP protocols

3.2.4 分組投遞率

分組投遞率為目的節點接收到的數據包個數與源發送的數據包個數之比，反映了網絡傳輸的可靠性。分組投遞率越高，說明路由協議傳輸數據分組的成功率越大、丟失數據分組的可能性越小。AODV、CBDRP、AODV-CMIRP 協議分組投遞率對比如圖6 所示，可以看出隨著節點個數增加，數據的分組投遞率均有所提升，因為節點個數增多時，節點的相遇概率會增加，提升了網絡的連通性，降低了路由空洞的概率。AODV-CMIRP 協議的簇頭更穩定，在簇頭選擇過程中考慮了簇內車輛節點的相對速度和相對移動度，增強了路由協議的可靠性，保證了節點之間的正常通信，因此AODV-CMIRP 協議分組投遞率優于CBDRP 協議。

圖6 AODV、CBDRP、AODV-CMIRP 協議分組投遞率對比Fig.6 Packet delivery fraction comparison of AODV，CBDRP，AODV-CMIRP protocols

4 結束語

本文提出一種用于車載自組織網絡連通性維護的AODV-CMIRP 路由協議。該協議根據最大化簇頭生存時間原則選取簇頭，將平均相對移動度和相對速度作為簇頭穩定性的評判依據。仿真結果表明，與AODV、OBDRP協議相比，AODV-CMIRP協議在簇頭生存時間、平均跳數、平均端到端時延、分組投遞率四項指標上表現均較好，減少了網絡重選簇頭的次數，進而提高網絡的穩定性。為進一步降低節點發射功率并均衡網絡能耗，后續將對AODV-CMIRP協議中節點的能量特性進行研究。