王朝煒，王天宇，劉 婷，王衛(wèi)東

(1.北京郵電大學(xué) 電子工程學(xué)院，北京 100876；2.泛網(wǎng)無(wú)線通信教育部重點(diǎn)實(shí)驗(yàn)室，北京 100876)

0 引言

6G移動(dòng)網(wǎng)絡(luò)有望成為一個(gè)內(nèi)生智能、高動(dòng)態(tài)、超密集的異構(gòu)網(wǎng)絡(luò)，以極低延遲和高速數(shù)據(jù)傳輸實(shí)現(xiàn)萬(wàn)物互聯(lián)。6G關(guān)鍵技術(shù)進(jìn)一步推進(jìn)車聯(lián)網(wǎng)應(yīng)用于大規(guī)模車路協(xié)同業(yè)務(wù)場(chǎng)景，進(jìn)一步提升交通系統(tǒng)效率。車聯(lián)網(wǎng)使用車輛對(duì)基礎(chǔ)設(shè)施(V2I)通信,為導(dǎo)航、游戲、XR視頻流、網(wǎng)絡(luò)緩存和移動(dòng)群感知等交通安全外的應(yīng)用提供互聯(lián)網(wǎng)服務(wù)[1]。信息娛樂(lè)應(yīng)用依賴蜂窩基礎(chǔ)設(shè)施與互聯(lián)網(wǎng)交互，此類數(shù)據(jù)密集型應(yīng)用程序?yàn)檐囕v用戶提供額外的信息和娛樂(lè)，并收集城市傳感數(shù)據(jù)用于各種用途。車輛和車載應(yīng)用數(shù)量的增加將產(chǎn)生巨大的數(shù)據(jù)流量并導(dǎo)致蜂窩網(wǎng)絡(luò)擁塞和授權(quán)頻譜緊缺[2-3]。網(wǎng)絡(luò)運(yùn)營(yíng)商可以將這些高吞吐量數(shù)據(jù)流量卸載到其他基礎(chǔ)設(shè)施[4]。

部署在交通路口的路側(cè)設(shè)備(Road Side Unit,RSU)是用于機(jī)會(huì)式數(shù)據(jù)卸載的理想基礎(chǔ)設(shè)施。RSU的作用類似于無(wú)線接入點(diǎn)(Access Point,AP)，利用IEEE 802.11ad/ay等Wi-Gig技術(shù)以60 GHz的中心頻率為多個(gè)客戶端同時(shí)提供速率超過(guò)4 Gb/s的點(diǎn)對(duì)點(diǎn)寬帶鏈路，幫助車輛卸載娛樂(lè)信息應(yīng)用程序的數(shù)據(jù)流量[5-6]。6G D2D技術(shù)的演進(jìn)使得Wi-Gig和基于蜂窩網(wǎng)的車用無(wú)線通信技術(shù)(C-V2X)的集成成為可能，可將大量數(shù)據(jù)流量從授權(quán)頻譜卸載到免費(fèi)頻譜，有望支持比5G顯著提高的數(shù)據(jù)速率[7]，使利用Wi-Gig技術(shù)的RSU數(shù)據(jù)卸載成為可行的解決方案。車輛停留在紅綠燈或停車場(chǎng)等區(qū)域并進(jìn)入RSU服務(wù)范圍內(nèi)時(shí)，移動(dòng)網(wǎng)絡(luò)運(yùn)營(yíng)商通過(guò)RSU進(jìn)行數(shù)據(jù)卸載[7]。在通信和計(jì)算能力有限的情況下，有效地調(diào)度網(wǎng)絡(luò)中資源的使用以達(dá)到最佳利用率，支持邊緣計(jì)算的RSU沿道路部署，以向車輛提供數(shù)據(jù)帶寬和計(jì)算卸載，該方案緩解了頻譜受限蜂窩系統(tǒng)中的資源占用[8]。部署和維護(hù)RSU的成本很高，RSU的規(guī)劃和使用至關(guān)重要。

目前,針對(duì)RSU部署方法的研究包括：Ni等[9]提出的RSU服務(wù)區(qū)概念，將鄰近街道的車聯(lián)網(wǎng)數(shù)據(jù)流量任務(wù)劃分給相應(yīng)的RSU，考慮了RSU的服務(wù)能力和車間傳輸時(shí)延，利用基于線性規(guī)劃的聚類算法，協(xié)同解決RSU在城市環(huán)境中的部署和任務(wù)分配；Kim等[10]考慮了3種不同類型的RSU部署方法(靜態(tài)、移動(dòng)和可控)，分別采用RSU、私人車輛和可控公共交通車輛部署車聯(lián)網(wǎng)通信設(shè)備，最大化它們的時(shí)空覆蓋(Space-Time Conservation,STC)。以上研究并未全面考慮車聯(lián)網(wǎng)中車輛的移動(dòng)狀態(tài)。通過(guò)對(duì)城市車輛數(shù)據(jù)集的分析發(fā)現(xiàn)：車輛并非時(shí)刻處于運(yùn)動(dòng)狀態(tài)中，而時(shí)常處于等紅綠燈、靠邊停車、低速行駛狀態(tài)中。本文重點(diǎn)利用車輛在路口等運(yùn)動(dòng)速度較低的情況，利用RSU進(jìn)行數(shù)據(jù)卸載的可行性，分析了將RSU布置在路口時(shí)，數(shù)據(jù)卸載的效率。

另一方面，車聯(lián)網(wǎng)中的數(shù)據(jù)卸載機(jī)制的研究包括：Raja等[1]設(shè)計(jì)了一種基于下一代車聯(lián)網(wǎng)的智能車聯(lián)網(wǎng)架構(gòu)，設(shè)計(jì)了基于SDN控制器的流量分類方法和基于反饋的智能數(shù)據(jù)卸載機(jī)制，將非車輛安全相關(guān)的數(shù)據(jù)流量分類并卸載到合適的RSU；Si等[11]提出了DAVE,考慮到車聯(lián)網(wǎng)數(shù)據(jù)卸載延遲容限的路由機(jī)制，將延遲容忍數(shù)據(jù)流量卸載到鄰近車載網(wǎng)絡(luò)；Wang等[12]提出了一種基于云/邊緣/霧計(jì)算的車聯(lián)網(wǎng)架構(gòu)的新分類方法；Fan等[13]研究了 C-V2X網(wǎng)絡(luò)的流量卸載問(wèn)題，提出了一種智能軟件定義的 C-V2X 網(wǎng)絡(luò)框架，通過(guò)將網(wǎng)絡(luò)數(shù)據(jù)平面與控制平面解耦來(lái)實(shí)現(xiàn)靈活且低復(fù)雜度的流量卸載，在數(shù)據(jù)平面上，蜂窩流量卸載和車輛輔助流量卸載是聯(lián)合進(jìn)行的。在控制平面，部署深度學(xué)習(xí)，降低軟件定義網(wǎng)絡(luò)(Software Defined Network,SDN)控制復(fù)雜度，提高流量的分流效率；Huang等[14]設(shè)計(jì)了一種基于移動(dòng)邊緣計(jì)算的k-hop遠(yuǎn)程卸載代理機(jī)制，當(dāng)有k-hop V2V路徑可以連接車輛和前方的RSU時(shí)，可以啟用V2I卸載，當(dāng)車輛已經(jīng)離開(kāi)對(duì)應(yīng)RSU的信號(hào)覆蓋范圍時(shí)，如果有k-hop V2V路徑可以將車輛與后方的RSU連接進(jìn)行V2I卸載；Gao等[15]設(shè)計(jì)了一種考慮到時(shí)延限制的基于概率的移動(dòng)數(shù)據(jù)卸載機(jī)制。以上研究較少考慮車聯(lián)網(wǎng)應(yīng)用的延遲容忍特點(diǎn)，并非所有車聯(lián)網(wǎng)應(yīng)用都需要實(shí)時(shí)的數(shù)據(jù)傳輸，一些傳感數(shù)據(jù)與云存儲(chǔ)數(shù)據(jù)實(shí)時(shí)性要求較低。本文分析了車聯(lián)網(wǎng)中車輛接入RSU的平均時(shí)間，研究了車聯(lián)網(wǎng)應(yīng)用的傳輸延遲時(shí)限的容忍程度。依據(jù)數(shù)據(jù)卸載的效率、傳輸時(shí)延的容忍度等參數(shù)對(duì)RSU的部署位置或設(shè)備的啟用進(jìn)行動(dòng)態(tài)調(diào)整，是本文的研究重點(diǎn)。

本文首先將上述場(chǎng)景建模，針對(duì)V2I數(shù)據(jù)業(yè)務(wù)面臨的問(wèn)題，分析了車聯(lián)網(wǎng)中RSU的利用率和接入等待時(shí)間，對(duì)RSU的部署位置進(jìn)行選擇。將RSU部署問(wèn)題證明為一個(gè)NP-hard問(wèn)題，然后設(shè)計(jì)了一種改進(jìn)的貪婪算法得出RSU部署方法，利用真實(shí)GPS 數(shù)據(jù)集仿真驗(yàn)證，最后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，總結(jié)全文并展望未來(lái)工作趨勢(shì)。

1 系統(tǒng)模型

城市交通干線路口是RSU部署的理想位置,最能適應(yīng)車載數(shù)據(jù)卸載的高吞吐量和延遲容忍特性。由于道路中車輛速度過(guò)快，分布不均勻，車輛遵循的機(jī)會(huì)式傳輸模式被稱為“存儲(chǔ)-轉(zhuǎn)發(fā)”模式，利用車輛移動(dòng)帶來(lái)的相遇機(jī)會(huì)實(shí)現(xiàn)通信的自組織網(wǎng)絡(luò)，具有一般DTN網(wǎng)絡(luò)傳輸特征，利用RSU的機(jī)會(huì)式通信可以為車輛提供Internet訪問(wèn)和商業(yè)應(yīng)用等[16]。車聯(lián)網(wǎng)數(shù)據(jù)卸載場(chǎng)景示意如圖1所示，RSU可以覆蓋并為相對(duì)靜止的車輛提供無(wú)線接入。當(dāng)車輛在紅綠燈處短暫停車時(shí)，車載信息娛樂(lè)應(yīng)用程序會(huì)通過(guò)最近的RSU執(zhí)行點(diǎn)對(duì)點(diǎn)數(shù)據(jù)傳輸。

圖1 車聯(lián)網(wǎng)數(shù)據(jù)卸載場(chǎng)景示意

網(wǎng)絡(luò)模型：城市場(chǎng)景可以被建模為一張圖G= {V,E},圖的節(jié)點(diǎn)代表城市道路的交叉路口，圖的邊代表連接各個(gè)路口的道路。V={vi:i= 1,2,…,I}表示節(jié)點(diǎn)的集合，E= {ei:i= 1,2,…,J}表示邊的集合。圖中的節(jié)點(diǎn)和邊的總數(shù)分別是I和J。

U= {ui:i= 1,2,…,M}表示M輛車的集合，T={ti:i= 1,2,…,N}表示N個(gè)時(shí)間段。L(U)是一個(gè)由M輛車在N個(gè)時(shí)間點(diǎn)上的地理坐標(biāo)組成的矩陣。例如,lij表示車輛ui在j時(shí)刻的地理坐標(biāo):

(1)

在所有路口都布放RSU不現(xiàn)實(shí)也不經(jīng)濟(jì)，RSU部署算法應(yīng)從所有路口的集合中選出一部分用于部署RSU。集合R= {ri:i= 1,2,…,K}表示部署算法選中的RSU的坐標(biāo)。集合R中的元素會(huì)隨著部署算法的迭代而改變，R?V，K≤I。

(2)

例如，車輛ui的網(wǎng)絡(luò)訪問(wèn)狀態(tài)將被其駕駛路徑中遇到的RSU影響。車輛ui的網(wǎng)絡(luò)訪問(wèn)狀態(tài)將被記錄為一個(gè)0-1序列，如LR(ui)=[0 1 1 … 0]。

時(shí)間線示意如圖2所示，以進(jìn)一步闡明網(wǎng)絡(luò)狀態(tài)階段。灰色和空白線框分別代表服務(wù)時(shí)間和等待時(shí)間。箭頭線代表該服務(wù)期間卸載的數(shù)據(jù)包。等待超出容限的數(shù)據(jù)包將被丟棄。

圖2 車輛網(wǎng)絡(luò)狀態(tài)時(shí)間線示意

傳輸模型：考慮到車聯(lián)網(wǎng)場(chǎng)景的延遲容忍特征，研究了等待時(shí)延，將TL作為數(shù)據(jù)卸載等待時(shí)間的限制[15]。車載應(yīng)用的平均數(shù)據(jù)生成率為d0，通過(guò)RSU的數(shù)據(jù)卸載率為σ。

(3)

部署算法通過(guò)調(diào)整場(chǎng)景中RSU的位置來(lái)改變?chǔ)伺cμ的比例。當(dāng)λ增加時(shí)，車輛更有可能遇到RSU。當(dāng)μ減小時(shí)，車輛在RSU通信范圍內(nèi)停留的時(shí)間更長(zhǎng)。

(4)

當(dāng)式(4)中的2個(gè)項(xiàng)目大小相似時(shí)，數(shù)據(jù)卸載的質(zhì)量最好。在這種情況下，車輛每個(gè)階段的數(shù)據(jù)量剛好等于該階段可以卸載的數(shù)據(jù)量，數(shù)據(jù)丟失或延遲的概率最小，成本會(huì)在合理范圍內(nèi)。

UR的期望值為：

(5)

P= {pi:i= 1,2,…,I}表示在每個(gè)路口部署RSU的成本。成本受很多方面的影響，包括基本成本、維護(hù)成本和交叉口的擁堵程度。成本集P與路口集V之間存在一一對(duì)應(yīng)關(guān)系，主要從路口的交通量和道路拓?fù)浣Y(jié)構(gòu)估計(jì)。

歸一化目標(biāo)函數(shù)反映了部署算法對(duì)RSU利用率和數(shù)據(jù)卸載延遲的影響。通過(guò)適當(dāng)部署RSU來(lái)改變車輛的通信狀態(tài)，該函數(shù)的值將會(huì)增加。

F(R)=UR/Tw。

(6)

定義2(RSU部署問(wèn)題)：從給定的一組路口中選擇其中一組子集來(lái)部署RSU，以最大化目標(biāo)函數(shù)并服從預(yù)算約束B(niǎo)。

給定：I個(gè)候選路口，V={vi:i= 1,2,…,I}和對(duì)應(yīng)的開(kāi)銷P= {pi:i= 1,2,…,I}，N個(gè)時(shí)間點(diǎn)T= {ti:i= 1,2,…,N}。

目標(biāo)：選出集合R= {ri:i= 1,2,…,K}用于部署RSU，R?V，K≤I，使得F(R)最大。

限制條件：P(R)≤B。

2 RSU部署算法

理論證明：本文提出的問(wèn)題是在有限的成本范圍內(nèi)選擇一組合適的位置來(lái)部署RSU，以實(shí)現(xiàn)更好的數(shù)據(jù)卸載效率，可以證明這是一個(gè)NP-hard問(wèn)題。首先證明它屬于NP問(wèn)題，假設(shè)該問(wèn)題不能在多項(xiàng)式時(shí)間內(nèi)找到答案，但存在可能的解Ω′，可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證Ω′是問(wèn)題的解，且驗(yàn)證的時(shí)間復(fù)雜度為O(n)，此時(shí)該問(wèn)題是一個(gè)NP問(wèn)題。MCP問(wèn)題：對(duì)于給定的集合S= {si:i= 1,2,…,n}，每個(gè)si都有對(duì)應(yīng)的收益Fi和成本Ci，并且目標(biāo)是找到S′?S以滿足相應(yīng)的預(yù)算成本限制Cmax并獲得較高的收益。為了進(jìn)一步證明該問(wèn)題NP-hard，可將MCP問(wèn)題的條件與本問(wèn)題進(jìn)行一一映射，以將MCP問(wèn)題規(guī)約為本文問(wèn)題：

Fi→Ei,si→ri，

Ci→pi,Cmax→B。

MCP問(wèn)題的任何實(shí)例都可從本文問(wèn)題中找到對(duì)應(yīng)的實(shí)例。在文獻(xiàn)[17-18]中，MCP問(wèn)題已被詳細(xì)證明是NP-hard，因而本文問(wèn)題為NP-hard。由于在多項(xiàng)式時(shí)間內(nèi)很難找到NP-hard問(wèn)題的精確解，本文設(shè)計(jì)了一種改進(jìn)的貪婪算法，在縮短求解問(wèn)題的時(shí)間復(fù)雜度的同時(shí)得到逼近精確解的近似解。

邊際效應(yīng)：邊際效應(yīng)源自與此RSU的開(kāi)銷相比通過(guò)添加一個(gè)RSU后目標(biāo)函數(shù)減少的量。貪婪的策略總是選擇本輪迭代中邊際效應(yīng)最大的RSU。

(7)

RSU部署算法如下。

輸入:路口集合 V={vi:i=1,2,…,I},部署成本集合 P= {pi:i = 1,2,…,I},預(yù)算限制 B,當(dāng)前成本 P輸出:選出最優(yōu)路口集合 Ω Initialize:Ω=?,S=?,P=0;1.forS′?V,P(S′)≤Bdo2. S←S′,max=0;3. forvi∈V-Sdo4. S′←{S∪vi},5. ΔF(S)=F(S′)-F(S);6. Ei=-ΔF(S)pi7. ifEi>max and P(S′) ≤ B8. S←S′9. max←Ei10. end if11. ifF(S)

本文設(shè)計(jì)了改進(jìn)的貪婪算法解決用于數(shù)據(jù)卸載的RSU部署問(wèn)題，通過(guò)在預(yù)算約束內(nèi)放置更多RSU來(lái)最大化目標(biāo)函數(shù)。改進(jìn)的貪婪算法總是預(yù)先選擇一組最有效的路口進(jìn)行放置，然后執(zhí)行其余的貪婪迭代。改進(jìn)的貪婪算法考慮了添加RSU部署位置時(shí)的邊際效應(yīng)，大大降低了算法的時(shí)間復(fù)雜度。當(dāng)預(yù)算用完，或者邊際效應(yīng)趨于零時(shí)，算法會(huì)自動(dòng)停止并提出當(dāng)前的最佳部署位置集合。在最差情況下總共有m次選擇迭代，每輪會(huì)遍歷n個(gè)RSU侯選位置，算法的時(shí)間復(fù)雜度為O(mn)。

3 仿真結(jié)果與分析

模擬采用由上海市4 000多條出租車軌跡組成的真實(shí)交通數(shù)據(jù)集[19-20]。本文首先對(duì)交通數(shù)據(jù)集進(jìn)行了初步處理，剔除不適當(dāng)?shù)能壽E。對(duì)不同數(shù)據(jù)文件的采樣周期進(jìn)行了縮放，以保證模擬的可靠性。部署成本P= {pi:i= 1,2,…,I}服從均值為1的高斯分布，總成本預(yù)算以20為間隔從30增加到250。仿真實(shí)驗(yàn)假設(shè)毫米波點(diǎn)對(duì)點(diǎn)傳輸信道能夠獲取較為穩(wěn)定的傳輸速率；數(shù)據(jù)生成速率d0和數(shù)據(jù)卸載速率σ分別設(shè)置為500 MB/s和4 GB/s。本節(jié)分析了RSU利用率、服務(wù)等待時(shí)間和等待容忍度，將3種算法：均勻布放、貪心算法和RSU部署算法用于比較它們的效率。均勻布放算法將RSU放置在固定間隔距離處，普通貪心算法總是選擇當(dāng)前輪次成本最低的位置來(lái)放置RSU。

目標(biāo)F(R)與不同預(yù)算的關(guān)系如圖3所示。RSU部署算法對(duì)目標(biāo)函數(shù)及其邊際效應(yīng)遵循貪婪策略，使得目標(biāo)函數(shù)隨著預(yù)算的增加而增加。當(dāng)RSU部署算法放置大約150個(gè)RSU時(shí)，目標(biāo)函數(shù)已降至理想的小值。RSU部署算法不僅考慮了部署成本，還考慮了對(duì)整個(gè)系統(tǒng)的邊際影響，算法的效率和最終效果優(yōu)于均勻算法和貪心算法，最終可以多部署15%的RSU，其最終效果優(yōu)于均勻和貪婪的部署。

圖3 不同部署成本下算法的F(R)對(duì)比

圖4和圖5顯示了服務(wù)等待時(shí)間和RSU利用率與不同預(yù)算的關(guān)系。

圖4 不同部署成本下算法的車輛平均接入間隔對(duì)比

圖5 不同部署成本下算法的RSU利用率對(duì)比

當(dāng)預(yù)算增加時(shí)，算法會(huì)在網(wǎng)絡(luò)中部署更多的RSU，以提高遇到RSU的幾率。同時(shí)，算法增加了車輛在路口停留的期望時(shí)間。當(dāng)預(yù)算達(dá)到150個(gè)單位時(shí)，Tw顯著下降到大約1個(gè)GPS采樣周期(13 s)。

隨著總預(yù)算的增加，車輛與RSU之間的有效通信時(shí)間隨之增加。算法不僅減少了Tw，而且使RSU能夠?yàn)檐囕v提供更長(zhǎng)時(shí)間的數(shù)據(jù)卸載。因此，UR隨著預(yù)算的增長(zhǎng)而增加。同時(shí)，由于Tw的下降，數(shù)據(jù)幾乎不可能等待超過(guò)時(shí)間限制TL，這進(jìn)一步增加了UR。

圖6顯示了具有不同延遲容忍度車輛應(yīng)用的 RSU利用率。在前3組仿真中，TL固定為10 min。但是，不同的TL，數(shù)據(jù)卸載的效果會(huì)有明顯差異。仿真實(shí)驗(yàn)中，TL參與了F(R)，Tw，和UR的計(jì)算。TL根據(jù)車輛應(yīng)用的延遲容忍度而變化。對(duì)于短TL的應(yīng)用，只有大約80%的數(shù)據(jù)有機(jī)會(huì)通過(guò)RSU卸載，因?yàn)橛邢薜腞SU密度不足以支持延遲容忍時(shí)間內(nèi)的機(jī)會(huì)式數(shù)據(jù)卸載。具有長(zhǎng)TL的應(yīng)用程序的機(jī)會(huì)式卸載RSU利用率較高，RSU密度足以支持車輛延遲容忍時(shí)間內(nèi)機(jī)會(huì)式地接入RSU并進(jìn)行數(shù)據(jù)卸載。

圖6 不同延遲容忍下算法的RSU利用率

4 結(jié)束語(yǔ)

本文研究了6G車聯(lián)網(wǎng)中機(jī)會(huì)式數(shù)據(jù)卸載的RSU部署問(wèn)題，減輕車聯(lián)網(wǎng)的擁塞和延遲問(wèn)題。綜合考慮卸載效果和部署成本的同時(shí)，將RSU部署問(wèn)題轉(zhuǎn)化為一個(gè)NP-hard問(wèn)題。引入了一個(gè)目標(biāo)函數(shù)來(lái)衡量數(shù)據(jù)卸載的效果，并設(shè)計(jì)了一種改進(jìn)的貪婪算法部署RSU，以最大化目標(biāo)函數(shù)。使用真實(shí)出租車GPS數(shù)據(jù)集初始化場(chǎng)景并進(jìn)行仿真，結(jié)果表明RSU部署算法在預(yù)算限制內(nèi)有效增加了車聯(lián)網(wǎng)機(jī)會(huì)式卸載的RSU利用率，并且優(yōu)于其他算法。