利用機器學習和雙平面博弈模型的車聯網擁擠感知路由算法

譚曉芳 張 搴 付凡成

1(南昌理工學院計算機信息工程系 江西 南昌 330044)2(鄭州輕工業大學計算機與通信工程學院 河南 鄭州 450002)

0 引 言

車載自組織網絡作為一種特殊類型的移動自組織網絡(Mobile Ad-Hoc Network, MANET)，已成為智能交通系統(Intelligent Transportation System, ITS)的重要組成部分[1]。在VANET中，車輛配備有車載單元(On-Board Units, OBU)，這些單元能夠用于事件數據記錄器、全球定位系統、前向和后向雷達、傳感設備和短程無線接口。使用OBU，每個車輛充當發送器、接收器和路由器，以將信息傳遞給其他車輛。此外，這些車輛還可以與沿路邊部署的其他固定基礎設施通信，這些基礎設施被稱為路側單元[2](Road Side Units, RSU)。作為互聯網接入點，RSU在蜂窩網絡中扮演基站的角色。通常，VANET由RSU和車輛的OBU組成，它們在動態變化的VANET環境中反復交互[3]。

在VANET的運營期間，有兩種基本技術可以傳播車輛應用的數據：車輛與基礎設施(Vehicle-to-Infrastructure，V2I)和車輛與車輛(Vehicle-to-Vehicle; V2V)之間的通信。V2I通信可以幫助車輛從/向RSU下載/上傳內容，并且V2V通信主要依賴于車輛之間的協作來交換數據分組，而無需RSU幫助。V2I和V2V通信必須共存并相互補充，以滿足VANET的各種通信要求[4]。為了確保VANET性能，通過V2I和V2V通信有效地傳遞信息對于為移動車輛提供滿意的服務變得重要。大多數研究都考慮如何有效地管理涉及V2I和V2V通信的控制問題[5]。隨著VANET的蓬勃發展，車載擁擠感知(Vehicular Crowd Sensing, VCS)成為一種新的范例，它利用普遍存在的傳感器嵌入式OBU來有效地收集數據。文獻[6]使用基于語義的信息網絡新范式，解決了車聯網中信息傳播的問題，并對所提出模型的流量模型和網絡架構進行了表征。文獻[7]提出了兩種新的路由算法用于群體傳輸車載網絡，所提算法能夠在較低開銷下改善數據傳輸，而且開銷可忽略不計。文獻[8]從云計算和車輛互聯網(Internet of Vehicles, IoV)之間的服務關系角度討論了云輔助的分類，提出了一種利用來自聯網車輛的數據來提高運輸效率的新方法。文獻[9]通過擁擠感知(Efficient Data Dissemination by Crowdsensing, EDDC)方案有效解決了數據傳播問題，并在車載網絡中提出了一種混合路由機制。

本文提出了用于VANET管理的新型V2I和V2V算法。對于V2I通信，基于激勵的VCS算法開發了一種新型垂直博弈模型。在垂直博弈中，車輛和RSU是博弈玩家，車輛充當移動傳感器以收集所需信息，RSU充當系統服務器以共享和處理多種類型的收集信息。對于V2V通信，開發了一種新的水平博弈模型，以實現基于學習的車輛間通信協議。在橫向博弈中，車輛是博弈玩家，以提高路由服務的質量和可靠性。在動態變化的VANET環境下，本文方案被設計為雙平面垂直—水平博弈模型。通過考慮現實世界的VANET環境，提出的算法交互式順序博弈過程的方法是合適的，同時也確保了系統的實用性。為了研究每個博弈中博弈玩家之間的戰略互動，采用強化學習方法。強化學習涉及系統代理如何采取行動以最大化其獎勵。本文主要創新如下：

1)針對VANET設計了用于V2I和V2V通信的新型雙平面模型，在縱向博弈模型中網絡代理和車輛將向著擁擠感知過程工作；在橫向博弈模型中VANET為車輛選擇最佳路線。

2)基于橫縱向模型，利用強化學習的自主學習和優化決策為車聯網擁擠感知提供了一種有效的雙平面控制機制，能有效提升RSU任務成功率。

3)不同于現有方案的非自適應性和離線模式，所提算法基于分布式在線方法實現擁擠感知的自適應性和實時性，并通過控制決策權衡最優性和適用性。

本文算法將動態VANET環境的響應以及博弈論和強化學習算法的相互組合，與現有方案相比，在RSU的任務成功率、規范化路由吞吐量和端到端數據包延遲方面有較大改善。

1 方案設計

本文方案主要由基于強化學習的VCS策略和基于雙平面博弈模型的路由算法組成，其中雙平面博弈模型和強化學習是VANET控制方案的理論基礎。通過采用基于強化學習的博弈方法，并結合分布式在線計算和有效的路由算法，以適應快速變化的VANET環境。本文方案整體思路如圖1所示。

圖1 所提方案的整體架構

1.1 新型縱向和橫向博弈模型

博弈玩家N={R,V}的有限集合，其中：R代表RSU，V={V1，V2,…，Vi,…,Vk}是多個車輛的集合，Vi是第i個車輛，k是GV2I博弈的車輛數量；車輛則被假定為VCS過程中的移動節點。

RSU中有限的傳感任務集合X={X1，X2，…，XS}，S是總傳感任務的數量。

(1)

T={H1,H2，…,Ht,Ht+1,…}表示時間，其由具有用于V2I通信的不完全信息的一系列時間步驟表示。

GV2V可以制定用于路線操作的車輛的相互作用。

有限的一組博弈玩家V={V1，V2，…，Vn}NVi，其中n是GV2V博弈的車輛數量。

NVi是Vi的鄰近車輛。

UVi∈V是Vi收到的回報。

T={H1,H2，…,Ht,Ht+1,…}表示時間，其由具有用于V2V通信的不完全信息的一系列時間步驟表示。

1.2 利用強化學習的VCS策略

強化模型[12]能選擇執行使系統狀態得到更多增益的行為，這主要由該模型通過對系統現有狀態的感知，并對下一步的行為所能帶來的增益進行計算和評估來實現的；若節點執行狀態的決策發生了變化，便可以得到執行此行為的系統增益值。由圖2可知[13]，在路由發現過程t時刻，網絡中的每個節點都會選擇不同的動作策略ai(t)來共同對網絡產生影響，節點從狀態si(t)轉換到si(t+1)后，便得到ri(t+1)即環境回饋的相應回報值，然后各個節點對自身的價值函數Vi(s)再次進行新的評估，并對鄰居節點廣播該函數。

圖2 強化學習決策過程

對于單一節點的系統狀態評估值，可以使用無限視野價值評估模型來對其進行計算：

(2)

并且將未來有限步內的系統狀態轉換所帶來的增益rt設置為擁有同樣的權重γ。對于系統的優化問題，可以將其轉化為對由源節點S到目的節點D中經過的所有數據傳輸節點進行調整的決策過程，從而得到價值函數V(s)的最大值，以下為具體的求解過程。

將系統狀態集記作S，當前狀態能執行的動作集記作A，并且S和A的某種運算結果都可以使用系統增益R以及狀態轉移分布函數T(·)來表示。此處從狀態s執行動作a帶來的系統增益由R(s,a)表示，s經過動作a后轉移到s′的概率由T(s,a,s′)表示。對貝爾曼方程進行求解可得系統最優解V*(s)：

(3)

式中：狀態轉移增益權重記作γ；在狀態集S中所對應的每個狀態s′的當前價值評估值記作V*(s′)；將價值評估函數V*(s)能得到最大值的動作記為a，并選擇動作a作為下一步的狀態轉移操作。

將T(s,a,s′)作為每一條通信鏈路數據投遞成功和投遞失敗的比例，并對所有節點對嘗試發送的單播包數NA、單播傳輸失敗包數NF、接收到的單播包數NR、接收到的廣播包數NB和混雜接收單播包數NP等統計量進行記錄，從而對T(s,a,s′)進行計算。對投遞率進行計算時，需要在接收數據包統計量前面加上置信參數σ，并把ρ當作節點沒有發送數據包時的投遞率估計值，得到最終投遞率表示為：

(4)

式(4)表示的是系統接下來的狀態轉換為投遞成功s′=S時的轉移概率T(s,a,S)。因為指定了rS和rF為固定值-1和-7，因此T(s,a,s′)的簡單組合函數為：

R(s,a)=rS·T(s,a,S)+rF·T(s,a,F)

(5)

由此，T(s,a,s′)、R(s,a)評估模型得到了確定，再對貝爾曼方程進行求解可得V(s)的最優值：

(6)

通過分析可知，每個動作集a只會讓當前狀態s向兩種可能的狀態進行轉換，若P表示為下一跳的節點，那么系統狀態就會轉變為兩種可能：1)發生傳輸成功事件S，系統會從當前狀態s=N轉化到s′=P；2)發生傳輸失敗事件F，系統當前狀態s=N就會保持停留使得s′=N。由此可得系統Q值的計算過程為：

Q(N,P)=pS·[rS+V(P)]+pF·[rF+V(N)]

(7)

式中：數據包成功傳輸到節點P的概率由pS表示；傳輸失敗的概率由pF表示。轉化成求解問題：

(8)

若通過評估模型計算得到最優值函數，則選取能讓每個狀態能夠獲得最大Q值的動作就是最佳的決策過程，并將該過程稱為系統的開發策略。

1.3 雙平面博弈模型結合強化學習的V2V路由算法

V2V通信代表了支持使用端到端多跳路由的各種上下文感知應用程序的最理想技術之一。當日常道路旅行的安全性、效率和舒適性需要提高時，車輛間通信是實現這一目標的關鍵。然而，不同的車輛移動性經常導致不可靠的連接性和相應不穩定的服務質量。因此，MANET的傳統路由協議表明它們在VANET中的性能很差；VANET的路由協議應該能夠克服車輛的高移動性。

(9)

(10)

在路由路徑形成期間，每個單獨的車輛估計其相鄰車輛的LC值。目標車輛一跳內的車輛的PC值設置為從它們自己到目的地節點的單跳LC值。其余車輛，即Vj，LC值設定如下：

(11)

基于鄰近車輛的PC值，可以估計V2V通信的路由成本。通常，大多數V2V路由算法是通過依賴于車輛協作的假設來設計的，假設車輛愿意充當路由路徑中的中繼節點，而充當中繼節點的車輛必須犧牲其能量和帶寬。因此，路由算法需要刺激VANET車輛之間的合作行為才能有效[16-17]。

(12)

(13)

(14)

V2I和V2V算法的偽代碼如算法1所示。

算法1V2I和V2V算法

函數V2I(){

1.初始化參數

2.使用式(1)，制定車輛選取策略Sv使收益uv最大化

3.使用式(2)，確定價值評估模型

4.使用式(3)和(4)，確定目標函數和投遞概率

5.使用式(5)進行函數組合

6.Call V2V()

}

函數 V2V(){

1.使用式(6)，獲得最優值

2.使用式(7), 獲得系統Q值

3.使用式(8), 在源車處獲得到達目的地車輛

4.使用式(9), 進行估計

5.使用式(10), 獲得求和

Return

}

函數 Main(){

1.初始化控制參數。

2.學習值并平均分配。

For(; ;){

3. Call V2I()

}

}

1.4 算法流程

基于強化學習的垂直和水平博弈模型，通過逐步交互式博弈過程設計了一種新型V2I和V2V通信算法。該算法允許RSU和車輛學習當前的VANET情況并確定他們的最佳策略。在V2I博弈模型中，每個車輛通過參與VCS服務獲得激勵。在V2V博弈模型中，該激勵被用作虛擬貨幣以補償中繼車輛的成本。在實際操作方面，可以將計算負擔從中央系統轉移到分布式車輛。所提出的V2I和V2V算法的流程如圖3所示。

圖3 本文算法流程圖

2 實 驗

基于MATLAB/2016b仿真環境搭建了用于VANET的仿真平臺，該平臺運行于Windows 8 GB RAM 64位 Inter(R)CoreTMi5-7500K 2.7 GHz臺式計算機中。為驗證本文方法的感知和路由性能，將其與文獻[6]、文獻[8]和文獻[9]所提方法進行比較。文獻[6]制定了一個移動眾包博弈方案，其中每輛車根據傳感和傳輸成本以及預期的支付選擇其傳感工作，而服務器根據其傳感精度支付每輛車的成本。文獻[8]中，車輛必須在數據更新之前檢索所有數據單元，否則檢索數據單元版本將不一致，車輛必須在規定的延遲要求范圍內接收所有要求的數據單元，此外實驗方案側重于異構車輛網絡中協同狀態下同態數據的分發效率。文獻[9]側重于車聯網數據中的帶寬效率與業務異構性，實驗方案中車流量負載設置略有不同。EDDC方案通過使用附近RSU的擁擠感知來設計混合路由，以保證車載網絡中數據傳播的質量。文獻[9]評估了一種機會性擁擠感知方案，其中來自大量連接傳感器的流量通過新興的NB-IoT技術傳輸，基于仿真結果，確認了其優越性。為確保公平比較，根據文獻[18]，針對本文方法的實驗，采用以下假設和對應的實驗方案：

? 假設模擬系統是VANET的常見無線通信系統。

? 在200 km路段上隨機分布了1 200輛車和60輛RSU，每輛移動車的速度隨機選擇為40 km/h、80 km/h或100 km/h。

? 每輛車的最大無線覆蓋范圍設置為500 m。

? VCS的車輛成本C設置為RSU與相應車輛之間的相對距離與最大覆蓋范圍的比率。

? 隨機選擇源車輛和目的車輛。最初，每輛車的虛擬貨幣設定為100。

? 數據包在源節點以k(包/s)的速率生成，并且提供的負載范圍在0～4.0之間變化。因此仿真模型中的持續時間H為1 s，模擬的總持續時間為2 h。

? 假設車輛不受噪音或物理障礙的影響。

? 車輛帶寬容量為20 Mbit/s，每條消息由CBR數據包組成。

? RSU的任務和容量分別為10和2 Gbit/s。

? 基于200次模擬運行獲得的網絡性能測量被繪制為每秒數據包生成的函數。

為了證明方法的有效性，測量了RSU的任務成功率，標準化路由吞吐量和端到端數據包延遲。表1為仿真實驗中所使用的系統參數。

表1 模擬實驗中使用的系統參數

圖4比較了每個方案的RSU任務成功率。任務成功率是以任務完成相對于總RSU任務的百分比來衡量的，是V2I通信操作中的關鍵因素。隨著車輛的交通負荷增加，車輛致力于其自己的V2V通信，導致任務成功率降低。所有方案都表現出類似的趨勢，然而本文方案在從低到大的交通負荷情況下優于現有方法。RSU在交互式垂直博弈過程中為車輛支付適應性激勵，車輛自發地參與了眾籌工作。這種情況可以保證比其他方案更高的RSU任務成功率。

圖4 RSU的任務成功率

圖5比較了路由吞吐量。路由吞吐量被定義為在目的地車輛處接收的數據分組與在源車輛中生成的數據分組的總數的比率。通過本文方案實現的路由吞吐量的增益，是采用迭代學習模型的有效水平博弈范例的結果。特別地，本文方案捕獲相對距離和車輛的穩定性，自適應地選擇從源車輛到目的地車輛的最佳路線路徑。該方法可以增加V2V通信中的路由吞吐量。因此，本文方案實現了優于現有方案的路由吞吐量性能，現有方案被設計為單側協議并且不響應當前的VANET條件。

圖5 規范化路由吞吐量

圖6曲線表示歸一化的端到端分組延遲。通常隨著分組生成速率增加，分組延遲隨著業務負載線性增加。由于本文方案以分布式學習方式建立路由路徑，因此在每個水平博弈時段，提出的V2V通信算法中的每個車輛通過反映VANET環境中的變化來自適應地做出路由決定。所以，本文方法比其他方案更有效地減少了分組延遲。

圖6 規范化的端到端數據包延遲

仿真結果表明，本文方案使用基于學習的雙平面博弈模型，可以監視當前的VANET條件并適應高度動態的環境。方法中的RSU和車輛從環境中獲取信息，獲得知識，并以自適應的方式做出明智的決策。仿真結果表明，該方案通常表現出比現有文獻[6，8-9]方案更好的性能。盡管本文方案沒有提供最佳解決方案，但比現有方案具有實質性優勢。表1中的系統參數值是可變的，如果更改變系統參數值，則會更改模擬結果。在不同的模擬參數值下，性能趨勢幾乎相同。不同的仿真場景實驗結果證實了本文方案優于其他現有方案。

3 結 語

在VANET中，針對V2I和V2V通信問題，本文提出了一種新型雙平面博弈模型。基于VANET的特征，集成了交互式反饋機制，并基于強化學習和博弈論概念設計了縱向和橫向博弈模型，開發了適用于不完備信息條件下的高效VCS和交互式路由算法。在所提出的雙平面博弈模型中，單獨的RSU和車輛是博弈玩家，并且為自適應的機會性VCS和路由動態地學習其策略。使用基于反饋的自我監控和分布式學習技術，博弈玩家可以動態地適應當前的VANET情況，并有效地最大化預期收益。通過仿真實驗與現有方案進行對比，證明了本文算法在RSU任務成功率和吞吐量等指標的顯著改善。

盡管本文算法已經實現了VANET管理中提高吞吐量和VCS任務完整性的目標，但仍有待進一步提高VANET系統效率。其主要問題包括在負載平衡、認知無線電和網絡安全領域設計和驗證新的VANET控制方案。此外，當RSU旨在最大限度地減少對車輛的總支付時，可以擴展包括博弈模型中簡單懲罰的設計機制，以優化VANET特征控制算法。