基于車輛載帶中繼的路邊單元突發(fā)業(yè)務(wù)分組調(diào)度最優(yōu)策略

代 亮 張亞楠 錢(qián) 超 孟 蕓 黃 鶴

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

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

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

1 相關(guān)工作及本文貢獻(xiàn)

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

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

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

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

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

2 系統(tǒng)模型

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

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

RSU-車輛分組隨機(jī)調(diào)度系統(tǒng)如圖2 所示,突發(fā)業(yè)務(wù)分組隨機(jī)到達(dá) RSU1,在其緩存中存儲(chǔ)并排隊(duì)等待發(fā)送.將系統(tǒng)時(shí)間劃分為等長(zhǎng)時(shí)隙,在某個(gè)時(shí)隙內(nèi),若沒(méi)有車輛到達(dá) RSU1,則分組在緩存中排隊(duì)等候;若該時(shí)隙內(nèi)有車輛到達(dá),則 RSU1根據(jù)分組調(diào)度策略確定是否向經(jīng)過(guò)車輛發(fā)送分組,以及發(fā)送的分組數(shù)量.

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

2.1 突發(fā)業(yè)務(wù)到達(dá)模型

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

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

RSU1中的緩存用來(lái)存儲(chǔ)尚未傳輸?shù)姆e壓分組,緩存容量為K 個(gè)分組,其中 K=∞和 K＜∞ 分別表示緩存容量無(wú)限和有限的情況.第 t-1 個(gè)時(shí)隙結(jié)束時(shí),緩存中的分組個(gè)數(shù),即隊(duì)列長(zhǎng)度,用 q[t] 表示,其狀態(tài)變化為

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

2.2 車輛到達(dá)模型

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

因此,一個(gè)時(shí)隙內(nèi)沒(méi)有車到達(dá) RSU1的概率為1-Pa.當(dāng)時(shí)隙足夠小時(shí)可確保每個(gè)時(shí)隙最多有一輛車到達(dá).

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

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

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

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

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

令 v∈[Vmin,Vmax),則車速分布的截?cái)喔怕拭芏群瘮?shù)為[36]

2.4 傳播時(shí)延

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

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

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

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

3 馬爾科夫決策框架與時(shí)延分析

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

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

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

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

1)若時(shí)隙 t-1結(jié)束時(shí),RSU1緩存中有 k 個(gè)分組,且在時(shí)隙 t有 i個(gè)分組到達(dá) RSU1,并發(fā)送i-m個(gè)分組給經(jīng)過(guò)車輛,則 RSU1緩存在時(shí)隙 t增加了m個(gè)分組,其轉(zhuǎn)移概率為

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

2)若時(shí)隙 t-1結(jié)束時(shí),RSU1緩存中有 k 個(gè)分組,且在時(shí)隙 t有 i個(gè)分組到達(dá) RSU1,并發(fā)送i+s個(gè)分組給經(jīng)過(guò)車輛,則 RSU1緩存在時(shí)隙 t減少了s個(gè)分組,其轉(zhuǎn)移概率為

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

3)若時(shí)隙 t-1結(jié)束時(shí),RSU1緩存中有 k 個(gè)分組,且在時(shí)隙 t 緩存中分組個(gè)數(shù)保持不變的概率為

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

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

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

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

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

4 優(yōu)化問(wèn)題與調(diào)度策略

于是,平均排隊(duì)時(shí)延與平均傳播時(shí)延分別可轉(zhuǎn)化為

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

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

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

5 仿真分析

本文的仿真分為3 部分.1)通過(guò)優(yōu)化問(wèn)題(18)的最優(yōu)解計(jì)算最優(yōu)分組調(diào)度參數(shù)驗(yàn)證本文所提出的路邊單元突發(fā)業(yè)務(wù)分組調(diào)度最優(yōu)策略(Optimal packet scheduling strategy for roadside units＇ bursty traffic,OPSS-RSUs)具有門(mén)限結(jié)構(gòu);2)仿真并做出突發(fā)業(yè)務(wù)分組平均排隊(duì)時(shí)延、平均端到端時(shí)延隨平均傳播時(shí)延的變化曲線,分析平均排隊(duì)時(shí)延與平均傳播時(shí)延間的折中;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)在平均排隊(duì)時(shí)延、平均傳播時(shí)延以及平均端到端時(shí)延三個(gè)方面進(jìn)行對(duì)比和分析.

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

表1 仿真參數(shù)表Table 1 Simulation parameters

5.1 OPSS-RSUs 方法門(mén)限結(jié)構(gòu)驗(yàn)證

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

表2 分組到達(dá)參數(shù)表Table 2 Packets arrival parameters

圖5 OPSS-RSUs 方法雙門(mén)限結(jié)構(gòu)Fig.5 Double threshold structure of OPSS-RSUs

由圖5 可知,調(diào)度策略 s 是基于車速狀態(tài) w和分組隊(duì)列長(zhǎng)度 k 的雙門(mén)限結(jié)構(gòu).在圖5(a)中,當(dāng)w=3時(shí),根據(jù)式(19),有

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

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

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

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

5.2 排隊(duì)時(shí)延與傳播時(shí)延的折中驗(yàn)證

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

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

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

5.3時(shí)延性能對(duì)比分析

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

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

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

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

其中,對(duì)某一狀態(tài),非有效行動(dòng)的報(bào)酬為-∞,仿真中設(shè)定為-100 000 000.

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

算法整體步驟如下:

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

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

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

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

圖7時(shí)延隨變化曲線Fig.7 Change of delay with

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

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

6 結(jié)論

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