劉靜茹,朱 浩,章國(guó)安

(南通大學(xué) 信息科學(xué)技術(shù)學(xué)院,江蘇 南通 226019)

0 引 言

車聯(lián)網(wǎng)作為智能交通系統(tǒng)的重要組成部分,已經(jīng)成為研究熱點(diǎn)。車聯(lián)網(wǎng)包括一個(gè)由大量車輛節(jié)點(diǎn)和基礎(chǔ)設(shè)施組成的異構(gòu)系統(tǒng),車輛和基礎(chǔ)設(shè)施之間的通信使車輛節(jié)點(diǎn)能夠獲取交通信息,從而有效地提高交通安全和運(yùn)輸效率[1]。為了在車聯(lián)網(wǎng)中傳遞消息,分組必須通過多跳無(wú)線通信從源節(jié)點(diǎn)發(fā)送到目的節(jié)點(diǎn),因此要用到路由功能來選擇最佳下一跳。然而車輛的快速移動(dòng)導(dǎo)致節(jié)點(diǎn)分布不均勻和通信鏈路斷開,再加上網(wǎng)絡(luò)結(jié)構(gòu)受道路拓?fù)浣Y(jié)構(gòu)的影響,路由協(xié)議的設(shè)計(jì)變得十分困難。

根據(jù)參與通信的移動(dòng)車輛節(jié)點(diǎn)數(shù)目,車聯(lián)網(wǎng)中的路由協(xié)議主要分為單播路由、廣播路由和多播/位置輔助路由[2]。單播路由技術(shù)是指從一個(gè)源節(jié)點(diǎn)經(jīng)過多跳無(wú)線通信將分組發(fā)送到一個(gè)特定目的地的路由技術(shù),本文主要研究單播路由。單播路由中比較常見的是基于拓?fù)涞穆酚珊突诘乩砦恢玫穆酚??；谕負(fù)涞穆酚蓞f(xié)議使用路由表存儲(chǔ)有關(guān)路由路徑的信息,到所有目的地的路由必須在通信之前建立,每個(gè)節(jié)點(diǎn)定期廣播控制分組,以便與網(wǎng)絡(luò)中的其他節(jié)點(diǎn)共享信息,并更新路由表[3]。基于地理位置的路由利用全球定位系統(tǒng)(Global Positioning System,GPS)技術(shù),根據(jù)節(jié)點(diǎn)之間共享的位置信息轉(zhuǎn)發(fā)分組,可以減少節(jié)點(diǎn)高移動(dòng)性的影響,避免維護(hù)整個(gè)網(wǎng)絡(luò)的路由表。文獻(xiàn)[4-5]都將軟件定義網(wǎng)絡(luò)運(yùn)用到車聯(lián)網(wǎng)中,顯示了集中控制的好處。其中文獻(xiàn)[4]提出了一種車聯(lián)網(wǎng)中結(jié)合移動(dòng)性預(yù)測(cè)的集中式路由方案,由人工智能驅(qū)動(dòng)的軟件定義網(wǎng)絡(luò)控制器輔助,基于移動(dòng)性預(yù)測(cè),可由路側(cè)單元或基站估計(jì)網(wǎng)絡(luò)拓?fù)漕l繁變化下每輛車請(qǐng)求的成功傳輸率和平均延遲;基于全局網(wǎng)絡(luò)信息,SDN控制器為轉(zhuǎn)換器計(jì)算最優(yōu)路由路徑。文獻(xiàn)[6]提出的基于地理位置的貪婪周邊無(wú)狀態(tài)路由協(xié)議,總是選擇距離目的地最近的鄰居節(jié)點(diǎn)作為下一跳節(jié)點(diǎn),這在車輛高速移動(dòng)的情況下有很大難度。文獻(xiàn)[7]提出了一種基于車輛位置分析的路由算法,根據(jù)預(yù)測(cè)的車輛軌跡做出傳輸決策,但是沒有考慮到道路上現(xiàn)實(shí)因素的影響。文獻(xiàn)[8-10]都注意到了十字路口交通信號(hào)燈引起的車輛聚集現(xiàn)象,例如,文獻(xiàn)[8]根據(jù)街道中間區(qū)域的車輛分布和密度計(jì)算街道的連通性,提出了一個(gè)以街道為中心的基于街道連通性的交通燈感知路由協(xié)議?；趶?qiáng)化學(xué)習(xí)的算法可以優(yōu)化車聯(lián)網(wǎng)路由的不同服務(wù)質(zhì)量參數(shù),如端到端延時(shí)、分組投遞率、開銷等[11],如文獻(xiàn)[12-14]都結(jié)合了強(qiáng)化學(xué)習(xí)算法進(jìn)行路由。結(jié)合強(qiáng)化學(xué)習(xí)中的Q學(xué)習(xí)算法進(jìn)行路由,不需要維護(hù)路由表,只需要建立一個(gè)Q值表,然后根據(jù)Q值表選擇最優(yōu)路由路徑。文獻(xiàn)[15-19]中采用了Q學(xué)習(xí)算法,其中,文獻(xiàn)[15]提出了一種基于Q學(xué)習(xí)的分層路由協(xié)議,根據(jù)Q表選擇下一個(gè)最優(yōu)網(wǎng)格,跳過相鄰車輛,將消息從源車輛發(fā)送到目的車輛;文獻(xiàn)[17]中加入了RSU進(jìn)行輔助,同時(shí)考慮到交通燈的影響,利用Q學(xué)習(xí)算法和貪婪轉(zhuǎn)發(fā)算法進(jìn)行路由。

車聯(lián)網(wǎng)中車輛節(jié)點(diǎn)快速變化導(dǎo)致通信鏈路連接不穩(wěn)定,同時(shí)網(wǎng)絡(luò)會(huì)受到道路拓?fù)浣Y(jié)構(gòu)的影響。為了解決此問題,本文提出了一種改進(jìn)的基于Q學(xué)習(xí)的地理位置路由協(xié)議(Geographic Location Routing Protocol Based on Q-learning,QGR)。該協(xié)議將不同的地理區(qū)域劃分為網(wǎng)格,同時(shí)結(jié)合Q學(xué)習(xí)探索道路環(huán)境,是對(duì)QGrid[15]協(xié)議的改進(jìn),充分利用Q學(xué)習(xí)算法和網(wǎng)格的結(jié)合,可以找到最優(yōu)下一跳網(wǎng)格和次優(yōu)下一跳網(wǎng)格。該協(xié)議不僅提高了分組投遞率,而且降低了傳輸延時(shí),減少了通信跳數(shù)。

1 Q學(xué)習(xí)算法

Q學(xué)習(xí)是一種免模型的強(qiáng)化學(xué)習(xí)算法,它是基于馬爾科夫決策過程的,可以用元組(S,A,P,R,γ)來表示,S代表狀態(tài)空間的離散集合,A代表動(dòng)作空間的離散集合,P代表狀態(tài)轉(zhuǎn)移概率,R代表即時(shí)獎(jiǎng)勵(lì),γ代表折扣因子。機(jī)器是車聯(lián)網(wǎng)中具有歷史交通流信息的云服務(wù)器,也是Q學(xué)習(xí)中的學(xué)習(xí)者和決策者,通過不斷地與環(huán)境交互以學(xué)習(xí)控制策略。

本文將不同網(wǎng)格的集合定義為狀態(tài)空間S,動(dòng)作空間A是下一跳網(wǎng)格的集合,整個(gè)車聯(lián)網(wǎng)就是環(huán)境,機(jī)器根據(jù)獎(jiǎng)勵(lì)推斷環(huán)境,獎(jiǎng)勵(lì)用來代表分組是否被發(fā)送到了目的地。機(jī)器觀察到當(dāng)前的環(huán)境狀態(tài)st,然后選擇一個(gè)動(dòng)作at,采取該動(dòng)作后,機(jī)器獲得了一個(gè)獎(jiǎng)勵(lì)Rt,同時(shí)系統(tǒng)狀態(tài)轉(zhuǎn)變到下一個(gè)狀態(tài)st+1。假設(shè)在消息發(fā)送的過程中,消息的目的地是固定的。如果消息發(fā)送到了目的地,獎(jiǎng)勵(lì)就是100,否則獎(jiǎng)勵(lì)就是0。

對(duì)于狀態(tài)動(dòng)作對(duì)(st,at),假定基于t個(gè)采樣已估計(jì)出Q值函數(shù)為

(1)

式中:ri表示i步的獎(jiǎng)勵(lì)。則在得到第t+1個(gè)采樣rt+1時(shí),有

(2)

式中:rt+1表示t+1步的獎(jiǎng)勵(lì),表達(dá)式為

(3)

Q′(st,at)=(1-α)×Q(st,at)+

(4)

Q表存儲(chǔ)了狀態(tài)動(dòng)作對(duì)的Q值Q(st,at),該值代表了在當(dāng)前狀態(tài)st下采取動(dòng)作at所期望得到的獎(jiǎng)勵(lì)。每執(zhí)行一步策略就更新一次值函數(shù)估計(jì),得到Q學(xué)習(xí)的訓(xùn)練公式為

Q(st,at)←(1-α)×Q(st,at)+

(5)

2 基于Q學(xué)習(xí)的地理位置路由協(xié)議與應(yīng)用

2.1 基于Q學(xué)習(xí)的地理位置路由協(xié)議

本文提出了一種基于Q學(xué)習(xí)的地理位置路由協(xié)議,將選定的地理位置區(qū)域劃分成36個(gè)大小一致的網(wǎng)格。區(qū)域中的車輛定期向數(shù)據(jù)中心發(fā)送GPS數(shù)據(jù)報(bào)告,具體的信息包括車輛的ID、經(jīng)度、緯度、時(shí)間戳、移動(dòng)速度、行駛方向和當(dāng)前的狀態(tài)。車輛的歷史軌跡具有很強(qiáng)的規(guī)律性,因此,根據(jù)歷史交通流信息訓(xùn)練Q學(xué)習(xí)算法。QGR協(xié)議由兩部分組成:宏觀方面,根據(jù)Q值決定最優(yōu)/次優(yōu)下一跳網(wǎng)格;微觀方面,確定所選網(wǎng)格的特定車輛。計(jì)算出車輛從當(dāng)前網(wǎng)格向不同方向的鄰居網(wǎng)格移動(dòng)的Q值,每輛車存儲(chǔ)Q學(xué)習(xí)的Q值表,然后通過查詢Q值表選擇最優(yōu)下一跳網(wǎng)格。在選定的下一跳網(wǎng)格中,選擇距離目的地最近的車輛,當(dāng)最優(yōu)下一跳網(wǎng)格中沒有鄰居車輛時(shí),選擇次優(yōu)下一跳網(wǎng)格中的車輛。該協(xié)議的目的是將消息從源車輛所在的網(wǎng)格以高概率發(fā)送到目的地。本文將不同的網(wǎng)格定義為狀態(tài),學(xué)習(xí)狀態(tài)的數(shù)量將會(huì)大大減少,Q學(xué)習(xí)的Q值表將在整個(gè)周期中使用,節(jié)省了大量的系統(tǒng)資源和時(shí)間。機(jī)器采取的動(dòng)作是將分組從一個(gè)網(wǎng)格發(fā)送到另一個(gè)網(wǎng)格,當(dāng)目的地在鄰居網(wǎng)格,獎(jiǎng)勵(lì)就是100,否則初始獎(jiǎng)勵(lì)就是0。本協(xié)議中,折扣因子是一個(gè)動(dòng)態(tài)參數(shù),取決于網(wǎng)格中的車輛數(shù)量和網(wǎng)格到目的地的距離。用M代表網(wǎng)格總數(shù),n(gi)表示網(wǎng)格gi中記錄的車輛數(shù)量,計(jì)算出所有網(wǎng)格中車輛數(shù)量的平均數(shù)為

(6)

這里用一個(gè)分段函數(shù)來描述折扣因子的變化,定義為

(7)

式中:β是權(quán)重因子,其范圍是β∈[0,1];NP是車輛數(shù)量的影響因子,定義如式(8)所示;DP是到目的地距離的影響因子,定義如式(9)所示。

(8)

(9)

(10)

式(8)中的μ是一個(gè)常數(shù)值;式(9)中的distc是當(dāng)前網(wǎng)格距離目的網(wǎng)格的距離,distn是下一跳網(wǎng)格距離目的網(wǎng)格的距離。在通信的開始,機(jī)器對(duì)于整個(gè)環(huán)境一無(wú)所知,Q表中的所有元素都被初始化為0。利用Q學(xué)習(xí)方法獲得Q值表,Q值代替元組中的狀態(tài)轉(zhuǎn)移概率,將Q值表存儲(chǔ)在每輛車中,然后根據(jù)該表傳遞消息。

在QGR中,車輛不需要維護(hù)路由表,它們只根據(jù)Q學(xué)習(xí)的Q值表發(fā)送消息,即當(dāng)前車輛選擇具有最大Q值的最優(yōu)下一跳網(wǎng)格,并在最優(yōu)網(wǎng)格中選擇距離目的地最近的車輛,如果最優(yōu)網(wǎng)格中沒有車輛,就選擇具有第二大Q值的次優(yōu)網(wǎng)格作為下一跳網(wǎng)格。Q值表包含與不同目的網(wǎng)格對(duì)應(yīng)的最佳下一跳網(wǎng)格,因此在給定任意一個(gè)目的網(wǎng)格時(shí),都可以根據(jù)Q值找到對(duì)應(yīng)的轉(zhuǎn)發(fā)路徑。

用vt代表當(dāng)前的車輛節(jié)點(diǎn),消息傳遞流程如圖1所示,當(dāng)選擇下一跳車輛時(shí)有四種類型:

圖1 消息傳遞流程

1)如果目的節(jié)點(diǎn)在當(dāng)前節(jié)點(diǎn)通信范圍內(nèi),將消息直接傳遞給目的節(jié)點(diǎn);

2)如果目的節(jié)點(diǎn)不在當(dāng)前節(jié)點(diǎn)通信范圍內(nèi),從Q表中尋找最優(yōu)下一跳網(wǎng)格,在選定的最優(yōu)下一跳網(wǎng)格中尋找傳遞消息的下一跳車輛,應(yīng)選擇vt通信范圍內(nèi)距離目的節(jié)點(diǎn)最近的車輛;

3)如果最優(yōu)下一跳網(wǎng)格中沒有鄰居車輛,從Q表中尋找次優(yōu)下一跳網(wǎng)格,在選定的次優(yōu)下一跳網(wǎng)格中尋找傳遞消息的下一跳車輛,應(yīng)選擇vt通信范圍內(nèi)距離目的節(jié)點(diǎn)最近的車輛;

4)如果次優(yōu)下一跳網(wǎng)格中沒有鄰居車輛,則考慮vt鄰居車輛中距離目的節(jié)點(diǎn)最近的車輛為下一跳車輛(可以為本身)。

2.2 應(yīng)用舉例

實(shí)例場(chǎng)景如圖2所示,將地理區(qū)域劃分為36個(gè)網(wǎng)格,源車輛S位于第17個(gè)網(wǎng)格中,目的車輛D位于第20個(gè)網(wǎng)格中。目的車輛不在源車輛的通信范圍內(nèi),根據(jù)Q表找到最優(yōu)下一跳網(wǎng)格22,網(wǎng)格22中沒有鄰居車輛,找到次優(yōu)下一跳網(wǎng)格16,且網(wǎng)格16中有多個(gè)鄰居車輛,選擇距離目的地最近的鄰居車輛作為中繼;網(wǎng)格16的最優(yōu)下一跳網(wǎng)格中沒有鄰居車輛,則選擇次優(yōu)下一跳網(wǎng)格15,于是選擇網(wǎng)格15中的車輛作為下一跳;網(wǎng)格15的最優(yōu)下一跳網(wǎng)格是21,選擇網(wǎng)格21中的車輛作為中繼;目的車輛位于網(wǎng)格21的中繼車輛的通信范圍內(nèi),所以最后一跳直接將分組傳遞給目的車輛。

圖2 實(shí)例場(chǎng)景示意

3 性能評(píng)估

3.1 仿真環(huán)境和參數(shù)

基于城市道路進(jìn)行仿真,實(shí)驗(yàn)域的大小為3 000 m×3 000 m,主要仿真參數(shù)如表1所示。不同的車輛上傳GPS數(shù)據(jù)的時(shí)間是不一樣的,當(dāng)它們同時(shí)在彼此的通信范圍內(nèi),也可能不會(huì)同時(shí)上傳GPS數(shù)據(jù),這會(huì)導(dǎo)致GPS數(shù)據(jù)集中實(shí)際相鄰的車輛斷開連接。因此,使用時(shí)間間隔ΔT來表示實(shí)際的GPS數(shù)據(jù)上傳時(shí)間。如果一個(gè)時(shí)間間隔內(nèi),有兩輛車在對(duì)方的通信范圍內(nèi),則認(rèn)為這兩輛車在此期間相遇,時(shí)間間隔越大,鄰居車輛越多。時(shí)間間隔的選擇會(huì)極大地影響網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),這關(guān)系到路由性能的好壞。網(wǎng)格長(zhǎng)度與無(wú)線通信半徑相關(guān)聯(lián),在本協(xié)議中也是一個(gè)重要參數(shù):一方面,如果網(wǎng)格長(zhǎng)度過小,Q學(xué)習(xí)中的狀態(tài)數(shù)(即網(wǎng)格數(shù))就會(huì)增多,到目的地的跳數(shù)也會(huì)增加;另一方面,如果網(wǎng)格長(zhǎng)度過大,相鄰車輛可能與攜帶消息的車輛位于同一網(wǎng)格中。因此要選擇一個(gè)合適的網(wǎng)格長(zhǎng)度,本協(xié)議的網(wǎng)格長(zhǎng)度設(shè)為500 m?？紤]到傳輸范圍的問題,通信半徑設(shè)置為500 m。TTL是生存時(shí)間值,指定了分組被丟棄之前允許通過的最大網(wǎng)段數(shù)量。TTL的作用是避免分組在網(wǎng)絡(luò)中的無(wú)限循環(huán)和收發(fā),節(jié)省網(wǎng)絡(luò)資源。每條消息都有TTL次轉(zhuǎn)發(fā)機(jī)會(huì),如果經(jīng)過一輪循環(huán)后,消息沒有傳遞成功,則TTL減1;如果TTL=0時(shí)消息還沒有傳遞成功,則該消息將會(huì)被丟棄,并向發(fā)送者發(fā)送非成功傳遞信號(hào)。因此,TTL越大,會(huì)有更多的消息被傳遞成功。

表1 仿真參數(shù)

將本文的路由協(xié)議與GPSR[5]和QGrid[14]進(jìn)行比較,用于評(píng)估路由協(xié)議性能的指標(biāo)如下:

1)分組投遞率:在仿真時(shí)間內(nèi),目的節(jié)點(diǎn)成功接收分組的總數(shù)量與源節(jié)點(diǎn)發(fā)送分組的總數(shù)量之比。

2)平均延時(shí):一個(gè)分組從源節(jié)點(diǎn)被轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)所需要的平均時(shí)間。

3)平均跳數(shù):一個(gè)分組從源節(jié)點(diǎn)到目的節(jié)點(diǎn),在路由路徑上經(jīng)過的平均節(jié)點(diǎn)數(shù)。

3.2 仿真結(jié)果與分析

圖3～5顯示了時(shí)間間隔的選擇對(duì)路由協(xié)議性能的影響。在相同的TTL下,從圖3中可以看出,時(shí)間間隔越大,分組投遞率越高;從圖4中可以看出,時(shí)間間隔越大,傳輸延時(shí)越小;從圖5中可以看出,時(shí)間間隔越大,通信跳數(shù)越多。所以,增加時(shí)間間隔可以提高分組投遞率、降低傳輸延時(shí),但同時(shí)也會(huì)增加轉(zhuǎn)發(fā)的跳數(shù)。這是因?yàn)楫?dāng)時(shí)間間隔增加的時(shí)候,鄰居車輛的數(shù)量就會(huì)增加。將該協(xié)議和另外兩種基于地理位置的路由協(xié)議在ΔT=10 s和ΔT=20 s的情況下進(jìn)行了比較,分別評(píng)估三種路由協(xié)議的性能,其他實(shí)驗(yàn)參數(shù)如表1所示。GPSR只選擇鄰近的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā),沒有考慮到整個(gè)區(qū)域的網(wǎng)絡(luò)狀況。QGrid在選擇下一跳網(wǎng)格時(shí),只考慮選擇了最優(yōu)網(wǎng)格,而且在Q學(xué)習(xí)算法中只考慮了下一跳網(wǎng)格中的車輛數(shù)目。而本文的QGR算法對(duì)前面兩種算法進(jìn)行了改進(jìn),選擇下一跳網(wǎng)格時(shí),不僅僅考慮了網(wǎng)格中的車輛數(shù)量,還考慮了網(wǎng)格中車輛距離目的地的距離,當(dāng)最優(yōu)下一跳網(wǎng)格中沒有車輛時(shí),考慮選擇次優(yōu)下一跳網(wǎng)格中的車輛,充分利用了網(wǎng)格的特點(diǎn)和優(yōu)勢(shì)。

圖3 QGR協(xié)議在不同時(shí)間間隔下的分組投遞率

圖4 QGR協(xié)議在不同時(shí)間間隔下的延時(shí)

圖5 QGR協(xié)議在不同時(shí)間間隔下的跳數(shù)

圖6～8中設(shè)置參數(shù)ΔT=10 s。從圖6中可以看出,QGR的分組投遞率高于QGrid和GPSR,而且三種協(xié)議的分組投遞率隨著TTL的增加而增加。這是因?yàn)門TL越大,會(huì)有更多的消息被傳遞成功。圖7中GPSR的延時(shí)明顯較高,當(dāng)TTL較小時(shí),QGrid和QGR的曲線幾乎重合,但是當(dāng)TTL較大的時(shí)候,QGR的延時(shí)就小于QGrid的延時(shí)。圖8表示一個(gè)仿真周期的平均跳數(shù)隨著TTL的增加而增加,GPSR的跳數(shù)最多,QGR和QGrid的跳數(shù)比較相近,本文的QGR路由協(xié)議具有最小的跳數(shù)。

圖6 ΔT=10 s的情況下三種協(xié)議的分組投遞率

圖7 ΔT=10 s的情況下三種協(xié)議的延時(shí)

圖8 ΔT=10 s的情況下三種協(xié)議的跳數(shù)

圖9～11中設(shè)置參數(shù)ΔT=20 s。圖9表示的是三種路由協(xié)議的分組投遞率的對(duì)比,可見在每一個(gè)TTL值下,本文的QGR協(xié)議都具有最高的分組投遞率,而另外兩種協(xié)議的分組投遞率比較相近,且都低于本文的協(xié)議。圖10顯示的是三種協(xié)議的平均延時(shí)的對(duì)比,可以看出本文的QGR協(xié)議具有最低的延時(shí)。圖11表明,相對(duì)于另外兩種路由協(xié)議,QGR用了最少的跳數(shù)進(jìn)行消息傳遞。因此,可以發(fā)現(xiàn),本文的QGR協(xié)議具有最高的分組投遞率,而且擁有最小的延時(shí)和最小的跳數(shù)。

圖9 ΔT=20 s的情況下三種協(xié)議的分組投遞率

圖10 ΔT=20 s的情況下三種協(xié)議的延時(shí)

圖11 ΔT=20 s的情況下三種協(xié)議的跳數(shù)

4 結(jié) 論

本文提出了一種基于Q學(xué)習(xí)的地理位置路由協(xié)議。該協(xié)議將地理區(qū)域劃分成大小一致的網(wǎng)格,在給定目的地的情況下計(jì)算出車輛從當(dāng)前網(wǎng)格向不同方向的鄰居網(wǎng)格移動(dòng)的Q值,每輛車存儲(chǔ)Q學(xué)習(xí)的Q值表,通過查詢Q值表選擇最優(yōu)下一跳網(wǎng)格,在選定的下一跳網(wǎng)格中選擇距離目的地最近的鄰居車輛,當(dāng)最優(yōu)下一跳網(wǎng)格中沒有車輛時(shí)選擇次優(yōu)下一跳網(wǎng)格中的車輛。仿真結(jié)果表明,該協(xié)議能夠提高分組投遞率,降低傳輸延時(shí),并且減少通信跳數(shù)。