一種基于路側裝置修正的遺傳VANET算法

朱 正 國

(安徽城市管理職業學院 信息技術學院, 合肥 230011)

0 前 言

車載自組網(vehicular ad-hoc network，VANET)是移動自組織網絡(mobile ad-hoc network，MANET)的一個分支，車輛可以在車 — 車、車 — 基礎設施模式下相互連接，或者在混合模式下進行連接[1-3]。 VANET中的路由協議分為基于拓撲的路由協議和基于地理位置的路由協議等兩大類[4-5]。

基于地理位置的路由協議適用于MANET[6]。其中，GPSR是典型的基于地理位置的路由協議[7]，使用車載全球定位系統接收器獲取車輛移動信息，選擇距離目的地最近的車輛轉發數據。首先，源車輛選擇距離目的地最近的相鄰車輛作為第一鄰居(first neighbor，FN)；然后，FN以相同方法選取下一個FN，直到數據包到達目標節點。但由于節點運動速度較快，一旦轉發失敗(即無法找到適合目標節點的FN或者通過GPSR協議發現的FN由于各種原因已失效)，則會重新尋找轉發鄰居，從而導致吞吐量下降[8]。

Wang等人提出了一種基于預測的貪婪周邊無狀態路由協議，通過車輛的速度和方向來預測相鄰車輛位置，直到接收到新信息[9]。袁學松提出了一種基于高速公路應用場景的鄰居發現方法NDK，通過卡爾曼濾波(kalman filter，KF)理論預測節點鄰居表[10]。路徑感知GPSR(path aware greedy perimeter stateless routing，PA-GPSR)在鄰居表中設計擴展表，選擇最佳路徑并繞過恢復模式下傳遞數據包的節點，但節點位置信息過于完美，不適合較復雜的場景[11]。Cao等人提出了一種基于模糊多因素決策(IRFMFD)的交叉口路由協議，適用于城市場景下的VANET傳輸[12]。為了解決VANET中高速公路場景下拓撲頻繁改變而導致的車輛節點丟失等問題，提出了一種基于遺傳算法(genetic algorithm,GA)的高效鄰居發現方法(neighbor discovery method by genetic algorithm，NDG)。

1 預測節點下一時刻位置與鄰居節點更新方案

1.1 路由節點丟失問題

使用GPSR協議時會出現中繼遺失的情況[13]，雙向路況通信模型如圖1所示。當車輛C要和車輛E通信時，根據GPSR協議，車輛C的數據將被發送至距其最遠且在通信范圍內的車輛D。但在下一時刻，由于車輛E的通信范圍與車輛D無交集，因此車輛C不能將數據包傳輸給車輛E，從而導致中繼遺失。此時，車輛C需要重新尋找中繼并傳輸數據包，網絡吞吐量下降。

圖1 雙向路況通信模型

當車輛C進入路側單元(RSU)的通信范圍后，RSU請求與其構建拓撲。車輛C按照規定的時間間隔進行信號和拓撲檢測，在接收到RSU的請求后同意構建拓撲。車輛C進入拓撲后既可以與其他車輛通信，也可以與RSU通信。當車輛C超出RSU的通信范圍時，車輛C和卡車建立拓撲，卡車作為FN傳輸數據。

下一時刻，車輛D超出RSU的通信范圍，RSU請求和車輛D斷開拓撲。車輛D按照規定的時間間隔進行信號和拓撲檢測，在接收到RSU的請求后同意斷開拓撲。此時車輛D重新按照規定的時間間隔進行拓撲檢測，發現其不在卡車的通信范圍內，故向卡車發送斷開拓撲的請求，卡車接受請求后，車輛D完全斷開模型拓撲。

初始狀態下，車輛E不在拓撲內，下一時刻車輛E通過偽基站進入拓撲，車輛節點數據傳輸不超過3跳。為了防范重新發現節點的不良影響，對節點通信范圍內所有節點下一時刻的位置、速度、加速度和運動方位等基本信息進行實時預測。本次研究使用GA[14]對節點基本信息進行預測。

1.2 預測節點下一時刻位置

GA具有高魯棒性和強通用性的特點，可以通過模擬自然進化過程找到最優解[15]。軌跡數據是一種多變量、多特征的數據，需要在多個變量之間找到最優解。本次研究根據車輛一段時間內的歷史軌跡，使用GA建立車輛歷史行為模式，以預測節點下一時刻位置。使用GA預測節點下一時刻位置的步驟如下：

(1) 基因編碼：在種群初始化之前，對歷史信息進行編碼。每隔1 s記錄1次車輛位置，車輛軌跡是染色體，車輛位置是基因。為了識別軌跡中的車輛身份，將染色體按時間順序排列，包括車輛ID和車輛位置。T={IDi，Ai，Bi，Ci，Di，Ei，Fi}，其中IDi是車輛i的身份，Ai、Bi、Ci、Di、Ei、Fi是車輛i的歷史軌跡，根據歷史軌跡可以解析出車輛的速度、加速度、位置、方向等基本信息。記錄t時刻的前6個軌跡，并動態清除t時刻前7個及更早的軌跡。對軌跡點使用實數編碼方法，即每個軌跡點由1個基因編碼，如1、2、3、4、5、6。對車輛身份使用二進制編碼，如00、01、10、11等。

(2) 初始化種群：隨機選擇部分個體作為初始種群。

(3) 適應度函數：用于衡量個體軌跡的相似度。

(4) 個體選擇：根據相似度大小，在種群中優選部分個體作為下一輪種群進化的初始成員。

(5) 基因交換：選擇2個個體，按照規定的方式交換它們的一些基因，產生1個新的個體。

(6) 基因變異：基因交換完成后，存在很多個體。由于遺傳的多樣性，以95%的概率選擇正常情況下第i個個體第j個基因(即第i條軌跡上的第j個位置)的個體，以5%的概率選擇第i個個體的第j個基因突變。

(7) 確定位置：根據獲得的軌跡確定最終位置。

1.3 鄰居節點更新方案

本次研究僅考慮最多2跳的情況，即如果源節點直接傳輸或者通過1個FN將數據傳輸至目標節點失敗，則命令源節點不傳輸數據至目標節點。因為當網絡中存在3跳及以上時，路由壽命的陡降可能導致路由失效。

為了解決車輛計算和存儲能力過載[16]等問題，采用基于GA的高效鄰居發現方法(NDG，neighbor discovery method based on genetic algorithm)，在NDG中引入RSU，如圖2所示。RSU放置在隔離帶中間某個位置，由于 RSU的覆蓋范圍較廣且計算能力強，因此使用RSU計算數據。RSU在NDG中起到轉發數據和計算參數的作用。

圖2 系統模型

車輛C發送數據給車輛E的過程包括以下3個步驟：

(1) 車輛C查詢鄰居表中是否存在車輛E。鄰居表中包含C的鄰居節點、C與鄰居節點的權重。

(2) 采用NDG計算鄰居節點下一時刻的基本數據。

(3) 當發現車輛D并非車輛C的鄰居節點時，將數據傳輸給車輛C鄰居表中下一時刻方向相同的鄰居節點中權重最大的車輛B。

源節點2跳范圍內的鄰居車輛數、源節點t時刻的速度和最高時速等因素影響著通信質量。車輛在選擇FN的權重如式(1)所示：

(1)

式中：Wi—— 車輛i的權重；

Ni—— 車輛i在2跳范圍內的鄰居車輛數，Ni=min(Ni,10)；

vm—— 高速公路的最高限速，vm=120 km/h；

vi—— 車輛i的速度；

a—— 鄰居影響比例；

b—— 車速影響比例。

其中：

(2)

FN的選擇過程如圖3所示，主要包括以下3個步驟：

圖3 FN的選擇過程

(1) 車輛向RSU發送傳輸數據的請求，RSU命令車輛反饋ID號、位置、車速、方向、通信范圍和半徑等基本信息。

(2) RSU判斷源車輛是否在其通信范圍內，如果不在則計算其通信范圍內的車輛權重，并建立鄰居表。

(3) 選取源車輛通信范圍內權重最小的車輛作為FN，如果權重相同，則選取ID號較小的車輛作為FN。

1.4 NDG流程介紹

NDG流程如圖4所示，主要包括以下8個步驟：

圖4 NDG流程

(1) 源車輛向RSU發送傳輸數據的請求；

(2) RSU收集車輛基本信息；

(3) RSU使用GA預測下一時刻車輛軌跡；

(4) 計算RSU和車輛的距離d1；

(5) 如果d1≥RRSU+RV(RRSU為RSU的通信半徑，RV為車輛的通信半徑)，則RSU選擇FN，調取FN的通信半徑RFN，計算車輛和FN的距離d2；

(6) 如果d2

(7) 如果d2≥RBN+RV，則不構建拓撲；

(8) 如果d1

2 仿真結果分析

假設全部車輛均安裝了定位裝置(如GPS、BDNSS等)，且車輛和RSU的通信范圍均是標準的圓。同時，車輛可以通過車載裝置獲得基本數據，如車輛的準確位置、速度、ID號、加速度和運動方向等[17]。為了確保仿真實驗的真實性，對FL-QN[14]和GPSR-2P進行仿真實驗，在Matlab2020仿真平臺上生成一段10 km×30 m的車道模型，車道為高速公路場景下雙向8車道，每隔2 km設置一個通信范圍為500 m的RSU。仿真參數說明如表1所示。選取數據包傳遞率(PDR)、端到端延遲(EED)、吞吐量等指標進行仿真實驗[18]。

表1 仿真參數說明

(1) PDR。源車輛傳輸的數據包數量與正確傳輸給目標車輛的數據包數量的比率。PDR的計算如式(3)所示：

(3)

式中：RPD—— PDR；

PR—— 接收到的數據包數量；

PS—— 發送的數據包數量。

(2) EED。相同數據流的所有數據包到達目的地的平均時間。EED的計算如式(4)所示：

(4)

式中：n—— 數據包數量；

TR,i—— 數據包i的接收時間；

TS,i—— 數據包i的發送時間。

(3) 吞吐量。單位時間內路由協議在網絡中傳輸的信息量。吞吐量的計算如式(5)所示：

(5)

式中：PT—— 吞吐量。

由PDR仿真實驗結果(見圖5)可知，相較于FL-QN和GPSR-2P，NDG的PDR最大，且穩定在90%以上。這是因為NDG使用了GA預測節點下一時刻位置，并利用中繼、RSU來輔助數據傳輸。

圖5 PDR仿真實驗結果

由EED仿真實驗結果(見圖6)可知，相較于FL-QN和GPSR-2P，NDG的EED最小。這是因為GPSR-2P選擇2條路徑來發送相同的數據包，增加了延遲時間和重復數據包的數量；FL-QN未對FN進行修正，會在稀疏場景中重新發現鄰居，導致路由數據包不斷重發，進而增加了EED。

圖6 EED仿真實驗結果

由吞吐量仿真實驗結果(見圖7)可知，3種算法的吞吐量都隨著車輛密度的增加而增加，但相較于FL-QN和GPSR-2P，NDG的吞吐量最大。這是因為GPSR-2P選擇2條路徑來發送相同的數據包，增加了接收時間與發送時間差；而FL-QN未對FN進行修正，會在稀疏場景中重新發現鄰居，導致路由數據包不斷重發，進而降低了吞吐量。

圖7 吞吐量仿真實驗結果

3 結 語

VANET是MANET的一個分支，已被廣泛應用于各個領域中。本次研究針對高速公路場景下數據傳輸的問題，提出了基于GA的高效鄰居發現方法。當車輛進入RSU通信范圍內時，利用RSU估算車輛下一時刻位置。RSU根據權重大小選擇最佳鄰居、計算最優路由方式，將最佳鄰居和路由信息發送給車輛。仿真實驗結果表明，本算法在不同的節點密度下均優于FL-QN和GPSR-2P。