畢 翔，黃 晃，張本宏，衛(wèi) 星，3

（1.合肥工業(yè)大學(xué) 計(jì)算機(jī)與信息學(xué)院，合肥 230009；2.合肥工業(yè)大學(xué) 安全關(guān)鍵工業(yè)測(cè)控技術(shù)教育部工程研究中心，合肥 230009；3.合肥工業(yè)大學(xué) 智能制造技術(shù)研究院，合肥 230009）

0 概述

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

專用短程通信（Dedicated Short Range Communication，DSRC）技術(shù)的MAC 層協(xié)議［4］作為V2V 通信中常用的一種技術(shù)，主要由IEEE 1609.4 和IEEE 802.11P 協(xié)議構(gòu)成。車輛節(jié)點(diǎn)采用競(jìng)爭(zhēng)機(jī)制獲得信道的使用權(quán)。在城市車輛高密度場(chǎng)景下，信道訪問的沖突問題頻繁發(fā)生，從而嚴(yán)重影響了VANETs 的整體性能。

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

上述路由建立方法屬于非實(shí)時(shí)的方法，適用于拓?fù)浣Y(jié)構(gòu)較穩(wěn)定的網(wǎng)絡(luò)，無法滿足VANETs 拓?fù)浣Y(jié)構(gòu)快速變化的網(wǎng)絡(luò)進(jìn)行實(shí)時(shí)數(shù)據(jù)傳輸?shù)囊蟆，F(xiàn)有VANETs 中基于Q 學(xué)習(xí)的算法［12-14］通過車輛與環(huán)境不斷交互獲取新Q值的方式，達(dá)到適應(yīng)周圍復(fù)雜多變VANETs 環(huán)境的目的。但這種Q值更新并不涉及Q 表結(jié)構(gòu)的維護(hù)，也不能實(shí)時(shí)體現(xiàn)環(huán)境參數(shù)的變化。此外，在數(shù)據(jù)傳輸階段，僅依據(jù)最大Q值尋找下一跳的方式，因?yàn)檐囕v的機(jī)動(dòng)性和鏈路狀態(tài)不確定性，所以容易造成“盲路”問題［15］。

本文提出基于分簇和改進(jìn)Q 學(xué)習(xí)的多跳通信復(fù)合路由算法RCRIQ，通過定義一種網(wǎng)關(guān)效用性函數(shù)，將邊緣車輛中通信性能較優(yōu)且速度相對(duì)穩(wěn)定的節(jié)點(diǎn)作為網(wǎng)關(guān)節(jié)點(diǎn)，以提升通信路由的穩(wěn)定性。通過動(dòng)態(tài)方法確定學(xué)習(xí)率和折扣率，實(shí)現(xiàn)了對(duì)現(xiàn)有Q 學(xué)習(xí)算法的改進(jìn)。

1 系統(tǒng)模型

分布式網(wǎng)絡(luò)模型結(jié)構(gòu)如圖1 所示（彩色效果見《計(jì)算機(jī)工程》官網(wǎng)HTML 版）。

圖1 分布式網(wǎng)絡(luò)模型結(jié)構(gòu)Fig.1 Structure of distributed network model

每一個(gè)橢圓形區(qū)域是一個(gè)完整的簇結(jié)構(gòu)，簇內(nèi)黃色車輛表示簇頭車輛，如圖中編號(hào)為1、7、12、16、19 的車輛。綠色車輛表示網(wǎng)關(guān)車輛，如圖中編號(hào)為2、5、8、14、17、22 的車輛。藍(lán)色車輛表示簇成員車輛，如簇A 中編號(hào)為9、10、11 的車輛。紅色車輛表示未定義車輛，如圖中編號(hào)為23 車輛。在簇內(nèi)的簇成員之間通信需借助簇頭的轉(zhuǎn)發(fā)，跨越不同簇之間進(jìn)行通信，由簇頭將數(shù)據(jù)包傳輸給本簇的網(wǎng)關(guān)車輛，再由網(wǎng)關(guān)節(jié)點(diǎn)選擇鄰居簇的簇頭車輛或網(wǎng)關(guān)節(jié)點(diǎn)完成轉(zhuǎn)發(fā)。其中，簇頭采用獨(dú)立的信道分別對(duì)簇內(nèi)和簇間數(shù)據(jù)包進(jìn)行轉(zhuǎn)發(fā)。

2 網(wǎng)關(guān)選擇

在傳統(tǒng)基于分簇的路由算法中，當(dāng)大多數(shù)路由協(xié)議在通信范圍內(nèi)沒有合適的中繼車輛時(shí)，數(shù)據(jù)包采用“存儲(chǔ)轉(zhuǎn)發(fā)”的方式，造成延遲偏高。如果選擇邊緣車輛中合適的車輛作為網(wǎng)關(guān)車輛，可以進(jìn)一步拓展單個(gè)簇的覆蓋范圍，降低通信延遲。

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

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

本文通過網(wǎng)關(guān)效用性函數(shù)fG構(gòu)建網(wǎng)關(guān)效用性函數(shù)列表LGW。網(wǎng)關(guān)效用性函數(shù)形式化如式（2）所示：

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

3 基于車輛運(yùn)動(dòng)學(xué)特征改進(jìn)的Q 學(xué)習(xí)算法

標(biāo)準(zhǔn)的Q 學(xué)習(xí)是一種基于智能體的啟發(fā)式算法，智能體的學(xué)習(xí)過程可以用一個(gè)三元組［16］表示{S，A，R}。其中，S表示狀態(tài)空間，A表示動(dòng)作空間，智能體在相鄰狀態(tài)之間轉(zhuǎn)移的行為被當(dāng)作一個(gè)動(dòng)作，R表示對(duì)于執(zhí)行一次動(dòng)作對(duì)應(yīng)的即時(shí)獎(jiǎng)勵(lì)。本文提出改進(jìn)Q 學(xué)習(xí)的相關(guān)定義及其學(xué)習(xí)過程。

定義1（基本組件）整個(gè)VANETs 環(huán)境作為智能體的學(xué)習(xí)環(huán)境。狀態(tài)空間S與傳統(tǒng)車聯(lián)網(wǎng)中運(yùn)用Q 學(xué)習(xí)的研究不同，本文沒有將環(huán)境中的每一輛車當(dāng)作一個(gè)狀態(tài)，一輛簇頭或網(wǎng)關(guān)車輛和它的鄰居簇頭車輛和網(wǎng)關(guān)車輛分別作為獨(dú)立的一個(gè)狀態(tài)，由多個(gè)這樣的狀態(tài)構(gòu)成的集合為狀態(tài)空間。智能體從一跳鄰居中選擇下一跳并發(fā)生狀態(tài)轉(zhuǎn)移的過程，可以看作是一個(gè)動(dòng)作，智能體可執(zhí)行的動(dòng)作為當(dāng)前節(jié)點(diǎn)的單跳鄰居列表，多個(gè)這樣動(dòng)作的集合構(gòu)成動(dòng)作空間A。在智能體中每一個(gè)數(shù)據(jù)包是一個(gè)智能體，它的職責(zé)是在每個(gè)離散狀態(tài)下通過執(zhí)行不同的動(dòng)作以獲得不同的獎(jiǎng)勵(lì)，以尋求到達(dá)目的節(jié)點(diǎn)的最優(yōu)策略。

定義2（獎(jiǎng)勵(lì)值）根據(jù)定義1，智能體每執(zhí)行一次動(dòng)作所獲得的獎(jiǎng)勵(lì)被稱為即時(shí)獎(jiǎng)勵(lì)，用R表示，取值范圍為[0，1]。

僅當(dāng)下一跳車輛是目的車輛的簇頭車輛或網(wǎng)關(guān)車輛時(shí)，獲得的獎(jiǎng)勵(lì)值等于1，其余情況的即時(shí)獎(jiǎng)勵(lì)均為0。獎(jiǎng)勵(lì)值形式化表示如式（3）所示：

其中：Vj表示當(dāng)前簇頭車輛Vi的鄰居簇頭或網(wǎng)關(guān)車輛；表示目的車輛Vk所在簇的簇頭或網(wǎng)關(guān)車輛的鄰居列表。

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

Q 學(xué)習(xí)過程主要是更新節(jié)點(diǎn)維護(hù)的Q 表結(jié)構(gòu)，同時(shí)更新Q 表中的狀態(tài)行為值，Q 學(xué)習(xí)的形式化如式（4）所示：

3.1 基于鏈路持續(xù)時(shí)間的學(xué)習(xí)率

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

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

1）如果ai(0)=0，對(duì)于任意t≥0 滿足ai(t)=0，表示車輛i在t≥0 時(shí)始終做勻速直線運(yùn)動(dòng)。

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

根據(jù)情況2，只要車輛沒有達(dá)到最大限速或者停止，則車輛i的加速度仍然是ai(0)。當(dāng)車輛達(dá)到最大限速vmax或者速度減為0 時(shí)，加速度會(huì)變?yōu)?，即車輛達(dá)到最大限速vmax后做勻速直線運(yùn)動(dòng)，或者車輛速度減為0 之后車輛處于靜止?fàn)顟B(tài)。

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

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

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

車輛i在t時(shí)間段內(nèi)行駛的距離如式（9）所示：

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

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

兩輛車在T時(shí)間段內(nèi)的距離差如式（10）和式（11）所示：

當(dāng)車輛Vj在車輛Vi之前，兩者距離差為R，當(dāng)車輛Vi在車輛Vj之前，兩者距離差為-R。

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

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

3.2 折扣率

車輛在選擇下一跳節(jié)點(diǎn)時(shí)，應(yīng)避開選擇距離當(dāng)前車輛節(jié)點(diǎn)較遠(yuǎn)的車輛節(jié)點(diǎn)，將選擇距離較遠(yuǎn)的鄰居車輛作為下一跳中繼車輛，增加了鏈路的不穩(wěn)定性。因此，車輛i與鄰居車輛的距離因子如式（15）所示：

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

3.3 改進(jìn)的Q 學(xué)習(xí)算法

改進(jìn)的Q 學(xué)習(xí)算法如式（16）所示：

傳統(tǒng)的Q 學(xué)習(xí)算法選取鄰居列表中Q值最大的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。因車輛行駛軌跡的隨機(jī)性，會(huì)造成鏈路拓?fù)浣Y(jié)構(gòu)的改變。由于鏈路通信狀況具有不確定性，因此按照最大Q值選擇下一跳的方式并不一定是最優(yōu)的。當(dāng)前車輛Vi在選擇下一跳鄰居簇頭或網(wǎng)關(guān)時(shí)，本文引入節(jié)點(diǎn)性能評(píng)估函數(shù)，有效緩解只按照最大Q值的方式選擇下一跳節(jié)點(diǎn)造成“盲路”問題。實(shí)時(shí)計(jì)算的性能評(píng)估函數(shù)值還可以起到對(duì)選擇的下一跳節(jié)點(diǎn)進(jìn)行修正的作用，確保選擇的下一跳節(jié)點(diǎn)能夠及時(shí)適應(yīng)網(wǎng)絡(luò)環(huán)境的改變。本文對(duì)式（16）進(jìn)一步修改，改進(jìn)后的Q 學(xué)習(xí)算法如式（17）所示：

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

其中：argmaxQj(j′，k)表示按照傳統(tǒng)Q 學(xué)習(xí)算法中最大Q值的方式選出Q 表中到達(dá)目的節(jié)點(diǎn)對(duì)應(yīng)的鄰居節(jié)點(diǎn)j'；argmaxFj(j″，k)表示從性能評(píng)估函數(shù)的角度選出鄰居車輛j''。，根據(jù)式（18）得到的車輛j'和車輛j''完成對(duì)Wj(m，k)最終的賦值，如式（19）所示：

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

4 RCRIQ 路由算法

分簇機(jī)制能夠有效解決大規(guī)模網(wǎng)絡(luò)中數(shù)據(jù)傳輸效率較低的問題。Q 學(xué)習(xí)作為一種自學(xué)習(xí)算法，通過與周圍環(huán)境的不斷交互來達(dá)到適應(yīng)復(fù)雜多變外部環(huán)境目的。因此，將Q 學(xué)習(xí)算法運(yùn)用到復(fù)雜多變的VANETs 環(huán)境是合適的。但是，Q 學(xué)習(xí)采用最大值查找最優(yōu)路徑的方式，容易產(chǎn)生“盲路”問題。在數(shù)據(jù)包路由階段，本文給出節(jié)點(diǎn)性能評(píng)估函數(shù)對(duì)下一跳車輛的綜合性能進(jìn)行評(píng)估，路由過程按照Q學(xué)習(xí)算法和節(jié)點(diǎn)性能評(píng)估函數(shù)兩種策略選擇下一跳車輛。

4.1 節(jié)點(diǎn)性能評(píng)估函數(shù)

當(dāng)車輛Vi選擇到達(dá)目的車輛Vk的下一跳中繼節(jié)點(diǎn)Vj時(shí)，Vi需要對(duì)下一跳車輛Vj的選擇方法進(jìn)行量化評(píng)估。從鏈路通信質(zhì)量因子、方向因子和移動(dòng)因子3 個(gè)角度衡量車輛Vi和Vj之間鏈路的綜合性能。

4.1.1 鏈路通信質(zhì)量因子

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

當(dāng)收到鄰居車輛發(fā)送的HELLO 報(bào)文時(shí)，車輛從中提取鄰居車輛的qlink值。qlink值越大，表明鏈路通信質(zhì)量越好，選擇qlink值較大的鄰居車輛，可以提高鏈路的穩(wěn)定性，提高傳輸效率。

4.1.2 方向因子

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

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

4.1.3 移動(dòng)因子

移動(dòng)因子可以量化下一跳車輛移動(dòng)性對(duì)路由鏈路穩(wěn)定性的影響。車輛的移動(dòng)性會(huì)對(duì)相鄰兩輛車之間的鏈路產(chǎn)生影響，選擇穩(wěn)定性更好的鏈路，更有利于數(shù)據(jù)包的傳輸。本文以當(dāng)前車輛Vi和Vj為例，移動(dòng)因子形式化表示如式（22）～式（27）所示：

其中：為預(yù)先給定的移動(dòng)性閾值，當(dāng)車輛Vi和車輛Vj之間的移動(dòng)性小于該閾值時(shí)，給移動(dòng)因子賦值為1，表示從移動(dòng)性角度選擇對(duì)應(yīng)的下一跳鄰居車輛作為中繼車輛，否則賦值為-1。

根據(jù)鏈路通信質(zhì)量因子、方向因子、移動(dòng)因子定義節(jié)點(diǎn)性能評(píng)估函數(shù)，用于評(píng)估下一跳車輛Vj的綜合性能。節(jié)點(diǎn)性能評(píng)估函數(shù)如式（28）所示：

其中：Fi(j，k)表示當(dāng)前車輛節(jié)點(diǎn)i選擇鄰居節(jié)點(diǎn)j作為到達(dá)目的車輛節(jié)點(diǎn)k的下一跳節(jié)點(diǎn)時(shí)，對(duì)應(yīng)的節(jié)點(diǎn)性能評(píng)估函數(shù)值。當(dāng)取值都為1 時(shí)，的取值為1，對(duì)最終的函數(shù)值形成正反饋，否則方向因子或移動(dòng)因子中只要一個(gè)取值為-1，最終Fi(j，k)值為0，將最終求得F值最大的節(jié)點(diǎn)作為候選中繼節(jié)點(diǎn)。

4.2 路由建立過程

當(dāng)源節(jié)點(diǎn)發(fā)送數(shù)據(jù)包時(shí)，由所在簇的簇頭代為轉(zhuǎn)發(fā)。簇頭車輛首先檢查Q 表以查看是否有到目的節(jié)點(diǎn)的下一跳車輛，若存在，則啟動(dòng)數(shù)據(jù)傳輸過程。路由轉(zhuǎn)發(fā)策略流程如圖4 所示。

圖4 路由轉(zhuǎn)發(fā)策略流程Fig.4 Procedure of routing forwarding strategy

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

路由轉(zhuǎn)發(fā)策略的偽代碼如下：

車輛V4選擇鄰居車輛V7作為到達(dá)目的車輛Vd的中繼車輛對(duì)應(yīng)的Q值為0.6，選擇鄰居車輛V6作為到達(dá)目的車輛Vd的中繼車輛對(duì)應(yīng)的Q值為0.52，其中學(xué)習(xí)率取值為0.8，折扣率取值為0.7。數(shù)據(jù)包傳輸路徑示意圖如圖5 所示。

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

如果按照最大Q值的方式選擇下一跳車輛，則最終的數(shù)據(jù)包傳輸路徑為Vs→V2→V4→V6→V9→V11→Vd或Vs→V1→V4→V6→V9→V11→Vd。因?yàn)楣?jié)點(diǎn)性能評(píng)估函數(shù)綜合考慮了下一跳車輛的通信性能，所以在選擇下一跳車輛時(shí)會(huì)根據(jù)實(shí)際鏈路質(zhì)量、數(shù)據(jù)包傳輸方向和兩輛車之間的移動(dòng)性進(jìn)行綜合分析。例如，當(dāng)車輛V1選擇下一跳車輛時(shí)，按照最大Q值的方式應(yīng)選擇網(wǎng)關(guān)車輛節(jié)點(diǎn)V4。然而，因?yàn)閂4車輛作為另一個(gè)簇的網(wǎng)關(guān)車輛，與當(dāng)前簇的相對(duì)速度和簇內(nèi)的網(wǎng)關(guān)車輛V3相比，V3車輛更穩(wěn)定，即按照節(jié)點(diǎn)性能評(píng)估函數(shù)值最大的方式選出的下一跳車輛是V3，綜合考慮選擇V3作為下一跳車輛。兩種策略綜合評(píng)估的機(jī)制在確保Q值最大和最優(yōu)可達(dá)性的同時(shí)，使得其他運(yùn)動(dòng)特征和通信方面的參數(shù)也是最優(yōu)的，實(shí)現(xiàn)數(shù)據(jù)高效傳輸?shù)哪康摹?/p>

4.3 路由維護(hù)階段

當(dāng)數(shù)據(jù)包在路由鏈路中丟失時(shí)，傳統(tǒng)路由協(xié)議會(huì)從源車輛重新將數(shù)據(jù)包發(fā)送到目標(biāo)車輛［18-19］，或者切換到第2 條備用路由［20］，繼續(xù)發(fā)送數(shù)據(jù)包，這2 種方式具有較高的路由開銷。本文采用的策略如下：若車輛與下一跳車輛之間的鏈路斷連，則會(huì)通過Q 表結(jié)構(gòu)的維護(hù)，刪除Q 表中失效車輛的記錄，即刪除鄰居車輛對(duì)應(yīng)的行。如果Q 表中到達(dá)目的節(jié)點(diǎn)的Q值在指定的時(shí)間內(nèi)沒有更新，則視為目的節(jié)點(diǎn)已失效，將刪除Q 表中該目的車輛對(duì)應(yīng)的列數(shù)據(jù)。因?yàn)镼 表的結(jié)構(gòu)和Q值，體現(xiàn)了網(wǎng)絡(luò)的狀況。因此，通過Q值的不斷迭代更新和Q 表結(jié)構(gòu)的不斷維護(hù)，使得RCRIQ 能夠?qū)崟r(shí)適應(yīng)網(wǎng)絡(luò)環(huán)境的改變。

5 仿真結(jié)果

本文采用GAPC［21］中的分簇算法構(gòu)建簇結(jié)構(gòu)，在此基礎(chǔ)上，RCRIQ 分別與GPSR、RSAR、TCRA 算法從路由跳數(shù)、鏈路持續(xù)時(shí)間、吞吐量、丟包率、通信延遲等角度進(jìn)行仿真實(shí)驗(yàn)。為了確保仿真的真實(shí)性和有效性，本文采用德國(guó)科?。?2］和國(guó)內(nèi)某市［23］移動(dòng)數(shù)據(jù)集作為車輛移動(dòng)數(shù)據(jù)集，根據(jù)節(jié)點(diǎn)數(shù)的不同，分別進(jìn)行40、60、80、100、120、140、160、180、200 個(gè)車輛節(jié)點(diǎn)的仿真實(shí)驗(yàn)。本文實(shí)驗(yàn)的仿真參數(shù)設(shè)置如表1 所示。

表1 本文實(shí)驗(yàn)的仿真參數(shù)設(shè)置Table 1 Simulation parameters settings of experiment in this paper

5.1 路由跳數(shù)對(duì)比

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

圖6 不同路由算法的路由跳數(shù)對(duì)比Fig.6 Routing hops comparison among different routing algorithms

5.2 路由生存時(shí)間對(duì)比

路由生存時(shí)間表示從源節(jié)點(diǎn)到目的節(jié)點(diǎn)之間通信鏈路的存活時(shí)間。本文根據(jù)路由生存時(shí)間的變化情況來衡量通信鏈路的穩(wěn)定性。在不同車輛節(jié)點(diǎn)下，各路由算法的路由生存時(shí)間對(duì)比如圖7 所示。隨著車輛節(jié)點(diǎn)數(shù)目的增多，在2 個(gè)數(shù)據(jù)集上4 種算法的路由生存時(shí)間均增加，這是因?yàn)殡S著節(jié)點(diǎn)數(shù)的增加，鄰居列表中選擇通信狀況且穩(wěn)定性較優(yōu)的下一跳節(jié)點(diǎn)的可能性增加，以確保4 種路由算法的生存時(shí)間均增加。在2 個(gè)不同的移動(dòng)數(shù)據(jù)集下，RCRIQ算法的路由生存時(shí)間分別比RSAR、GPSR 和TCRA平均提高13.49%、23.41%和16.33%。路由生存時(shí)間的提升是因?yàn)镽CRIQ 的節(jié)點(diǎn)性能評(píng)估函數(shù)充分考慮了鏈路通信質(zhì)量、數(shù)據(jù)包傳輸方向、車輛之間移動(dòng)性對(duì)通信鏈路的影響，而RSAR 僅考慮了速度變化對(duì)通信鏈路穩(wěn)定性的影響。GPSR 的路由生存時(shí)間最低是因?yàn)樗捎秘澙窓C(jī)制，沒有考慮鏈路穩(wěn)定性和網(wǎng)絡(luò)負(fù)載情況對(duì)路由生存時(shí)間的影響。TCRA 路由生存時(shí)間較短的原因是基于AODV 協(xié)議，需要不斷對(duì)路由進(jìn)行維護(hù)，不能很好適應(yīng)VANETs 環(huán)境。

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

5.3 吞吐量對(duì)比

吞吐量表示目的車輛在一定時(shí)間內(nèi)接收有效數(shù)據(jù)包的總字節(jié)數(shù)與時(shí)間間隔的比值［24］。在不同車輛節(jié)點(diǎn)下，不同路由算法的吞吐量對(duì)比如圖8 所示。隨著車輛節(jié)點(diǎn)規(guī)模的不斷增大，在2 個(gè)數(shù)據(jù)集中4 種路由算法的吞吐量均增大。RCRIQ 的平均吞吐量分別比RSAR、GPSR 和TCRA 提高28.76%、52.97%、15.96%。RCRIQ充分考慮影響鏈路穩(wěn)定性的因素，同時(shí)還將相鄰車輛的鏈路持續(xù)時(shí)間和距離定量化表示成Q 學(xué)習(xí)中的學(xué)習(xí)率和折扣率。鏈路持續(xù)時(shí)間長(zhǎng)和距離近的鄰居節(jié)點(diǎn)能夠獲得更大的Q值，便于后續(xù)數(shù)據(jù)傳輸階段按照最大Q值策略查找下一跳車輛。相反，在RSAR 數(shù)據(jù)傳輸階段，只按照最大Q值查找下一跳節(jié)點(diǎn)，因車輛具有移動(dòng)性，容易產(chǎn)生“盲路”問題，最終影響數(shù)據(jù)包的傳輸。GPSR 的吞吐量最低是因?yàn)槠錄]有重傳機(jī)制，當(dāng)采用貪婪機(jī)制未能成功選出下一跳節(jié)點(diǎn)時(shí)，會(huì)直接丟棄該數(shù)據(jù)包，造成有效傳輸?shù)侥康墓?jié)點(diǎn)的數(shù)據(jù)包偏少。TCRA 吞吐量較高是因?yàn)榉执乜梢詫?duì)網(wǎng)絡(luò)頻譜進(jìn)行高效管理，減少網(wǎng)絡(luò)擁塞的出現(xiàn)，極大提高單位時(shí)間內(nèi)的數(shù)據(jù)傳輸率。

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

5.4 丟包率對(duì)比

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

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

5.5 時(shí)延對(duì)比

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

圖10 不同路由算法的時(shí)延對(duì)比Fig.10 Time delay comparison among different routing algorithms

6 結(jié)束語

傳統(tǒng)VANETs 路由算法存在路由維護(hù)成本和通信延遲較高且吞吐量較低的問題。為此，本文提出基于分簇和改進(jìn)Q 學(xué)習(xí)的復(fù)合路由算法，采用節(jié)點(diǎn)性能評(píng)估函數(shù)和最大Q值兩種方式對(duì)待選的下一跳節(jié)點(diǎn)進(jìn)行綜合評(píng)估。在德國(guó)科隆數(shù)據(jù)集和國(guó)內(nèi)某市移動(dòng)數(shù)據(jù)集上的仿真實(shí)驗(yàn)結(jié)果表明，相比RSAR、GPSR 和TCRA 路由算法，RCRIQ 能提高數(shù)據(jù)包 傳輸率并延長(zhǎng)鏈路存活時(shí)間，且降低傳輸延遲和丟包率，有效緩解由VANETs 網(wǎng)路拓?fù)漕l繁變化帶來的問題。由于LTE 具有高帶寬和覆蓋范圍大的特點(diǎn)，因此下一步將結(jié)合LTE 與專用短程通信構(gòu)建混合分簇網(wǎng)絡(luò)模型，以提高大數(shù)據(jù)包的傳輸效率。