薛建彬,安亞寧

(蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050)

1 引言

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

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

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

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

2 系統(tǒng)模型

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

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

2.1 傳輸時(shí)間模型

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

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

(1)

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

2.2 計(jì)算模型

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

(2)

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

(3)

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

進(jìn)一步，本地能耗開銷表示為：

(4)

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

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

(5)

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

Oi=riτi1,?i∈N

(6)

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

(7)

對(duì)式(5)～式(7)化簡(jiǎn)可得：

(8)

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

(9)

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

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

(10)

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

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

(11)

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

2.3 收益模型

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

Gi=φf(shuō)pilog2(1+Oi)

(12)

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

3 問題描述

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

4 資源分配方案

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

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

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

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

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

(14)

(15)

(16)

(17)

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

(18)

(19)

(20)

(21)

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

□

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

(22)

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

(23)

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

(24a)

s.t.λ>0,μ≥0

(24b)

因?yàn)?P1)問題是凸問題并且滿足Slater條件，因此原始問題(P1)和對(duì)偶問題(P2)存在強(qiáng)對(duì)偶性，因此，可以通過(guò)求解(P1)問題進(jìn)而獲得(P2)問題的解。利用KKT條件可以得到：

(25a)

(25b)

(25c)

(25d)

(25e)

(25f)

(26a)

(26b)

(26c)

(26d)

4.2 次梯度算法優(yōu)化拉格朗日乘子

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

(27)

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

步驟1初始化參數(shù)精度ε>0,令t=1,μi(1)>0，根據(jù)式(26b)～式(26d)計(jì)算(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àn)證本文提出的最優(yōu)任務(wù)和時(shí)延分配方案對(duì)系統(tǒng)性能的影響，采用Matlab仿真并分析所提方案的性能。本文取N=3，即有3個(gè)代理協(xié)助終端用戶處理密集型任務(wù)；對(duì)于不同的計(jì)算任務(wù)量，將系統(tǒng)總時(shí)延設(shè)定為等差數(shù)列，即當(dāng)總?cè)蝿?wù)量L=10時(shí)，取T=0.1，當(dāng)總?cè)蝿?wù)量L=200時(shí)，取T=2，任務(wù)量越大，執(zhí)行任務(wù)所需要的時(shí)間越多。其它仿真參數(shù)如表1所示。本文采用2種基準(zhǔn)方案作為對(duì)比方案，并將本文所提方案與文獻(xiàn)[3]所提方案進(jìn)行對(duì)比分析。具體如下：

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

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

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

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

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

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

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

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

Figure 4 Relationship between total number of tasks and system overhead圖4 計(jì)算總?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描述了用戶端到代理端的距離不同時(shí)，用戶總?cè)蝿?wù)量與各個(gè)代理任務(wù)分配的關(guān)系。從圖5中可以看出，當(dāng)距離相等時(shí)，計(jì)算能力較強(qiáng)的代理分配到的任務(wù)較多，其原因在于計(jì)算能力越強(qiáng)，幫助終端計(jì)算任務(wù)的能力越強(qiáng)，從而能耗和延遲較小，系統(tǒng)開銷也較小；另外，對(duì)于同一代理，分配到的任務(wù)量隨著距離的減小而增加，這與圖3的仿真分析結(jié)果相吻合。

6 結(jié)束語(yǔ)

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