3D-VANET中基于模糊邏輯和Q學習的拓撲感知路由協(xié)議*

鄭澤濤，何榮希，周 宇

(大連海事大學 信息科學技術(shù)學院，遼寧 大連 116026)

0 引 言

隨著汽車保有量不斷增長，為提高人們出行的高效性與安全性，智能交通系統(tǒng)(Intelligent Transport System，ITS)應(yīng)運而生。車載自組網(wǎng)(Vehicular Ad-hoc Network，VANET)由車輛與路邊單元(Road Side Unit，RSU)組成，是實現(xiàn)ITS數(shù)據(jù)可靠交互的關(guān)鍵支撐技術(shù)。車輛的快速運動，導致VANET拓撲變化頻繁，通信鏈路更易中斷。由于拓撲路由協(xié)議在傳輸數(shù)據(jù)包前需建立完整路徑，因此在VANET中性能較差[1]。與之不同，地理位置路由協(xié)議不需預先建立路徑，節(jié)點可根據(jù)本地信息進行路由轉(zhuǎn)發(fā)，在VANET中具有較好的性能，已引起業(yè)界極大關(guān)注。

貪婪周邊無狀態(tài)路由協(xié)議(Greedy Perimeter Stateless Routing，GPSR)[1]是經(jīng)典的位置路由協(xié)議，通過選擇距離目的節(jié)點最近的鄰節(jié)點進行數(shù)據(jù)轉(zhuǎn)發(fā)。文獻[2-4]中的位置路由協(xié)議都是針對城市二維場景設(shè)計，也稱為平面路由協(xié)議。伴隨著城市現(xiàn)代化建設(shè)的不斷推進，越來越多地涌現(xiàn)高架橋、立交橋等立體式交通格局。在上述多層道路場景中，由于道路遮擋造成信號衰減，不同層間車輛的傳輸半徑各異，同時不同層的車輛間運動狀態(tài)差異也較大。而已有平面路由協(xié)議并未涉及跨層間節(jié)點傳輸問題，不宜直接用于立體交通場景[5]，因此，很有必要針對網(wǎng)絡(luò)拓撲變化更頻繁的三維場景VANET(3D-VANET)特點，重新設(shè)計位置路由協(xié)議。

由于城市3D-VANET中往往包含多種道路場景，每種道路場景的網(wǎng)絡(luò)拓撲都具有不同的特點，不同道路場景之間節(jié)點分布和運動差異較大。3D-VANET中應(yīng)依據(jù)道路場景自適應(yīng)調(diào)整信標間隔。

本文針對城市三維場景提出了一種基于模糊邏輯和Q學習的拓撲感知路由協(xié)議(Topology Aware Routing Protocol Based on Fuzzy Logic and Q-learning，TARP-FQ)。該協(xié)議采用模糊邏輯方法綜合考慮網(wǎng)絡(luò)拓撲與負載信息判斷網(wǎng)絡(luò)情況，動態(tài)地調(diào)整信標間隔，以平衡鄰節(jié)點信息準確性與控制開銷成本，提高后續(xù)路由決策的正確性和有效性。在此基礎(chǔ)上，采用Q學習算法對VANET網(wǎng)絡(luò)進行建模，通過獲取的本地信息計算鏈路質(zhì)量以及鏈路質(zhì)量變化，根據(jù)節(jié)點間的拓撲變化調(diào)整Q學習參數(shù)，并結(jié)合未來獎勵函數(shù)靈活選擇下一跳轉(zhuǎn)發(fā)節(jié)點，保證轉(zhuǎn)發(fā)鏈路的可靠性，避免局部最優(yōu)問題的發(fā)生。

1 網(wǎng)絡(luò)模型

與已有研究[6-8]僅針對單一場景進行路由設(shè)計不同，本文所構(gòu)建的城市三維場景由單層道路、高架道路、立交橋等多種道路構(gòu)成。假設(shè)車輛隨機分布在道路上，按照交通規(guī)則沿道路行進，而且每種道路上車輛的分布和運動狀態(tài)呈現(xiàn)不同特點。由于多層道路的存在，車輛擁有兩種數(shù)據(jù)包轉(zhuǎn)發(fā)模式，分別為層內(nèi)轉(zhuǎn)發(fā)模式和層間轉(zhuǎn)發(fā)模式[9]。層內(nèi)轉(zhuǎn)發(fā)指發(fā)送數(shù)據(jù)包和接收數(shù)據(jù)包的車輛位于同層道路，而層間轉(zhuǎn)發(fā)是指位于不同層道路的車輛進行數(shù)據(jù)包的收發(fā)。由于多層道路之間存在遮擋造成信號衰減，層內(nèi)轉(zhuǎn)發(fā)模式的傳輸距離r要大于層間轉(zhuǎn)發(fā)模式的傳輸距離r′。所有車輛均配備GPS設(shè)備獲取自身實時位置信息，裝配有符合IEEE 802.11p車聯(lián)網(wǎng)無線接入標準的車載單元設(shè)備(On Board Unit，OBU)進行數(shù)據(jù)包傳輸。網(wǎng)絡(luò)中每個節(jié)點通過周期性交換HELLO包獲取鄰節(jié)點信息，并且可以判斷其所在的道路。每個交叉路口配備與車輛具有相同通信能力的RSU，每輛車以及RSU均有唯一標識。

2 TARP-FQ協(xié)議描述

TARP-FQ主要由基于模糊邏輯的動態(tài)信標間隔調(diào)整和基于Q學習的路由選擇兩個模塊組成。動態(tài)信標間隔調(diào)整模塊根據(jù)收集的節(jié)點速度、方向、鄰節(jié)點數(shù)和網(wǎng)絡(luò)負載信息，通過模糊邏輯處理數(shù)據(jù)，感知網(wǎng)絡(luò)拓撲變化情況與網(wǎng)絡(luò)狀態(tài)，進而選擇合適的信標間隔，為路由選擇提供準確的鄰節(jié)點信息和良好的網(wǎng)絡(luò)環(huán)境。路由選擇模塊根據(jù)鏈路質(zhì)量和節(jié)點間拓撲變化情況作出最佳路由決策，并完成數(shù)據(jù)包轉(zhuǎn)發(fā)。當車輛攜帶數(shù)據(jù)包時，選擇抵達臨時目的節(jié)點最大Q值車輛進行轉(zhuǎn)發(fā)。當車輛產(chǎn)生新的數(shù)據(jù)需要發(fā)送或數(shù)據(jù)包轉(zhuǎn)發(fā)至RSU時，結(jié)合Q值和RSU信息選取下一個臨時目的節(jié)點，并繼續(xù)通過Q值選擇節(jié)點進行轉(zhuǎn)發(fā)。

2.1 基于模糊邏輯的動態(tài)信標間隔調(diào)整

2.1.1 動態(tài)信標間隔

位置路由協(xié)議進行路由決策的基礎(chǔ)是鄰節(jié)點列表的準確性，但是拓撲結(jié)構(gòu)的頻繁變化將導致鄰節(jié)點狀態(tài)信息經(jīng)常發(fā)生改變。節(jié)點間周期性交換信標消息是維護鄰節(jié)點信息的常用方法，VANET采用HELLO包作為信標消息進行交互，節(jié)點通過HELLO包獲取需要的鄰節(jié)點信息。

平面場景中由于道路限制與相互約束，車輛之間運動差異較小，采用固定信標間隔策略即可滿足網(wǎng)絡(luò)的需求。而在城市三維場景中，不同道路中的網(wǎng)絡(luò)拓撲變化情況截然不同，采用較大的固定信標間隔無法保證拓撲快速變化時鄰節(jié)點列表的準確性，而采用較小的固定信標間隔，由于無線鏈路資源有限，當網(wǎng)絡(luò)中存在大量HELLO包時會增加與用戶數(shù)據(jù)包碰撞的概率，造成數(shù)據(jù)包丟失。因此在城市三維場景中采用固定信標間隔策略會存在一些問題，下面以圖1為例加以說明。圖中車輛A、B位于S3道路的同向車道，C位于A、B的反向車道，D位于環(huán)形高架S4道路，E和F位于單向S1道路，其中A、E有數(shù)據(jù)包將要發(fā)送。圖1分別給出了t0、t1時刻的情況。

圖1 信標間隔大小對鄰節(jié)點信息準確性的影響

(1)假設(shè)t0時刻所有車輛第一次廣播HELLO包，當選取較小的固定信標間隔t2-t0時，可以捕獲C、D即將離開A通信范圍的信息，進而降低其轉(zhuǎn)發(fā)權(quán)重，而當選取較大的固定信標間隔t3-t0時，實際上t3時刻C、D已離開A通信范圍，但仍作為潛在的下一跳轉(zhuǎn)發(fā)節(jié)點存在于A的鄰節(jié)點列表中，不能精準捕獲網(wǎng)絡(luò)拓撲的變化，會導致次優(yōu)甚至錯誤的路由決策。

(2)在S1道路中，受道路和車輛間的相互約束，網(wǎng)絡(luò)拓撲變化較慢，此時較長的固定信標間隔即可保證E鄰節(jié)點信息的有效性。如果選擇較短的固定信標間隔，則會引入較大的網(wǎng)絡(luò)開銷，浪費信道資源。

可見3D-VANET中采用固定信標間隔策略無法滿足高性能路由需求，因此本節(jié)設(shè)計了動態(tài)信標間隔調(diào)整策略，引入模糊邏輯方法，可根據(jù)局部網(wǎng)絡(luò)拓撲變化以及網(wǎng)絡(luò)負載情況動態(tài)調(diào)整信標間隔。

由于3D-VANET是一種動態(tài)變化的網(wǎng)絡(luò)，很難通過具體的數(shù)學公式來描述網(wǎng)絡(luò)的變化情況，而模糊邏輯作為一種類似于人類推理的方法，采用非數(shù)字語言變量進行描述，可以更精確、動態(tài)地自適應(yīng)優(yōu)化參數(shù)，因此本節(jié)通過模糊邏輯方法處理不精確的信息，改善決策，提高性能。模糊邏輯一般包括三個步驟：模糊化輸入、模糊化處理和解模糊。輸入步驟將數(shù)值轉(zhuǎn)化為模糊語言，采用IF/THEN的模糊規(guī)則對其進行處理，最后通過解模糊以數(shù)值形式輸出。

2.1.2 模糊化輸入與處理

TARP-FQ的模糊化輸入考慮4個評價指標，即速度標準差、行進方向數(shù)、鄰節(jié)點數(shù)量變化率和網(wǎng)絡(luò)負載得分。速度標準差和行進方向數(shù)可以反映出車輛運動狀態(tài)的差異，鄰節(jié)點數(shù)量變化率則可以看出當前信標間隔是否可以準確捕獲網(wǎng)絡(luò)拓撲的變化，最后根據(jù)當前網(wǎng)絡(luò)負載情況衡量可接受的網(wǎng)絡(luò)開銷，當網(wǎng)絡(luò)負載較大時增大信標間隔以減輕網(wǎng)絡(luò)負載壓力，實現(xiàn)信息準確與網(wǎng)絡(luò)開銷之間的平衡。

當節(jié)點啟動HELLO包廣播機制時，首先通過模糊邏輯方法處理節(jié)點速度標準差、行進方向數(shù)、鄰節(jié)點數(shù)量變化率、網(wǎng)絡(luò)負載得分4個參數(shù)以確定信標間隔，并將計算出的下一次發(fā)送時間寫入即將發(fā)送的HELLO包中。

(1)速度標準差

在平面場景中，位于相同道路的車輛，其運動相互影響，相對速度往往較小，網(wǎng)絡(luò)拓撲較為穩(wěn)定。在三維場景中VANET具有層間轉(zhuǎn)發(fā)模式，因此還需要考慮當前層道路之外的車輛。由于不同道路中交通燈設(shè)置、車流量大小等因素不同，跨層車輛之間相對速度較大，網(wǎng)絡(luò)拓撲變化較快，為反映車輛之間運動速度的差異性，采用速度標準差來衡量相對移動性大小。網(wǎng)絡(luò)中車輛速度標準差Sc定義為

(1)

(2)行進方向數(shù)

在平面場景路由協(xié)議的研究中，相鄰車輛僅沿著道路雙向運動，而在城市三維場景中由于高架、立交橋等道路形式的存在，相鄰車輛可能存在多個行進方向。當相鄰車輛行進方向越多時，網(wǎng)絡(luò)拓撲的變化將越頻繁。為便于計算，定義8個車輛行進方向，如圖2所示。圖中c為車輛當前位置，cc′為當前車輛的行進方向。

圖2 節(jié)點行進方向

節(jié)點的鄰節(jié)點列表中車輛節(jié)點行進方向數(shù)dirnum計算如下：

(2)

當鄰節(jié)點列表中有節(jié)點行進方向為diri時，將diri值置1，否則為0。

(3)鄰節(jié)點數(shù)量變化率

在平面場景中，網(wǎng)絡(luò)較為穩(wěn)定，車輛鄰節(jié)點列表變動較小，而在三維場景中，除單層道路外，還包含多種道路結(jié)構(gòu)，不同的道路中網(wǎng)絡(luò)拓撲變化情況截然不同。因此引入鄰節(jié)點數(shù)量變化率來表示當前信標間隔捕獲拓撲變化的能力。鄰節(jié)點數(shù)量變化率Nio定義為

(3)

式中：Nneighbour為鄰節(jié)點列表中當前鄰節(jié)點數(shù),Nin和Nout分別為一個信標間隔時間內(nèi)新增節(jié)點數(shù)和離開節(jié)點數(shù)。當鄰節(jié)點數(shù)量變化率較大時，說明當前信標間隔設(shè)置過長，不能及時捕獲網(wǎng)絡(luò)拓撲的變化；反之則說明當前網(wǎng)絡(luò)較為穩(wěn)定，可以適當增大信標間隔以減少網(wǎng)絡(luò)開銷。

(4)網(wǎng)絡(luò)負載得分

大量HELLO包的廣播會增大網(wǎng)絡(luò)負載，導致無線共享信道更加擁塞，降低了數(shù)據(jù)包傳輸效率。因此在網(wǎng)絡(luò)負載較重時，可以通過增大信標間隔來減少節(jié)點廣播HELLO包的數(shù)量。為此，引入平均負載得分Laverage來衡量網(wǎng)絡(luò)負載狀態(tài)，其定義為

(4)

式中：n為當前車輛鄰節(jié)點數(shù)，Lscore-i為通過式(16)計算得到節(jié)點i的負載得分，i=0表示當前車輛節(jié)點。

在模糊化過程中，需要借助模糊隸屬函數(shù)對輸入因子進行處理。模糊隸屬函數(shù)是一種用于表征模糊集合的數(shù)學工具，可以利用模糊集合根據(jù)實際網(wǎng)絡(luò)情況對指標間的相似程度進行度量。利用模糊集定義四個指標：速度標準差Sc{小、中、大}、行進方向數(shù)dirnum{少、多}、鄰節(jié)點數(shù)量變化率Nio{低、中、高}和網(wǎng)絡(luò)負載得分Laverage{低、中、高}。隸屬函數(shù)采用三角形函數(shù)和梯形函數(shù)，如圖3所示。

圖3 模糊邏輯輸入?yún)?shù)隸屬函數(shù)

2.1.3 解模糊輸出信標間隔

對輸入因子進行模糊處理之后，需要根據(jù)模糊邏輯準則使用IF/THEN規(guī)則進行模糊邏輯推理，TARP-FQ的模糊邏輯部分準則如表1所示，其中模糊評價分為{很長、長、較長、中等偏長、中等偏短、較短、短、很短}8個等級。

表1 模糊邏輯部分準則示例

以表1中第一條規(guī)則為例，IF車輛速度標準差大，行進方向數(shù)多，鄰節(jié)點變化率高，網(wǎng)絡(luò)負載得分高，THEN采用很短的信標間隔。為得到確切的解模糊輸出值，需要利用輸出隸屬函數(shù)對得到的若干模糊評價進行轉(zhuǎn)換，TARP-FQ采用的輸出隸屬函數(shù)如圖4所示，使用重心法求出解模糊的輸出值。定義得到的輸出值為信標間隔因子σbeacon，由式(5)計算得出信標間隔大小ΔtB。

圖4 模糊邏輯輸出隸屬函數(shù)

ΔtB=Δtmax-(Δtmax-Δtmin)×σbeacon。

(5)

式中:Δtmax、Δtmin分別表示網(wǎng)絡(luò)內(nèi)設(shè)置的最大信標間隔和最小信標間隔。

2.2 基于Q學習的路由選擇

2.2.1 Q學習算法建模

學習環(huán)境G：整個網(wǎng)絡(luò)作為智能體的學習環(huán)境。

主體智能體Agent：傳輸數(shù)據(jù)包的節(jié)點。

狀態(tài)空間S：除當前智能體節(jié)點之外的所有節(jié)點組成狀態(tài)空間。

瞬時獎勵R：當前智能體節(jié)點通過一次動作從環(huán)境中獲得的瞬時獎勵。

動作Actions：選擇一個鄰節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包。

網(wǎng)絡(luò)中車輛之間通過HELLO包交互狀態(tài)信息，在每一個狀態(tài)和可能的動作之間建立一張Q值表，維護每一個“狀態(tài)-動作”對的評價值——Q值，實現(xiàn)智能體節(jié)點在環(huán)境中不斷地試錯并調(diào)整最優(yōu)動作。Q值表記錄著當前節(jié)點通過鄰節(jié)點抵達所維護目的節(jié)點的Q值大小。

根據(jù)文獻[10]可將Q學習算法更新公式表示為

(6)

式中：c為當前節(jié)點，x為c的鄰節(jié)點，d為目的節(jié)點，N(x)為x鄰節(jié)點的集合，y為x鄰節(jié)點集中的一個節(jié)點，α(0<α<1)為學習率，γ(0<γ<1)表示折扣因子。車輛在轉(zhuǎn)發(fā)數(shù)據(jù)包時將每個相鄰的RSU作為候選的臨時目的節(jié)點，因此Q值表中維護的是通過鄰節(jié)點抵達每個相鄰RSU的Q值大小。

2.2.2 Q學習參數(shù)設(shè)計

本小節(jié)根據(jù)VANET中鏈路質(zhì)量、鏈路質(zhì)量變化以及是否可以抵達目的節(jié)點三個方面對Q學習算法中參數(shù)進行設(shè)計。

當前節(jié)點接收到鄰節(jié)點的HELLO包時，首先計算折扣因子γ，其值為

γ=γpreγscore。

(7)

式中：γpre為預設(shè)常數(shù)(0<γpre<1)，根據(jù)多次仿真實驗，將γpre設(shè)置為0.85；γscore表示鏈路質(zhì)量得分，通過可替代度、鏈路維持時間和鄰節(jié)點負載狀態(tài)來衡量節(jié)點間傳輸數(shù)據(jù)包的可靠性。在選擇下一跳節(jié)點進行轉(zhuǎn)發(fā)時，要盡量避免選擇可替代度低、即將離開通信范圍或者負載過大的節(jié)點。本節(jié)采用調(diào)和平均數(shù)計算鏈路質(zhì)量，調(diào)和平均數(shù)相較于算數(shù)平均數(shù)可以更靈敏地反映較小值的影響，避免某個網(wǎng)絡(luò)參數(shù)過差而產(chǎn)生的瓶頸效應(yīng)。γscore的計算公式為

(8)

式中：AL、SLET和Lscore分別代表可替代度、鏈路維持時間得分和鄰節(jié)點負載得分。

(1)可替代度

在數(shù)據(jù)包轉(zhuǎn)發(fā)過程中，如果當前鏈路失效，則需要由備用鏈路對數(shù)據(jù)進行轉(zhuǎn)發(fā)。因此，有效的候選鏈路數(shù)量是影響鏈路穩(wěn)定性的重要因素之一。在三維場景中，由于跨層傳輸半徑減小以及鄰節(jié)點所處道路的不同，擁有的候選鏈路也會隨著所選擇轉(zhuǎn)發(fā)節(jié)點的改變而改變。為此，本節(jié)引入有效候選節(jié)點與可替代度兩個概念。

有效候選節(jié)點定義為所選擇轉(zhuǎn)發(fā)節(jié)點的鄰節(jié)點列表中可以進一步抵達目標RSU的節(jié)點?？商娲葎t表示擁有的有效候選節(jié)點數(shù)量可以確保數(shù)據(jù)轉(zhuǎn)發(fā)可靠性的程度，定義為

(9)

式中：N表示所選擇轉(zhuǎn)發(fā)節(jié)點的鄰節(jié)點數(shù)；當節(jié)點j為有效候選節(jié)點時，ali=1，否則為0；h為常數(shù)，根據(jù)多次仿真設(shè)置為3，即當有3個及以上有效候選節(jié)點時有充足的候選鏈路用于數(shù)據(jù)轉(zhuǎn)發(fā)。

(2)鏈路維持時間

基于距離貪婪的轉(zhuǎn)發(fā)策略傾向于選取距離目的節(jié)點最近的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包，但所選節(jié)點往往位于通信距離邊緣。在數(shù)據(jù)包進行傳輸時，所選節(jié)點可能已經(jīng)離開通信范圍，造成鏈路斷開。VANET中車輛節(jié)點運動會受到道路和交通規(guī)則等限制，在短時間內(nèi)的運動狀態(tài)具有一定的可預測性。因此可以通過車輛運動狀態(tài)預測節(jié)點之間鏈路維持時間，從而選擇一條更穩(wěn)定的鏈路進行數(shù)據(jù)包轉(zhuǎn)發(fā)。

文獻[11]設(shè)置的場景中船舶可以朝任意方向運動，通過傳輸距離、速度、位置和運動方向預測船舶之間的鏈路維持時間，因此可借助其方法進行計算。值得注意的是，跨層傳輸時由于道路遮擋，最大傳輸半徑會減小。由于道路高度對最大傳輸距離產(chǎn)生的影響遠小于信號衰減，可忽略不計。假定節(jié)點i與節(jié)點j在彼此通信距離Rij之內(nèi)，(xi,yi)、(xj,yi)，vi、vj與θi、θj分別表示節(jié)點位置坐標、行進速度與前進方向，節(jié)點間鏈路維持時間LETij可以表示為

(10)

式中:

a=vicosθi-vjcosθj，

(11)

b=xi-xj，

(12)

c=visinθi-vjsinθj，

(13)

d=yi-yj。

(14)

較長的鏈路維持時間對鏈路穩(wěn)定性影響較??；反之，鏈路發(fā)生斷開的可能性大大增加。因此本文采用鏈路維持時間得分SLET來直觀衡量鏈路維持時間對鏈路質(zhì)量的影響。鏈路維持時間得分SLET表示為

(15)

式中：m和k為常數(shù)，m越小，得分SLET上升越快。鏈路維持時間得分SLET將范圍在(0,+∞)的鏈路維持時間映射到[0,1]的得分之上。鏈路維持時間越長，得分變化越小且越接近1；但當鏈路維持時間較小時，得分隨鏈路維持時間的改變有明顯變化。當鏈路維持時間小于常數(shù)k時，得分為0，即認為鏈路維持時間小于k時鏈路將十分不穩(wěn)定。根據(jù)多次仿真實驗，本文設(shè)置m=10，k為鄰節(jié)點的信標間隔。

(3)負載信息

鄰節(jié)點的負載狀態(tài)同樣是影響鏈路質(zhì)量的關(guān)鍵因素之一。當有數(shù)據(jù)包進行傳輸時，一旦網(wǎng)絡(luò)中所有節(jié)點均使用相同的轉(zhuǎn)發(fā)路徑，一段時間后大量數(shù)據(jù)包在此條路徑中傳輸會造成節(jié)點負載過大。當節(jié)點的負載較大時可能會導致較大的擁塞概率，降低網(wǎng)絡(luò)吞吐量[12]。

信道閑時比率和自身節(jié)點緩存剩余容量情況可以反映出節(jié)點的負載狀態(tài)，因而可定義節(jié)點負載得分Lscore為

Lscore=ηI+(1-η)Q。

(16)

式中：η∈(0,1)為權(quán)重因子，用于調(diào)節(jié)信道閑時比率和自身節(jié)點緩存剩余容量情況對節(jié)點負載得分的影響；I為信道閑時比率得分，可定義為

(17)

式中：φ為大于π的常數(shù)，l表示信道閑時比率。在VANET中，IEEE 802.11p協(xié)議基于CSMA/CD，可以通過對信道狀態(tài)進行監(jiān)聽，獲取信道的忙閑狀態(tài)。信道閑時比率表示在給定時間T內(nèi)節(jié)點感知信道為空閑狀態(tài)時間所占的比例。假定信道每隔ε時間段進行一次監(jiān)測，則信道閑時比率l的可定義為

(18)

節(jié)點緩存剩余容量得分Q定義為

(19)

式中：q表示節(jié)點自身節(jié)點緩存剩余容量情況，qmin、qmax分別為最小閾值與最大閾值。q越小，表明節(jié)點當前節(jié)點緩存剩余容量越少，即緩存隊列占用越多，更容易造成擁塞，其值為

(20)

式中：qavg表示在一個信標間隔時間內(nèi)節(jié)點平均緩存剩余容量，C為節(jié)點緩存列隊的總?cè)萘看笮　?/p>

(3)學習率

學習率決定更新函數(shù)的更新速度，反映了Q學習算法對動態(tài)環(huán)境的適應(yīng)能力，過大的學習率可能會使Q值因為節(jié)點間較小變化產(chǎn)生很大波動；但如果學習率過小，則Q值不能及時反映節(jié)點間鏈路的真實狀態(tài)。因此可以通過動態(tài)調(diào)整學習率適應(yīng)節(jié)點間不同的拓撲變化情況，可定義α為

(21)

網(wǎng)絡(luò)中每個節(jié)點都維護著通過鄰節(jié)點可以抵達的RSU的Q值。當RSU在節(jié)點c通信范圍內(nèi)時，節(jié)點c的獎勵值由瞬時獎勵R組成，即

(22)

式中：NRSU表示RSU的一跳鄰節(jié)點集。當節(jié)點c為RSU一跳鄰節(jié)點時，瞬時獎勵R為1，其余情況為0。

網(wǎng)絡(luò)中每一個節(jié)點通過式(6)更新Q值，當距離目標RSU跳數(shù)越少、鏈路質(zhì)量越高時，最終得到的Q值越大，節(jié)點通過選擇最大Q值節(jié)點進行轉(zhuǎn)發(fā)。

2.2.3 RSU選擇

當源節(jié)點有數(shù)據(jù)包要發(fā)送或RSU接收到數(shù)據(jù)包時，需要選擇下一個臨時目的節(jié)點。下面以圖5為例加以說明。

圖5 RSU選擇

S1、S2道路上的車輛均維護著抵達相鄰RSU(RSUA、RSUB和RSUC)的Q值。假設(shè)車輛A有數(shù)據(jù)包要發(fā)送，首先在相鄰RSU中選擇得分S最高的作為第一臨時目的節(jié)點，進而選擇相應(yīng)Q值最大的車輛轉(zhuǎn)發(fā)數(shù)據(jù)包。當RSU接收到數(shù)據(jù)包時，根據(jù)得分S在其相鄰的RSU中繼續(xù)選擇下一個臨時目的節(jié)點。當目的車輛位于當前RSU與相鄰RSU連通的路段上時，向相鄰RSU轉(zhuǎn)發(fā)數(shù)據(jù)包直至抵達目的車輛。得分S的表達式為

(23)

di=min[|yi-yj|+|xi-xj|]，j=0,1… 。

(24)

式中：(xi,yi)、(xj,yj)分別表示RSUi和RSUj的地理位置。當數(shù)據(jù)包位于RSU時，為保證數(shù)據(jù)包朝著距離目的節(jié)點更近的方向傳輸，di要滿足

di=max[|ynow-yj|+|xnow-xj|]，j=0,1… 。

(25)

式中：(xnow,ynow)為當前RSU的地理位置。

根據(jù)式(23)可知，當Q值越大、曼哈頓距離越小時，得分S越大。

3 仿真與分析

3.1 仿真設(shè)置

利用VanetMobisim和OPNET平臺搭建了3 000 m×4 000 m×10 m的城市3D-VANET仿真場景，對TARP-FQ、QTAR[4]、FL-DGR[3]、ITSR[9]、GPSR[2]五種路由協(xié)議性能進行仿真對比，MAC標準為IEEE 802.11p。仿真場景由單層單向車道、單層雙向車道、雙向高架車道以及環(huán)形高架車道組成，仿真性能指標包括包投遞率(Packet Delivery Ratio，PDR)和平均端到端時延(Average End-to-end Delay，AED)。其余主要仿真參數(shù)如表2所示。

表2 仿真參數(shù)

3.2 PDR性能

圖6所示為三維場景中采用動態(tài)信標間隔和固定信標間隔(1 s、3 s和5 s)時TARP-FQ協(xié)議的PDR隨節(jié)點數(shù)變化的情況，可以看出，動態(tài)信標策略的平均信標間隔始終大于3 s(信標間隔越大，控制開銷越小)，但其PDR卻遠高于采用3 s固定信標間隔的PDR，接近于1 s固定信標間隔的PDR性能(節(jié)點數(shù)大于400時，動態(tài)信標策略的PDR還略優(yōu)于1 s固定信標間隔)。這是因為采用基于模糊邏輯的動態(tài)信標間隔調(diào)整策略時，節(jié)點間拓撲變化較小時，采用較大的信標間隔即可保證數(shù)據(jù)的可靠傳輸，而當網(wǎng)絡(luò)變化加劇時，通過縮小信標間隔來獲得更精確的鄰節(jié)點信息，提高包投遞率，因此其整體性能優(yōu)于采用固定信標間隔。

圖6 不同信標策略的包投遞率

圖7對比了城市三維場景中五種路由協(xié)議的PDR性能，可看出，當車輛數(shù)小于350時，五種協(xié)議的PDR隨車輛數(shù)增加明顯增大，原因在于網(wǎng)絡(luò)的連通性隨著節(jié)點密度的增加而增高；但當節(jié)點數(shù)大于350時，隨著節(jié)點數(shù)增多，網(wǎng)絡(luò)分區(qū)現(xiàn)象減少，而信道發(fā)生沖突的可能性逐漸增大，五種協(xié)議的PDR趨于平緩甚至略有降低。同時從圖7可以看出，GPSR、ITSR的PDR小于其他三種考慮鏈路質(zhì)量的路由協(xié)議。這是因為基于距離貪婪轉(zhuǎn)發(fā)的路由協(xié)議容易采用位于通信范圍邊緣和節(jié)點狀態(tài)較差的車輛轉(zhuǎn)發(fā)數(shù)據(jù)包，會造成數(shù)據(jù)包丟失。同時，從圖中可看出采用Q學習算法的路由協(xié)議(TARP-FQ和QTAR)在網(wǎng)絡(luò)連通性較低時也能夠獲得較高的PDR。這是因為Q-learning算法可以根據(jù)未來獎勵選擇全局最優(yōu)策略，避免了跨層傳輸時局部最優(yōu)問題的發(fā)生。另外，由于TARP-FQ協(xié)議根據(jù)鏈路變化情況動態(tài)調(diào)整學習率，根據(jù)網(wǎng)絡(luò)拓撲變化調(diào)整信標間隔，因此以較低的網(wǎng)絡(luò)開銷成本獲取了最高的PDR。

圖7 不同路由協(xié)議的包投遞率

3.3 AED性能

圖8對比了不同路由協(xié)議的AED性能，可以看出五種協(xié)議的AED均隨節(jié)點數(shù)增多不斷增大。這是因為隨著節(jié)點數(shù)增多，網(wǎng)絡(luò)連通性增大，數(shù)據(jù)包可以傳輸?shù)礁h的節(jié)點。同時，節(jié)點數(shù)的增加可能會造成網(wǎng)絡(luò)擁塞，也會增大網(wǎng)絡(luò)時延。從圖8中還可以看出ITSR與GPSR具有最小的AED，原因在于兩個方面：首先兩者為基于距離貪婪轉(zhuǎn)發(fā)的路由協(xié)議，總是選擇距離目的節(jié)點最近的鄰節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包，所經(jīng)過的中繼節(jié)點數(shù)目最少；其次，由于在轉(zhuǎn)發(fā)過程中，其丟失數(shù)據(jù)包的可能性高于其他三種協(xié)議，尤其是源節(jié)點與目的節(jié)點距離越遠時，數(shù)據(jù)包成功接收的可能性越小。由于ITSR是針對三維場景設(shè)計的路由協(xié)議，考慮了跨層傳輸通信距離減少的特點，大多數(shù)情況下AED略優(yōu)于GPSR。FL-DGR協(xié)議僅考慮了當前節(jié)點與鄰節(jié)點之間的鏈路狀態(tài)，而TARP-FQ、QTAR考慮了未來獎勵做出全局最優(yōu)決策，因此相比于FL-DGR擁有較低的AED。同時，TARP-FQ根據(jù)網(wǎng)絡(luò)拓撲變化情況動態(tài)調(diào)整信標間隔，有利于獲取更精準的鄰節(jié)點信息，其AED小于QTAR。

圖8 不同路由協(xié)議的平均端到端時延

4 結(jié) 論

本文針對城市3D-VANET中道路多樣性的特點，設(shè)計了一種基于模糊邏輯和Q學習的拓撲感知路由(TARP-FQ)協(xié)議。該協(xié)議采用模糊邏輯方法判斷網(wǎng)絡(luò)拓撲變化情況以及網(wǎng)絡(luò)負載狀態(tài)，動態(tài)選擇合適的信標間隔大小，解決了傳統(tǒng)路由協(xié)議在網(wǎng)絡(luò)頻繁變化時節(jié)點信息不準確、網(wǎng)絡(luò)拓撲穩(wěn)定時浪費信道資源的問題。另外，還通過Q學習算法對VANET進行建模，在不同的網(wǎng)絡(luò)環(huán)境中根據(jù)鏈路質(zhì)量和鏈路變化調(diào)整路由決策，同時結(jié)合未來獎勵避免發(fā)生局部最優(yōu)問題。仿真結(jié)果表明，TARP-FQ協(xié)議有利于減少網(wǎng)絡(luò)開銷，降低平均端到端時延和提高包投遞率。