劉靜茹,朱 浩,章國安

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

0 引 言

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

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

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

1 Q學習算法

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

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

對于狀態(tài)動作對(st,at),假定基于t個采樣已估計出Q值函數為

(1)

式中:ri表示i步的獎勵。則在得到第t+1個采樣rt+1時,有

(2)

式中:rt+1表示t+1步的獎勵,表達式為

(3)

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

(4)

Q表存儲了狀態(tài)動作對的Q值Q(st,at),該值代表了在當前狀態(tài)st下采取動作at所期望得到的獎勵。每執(zhí)行一步策略就更新一次值函數估計,得到Q學習的訓練公式為

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

(5)

2 基于Q學習的地理位置路由協(xié)議與應用

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

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

(6)

這里用一個分段函數來描述折扣因子的變化,定義為

(7)

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

(8)

(9)

(10)

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

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

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

圖1 消息傳遞流程

1)如果目的節(jié)點在當前節(jié)點通信范圍內,將消息直接傳遞給目的節(jié)點;

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

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

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

2.2 應用舉例

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

圖2 實例場景示意

3 性能評估

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

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

表1 仿真參數

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

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

2)平均延時:一個分組從源節(jié)點被轉發(fā)到目的節(jié)點所需要的平均時間。

3)平均跳數:一個分組從源節(jié)點到目的節(jié)點,在路由路徑上經過的平均節(jié)點數。

3.2 仿真結果與分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結 論

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