鄭澤濤，何榮希，周 宇

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

0 引 言

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

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

由于城市3D-VANET中往往包含多種道路場景，每種道路場景的網(wǎng)絡(luò)拓?fù)涠季哂胁煌奶攸c(diǎn)，不同道路場景之間節(jié)點(diǎn)分布和運(yùn)動(dòng)差異較大。3D-VANET中應(yīng)依據(jù)道路場景自適應(yīng)調(diào)整信標(biāo)間隔。

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

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

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

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

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

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

2.1.1 動(dòng)態(tài)信標(biāo)間隔

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

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

圖1 信標(biāo)間隔大小對鄰節(jié)點(diǎn)信息準(zhǔn)確性的影響

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

(2)在S1道路中，受道路和車輛間的相互約束，網(wǎng)絡(luò)拓?fù)渥兓^慢，此時(shí)較長的固定信標(biāo)間隔即可保證E鄰節(jié)點(diǎn)信息的有效性。如果選擇較短的固定信標(biāo)間隔，則會引入較大的網(wǎng)絡(luò)開銷，浪費(fèi)信道資源。

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

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

2.1.2 模糊化輸入與處理

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

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

(1)速度標(biāo)準(zhǔn)差

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

(1)

(2)行進(jìn)方向數(shù)

在平面場景路由協(xié)議的研究中，相鄰車輛僅沿著道路雙向運(yùn)動(dòng)，而在城市三維場景中由于高架、立交橋等道路形式的存在，相鄰車輛可能存在多個(gè)行進(jìn)方向。當(dāng)相鄰車輛行進(jìn)方向越多時(shí)，網(wǎng)絡(luò)拓?fù)涞淖兓瘜⒃筋l繁。為便于計(jì)算，定義8個(gè)車輛行進(jìn)方向，如圖2所示。圖中c為車輛當(dāng)前位置，cc′為當(dāng)前車輛的行進(jìn)方向。

圖2 節(jié)點(diǎn)行進(jìn)方向

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

(2)

當(dāng)鄰節(jié)點(diǎn)列表中有節(jié)點(diǎn)行進(jìn)方向?yàn)閐iri時(shí)，將diri值置1，否則為0。

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

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

(3)

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

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

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

(4)

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

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

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

2.1.3 解模糊輸出信標(biāo)間隔

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

表1 模糊邏輯部分準(zhǔn)則示例

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

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

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

(5)

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

2.2 基于Q學(xué)習(xí)的路由選擇

2.2.1 Q學(xué)習(xí)算法建模

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

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

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

瞬時(shí)獎(jiǎng)勵(lì)R：當(dāng)前智能體節(jié)點(diǎn)通過一次動(dòng)作從環(huán)境中獲得的瞬時(shí)獎(jiǎng)勵(lì)。

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

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

根據(jù)文獻(xiàn)[10]可將Q學(xué)習(xí)算法更新公式表示為

(6)

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

2.2.2 Q學(xué)習(xí)參數(shù)設(shè)計(jì)

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

當(dāng)前節(jié)點(diǎn)接收到鄰節(jié)點(diǎn)的HELLO包時(shí)，首先計(jì)算折扣因子γ，其值為

γ=γpreγscore。

(7)

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

(8)

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

(1)可替代度

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

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

(9)

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

(2)鏈路維持時(shí)間

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

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

(10)

式中:

a=vicosθi-vjcosθj，

(11)

b=xi-xj，

(12)

c=visinθi-vjsinθj，

(13)

d=yi-yj。

(14)

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

(15)

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

(3)負(fù)載信息

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

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

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

(16)

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

(17)

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

(18)

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

(19)

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

(20)

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

(3)學(xué)習(xí)率

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

(21)

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

(22)

式中：NRSU表示RSU的一跳鄰節(jié)點(diǎn)集。當(dāng)節(jié)點(diǎn)c為RSU一跳鄰節(jié)點(diǎn)時(shí)，瞬時(shí)獎(jiǎng)勵(lì)R為1，其余情況為0。

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

2.2.3 RSU選擇

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

圖5 RSU選擇

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

(23)

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

(24)

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

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

(25)

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

根據(jù)式(23)可知，當(dāng)Q值越大、曼哈頓距離越小時(shí)，得分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é)議性能進(jìn)行仿真對比，MAC標(biāo)準(zhǔn)為IEEE 802.11p。仿真場景由單層單向車道、單層雙向車道、雙向高架車道以及環(huán)形高架車道組成，仿真性能指標(biāo)包括包投遞率(Packet Delivery Ratio，PDR)和平均端到端時(shí)延(Average End-to-end Delay，AED)。其余主要仿真參數(shù)如表2所示。

表2 仿真參數(shù)

3.2 PDR性能

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

圖6 不同信標(biāo)策略的包投遞率

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

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

3.3 AED性能

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

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

4 結(jié) 論

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