代 亮 張亞楠 錢 超 孟 蕓 黃 鶴

車聯(lián)網作為協(xié)同車-路-環(huán)境的開放融合網絡系統(tǒng),可為智能交通系統(tǒng)管理和控制提供新思路和手段[1],還可作為物聯(lián)網實體為道路及周邊的事件監(jiān)測作傳輸載體[2].

高速公路沿線部署多個RSU 給行駛車輛提供信息服務是車聯(lián)網的重要應用場景.RSU 不僅可作為經過其無線覆蓋范圍內過往車輛的互聯(lián)網接入設備;部分RSU 還承擔著其周邊交通狀況、環(huán)境監(jiān)測、自然災害及動物活動信息的收集和轉發(fā)功能.為了降低高速公路車聯(lián)網中通信基礎設施的部署開銷,部分RSU 與骨干網絡處于隔離狀態(tài)[3].孤立RSU可通過移動車輛以“存儲-載帶-轉發(fā)”的方式將所收集到的周邊交通狀況、環(huán)境監(jiān)測、動物活動等信息轉發(fā)到與骨干網絡相連的RSU[4-6].由于源RSU業(yè)務源的動態(tài)變化性和不可預測性使得自適應的分組調度面臨挑戰(zhàn),如森林火災監(jiān)控、各種靜止或移動的被監(jiān)測保護動物等,業(yè)務狀態(tài)在短時間內表現出高度的突發(fā)性[7-8],需要以自適應和魯棒的方法解決突發(fā)業(yè)務調度問題,以提高網絡資源利用率.

在上述應用背景下,應設計有效的源RSU 節(jié)點分組調度策略,在其無線覆蓋范圍內有車輛經過時,決定是否將收集的數據發(fā)送給過往車輛進行載帶中繼傳輸.分組端到端時延由源RSU 緩存中的排隊時延與車輛載帶分組至目的RSU 過程中的傳播時延兩部分組成.若源RSU 給到達車輛均發(fā)送分組,能使平均排隊時延最小,但會導致較大的平均傳播時延;若為了等待速度較快的車輛而導致分組在緩存中過多積壓,則平均排隊時延增加.因此,平均排隊時延和平均傳播時延之間存在最佳折中能使平均端到端時延最小化.當源RSU 的突發(fā)業(yè)務到達其緩存隊列時,如果能根據突發(fā)業(yè)務到達率動態(tài)調整載帶車輛的速度選擇范圍,就能緩解由于分組隊列阻塞帶來的排隊時延增長.

1 相關工作及本文貢獻

車聯(lián)網中由于車輛移動速度快導致網絡拓撲頻繁變化,網絡節(jié)點間斷連通,這種間歇連通特性雖然增大了數據傳輸時延,但也增加了數據分發(fā)的機會和網絡容量,適用于時延容忍的業(yè)務[9].車聯(lián)網可使用“存儲-載帶-轉發(fā)(Store-carry-forward)”的機會傳輸方式進行時延容忍業(yè)務的多跳傳輸[10].現有的高速公路車聯(lián)網場景以“存儲-載帶-轉發(fā)”方式進行時延容忍業(yè)務傳輸研究主要關注于如何保證車輛間多跳傳輸的可達性,而對網絡性能考慮較少.文獻[11]在高速公路場景下,得到了通過車輛載帶中繼的消息在一定距離上的傳播時延的概率分布,以此為基礎,研究兩個緊鄰車輛簇中后簇簇首通過車輛載帶中繼將分組發(fā)給前簇簇尾的時延概率分布,進而得到該場景下端到端時延的分布情況[12].Huang 等[13]考慮了車輛分布稀疏且相對移動速度不同會導致其通信過程頻繁中斷,研究了長距離車輛載帶中繼消息恢復時延的穩(wěn)態(tài)分布.文獻[14]提出了一種結合V2V (Vehicle to vehicle)和V2I (Vehicle to infrastructure)混雜方式的車輛載帶中繼的車聯(lián)網數據分發(fā)方法,有數據待發(fā)的車輛可以通過多跳成簇的方式,將數據通過其他車輛載帶中繼到RSU 節(jié)點,該方法可以優(yōu)化網絡資源利用率及減少數據交付時延.

互不連通的RSU 可通過過往車輛“存儲-載帶-轉發(fā)”的方式將所收集到的周邊的交通狀況、環(huán)境監(jiān)測、動物活動等信息轉發(fā)到與骨干網絡相連的RSU,進而傳送給數據中心[4-6].高速公路車聯(lián)網中,RSU 可作為多種傳感器網絡的匯入網關,承擔著周邊交通狀況、環(huán)境監(jiān)測、動物活動等信息的收集和轉發(fā)功能.該場景下,在RSU 節(jié)點形成的業(yè)務具有突發(fā)性[15].在進行RSU 分度調度研究時,需要考慮業(yè)務突發(fā)性對分組排隊時延和分組傳播時延的影響.目前車聯(lián)網突發(fā)業(yè)務相關研究主要集中在由車輛隨機到達引起的業(yè)務突發(fā)性,包括車與車,車與路邊單元之間待傳輸的業(yè)務.文獻[16]通過V2V多跳方式將具有突發(fā)性的車輛業(yè)務傳輸到RSU,并根據車輛與RSU 間的延遲約束估算覆蓋該路段所需的最少RSU 數量.文獻[17]在車輛通信環(huán)境下提出一種突發(fā)分組生成算法,能更加精確地描述突發(fā)業(yè)務傳輸過程中的分組生成情況.在文獻[18]中,作者研究了異構車載網絡基于位置路由的端到端時延界問題,考慮了車輛間通信的突發(fā)特性,將車輛間多跳通信建模成廣義隨機有界突發(fā)模型.文獻[19]考慮了車輛業(yè)務的突發(fā)性和信道環(huán)境的高度動態(tài)性,研究V2V 多跳通信過程中業(yè)務源緩存情況、端到端時延性能及多跳傳輸帶來的業(yè)務突發(fā)累積效應.文獻[20]根據車輛軌跡數據統(tǒng)計車輛行駛過程中與RSU 相遇的概率分布,在業(yè)務分組具有隨機性和突發(fā)性的條件下,研究車聯(lián)網中移動數據卸載問題.也有相關文獻從較大時間尺度來考慮車聯(lián)網性能,車聯(lián)網的業(yè)務需求及可用網絡資源隨著交通流量的時空變化而變化,其業(yè)務到達具有突發(fā)性[21-22].

由車輛載帶中繼的分組在RSU 間傳輸過程中,其端到端時延主要由排隊時延和傳播時延兩部分組成.貪婪中繼方案(Greedy bundle relaying scheme,GBRS)[23]不考慮車輛速度,源RSU 向經過的每個車輛均發(fā)送1 個分組,該方法能使排隊時延最小,但傳播時延較大.為降低傳播時延,Khabbaz等[23-25]提出了一種RSU 分組概率中繼方案(Probabilistic bundle relaying scheme,PBRS),在該方案中定義一個稱為發(fā)送概率的參數Pr,該發(fā)送概率與車速成正相關,該方案不能對分組隊列長度的動態(tài)變化做出相應調整.在文獻[26-28]中作者基于分組重傳機制,將虛擬空間引入分組延遲感知的分組傳輸方案,目的是在1 個分組到達目的RSU 前,源RSU 可將虛擬空間中該分組備份重傳給后續(xù)到達但速度更快的車輛,以便更早地交付給目的RSU,但會造成分組冗余傳輸,影響網絡資源利用率.Ramaiyan 等[29]假設源節(jié)點能感知車輛到達時間和車速,并根據車速和累計的分組數量做傳輸決策,利用動態(tài)規(guī)劃方法解決了RSU 間分組傳輸端到端時延最小化問題,該方法需要已知完整的網絡信息知識(即精確的車輛到達時刻、車輛速度等),并以每輛車到達時刻作為決策點,不能及時感知RSU緩存中分組的動態(tài)變化.在文獻[30]中,作者在相同背景下,通過建立馬爾科夫鏈分析了傳播時延對接收端RSU 緩沖區(qū)中分組傳輸和重新排序的影響,統(tǒng)計間歇性連通車載網絡場景下的延遲數據來評估網絡性能.

在上述研究工作中,源RSU 向每個經過車輛發(fā)送1 個分組的方式使得傳輸資源利用率低,且排隊時延受分組到達率的影響較大.據此,Khabbaz 等[23-24,31-32]提出了一種批量分組概率傳輸方案(Probabilistic bundle relaying scheme with bulk bundle release,PBRS-BBR),通過提高服務率減少分組在緩存中的排隊時延,并仿真驗證了PBRSBBR 相對于批量分組貪婪傳輸方案(Greedy bundle relaying scheme with bulk bundle release,GBRS-BBR)的優(yōu)勢.在文獻[33]中,Fawaz 等建模并分析了上游RSU 與中游RSU 同時依靠車流向下游RSU 載帶中繼分組的場景,提出了一個能夠緩解存儲飽和度且延遲最小的分組批量發(fā)送方案.Wang 等[10]的研究側重于RSU 向過往車輛發(fā)送數據的下行傳輸問題,在雙向車流中選擇中繼車輛將信息從RSU 轉發(fā)給有下載需求的目的車輛,減少車輛的傳輸中斷時間.

本文針對基于車輛載帶中繼的RSU 突發(fā)業(yè)務分組調度問題,提出一種能使分組端到端時延最小的隨機優(yōu)化策略.該策略根據源RSU 緩存中的分組累積數量和移動車輛的速度狀態(tài)做分組調度決策,能根據突發(fā)業(yè)務量的實時變化,動態(tài)調整分組調度的載帶車輛速度選擇范圍.當突發(fā)業(yè)務到達時,及時增加載帶車輛資源;突發(fā)業(yè)務量過后,再次調整車速選擇范圍,從而保證系統(tǒng)服務質量,實現分組傳輸過程中的平均端到端延時最小化.

2 系統(tǒng)模型

基于車輛載帶中繼的RSU 突發(fā)業(yè)務分組傳輸場景如圖1 所示,高速公路某個路段存在兩個固定RSU 節(jié)點,分別為源節(jié)點 RSU1與目的節(jié)點 RSU2.由于部署位置原因 RSU1不能接入互聯(lián)網,該節(jié)點作為多種傳感器網絡的網關節(jié)點負責將周邊具有突發(fā)性質的監(jiān)測數據轉發(fā)給與骨干網絡相連的RSU2節(jié)點.兩個RSU 間隔距離用 L 表示,該距離遠大于RSU 的無線覆蓋范圍[24-25].相比距離 L,RSU 無線覆蓋范圍可忽略.

圖1 路邊單元突發(fā)業(yè)務分組傳輸調度示意圖Fig.1 The schematic of bursty traffic transmission scheduling between roadside units

RSU-車輛分組隨機調度系統(tǒng)如圖2 所示,突發(fā)業(yè)務分組隨機到達 RSU1,在其緩存中存儲并排隊等待發(fā)送.將系統(tǒng)時間劃分為等長時隙,在某個時隙內,若沒有車輛到達 RSU1,則分組在緩存中排隊等候;若該時隙內有車輛到達,則 RSU1根據分組調度策略確定是否向經過車輛發(fā)送分組,以及發(fā)送的分組數量.

圖2 RSU-車輛分組隨機調度系統(tǒng)Fig.2 The packet scheduling system of RSU-vehicles

2.1 突發(fā)業(yè)務到達模型

假設每個時隙有不同數量的突發(fā)業(yè)務分組隨機到達 RSU1,且分組到達過程是獨立同分布的.突發(fā)業(yè)務可用多狀態(tài)伯努利分布進行描述[34-35].令a[t]=m表示在第 t 個時隙有 m 個分組新到達 RSU1,分組到達過程的概率質量函數表示為

其中,θm∈[0,1]表示a[t]=m,m ∈{0,1,···,M}的概率,由于受到物理限制,M為每個時隙RSU 所能接收周 邊監(jiān)測數據的最大分組個數.則 a[t] 的分布∑滿足且分組平均到達率為

RSU1中的緩存用來存儲尚未傳輸的積壓分組,緩存容量為K 個分組,其中 K=∞和 K＜∞ 分別表示緩存容量無限和有限的情況.第 t-1 個時隙結束時,緩存中的分組個數,即隊列長度,用 q[t] 表示,其狀態(tài)變化為

其中,s[t]∈[0,S]表示 RSU1在第 t 個時隙向到達車輛發(fā)送的分組個數,S 為每個時隙受到物理限制,RSU 所能傳輸的最大分組數量.新到達的分組在該時隙可以立即傳送,故在本系統(tǒng)中不區(qū)分新到達的分組和已存儲在緩存中的分組.因此,可將第 t 個時隙的隊列狀態(tài)等效定義為x[t]=q[t]+a[t],得出

2.2 車輛到達模型

高速公路自由流交通狀態(tài)下,車輛到達RSU1服從參數為λ 的泊松過程.用 T 表示兩車相繼到達RSU1的時間間隔,則 T 服從負指數分布,其概率密度函數為f(t)=λe－λt,t＞0,概率分布函數為F(t)=Pr(T ≤t)=1-e－λt,t ＞0.令系統(tǒng)時隙長度為固定值,用 Δt 表示,則在該時隙內(至少)有1 輛車到達RSU1的概率(即兩輛車相繼到達的時間間隔小于等于 Δt 的概率)為

因此,一個時隙內沒有車到達 RSU1的概率為1-Pa.當時隙足夠小時可確保每個時隙最多有一輛車到達.

2.3 離散車速狀態(tài)模型

令 v[t]表示第 t個時隙到達 RSU1的車輛速度,其中 v[t]=0表示該時隙沒有車輛進入 RSU1覆蓋范圍.假設在RSU 間行駛過程中,車輛速度保持不變,并且對于各個時隙獨立同分布.本文將連續(xù)的車速量化成 W+1個離散的車速狀態(tài):令V=[v1,v2,···,vW+1]為閾值向量,其中,v1=Vmax和vW+1=Vmin分別是車速的上限和下限,且滿足vw＞vw+1,即下標越小代表車速越快.

將第 t 個時隙到達 RSU1的車輛速度狀態(tài)用h[t]表示,其中,h[t]=w,1 ≤w ≤W,表示v[t]∈[vw+1,vw);h[t]=W +1表示該時隙 t 內沒有車輛到達,即 v[t]=0 .車速離散為5 個狀態(tài)的模型如圖3(a)所示,其中,w=1和 w=4 分別表示車速最快與最慢的狀態(tài);w=5表示無車輛到達 RSU1.類似地,W +1個離散車速狀態(tài)模型如圖3(b)所示.

圖3 離散車速狀態(tài)模型Fig.3 Discrete velocity states models

車速處于狀態(tài) w 的概率用 ηw表示,其概率質量函數表達式為

令 v∈[Vmin,Vmax),則車速分布的截斷概率密度函數為[36]

2.4 傳播時延

在車速狀態(tài)模型中將連續(xù)的車速離散為W +1個狀態(tài),則傳播時延也相應的離散為W+1 個狀態(tài).令 Tw表示車速狀態(tài)為w時,RSU1向車輛發(fā)送1 個分組的平均傳播時延,并分以下兩種情況討論:

1)當車速狀態(tài)為w,1 ≤w ≤W 時,速度取區(qū)間中值,該狀態(tài)下發(fā)送1 個分組的平均傳播時延表達式為

顯然,平均傳播時延 Tw與車速成反比,即車速狀態(tài)越好,平均傳播時延越小,即T1＜T2＜···＜TW.

2)當車速狀態(tài)為w=W +1 時,表示沒有車輛到達 RSU1,故不能傳輸分組,此狀態(tài)下平均傳播時延為0,即 Tw+1=0 .

3 馬爾科夫決策框架與時延分析

馬爾科夫決策是用于不確定條件下的決策優(yōu)化模型,描述代理與環(huán)境或系統(tǒng)交互的隨機決策過程[37-38].基于車輛載帶中繼的路邊單元分組調度問題面臨突發(fā)業(yè)務到達時刻與數量的隨機性、車輛到達的隨機性,以及車速的隨機性.本文基于馬爾科夫決策的隨機優(yōu)化方法,提出一個分組調度最優(yōu)策略,該策略能根據突發(fā)業(yè)務量、緩存狀態(tài)的實時變化,動態(tài)、彈性地調整車速狀態(tài)的選擇范圍以最小化端到端分組傳輸時延.本節(jié)通過建立馬爾科夫決策(Markov decision process,MDP)框架對分組傳輸過程中的排隊時延和傳播時延進行分析,并以分組端到端時延最小化為目標,建立一個非線性優(yōu)化問題.

MDP 框架制定如下:上文所描述的分組傳輸系統(tǒng)可由一個5 元組組成.其中,X={0,1,···,K}表示系統(tǒng)狀態(tài)集合,每個狀態(tài)代表 RSU1緩存中的分組隊列長度;N={(m,w)|m ∈{0,1,···,M},w ∈{1,···,W +1}}表示所有可能的分組到達狀態(tài)與車速狀態(tài)的組合,表示系統(tǒng)的不確定性;S={0,1,···,S}表示發(fā)送分組個數的行動集合;P={τk,l|k,l ∈X}表示轉移概率矩陣,其中τk,l=Pr{x[t+1]=l|x[t]=k}表示從時隙 t 到時隙t+1,RSU1緩存中分組隊列長度由 k轉變?yōu)閘 的一步轉移概率;D 表示分組從 RSU1傳輸到 RSU2的平均端到端時延,即MDP 框架中的報酬函數.令表示平均排隊時延,表示平均傳播時延,可得到:

在每個時隙,RSU1根據系統(tǒng)狀態(tài)、車速狀態(tài)做出行動決策.在系統(tǒng)狀態(tài) x[t]=k,車速狀態(tài)h[t]=w的條件下,RSU1向到達車輛發(fā)送 s 個分組的概率用表示,即

系統(tǒng)轉移概率分以下三種情況討論:

1)若時隙 t-1結束時,RSU1緩存中有 k 個分組,且在時隙 t有 i個分組到達 RSU1,并發(fā)送i-m個分組給經過車輛,則 RSU1緩存在時隙 t增加了m個分組,其轉移概率為

其中,k∈[0,K-1],m ∈[1,M] .

2)若時隙 t-1結束時,RSU1緩存中有 k 個分組,且在時隙 t有 i個分組到達 RSU1,并發(fā)送i+s個分組給經過車輛,則 RSU1緩存在時隙 t減少了s個分組,其轉移概率為

其中,k∈[1,K],s ∈[1,S] .

3)若時隙 t-1結束時,RSU1緩存中有 k 個分組,且在時隙 t 緩存中分組個數保持不變的概率為

當 M≤K時,RSU1緩存狀態(tài)的一步轉移馬爾科夫鏈如圖4 所示.

圖4 馬爾科夫鏈模型Fig.4 Markov chain model

馬爾科夫鏈的局部平衡方程為

根據MDP 框架,狀態(tài)轉移概率矩陣用 P 表示,矩陣中第 (i+1,j+1)個元素為τi,j;系統(tǒng)到達穩(wěn)態(tài)時,隊列狀態(tài)為k 的穩(wěn)態(tài)概率用 πk表示,且π=[π0,π1,···,πK]T.因為本系統(tǒng)所建立得馬爾科夫鏈是齊次、不可約且非周期的,所以其穩(wěn)態(tài)概率可以通過ΠP=Π獲得.歸一化方程為:.令f表示參數為的向量,當調度概率已知,則通過解以上方程可得到 πk,所以 πk是f的函數,可表示為πk(f).

根據式(9),在緩存隊列狀態(tài)為x[t]=k,車速為h[t]=w的條件下,時隙 t發(fā)送 s 個分組的平均傳播時延為每個時隙 RSU1發(fā)送分組產生的平均傳播時延為

4 優(yōu)化問題與調度策略

于是,平均排隊時延與平均傳播時延分別可轉化為

本文采用LINGO 軟件中的建模語言對優(yōu)化問題(18)進行描述,利用該軟件中的非線性模型求解器解出該優(yōu)化問題的全局最優(yōu)解分別根據求得最優(yōu)穩(wěn)態(tài)概率和最優(yōu)分組調度參數

對于已知的車速狀態(tài) w和發(fā)送分組個數 s,隊列長度 k 存在一個最優(yōu)門限且滿足s2),即在相同車速狀態(tài) w下,發(fā)送分組數 s 越多,隊列長度門限越大.此時,最優(yōu)傳輸參數的門限結構為

同理,對于已知隊列長度 k和發(fā)送分組個數s,車速狀態(tài)存在一個最優(yōu)門限且滿足s2),即在相同分組隊列長度 k 的條件下,車速狀態(tài)越小(車速越快),發(fā)送分組數 s 越多,車速狀態(tài)門限越小.此時,最優(yōu)傳輸參數的門限結構為

5 仿真分析

本文的仿真分為3 部分.1)通過優(yōu)化問題(18)的最優(yōu)解計算最優(yōu)分組調度參數驗證本文所提出的路邊單元突發(fā)業(yè)務分組調度最優(yōu)策略(Optimal packet scheduling strategy for roadside units＇ bursty traffic,OPSS-RSUs)具有門限結構;2)仿真并做出突發(fā)業(yè)務分組平均排隊時延、平均端到端時延隨平均傳播時延的變化曲線,分析平均排隊時延與平均傳播時延間的折中;3)將本文提出的OPSS-RSUs 方法與貪婪中繼方案GBRSBBR (Greedy bundle relaying scheme with bulk bundle release)、概率中繼方案PBRS-BBR (Probabilistic bundle relaying scheme with bulk bundle release)以及Q-Learning 算法Q-Learning-BBR(Q-learning scheme with bulk bundle release)在平均排隊時延、平均傳播時延以及平均端到端時延三個方面進行對比和分析.

仿真參數設置如表1 所示,其中,速度區(qū)間取[16.67,33.33] m/s,即[60,120] km/h;將連續(xù)車速離散為W+1=5個車速狀態(tài),即 1≤w ≤5,且w越小表示車速狀態(tài)越快,車速狀態(tài) w=5 時表示沒有車輛到達 RSU1.根據式(5),不同車速狀態(tài)的概率取值為[η1,η2,η3,η4,η5]=[0.1259,0.1494,0.1494,0.1259,0.4493].相應地,根據式(8),不同車速狀態(tài)下 RSU1發(fā)送1 個分組的傳播時延為[T1,T2,T3,T4,T5]=[320.0256,369.2421,436.3477,533.2622,0].為便于分析,取 S=2,即 RSU1在每個時隙向到達車輛發(fā)送的分組個數 s∈{0,1,2}.

表1 仿真參數表Table 1 Simulation parameters

5.1 OPSS-RSUs 方法門限結構驗證

本文按分組到達概率 θi的不同分為兩組方案進行仿真,且兩組 θi的取值如表2 所示.其中,方案1 中分組的平均到達率,方案2 中

表2 分組到達參數表Table 2 Packets arrival parameters

圖5 OPSS-RSUs 方法雙門限結構Fig.5 Double threshold structure of OPSS-RSUs

由圖5 可知,調度策略 s 是基于車速狀態(tài) w和分組隊列長度 k 的雙門限結構.在圖5(a)中,當w=3時,根據式(19),有

當 0≤k ＜11時,RSU1發(fā)送0 個分組;當11 ≤k ＜12時,發(fā)送1 個分組;當 k≥12 時,發(fā)送2 個分組.因此,在相同車速狀態(tài)下,分組隊列長度較小時,RSU1不發(fā)送分組以等待速度更快的車輛;當分組累積數量增大到門限值時,RSU1會及時發(fā)送分組,以降低排隊時延.

當 3＜w ≤5時,RSU1發(fā)送0 個分組;當2 ＜w ≤3時,發(fā)送1 個分組;當 w≤2 時,發(fā)送2 個分組.由此可得出結論,在相同分組隊列長度的條件下,車速狀態(tài) w 越大(車速越小),RSU1發(fā)送分組個數越少;反之,發(fā)送分組個數越多.

綜上所述,車速狀態(tài)越好,分組隊列長度越大,則發(fā)送分組數目越多;車速狀態(tài)越差,分組隊列長度越小,則發(fā)送分組數目越少甚至不發(fā)送分組.

當 k=24,s=2 時,方案1 與方案2 車速狀態(tài)的門限值分別出現在車速狀態(tài)3 與車速狀態(tài)4 處,說明在相同的分組隊列長度條件下,分組到達率較小時,該調度策略選取速度較快(w≤3)的車輛發(fā)送分組,放棄車速較慢的車輛(w=4,5).當增大時,分組累積速率加快,該調度策略將擴大發(fā)送分組的車速選擇范圍(w≤4),給速度較慢的車(w=4)也發(fā)送分組,該方法能防止排隊時延的過快增長.

5.2 排隊時延與傳播時延的折中驗證

在優(yōu)化問題式(18)中,將平均傳播時延

如圖6(a)所示,在OPSS-RSUs 方法中,當平均傳播時延較小時,說明 RSU1僅選擇速度較快的車輛發(fā)送分組,故平均排隊時延較高;隨著平均傳播時延逐漸增大,RSU1擴大載帶分組的車速選擇范圍,使得分組傳輸機會增加,平均排隊時延隨之快速下降;當平均傳播時延繼續(xù)增大時,由于分組平均到達率 αˉ 不變,擴大車速選擇范圍對平均排隊時延的影響逐漸減弱,平均排隊時延的下降速率逐漸平緩并趨近于0,即分組到達 RSU1后幾乎立刻發(fā)送給車輛.因此,平均排隊時延與平均傳播時延之間存在折中,且該折中點能使得平均端到端時延最小化.在圖6(b)中,隨著平均傳播時延逐漸增大,平均端到端時延經歷了先降低后增加的過程,驗證了折中點的存在性.

圖6 平均排隊時延和平均端到端時延隨平均傳播時延的變化曲線Fig.6 Changes in average queuing delay and average end-to-end delay as the average propagation delay increases

5.3時延性能對比分析

GBRS-BBR 方法不考慮車輛速度,在緩存中分組個數不為0 的情況下,向每一個經過的車輛均發(fā)送分組,即傳輸參數如下式所示:

PBRS-BBR 方法中,RSU1向第 i 輛車傳輸分組的概率為Pbr,i∈[0,1],根據文獻[25] 中式(4),RSU 給第 i 輛車發(fā)送分組的概率表達式為

其中,μv表示車輛到達率,dSD表示源-目的RSU間隔距離,Vmax表示限定車速的最大值,vi表示第i輛車的速度.由此可知,在車輛到達率 μv為定值的條件下,Pbr,i僅由車速決定,車速越大,Pbr,i越大;反之,Pbr,i越小.因此PBRS-BBR 方法僅能降低分組平均傳播時延,無法對平均排隊時延進行控制.

Q-Learning 是一種無模型的強化學習算法,在該算法中.定義系統(tǒng)狀態(tài) state(k,w),其中k ∈{0,1,···,K},w∈{1,···,W};行動 act 表示發(fā)送分組個數;報酬 r為狀態(tài) state(k,w)且采取行動 act 時,單位時隙所產生的端到端時延,故狀態(tài)-行動報酬矩陣 R 如下式所示:

其中,對某一狀態(tài),非有效行動的報酬為-∞,仿真中設定為-100 000 000.

本文使用 ?-greedy (?-貪婪算法)來保證源路邊單元探索環(huán)境參數及保障數據包調度決策質量.應用 ?-greedy 之后的源路邊單元在進行強化學習決策時,做出在當前車輛速度狀態(tài)和數據包隊列狀態(tài)下進行發(fā)送分組數量的決策.

算法整體步驟如下:

在當前狀態(tài) state(k,w) 的所有行動中選取一個行動act;

算法中 ? 是一個在0和1 之間服從均勻分布的隨機變量,在每次決策之前隨機選取，在每次迭代中 0≤? ≤1 是恒定的探索參數.

本文所提出的OPSS-RSUs 方法以端到端時延最小化為優(yōu)化目標,根據分組排隊數量和車速狀態(tài)兩個因素決定是否給該車發(fā)送分組以及發(fā)送分組的數量.將車輛到達率取固定值 λ=0.55,平均分組到達率的變化范圍取 [0.1,1.0],OSPT-RSUs、GBRSBBR、PBRS-BBR和Q-Learning-BBR 四種分組調度方法的平均排隊時延、平均傳播時延以及平均端到端時延的仿真結果如圖7 所示.

與另外三種方法相比,GBRS-BBR 方法產生的平均排隊時延最小,但平均傳播時延最大,如圖7(a)和圖7(b)所示.GBRS-BBR 方法向所有到達車輛發(fā)送分組,能在最短時間內將分組發(fā)送給車輛,但不對車速進行選擇,其平均傳播時延是RSU1和 RSU2的間隔距離與車速期望值的比值,大小不隨變化.PBRS-BBR 方法中,RSU1向不同車輛發(fā)送分組的概率 Pbr,i與其速度大小成正相關,其平均傳播時延小于GBRS-BBR.當 αˉ 較小時,該方法與Q-Learning-BBR 方法均能通過降低平均傳播時延達到降低端到端時延的目的;當 αˉ 較大時,分組在 RSU1緩存中迅速累積,排隊時延增大,PBRS-BBR和Q-Learning-BBR 方法的端到端時延顯著高于GBRS-BBR 方法和OSPT-RSUs 方法,如圖7(c)所示.對比圖7(c)與圖7(a)和圖7(b)可知,本文所提出的OSPT-RSUs 方法能根據的增大動態(tài)地擴大車速選擇范圍,用較小平均排隊時延的增長換取平均傳播時延的大幅降低,從而使得平均端到端時延顯著小于其他三種方法.

圖7時延隨變化曲線Fig.7 Change of delay with

圖8時延隨 λ 變化曲線Fig.8 Change of delay with λ

隨著車輛到達率 λ 取值由小增大,四種分組調度方法的平均排隊時延均呈下降趨勢,如圖8(a)所示.當車輛到達率 λ 較小時,為防止緩存中分組累積數量過多導致排隊時延過大,OSPT-RSUs 方法會擴大車速選擇范圍增加分組服務率,因此其平均傳播時延較大,且與GBRS-BBR 方法相近,如圖8(b)所示.隨著 λ 不斷增大,分組載帶機會增多,OSPTRSUs 方法能通過不斷優(yōu)化載帶車輛的速度范圍,使得平均傳播時延和端到端總時延逐漸降低,其分組平均端到端時延較GBRS-BBR、PBRS-BBR 以及Q-Learning-BBR 方法有明顯優(yōu)勢,如圖8(c)所示.

6 結論

本文研究了高速公路車聯(lián)網場景下基于車輛載帶中繼的RSU 突發(fā)業(yè)務分組調度問題,提出一種能使分組端到端時延最小的隨機優(yōu)化策略,該策略根據源RSU 緩存中的分組累積數量和移動車輛的速度狀態(tài)做分組調度決策.本文通過受限馬爾科夫決策框架對分組傳輸過程中的狀態(tài)轉移過程進行分析,建立一個非線性平均端到端時延最小化問題并求解.該方法可使得源路邊單元根據突發(fā)業(yè)務到達率的實時變化,動態(tài)、彈性地調整分組調度策略,即動態(tài)調整車速選擇范圍,當突發(fā)業(yè)務量到達時,及時增加載帶車輛資源;突發(fā)業(yè)務量過后,再次調整車速選擇范圍,從而保證系統(tǒng)服務質量,實現分組傳輸過程中的平均端到端延時最小化.