基于邊緣云和移動(dòng)輔助設(shè)備的計(jì)算卸載優(yōu)化方案

方加娟 李 凱

1(鄭州職業(yè)技術(shù)學(xué)院軟件工程系 河南 鄭州 450121)2(南京理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 江蘇 南京 210094)

0 引 言

近年來，全球移動(dòng)設(shè)備的數(shù)量急劇增加，隨著移動(dòng)設(shè)備的普及，覆蓋不同領(lǐng)域的新的應(yīng)用程序如人臉識(shí)別、增強(qiáng)現(xiàn)實(shí)、自然語言處理和交互式游戲相繼出現(xiàn)。這些應(yīng)用具有密集的計(jì)算需求。為了滿足現(xiàn)實(shí)計(jì)算需求，移動(dòng)邊緣計(jì)算(Mobile Edge Computing，MEC)的概念被研究人員提了出來[1-2]。

移動(dòng)邊緣計(jì)算[3]是指將移動(dòng)網(wǎng)絡(luò)與互聯(lián)網(wǎng)有效地結(jié)合，利用在移動(dòng)網(wǎng)絡(luò)邊緣部署的計(jì)算、存儲(chǔ)和處理功能，為用戶提供高帶寬和超低時(shí)延的網(wǎng)絡(luò)服務(wù)解決方案。計(jì)算卸載[4]作為 MEC 架構(gòu)中的一項(xiàng)關(guān)鍵技術(shù)，是指終端設(shè)備將部分或全部計(jì)算任務(wù)交給云計(jì)算環(huán)境處理的技術(shù)。基于MEC的計(jì)算卸載技術(shù)可以提高移動(dòng)設(shè)備的性能，通過節(jié)省移動(dòng)設(shè)備的能耗來延長設(shè)備的工作時(shí)間。

盡管計(jì)算卸載技術(shù)可以很好地提高移動(dòng)設(shè)備端的能力，但仍存在諸多問題，計(jì)算卸載效率問題是其中之一。在具有大量計(jì)算密集型任務(wù)的CUE的延遲敏感系統(tǒng)中，當(dāng)多個(gè)移動(dòng)用戶同步通過無線信道進(jìn)行計(jì)算卸載時(shí)，設(shè)備之間勢必會(huì)出現(xiàn)相互干擾，從而降低數(shù)據(jù)傳輸速率，導(dǎo)致數(shù)據(jù)傳輸時(shí)間的延長。因此，在計(jì)算資源有限的情況下，將所有CUE的任務(wù)卸載到云端并不總是明智的[5]。如今，隨著移動(dòng)設(shè)備的性能穩(wěn)步提高，許多移動(dòng)設(shè)備并沒有充分利用它們的處理器，因此將任務(wù)卸載到這些臨近閑置移動(dòng)設(shè)備是一個(gè)誘人的選擇。為了平衡功耗與服務(wù)響應(yīng)時(shí)間，移動(dòng)設(shè)備需要合理選擇卸載至云端和移動(dòng)終端處理的應(yīng)用部分。柳興等[6]通過遺傳算法來搜索移動(dòng)終端和云端計(jì)算資源聯(lián)合執(zhí)行應(yīng)用的全局最優(yōu)解，主要研究了遷移任務(wù)的選擇問題。張文柱等[7]從移動(dòng)終端硬件出發(fā)，在能耗方面進(jìn)行了優(yōu)化處理。曹儐等[8]提出一種利用臨近閑置移動(dòng)終端作為卸載目標(biāo)的分布式博弈算法，給出一種最優(yōu)結(jié)果。Ti等[9]給出了一種在移動(dòng)用戶、移動(dòng)對等點(diǎn)設(shè)備和云端之間進(jìn)行聯(lián)合計(jì)算卸載的非中心式博弈算法，通過多用戶的設(shè)置制定了資源分配的優(yōu)化方案，有效提高了計(jì)算卸載效率問題。

為了盡可能縮短CUE任務(wù)的完成時(shí)間，本文在文獻(xiàn)[9]研究的基礎(chǔ)上做進(jìn)一步的探索，主要考慮以下幾點(diǎn)：識(shí)別具有空閑計(jì)算資源的輔助用戶設(shè)備HUE；決策對等點(diǎn)和云端之間的計(jì)算卸載平衡；云計(jì)算資源的分配問題。由于HUE不需要消耗它們有限的能量來為其他人計(jì)算，引入了帶寬激勵(lì)的概念，探討交換帶寬計(jì)算活動(dòng)的好處。

1 移動(dòng)邊緣計(jì)算

MEC是由歐洲電信標(biāo)準(zhǔn)協(xié)會(huì)ETSI提出的基于5G 演進(jìn)架構(gòu)的一項(xiàng)新技術(shù)。移動(dòng)邊緣計(jì)算借助邊緣計(jì)算中心在無線接入網(wǎng)(RAN)內(nèi)提供IT服務(wù)環(huán)境、云計(jì)算和存儲(chǔ)功能，其目標(biāo)是減少網(wǎng)絡(luò)延遲，確保高效的網(wǎng)絡(luò)運(yùn)營和服務(wù)交付，并提高用戶體驗(yàn)。

1.1 MEC基本架構(gòu)

移動(dòng)邊緣計(jì)算的關(guān)鍵要素是集成在RAN元素上的移動(dòng)邊緣計(jì)算IT應(yīng)用服務(wù)器。MEC的基本框架如圖1所示，該框架從一個(gè)比較宏觀的層次出發(fā)，對MEC架構(gòu)下不同的功能實(shí)體進(jìn)行了網(wǎng)絡(luò)層、移動(dòng)邊緣主機(jī)層和移動(dòng)邊緣系統(tǒng)層的劃分。其中MEC主機(jī)層包含主機(jī)(ME host)和相應(yīng)的主機(jī)層管理實(shí)體(ME host-level management entity)，ME主機(jī)又可以進(jìn)一步劃分為ME平臺(tái)(ME platform)、ME應(yīng)用(ME application)和虛擬化基礎(chǔ)設(shè)施(Virtualization Infrastructure)。網(wǎng)絡(luò)層主要包含3GPP蜂窩網(wǎng)絡(luò)、本地網(wǎng)絡(luò)和外部網(wǎng)絡(luò)等相關(guān)的外部實(shí)體，該層主要表示MEC工作系統(tǒng)與局域網(wǎng)、蜂窩移動(dòng)網(wǎng)或者外部網(wǎng)絡(luò)的接入情況。最上層是 ME系統(tǒng)層的管理實(shí)體，負(fù)責(zé)承載應(yīng)用程序及MEC系統(tǒng)的全局掌控。

圖1 MEC架構(gòu)示意圖

1.2 MEC計(jì)算卸載技術(shù)

MEC計(jì)算卸載技術(shù)不僅解決了移動(dòng)設(shè)備在計(jì)算性能、資源存儲(chǔ)和能效方面的不足，還減輕了核心網(wǎng)的壓力，降低了因傳輸帶來的時(shí)延。計(jì)算卸載主要包含資源分配和卸載決策兩個(gè)方面。資源分配主要研究將資源卸載到哪里的問題；卸載決策則研究的是用戶終端如何卸載和卸載內(nèi)容的問題。圖2為計(jì)算卸載決策和資源分配示意圖。其中：(a)為CUE卸載決策的3種方式，分別是本地執(zhí)行、完全卸載和部分卸載，具體決策結(jié)果可通過CUE能量消耗和完成計(jì)算任務(wù)時(shí)延決定；(b)為計(jì)算卸載的資源分配方案，該方案采用MDP 解決了在SCeNB中的虛擬機(jī)(Virtual Machine，VM)分配問題。CUE1通過創(chuàng)建VM，將計(jì)算任務(wù)全部卸載到SCeNB1上。對于CUE2，考慮到從SCeNB1到其他SCeNB的時(shí)延問題，CUE2在時(shí)延更低的SCeNB3上進(jìn)行計(jì)算卸載。但是，如果考慮VM的遷移成本時(shí)，一般會(huì)在MEC計(jì)算資源充足的情況下，優(yōu)先選擇近距離的MEC中進(jìn)行卸載。

圖2 計(jì)算卸載決策和資源分配示意圖

2 計(jì)算卸載方案

考慮一個(gè)與邊緣云關(guān)聯(lián)的基站，可以服務(wù)N個(gè)CUE，每個(gè)CUE都有一個(gè)計(jì)算密集型任務(wù)要執(zhí)行。同時(shí)，附近還存在M個(gè)帶有空閑處理器的HUE。為了激勵(lì)HUE輔助CUE進(jìn)行計(jì)算卸載，CUE需要分出一部分可用帶寬給HUE，因此，假設(shè)每個(gè)HUE至多可以幫助一個(gè)CUE，不考慮用戶的移動(dòng)性和切換的情況下，每個(gè)CUE有兩個(gè)選擇：

(1)將其任務(wù)卸載到邊緣云上，這時(shí)CUE的全帶寬可用于卸載，因此卸載延遲被最小化，但是對任務(wù)應(yīng)用的計(jì)算能力降低。

(2)將部分帶寬提供給一個(gè)HUE，然后將部分任務(wù)卸載到云，另外部分則卸載到該HUE。此時(shí)由于只有部分帶寬可供卸載導(dǎo)致卸載延遲會(huì)增加，但是具備更多的應(yīng)用計(jì)算能力。

2.1 通信模型

每個(gè)CUE都具備一定的帶寬B(以赫茲為單位)，假設(shè)αi,j∈(0,1)是HUEj協(xié)助CUEi所需的帶寬份額。當(dāng)CUEi卸載到HUEj和利用基站卸載到邊緣云時(shí)，CUEi到HUEj和基站的遍歷瑞利衰落信道容量分別為：

(1)

(2)

在CUEi所提供的帶寬上，HUEj達(dá)到了其預(yù)期接收器的比特率，其規(guī)模增益為gj：

(3)

2.2 計(jì)算模型：云-HUE卸載

(4)

(5)

(6)

(7)

(8)

(9)

本文忽略了發(fā)送計(jì)算結(jié)果所花費(fèi)的時(shí)間，因?yàn)橄鄬τ谳斎霐?shù)據(jù)，輸出數(shù)據(jù)的大小往往很小。

2.3 計(jì)算模型：僅云卸載

假設(shè)現(xiàn)在一個(gè)CUEk(k∈C,k≠i)只將其任務(wù)的一部分卸載到云上。總的完成時(shí)間為：

(10)

3 資源分配和解決方案

讓π表示所有用戶的一個(gè)集合分區(qū)，其中每個(gè)子集都有一個(gè)CUE，最多有一個(gè)HUE，Π表示所有這些可能分區(qū)的集合。例如，當(dāng)C={1,2}和H={1}時(shí)，有三個(gè)分區(qū):

Π={{1,1},{2}},{{1},{2,1}},{{1},{2}}

(11)

在每個(gè)子集中，第一項(xiàng)和第二項(xiàng)分別是CUE和HUE，假設(shè)ρδ和ζδ分別表示δ集合中具有基數(shù)1和2的子集，例如δ={{1}，{2，1}}表示CUE1只卸載到云上，而CUE2卸載到云和HUE1上，ρδ={1}，ζδ={2，1}。然后，決定哪個(gè)HUE與每個(gè)CUE配對，哪個(gè)任務(wù)共享卸載到配對的HUE和云，以及如何在用戶之間劃分云資源的問題可以表示為：

(12)

由于αi,j<1，所以

(13)

3.1 HUE固定分配

假定HUE到CUE的分配是固定的，并且優(yōu)化擴(kuò)展到任務(wù)共享以卸載和用戶之間的云資源分區(qū)。

3.1.1最佳解決方案

對于給定的HUE分配δ，式(12)可以變?yōu)椋?/p>

(14)

式中：ζδ表示δ集合中基數(shù)為2的子集。

(15)

可以獲得：

(16)

Tk≤Vk∈ρδ

(17)

本文應(yīng)用迭代技術(shù)來最優(yōu)求解式(16)，對于迭代t，使用式(17)和式(18)將其中的第一約束轉(zhuǎn)換為單項(xiàng)式：

(18)

式中：λ1(t)、λ2(t)、λ3(t)為：

(19)

同樣，對于每次迭代t，第四約束條件可以通過式(17)和式(18)將其轉(zhuǎn)換為單項(xiàng)式：

(20)

式中：γ1(t)、γ2(t)為：

(21)

總而言之，迭代t要解決的整體優(yōu)化問題是：

(22)

s.t. 式(18) ?{i,j}∈ζδ

式(20)k∈ρδ

當(dāng)|V(t)-V(t-1)|<ε，0≤ε<1時(shí)迭代終止。

算法1基于GP的固定HUE分配算法

2.while true do

t=t+1;

計(jì)算λ1(t)、λ2(t)、λ3(t);

if |V(t)-V(t-1)|≤εthen

Break;

end if

end while

3.1.2次優(yōu)云資源分配

在式(12)中，云資源的最佳分配取決于HUE分配。制定了一個(gè)獨(dú)立于這些任務(wù)的有效的次優(yōu)分配。為此，考慮每個(gè)CUE僅卸載到云的情況，即：

(23)

上述優(yōu)化問題類似于式(16)，因此可以使用基于GP的算法最佳地求解。通過求解式(23)得到的F′i值就是所尋求的次優(yōu)分配。

3.2 云資源固定分配

(24)

和

(25)

(26)

式(25)中的第一和第二約束分別隨MEC的增加而減小。因此，當(dāng)兩個(gè)約束都滿足相等條件時(shí)，就可以得到卸載到云中的最佳比特?cái)?shù):

(27)

CUEk僅云卸載的完成時(shí)間為:

(28)

3.3 HUE最佳分配

式(12)的最優(yōu)解可以通過搜索3.1.1節(jié)中描述的所有可能的HUE分配以及對每個(gè)HUE分配的優(yōu)化來獲得。但是，這需要搜索(M+N)!/M!個(gè)HUE分配。或者，從3.1.2節(jié)和3.2節(jié)中導(dǎo)出的用于云資源分配和卸載位數(shù)的次優(yōu)解中，因此HUE分配問題可以簡化為：

(29)

并通過一個(gè)二分圖形匹配算法對其進(jìn)行優(yōu)化求解。

(30)

(31)

(32)

式(32)中的HUE選擇問題可以表示為所定義的圖的瓶頸匹配(Bottleneck Matching，BM)問題，即最大邊緣權(quán)重盡可能小的最大匹配問題：

(33)

(a)圖形網(wǎng)絡(luò) (b)帶有虛擬頂點(diǎn)的圖像 (c)BM輸出

4 實(shí)驗(yàn)結(jié)果與分析

表1 模擬參數(shù)

本文主要對比4種不同的卸載方案：

(1)“HUE-云BM”方案，卸載量由式(24)、式(25)給出，HUE分配通過BM算法獲得。

(2)“HUE-云BM-GP”，首先獲得卸載量和HUE 分配，然后通過算法1求解式(16)，更新卸載量和云資源分配。

(3)“HUE-云 隨機(jī)選擇”，其中卸載量是式(24)、式(25)的解決方案，每個(gè)CUE隨機(jī)分配一個(gè)HUE。這個(gè)基線的復(fù)雜性是Ω(min(N,M))。

(4)“云”，僅卸載到云，這是任務(wù)計(jì)算的傳統(tǒng)選擇。

圖4-圖5為不同策略的完成時(shí)間對比，其中云的計(jì)算能力在4～20 GHz之間變化，圖4中有30個(gè)CUE和50個(gè)HUE存在網(wǎng)絡(luò)中，圖5則將網(wǎng)絡(luò)中的CUE和HUE的數(shù)量分別增加到70和100。可以發(fā)現(xiàn)，卸載到云和HUE的具有極大的優(yōu)勢，即便HUE是隨機(jī)分配的。算法1對計(jì)算結(jié)果的提升度很小，簡單的“HUE-云BM”方案即可達(dá)到理想的結(jié)果。

圖4 不同卸載方案的完成時(shí)間對比(CUE=30)

圖5 不同卸載方案的完成時(shí)間對比(CUE=70)

在圖6中，通過詳細(xì)檢查特定CUE任務(wù)的卸載延遲和計(jì)算時(shí)間，進(jìn)一步了解不同方案的性能。通過分析不同方案在本地、HUE與云的計(jì)算時(shí)間和卸載時(shí)間發(fā)現(xiàn)，計(jì)算時(shí)間在不同的處理器之間很平衡，并且卸載延遲時(shí)間在總時(shí)間中所占比例不高。

圖6 不同卸載方案的計(jì)算時(shí)間和卸載延遲對比

5 結(jié) 語

本文提出一個(gè)將計(jì)算卸載到邊緣云和移動(dòng)對等端的通用框架。該設(shè)計(jì)旨在保持應(yīng)用程序延遲需求的同時(shí)，最大限度地減少總計(jì)算時(shí)間。數(shù)值結(jié)果表明，通過帶寬激勵(lì)，將計(jì)算卸載到邊緣云和移動(dòng)對等端的方案是可行的。與將計(jì)算卸載到邊緣云方案相比，該方案具有較大的性能增益，在卸載延遲時(shí)間沒有明顯增加的情況下，總計(jì)算時(shí)間可以減少35%～40%。