移動邊緣計算中基于用戶體驗的計算卸載方案

楊 天,田 霖,孫 茜,張宗帥,王園園

(1.重慶郵電大學 通信與信息工程學院,重慶 400065;2.中國科學院計算技術研究所 a.無線通信技術研究中心; b.移動計算與新型終端北京市重點實驗室,北京 100190)

0 概述

隨著5G時代的到來,不斷涌現的增強現實[1]、圖像識別[2]等新興應用對計算能力的要求越來越高,但用戶設備的計算能力和續航能力限制了用戶體驗。對此,移動云計算(Mobile Cloud Computing,MCC)[3]可以作為一種有效的解決方案,但其同時給移動回傳網絡帶來了巨大的負載壓力,并且存在較高時延。針對這些問題,國內外研究機構與企業提出了移動邊緣計算(Mobile Edge Computing,MEC)[4]技術。MEC將云資源下沉到更接近用戶的位置,在網絡邊緣為用戶提供云服務。用戶可將計算任務卸載至MEC服務器中執行,從而擺脫終端設備計算能力的限制。此外,由于任務數據直接在無線接入網側進行處理,因此MEC能夠減輕回傳網絡的壓力,減小時延[5]。但由于MEC中無線資源與計算資源存在高度共享性,因此為保障用戶體驗,需要制定合理的計算卸載策略[6-7]。

在MEC計算卸載過程中,時延過高會導致一些應用無法正常使用,而能耗過高則會嚴重降低移動設備的電池壽命。因此,現有MEC計算卸載方案大多以時延和能耗為優化目標。文獻[8]提出一種基于馬爾科夫決策過程的時延優化卸載方案,通過分析每個計算任務的平均時延和移動設備的平均功耗并設計一維搜索算法,得到最優任務調度策略。文獻[9]設計一種啟發式方法對卸載任務進行調度,通過劃分用戶的計算任務,使所有用戶的任務平均完成時間最少。文獻[10]提出一種基于遺傳算法的次優算法,通過設計一個節能的計算卸載管理方案優化卸載決策、信道分配和計算資源分配過程,從而最小化系統能耗。文獻[11]提出一種基于人工魚群算法的能耗優化方案,從任務執行能耗和通信能耗兩方面對卸載問題進行建模,在計算資源和時延的約束下最小化總能耗。

以上研究僅針對單個指標進行優化,沒有對時延和能耗進行綜合考慮。文獻[12]對時延和能耗進行聯合優化,將計算卸載問題轉換為最小化任務執行開銷的多用戶卸載博弈問題,通過設計分布式計算卸載算法實現博弈的納什均衡。文獻[13]構建一種計算卸載和干擾管理集成框架,通過最小化任務開銷獲得最優卸載策略和資源分配。文獻[14]將計算卸載問題建模為任務執行成本最小化問題,其中執行成本由時延、能耗以及價格三部分組成,并通過設計分布式勢博弈算法和資源分配算法制定計算卸載策略。

在對時延和能耗進行聯合優化時,權重因子的設置十分關鍵。權重因子反映用戶對時延和能耗的關注程度,影響卸載策略的制定。上述研究為所有用戶統一設置固定的權重因子,表示所有用戶對時延和能耗的需求相同。然而在實際場景中,用戶需求往往存在差異,因此,統一設置固定的權重因子并不合理,會使制定的卸載策略難以保障用戶體驗。

針對固定權重因子無法應對用戶差異化需求的問題,本文提出一種基于用戶體驗的計算卸載方案,在多用戶移動邊緣計算場景下,聯合優化時延和能耗。利用用戶執行計算任務的時延和能耗性能增益率構建效用函數,將計算卸載問題建模為效用最大化問題,同時通過考慮設備續航能力構建自適應權重因子,對時延和能耗進行權衡。由于所提問題是一個混合整數非線性規劃問題(Mixed Integer Nonlinear Programming Problem,MINP),難以直接進行求解,因此將其拆分為卸載決策和資源分配兩個子問題,分別通過功率分配算法、計算資源分配算法和計算任務卸載決策算法進行求解,得到最終的計算卸載策略。

1 系統模型

給出一個多用戶移動邊緣計算場景,如圖1所示,其由一個配備有MEC服務器的宏蜂窩小區和多個用戶組成。系統帶寬劃分為N個子信道,每個子信道的帶寬為W。用戶設備通過OFDMA的方式與基站關聯,每個卸載用戶占用一條子信道,不同用戶設備之間不存在干擾。小區中用戶數量為I,用集合Iu={1,2,…,I}表示。假設每個用戶都有一個計算任務需要執行,用戶i的計算任務表示為Ti={di,ci},其中,di是任務的輸入數據量,ci是完成任務所需的CPU周期。參數di和ci都可以通過軟件分析得到[8]。

圖1 多用戶移動邊緣計算場景Fig.1 Scenario of multi-user mobile edge computing

用戶根據需求可以在本地執行計算任務,也可以將任務卸載到MEC服務器中執行。本文假設所有用戶的計算任務是不可分割的,每個用戶具有不同的本地計算資源和續航能力,并且無論是本地執行還是卸載執行都可以滿足任務的最低時延要求。

1.1 本地計算模型

(1)

對于本地執行能耗的計算,本文使用一種被廣泛采用的每周期計算能耗模型ε=κf2[15-16],其中,κ是一個與芯片架構有關的能量因子,此處取κ=10-26。因此,用戶i的本地執行能耗為:

(2)

1.2 卸載計算模型

任務卸載執行時,用戶通過基站將任務數據發送到MEC服務器,由MEC服務器進行數據處理,并將結果反饋給用戶。因此,任務卸載執行的時延包括3個部分,即卸載任務到MEC服務器的上行傳輸時延、MEC服務器的處理時延和反饋結果的下行傳輸時延[5]。

用戶i的上行傳輸速率為:

(3)

其中,pi為用戶i的上行發射功率,hi為信道增益,σ2為噪聲功率。

得到上行速率后,根據已知的輸入數據量,可以計算得到用戶i的上行傳輸時延為:

(4)

(5)

由于反饋結果的數據量遠小于輸入數據(系統設置、程序代碼和輸入參數)的大小,下行傳輸的時延在計算卸載研究中往往可以忽略不計[17-18],因此本文不考慮下行傳輸的時延。用戶i任務卸載執行的總時延為:

(6)

對于卸載執行能耗的計算,由于MEC服務器通過電纜供電,因此本文不考慮MEC服務器的執行能耗[10-12]。用戶i的卸載執行能耗為:

(7)

2 計算卸載問題

2.1 用戶效用

任務卸載執行的目的是獲得比本地執行更好的性能表現,從而提升用戶使用體驗。因此,本文采用時延和能耗的性能增益率作為效用函數。性能增益率[19]表示為:

(8)

其中,Dgr和Egr分別是時延和能耗的增益率。進而用戶i的效用定義為:

(9)

2.2 自適應權重因子

(10)

(11)

其中,ε是一個縮放因子,用于調節電量剩余率與權重因子的對應關系。由式(10)和式(11)可知,每個用戶的權重因子大小與自身剩余電量相關,高電量用戶的時延權重因子更大,低電量用戶的能耗權重因子更大。

2.3 問題描述

將計算卸載問題轉化為一個資源約束下的系統效用最大化問題,定義為:

s.t.

C1:ai∈{0,1},?i∈Iu

C3:0

(12)

其中:A表示卸載用戶集合;P表示卸載用戶的功率分配集合;F表示卸載用戶的計算資源分配集合;pmax為用戶設備的最大發射功率;fmax為MEC服務器計算資源總量;約束條件C1限制用戶的卸載決策變量為二進制整數變量;約束條件C2表示卸載的用戶數不得超過子信道數;約束條件C3表示卸載用戶設備的發射功率不得大于最大發射功率;約束條件C4保證卸載集合中的用戶都能獲得MEC服務器分配的計算資源;約束條件C5表示所有卸載用戶分配到的計算資源總和不得超過MEC服務器資源總量。

式(12)是一個混合整數非線性規劃問題,其為NP難問題。因此,本文將該問題分解為卸載決策子問題和資源優化子問題分別求解。

3 基于用戶體驗的計算卸載方案

將式(12)改寫為如下形式:

s.t. C1～C5

(13)

由于約束條件中卸載決策變量和資源分配變量完全解耦,因此可以將式(13)拆分成資源分配和卸載決策兩個子問題分別求解。首先固定卸載決策變量求解資源分配問題,然后在確定資源分配的情況下進行卸載決策求解。

3.1 資源分配

由式(13)拆分出的資源分配子問題為:

s.t. C3～C5

(14)

對于給定的卸載策略,將式(8)和式(9)代入式(14),得到:

(15)

(16)

可以看出,式(15)中減號左側項為常數,因此,求解式(15)的最大值等價于求解式(16)的最小值。將式(1)～式(7)代入式(16)后,資源分配子問題轉化為:

(17)

根據式(17)可進一步將資源分配問題分解為上行發射功率分配問題和計算資源分配問題。

3.1.1 上行發射功率分配

由式(17)拆分出的上行功率優化子問題為:

s.t. 0

(18)

由于g(pi)的二階導數在定義域中并不總是為正,因此式(18)問題是非凸的。在文獻[19]中,該問題已被證明是一個擬凸問題。本文采用文獻[20]提出的二分法對其進行求解。

g(pi)的一階導數為:

(19)

可以看出,g′(pi)的正負完全取決于等號右側的分子部分,令:

(20)

算法1上行發射功率分配二分法

輸入pmax,θi,φi,ni,ε,ei

根據式(20)計算υ(pmax)

ifυ(pmax)≤0 then

else

令ph=0,pt=pmax

repeat

pm=(ph+pt)/2

ifυ(pm)≤0 then

ph=pm

else

pt=pm

end if

until(pt-ph)≤ξ

end if

3.1.2 計算資源分配

由式(17)拆分出的計算資源分配子問題為:

s.t. C3,C4

(21)

(22)

(23)

3.2 卸載決策

由式(13)拆分出的卸載決策子問題為:

s.t. C1,C2

(24)

經過資源分配后,卸載決策子問題轉化為:

s.t.|A|≤N

(25)

假設已有卸載用戶集合S,記ΔU(S∪i)為用戶i加入S后系統效用的增量,則有:

ΔU(S∪i)=U(S∪{i})-U(S)=1-Δ(i)-Δ(i|S)

(26)

可以看出,Δ(i)與卸載決策無關,在得到功率分配后這一項變成常量,且恒大于0。Δ(i|S)是一個與當前卸載用戶集合大小有關的變量,其隨卸載用戶集合規模的增大而增大。因此,ΔU(S∪i)是一個隨卸載用戶集合增大而減小的單調遞減函數。若ΔU(S∪i)>0,則表明將用戶i加入當前的卸載用戶集合S后系統效用增大。

當S=?時Δ(i|S)取到最小值0,此時Δ(i)在功率分配后是已知的。因此,當ΔU(S∪i)=1-Δ(i)時ΔU(S∪i)取到最大值,記為ΔU(S∪i)max。若ΔU(S∪i)max≤0,則表明卸載用戶i肯定無法使得系統效用增大,那么用戶i需要直接在本地執行計算任務。令集合AL表示初始本地執行集合,在分配功率后可以直接篩選出所有ΔU(S∪i)max<0的用戶并添加至AL。

如前所述,ΔU(S∪i)隨著集合S規模的增大而減小。得到AL后可以求得ΔU(S∪i)的最小值,即ΔU(S∪i)min=ωi-Δ(i)-Δ(i|Smax),其中,Smax=Iu(AL∪{i})。如果ΔU(S∪i)min≥0,則表明將用戶i加入卸載集合能夠增加系統效用,即使卸載用戶集合的規模已經達到上限。令集合AC表示初始卸載用戶集合,將所有滿足ΔU(S∪i)min≥0的用戶篩選出來直接添加至其中。確定AL和AC后,Iu中剩余用戶組成集合ARE。

基于以上分析,本文提出一種計算任務卸載決策算法。首先根據最大和最小效用增量進行初始決策,得到AL和AC,然后根據AC中用戶數與子信道數的關系進行二次決策。算法描述如下:

算法2計算任務卸載決策算法

輸出A,F

初始化AL=?,AC=?,ARE=?,S=Iu

//初始決策

根據ΔU(S∪i)max是否小于0得到AL

根據ΔU(S∪i)min是否大于0得到AC

//二次決策

令A←AC

if|A|≥N then

while|A|>N

update A=A{i}

根據式(22)計算F

end while

else

repeat

//加入效用最大且系統效用增量為正的用戶

if ΔU(A∪i)>0

update A=A∪{i}

根據式(22)計算F

end if

until|A|=N or ∑U=max∑U

end if

4 仿真與結果分析

對本文方案進行仿真及分析驗證。考慮一個多用戶移動邊緣計算場景,小區中用戶隨機分布,信道建模采用l-α,其中,l為用戶到基站的距離,α為路徑損耗因子,此處取α=3[10]。計算任務為人臉識別任務,輸入數據量di為420 KB,所需CPU周期數ci為1 GHz/s[15,20]。其他仿真參數如表1所示。

表1 仿真參數Table 1 Simulation parameters

選用以下方案與本文方案進行對比:

方案1全部本地執行,即小區中所有用戶的計算任務在本地執行。

方案2固定時延因子為0.5,即所有用戶時延權重因子統一設置為0.5,能耗權重因子設置為0.5。

方案3固定時延因子為0.2,即所有用戶時延權重因子統一設置為0.2,能耗權重因子設置為0.8。

方案4固定時延因子為0.8,即所有用戶時延權重因子統一設置為0.8,能耗權重因子設置為0.2。

4.1 不同用戶總數下的系統性能

各方案在不同用戶總數下的卸載用戶數對比如圖2所示。可以看出,當用戶總數小于5時,5個方案中所有用戶都完成了卸載執行任務,此后隨著用戶總數的增加,各方案的卸載用戶數出現差異,時延權重因子的值越小,卸載用戶數越多。本文方案在相同用戶總數的情況下卸載用戶數僅次于時延因子設置為0.2的方案,而在全部本地執行的方案下,所有用戶本地執行任務,因此卸載用戶數為0。

圖2 不同用戶總數下的卸載用戶數Fig.2 Number of offloading users under different total number of users

不同用戶總數下各方案的性能對比如圖3所示。由圖3(a)可以看出:全部本地執行方案系統效用為0;在固定權重因子方案中,時延因子越小系統效用越大;本文方案的系統效用僅低于方案3。由圖3(b)可以看出:全部本地執行方案耗費能量最多;在固定時延因子的方案中,時延因子越小能耗越小;本文方案的能耗較低,僅高于方案3。由圖3(c)可以看出:時延因子越小時延越高,尤其是在系統效用和能耗指標中處于最好水平的方案3,總時延在各方案中也為最高;全部本地執行方案的總時延處于次優水平;本文方案的總時延小于方案3,但高于其他方案。

綜上所述,任務卸載執行能夠顯著降低能耗。對于時延性能而言,當卸載用戶數較少時能夠分得充足資源,因此,卸載時延會低于本地執行時延,這也是圖3(c)中方案4總時延低于方案1的原因。但是當卸載人數較多時(例如方案3),卸載用戶分得的資源變少,此時卸載時延會高于本地執行時延。

圖3 不同用戶總數下的系統效用、能耗和時延Fig.3 System utility,energy consumption and delay under different total number of users

雖然在系統效用對比中,方案3的系統效用高于本文方案,但對于具有不用剩余電量的用戶而言,整體效用的大小不能完全反映實際的用戶體驗。當用戶存在差異化需求時,為追求整體效用可能會犧牲一些用戶的體驗。下文將對此進行驗證。

4.2 不同電量剩余率下的用戶任務執行時延和能耗

以電量剩余率作為變量,生成10個具有隨機剩余電量的用戶,在不同方案下制定卸載策略,通過對比這些用戶的任務執行時延和能耗,驗證本文方案對于滿足用戶差異化需求的有效性,其中不同的剩余電量映射不同的用戶需求。

本文方案下的用戶電量剩余率如圖4所示,其中:電量剩余率高于0.7的用戶為高電量用戶,這些用戶的需求為更低時延;電量剩余率低于0.3的用戶為低電量用戶,這些用戶的需求為更低能耗;其余用戶屬于普通用戶,這些用戶沒有特別明確的某一方面性能要求。由此可見,在10個用戶中,用戶4及用戶6～用戶8屬于高電量用戶,用戶2、用戶5和用戶9屬于低電量用戶,其余用戶屬于普通用戶。

圖4 本文方案下的用戶電量剩余率Fig.4 Power remaining rate of users under the proposed scheme

本文方案與方案3、方案4下各用戶的卸載決策如圖5所示。可以看出:在方案3下,除用戶2以外的其他所有用戶都卸載執行任務;在方案4下,用戶5和用戶10選擇卸載執行,其中用戶5是低電量用戶,用戶10是普通電量用戶,其余低電量用戶的任務在本地執行;在本文方案下,用戶1、用戶2、用戶5、用戶9和用戶10卸載執行,所有低電量用戶均選擇卸載執行任務,其余卸載用戶的電量也相對較低,處于即將進入低電量狀態。

圖5 3種方案的卸載決策對比Fig.5 Offloading decision comparison of three schemes

本文方案與方案3、方案4的時延和能耗對比如圖6和圖7所示。可以看出:卸載用戶過多,使得每個用戶分得計算資源過少,方案3下所有用戶的時延較其他方案最高,導致更關注時延的高電量用戶(用戶4及用戶6～用戶8)體驗較差,但大量用戶卸載使得能耗得到降低,低電量用戶5和低電量用戶9體驗良好,而低電量用戶2未得到卸載,能耗過高;在方案4下,大量用戶本地執行任務,時延較其他方案最低,卸載執行的用戶5和用戶10獲得大量計算資源,得到比本地執行任務更低的時延;然而從能耗上看,方案4下除卸載用戶以外其余所有用戶能耗都過高,這對低電量用戶的體驗產生了負面影響;本文方案中卸載執行任務的用戶時延較高,但仍低于方案3,并且這些用戶都屬于低電量用戶,更關注能耗,而所有高電量用戶都在本地執行任務,時延較低,從而保障了這些用戶的體驗;從能耗上看,卸載執行的用戶能耗大幅度降低,其中包括所有低電量用戶以及用戶1和用戶10這兩個即將變為低電量狀態的用戶,保障了這些用戶的體驗,用戶3、用戶4及用戶6～用戶8的能耗較高,但是由于這些用戶電量充足,因此影響不大。由此可知,本文方案制定的卸載策略更為合理。

圖6 3種方案的時延對比Fig.6 Delay comparison of three schemes

圖7 3種方案的能耗對比Fig.7 Energy consumption comparison of three schemes

綜上所述,固定權重因子的方案無法滿足差異化的用戶需求,而本文提出的計算卸載方案可根據用戶實際情況自適應調整權重因子大小,使時延和能耗之間得到有效平衡,能夠保障用戶的良好體驗。

5 結束語

為滿足具有不同剩余電量用戶的不同計算卸載需求,本文提出一種考慮用戶體驗的計算卸載方案。通過構造基于電量剩余率的自適應權重因子,描述用戶在完成計算任務時對時延和能耗的要求。該方案可根據用戶狀態制定合理的卸載策略和功率及計算資源分配策略,在滿足用戶對時延和能耗要求的前提下實現最大的系統效用,提升用戶體驗同時保證計算卸載的整體性能。本文方案假設計算卸載發生在準靜態場景,未考慮用戶移動性對計算卸載的影響,并且其僅針對單小區MEC系統制定卸載策略,未考慮多小區場景下的信道分配問題。因此,下一步將對超密集網絡場景下的多接入邊緣計算卸載方案和動態信道下的計算卸載方案進行研究。