移動邊緣計算中一種有效的計算資源分配和>偏分任務卸載算法

李昌群，陳國龍

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

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

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

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

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

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

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

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

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

1 移動邊緣計算的相關研究

目前關于移動邊緣計算的相關研究主要涉及任務卸載和資源分配的兩個領域，研究工作的主要目標可以分為如下3種：

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

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

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

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

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

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

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

2.1 本地計算模型

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

(1)

Ei,l=PiλiCi

(2)

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

(3)

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

2.2 通信模型

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

(4)

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

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

(5)

相應的上行消耗的能量為：

(6)

2.3 邊緣云計算模型

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

(7)

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

Ti,0=Ti,t+Ti,e

(8)

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

(9)

(10)

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

(11)

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

3 問題的構造和提出的解決算法

3.1 問題的構造

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

3.2 提出的解決算法

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

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

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

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

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

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

(12)

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

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

(13)

(14)

μ≥0

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

(15)

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

(16)

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

(17)

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

(18)

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

令Ti,l=Ti,0，有

(19)

從而得到:

(20)

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

表2 計算資源和任務卸載的算法

4 仿真實驗

4.1 參數(shù)的設置

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

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

4.2 實驗結果

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

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

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

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

圖3 任務處理時間隨著寬帶的變化

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

圖4 任務處理時間隨著寬帶的變化

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

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

5 結論和未來的研究工作

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

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