方加娟 李 凱

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

0 引 言

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

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

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

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

1 移動邊緣計算

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

1.1 MEC基本架構(gòu)

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

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

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

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

圖2 計算卸載決策和資源分配示意圖

2 計算卸載方案

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

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

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

2.1 通信模型

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

(1)

(2)

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

(3)

2.2 計算模型：云-HUE卸載

(4)

(5)

(6)

(7)

(8)

(9)

本文忽略了發(fā)送計算結(jié)果所花費的時間，因為相對于輸入數(shù)據(jù)，輸出數(shù)據(jù)的大小往往很小。

2.3 計算模型：僅云卸載

假設(shè)現(xiàn)在一個CUEk(k∈C,k≠i)只將其任務(wù)的一部分卸載到云上?？偟耐瓿蓵r間為：

(10)

3 資源分配和解決方案

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

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

(11)

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

(12)

由于αi,j<1，所以

(13)

3.1 HUE固定分配

假定HUE到CUE的分配是固定的，并且優(yōu)化擴展到任務(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)換為單項式：

(18)

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

(19)

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

(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時迭代終止。

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

2.while true do

t=t+1;

計算λ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分配。制定了一個獨立于這些任務(wù)的有效的次優(yōu)分配。為此，考慮每個CUE僅卸載到云的情況，即：

(23)

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

3.2 云資源固定分配

(24)

和

(25)

(26)

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

(27)

CUEk僅云卸載的完成時間為:

(28)

3.3 HUE最佳分配

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

(29)

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

(30)

(31)

(32)

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

(33)

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

4 實驗結(jié)果與分析

表1 模擬參數(shù)

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

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

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

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

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

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

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

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

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

圖6 不同卸載方案的計算時間和卸載延遲對比

5 結(jié) 語

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