李昌群，陳國龍

1.安徽糧食工程職業(yè)學(xué)院信息技術(shù)系，安徽合肥，231131；2.蚌埠學(xué)院計算機與信息工程學(xué)院，安徽蚌埠，233000

隨著網(wǎng)絡(luò)通信技術(shù)和物聯(lián)網(wǎng)的飛速發(fā)展，移動終端設(shè)備的數(shù)量呈指數(shù)式急劇增長。根據(jù)IOT ANALYTCS網(wǎng)站的報告，全球活躍的物聯(lián)網(wǎng)設(shè)備的數(shù)量到2025年將達到220億臺[1]。隨之而來的是各種各樣的移動應(yīng)用程序，例如虛擬現(xiàn)實(virtual reality)、人臉識別(face recognition)、自動駕駛(autonomous driving)，正在出現(xiàn)和改變著我們的生活[2]。這些移動應(yīng)用程序需要大量的計算資源和消耗大量的能量，而移動終端設(shè)備的計算資源和電池容量都有限，這不利于移動應(yīng)用程序的處理。傳統(tǒng)的方法是把移動應(yīng)用程序卸載到公有云，如Amazon EC2 和 Windows Azure的數(shù)據(jù)中心來處理，可以解決上述問題。但是由于公有云的數(shù)據(jù)中心離移動用戶比較遠，這會導(dǎo)致產(chǎn)生很長的傳輸延遲，這不利于需要實時處理的應(yīng)用程序。移動邊緣計算(Mobile Edge Computing，簡稱MEC)被認為是一種能夠解決資源密集型應(yīng)用和資源受限的移動設(shè)備之間矛盾的有前途的技術(shù)[3-4]。跟傳統(tǒng)的云計算不同的是，移動運營商擁有移動邊緣計算的數(shù)據(jù)中心，并且把云資源部署在蜂窩基站或者無線接入點，離終端用戶比較近，這可以大大地降低終端設(shè)備用戶和公有云數(shù)據(jù)中心之間由于長距離的傳輸所產(chǎn)生的延遲和核心網(wǎng)的處理壓力[5]。移動云計算和移動邊緣的比較如表1所示。

表1 移動云計算和移動邊緣計算的比較

和傳統(tǒng)的云計算相比，移動邊緣計算有以下4個明顯的優(yōu)勢[6]：

(1)移動終端設(shè)備的應(yīng)用程序產(chǎn)生的數(shù)據(jù)，邊緣端的服務(wù)器中預(yù)處理，這可以極大地減輕海量數(shù)據(jù)給核心網(wǎng)的網(wǎng)絡(luò)帶寬造成的壓力。

(2)把部分數(shù)據(jù)處理放在移動終端設(shè)備上進行，而不是全部放在云計算中心，通過利用部署在靠近用戶的服務(wù)器對采集到的數(shù)據(jù)進行處理，避免了與云數(shù)據(jù)中心的交互環(huán)節(jié)，降低了數(shù)據(jù)處理的響應(yīng)時間，提高了系統(tǒng)的性能。

(3)用戶的終端設(shè)備產(chǎn)生的數(shù)據(jù)是存儲在邊緣端的數(shù)據(jù)中心上，而不是存儲在公有云的數(shù)據(jù)中心中，這降低了用戶的敏感數(shù)據(jù)在上傳公有云的數(shù)據(jù)中心過程中被非法竊取的風(fēng)險，可以保護用戶的隱私數(shù)據(jù)安全。

(4)在移動邊緣計算系統(tǒng)中，數(shù)據(jù)不需要放到公有云的數(shù)據(jù)中心進行處理，這不但減少了數(shù)據(jù)從終端設(shè)備傳輸?shù)皆茢?shù)據(jù)中心的能耗，而且也極大地降低了云數(shù)據(jù)中心的能耗。

近些年來，得益于移動邊緣計算的以上這些優(yōu)勢，以自動駕駛(Autonomous Driving)、虛擬現(xiàn)實(virtual reality)等為代表的新型應(yīng)用得到了飛速的發(fā)展。這些新型的應(yīng)用對網(wǎng)絡(luò)傳輸延時、數(shù)據(jù)隱私保護和安全方面都有較高的要求[7]，由于移動邊緣計算能夠滿足它們的要求，因此基于移動邊緣計算的應(yīng)用和平臺越來越多地涌現(xiàn)出來了。

1 移動邊緣計算的相關(guān)研究

目前關(guān)于移動邊緣計算的相關(guān)研究主要涉及任務(wù)卸載和資源分配的兩個領(lǐng)域，研究工作的主要目標(biāo)可以分為如下3種：

其一，降低設(shè)備處理任務(wù)的能耗。例如，Liu等[8]在具有時間截止和傳輸錯誤率的約束條件下，探討一種在可接受的時延和通信質(zhì)量下最小化移動設(shè)備能耗的卸載決策方法。呂昕晨等[9]研究了MEC系統(tǒng)中時延敏感應(yīng)用的節(jié)能任務(wù)接納，提出了約束條件下的總能耗最小化邊緣服務(wù)器的計算資源和延遲。曾鳴等[10]研究了在傳輸資源和計算資源都稀缺的嚴格延遲限制的情況下，無線與無線聯(lián)合分配的傳輸能耗問題。胡錦天等[11]提出了一種任務(wù)遷移策略來優(yōu)化能耗，同時保持在任務(wù)遷移過程中的高性能。

其二，降低任務(wù)處理的時間。如王思華等[12]提出了一種多疊強化學(xué)習(xí)(RL)算法，避免相同資源分配方案和用戶狀態(tài)的重復(fù)學(xué)習(xí)，優(yōu)化頻譜分配和傳輸功率分配，最小化用戶間的最大計算和傳輸延遲。Fan等[13]提出了一種非合作博弈方法 ,通過分布式迭代算法解決了MEC服務(wù)器間的多類型任務(wù)卸載，實現(xiàn)了所有任務(wù)總執(zhí)行延遲的最小化。Liu等[14]比較混合多址傳輸場景中的三種卸載方式，并設(shè)計了一種有效算法，實現(xiàn)了用戶靈活地在混合非正交多址與正交多址傳輸間選擇最佳地卸載策略，以降低任務(wù)處理的時間。

其三，如何在任務(wù)處理時間和設(shè)備能耗間做出平衡和選擇。盡管移動邊緣計算應(yīng)用程序的任務(wù)卸載功能能夠提高移動終端設(shè)備端的處理能力和降低這些設(shè)備的能耗，但在一個需要大量密集型計算任務(wù)的系統(tǒng)中，由于無線信道的帶寬有限，設(shè)備間會競爭網(wǎng)絡(luò)資源，并形成相互干擾，導(dǎo)致數(shù)據(jù)傳輸速率降低，延長數(shù)據(jù)傳輸時間。同時，在邊緣云數(shù)據(jù)中心計算資源有限的情況下，把所有的應(yīng)用程序卸載到邊緣云端并不是明智的選擇[9]。隨著移動終端設(shè)備的性能的提高，把一部分移動應(yīng)用程序放在終端處理，另一部分卸載到邊緣云的數(shù)據(jù)中心，可以降低移動設(shè)備間由于網(wǎng)絡(luò)資源競爭導(dǎo)致的數(shù)據(jù)傳輸時間延長以及對邊緣云數(shù)據(jù)中心計算資源的需求。如Yang等[15]開發(fā)了一種混合遺傳爬坡算法，在非正交多址(NOMA)支持的小單元MEC網(wǎng)絡(luò)中分別建立通信模型和計算模型，通過快速找到最優(yōu)解以實現(xiàn)在不同需求下任務(wù)卸載總成本以及計算能力的能量與傳輸時延問題最小化的目標(biāo)。

綜上，目前多數(shù)研究停留在考慮全任務(wù)卸載的問題上，即任務(wù)要么在本地設(shè)備處理，要么在邊緣云處理[9，16-17]。而在進一步的研究中，也僅考慮了采用DVS技術(shù)進行偏分任務(wù)卸載[18]，沒有考慮到計算資源的分配。關(guān)于該方向的研究尚未被充分挖掘，這對大數(shù)據(jù)應(yīng)用程序尤為重要。因此，文章就移動邊緣計算的邊緣云計算資源分配和偏分任務(wù)卸載的問題開展研究，以期為該領(lǐng)域的相關(guān)研究提供參考。

2 MEC系統(tǒng)模型的設(shè)置

MEC系統(tǒng)模型由多個服務(wù)器組成的數(shù)據(jù)中心和N個物聯(lián)網(wǎng)設(shè)備組成，如圖1所示。參考文獻[16，18]，建立MEC系統(tǒng)模型。設(shè)物聯(lián)網(wǎng)設(shè)備i∈{1,2,…,N}的任務(wù)記作i。每個物聯(lián)網(wǎng)設(shè)備有一個延遲敏感(delay-sensitive)和需要大量計算資源的任務(wù)要處理。這些任務(wù)要么放在本地的設(shè)備處理，要么卸載到邊緣云數(shù)據(jù)中心處理。物聯(lián)網(wǎng)設(shè)備可以通過基站(Base Station,簡稱BS)來訪問數(shù)據(jù)中心中的計算資源。F表示邊緣云數(shù)據(jù)中心服務(wù)器的CPU頻率；fi,l表示物聯(lián)網(wǎng)設(shè)備i的CPU頻率；Di表示任務(wù)i的大??；Ci表示完成任務(wù)i所需要的CPU周期數(shù)；λ∈(0，1)，表示任務(wù)i在本地處理所占的比例。

圖1 一個典型的MEC系統(tǒng)

2.1 本地計算模型

在本地計算模型中，移動應(yīng)用程序?qū)⒃谖锫?lián)網(wǎng)的終端設(shè)備處理。fi,l表示設(shè)備i的計算能力，用每秒的CPU周期數(shù)來衡量。因此，物聯(lián)網(wǎng)設(shè)備i處理任務(wù)所需要的時間Ti,l和消耗的能耗Ei,l可以分別表示為 ：

(1)

Ei,l=PiλiCi

(2)

在公式(2)中，Pi表示每一個CPU周期所消耗的能量，可以用如下公式來表示：

(3)

ki是固定的參數(shù)，它的值取決于芯片的結(jié)構(gòu)[19]。

2.2 通信模型

當(dāng)應(yīng)用程序通過無線信道卸載到邊緣云時，上行鏈路傳輸會產(chǎn)生額外的時間和能量。對于物聯(lián)網(wǎng)設(shè)備i來說，上行傳輸?shù)臄?shù)據(jù)率可用如下公式表示:

(4)

在公式(4)中，Bi表示分配給物聯(lián)網(wǎng)設(shè)備i的帶寬，qi表示傳輸功率，hi表示路徑損耗，N0表示噪聲功率。

基于公式(4)，上行傳輸時間可以表示為：

(5)

相應(yīng)的上行消耗的能量為：

(6)

2.3 邊緣云計算模型

當(dāng)任務(wù)到達邊緣云數(shù)據(jù)中心之后，服務(wù)器將分配計算資源來處理這些任務(wù)。對于物聯(lián)網(wǎng)設(shè)備i來說，假設(shè)分配它的計算資源用Fi,e來表示，那么在邊緣云中的處理時間可以表示為：

(7)

根據(jù)公式(5)和(7)，當(dāng)任務(wù)在邊緣云處理時，總的任務(wù)卸載所需要的時間可以表示為

Ti,0=Ti,t+Ti,e

(8)

基于以上模型，在本地處理的計算開銷Zi,l和卸載到邊緣云的計算開銷Zi,0可以分別表示為：

(9)

(10)

相應(yīng)的系統(tǒng)計算開銷Zi可以表示為：

(11)

跟很多研究一樣，忽略了把計算結(jié)果從邊緣云傳輸?shù)轿锫?lián)網(wǎng)設(shè)備的時間，這是由于對于很多應(yīng)用程序來說，如人臉識別應(yīng)用程序，計算結(jié)果的大小通常來說相對于輸入數(shù)據(jù)來說小很多。

3 問題的構(gòu)造和提出的解決算法

3.1 問題的構(gòu)造

我們的目標(biāo)是最小化系統(tǒng)計算開銷，所構(gòu)造的優(yōu)化問題可以表示為：

3.2 提出的解決算法

在提出算法之前，先給出定理1，該定理在文獻[19]中已經(jīng)得到了證明?；谶@個定理，提出解決問題1的算法。

在定理1的公式中，supf～(x,y)=supyf(x,y)。

定理1表明，當(dāng)最小化一個函數(shù)時，可先優(yōu)化其中一些變量，再優(yōu)化剩下的變量?；诙ɡ?，對于給定的λi，可以把問題1分為以下兩個子問題：

子問題1：邊緣云計算開銷的最小化問題；

子問題2：本地計算開銷的最小化問題。

在問題1的基礎(chǔ)上，子問題1可以表達為：

(12)

其中，μ≥0是拉格朗日乘子。

根據(jù)凸優(yōu)化中的KKT條件[19]，得到下面的結(jié)果：

(13)

(14)

μ≥0

通過公式(13)，可以知道μ>0，并且可以得到

(15)

因此，把公式(15)代入到公式(14)，可以得到

(16)

通過公式(16)，可以得到

(17)

公式(15)代公式(17)，可以得到公式(18)

(18)

因此，通過把公式(18)分別代入到公式(8)和(11)，就可以得到在任務(wù)卸載的情況下的計算時間和卸載開銷。

令Ti,l=Ti,0，有

(19)

從而得到:

(20)

基于以上的結(jié)果，提出如下的資源分配和任務(wù)卸載的算法(表2)。

表2 計算資源和任務(wù)卸載的算法

4 仿真實驗

4.1 參數(shù)的設(shè)置

假設(shè)一個MEC系統(tǒng)中有N=5個設(shè)備，對于物聯(lián)網(wǎng)設(shè)備i的參數(shù)設(shè)置(見表3)主要參考文獻[9，16-17]，但這些文獻中，作者只考慮了二分任務(wù)卸載。故本研究側(cè)重于探索部分任務(wù)卸載的情景，這大數(shù)據(jù)應(yīng)用程序更實際。

表3 參數(shù)值的設(shè)置

4.2 實驗結(jié)果

為了驗證所提出算法的有效性，研究將針對本地任務(wù)處理(Local)(在這種情況下，所有的任務(wù)都放在本地的設(shè)備端處理)和邊緣云任務(wù)處理(Edge Cloud)(在這種情況下，所有的任務(wù)都放在邊緣云處理)兩種基準(zhǔn)算法進行比較：

如圖2，物聯(lián)網(wǎng)設(shè)備的任務(wù)由不同帶寬值情況下的選擇決定。1表示物聯(lián)網(wǎng)設(shè)備把任務(wù)卸載到邊緣云，0表示任務(wù)在本地的設(shè)備處理。從圖中可以看出編號為需要計算資源比少的物聯(lián)網(wǎng)設(shè)備，像設(shè)備1和2，在帶寬比較小的情況下會在本地設(shè)備處理任務(wù)。隨著網(wǎng)絡(luò)帶寬的增大，需要大量計算資源的物聯(lián)網(wǎng)設(shè)備會選擇把任務(wù)卸載到邊緣云處理。

圖2 物聯(lián)網(wǎng)設(shè)備的任務(wù)選擇決定

圖3、圖4、圖5分別反映在不同網(wǎng)絡(luò)帶寬值情況下物聯(lián)網(wǎng)設(shè)備的任務(wù)處理時間、能耗和系統(tǒng)代價的變化。其中，系統(tǒng)代價以能耗和任務(wù)處理時間作為衡量標(biāo)準(zhǔn)。如圖3，當(dāng)網(wǎng)絡(luò)帶寬值很小時，就所提出的算法和邊緣處理算法來說，任務(wù)處理時間、能耗和系統(tǒng)代價都比較大。

圖3 任務(wù)處理時間隨著寬帶的變化

圖4顯示在本地處理所需要時間最小情境下，所提出算法能達到最低的能耗，并且邊緣云所消耗的能量逐漸比本地處理所消耗的能耗低。

圖4 任務(wù)處理時間隨著寬帶的變化

隨著網(wǎng)絡(luò)帶寬值的增大，如圖5所示，很明顯地發(fā)現(xiàn)，本地處理的系統(tǒng)代價超過邊緣云處理的系統(tǒng)代價，邊緣云的系統(tǒng)代價越來越小。跟兩個基準(zhǔn)算法相比，所提出的算法能取得比較小的系統(tǒng)代價，從而驗證了所提出的算法的有效性。

圖5 系統(tǒng)代價隨著寬帶的變化

5 結(jié)論和未來的研究工作

在本文中我們研究了移動邊緣計算中的計算資源分配和任務(wù)卸載的問題。由于所建立的問題是MINP，是典型的NP難的問題。針對這種情況，我們提出了一種有效的任務(wù)卸載和計算資源分配的算法。仿真實驗表明，所提出的算法能有效地降低系統(tǒng)的任務(wù)處理延遲和能耗。

在未來的研究工作中，針對所構(gòu)造的問題，我們將研究其他的經(jīng)典算法如，ADMM和Dinkelbach等算法的復(fù)雜性。同時，我們也將采用機器學(xué)習(xí)的算法，如深度強化學(xué)習(xí)來解決MINP的問題。