基于交通流量預測的車聯網雙邊拍賣邊緣計算遷移方案

林艷，閆帥,2，張一晉，李春國，束鋒

（1.南京理工大學電子工程與光電技術學院，江蘇 南京 210094；2.中國科學技術大學信息科學技術學院，安徽 合肥 230027；3.東南大學信息科學與工程學院，江蘇 南京 210096；4.海南大學信息與通信工程學院，海南 ?？?570228）

1 引言

近年來，車聯網[1]作為汽車、電子、信息通信、交通管理等行業深度融合的新型產業形態，在人工智能和信息通信技術的推動下向著智能化、網聯化方向演進，成為經濟和社會新的增長點。在移動邊緣計算[2-4]技術的賦能下，車聯網可支撐高精度地圖和復雜交通情況等相關數據的處理和分析，為智能駕駛、無人駕駛等應用提供高可靠、低時延的服務。針對具有高算力需求和低時延約束的車聯網衍生業務，車輛用戶由于自身計算能力有限，會要求將其關聯的計算任務卸載至具有更高算力的鄰近邊緣服務器完成計算遷移。因此，在智能交通的發展趨勢下，車聯網中的邊緣計算遷移具有強勁的技術發展需求[5-7]。

相較于傳統蜂窩網絡的邊緣計算遷移，車聯網的高密度、高動態環境對邊緣計算遷移的應用提出了重大挑戰。一方面，動態的交通流量使網絡拓撲結構不斷發生變化，從而導致邊緣計算遷移決策復雜化；另一方面，當大量車輛同時涌入某路段時，容易造成鄰近的邊緣服務器負載過多而較遠的邊緣服務器空閑的情況出現，且車輛在排隊等待服務過程中可能已經移動至該邊緣服務器的服務范圍之外。因此，如何針對動態變化的交通流量，合理利用有限的計算資源來提高邊緣計算遷移率成為車聯網中亟待解決的關鍵技術問題。

針對上述問題，國內外研究學者提出了一系列車聯網邊緣計算遷移方案。為了合理利用邊緣服務器計算資源，文獻[8]針對固定交通流量的場景設計了一種適用于多用戶多邊緣計算服務器場景下的聯合負載均衡和任務卸載方案，保證了各服務器之間有關任務處理時延的公平性，但該方案不適用于動態變化的交通場景。文獻[9]研究基于路側單元調度的合作博弈計算遷移方案，有效提高了計算資源利用率，但未考慮交通環境變化對資源利用率的影響。文獻[10]考慮在計算資源負載不均的情況下，利用遺傳算法實現對不同優先級的計算任務執行遷移策略，進而提高了邊緣計算遷移率，但未考慮對邊緣計算資源的充分利用。特別地，文獻[11]考慮多用戶競爭有限計算資源的情況下，設計了一種基于單邊拍賣模型的計算遷移方案，以同時降低計算任務服務時延和能量消耗，但該卸載方案仍未考慮邊緣服務器端的計算資源利用率。除此之外，針對車聯網高動態網絡環境，文獻[12-16]提出一系列基于強化學習的邊緣計算遷移方案，旨在最大化車聯網系統的長期收益（如時延、能耗等），同時滿足多樣化的車聯網應用需求，但未考量計算資源利用率的問題。根據上述文獻可知，尚未有研究考慮交通流量的動態變化對邊緣計算遷移性能的影響。

本文的研究目標是探索如何利用交通流量預測信息來輔助設計車聯網的邊緣遷移方案，同時實現邊緣計算遷移率和資源利用率的最大化。在此目標下，本文首先以城市車聯網為例，分別建立了邊緣計算遷移模型和交通流量預測模型；其次，設計考慮任務優先級且表征計算遷移率和計算利用率的效用函數，以及建立對應的雙目標優化問題；再次，通過結合雙邊拍賣理論，將問題轉化為車輛與邊緣計算服務器之間的資源拍賣問題，再通過分別設計車輛與邊緣計算服務器的報價函數，采用McAfee 拍賣算法，進而完成邊緣計算遷移；最后，通過仿真驗證所提方案可以同時顯著提升邊緣計算遷移率和資源利用率。

2 系統模型

2.1 網絡模型

考慮如圖1 所示的城市車聯網模型，該模型包含由4 個雙向多車道路段組成的十字交叉路口，每個路段上有若干移動車輛勻速行駛。各路段上等間隔均勻部署N個路側單元（RSU,road side unit），每個RSU 均配置一個車聯網邊緣計算（VEC,vehicular edge computing）服務器，負責為本路段車輛同時提供通信和計算資源。

假設系統可劃分為等間隔的資源分配周期，且在每個周期內有隨機數量的車輛進入各路段。在總周期內，進入各路段的車輛總數記為M。假設每輛車僅攜帶一個計算任務。由于車輛計算能力有限，故需要將其計算任務卸載至鄰近的RSU 來完成計算。為此，車輛首先需要與RSU 通信請求獲取計算資源，然后RSU 之間通過宏基站進行信息交互并獲取資源分配方案，最后車輛依據分配方案完成任務卸載。

2.2 任務卸載模型

假設車輛的計算任務由計算任務的數據量大小、任務優先級、計算資源需求量大小等特征表征。本文考慮的車輛邊緣計算遷移過程可分為以下4 個階段。

圖1 城市車聯網系統模型

1) 車輛移動。由于RSU 的通信覆蓋范圍有限，車輛需要移動至指定的RSU 覆蓋范圍內，才可將其任務卸載至對應的VEC 服務器上完成計算遷移。當車輛i需移動至RSUj處完成任務卸載時，車輛的移動時間可表示為

其中，Lij表示當前車輛i移動至RSUj覆蓋范圍內所需移動距離，vi表示車輛i的速度。

2) 任務上傳。當車輛i已在RSUj的覆蓋范圍內時，車輛可將計算任務上傳給對應的VEC 服務器j。本文假設多用戶干擾已通過正交頻分復用技術消除，且車輛在任務上傳時間內無線信道狀態保持穩定[17]?？紤]計算任務數據量大小動態變化的情況，比如服從均勻分布U[300,1 000]。此時，當車輛i將數據量大小為DiKB的計算任務上傳至RSUj所消耗的時間可表示為

其中，B表示無線傳輸鏈路帶寬，Pi表示車輛i的發射功率，G ij表示車輛i與RSUj之間的信道增益，σ2表示加性高斯白噪聲的功率。

3) 任務執行。假設VEC 服務器j的計算能力可用CPU 速率Uj表征，即服務器計算單位比特數據時所需CPU 運轉周期數。另外，車輛i對計算資源的需求量si表示車輛單位時間內對CPU 運轉周期的需求量，假設計算資源需求量動態變化，比如服從均勻分布U[0.5,1.5]。于是，車輛i的計算任務在分配的VEC 服務器j上執行計算所消耗的時間為

4) 結果反饋。當VEC 服務器執行完任務，需將任務執行的結果反饋至關聯車輛。但由于計算結果數據量一般較小，相較于任務上傳和任務執行。其反饋時間較短[6]，故本文忽略結果反饋占用的時間。

在上述完整在上述完整的任務卸載過程中，車輛i經過時間移動至分配的VEC 服務器j之后，對VEC 服務器j的占用時間可表示為

2.3 交通流量預測模型

在交通網絡中，平均交通流量和平均車速作為主要參數，表現出強烈的隨機性和不確定性，本文考慮利用馬爾可夫決策過程理論建立交通流量預測模型[18]，為車聯網提供有力的邊緣遷移決策依據。

假設各RSU 負責統計交通流量信息，即單位時間周期內通過該RSU 所在路段的不同車道的車輛數。以圖1 中的路段1 為例，該路段第t個資源分配周期內表征各方向車輛數的向量V(t)可表示為

接下來，根據上述交通流量信息，可以獲得車輛狀態轉移的規律。駛入路段1 的車輛在駛入前的來源車道包括左轉車道A1、直行車道A2和右轉車道A3，分別以一定的概率駛入左轉車道B1、直行車道B2和右轉車道B3。路段1 的交通流量轉移關系如表1 所示。

表1 路段1 的交通流量轉移關系

其中，Vkm表示當前周期內進入路段1 的所有車輛中從車道Ak轉入車道Bm的車輛數，k=1,2,3。

根據表1，可以得到轉移概率矩陣P為

假設下一周期的車輛轉移概率保持不變，且下一周期各來源車道的車輛數與當前周期目標路段各車道的車輛數對應相等。依據馬爾可夫決策過程，則可以預測下一周期目標路段的交通流量V(t+1)為

3 問題描述

本文的研究目標是探索利用交通流量預測信息設計一種計算遷移方案，使車輛計算任務完成率最大化，同時使VEC 服務器的計算資源利用率最大化。為了量化評價車輛計算任務完成率以及VEC服務器的利用率，本文定義以下性能指標。

1) 車輛效用函數

為便于建模，本文將整個資源分配過程的總時間T劃分為有限個單位時間間隙Δt，且假設每輛車占用VEC 服務器計算資源的時間為Δt的整數倍。設xi,j,t為卸載決策變量，表征在第t個Δt內車輛i是否將任務卸載至VEC 服務器j，xi,j,t=1表示卸載，xi,j,t=0表示未卸載。車輛i的計算任務被執行完之后產生的效益值表示為Ri。一方面，該效益值與任務的數據量大小Di和優先級有關，即數據量越大，優先級越高，其效益值越高。另一方面，車輛i在任務上傳前的等待時間可表示為

車輛的等待時間越長，產生的效益值越低。因此，效益值可表示為通過對所有路段中的車輛特征信息進行統計，為量化表征車輛任務卸載所產生的效益值，本文將車輛任務卸載的效用函數UV定義為成功卸載任務的車輛產生的效益與所有車輛任務可產生效益的比值，如式(9)所示。

2)VEC 服務器效用函數

在VEC 服務器計算資源有限的條件下，如何為多車輛設計任務卸載方案的問題可以轉換成如何為多車輛分配計算資源的問題。假設VEC 服務器j可提供的計算資源量Cj可表征為單位時間內可提供的CPU 運轉周期數。為了充分利用VEC 服務器的計算資源，本文采用一種計算資源的時間復用方案，即在VEC 服務器可提供的最大計算資源量約束條件下，允許不同車輛在相同時間將計算任務卸載至同一個VEC 服務器。設Cj,t為VEC 服務器j在第t個時間間隙Δt內持有的計算資源量，因此，通過統計VEC 服務器計算資源的分配情況，為量化表征VEC 服務器的計算資源的利用率，本文將VEC 服務器資源效用函數UE定義為執行任務卸載的VEC 服務器實際產生的效益與所有服務器計算資源所能產生效益的比值，表示為

3）優化問題建立

為了同時最大化車輛任務卸載產生的效益值和VEC 服務器的利用率，本文研究的優化問題可以構建為

4 邊緣遷移雙邊拍賣方案設計

上述建立的優化問題屬于多目標0-1 規劃問題，且屬于NP-hard 問題?？紤]到車聯網中車輛與VEC 服務器之間屬于一種“多對多”的供求關系，故可以利用拍賣理論[19-20]構建成雙邊拍賣問題，如圖2 所示。具體而言，雙邊拍賣過程包含資源供應商代理、資源消費者代理和拍賣管理者3 類參與者，其中資源供應商代理和資源消費者代理分別為VEC 服務器和車輛，拍賣管理者為區域內的宏基站。宏基站將按照給定的拍賣策略，促成供應商和消費者在交易資源的價格上達成一致，最終完成交易。下面將詳細介紹邊緣遷移雙邊拍賣算法。

4.1 算法描述

本文采用拍賣理論中經典的McAfee 拍賣算法[20]來設計求解方案。McAfee 拍賣算法的基本思想是將消費者、供應商報價分別進行降序、升序排列，找出臨界用戶，并將其報價作為實際交易價格。為此，需要先分別設計車輛端和VEC 服務器端的報價，然后對報價排序，再根據報價分配服務器的計算資源。

圖2 邊緣遷移雙邊拍賣方案

1) 車輛報價

車輛的報價與自身的特征信息有關。在本文的模型中，車輛i的特征信息包括計算任務數據量大小Di、車輛速度vi、任務優先級以及計算資源需求量si?？紤]到拍賣失敗次數對報價的影響，本文基于拍賣補償策略[11]將車輛報價設計為

以拍賣總輪數Sum=10的情況為例，當數據量大小Di=500 KB、任務優先級參數βV=10%時，若車輛參與拍賣的失敗次數Numi依次取值為{1,2,3,4}，根據式(12)可以計算得到車輛報價分別為{672,756,864,1 008}。由此可以看出，隨著車輛拍賣失敗次數的增加，車輛報價不斷增長，且增長速度也不斷提高。

為了進一步考慮交通流量對車輛邊緣遷移效用的影響，即交通流量的不同會造成各車道的擁擠程度不同，對計算資源需求的緊迫程度也不同，本方案利用RSU 統計的周期內該路段交通流量信息，來衡量不同車道上車輛的任務卸載的優先級。具體而言，基于交通流量優先級將車輛報價設計為

2) VEC 服務器報價

對于VEC 服務器，其報價完全由其持有計算資源量決定，即計算資源越多，報價越高。這是因為當持有計算資源越多，該VEC 服務器能計算的車輛任務也越多。本文假設VEC 服務器報價與持有計算資源量呈線性關系，并將VEC 服務器的報價函數設計為

其中，γ為單位資源量的報價。

3) 算法流程

基于上述報價設計，本文提出一種基于交通流量預測的車聯網雙邊拍賣邊緣遷移算法，如算法1所示。首先，在每個拍賣周期中，RSU 根據感知的車輛信息統計出本拍賣周期（即資源分配周期）內計算任務尚未被卸載的所有車輛，作為消費者隊列匯總給基站。最后，基站根據交通流量預測模型，預測本周期內的交通流量信息，獲得交通流量優先級，計算車輛報價并降序排列。對于每輛車，分別計算車輛占用各服務器的時間段，同時計算VEC服務器的報價并升序排列。最后，對每個VEC 服務器確認如果其接受某個車輛計算任務的卸載，車輛占用的計算資源是否會超出其當前時間段內服務器的空閑資源量。若不超出，則雙方達成交易，該車輛退出消費者隊列并執行任務卸載，同時服務器需要更新其計算資源量持有情況以及報價；若超出，則該車輛本輪競拍失敗，更新車輛報價，等待下一拍賣周期。至此，本拍賣周期結束，進入下一拍賣周期。

算法1基于交通流量預測的車聯網雙邊拍賣邊緣遷移算法

4.2 算法復雜度分析

本節將以系統中單個目標路段為例，比較分析算法1 與窮舉法的算法復雜度。假設在第t個資源分配周期內，進入目標路段的車輛總數為Mt。若采用窮舉法進行計算遷移，即將每輛車的任務可選的N種卸載方案進行遍歷，故單位分配周期內算法復雜度為在算法1 中，考慮采用冒泡算法對車輛和VEC 服務器分別進行排序，則排序過程的復雜度分別可表示為經過報價排序后的每輛車依次嘗試與報價排序后的VEC 服務器進行逐個匹配，最終將計算任務卸載至最先匹配成功的服務器，故算法1 在單位分配周期內的算法復雜度可表示為O(M tN2)}。通過對比可以發現，當Mt和N都較大時，算法1 復雜度遠小于窮舉法。

5 仿真分析

5.1 仿真設置

本節利用MATLAB 平臺進行仿真實驗，并考慮由4個雙向多車道路段組成的十字交叉路口網絡模型如圖1 所示。在所有仿真實驗中，假設所有車輛全程均勻速行駛，且忽略車輛在十字路口處轉換路段和車道消耗的時間，另外假設車輛在相同路段行駛過程中不允許切換車道。主要仿真參數如表2 所示。

本節將針對函數和VEC 服務器資源利用效用函數對比以下3 種方案的仿真性能。

1) 順序卸載方案：車輛按照到達先后順序依次選擇VEC 服務器完成計算任務卸載。

2) 未輔助的拍賣卸載方案：在無交通流量預測信息輔助的情況下采用雙邊拍賣算法完成計算任務卸載，即車輛根據式(13)提交報價，VEC 服務器根據式(14)提交報價，基站再根據McAfee 拍賣算法分配計算資源。

3) 本文所提方案：在方案2 的基礎上引入交通流量預測信息的輔助完成計算任務卸載，即算法1。

表2 仿真參數設置

5.2 仿真結果

首先，為了驗證交通流量預測的有效性，表3給出了不同仿真次數下，路段1 左轉、直行和右轉車道在第6 個分配周期內交通流量預測情況。通過對比交通流量真實值和預測值可以發現，盡管存在一定的預測誤差，但三車道之間的交通流量大小相對關系基本不變。該結果表明預測交通流量對應的優先級能夠基本反映真實交通流量對應的優先級。

表3 路段1 第6 分配周期內交通流量部分預測結果

圖3 比較了不同車輛數量下的車輛任務卸載效用性能。當車輛數不斷增加時，3 種方案的車輛任務卸載效用函數UV正如預期般呈下降趨勢。這是因為在VEC 服務器的最大計算資源量約束下，增加車輛數會導致需要被卸載的任務數量增加，任務之間競爭有限計算資源更加激烈，進而車輛任務的卸載比例隨之降低。除此之外，通過比較3 種方案可以發現，得益于拍賣算法的優勢，未輔助的拍賣卸載方案明顯優于順序分配方案，可以獲得更高的車輛任務卸載效用。而本文所提方案在交通流量預測信息的輔助下，其車輛任務卸載效用性能相較于未輔助的拍賣卸載方案的性能得以大幅提高。其原因是本文所提方案中預測的交通流量信息用于衡量車輛任務卸載的優先級，再通過基于交通流量優先級的車輛報價設計，可使所在車道交通流量越大的車輛，任務被執行的優先級越高，從而車輛任務卸載產生的效用值也越高。該仿真結果驗證了本文所提方案在不同車輛數量的車聯網中的有效性，以及交通流量預測信息對車輛任務卸載效用性能的提升。

圖3 不同車輛數量下的車輛任務卸載效用比較

圖4 比較了3 種方案在不同VEC 服務器數量下的車輛任務卸載率性能。隨著每個路段中VEC 服務器數量的不斷增加，3 種方案的車輛任務卸載效用函數UV均呈上升趨勢。這是因為在車輛數基本保持不變的情況下，增加VEC 服務器的數量可以為車輛的任務卸載提供更多的選擇，從而使車輛任務的卸載完成率不斷增長。另外，通過對比3 種方案的性能可以發現，本文所提方案性能表現最優，且當VEC 服務器數量增加時，性能優勢越明顯。其原因是交通流量信息的輔助可以使優先級越高的車輛任務越能優先地被執行，并在VEC 服務器數量增加時，可以使更多優先級高的任務被執行。而未輔助的拍賣卸載方案比順序卸載方案性能表現更佳，是由于拍賣卸載方案能夠更有效地利用VEC 服務器的計算資源來提升車輛卸載效用。上述結果表明，可以通過增加VEC 服務器數量來提高車輛任務卸載效用。

圖4 不同VEC 服務器數量下的車輛任務卸載效用比較

圖5 進一步比較了3 種算法在不同車輛數量下的服務器資源利用率性能。由于車輛數增加導致計算任務數增加，而VEC 服務器的計算資源總量不變，因此VEC 服務器資源利用率提高，從而3 種算法的VEC 服務器資源利用效用UE均呈上升趨勢。相較于對比方案，本文所提方案在交通流量預測信息的輔助下，可以獲得性能最優的VEC 服務器資源利用效用。這是因為預測的交通流量信息能更好地估計車輛任務卸載的優先級，再通過拍賣算法可使VEC 服務器資源能被更好地利用。值得注意的是，隨著車輛數量的不斷增加，3 種方案的性能差異也隨之顯著增加，這表明交通流量預測信息有助于更多車輛合理利用服務器資源。

圖5 不同車輛數量下的服務器資源利用率比較

圖6 比較了3 種方案中VEC 服務器數量與服務器資源利用效用函數之間的關系。首先，可以觀察到，VEC 服務器資源利用效用函數UE隨服務器數量的增加而增加。這是由于VEC 服務器數量的增加，可以給車輛提供更多充分利用VEC 服務器計算資源的機會。其次，3 種方案的VEC 服務器資源利用效用在服務器個數較少時增長均較快（如N由3 增加至7 時），但當VEC 服務器數量較多時，其增長速度逐漸變慢。這是因為即使VEC 服務器數量不斷增加，以及被成功卸載的車輛任務數量隨之上升，但是VEC 服務器的計算資源總量也在增加，因此資源利用效用的增長速度會逐漸放緩。最后，通過對比3 種方案可知，本文所提方案的性能仍是最優的，未輔助的拍賣卸載方案次之。其原因是拍賣卸載方案同時考慮車輛效用和VEC 服務器效用的最大化，而交通流量信息的輔助能更進一步確保優先級較高的任務優先被執行，并能更合理地利用VEC 服務器資源。另外，隨著VEC 服務器數量的增加，本文所提方案的性能優勢越明顯，這再次驗證了本文所提方案的優越性。

圖6 不同VEC 服務器數量下的服務器資源利用率比較

6 結束語

本文考慮動態變化的交通流量場景下車聯網邊緣計算遷移問題，提出一種基于交通流量預測的雙邊拍賣邊緣計算遷移方案。該方案首先利用馬爾可夫決策過程理論建立交通流量預測模型，再通過交通流量預測信息衡量車輛任務優先級，進而完成雙邊拍賣理論中車輛報價的設計，并通過雙邊拍賣算法最終同時實現車輛任務邊緣遷移率和邊緣計算服務器資源利用率的最大化。仿真結果驗證了交通流量預測信息對邊緣計算遷移性能提升的有效性，且分別揭示了不同車輛數和VEC 服務器數對邊緣遷移率和計算資源利用率的影響規律。下一步工作將考慮結合強化學習理論解決未知交通流量動態變化規律時的車聯網邊緣計算遷移問題。