曹敦，張應寶，鄒電，王進，湯強，冀保峰

（1.長沙理工大學計算機與通信工程學院，湖南 長沙 410114；2.南京郵電大學寬帶無線通信與傳感網技術教育部重點實驗室，江蘇 南京 210003；3.河南科技大學信息工程學院，河南 洛陽 471023）

0 引言

在這個萬物互聯的時代，人工智能和通信技術的快速發(fā)展能實現車輛與X（即車、人、網絡、基礎設施等）的通信[1]，并提升車輛的自動駕駛能力，改善交通運營和服務智能化欠缺的現狀。同時新型車載終端的應用也對通信質量和服務智能化要求日益嚴苛[2-3]。移動邊緣計算（MEC,mobile edge computing）的出現能夠有效地應對這一挑戰(zhàn)。MEC是一種新型通信架構，將具有存儲、計算、通信功能的服務平臺部署在網絡邊緣位置，幫助移動終端用戶將服務任務就近卸載到邊緣節(jié)點上，進行協同處理[4-5]，從而減輕通信鏈路的傳輸壓力，縮短服務的響應時間，減少移動設備的能耗和傳輸成本[6-7]。MEC 技術作為5G 移動通信中開始應用的一項重要技術，目前受到工業(yè)界和學術界的廣泛關注[8]。而其在車聯網中的應用能提供低時延的計算智能，使用戶服務體驗[9-10]有質的改變。

車聯網服務類型可分為車載安全型、車載增強型和車載娛樂型三大類[11]。服務對時延、數據量、任務復雜度和子任務間耦合度等有不同的要求[12]。根據特征的不同，又可將任務分成不同的類型，如根據時延限制可分為時延敏感型和非時延敏感型，根據任務復雜度可分為計算資源密集型和稀疏型，根據子任務的耦合度分為可分離型和不可分離型[13]。時延敏感型的計算任務對數據的實時性要求極高，而計算密集型任務需要大量的存儲資源，但時延要求相對寬松[14]。依據Robertazzi的可分離任務理論[12]，可分離型任務可分成若干任意大小的子任務，每個子任務之間沒有依賴關系，可以按照任意順序進行處理。而車載娛樂型服務中的視覺視頻剪輯和動畫渲染等任務具有非時延敏感、數據量大、復雜度高、耦合度低的特點。在V2X（vehicle to everything）通信中，利用下沉到車輛及路側單元的計算資源設計一種任務可拆分、多節(jié)點協同的卸載決策，可滿足此類服務的服務質量（QoS,quality of service）要求。

然而，任務可拆分、多節(jié)點協同的卸載決策需面對一系列問題。在任務執(zhí)行周期內，車載任務卸載環(huán)境是動態(tài)不確定的，網絡拓撲結構及無線信道狀態(tài)會快速變化，如何選擇在任務執(zhí)行周期內可用的協同節(jié)點是需要解決的問題之一，且考慮協同節(jié)點通信和計算資源差異，如何進行任務不等拆分，使任務分布式計算執(zhí)行時延最小化，以提高信道利用率是需解決的問題之二。本文面對上述2 個問題，提出了一種V2X多節(jié)點協同分布式卸載策略。本文主要的研究工作總結如下。

1) 本文構建了V2X 下本地、MEC 和協同車輛多節(jié)點協同計算模型，它聯合了卸載策略和任務不等拆分問題，通過預測車輛行駛軌跡，將協同卸載問題建模成本地與協同節(jié)點分布式計算時間較大值最小化問題。

2) 本文采用博弈論中的納什均衡來求解上述問題中服務的卸載策略，并將串行卸載問題公式化為帶約束的高維非線性優(yōu)化問題。

3) 在卸載策略確定的情況下，本文采用序列二次規(guī)劃（SQP,sequential quadratic programming）算法求解上述優(yōu)化問題，通過拉格朗日函數將原問題轉化為二次規(guī)劃子問題，從而確定任務的不等拆分比例，實現本地與卸載的工作時間均衡。

4) 實驗結果表明，本文提出的算法具有良好的效能和優(yōu)越性。與其他4 種基準算法相比，本文提出的算法能夠獲得更低的系統時延，并有良好的收斂性。

1 相關工作

國內外學者針對移動邊緣計算的任務卸載問題開展了大量的研究。文獻[15]研究了靜止狀態(tài)下的用戶卸載，考慮到MEC的車載無線網絡和計算能力有限的問題，設計了一種無線和計算分配聯合優(yōu)化算法用來求解用戶的卸載決策。文獻[16]提出了LBB（linearization based branch and bound）和CRI（closest rounding integer）算法分別解決在用戶靜止和速度恒定狀態(tài)下的計算卸載策略，考慮到時變信道對任務卸載策略的影響，該研究提出了一種最接近四舍五入算法來解決固定時變頻譜效率問題。文獻[17]提出了在加速度不變的條件下多用戶計算卸載決策，考慮到多個用戶設備同時通過無線信道卸載計算任務時的信道干擾問題，設計了一種基于強化學習的進化博弈算法。文獻[18]研究了車輛無線網絡的移動感知計算卸載，考慮到車輛的隨機移動和卸載過程中可能出現的越區(qū)切換問題，該研究提出了一種分析模型用來計算卸載決策。文獻[19]提出了一種通過建立適用于移動和普適計算場景的三層體系架構來優(yōu)化用戶計算卸載決策的方法。

文獻[20]研究了服務請求車輛發(fā)送不可拆分數據包時的平均上行局部時延，該研究利用最接近接收方模型確定單個邊緣節(jié)點。文獻[21]研究了每個用戶通過無線多址傳輸將計算任務卸載到多用戶協同計算，考慮到非正交多址接入（NOMA,non-orthogonal multiple access）的共信道干擾和MEC的計算任務均等拆分問題，該研究提出了聯合最優(yōu)任務卸載和資源分配的算法求解卸載決策。文獻[22]通過研究多用戶多輸入多輸出預編碼和計算資源不等分配方法，提出了一種利用半定松弛法和舍入法優(yōu)化卸載決策。文獻[23]提出了基于多臂強盜理論進行任務的不等拆分策略。文獻[24]提出了在動態(tài)環(huán)境下基于自適應學習的多車輛等分任務卸載策略，該研究以最小化平均卸載時延為目標，提出了一種基于V2V 通信的多車任務卸載系統模型。

綜上所述，當前已有的相關研究集中于以下2 個方面：1) 通過建立車輛的不同運動模型，優(yōu)化用戶的卸載決策問題；2) 根據服務任務類型的差異，優(yōu)化卸載決策問題。當前關于協同卸載策略的研究工作雖然很多，但是聚集在車輛行駛軌跡預測下的不等任務拆分策略還較少。本文研究了V2X多節(jié)點協同串行卸載、分布式計算策略，聯合優(yōu)化了卸載決策和任務不等分配比例。

2 系統模型

本文主要考慮高速直行道路場景。因反向行駛車輛相對宿主車輛有較大反向相對速度，停留在宿主車輛通信范圍的時間較短，因此協同車輛僅考慮與宿主車輛同向行駛的車輛，并且考慮車輛變道、變加速等行駛行為。為充分利用計算資源和減少卸載計算時延，宿主車輛可以選擇部分任務在本地執(zhí)行，其余任務利用V2X 通信模式卸載到協同節(jié)點上協助處理。

2.1 網絡模型

網絡模型如圖1 所示。可提供邊緣計算的路側單元（RSU,road side unit）標記為v0，假設RSU 覆蓋范圍內有N輛車呈泊松分布，表示為V={v1,v2,…,vi,…,v N},i∈[1,N]。假設車輛內都裝有北斗衛(wèi)星導航系統等定位設備，可以實時獲取車輛的軌跡信息[25]。集合V中車輛終端的軌跡信息用集合S表示，，第α輛車在第t時刻的軌跡信息為，其中為速度，為第α輛車的位置坐標。當車輛vi為宿主車輛時，在卸載時延和通信范圍的約束下，vi有n∈[0,N]個可選擇的協同節(jié)點Mi={mi,0,mi,1,…,mi,j,…,mi,n},(i≠ 0,j≠i,j∈[0,n])，其中，mi,j表示宿主車輛vi的第j個協同節(jié)點，mi,0=v0表示RSU 可用。協同節(jié)點的卸載順序為Qi,j={qi,0,qi,1,…,qi,j,…,qi,n},(i≠0,j≠i,j∈[0,n])，其中，qi,j表示vi卸載到mi,j的卸載順序數，qi,j∈ {1,2,…,n+1}，例如qi,j=4 表示mi,j為第4 個執(zhí)行卸載的協同節(jié)點。宿主車輛vi的協同策略可通過協同節(jié)點集Mi根據Qi,j排序后獲得，表示為Ai=rank(M i,Qi,j)，rank(·) 表示將Mi中元素mi,j按Qi,j中對應元素qi,j的值升序排列。

圖1 V2X多節(jié)點協同分布式卸載策略網絡模型

為了便于閱讀，本文中主要變量及含義如表1所示。

表1 主要變量及其含義

2.2 通信模型

本文各節(jié)點采用正交頻分多址（OFDMA,orthogonality frequency division multiple access）技術接入系統。任務車輛在執(zhí)行邊緣卸載時，通過V2R（vehicle to RSU）、V2V（vehicle to vehicle）通信模式將計算任務卸載到路側單元和協同車輛。本文假設多協同節(jié)點干擾已通過正交頻分多址技術消除，且車輛在任務上傳時間內無線信道狀態(tài)保持穩(wěn)定[23]。不失一般性，假設V2V 通信模式復用V2R 通信模式的上行傳輸通道。根據香農定律可得，數據的上傳速率為

其中，*可為v 或r，vw和rw分別表示V2V 和V2R信道帶寬；1p表示上傳鏈路信道衰落因子；p2表示路徑損耗因子；li,j表示從vi到mi,j的歐氏距離；0ρ表示通信內部高斯噪聲密度；P為發(fā)射功率。

2.3 運動模型

本文構建行駛軌跡預測模型，通過t時刻的位置信息預測t+Δt時刻的位置信息。假設本文的行駛軌跡預測模型目標是估計用戶短時間 Δt內的移動軌跡。為方便描述，依據車輛行駛方向平行道路建立二維坐標，第α輛車在t+Δt時刻的二維坐標為

由L2 范數可獲得第α、β輛車在t+Δt時刻的距離為

即

2.4 計算模型

定義協同節(jié)點mi,j被分配的計算任務為其中，Di,j表示任務量大小，表示任務Di,j從vi卸載到mi,j的順序標簽值，表示任務Zi,j所能容忍的最大時延。一些計算任務具有較高的復雜性，無法及時得到計算結果。因此，需要決策Zi,j中在本地及卸載計算的子任務量。

1) 本地計算

2) 卸載計算

卸載計算時延包括傳輸時延、計算時延和回傳時延，因任務完成結果的大小遠小于任務的大小，并且考慮到傳輸的下行（回傳）速度遠大于上行（傳輸）速度，所以本文忽略結果回傳的時延大小[22,26]，僅考慮上行傳輸時延和計算時延兩部分的影響。

協同節(jié)點mi,j的卸載計算時延為

本文研究的是非時延敏感型任務的協同計算，并考慮資源競爭的公平性，宿主車輛使用單信道進行任務串行卸載，同時為提高用戶服務質量及無線資源的利用率、最小化系統時延，設計各協同節(jié)點接受任務后分布式執(zhí)行。在卸載過程中，上行傳輸時間與執(zhí)行時間存在一段重疊時間。因此卸載部分所用的時間取決于所有協同節(jié)點上傳時延之和，再加最后被卸載協同節(jié)點的計算時延，即

2.5 問題形成

車聯網中利用MEC 進行卸載計算，為提高通信及計算資源的利用率，期望最小化任務卸載的計算時延。但任務卸載計算期間，網絡拓撲結構及信道質量因車輛的移動發(fā)生變化。因此，需預測車輛軌跡，選擇時延容限內可用的協同節(jié)點，并確定拆分任務方案、卸載節(jié)點及任務卸載順序。需解決的串行卸載、并行計算問題為

因為任務在本地和協同節(jié)點分布式執(zhí)行，所以任務執(zhí)行總時長取決于本地或協同節(jié)點任務執(zhí)行時長的較大值。約束條件1C 表示任務在本地和協同節(jié)點分布式執(zhí)行的約束邊界；C2表示在任務執(zhí)行期內vi到mi,j之間的相對距離小于或等于通信范圍R；C3表示本地和卸載計算任務量之和等于總任務量；C4表示當前協同節(jié)點mi,j執(zhí)行卸載任務的計算時延必須小于還未分配計算任務的協同卸載計算時延之和，其目的在于保證最后一個協同節(jié)點將子任務的計算結果回傳到宿主車輛后，其余協同節(jié)點的計算結果均已完成回傳。

3 算法設計

為了解決式(8)描述的優(yōu)化問題，本文提出了一種協同分布式卸載-SQP 策略（CDOS-SQP,cooperative distributed offloading strategy-SQP）。在CDOS-SQP 中，分別提出了一種基于博弈論的卸載策略和基于SQP 算法[27]的任務分配方法，前者確定計算任務的卸載策略集Ai，而后者根據Ai確定任務不等拆分集iD。

3.1 基于博弈論的卸載機制

本節(jié)確定宿主車輛協同卸載時可用的mi,j，可通過卸載順序集Qi,j獲得協同策略集Ai來解決此問題。

在宿主車輛和協同節(jié)點的不斷移動下，確定車輛vi為宿主車輛時的協同節(jié)點集Mi的準則是：在任務執(zhí)行期內協同車輛始終處于宿主車輛的通信范圍R內。本文應用博弈論中的重復剔除嚴格劣戰(zhàn)略來獲得Mi。

使用博弈論中的重復剔除嚴格劣戰(zhàn)略，將t+tΔ 時刻車輛間的距離大于通信范圍R定義為劣戰(zhàn)略，終止條件為此時刻集合Mi中不包含劣戰(zhàn)略。從而確定從t時刻到時刻始終處于R范圍內的協同節(jié)點集Mi。下面使用博弈論中的納什均衡來確定最優(yōu)卸載順序集

首先，定義mi,j的為宿主車輛vi卸載到的上傳時延及在mi,j的計算時延之和，即

然后，使用博弈論中的納什均衡來確定協同節(jié)點執(zhí)行任務的卸載順序。策略博弈[28]Γ涉及3 個要素，分別為參與者Mi、策略Qi以及效用函數Ui，具體說明如下。

1) 參與者。宿主車輛vi的n+1 個參與博弈的協同節(jié)點集Mi。

3) 效用函數。當vi的協同節(jié)點集Mi選擇其串行卸載順序集為Qi,j時的代價函數為定義如式(11)所示。每個協同節(jié)點都希望選擇最優(yōu)卸載順序獲得最大效用。

納什均衡是指博弈中每個參與者都確信在其他參與者策略給定的情況下，自己選擇了最優(yōu)策略，從而使自己效用最大化。具體描述介紹如下。

算法1使用基于博弈論的卸載決策求解卸載策略集Ai

3.2 基于SQP 算法的任務分配

本節(jié)研究協同卸載下任務不等拆分集iD?，F已通過卸載機制計算出Ai，已知式(8)中的約束條件C2僅影響策略集合Ai，則在本節(jié)計算需確立集合Di中任務的不等拆分比例，使任務執(zhí)行時延Tvec最小化時不考慮約束條件C2。由于集合Di中任務可在本地和協同節(jié)點并行計算，因此將式(8)轉化為本地和卸載這兩類并行執(zhí)行時間差值ΔTvec最小化問題，即

因為協同策略集Ai中有多個協同節(jié)點，所以任務不等拆分時按照協同節(jié)點數將其拆分成多份不等任務，即式(12)的優(yōu)化問題可描述為帶約束條件高維非線性優(yōu)化函數問題。SQP 算法是求解此類最有效的優(yōu)化算法之一，具有收斂性較好、邊界搜索能力強、計算效率高等優(yōu)點。本文采用SQP 算法求解式(12)的優(yōu)化目標問題。

優(yōu)化問題的數學模型簡化為

其中，X為Rn中的一個非空多面體子集，即任務不等拆分集Di；ΔTvec(X)為優(yōu)化目標函數，ΔTvec越接近0，分布式執(zhí)行程度越高，Tvec越小；約束條件中，優(yōu)化變量X取值范圍的最大值為，最小值為0；h(X)為式(12)中C2描述的等式約束；g(X)為式(12)中C3描述的不等式約束；Rn表示數值取自實數空間，因此可將式(12)中的優(yōu)化目標函數問題轉化成求解式(13)，拉格朗日函數為

其中，1λ和2λ為約束函數的加權因子。

在kX點根據二階泰勒公式近似展開為

其中，Sk為優(yōu)化問題的搜索方向；[B] 為擬牛頓法近似構造的海塞矩陣，符號?為梯度。拉格朗日函數的一階導數為

函數g(X)在Xk點展開的二階泰勒近似式為

活動三：尋找能量傳遞的規(guī)律。教師引導學生結合書本102頁的知識，用彩色木棒標識出主圖中能量的流動途徑。此部分在高中會詳細學習，為了降低難度，教師提供下列提示：

等式約束h(X)=0在Xk點展開的二階泰勒近似式為

將式(15)～式(18)聯合計算代入式(12)，經過整理得二次規(guī)劃子問題為

求解上述二次規(guī)劃子問題[29]，得到搜索方向Sk，沿搜索方向進行一維搜索，?k為第k次搜索的下降方向Sk的最優(yōu)步長，利用Wolfe 步長規(guī)則獲取，按照式(20)進行迭代更新，最終得到原問題的最優(yōu)解為

其中，[B] 為Lagrange 函數的Hessian 矩陣正定擬牛頓近似，并通過稠密半定牛頓近似法 BFGS（Broyden-Fletcher-Goldfarb-Shanno）進行計算，作為不斷更新的校正矩陣，搜索方向迭代更新矩陣Bk是的近似，更新式為

其中，Bk為n階對稱正定矩陣。

本文使用SQP 算法，利用擬牛頓法（變尺度法）來近似構造海塞（Hessian）矩陣[B]，以建立二次規(guī)劃子問題式(19)，又稱約束變尺度法。通過求解二次規(guī)劃子問題得到迭代的搜索方向Sk，沿搜索方向進行一維搜索，找到迭代的步長 ?k，利用式(21)更新修正Bk+1，最后按照迭代式(20)最終得到問題的最優(yōu)解Di，式(14)～式(21)為SQP的一般方法。偽代碼如算法2 所示。

算法2基于SQP 算法求解任務不等拆分集Di

4 仿真結果及性能分析

本節(jié)將評估所提算法在車輛移動下，通過SQP算法將任務不等拆分后在分布式協同執(zhí)行下的性能。使用各種度量來評估性能，如系統總時延、迭代次數，本文還研究了算法在不同參數設置下性能的表現。

4.1 仿真設置

本文采用V2X多節(jié)點分布式卸載策略，定義的道路場景如圖1 所示。在車輛數一定的情況下，道路上車輛服從泊松分布，主要實驗參數如表2 所示。為了獲得方法的一般性能，本文采用蒙特卡羅方法進行了1 000 次仿真，獲得平均性能以衡量方法的性能。車輛在直道上行駛的最大速度符合高速公路最大安全速度及車輛間安全行駛速度的規(guī)定，初始速度隨機在60 km/h 至最大速度之間選擇，并在單次仿真過程中保持不變。后述實驗過程中在沒有特殊說明情況下，均采用表2 中實驗參數[30]。

表2 主要實驗參數

4.2 仿真結果及分析

本節(jié)說明使用上述及本文所提協同卸載模型，分別改變任務量、上傳功率、車輛密度和車輛初始速度范圍，獲得系統總時延，比較分析CDOS-SQP的優(yōu)越性。

車輛總數N固定為25 輛，任務量與系統時延關系如圖2 所示。隨著計算任務量增加，本文所提CDOS-SQP的系統時延均低于對比策略。在任務量最大時，CDOS-SQP 策略系統時延相對最劣對比策略減少67%，相對最優(yōu)對比策略減少8%。當計算任務量較大時，CDOS-SQP的系統時延顯著優(yōu)于對比策略，并且隨著計算任務量的增加，CDOS-SQP增長速度相比其他策略較緩。造成上述結果的原因是，隨著計算任務量的不斷增加，系統的最優(yōu)策略會傾向于在邊緣側和本地聯合計算。而CDOS-SQP 相比對比策略可選擇協同節(jié)點數最多，因此CDOS-SQP的優(yōu)勢隨著計算任務量的增加更加明顯。

圖2 任務量與系統時延關系

計算任務量固定為50 MB，上傳功率與系統時延關系如圖3 所示。從圖3 中可以看出，策略只需在本地計算，所以上傳功率對的系統時延大小并無影響，而其余策略的任務卸載執(zhí)行時延隨著上傳功率的增大而減小。這是因為宿主車輛上傳功率增加會提高信噪比，從而增加信道容量，使采用邊緣卸載的策略上傳時延減小。同時CDOS-SQP 相比對比策略可用的協同節(jié)點數最多，且多協同節(jié)點采用分布式卸載策略并計算任務，其系統時延是最小的。通過實驗對比可知，本文策略優(yōu)于對比策略。

圖3 上傳功率與系統時延關系

相同計算任務下車輛密度的變化對系統時延的影響如圖4 所示。從圖4 可知，除外，其余策略隨著車輛密度的增加，系統時延不斷減小。造成上述現象的原因是：策略任務僅在本地執(zhí)行，車輛密度的變化對其沒有影響；而在其他卸載策略中，隨著車輛密度的不斷增大，可用的協同節(jié)點也隨著增多，由式(1)～式(6)可知，節(jié)點間歐氏距離越小，上傳時延也將越小，因此隨車密度增加，系統總時延減少。而CDOS-SQP 可用的協同節(jié)點最多，因此表現最優(yōu)。

圖4 車輛密度與系統時延關系

車輛密度為20 輛，總任務量為50 MB，車輛初始速度變化范圍與系統時延的關系如圖5 所示。結果表明，隨著初始速度變化范圍的增加，計算任務的系統時延不斷增大。從圖5 中可看出，車輛的運動速度對沒有產生影響，而對的結果會產生較大的波動。因為當車輛初始速度變化范圍越大時，宿主車輛與協同節(jié)點的連通時間將越短，使可用的協同節(jié)點數也將越少。所以對于和算法而言，全部任務只進行卸載計算影響最明顯。CDOS-SQP 性能最優(yōu)的原因是，同時采用本地和協同節(jié)點分布式執(zhí)行，并且可利用多協同節(jié)點進行并行計算執(zhí)行。

圖5 車輛初始速度變化范圍與時延關系

圖6給出了不同參數條件下迭代次數與收斂性的變化關系，展示了SQP 算法在不同參數下解決式(13)所示優(yōu)化問題的迭代次數。通過圖6 可知，當迭代34 次后實驗結果趨于平穩(wěn)，即趨于目標函數的最優(yōu)解。隨著迭代次數的增加，SQP 算法得到目標函數的值越來越接近滿足約束條件的最優(yōu)解。這表明SQP 算法解決式(13)所示優(yōu)化問題，具有迭代次數較少、收斂性較好的優(yōu)點。

圖6 迭代次數與收斂性的變化關系

5 結束語

本文對可拆分任務的V2X多節(jié)點分布式卸載策略進行研究?？紤]車輛行駛軌跡和最大時延約束，建立了基于博弈論的卸載策略和基于SQP算法的任務分配模型。利用博弈論中的重復剔除嚴格劣戰(zhàn)略和納什均衡確定出協同策略集；將原問題轉換為帶約束的高維非線性優(yōu)化問題，根據SQP 算法將該問題轉換為求解二次規(guī)劃子問題，利用拉格朗日和BFGS 方法得到最優(yōu)解，并分析了算法的收斂性。仿真結果表明，本文所提CDOS-SQP 具有較好的收斂性和優(yōu)越性。下一步的工作將研究更普遍的道路結構（如彎道、十字路口等多結構復雜道路場景）和考慮更精準的行駛軌跡預測的協同卸載問題。