基于邊緣計算的新型任務卸載與資源分配策略*

2020-06-22 12:29:48薛建彬安亞寧

計算機工程與科學 2020年6期

薛建彬,安亞寧

(蘭州理工大學計算機與通信學院，甘肅蘭州 730050)

1 引言

隨著移動互聯網和大數據技術的不斷發展，終端用戶需要運行越來越多的資源和計算密集型應用，如遠程醫療、圖像處理等[1]，但由于終端用戶本身的局限性，無法滿足密集型任務低時延、低功耗的需求，因此，為了提高終端用戶的滿意度，需要為終端用戶提供大量的計算和存儲資源。移動邊緣計算MEC (Mobile Edge Computing)通過在無線網絡邊緣為用戶提供計算、存儲和處理能力，由于MEC的鄰近性、低時延等優勢，MEC在時延敏感、實時性要求高、數據量大等場景中的應用中尤為常見[2]。但是，由于邊緣服務器的計算處理能力有限，在實際應用中，當有大量用戶和任務請求計算時，單個邊緣服務幫助終端處理任務時，將不足以為用戶提供計算資源，同時還產生了額外的開銷，從而無法滿足用戶體驗。因此，研究多個邊緣服務器協作，將計算資源進行合理分配，具有重要的現實意義。

針對邊緣計算中的任務卸載和資源分配,許多學者做了相關研究。Lin等人[3]提出一個D2D(Device-to-Device)協作的計算卸載和資源分配系統，以最小化任務執行成本。文獻[4]通過考慮二進制卸載模型，研究了終端設備的計算模式選擇、系統傳輸時間分配的聯合優化問題,旨在最大化所有終端設備的計算速率。文獻[5]研究了卸載決策和資源分配的聯合優化問題,目的是降低系統的總能耗。Wang等人[6]在延遲約束條件下，提出一種有效的卸載方案，通過聯合優化AP(Access Point)的能量波束成形、CPU周期數、卸載的任務數大小以及分配給每個用戶的時間，最小化AP端能耗。文獻[7]在延遲約束條件下，建立4個時隙協作協議下的三節點模型，通過聯合優化任務分配，最小化用戶和助手的總能耗。

文獻[3-7]僅研究了單個服務器的MEC系統，在此基礎上，有學者研究了多個MEC協作的系統。其中，文獻[8]提出了一種新的卸載方案，通過多個MEC-BS(Mobile Edge Computing Base Station)的協作進一步將額外任務卸載到與其連接的其他MEC-BS來增強MEC-BS的計算卸載服務，提高了終端的收益。Yang等人[9]提出一種由微基站和宏基站組成的雙層體系架構，用戶通過將計算任務卸載到微基站或由微基站中繼到宏基站來完成任務執行，有效降低了系統能耗。雖然文獻[8,9]在降低時延和能耗方面有良好的效果，但只考慮將終端的任務進行單一的劃分。進而，文獻[10]研究了將終端用戶的任務分割成多個子任務，并選擇卸載到邊緣的多個AP節點上的情況，通過聯合優化任務分配決策及其CPU頻率以最小化其能耗和任務的執行延遲，有效地降低了設備能耗和延遲。Wu等人[11]設計了無線供電的多用戶MEC系統，用戶將其計算任務劃分為多個部分，分別進行本地計算和邊緣計算，以最大化用戶的計算速率，即特定時間塊上的計算位數。

盡管上述關于MEC中任務卸載和資源分配的研究都有獨特解決方案，但仍存在一定的局限性。現有研究大多僅考慮單節點計算卸載和資源分配，對多節點協作計算的資源分配鮮有研究；同時，大多數研究僅考慮全部卸載或者單一任務劃分的部分卸載模型，對細粒度任務劃分很少涉及。基于此，本文提出一對多的廣播系統任務分配問題，即將每個終端用戶所需要計算的任務劃分為多個子任務，分別在自身設備和不同的AP上并行執行，在延遲約束條件下，設計了一種基于拉格朗日乘子法的任務分配優化算法，對用戶本身和不同參數的AP進行合理的任務分配，以聯合優化任務分配和執行時延，實現最小化系統開銷。

2 系統模型

圖1搭建了一個協同計算卸載任務分配系統，假設考慮系統中的一個具有可分割的待處理密集型任務的終端用戶，一個協助終端用戶處理任務的AP集合N={1,…,N},稱之為代理集合，第i(i∈N)個AP稱為代理i，表示為Ai。終端用戶UE通過本地計算和利用無線網絡將自身的任務卸載到代理AP進行任務處理，AP幫助計算處理之后將結果返回給用戶。

Figure 1 System model圖1 系統模型

2.1 傳輸時間模型

本文考慮具有持續時間T的一個特定時間塊，終端用戶和N個AP之間的計算卸載采用頻分多址FDMA(Frequency Division Multiple Access)協議，如圖2所示。終端用戶和AP之間的通信分配有帶寬為B的正交頻帶。對于每個代理Ai(i∈N)，該時間塊T被分為3個時隙，表示為τi1，τi2和τi3，分別用于終端用戶將計算任務Oi卸載到Ai，Ai進行遠程計算以及Ai將計算結果下載到終端用戶。考慮到卸載任務經過Ai處理之后，任務量大小遠遠小于原始任務量大小，因此本文忽略Ai將計算結果下載到終端用戶的時延τi3，即τi3=0。因此，時延必須滿足：

τi1+τi2≤T,?i∈N

(1)

Figure 2 FDMA-based computing offloading protocol圖2 基于FDMA的計算卸載協議

2.2 計算模型

每個用戶具有一個可分割的計算任務，可以任意地將計算任務劃分為(N+1)個部分，以便分別在用戶自身和代理AP處并行執行。為了便于分析，將終端用戶總的計算任務量表示為L(Mb)，用l表示用戶進行本地計算的任務量，用Oi表示第i個代理Ai分配的任務量。因此，計算任務量滿足以下約束：

(2)

(1) 終端用戶在整個時間塊T執行本地計算任務l時，用C0表示終端用戶計算單位比特卸載任務所需要的CPU周期數,因此本地計算的能耗為：

(3)

其中，k0表示有效電容系數，取決于設備的CPU結構。

進一步，本地能耗開銷表示為：

(4)

其中，0<ω0<1為本地能耗懲罰因子。

(2) 當用戶選擇將任務卸載到邊緣代理時，通過無線網絡傳輸會產生相應的傳輸時延和能耗開銷。故用戶端到代理Ai端的傳輸速率為：

(5)

因此，終端用戶卸載到Ai的任務量可表示為：

Oi=riτi1,?i∈N

(6)

在第1時隙，終端用戶將計算任務上傳到AP，在上傳過程中，產生的傳輸能耗為：

(7)

對式(5)～式(7)化簡可得：

(8)

所以，終端用戶(EU)傳輸、卸載任務總的能耗開銷為：

(9)

其中，0<ωi<1為傳輸能耗懲罰因子。

在第2時隙，每個AP對終端用戶上傳的任務進行遠程計算，Ci表示Ai計算單位比特卸載任務數所需要的CPU周期數，故Ai處理Oi任務消耗的能量為[6]：

(10)

其中，ki表示有效電容系數，取決于設備芯片結構，本文令ki=10-21。

因此，所有代理AP為終端用戶遠程計算任務總的能耗開銷為：

(11)

其中，0<αi<1為遠程執行任務時的能耗懲罰因子。

2.3 收益模型

系統的收益來自于邊緣代理，邊緣代理AP通過為用戶提供服務獲得收益，因此系統的收益函數與用戶的資源需求量密切相關，任務需求量越大，獲得的收益也越多。本文采用在移動云計算和無線網絡通信中普遍使用的對數函數表示計算任務卸載的效用收益[12]，因此終端用戶將Oi任務卸載到Ai獲得的收益表示為：

Gi=φfpilog2(1+Oi)

(12)

其中，fpi表示Ai的計算能力；φ是一個大于0的參量，與用戶QoS需求有關。

3 問題描述

根據上述分析，通過優化分配的計算任務量{l,Oi},i∈N，根據當前的網絡環境選擇為哪些AP卸載多少計算任務以及為本地分配多少任務量等，并優化自身時延分配策略{τi1,τi2}，從而最小化系統開銷。本文給出了優化目標函數如式(13)所示，將問題描述為(P1)：

(13)

s.t.τij≥0,j∈{1,2},?i∈N

(13a)

0≤l≤L

(13b)

0≤Oi≤L,?i∈N

(13c)

式(1)和式(2)

(13d)

其中，式(13a)表示時延約束，式(13b)、式(13c)是任務量約束。

4 資源分配方案

根據上述分析，終端用戶為了提高自身的任務處理效率，節省系統能耗，縮短時延，將會根據自身設備和不同的邊緣代理的屬性及信道環境，為不同代理和自身分配不同量的任務，以使系統開銷最小。

4.1 基于拉格朗日乘子法的任務和時延分配優化

本節通過拉格朗日分解方法簡化模型對問題進行求解。拉格朗日松弛算法已經成功應用于許多優化問題，如網絡優化問題、生產調度問題及整數優化問題等。首先證明所提優化問題是一個凸問題。

定理1目標函數U是優化變量(l,Oi,τi1,τi2)的凸函數。

證明首先，對目標函數U求各優化變量的一階偏導，可得：

(14)

(15)

(16)

(17)

其次，對目標函數U求各優化變量的二階偏導，可得：

(18)

(19)

(20)

(21)

顯然，目標函數U是各優化變量的下凸函數，因此定理1成立。

□

由于約束條件式(13a)～式(13d)是線性函數，所以(P1)問題是凸優化問題。本文采用拉格朗日對偶方法來獲得問題(P1)的最優解。λ≥0和μi≥0分別表示關于約束式(1)和式(2)的拉格朗日乘子，因此構造拉格朗日函數為：

(22)

(P1)問題的對偶函數為：

(23)

所以，(P1)問題的對偶問題表示為(P2)：

(24a)

s.t.λ>0,μ≥0

(24b)

因為(P1)問題是凸問題并且滿足Slater條件，因此原始問題(P1)和對偶問題(P2)存在強對偶性，因此，可以通過求解(P1)問題進而獲得(P2)問題的解。利用KKT條件可以得到：

(25a)

(25b)

(25c)

(25d)

(25e)

(25f)

(26a)

(26b)

(26c)

(26d)

4.2 次梯度算法優化拉格朗日乘子

對于拉格朗日求解的算法，證明局部最優解與全局最優解是基本一致的，其中次梯度算法是求解拉格朗日問題的有效方法[13]。因此，本文利用次梯度算法對拉格朗日乘子μi進行不斷迭代更新，得到優化變量的最優解。迭代公式為：

(27)

拉格朗日乘子更新算法具體步驟如下所示：

步驟1初始化參數精度ε>0,令t=1,μi(1)>0，根據式(26b)～式(26d)計算(Oi,τi1,τi2)。

步驟2根據式(27)更新拉格朗日乘子μi(t)。

步驟3再根據式(26b)～式(26d)更新(Oi,τi1,τi2)。

5 仿真結果及性能分析

為了驗證本文提出的最優任務和時延分配方案對系統性能的影響，采用Matlab仿真并分析所提方案的性能。本文取N=3，即有3個代理協助終端用戶處理密集型任務；對于不同的計算任務量，將系統總時延設定為等差數列，即當總任務量L=10時，取T=0.1，當總任務量L=200時，取T=2，任務量越大，執行任務所需要的時間越多。其它仿真參數如表1所示。本文采用2種基準方案作為對比方案，并將本文所提方案與文獻[3]所提方案進行對比分析。具體如下：

(1)僅本地計算方案。即傳統的任務處理方式，將用戶計算任務全部留在用戶端進行本地計算而不進行任務卸載，對應于本文參數設置為：l=L，Oi=0，τij=0，?i,j。

(2)等時間等任務分配方案。即將用戶請求計算任務平均分配給本地和邊緣代理服務器，以及將時間進行平均分配，對應于本文參數設置為τi1=τi2=T/2，l=Oi=L/4,i∈{1,2,3}。

(3)文獻[3]方案。選取與本文所采用參數匹配的參數對文獻[3]所提方案進行仿真，并與本文方案仿真結果進行對比分析。

Table 1 Simulation parameter setting表1 仿真參數設置

圖3所示是用戶端到邊緣代理1、代理2和代理3的距離di分別為80 m、60 m和40 m時，用戶端計算任務總量與任務分配量的關系。從圖3中可以看出，任務分配量隨任務總量的增大而增大，由于用戶本身具有固定的計算能力，所以隨著總任務量的增大，分配給用戶本身的任務基本趨于平穩。圖3中，距離用戶端較遠且計算能力較弱的代理1，被卸載較少的計算任務量；而距離用戶端較近且計算能力較強的代理2和代理3，會被分配較多的計算任務量，并且隨著用戶端計算任務量的不斷增大，代理2和代理3被分配的計算任務越來越多，而代理1變化較小，其原因在于代理1計算能力較弱且與用戶端之間的通信距離較大，造成的通信開銷也較大。

Figure 3 Relationship between total number of tasks and task allocation圖3 計算總任務量和任務分配關系

圖4描述了4種不同方案的系統開銷隨用戶端計算任務總量的變化曲線。如圖4所示，任務執行開銷均隨著輸入數據大小的增加而增加，原因在于較大的輸入數據需要較長的執行等待時間和較大的能量才能完成任務計算，從而導致較大的任務執行成本。

可以直觀看出，本文所提方案明顯優于2種基準方案，其原因在于所提MEC系統能實現任務的合理分配，使得本文方案具有較低的系統開銷。此外，等時間等任務分配的情況下，均衡任務和時間分配，不是最優的分配方案，因此開銷并未最小化；而僅考慮本地計算的情況，由于本地計算能力固定且較小，故所產生的系統開銷較大。比較從本文所提方案和文獻[3]中獲得的結果，可以看到本文提出的方案具有更好的性能，特別是當任務量較小時，任務執行開銷基本一致，而隨著任務量的不斷增大，本文所提方案更優于文獻[3]的。

Figure 4 Relationship between total number of tasks and system overhead圖4 計算總任務量與系統開銷關系

Figure 5 Relationship between total tasks and task allocation under different distances圖5 不同距離下總任務量與任務分配關系

圖5描述了用戶端到代理端的距離不同時，用戶總任務量與各個代理任務分配的關系。從圖5中可以看出，當距離相等時，計算能力較強的代理分配到的任務較多，其原因在于計算能力越強，幫助終端計算任務的能力越強，從而能耗和延遲較小，系統開銷也較小；另外，對于同一代理，分配到的任務量隨著距離的減小而增加，這與圖3的仿真分析結果相吻合。

6 結束語

本文研究了移動邊緣計算環境中，具有可分割的待處理密集型任務的終端用戶的計算卸載和資源分配問題。在考慮用戶時延的需求下，提出了以最小化系統所有實體開銷為目標的優化問題，開銷主要由能耗成本和卸載收益組成；然后基于拉格朗日法求解該約束優化問題，并為用戶本身和各個代理AP進行合理的任務分配；最后得到了最優的任務和時延分配結果，有效地降低了系統開銷，提升了系統整體性能。