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

薛建彬,安亞寧

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

1 引言

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

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

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

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

2 系統(tǒng)模型

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

Figure 1 System model圖1 系統(tǒng)模型

2.1 傳輸時間模型

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

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

(1)

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

2.2 計算模型

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

(2)

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

(3)

其中，k0表示有效電容系數(shù)，取決于設(shè)備的CPU結(jié)構(gòu)。

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

(4)

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

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

(5)

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

Oi=riτi1,?i∈N

(6)

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

(7)

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

(8)

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

(9)

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

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

(10)

其中，ki表示有效電容系數(shù)，取決于設(shè)備芯片結(jié)構(gòu)，本文令ki=10-21。

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

(11)

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

2.3 收益模型

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

Gi=φfpilog2(1+Oi)

(12)

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

3 問題描述

根據(jù)上述分析，通過優(yōu)化分配的計算任務(wù)量{l,Oi},i∈N，根據(jù)當前的網(wǎng)絡(luò)環(huán)境選擇為哪些AP卸載多少計算任務(wù)以及為本地分配多少任務(wù)量等，并優(yōu)化自身時延分配策略{τi1,τi2}，從而最小化系統(tǒng)開銷。本文給出了優(yōu)化目標函數(shù)如式(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)是任務(wù)量約束。

4 資源分配方案

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

4.1 基于拉格朗日乘子法的任務(wù)和時延分配優(yōu)化

本節(jié)通過拉格朗日分解方法簡化模型對問題進行求解。拉格朗日松弛算法已經(jīng)成功應用于許多優(yōu)化問題，如網(wǎng)絡(luò)優(yōu)化問題、生產(chǎn)調(diào)度問題及整數(shù)優(yōu)化問題等。首先證明所提優(yōu)化問題是一個凸問題。

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

證明首先，對目標函數(shù)U求各優(yōu)化變量的一階偏導，可得：

(14)

(15)

(16)

(17)

其次，對目標函數(shù)U求各優(yōu)化變量的二階偏導，可得：

(18)

(19)

(20)

(21)

顯然，目標函數(shù)U是各優(yōu)化變量的下凸函數(shù)，因此定理1成立。

□

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

(22)

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

(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 次梯度算法優(yōu)化拉格朗日乘子

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

(27)

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

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

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

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

步驟4判斷迭代是否終止。如果|Oi(t+1)-Oi(t)|<ε，|τi1(t+1)-τi1(t)|<ε，|τi2(t+1)-τi2(t)|<ε或t>Tmax，則終止迭代，所得即為最優(yōu)解；否則,令t=t+1，返回步驟2。其中，Tmax是最大迭代次數(shù)。

5 仿真結(jié)果及性能分析

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

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

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

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

Table 1 Simulation parameter setting表1 仿真參數(shù)設(shè)置

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

Figure 3 Relationship between total number of tasks and task allocation圖3 計算總?cè)蝿?wù)量和任務(wù)分配關(guān)系

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

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

Figure 4 Relationship between total number of tasks and system overhead圖4 計算總?cè)蝿?wù)量與系統(tǒng)開銷關(guān)系

Figure 5 Relationship between total tasks and task allocation under different distances圖5 不同距離下總?cè)蝿?wù)量與任務(wù)分配關(guān)系

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

6 結(jié)束語

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