車聯(lián)網(wǎng)中路邊設(shè)施的分布式調(diào)度策略的研究

顧偉 任勇軍

0 引言

車聯(lián)網(wǎng)(Vehicular Ad Hoc Networks,VANETs)已成為智能交通系統(tǒng)(Intelligent Transportation System,ITS)的重要組成部分[1-2].在VANETs(圖1)中，車輛通過安裝車載設(shè)備(On-Broad Units,OBU)[3-4]與其他車輛和路邊設(shè)施(Road Side Unit,RSU)進行通信,其中車與車之間通信簡稱為V2V通信,車與RSU通信簡稱為V2I通信.

圖1 VANETs結(jié)構(gòu)Fig.1 Structure of VANETs

RSU在VANETs中起重要作用.在V2V通信中，RSU為其覆蓋范圍內(nèi)的車輛提供通信服務(wù)，包括轉(zhuǎn)發(fā)消息或者起網(wǎng)關(guān)作用，為其覆蓋范圍內(nèi)的車輛接入外網(wǎng).通過RSU轉(zhuǎn)發(fā)消息，提高了車輛從外網(wǎng)獲取消息的成功率.

若采用有線電網(wǎng)給RSU供電，并沿路部署RSU,這將耗資巨大，不易實現(xiàn).為此，綠色能源供電成為一個可考慮的選擇.由于RSU能夠采集的能量有限，需采用有效的調(diào)度策略，合理地選擇服務(wù)的車輛，進而提高RSU能量的利用率.

因此，為RSU設(shè)計有效的調(diào)度策略是提高RSU能量利用率的關(guān)鍵.文獻[5]提出一種RSU的調(diào)度策略，但不是針對綠色能源供電場景.文獻[6]提出一種新的RSU部署策略，其RSU由電網(wǎng)和太陽能共同供電；同時，該策略還引用了休眠模式，即當RSU無需工作時，就進入休眠狀態(tài)，降低能耗.文獻[7]為了減少RSU的電能消耗，研究了開/關(guān)的休眠周期.文獻[8]考慮綠色能源給RSU供電問題，并研究了在滿足一定約束條件下最大化RSU服務(wù)的車輛數(shù)問題.

本文針對太陽能供電的RSU服務(wù)車輛的調(diào)度問題進行研究，并提出基于Markov 鏈和基于閾值的兩個在線調(diào)度策略，提高了RSU服務(wù)的車輛數(shù).

1 系統(tǒng)模型

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

考慮雙車道的單向道路場景，如圖2所示.車輛進入路段服從均值為λ的泊松分布.令V表示N輛車構(gòu)成的車輛集(V={?1,?2,…,?N})，這些車輛隨機分布于路段上;令R表示部署于路旁的M個RSU集(R={R1，R2，…，RM}).

圖2 單向道路場景Fig.2 One-way road scenario

每輛車在道路上的行駛速度服從在[vmin,vmax]區(qū)間的截斷常態(tài)分布(Truncated Normal Distribution,TND).每輛車向RSU請求的數(shù)據(jù)大小為在[Dmin,Dmax]區(qū)間的均勻分布隨機變量.

RSU僅由綠色能源供電.令hr(t)表示第r個RSURr在時隙t采集的能量，其中r=1,2,…,M.假定采集的能量為太陽能.令kr表示Rr的電池容量.RSU利用電池存儲所采集的能量.令Er(t)表示Rr的電池在時隙t的能量狀態(tài).對于任意時刻，Rr所采集的能量和電池所存儲的能量之和不大于其電池容量，即：hr(t)+Er(t)

1.2 通信模型

僅考慮RSU向車輛傳輸?shù)南滦墟溌?將時間細分為多個時隙，每個RSU為其覆蓋范圍內(nèi)的車輛分配一個時隙.車輛在所分配的時隙內(nèi)行駛并通信.令I(lǐng)表示可用的時隙集，每個時隙的時長為τ.

當車輛在道路上行駛時，車輛向其最近的RSU發(fā)送數(shù)據(jù)請求消息.該消息包含車輛的行駛速度和位置信息.每個RSU依據(jù)車輛的移動信息計算通信能量成本，并據(jù)此給該車輛分配最佳時隙，進而最小化能量消耗.

假定RSU與車輛間通信鏈路服從對數(shù)距離路徑損耗模型[9].依據(jù)式(1)計算Rr與車輛?i(i=1,2,…,N)的能量成本Cr(i,t)：

(1)

式中：Ptx表示Rr在時隙t的傳輸功率；Prx(i,t)表示車輛?i在時隙t的接收功率；d0表示參考距離；dr(i,t)表示Rr與車輛?i在時隙t的距離；γ表示路徑衰減指數(shù)；B表示信道的帶寬；N0表示噪聲功率；Pd0表示在參考距離時的路徑損耗；D表示數(shù)據(jù)率.

2 分布式在線調(diào)度策略

本文提出兩種在線調(diào)度策略：基于Markov 鏈的調(diào)度策略和基于閾值的調(diào)度策略.

2.1 基于Markov 鏈的調(diào)度策略

基于Markov 鏈的調(diào)度策略旨在使多個RSU間的能源管理行為一致.每個RSU依據(jù)其現(xiàn)有的能量和所采集的能量數(shù)據(jù)，并結(jié)合與車輛通信所消耗的能量數(shù)據(jù)，決定服務(wù)于哪輛車.

受文獻[10]的啟發(fā)，采用離散狀態(tài)Markov鏈捕獲RSU可采集能量的變動性和RSU將消耗的能量.先對RSU所采集的能量進行統(tǒng)計，再構(gòu)建控制下行鏈RSU通信的查詢表.查詢表存儲了RSU應(yīng)該采取的最優(yōu)動作.

用有限狀態(tài)Markov鏈表述RSU能量狀態(tài).每個狀態(tài)由一個二元組表示.具體而言，用二元組〈hr(t),Er(t)〉表示Rr的能量狀態(tài)，其中hr(t)表示Rr所采集的能量，Er(t)表示Rr目前電池所存儲的能量.

若Rr采取了動作αr(t)，則Rr的能量狀態(tài)從〈hr(t),Er(t)〉轉(zhuǎn)變?yōu)闋顟B(tài)〈hr(t+1),Er(t+1)〉的轉(zhuǎn)換概率為

P〈hr(t+1),Er(t+1)|〈hr(t),Er(t)〉〉(αr(t))=

P{hr(t+1)|hr(t)}×

P{Er(t+1)|Er(t),hr(t),αr(t)},

(2)

式中：αr(t)表示Rr在時隙t所采集的動作，若αr(t)為零，表示Rr為了保存能量，不為車輛提供服務(wù).

2.1.1 能量采集模型

由于在線調(diào)度策略要實時地決策服務(wù)的車輛，因此需預(yù)測在觀察時間內(nèi)RSU可以采集的能量.本文采用文獻[11]的能量預(yù)測(采集)模型.該模型通過歷史能量數(shù)據(jù)估計在未來可能采集的能量.對RSU采集的能量進行限定( [0,hmax]),hmax表示RSU可采集的最大能量，具體內(nèi)容可參見文獻[11].

2.1.2 電池的能量狀態(tài)

RSU電池能量的狀態(tài)轉(zhuǎn)換取決于與車輛通信時消耗的能量和所采集的能量.在每個時隙，RSU需要估計與車輛通信所消耗的能量.為了簡化表述，將每個RSU的覆蓋區(qū)域劃分為5個層次(Z1,Z2,Z3,Z4,Z5)，如圖3所示.

圖3 RSU覆蓋區(qū)域的層次劃分Fig.3 Hierarchical division of RSU coverage

令Ci表示RSU服務(wù)區(qū)域Zi內(nèi)車輛所消耗的能量，其中i=1,2,3,4,5.Ci的值可以通過式(1)進行計算.在每個時隙，RSU優(yōu)化給最遠的區(qū)域(Z5)進行服務(wù).

2.1.3 調(diào)度策略

調(diào)度策略旨在優(yōu)化RSU通信，使其在避免能量消耗殆盡的基礎(chǔ)上最大化RSU服務(wù)的車輛數(shù).

為了最大化服務(wù)車輛數(shù)，對動作αr(t)進行獎勵.如果Rr能夠與車輛通信，則κ(αr(t))=1；若不能通信，則κ(αr(t))=0.在整個觀察時間T內(nèi)，最大化服務(wù)車輛數(shù)就等價于獲取最大的獎勵.為此，建立目標函數(shù)：

(3)

式中：E(·)表示期望函數(shù).

利用文獻[12]的逆向歸納法(Backward Induction)求解式(3).令K(hr(t)，Er(t))表示從時隙t至?xí)r隙T期望所獲取的最大獎勵，其定義如式(4)和式(5)所示：

K(hr(T+1)，Er(T+1))=0，

(4)

E(K(hr(t+1),Er(t+1)))}.

(5)

將最大化K(hr(t),Er(t))的動作存儲于查詢表中.當通信狀態(tài)和轉(zhuǎn)換概率發(fā)生變化時，就更新此查詢表.一旦完成了查詢表的構(gòu)建，RSU就依據(jù)查詢表選擇所實施的動作.

2.2 基于閾值的調(diào)度策略

基于閾值的調(diào)度策略是依據(jù)服務(wù)于車輛所消耗的能量和RSU現(xiàn)存儲的能量信息進行調(diào)度的.與基于Markov 鏈的調(diào)度策略類似，基于閾值的調(diào)度策略仍假定在觀察時間內(nèi)，RSU能夠預(yù)測其所采集的能量.

具體而言，假定在時隙t，有n輛車向Rr請求服務(wù).令vr={?1,?2,…,?n}表示這n輛車所構(gòu)建的車輛集.不失一般性，假定車輛?i是vr集內(nèi)的任意一輛車，即?i∈vr.Rr先計算服務(wù)于車輛?i時的能量補償因子λr,i(t)：

(6)

式中φr(i,t)表示Rr服務(wù)于車輛?i后剩余的能量與RSU總的電池容量之比，其定義如式(7)所示：

(7)

式中：Er(t)表示Rr現(xiàn)有的能量；Cr(i,t)表示Rr服務(wù)于車輛?i所消耗的能量；kr表示Rr的電池容量.

(8)

圖4 基于閾值的調(diào)度策略的執(zhí)行流程Fig.4 Execution flow of threshold-based scheduling strategy

3 性能分析

3.1 仿真環(huán)境

在Windows 7操作系統(tǒng)，8 GB內(nèi)存，core i7 CPU的PC上進行實驗仿真.道路長度2 km，采用雙向四車道，每個車道方向上部署3個RSU(M=3),每個RSU的覆蓋半徑為400 m.RSU的電池容量kr=100能量單位(Units of Energy,UE),hmax=10 UE.具體的仿真參數(shù)如表1所示.

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

本文將對基于Markov 鏈的調(diào)度策略、基于閾值的調(diào)度策略和文獻[8]算法進行對比分析.為了簡化表述，將基于Markov 鏈的調(diào)度策略、基于閾值的調(diào)度策略和文獻[8]算法分別標記為Markov-Scheduling、Threshold-Scheduling和Reference-[8]進行比較，分析它們的服務(wù)車輛數(shù)性能.選擇服務(wù)車輛數(shù)百分比作為性能指標，且服務(wù)車輛數(shù)百分比等于服務(wù)的車輛數(shù)與總的車輛數(shù)之比.

3.2 閾值ε的選取

圖5給出了閾值ε對Threshold-Scheduling策略的服務(wù)車輛數(shù)的影響.考慮到RSU覆蓋半徑和RSU電池的容量，只能有效地覆蓋幾輛車，所以，ε取值1，5和8進行仿真.

圖5 閾值ε的設(shè)定Fig.5 Setting of the threshold ε

大的閾值允許RSU服務(wù)更多車輛，即使它們有高的能量成本，但是當服務(wù)車輛數(shù)越多，RSUs的能耗速度就越快.相反，小的閾值限制了RSU服務(wù)的車輛數(shù).從圖5可知，相比于ε=1和ε=8，ε=5時RSU服務(wù)于車輛數(shù)最多.因此，在后續(xù)仿真實驗中，ε=5.

3.3 參數(shù)λ對服務(wù)的車輛數(shù)百分比的影響

圖6顯示了服務(wù)的車輛數(shù)百分比隨λ(平均車輛到達率)的變化情況，其中λ在1～3 輛/s變化.從圖6可知，服務(wù)的車輛數(shù)隨λ的增加而下降.因為λ越大，道路上的車輛數(shù)越多.在RSU數(shù)量不變(M=3)的情況下，車輛獲取RSU服務(wù)的機會越少，相應(yīng)地服務(wù)的車輛數(shù)百分比就隨之減少.

圖6 服務(wù)的車輛數(shù)百分比隨參數(shù)λ的變化情況Fig.6 Impact of traffic density on the percentage of served vehicles

圖6還顯示， Markov-Scheduling和Threshold-Scheduling的服務(wù)車輛數(shù)百分比均高于Reference-[8].Reference-[8]算法旨在降低RSU消耗的功率，它更傾向于選擇離RSU近的車輛進行服務(wù)，這就使得離RSU遠的車輛得到服務(wù)的概率下降.

3.4 車輛行駛速度對服務(wù)的車輛數(shù)百分比的影響

圖7為車輛行駛速度對服務(wù)的車輛數(shù)百分比的影響，其中車輛的平均速度為15～35 m/s.從圖7可知，平均速度增加，服務(wù)的車輛數(shù)百分比呈下降趨勢.因為車速越大，網(wǎng)絡(luò)拓撲變化越快，RSU服務(wù)的車輛的時間越短.相比于Reference-[8]算法，Markov-Scheduling和Threshold-Scheduling算法的優(yōu)勢并不明顯.因為Markov-Scheduling和Threshold-Scheduling算法在選擇服務(wù)車輛時，并沒有優(yōu)先服務(wù)車速快的車輛.

圖7 平均車速對服務(wù)車輛數(shù)百分比的影響Fig.7 Impact of average velocity on the percentage of served vehicles

3.5 參數(shù)hmax對服務(wù)車輛數(shù)百分比的影響

圖8給出了hmax對服務(wù)車輛數(shù)百分比的影響.從圖8可知，hmax越大，服務(wù)車輛數(shù)百分比也越大.因為hmax的增加，使RSU的電池電量保持較充足的概率增加，它可以服務(wù)的車輛數(shù)就越大.

圖8 hmax對服務(wù)車輛數(shù)百分比的影響Fig.8 Impact of hmax on the percentage of served vehicles

此外，相比于Reference-[8]，Markov-Scheduling和Threshold-Scheduling隨hmax變化的波動較大.hmax越大，Markov-Scheduling策略和Threshold-Scheduling策略的服務(wù)車輛數(shù)百分比的優(yōu)勢越明顯.

4 結(jié)語

RSU的能量消耗直接影響部署RSU的成本.本文針對面向太陽能供電的RSU，提出兩個分布式的在線調(diào)度策略.該調(diào)度策略最大化了服務(wù)的車輛數(shù).仿真結(jié)果表明，提出的兩個分布式在線調(diào)度策略能夠增加服務(wù)的車輛數(shù).本文僅針對簡單場景進行分析，在仿真階段，也僅考慮了2 km的道路.后期將進一步優(yōu)化所提出的調(diào)度策略，使其適用于復(fù)雜場景.