面向車輛邊緣計算的任務合作卸載

魯蔚鋒，印文徐，王 菁，費漢明，徐 佳*

(1.南京郵電大學計算機學院，江蘇南京 210023；2.江蘇省大數據安全與智能處理重點實驗室，江蘇南京 210023；3.國鐵吉訊科技有限公司，北京 100081)

近年來，物聯網相關技術和自動駕駛技術已經成為研究的一大熱點[1]。隨著車聯網相關技術的不斷更新和發展，終端車輛具備了計算、通信和緩存的功能，這些技術在智能車輛網絡方面發揮著關鍵性的作用[2]?？紤]到車聯網中實際的資源擁有情況，單一的路邊單元可能無法滿足終端設備的各項資源需求，造成了不必要的時延和能量的損耗，通過結合車聯網中的合作任務卸載機制可以有效地提高系統的資源利用率，減輕網絡流量負擔，進一步降低時延。

目前國內外有很多研究車聯網中通信、計算和緩存資源的聯合分配問題[3–5]以及由云邊端組成的3層分布式系統中的卸載問題[6–8]。Fan等[9]結合了基站的緩存和計算資源，設計了一種資源管理算法，指導基站聯合調度計算卸載和數據緩存分配。Zhou等[10]結合車聯網的計算、通信和緩存資源，設計了一種新穎的以信息為中心的異構網絡框架，該框架支持邊緣計算中的內容緩存和計算。Zhou等[11]研究了動態多用戶移動邊緣計算系統中計算卸載和資源分配的聯合優化，不僅考慮到任務的延遲約束還考慮異構計算任務的不確定資源需求。Xue等[12]將非正交多址（NOMA）技術引入MEC系統中，提出了一種用于子信道分配的低復雜度次優匹配算法。Zhao等[13]考慮時延敏感型任務的卸載問題，將該問題建模為傳輸功率、子載波和計算資源分配聯合優化，通過一個迭代算法順序處理，通過等價參數凸規劃獲得最優解。Kuang等[14]研究MEC中協同計算任務卸載和資源分配聯合問題，通過對計算卸載決策、協同選擇、功率分配進行分別建模從而最小化系統時延。Dong等[15]設計了一種新型節能的主動復制機制，采用延遲率計算跟隨車輛作為主車輛的備份，保證了系統的可靠性。Zhu等[16]采用多智能體深度強化學習的方案，考慮了多車輛環境的不確定性，使車輛能夠做出卸載決策以獲得最優的長期獎勵。Zhu等[17]提出了一種新型的移動邊緣服務器機制，把邊緣服務器部署在移動車輛上形成車載邊緣，共同優化車輛的最優路徑規劃和系統的資源分配方案。Liu等[18]用博弈論的方法解決時延敏感型任務的傳輸調度優化問題，在不同終端用戶之間設計一個合理的非合作博弈，來找到最優的卸載方案。

目前已有的研究通常以時延和能耗作為約束條件來最小化系統總成本或最大化系統效用從而提出各種方案來解決優化問題，沒有以最小化系統時延為目標，不能滿足低時延的需求?？紤]到車聯網中實際的資源擁有情況，路邊單元和邊緣服務器相對于云服務器來說，計算能力和存儲能力不足。單一的路邊單元可能無法滿足終端設備的各項資源需求，導致不必要的時延和能量損耗。本文通過結合車聯網中的合作任務卸載機制可以有效地提高系統的資源利用率，減輕網絡流量負擔來降低時延，不僅充分研究了車輛邊緣計算系統中的通信模型和計算資源分配問題，還考慮到車聯網中停泊車輛和路邊單元實際的資源擁有情況，設計了對應的合作集群來協作終端設備完成任務的計算卸載，利用系統的空閑資源提高系統計算能力，以減少系統時延為目標設計算法。本文的主要貢獻包括3個方面：

1）設計了一種改進k聚類算法來劃分不同的路邊單元合作集群，不僅根據地理位置來劃分，還考慮了實際的計算負載狀況；

2）設計了一種任務合作卸載算法，充分利用了路邊單元和停泊車輛空閑的可用資源，實現了系統的負載均衡；

3）應用不同數據集的實驗結果表明，本文提出的算法可以找到有效的任務卸載方案。

1 系統模型

1.1 3層系統架構

如圖1所示，將車聯網中的任務合作卸載系統模型分為3層，分別為云服務器層、路邊單元合作集群層和停泊車輛合作集群層。云服務器層位于遠距離的云端數據中心，與邊緣服務器和路邊單元之間通過有線鏈路進行通信。路邊單元合作集群層位于更加靠近終端設備的網絡邊緣，位于同一合作集群的路邊單元之間可以進行X2通信[19]。停泊車輛合作集群層主要位于現實場景中的一些停車場，通過與邊緣服務器之間的無線通信協助完成任務的計算，來拓展邊緣服務器的計算能力。

圖1 3層系統架構Fig.1 Three-tier system architecture

系統中所有路邊單元的集合為G，將所有路邊單元劃分為 ?個合作集群，一個路邊單元的合作集群表示為：M?G。為了最小化路邊單元之間的通信時延，通過距離來進行集群的劃分。同時為了提高合作集群的高效性，允許一個路邊單元屬于多個不同的合作集群。每個路邊單元m的計算資源為fm，代表路邊單元m的計算能力，整個合作集群M的計算資源為FM=。停泊的車輛集合為PV，每個停泊車輛i∈PV的空閑計算資源為fi，則整個停泊車輛合作集群的計算資源為FV=

車聯網中終端設備的集合為J，每一個終端設備j∈J會通過無線鏈路連接到與它最近的路邊單元，連接到同一路邊單元m的終端設備集合表示為Jm∈J。對于每一個終端設備j的計算任務用三元組表示aj=(z j,cj,bj),?j∈J，其中，z j、cj、bj分別表示任務數據量大小、計算任務所需要CPU圈數和任務時延限制。

1.2 合作集群

本文利用改進的k聚類算法[20]來進行路邊單元合作集群的劃分，提出了路邊單元合作集群劃分算法，將路邊單元集合G劃分為 ?個合作集群，使各集群的聚類平方和最小，即以下目標函數最?。?/p>

式中，Md為第d個路邊單元合作集群，每個路邊單元m至少屬于一個合作集群，并且=G，?(m)為路邊單元m所屬合作集群的平均聚類中心，可表示為：

式中，Am為路邊單元m所在的合作集群集合，md為其中每個合作集群的聚類中心。

一些固定?？寇囕v的區域都可以看作是一個停泊車輛合作集群，比如路邊的停車位、商場的停車場等。所有停泊車輛的空閑資源共同構成整個合作集群的可用資源。當多個終端設備接入到同一路邊單元時，用來表示每個終端設備j在路邊單元m中的資源分配情況，其中，為計算資源分配，為通信資源分配。

1.3 通信模型

終端設備的任務可以在本地計算也可卸載計算，系統計算卸載模型一共分為4種情況，如圖2所示：

圖2 計算卸載模型Fig.2 Computational of fload model

1）當終端設備關聯的路邊單元m資源充足時，終端設備j會通過無線通信將任務卸載到路邊單元m計算。終端設備j到路邊單元m的無線通信速率為：

由此可得，終端設備j卸載任務到路邊單元m的傳輸時延為：

2）當路邊單元m的資源不足無法滿足終端設備的需求時，路邊單元m會將任務aj通過X 2通信傳輸給資源充足的路邊單元n，m和n位于同一路邊單元合作集群，可以協同完成任務的計算。

路邊單元m到n之間的傳輸時延為：

1.4 計算模型

相比于邊緣服務器，終端設備的計算能力有限，在選擇任務的計算卸載決策時要考慮終端設備的資源擁有情況。終端設備j將任務在本地計算的時延為：

式中，fj為終端設備j的CPU本地計算能力（即每秒CPU的圈數）。

本地計算的CPU能耗為：

式中，v為一個常量參數，跟終端設備的CPU硬件結構相關[21]。

則任務aj在終端設備j總共的本地計算時延為：

式中： τj代表當終端設備j資源不充足時，任務在設備本地等待處理的平均等待時間?！蕒0,1}代表終端設備j資源是否充足的標識變量，即當tj>bj或者Ej>時，=0；當資源充足時，=1。

任務進行計算卸載時首先會卸載到離終端設備最近的路邊單元m，再根據當前路邊單元資源是否充足來決定任務在路邊單元m計算還是借助路邊單元合作集群計算。

當多個終端設備接入到同一路邊單元時，路邊單元m分配給終端設備j的計算資源為：

任務aj卸載到路邊單元m的總執行時延為傳輸時延與計算時延之和：

1.5 問題的定義

本文的優化目標是最小化任務執行的總時延，任務執行的總時延包括任務本地計算時延和任務卸載計算時延，故可以定義系統目標函數：

約束1代表路邊單元分配給接入終端設備的通信資源限制；約束2代表每個路邊單元m的計算資源限制；約束3和約束4代表任務只能在一個地方執行。

目標函數和約束條件中包含多個非連續的0～1決策變量{x,y}，并且多個0～1變量之間存在耦合關系，導致了這個優化問題是混合整數非線性規劃問題,并且這個問題是NP難的。

定理1優化問題是NP（非確定性多項式時間）難的。

假設目標函數只包含一個0～1決策變量x，則可看作是一個0～1背包問題[22]，由于0～1背包問題是一個典型的NP難問題，而優化問題比0～1背包問題更加復雜，所以優化問題也是個NP難問題。因此，在第1.3節中設計了具體的算法來求解這個優化問題。

2 算法設計

2.1 路邊單元合作集群劃分算法

路邊單元合作集群劃分算法是一個不斷迭代的過程，首先選取 G個合作集群中心，然后根據路邊單元和這些合作集群中心的歐式距離，找到每個路邊單元所屬的合作集群。再根據式（1）更新合作集群的中心，不斷重復上述步驟，直到滿足某個終止條件。

算法1給出了路邊單元合作集群劃分算法的詳細步驟，步驟1隨機選取 ?個初始合作集群中心；步驟2～5對于每個單元m，計算其與每個合作集群中心的距離，距離哪個集群中心近，就劃分到對應的合作集群中，得到初始的合作集群；步驟7重新計算?個集群的中心；步驟8根據新的集群中心重新歸類每個單元m屬于的集群；步驟9-14是看算法是否滿足指定的終止條件，如果滿足3個終止條件中的任意一個，則直接返回最終的路邊單元合作集群算法結束，如果不滿足則回到步驟7繼續迭代。

2.2 任務合作卸載算法

為了方便描述，將優化目標函數表示為minF(x,y)的形式?？紤]到目標函數求解的復雜性，采用塊連續上界最小化（BSUM）[23]的分布式迭代優化方法來求解，BSUM方法的核心思想是將整個優化變量拆分為多個變量塊，通過迭代的方法，在固定其他變量塊的同時，來優化單一的變量塊，直到達到預定的精度閾值（上限）。利用BSUM方法求解優化問題首先要解決兩個問題，一個是目標函數的非凸問題，一個是0～1變量的非連續問題。

為了解決目標函數的非凸問題，通過添加平方懲罰項定義目標函數的近似上界函數，在每次迭代優化過程中，不直接對目標函數進行求解，而是對它的近似上界函數F求解。文獻中[23]已經證明優化近似上界函數的方法是合理的，優化原始目標函數的近似上界函數可以保證原始目標函數是嚴格下降的。其中對應變量x和y的近似上界函數分別為Fx和Fy：

式中， ξ為一個大于0的懲罰參數，x?代表在當前迭代中固定變量y而得到的最優解，y?代表在當前迭代中固定變量x而得到的最優解。

為了解決0～1變量的非連續問題，將變量x和y線性松弛成0到1之間的連續變量，則可以定義2個變量的可行解空間為：

在每次迭代t時，通過求解目標函數的近似上界函數來得到當前的最優解，即在第t+1次迭代時用以下方式來更新x和y的值：

由于最終求解出的優化變量是0到1之間的連續變量，所以需要把它們重新變為0～1變量，借助閾值舍入技術[24]來將松弛后的變量重新變回一個0～1變量。這里舉例說明閾值舍入技術，假定一個求解后的優化變量∈X和一個舍入閾值σ ∈(0,1)，則對應變量的取值為：

上述的閾值舍入技術同樣也可應用于變量y，然而通過閾值舍入后得到的解可能會超過系統的通信資源和計算資源限制。所以將近似上界函數變成為新的舍入問題F+wγ，即對式（20）的約束條件2和3進行以下調整：

式中， γρ和 γf分別為通信資源和計算資源可容忍的最大誤差值，總誤差γ=γρ+γf，w為總誤差的權重參數， γρ和 γf分別表示為：

對應問題F和它對應的舍入問題F+wγ，可以根據整性間隙的值來評估舍入技術的優劣，根據文獻[24]中對整性間隙的定義和證明，可以得出以下結論：

定理2（整性間隙）給定一個問題F它對應的舍入問題F+wγ，對應的整性間隙為：

整性間隙是用來衡量松弛后的優化問題和原優化問題之間的相關性。當整性間隙 β(β ≤1)越接近1時，說明對應的舍入技術越好。

算法2路邊單元合作集群劃分算法。

輸入：所有路邊單元的計算資源fm，所有車輛的計算資源fi；

算法2展示了任務合作卸載算法的具體步驟和過程。步驟1～7表示每個終端設備j∈J首先會根據自身資源的擁有情況來判斷任務是在本地計算還是卸載計算。對于每個卸載到路邊單元m的計算任務aj，執行步驟8～22來找到最優的卸載決策。步驟9表示初始化t=0 和 ε ， ε是一個很小的正數，用來保證算法收斂到 ε最優解[24]，具體解釋在定理2中做出說明。步驟10表示找到一個初始可行解，步驟11～16代表算法的迭代過程，在每次迭代的過程中通過求解式（23）和（24）來不斷更新x和y，直到，來保證收斂到 ε最優解。步驟17表示通過閾值舍入技術求解舍入問題+wγ，得到對應的0～1決策變量x(t+1),y(t+1)。步驟18～20表示計算當前問題的整性間隙β ，如果 β ≤1代表當前的舍入方案是可行的，輸出最優的卸載決策x?，y?。

定理3（收斂性）BSUM算法收斂到 ε最優解的時間復雜度為O(lg(1/ε))，是一個次線性收斂。

算法 ε的最優解xε∈X代表：xε∈{x|x∈X,F(x,y)-F(x?,y)≤ε}，其中，F(x?,y)是目標函數針對于變量x的全局最優值。

3 實驗仿真

3.1 實驗參數設置

基于Python3.0的環境進行實驗仿真，為了驗證本文路邊單元合作集群劃分算法的有效性，采用全球基站開放數據庫中的基站位置真實數據[25]，共包括全球5萬多個基站的相關數據，模擬現實場景中路邊單元合作集群的劃分。聚類算法的精度閾值設為0.005，最大的迭代次數設為3000。為評估任務合作卸載算法的各項性能，假設每個路邊單元附近有20～50個終端用戶，每個終端用戶大約每分鐘產生一個計算任務，車輛的計算資源在0.5到1.0 GHz之間，路邊單元的計算資源在2到5 GHz之間，云層的計算資源認為是無窮大的，任務的數據量大小在2到6GB之間，任務的時延限制在0.5到10 s之間。

3.2 實驗結果分析

圖3是250個基站聚類之前的實際位置。圖4是通過路邊單元合作集群劃分算法聚類之后的效果。

圖3 基站位置Fig. 3 Base station location

圖4 聚類效果Fig. 4 Clustering effect

從圖4可以看出，本文提出的算法將所有的基站劃分為了5個不同的合作集群，每個聚類中心一般都位于所有合作集群的中心，并且集群之間可以相互覆蓋，證明了本文算法的有效性。

為了證明提出的任務合作卸載算法的優越性，將本方案的實驗結果與只本地計算、只卸載計算、無緩存隊列、聯合優化方案[9]和無合作卸載進行對比，無合作卸載方案是指路邊單元之間不存在卸載任務的合作計算；聯合優化方案是指考慮到本地處理能力和卸載能力，集中優化移動邊緣計算中的聯合資源分配。圖5展示了在不同終端用戶數量和不同路邊單元數量下系統總時延的變化曲線，這里的系統總時延就是優化的目標函數。從圖5（a）可以看出，本文提出的合作任務卸載方案在不同終端用戶數量下系統總時延都要低于其他4種方案，可以降低23%的系統時延，說明本文方案可以有效地降低系統任務處理的總時延。從圖5（b）可以看出，在不同路邊單元數量下，本文方案也能發揮出很好的性能。當路邊單元數量達到50左右時，本文方案、只卸載計算和無合作卸載的總時延變化都趨于穩定，說明在當前的系統狀態下，此時的路邊單元數量剛好達到系統平衡點，路邊單元合作集群有著充足的計算資源，可以很好地完成所有任務的卸載計算。

圖5 不同情況下總時延的變化Fig. 5 Variation of total delay in different situations

圖6展示了在不同終端用戶數量和不同路邊單元數量下系統吞吐量的變化曲線，這里的吞吐量指的是系統每秒鐘所能處理的數據量。從圖6（a）可以看出，本文提出的方案在不同終端用戶數量下都有著優于其他方案的系統吞吐量，相比之下，本文方案能提升28%的吞吐量性能，是因為本文提出的任務合作卸載不僅考慮了終端用戶和路邊單元的資源負載情況，還借助了合作集群之間的空閑計算資源，提高了系統的資源利用率。從圖6（b）可以看出，本文方案在不同路邊單元數量下也同樣有著較高的系統吞吐量，系統吞吐量的提升在路邊單元數量40到60之間更為明顯，是因為在路邊單元數量較多時，僅依靠單一的路邊單元進行計算卸載已經無法滿足系統的計算卸載需求，更需要考慮不同路邊單元之間的協同計算。

圖6 不同情況下系統吞吐量的變化Fig.6 Variation of system throughput in different situations

4 結 論

本文對車輛邊緣計算構建了一個3層架構，并提出了一種車輛邊緣計算中的任務合作卸載機制，通過劃分路邊單元合作集群和停泊車輛合作集群，來協助終端設備完成任務的計算卸載，充分利用了系統的各項資源，降低了終端用戶任務的處理時延。通過實驗驗證了路邊單元合作集群劃分算法的有效性，和其他方案的對比實驗發現，本文提出的方案可以降低23%的系統時延，并且能提升28%的系統吞吐量。

未來的工作包括3個方面：1）多種通信模式：本文目前的研究主要考慮的是車輛和路邊單元之間的V2I通信，可以結合V2V、V2X等多種通信模式，充分利用系統的各項資源來研究車聯網中的任務卸載調度過程。2）停泊車輛的激勵機制：在停泊車輛協助完成任務的計算卸載時，考慮到現實中的停泊車輛不會主動貢獻自己空閑的計算資源，可以結合博弈論的相關研究，設計出合理的任務卸載激勵機制，激勵停泊車輛來完成任務的卸載計算。3）卸載方法優化：由于車輛邊緣計算中路況的復雜性以及車輛的高移動性，現實場景中系統需要實時獲取車輛周圍信息，可嘗試將在線算法與本文方案結合以滿足現實需求。