車聯網場景聯合緩存及內容請求策略①

余 意 李 松 王艷芬

(*中國礦業(yè)大學信息與控制工程學院 徐州 221116)

(**徐州市智能安全與應急協同工程研究中心 徐州 221008)

0 引言

車聯網(Internet of vehicle,IoV)使用無線通信、傳感探測等技術將服務器、路邊單元(road side unit,RSU)和車載單元等設備連接,采集車輛、道路、環(huán)境等信息,通過車與車、車與路、車與人之間的信息交互和共享,使車與基礎設施之間智能協同與配合,最終實現車輛智能化控制、智能交通管控和智能動態(tài)信息服務的一體化網絡[1-2]。

隨著智能網聯汽車數量的快速增長[3],交通信息的不及時傳輸會導致更高頻次的交通擁堵和交通事故,從而降低人們的出行效率[4]。作為5G 通信中的關鍵技術,V2V(vehicle-to-vehicle)通信使得道路上的鄰近車輛可直接建立連接[5],實現車輛在道路上的信息共享,如車輛自身狀態(tài)信息、道路預警和事故調查的信息等。通過在車輛網中引入緩存,車輛將交通狀態(tài)等信息緩存到本地,并經由V2V 通信與其他鄰近車輛共享,既可以實現安全高效的行駛,也能夠有效降低車輛網基礎設施的通信數據量[6]。

文獻[7]將V2V 通信與緩存結合,來有效控制車聯網多跳中的數據流量,減少車輛出行和數據通信的成本;為緩解車聯網下多媒體業(yè)務廣泛應用而給系統(tǒng)帶來的流量負擔和能源消耗,文獻[8]針對V2V、V2R(vehicle-to-RSU)的混合通信模式,提出一種用于信息娛樂服務的能量感知緩存方案,實現了更高的節(jié)能效果和更低的平均訪問延遲。文獻[9]通過評估車輛的社區(qū)相似性和隱私等級設計了一種動態(tài)概率緩存方案并提出了基于內容流行度的緩存部署車輛選擇方案,有效減少平均時延并增加緩存命中率。

隨著智能物聯網設備數量的急劇增長,設備間的社交關系的挖掘與利用逐漸成為無線通信研究中的熱點[10-12]。社交網絡將網絡信息空間與現實信息空間相連接,并產生包含了傳播信息和社交行為等維度的數據,這些數據可用于輔助IoT 設備間的通信。文獻[13]將車聯網與在線社交網絡相結合提出一種用于社交車聯網的信任感知通信架構以保證車輛提供信息的準確度。文獻[14]則基于社交關系提出一種物聯網場景下的安全內容共享方案,避免共享內容被不受信任的用戶攔截,實現內容分發(fā)安全性和用戶體驗的折中。文獻[15]將社交關系應用于車聯網中來預測車輛移動軌跡,從而有效減少了交通堵塞。

車聯網中內容緩存可有效減小RSU 的服務壓力以及節(jié)省車輛的通信資源,但卻增大了車輛的存儲資源消耗;利用社交關系和緩存聯合優(yōu)化車聯網中通信資源和存儲資源消耗的研究相對較少。

受以上研究啟發(fā),本文構建了車聯網場景下的基于社交關系的內容共享模型以權衡車輛的通信資源和存儲資源消耗,在滿足車輛內容獲取請求下,最小化系統(tǒng)的內容獲取代價。將內容獲取代價最小化問題構建成車輛的內容獲取的策略選擇問題,并將策略選擇轉化成一個局部合作博弈,通過分析該博弈的納什均衡,進而提出基于社交關系的局部協作緩存算法(social-based local cooperative caching algorithm,SLCCA)求得系統(tǒng)的內容獲取代價最小下的博弈策略。

1 系統(tǒng)模型

本文構建了車聯網場景下的基于社交關系的內容共享模型,本節(jié)從物理域和社交域2 個維度描述該模型。

1.1 物理域

如圖1 所示的車聯網系統(tǒng)中,該區(qū)域部署有單個RSU,區(qū)域中有N輛車,車輛集合可記為N={1,2,3,…,N},編號0 表示RSU。車輛i∈N 的最大存儲空間記為Ki,系統(tǒng)中的車輛都具備V2V 通信能力。車輛請求獲取的內容包括其他車輛的狀態(tài)信息、路況信息等,這些信息既可以通過V2R 通信鏈路獲取,也可以通過V2V 通信鏈路獲取。為避免V2V 鏈路和V2R 鏈路之間產生同頻干擾,車聯網系統(tǒng)中的V2V 通信使用專有頻譜。

圖1 物理域系統(tǒng)模型圖

車輛可請求的內容集合記為F={1,2,3,…,L},內容f∈F大小為Zf,RSU 有集合F中的所有內容的緩存。在包含τ個時隙的時間段T={t1,t2,…,tk,…,tτ} 內,集合N 中車輛會針對不同內容發(fā)起請求,并且一輛車最多只對一則內容發(fā)起請求。車輛的內容請求狀態(tài)矩陣記為,其中=0 表示在時隙tk車輛i沒有對內容f發(fā)起請求,反之則表示車輛i對內容f發(fā)起了請求。根據歷史記錄,車輛本地緩存有集合F中的一部分,車輛在時隙tk的內容緩存狀態(tài)矩陣記為,其中=0表示車輛i在時隙tk未緩存內容f,反之則表示車輛i緩存有內容f。

假設車輛在時間段T內不會出現大幅度位置變化,時隙tk內車輛i的地理位置坐標記為,車輛i和車輛j間地理距離由式(1)計算。

V2V 的最大通信距離記為dth,若≤dth,稱車輛i和車輛j互為鄰居車輛,則車輛i可與車輛j建立V2V 連接。時隙tk下車輛i的鄰居車輛中緩存有內容f的車輛集合記為,一個時隙里一輛車至多只能與一輛車建立V2V 連接。

如果車輛i緩存有內容f,則車輛無需向其他車輛或RSU 請求該內容;如果車輛i未緩存內容f,車輛i可從緩存有該內容的鄰居車輛或RSU 處獲取該內容。

1.2 社交域

車輛獲取到請求內容需要付出一定的代價,包括通信資源和存儲資源消耗。由于自身資源的有限性,車輛的使用者具有理性和自私的特點,并不會主動貢獻自己的通信資源或存儲資源。將社交關系引入到車聯網中可激勵具有緊密社交關系的車輛間建立連接并進行內容共享,還能通過分析車輛間的社交行為實現信任管理,以保證內容共享過程的可靠性。本文系統(tǒng)模型中的車輛社交屬性包括內容偏好程度、親密度、路徑相似度和信譽度。

車輛獲取到請求內容付出的代價與車輛對內容的偏好程度有關,若車輛i對內容f感興趣,則車輛i認為獲取到內容f更有價值。車輛i在時隙tk內對內容f的偏好程度服從齊夫分布,即式(2),車輛對內容的偏好程度記為矩陣。

親密度描述了車輛間的聯系強度,根據歷史記錄,在過去δ個時間段里,車輛i和車輛j之間的連接次數記為CTij,δ,第q次連接所持續(xù)的時長記為CDij,δ,q,q≤CTij,δ。時隙tk內,車輛i和車輛j間的親密度由式(3)計算[16]。

路徑相似度可用于表示車輛感興趣內容之間的相似性。車輛的路徑由一系列按時間排序的位置組成,δ個時間段里車輛i的路徑記為Tri,δ={(Li,1,t1),(Li,2,t2),…,(Li,h,th),…,(Li,δ,tδ)},(Li,h,th) 表示車輛i在時刻th時的位置Li,h。時隙tk內,車輛i和車輛j間的路徑相似度由式(5)計算[17]。

其中,‖·‖為兩點坐標的歐氏距離。

信譽度描述了車輛之間可信任程度,為提高獲取內容的安全性以及內容共享成功率,車輛通常選擇與信譽度高的車輛建立V2V 連接。時隙tk內,車輛i對車輛j的信譽度通過式(6)計算[16]。

其中,SRij,δ表示過去δ個時間段內車輛j向車輛i傳輸內容的成功率,可用式(7)描述。

其中,CSij,δ表示車輛j成功將車輛i請求的內容發(fā)送給車輛i的次數。

綜合考慮上述3 個維度的社交屬性,車輛i和車輛j之間的社交強度sij由式(8)定義。

其中,ω1、ω2和ω3分別是3 個維度社交屬性的權重,且ω1+ω2+ω3=1。

2 問題構建

在上述車聯網內容共享模型中,由于在內容獲取時需要占用相應通信資源和存儲資源,每輛汽車在獲得內容時需要付出一定的代價,系統(tǒng)中車輛的內容獲取總代價取決于車輛社交屬性、車輛的內容緩存狀態(tài)以及獲取內容方式。在上述模型中,車輛i有3 種內容請求方式。

(1)車輛i本地緩存有內容f,其無需建立通信鏈路請求該內容,內容獲取代價=0。

(2)車輛i與RSU 建立V2R 連接,車輛i需要付出從RSU 獲取內容的通信代價,若車輛i選擇將內容緩存在本地,則還需要付出內容存儲代價。

車輛與RSU 間的地理距離越小,意味著車輛獲取內容的通信代價越低。為了簡單起見,本節(jié)中的通信代價可認為是由于路徑損耗帶來的代價,記通信距離d帶來的路徑損耗為F(d),單位路徑損耗下的通信成本記為BL,那么通信距離d帶來的通信代價可記為F(d)·BL。在該方式下,車輛i從RSU獲取內容的通信代價可以建模為·BL。

車輛i對內容f的緩存選擇記為∈{0,1},=0 表示車輛i選擇不緩存內容f到本地,反之表示緩存到本地。記單位容量大小內容的緩存放置成本為α,車輛i將內容f緩存至本地的存儲代價表示為Zfα。

考慮到上述車輛對不同內容有不同的偏好,車輛i的內容獲取代價可用式(9)計算。

(3)車輛i與車輛j∈建立V2V 通信,車輛i需要付出與車輛j進行V2V 通信的代價,若車輛i選擇將內容緩存在本地,則還需要付出存儲代價。在該方式下,車輛i的V2V 通信代價與車輛之間的地理距離和社交強度相關。根據式(1)和式(8),結合車輛地理距離和社交關系,車輛i和車輛j之間的社交加權距離可由式(10)計算。

由式(10)可知,當車輛間的地理距離越小或社交關系越緊密時,越小,意味著車輛獲取內容的通信代價越小。根據前面分析,車輛i從RSU 獲取內容的通信代價建模為·BL。

考慮到車輛對不同內容有不同的偏好,車輛i的內容獲取代價可用式(11)計算。

依據式(9)、(11),車輛i獲取到內容f的內容獲取代價可用式(12)計算。

本文的優(yōu)化問題定義為最小化時間T內系統(tǒng)的總內容獲取代價,用式(13)表示。

其中限制條件式(13.3)表示所有內容占用的存儲空間不得超過車輛自身的存儲空間大小。如果自身的存儲空間不足以容納請求的新內容,則通過最近最少使用(least recently used,LRU)算法進行內容更新[18]。

由式(12)可知,鄰居車輛的緩存狀態(tài)會影響車輛i在時隙tk的選擇。若有較多的鄰居車輛有內容f的緩存,車輛i可以選擇與更多不同的車輛建立V2V 通信,相應可減少系統(tǒng)的內容獲取代價;反之車輛i在tk時的策略也會影響其他車輛的選擇,從而影響系統(tǒng)的內容獲取代價。為最小化車輛在時間段T內的內容獲取代價之和,車輛之間需要進行協作緩存,部分車輛貢獻自身的存儲資源將請求的內容緩存在本地,使得其他車輛可經由V2V 通信獲取到請求的內容,以權衡系統(tǒng)下車輛的通信資源消耗和存儲資源消耗。

優(yōu)化問題式(13)是一個NP-hard 問題[19]。本文將上述基于社交屬性的車輛間協作緩存問題建模成基于社交屬性的協作緩存博弈問題,并將時間段T分為博弈過程、內容獲取與共享過程,車輛作為博弈的參與者決定獲取請求內容的途徑以及是否將請求的內容保存到本地,在時間段T的前若干個時隙里通過多輪博弈得到優(yōu)化問題式(13)的最優(yōu)策略集。

3 局部協作緩存方案

3.1 協作緩存博弈

由上述分析可知,車輛i獲取內容f時的決策既包含從何處獲取,也包含是否將內容緩存到本地。記該博弈為G={N,S,u},其中N是參與博弈的所有車輛的集合;S是所有參與博弈的車輛的策略集合,車輛i獲取內容f的策略記為si,f=(Ci,f,Gi,f),S={si|i∈N},si={si,f|f∈F};u是參與博弈車輛的效用函數。

由式(12)可知,在決策si下,車輛i的內容獲取代價之和costi可用式(14)表示。

考慮到車輛間的協作,對于車輛i、策略為si下的效用函數ui定義為自身的內容請求代價和其鄰居車輛的內容請求代價之和。

式(15)中等號右側第2 部分表示車輛i的鄰居車輛的內容請求代價之和。

優(yōu)化問題式(13)可轉化為在博弈階段求得一個策略集合,使得所有車輛的效用函數之和最小,即優(yōu)化如下問題:

3.2 納什均衡分析

在上述博弈G中,對于任意車輛i∈N,優(yōu)化問題式(16)下整體最優(yōu)策略中車輛i的策略記為,如果車輛i單方面將自己的策略由改為而無法提升自己的效用,即式(17)無法成立,則博弈G的策略是一個純策略的納什均衡。

滿足式(18)的博弈稱為嚴格勢力場博弈,其中Φ(·) 是博弈的勢函數,文獻[20]表明嚴格勢力場博弈至少存在一個純策略的納什均衡點。

對于上述博弈G,構造勢函數Φ(·),用式(19)表示。

車輛i將其策略由改為,且,那么勢函數的變化量可用式(20)表示。

由式(18)可知,上述博弈G是一個嚴格勢力場博弈,因此該博弈至少存在一個納什均衡點,且在有限策略集合下,勢函數最小值點就是純策略納什均衡。

3.3 求解算法

根據上述討論與分析,針對建模的基于社交屬性的協作緩存博弈,受文獻[21]啟發(fā),本文提出基于社交關系的局部協作緩存算法。在初始化階段,所有的車輛先默認自己的策略為從RSU 獲取到請求內容并且不緩存請求內容,且將t1時隙的相關參數作為初始化參數,具體為。決策迭代過程分為3 個階段:第1 階段為車輛選擇,在這一階段中車輛i都是按照1/N的概率隨機選擇,選擇車輛后計算車輛i在第l次博弈中的代價costi(l) 和效用函數值ui(l);第2 階段為策略探索階段,車輛i主動隨機產生新策略,其他車輛被動更改策略,若車輛i在新策略下不緩存內容到本地,那么其他從車輛i獲取內容的車輛將策略更改為從RSU 獲取且不緩存到本地,根據式(12)和式(15),車輛i確定新策略下的效用函數值;第3 階段為策略更新階段,在這一階段中,車輛i按照式(21)、式(22) 和式(23)對其策略進行更新,式中β為調節(jié)因子,并更新本次迭代時的緩存狀態(tài)矩陣Cl。

上述算法描述如算法1 所示。

本文SLCCA 算法的復雜度取決于單個車輛的鄰居車輛數量。最差的情況下,所有的車輛都互相為鄰居車輛,且對于任意車輛i,ci,f=0,ri,f=1,?f∈F,在最多有N輛汽車和L個請求內容的情況下,車輛i請求的內容最多有2N種策略,上述算法的最差時間復雜度為O(LN2);最好的情況下,對于任意車輛i,其鄰居車輛集合為空,即沒有鄰居車輛,那么上述算法的最好時間復雜度為O(LN);平均情況下,對于任意車輛i,有輛車是其鄰居車輛,在有L個請求內容情況下,車輛i請求的內容最多有2N種策略,那么上述算法的平均時間復雜度也為O(LN2)。

4 仿真結果與分析

本節(jié)對上述提出的SLCCA 算法進行了仿真實驗和性能分析。仿真實驗中,路徑損耗模型簡化為F(d)=d-α,α為路徑損耗指數并設置為4,RSU 的覆蓋半徑為300 m,車輛總數量為20～50 輛,車輛存儲空間均為100 MB,單個請求內容大小均為5 MB,最大V2V 通信距離為90～150 m,3 個維度社交屬性的權重均為1/3,單位路徑損耗的通信成本為0.1,內容緩存放置成本為0.5。仿真過程中將本文策略與RSU 策略、隨機緩存和貪婪緩存等方案進行對比。

RSU 策略:若車輛的本地沒有請求內容的緩存,則與RSU 建立V2R 連接獲取請求內容,并且獲取的內容不緩存到本地。

隨機策略:所有車輛等概率隨機選擇獲取請求內容的策略,可以選擇V2V 通信獲取到請求的內容,也可以從RSU 獲取到請求的內容,車輛是否將請求內容緩存到本地也是等概率隨機的。

貪婪策略:所有車輛只考慮最小化自身的請求代價而不考慮系統(tǒng)整體的請求代價。

圖2 描述了不同策略下車輛的平均內容獲取代價與不同車輛數量之間的變化關系,其中V2V 最大通信距離dth=120 m。在RSU 策略下,車輛只能與RSU 建立V2R 連接獲取到請求內容并且不緩存到本地,隨著車輛數量的增加,車輛的平均內容獲取代價也會增加。在隨機策略下,車輛對獲取內容途徑和內容緩存的選擇都是隨機的,但車輛選擇到整體最優(yōu)策略概率較小,車輛平均內容獲取代價整體隨著車輛數量的增加而增加。在貪婪策略下,每輛車僅針對自身的內容獲取代價做出最優(yōu)選擇,部分車輛選擇從RSU 獲取,部分車輛從鄰居車輛經由V2V獲取,且獲取的內容不緩存到本地。隨著車輛數量的增加,本地有請求內容緩存的車輛數量會增加,車輛平均請求代價整體以較緩趨勢增加。在本文策略下,車輛不僅會考慮自身的內容獲取代價,也會考慮整體內容獲取代價而選擇性地將內容緩存到本地,其他車輛可經由V2V 通信獲取到請求內容。隨著車輛的增加,選擇緩存請求內容到本地的車輛會增加,因此車輛平均內容獲取代價隨著車輛數量的增加而增加。仿真結果表明,在相同車輛數量下,相較于其他3 種策略,本文策略的性能有優(yōu)勢。

圖2 車輛平均內容獲取代價-車輛數量

圖3 描述了不同策略下車輛的平均內容獲取代價與不同的V2V 通信距離之間的變化關系,其中車輛數量N=50。在RSU 策略下,車輛只與RSU 建立V2R 連接獲取請求內容,在車輛數量固定下,車輛的平均內容獲取代價不隨V2V 通信距離變化而變化。在隨機策略下,車輛的請求內容獲取途徑和請求內容的緩存都是隨機的,車輛平均請求代價本沒有明顯變化規(guī)律,但隨著V2V 通信距離的增加,向其他車輛請求建立連接時有更高幾率獲取到請求內容,車輛的平均內容獲取代價隨之減少。在貪婪策略下,車輛僅針對自身內容獲取代價做出最優(yōu)選擇,隨著V2V 通信距離的增加,可與其他車輛共享本地緩存內容的車輛的數量也會增加,車輛的平均內容獲取代價隨之減少。在本文策略下,車輛的策略選擇同時考慮自身內容獲取代價和整體內容獲取代價,部分車輛通過選擇緩存請求內容到本地,隨著V2V 通信距離增加,可共享給其他車輛,車輛的平均內容獲取代價隨著V2V 通信距離增加而減小。仿真結果表明,在相同V2V 通信距離限制下,相較于其他3 種策略,本文策略的性能有優(yōu)勢。

圖3 車輛平均內容獲取代價-最大V2V 通信距離

圖4 描述了本文策略下車輛的平均內容獲取代價與博弈次數之間的變化關系,其中車輛數量N=50,V2V 最大通信距離dth=120 m。隨著博弈次數的增加,車輛逐步做出更有利于減小車輛平均內容獲取代價的策略,一定次數博弈后,車輛的平均內容獲取代價不會隨著博弈次數的增加而改變。理論分析和仿真結果表明本文策略有較好的收斂性。

圖4 車輛平均內容獲取代價-博弈次數

表1 描述了不同策略的平均時間耗費,其中測試環(huán)境為AMD Ryzen 7 4800U Windows10,軟件版本為Matlab 2021a,V2V 最大通信距離dth=120 m,車輛數量N=20,測試次數為50 次。在RSU 策略下,車輛只與RSU 建立V2R 連接獲取請求內容,因此得到結果只需要耗費極少的時間。在隨機策略下,車輛的請求內容獲取途徑和請求內容的緩存都是隨機的,因此得到結果只需要耗費較少的時間。在貪婪策略下,車輛僅針對自身內容獲取代價做出最優(yōu)選擇,因此得到結果也只需要耗費較少的時間。在本文策略下,車輛的策略選擇需要同時考慮自身內容獲取代價和整體內容獲取代價,得到結果需要耗費較多的時間。但由圖2 和圖3 仿真結果可知,本文策略是在時間耗費和性能上的折中。

表1 不同策略的平均時間耗費

5 結論

為應對智能網聯汽車場景下的大數據量和海量連接等特點,實現安全高效的行駛以及降低核心網的數據流量,本文構建了車聯網場景下的內容共享模型。建模了基于車輛社交關系的內容獲取代價最小化問題,通過優(yōu)化車輛選擇獲取請求內容的途徑以及是否將請求內容緩存到本地來減小車輛的平均內容獲取代價。將建模的優(yōu)化問題轉化為車輛間的局部協作緩存博弈問題,通過分析博弈的納什均衡,提出基于社交關系的局部協作緩存算法求得優(yōu)化問題的最優(yōu)解。仿真結果表明,本文提出的基于社交關系的局部協作緩存算法可有效降低系統(tǒng)的平均內容獲取代價。