6G車聯網中基于路側設備部署優化的機會式數據卸載

王朝煒，王天宇，劉 婷，王衛東

(1.北京郵電大學 電子工程學院，北京 100876；2.泛網無線通信教育部重點實驗室，北京 100876)

0 引言

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

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

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

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

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

1 系統模型

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

圖1 車聯網數據卸載場景示意

網絡模型：城市場景可以被建模為一張圖G= {V,E},圖的節點代表城市道路的交叉路口，圖的邊代表連接各個路口的道路。V={vi:i= 1,2,…,I}表示節點的集合，E= {ei:i= 1,2,…,J}表示邊的集合。圖中的節點和邊的總數分別是I和J。

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

(1)

在所有路口都布放RSU不現實也不經濟，RSU部署算法應從所有路口的集合中選出一部分用于部署RSU。集合R= {ri:i= 1,2,…,K}表示部署算法選中的RSU的坐標。集合R中的元素會隨著部署算法的迭代而改變，R?V，K≤I。

(2)

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

時間線示意如圖2所示，以進一步闡明網絡狀態階段?；疑涂瞻拙€框分別代表服務時間和等待時間。箭頭線代表該服務期間卸載的數據包。等待超出容限的數據包將被丟棄。

圖2 車輛網絡狀態時間線示意

傳輸模型：考慮到車聯網場景的延遲容忍特征，研究了等待時延，將TL作為數據卸載等待時間的限制[15]。車載應用的平均數據生成率為d0，通過RSU的數據卸載率為σ。

(3)

部署算法通過調整場景中RSU的位置來改變λ與μ的比例。當λ增加時，車輛更有可能遇到RSU。當μ減小時，車輛在RSU通信范圍內停留的時間更長。

(4)

當式(4)中的2個項目大小相似時，數據卸載的質量最好。在這種情況下，車輛每個階段的數據量剛好等于該階段可以卸載的數據量，數據丟失或延遲的概率最小，成本會在合理范圍內。

UR的期望值為：

(5)

P= {pi:i= 1,2,…,I}表示在每個路口部署RSU的成本。成本受很多方面的影響，包括基本成本、維護成本和交叉口的擁堵程度。成本集P與路口集V之間存在一一對應關系，主要從路口的交通量和道路拓撲結構估計。

歸一化目標函數反映了部署算法對RSU利用率和數據卸載延遲的影響。通過適當部署RSU來改變車輛的通信狀態，該函數的值將會增加。

F(R)=UR/Tw。

(6)

定義2(RSU部署問題)：從給定的一組路口中選擇其中一組子集來部署RSU，以最大化目標函數并服從預算約束B。

給定：I個候選路口，V={vi:i= 1,2,…,I}和對應的開銷P= {pi:i= 1,2,…,I}，N個時間點T= {ti:i= 1,2,…,N}。

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

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

2 RSU部署算法

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

Fi→Ei,si→ri，

Ci→pi,Cmax→B。

MCP問題的任何實例都可從本文問題中找到對應的實例。在文獻[17-18]中，MCP問題已被詳細證明是NP-hard，因而本文問題為NP-hard。由于在多項式時間內很難找到NP-hard問題的精確解，本文設計了一種改進的貪婪算法，在縮短求解問題的時間復雜度的同時得到逼近精確解的近似解。

邊際效應：邊際效應源自與此RSU的開銷相比通過添加一個RSU后目標函數減少的量。貪婪的策略總是選擇本輪迭代中邊際效應最大的RSU。

(7)

RSU部署算法如下。

輸入:路口集合 V={vi:i=1,2,…,I},部署成本集合 P= {pi:i = 1,2,…,I},預算限制 B,當前成本 P輸出:選出最優路口集合 Ω 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)

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

3 仿真結果與分析

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

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

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

圖4和圖5顯示了服務等待時間和RSU利用率與不同預算的關系。

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

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

當預算增加時，算法會在網絡中部署更多的RSU，以提高遇到RSU的幾率。同時，算法增加了車輛在路口停留的期望時間。當預算達到150個單位時，Tw顯著下降到大約1個GPS采樣周期(13 s)。

隨著總預算的增加，車輛與RSU之間的有效通信時間隨之增加。算法不僅減少了Tw，而且使RSU能夠為車輛提供更長時間的數據卸載。因此，UR隨著預算的增長而增加。同時，由于Tw的下降，數據幾乎不可能等待超過時間限制TL，這進一步增加了UR。

圖6顯示了具有不同延遲容忍度車輛應用的 RSU利用率。在前3組仿真中，TL固定為10 min。但是，不同的TL，數據卸載的效果會有明顯差異。仿真實驗中，TL參與了F(R)，Tw，和UR的計算。TL根據車輛應用的延遲容忍度而變化。對于短TL的應用，只有大約80%的數據有機會通過RSU卸載，因為有限的RSU密度不足以支持延遲容忍時間內的機會式數據卸載。具有長TL的應用程序的機會式卸載RSU利用率較高，RSU密度足以支持車輛延遲容忍時間內機會式地接入RSU并進行數據卸載。

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

4 結束語

本文研究了6G車聯網中機會式數據卸載的RSU部署問題，減輕車聯網的擁塞和延遲問題。綜合考慮卸載效果和部署成本的同時，將RSU部署問題轉化為一個NP-hard問題。引入了一個目標函數來衡量數據卸載的效果，并設計了一種改進的貪婪算法部署RSU，以最大化目標函數。使用真實出租車GPS數據集初始化場景并進行仿真，結果表明RSU部署算法在預算限制內有效增加了車聯網機會式卸載的RSU利用率，并且優于其他算法。