基于分簇與改進Q 學習的車聯網V2V 復合路由算法

畢 翔，黃 晃，張本宏，衛 星，3

（1.合肥工業大學 計算機與信息學院，合肥 230009；2.合肥工業大學 安全關鍵工業測控技術教育部工程研究中心，合肥 230009；3.合肥工業大學 智能制造技術研究院，合肥 230009）

0 概述

在城市場景中，基于車-車（V2V）通信方式的車輛自組織網絡（VANETs）能夠快速地傳輸數據［1］，有效提高人們的出行安全和駕乘體驗，在智能交通系統中起著支撐性作用［2］。然而，車輛節點的運動隨機性和分布不均勻性給建立穩定的通信路由帶來了極大的挑戰［3］。

專用短程通信（Dedicated Short Range Communication，DSRC）技術的MAC 層協議［4］作為V2V 通信中常用的一種技術，主要由IEEE 1609.4 和IEEE 802.11P 協議構成。車輛節點采用競爭機制獲得信道的使用權。在城市車輛高密度場景下，信道訪問的沖突問題頻繁發生，從而嚴重影響了VANETs 的整體性能。

鑒于分簇機制能夠有效地緩解大規模無線網絡的訪問沖突問題［5］，研究人員提出基于分簇結構的VANETs 路由建立方法［6-8］，用于解決移動自組織網絡地理協議中的網絡規模問題［9］。文獻［10］提出一種基于目標感知的路由協議，以提高簇與簇之間數據的傳輸效率。與現有基于位置選擇下一跳簇頭的方式相比，該方式考慮簇頭和數據傳輸的方向，有效降低了數據反向傳輸對鏈路穩定性和通信延遲的影響。文獻［11］提出一種基于車輛屬性信息的兩級路由算法，在簇頭選擇階段，考慮車輛類型、總距離、車輛速度變化、鄰居數目等因素對簇結構穩定性的影響。但大多基于分簇的VANETs 路由算法需要路由請求和路由確認數據包建立從源節點到目的節點的多跳路由。車輛的高機動性和行駛軌跡的隨機性使得所建立的路由會因鏈路的斷開而變得不可用，需要不斷地對路由進行維護甚至重新建立從源車輛到目的車輛的路由，不僅影響了網絡的通信性能，也極大增加了通信開銷。

上述路由建立方法屬于非實時的方法，適用于拓撲結構較穩定的網絡，無法滿足VANETs 拓撲結構快速變化的網絡進行實時數據傳輸的要求。現有VANETs 中基于Q 學習的算法［12-14］通過車輛與環境不斷交互獲取新Q值的方式，達到適應周圍復雜多變VANETs 環境的目的。但這種Q值更新并不涉及Q 表結構的維護，也不能實時體現環境參數的變化。此外，在數據傳輸階段，僅依據最大Q值尋找下一跳的方式，因為車輛的機動性和鏈路狀態不確定性，所以容易造成“盲路”問題［15］。

本文提出基于分簇和改進Q 學習的多跳通信復合路由算法RCRIQ，通過定義一種網關效用性函數，將邊緣車輛中通信性能較優且速度相對穩定的節點作為網關節點，以提升通信路由的穩定性。通過動態方法確定學習率和折扣率，實現了對現有Q 學習算法的改進。

1 系統模型

分布式網絡模型結構如圖1 所示（彩色效果見《計算機工程》官網HTML 版）。

圖1 分布式網絡模型結構Fig.1 Structure of distributed network model

每一個橢圓形區域是一個完整的簇結構，簇內黃色車輛表示簇頭車輛，如圖中編號為1、7、12、16、19 的車輛。綠色車輛表示網關車輛，如圖中編號為2、5、8、14、17、22 的車輛。藍色車輛表示簇成員車輛，如簇A 中編號為9、10、11 的車輛。紅色車輛表示未定義車輛，如圖中編號為23 車輛。在簇內的簇成員之間通信需借助簇頭的轉發，跨越不同簇之間進行通信，由簇頭將數據包傳輸給本簇的網關車輛，再由網關節點選擇鄰居簇的簇頭車輛或網關節點完成轉發。其中，簇頭采用獨立的信道分別對簇內和簇間數據包進行轉發。

2 網關選擇

在傳統基于分簇的路由算法中，當大多數路由協議在通信范圍內沒有合適的中繼車輛時，數據包采用“存儲轉發”的方式，造成延遲偏高。如果選擇邊緣車輛中合適的車輛作為網關車輛，可以進一步拓展單個簇的覆蓋范圍，降低通信延遲。

根據式（1）計算簇成員與簇頭之間歐氏距離的平方，簇頭選擇邊緣車輛中合適的車輛構建候選列表ζ。如果簇成員與簇頭之間的距離滿足條件D(Vch，Vcm)≥Dth·Dth，則將這個車輛節點加入到ζ中，其中Dth為距離閾值常數。

其中：xch、ych、xcm和ycm分別表示簇頭車輛和簇成員車輛的x軸和y軸坐標值。

本文通過網關效用性函數fG構建網關效用性函數列表LGW。網關效用性函數形式化如式（2）所示：

其中：D(Vi，Vj)為車輛距離；R為車輛通信半徑；ncm為簇中車輛數目；為車輛Vi的簇成員列表；和分別為車輛Vj的總帶寬和已用帶寬；LCG為簇頭的候選網關列表。

3 基于車輛運動學特征改進的Q 學習算法

標準的Q 學習是一種基于智能體的啟發式算法，智能體的學習過程可以用一個三元組［16］表示{S，A，R}。其中，S表示狀態空間，A表示動作空間，智能體在相鄰狀態之間轉移的行為被當作一個動作，R表示對于執行一次動作對應的即時獎勵。本文提出改進Q 學習的相關定義及其學習過程。

定義1（基本組件）整個VANETs 環境作為智能體的學習環境。狀態空間S與傳統車聯網中運用Q 學習的研究不同，本文沒有將環境中的每一輛車當作一個狀態，一輛簇頭或網關車輛和它的鄰居簇頭車輛和網關車輛分別作為獨立的一個狀態，由多個這樣的狀態構成的集合為狀態空間。智能體從一跳鄰居中選擇下一跳并發生狀態轉移的過程，可以看作是一個動作，智能體可執行的動作為當前節點的單跳鄰居列表，多個這樣動作的集合構成動作空間A。在智能體中每一個數據包是一個智能體，它的職責是在每個離散狀態下通過執行不同的動作以獲得不同的獎勵，以尋求到達目的節點的最優策略。

定義2（獎勵值）根據定義1，智能體每執行一次動作所獲得的獎勵被稱為即時獎勵，用R表示，取值范圍為[0，1]。

僅當下一跳車輛是目的車輛的簇頭車輛或網關車輛時，獲得的獎勵值等于1，其余情況的即時獎勵均為0。獎勵值形式化表示如式（3）所示：

其中：Vj表示當前簇頭車輛Vi的鄰居簇頭或網關車輛；表示目的車輛Vk所在簇的簇頭或網關車輛的鄰居列表。

定義3（Q 表）Q 表的第一行包含所有可到達目的車輛ID，用di表示，第一列表示單跳鄰居的ID，用ni表示。Qi(j，k)表示節點i選擇節點j作為到達目的節點k的下一跳節點對應的Q值，Q值范圍為0～1。Q 表是一個二維表，其大小由鄰居節點數和目的節點數決定，Q值通過節點之間周期性發送的HELLO包來更新。

Q 學習過程主要是更新節點維護的Q 表結構，同時更新Q 表中的狀態行為值，Q 學習的形式化如式（4）所示：

3.1 基于鏈路持續時間的學習率

傳統運用在車聯網中的Q 學習算法由學習率和折扣率確定。文獻［17］在仿真實驗中選取多組學習率和折扣率進行實驗，但是其作為一個常量，一旦設定就不能更改，不能體現算法的自適應性，難以適應多種VANETs 場景。學習率越高，最新的學習值在更新的Q值中所占的比例越大，學習速度就越快。由于學習率設置得太大也會誤導數據包轉發，因此智能體在某些情況下可能獲得不正確的即時獎勵0。為了進一步提高RCRIQ 算法的自適應性，本文將當前節點和下一跳節點之間的鏈路持續時間與當前節點和鄰居節點列表持續時間總和的比值作為學習率，如式（5）所示：

車輛之間的初始距離服從對數正態分布，記作X∈loga N(ui，δi)，i=0，1，…，n，且滿足0 ≤X＜R。假定道路的最大限速為vmax，對于t≥0 的任意時刻，車輛i的瞬時加速度記作ai(t)，瞬時速度為vi(t)，在T時間段內行駛的距離為Si(T)。對t≥0 的任意時刻，加速度的取值情況可以分為2 種情況：

1）如果ai(0)=0，對于任意t≥0 滿足ai(t)=0，表示車輛i在t≥0 時始終做勻速直線運動。

2）如果ai(0)≠0，表示車輛做勻加速運動或勻減速直線運動，如式（6）所示：

根據情況2，只要車輛沒有達到最大限速或者停止，則車輛i的加速度仍然是ai(0)。當車輛達到最大限速vmax或者速度減為0 時，加速度會變為0，即車輛達到最大限速vmax后做勻速直線運動，或者車輛速度減為0 之后車輛處于靜止狀態。

假定車輛i的初始速度為vi(0)，車輛i在任意t≥0時刻的速度vi(t)表示如式（7）所示：

其中：u∈[0，t]；ai(u)為車輛i的瞬時加速度。

根據式（6）和式（7）得到速度vi(t)的進一步表示有兩種情況，一種是如果ai(0)=0，可得vi(t)=vi(0)，對于t≥0 任意時刻，車輛做勻速直線運動，另一種是當車輛做勻加速或勻減速直線運動，則：

車輛i在t時間段內行駛的距離如式（9）所示：

假設車輛Vi和Vj之間通信的初始距離為X，車輛Vj在車輛Vi之前。鏈路斷開情景示意圖如圖2 所示，兩輛車都自西往東行駛。

圖2 鏈路斷開情景示意圖Fig.2 Schematic diagram of link disconnection scenario

兩輛車在T時間段內的距離差如式（10）和式（11）所示：

當車輛Vj在車輛Vi之前，兩者距離差為R，當車輛Vi在車輛Vj之前，兩者距離差為-R。

以上分析的是兩輛車同向行駛的情況，當兩輛車反向行駛時，車輛Vi和車輛Vj之間的距離差表示如式（12）所示：

兩輛車之間的最大鏈路時間可以分為2 種情況：

3.2 折扣率

車輛在選擇下一跳節點時，應避開選擇距離當前車輛節點較遠的車輛節點，將選擇距離較遠的鄰居車輛作為下一跳中繼車輛，增加了鏈路的不穩定性。因此，車輛i與鄰居車輛的距離因子如式（15）所示：

根據式（15）可知，選擇距離當前車輛節點i最近的下一跳車輛節點j，的值也會相應增大。本文將的值作為折扣率。根據式（4）可知，折扣率越大表明下一跳節點j的鄰居節點j'到目的節點對應的Q值所占的比重越大，進而影響到當前節點i選擇節點j作為到達目的節點k的中繼節點所獲得Q值的比重。

3.3 改進的Q 學習算法

改進的Q 學習算法如式（16）所示：

傳統的Q 學習算法選取鄰居列表中Q值最大的鄰居節點作為下一跳節點。因車輛行駛軌跡的隨機性，會造成鏈路拓撲結構的改變。由于鏈路通信狀況具有不確定性，因此按照最大Q值選擇下一跳的方式并不一定是最優的。當前車輛Vi在選擇下一跳鄰居簇頭或網關時，本文引入節點性能評估函數，有效緩解只按照最大Q值的方式選擇下一跳節點造成“盲路”問題。實時計算的性能評估函數值還可以起到對選擇的下一跳節點進行修正的作用，確保選擇的下一跳節點能夠及時適應網絡環境的改變。本文對式（16）進一步修改，改進后的Q 學習算法如式（17）所示：

其中：Wj(m，k)表示當前車輛Vj選擇車輛m作為到達目的車輛Vk對應的下一跳時獲得的Q值；m表示車輛Vj的鄰居車輛列表中某車輛。Wj(m，k)表示如式（18）所示：

其中：argmaxQj(j′，k)表示按照傳統Q 學習算法中最大Q值的方式選出Q 表中到達目的節點對應的鄰居節點j'；argmaxFj(j″，k)表示從性能評估函數的角度選出鄰居車輛j''。，根據式（18）得到的車輛j'和車輛j''完成對Wj(m，k)最終的賦值，如式（19）所示：

其中：j'和j''分別表示按照兩種策略選擇下一跳節點時對應的節點。如果采用兩種方式選出的車輛對應同一輛車，則表明按照最大Q值方式選出的下一跳節點在具有最優可達性的同時，通信性能和運動學方面的參數也是最優的。當采用兩種方式選出的節點不是同一車輛時，車輛的移動性以及車輛駕駛操作的不確定性，會造成數據包反向傳輸以及下一跳車輛與當前車輛之間的鏈路不穩定。此外，通信中每輛車的通信狀況不確定，如果不考慮下一跳待選車輛的通信狀況，可能會加劇現有網絡的擁塞，導致通信延遲增加。按照最大Q值選中的車輛節點可能因為車輛機動性在下一刻超出當前車輛i的通信范圍，存在“盲路”問題。本文將式（18）和式（19）得到的Q值代入到式（17）中，完成本輪Q 學習過程。雖然選中的Q值不是最優的，但是從鏈路通信質量、數據包轉發的方向性，以及兩跳車輛之間鏈路穩定性的角度來確保當前選中的下一跳車輛是最優的。

4 RCRIQ 路由算法

分簇機制能夠有效解決大規模網絡中數據傳輸效率較低的問題。Q 學習作為一種自學習算法，通過與周圍環境的不斷交互來達到適應復雜多變外部環境目的。因此，將Q 學習算法運用到復雜多變的VANETs 環境是合適的。但是，Q 學習采用最大值查找最優路徑的方式，容易產生“盲路”問題。在數據包路由階段，本文給出節點性能評估函數對下一跳車輛的綜合性能進行評估，路由過程按照Q學習算法和節點性能評估函數兩種策略選擇下一跳車輛。

4.1 節點性能評估函數

當車輛Vi選擇到達目的車輛Vk的下一跳中繼節點Vj時，Vi需要對下一跳車輛Vj的選擇方法進行量化評估。從鏈路通信質量因子、方向因子和移動因子3 個角度衡量車輛Vi和Vj之間鏈路的綜合性能。

4.1.1 鏈路通信質量因子

鏈路通信質量因子從鏈路通信質量的角度量化下一跳車輛對網絡性能的影響。車輛定期發送HELLO 消息的時間間隔為τ，鄰居車輛通過計算在一段時間內接收到的HELLO 數據包數目和發送的數據包數目之間的比值，衡量相鄰兩跳車輛之間的鏈路質量。將5τ內每輛車HELLO 數據包接收率的平均值作為鏈路通信質量因子，并根據發送數據包數目分別進行討論，如式（20）所示：

當收到鄰居車輛發送的HELLO 報文時，車輛從中提取鄰居車輛的qlink值。qlink值越大，表明鏈路通信質量越好，選擇qlink值較大的鄰居車輛，可以提高鏈路的穩定性，提高傳輸效率。

4.1.2 方向因子

方向因子可量化評估數據包朝向性對鏈路通信效率的影響。在實際數據包轉發的過程中，數據包可能向后轉發，造成數據包離目的車輛越來越遠，背離了數據包朝向目的車輛所在方向轉發的初衷。本文通過定義當前車輛Vi、下一跳車輛Vj和目的車輛Vk三者之間角度的關系來確保每一次數據包轉發的過程都朝向目的方向，確保數據包離目的節點越來越近，使得數據包能盡快地轉發給目的車輛，形式化表示如式（21）所示：

圖3 方向因子計算過程示意圖Fig.3 Schematic diagram of direction factor calculation process

4.1.3 移動因子

移動因子可以量化下一跳車輛移動性對路由鏈路穩定性的影響。車輛的移動性會對相鄰兩輛車之間的鏈路產生影響，選擇穩定性更好的鏈路，更有利于數據包的傳輸。本文以當前車輛Vi和Vj為例，移動因子形式化表示如式（22）～式（27）所示：

其中：為預先給定的移動性閾值，當車輛Vi和車輛Vj之間的移動性小于該閾值時，給移動因子賦值為1，表示從移動性角度選擇對應的下一跳鄰居車輛作為中繼車輛，否則賦值為-1。

根據鏈路通信質量因子、方向因子、移動因子定義節點性能評估函數，用于評估下一跳車輛Vj的綜合性能。節點性能評估函數如式（28）所示：

其中：Fi(j，k)表示當前車輛節點i選擇鄰居節點j作為到達目的車輛節點k的下一跳節點時，對應的節點性能評估函數值。當取值都為1 時，的取值為1，對最終的函數值形成正反饋，否則方向因子或移動因子中只要一個取值為-1，最終Fi(j，k)值為0，將最終求得F值最大的節點作為候選中繼節點。

4.2 路由建立過程

當源節點發送數據包時，由所在簇的簇頭代為轉發。簇頭車輛首先檢查Q 表以查看是否有到目的節點的下一跳車輛，若存在，則啟動數據傳輸過程。路由轉發策略流程如圖4 所示。

圖4 路由轉發策略流程Fig.4 Procedure of routing forwarding strategy

在啟動路由發現過程中，簇頭車輛通過組播的形式向所有鄰居車輛發送RREQ 數據包并啟動路徑請求定時器，其中RREQ 數據包記錄了它在路由過程中經過的所有節點ID。與大多數研究采取只有當RREQ 數據包到達目的節點時才返回RREP 消息的策略不同，本文采取的策略是當中間某個節點的Q 表中有到達目的車輛對應的Q值存在時，由該節點根據RREQ 數據包中的路徑生成一個RREP 數據包，并以單播的形式返回給上一跳節點，其中RREP 數據包包含到達目的節點對應的Q值，以達到提前返回的目的，從而縮短路由整體的延遲。當上一跳節點收到返回的RREP 后，從中提取對應的Q值，并根據Q值計算公式更新Q 表結構和計算新的Q值，重復上述過程，直至數據包到達源簇頭車輛，源簇頭收到返回的RREP 消息后取消請求定時器。此外，本文將RREQ 數據包最大請求次數設為3 次，若在3 次定時周期內源簇頭都沒有收到返回的RREP 數據包，則通知源節點目的節點不可達。

路由轉發策略的偽代碼如下：

車輛V4選擇鄰居車輛V7作為到達目的車輛Vd的中繼車輛對應的Q值為0.6，選擇鄰居車輛V6作為到達目的車輛Vd的中繼車輛對應的Q值為0.52，其中學習率取值為0.8，折扣率取值為0.7。數據包傳輸路徑示意圖如圖5 所示。

圖5 數據包傳輸路徑示意圖Fig.5 Schematic diagram of data packet transmission paths

如果按照最大Q值的方式選擇下一跳車輛，則最終的數據包傳輸路徑為Vs→V2→V4→V6→V9→V11→Vd或Vs→V1→V4→V6→V9→V11→Vd。因為節點性能評估函數綜合考慮了下一跳車輛的通信性能，所以在選擇下一跳車輛時會根據實際鏈路質量、數據包傳輸方向和兩輛車之間的移動性進行綜合分析。例如，當車輛V1選擇下一跳車輛時，按照最大Q值的方式應選擇網關車輛節點V4。然而，因為V4車輛作為另一個簇的網關車輛，與當前簇的相對速度和簇內的網關車輛V3相比，V3車輛更穩定，即按照節點性能評估函數值最大的方式選出的下一跳車輛是V3，綜合考慮選擇V3作為下一跳車輛。兩種策略綜合評估的機制在確保Q值最大和最優可達性的同時，使得其他運動特征和通信方面的參數也是最優的，實現數據高效傳輸的目的。

4.3 路由維護階段

當數據包在路由鏈路中丟失時，傳統路由協議會從源車輛重新將數據包發送到目標車輛［18-19］，或者切換到第2 條備用路由［20］，繼續發送數據包，這2 種方式具有較高的路由開銷。本文采用的策略如下：若車輛與下一跳車輛之間的鏈路斷連，則會通過Q 表結構的維護，刪除Q 表中失效車輛的記錄，即刪除鄰居車輛對應的行。如果Q 表中到達目的節點的Q值在指定的時間內沒有更新，則視為目的節點已失效，將刪除Q 表中該目的車輛對應的列數據。因為Q 表的結構和Q值，體現了網絡的狀況。因此，通過Q值的不斷迭代更新和Q 表結構的不斷維護，使得RCRIQ 能夠實時適應網絡環境的改變。

5 仿真結果

本文采用GAPC［21］中的分簇算法構建簇結構，在此基礎上，RCRIQ 分別與GPSR、RSAR、TCRA 算法從路由跳數、鏈路持續時間、吞吐量、丟包率、通信延遲等角度進行仿真實驗。為了確保仿真的真實性和有效性，本文采用德國科隆［22］和國內某市［23］移動數據集作為車輛移動數據集，根據節點數的不同，分別進行40、60、80、100、120、140、160、180、200 個車輛節點的仿真實驗。本文實驗的仿真參數設置如表1 所示。

表1 本文實驗的仿真參數設置Table 1 Simulation parameters settings of experiment in this paper

5.1 路由跳數對比

路由跳數表示當數據包成功到達目的車輛時經過的中繼節點數目，用于評估路由的穩定性。圖6所示為在不同數據集上4 種路由算法的平均路由跳數與車輛數之間的關系。隨著節點數的增多，2 個數據集中4 種路由算法的平均路由跳數均呈現下降的趨勢。在德國科隆數據集中，當節點數從120 增加到140 時，RCRIQ 算法路由跳數的下降速度比RSAR快。RCRIQ 基于分簇機制，有利于隔離廣播沖突，以提高傳輸效率并減少傳輸路由跳數。盡管RCRIQ和RSAR 均基于Q 學習的原理，但是在路由構建階段，RCRIQ 由簇頭車輛選取邊緣車輛列表中通信性能和穩定性均較優的車輛作為網關車輛，極大拓展簇結構的通信范圍且減少路由整體通信跳數。在數據傳輸階段，RCRIQ 采用復合路由，綜合評估下一跳車輛的綜合性能，相比RSAR 只按照最大Q值選擇下一跳車輛的方式，更能適應復雜多變的VANETs環境。GPSR 路由跳數較少的原因在于其采用貪婪轉發的策略，當數據包成功轉發到目的節點時，能保證路由跳數最少。TCRA 主要基于分簇的路由算法，通過多個簇頭構建主干路由，可以極大提高通信效率，但在路由階段，沒有對鄰居簇頭進行量化評估，造成選擇的簇頭雖然距離最近，但通信性能并沒有達到最優節點的通信性能。

圖6 不同路由算法的路由跳數對比Fig.6 Routing hops comparison among different routing algorithms

5.2 路由生存時間對比

路由生存時間表示從源節點到目的節點之間通信鏈路的存活時間。本文根據路由生存時間的變化情況來衡量通信鏈路的穩定性。在不同車輛節點下，各路由算法的路由生存時間對比如圖7 所示。隨著車輛節點數目的增多，在2 個數據集上4 種算法的路由生存時間均增加，這是因為隨著節點數的增加，鄰居列表中選擇通信狀況且穩定性較優的下一跳節點的可能性增加，以確保4 種路由算法的生存時間均增加。在2 個不同的移動數據集下，RCRIQ算法的路由生存時間分別比RSAR、GPSR 和TCRA平均提高13.49%、23.41%和16.33%。路由生存時間的提升是因為RCRIQ 的節點性能評估函數充分考慮了鏈路通信質量、數據包傳輸方向、車輛之間移動性對通信鏈路的影響，而RSAR 僅考慮了速度變化對通信鏈路穩定性的影響。GPSR 的路由生存時間最低是因為它采用貪婪機制，沒有考慮鏈路穩定性和網絡負載情況對路由生存時間的影響。TCRA 路由生存時間較短的原因是基于AODV 協議，需要不斷對路由進行維護，不能很好適應VANETs 環境。

圖7 不同路由算法的路由生存時間對比Fig.7 Routing lifetime comparison among different routing algorithms

5.3 吞吐量對比

吞吐量表示目的車輛在一定時間內接收有效數據包的總字節數與時間間隔的比值［24］。在不同車輛節點下，不同路由算法的吞吐量對比如圖8 所示。隨著車輛節點規模的不斷增大，在2 個數據集中4 種路由算法的吞吐量均增大。RCRIQ 的平均吞吐量分別比RSAR、GPSR 和TCRA 提高28.76%、52.97%、15.96%。RCRIQ充分考慮影響鏈路穩定性的因素，同時還將相鄰車輛的鏈路持續時間和距離定量化表示成Q 學習中的學習率和折扣率。鏈路持續時間長和距離近的鄰居節點能夠獲得更大的Q值，便于后續數據傳輸階段按照最大Q值策略查找下一跳車輛。相反，在RSAR 數據傳輸階段，只按照最大Q值查找下一跳節點，因車輛具有移動性，容易產生“盲路”問題，最終影響數據包的傳輸。GPSR 的吞吐量最低是因為其沒有重傳機制，當采用貪婪機制未能成功選出下一跳節點時，會直接丟棄該數據包，造成有效傳輸到目的節點的數據包偏少。TCRA 吞吐量較高是因為分簇可以對網絡頻譜進行高效管理，減少網絡擁塞的出現，極大提高單位時間內的數據傳輸率。

圖8 不同路由算法的吞吐量對比Fig.8 Throughput comparison among different routing algorithms

5.4 丟包率對比

丟包率用來衡量源節點發送的數據包經過路由轉發之后丟失數據包的比例［25］。圖9 所示為不同數據集中丟包率與車輛節點數目之間的關系。隨著車輛節點數目增加，4 種算法的丟包率均呈先下降后趨于平穩的狀態。RCRIQ 的平均丟包率分別 比RSAR、GPSR 和TCRA 分別減少56.78%、94.02% 和17.83%。RCRIQ 平均丟包率位于7.1%～10.6%之間，隨著節點數目的變化，丟包率整體變化不大。造成這種現象的原因是RCRIQ 基于Q 學習，通過Q值更新達到適應動態變化的VANETs 環境。與RSAR 不同，RCRIQ 通過簇頭或網關車輛實時維護Q 表結構，數據包通過Q 表結構的變化，可以實時感知網絡的變化。RSAR 也基于Q 學習理論，在構建路由時，對鏈路穩定性進行了評估，因此丟包率與RCRIQ 整體接近。GPSR 采用貪婪轉發和邊緣轉發的思想選擇下一跳節點，能夠適應高密度的場景。TCRA 依賴于簇頭，因為簇頭在選擇完成后丟包率變化不大，所以最終的丟包率變化也不大。

圖9 不同路由算法的丟包率對比Fig.9 Packet loss rates comparison among different routing algorithms

5.5 時延對比

時延表示數據包從源車輛出發，經過一系列中繼節點路由傳輸，最終成功到達目的車輛時所花費的時間。本文通過時延可以衡量路由算法的通信性能。不同算法的時延對比如圖10 所示。隨著車輛節點數目的增加，在德國科隆數據集中，節點數為120～160，4 種算法的時延先短暫上升后下降，其原因為隨著節點數目增多，短時間內會出現大量沖突的數據包，造成大量數據包丟失以至于重傳。隨著路由算法對網絡環境的適應，時延呈現下降的趨勢。RCRIQ 的平均時延比RSAR 降低14.52%，這是因為隨著車輛節點數目增加，RCRIQ 中簇頭節點和網關節點數目也增加了，找到綜合性能最優的下一跳節點的可能性更大，因此網絡整體延遲更低。GPSR 采用貪婪策略對數據包進行傳輸，當通過貪婪和邊緣轉發方式都無法到達目的地時，直接丟棄該數據包，以降低傳輸延遲。此外，圖9 中GPSR 算法的數據丟包率最大，也間接說明其延遲最低。TCRA 延時最高的原因是分簇的形成需要花費一定的時間，不能根據VANETs 環境的變化及時做出調整，且TCRA 基于AODV 協議，需要不斷對建立的路由進行維護，而在VANETs中拓撲斷連的現象非常普遍。

圖10 不同路由算法的時延對比Fig.10 Time delay comparison among different routing algorithms

6 結束語

傳統VANETs 路由算法存在路由維護成本和通信延遲較高且吞吐量較低的問題。為此，本文提出基于分簇和改進Q 學習的復合路由算法，采用節點性能評估函數和最大Q值兩種方式對待選的下一跳節點進行綜合評估。在德國科隆數據集和國內某市移動數據集上的仿真實驗結果表明，相比RSAR、GPSR 和TCRA 路由算法，RCRIQ 能提高數據包 傳輸率并延長鏈路存活時間，且降低傳輸延遲和丟包率，有效緩解由VANETs 網路拓撲頻繁變化帶來的問題。由于LTE 具有高帶寬和覆蓋范圍大的特點，因此下一步將結合LTE 與專用短程通信構建混合分簇網絡模型，以提高大數據包的傳輸效率。