基于邊緣云和移動輔助設備的計算卸載優化方案

方加娟 李 凱

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

0 引 言

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

移動邊緣計算[3]是指將移動網絡與互聯網有效地結合，利用在移動網絡邊緣部署的計算、存儲和處理功能，為用戶提供高帶寬和超低時延的網絡服務解決方案。計算卸載[4]作為 MEC 架構中的一項關鍵技術，是指終端設備將部分或全部計算任務交給云計算環境處理的技術。基于MEC的計算卸載技術可以提高移動設備的性能，通過節省移動設備的能耗來延長設備的工作時間。

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

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

1 移動邊緣計算

MEC是由歐洲電信標準協會ETSI提出的基于5G 演進架構的一項新技術。移動邊緣計算借助邊緣計算中心在無線接入網(RAN)內提供IT服務環境、云計算和存儲功能，其目標是減少網絡延遲，確保高效的網絡運營和服務交付，并提高用戶體驗。

1.1 MEC基本架構

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

圖1 MEC架構示意圖

1.2 MEC計算卸載技術

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

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

2 計算卸載方案

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

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

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

2.1 通信模型

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

(1)

(2)

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

(3)

2.2 計算模型：云-HUE卸載

(4)

(5)

(6)

(7)

(8)

(9)

本文忽略了發送計算結果所花費的時間，因為相對于輸入數據，輸出數據的大小往往很小。

2.3 計算模型：僅云卸載

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

(10)

3 資源分配和解決方案

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

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

(11)

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

(12)

由于αi,j<1，所以

(13)

3.1 HUE固定分配

假定HUE到CUE的分配是固定的，并且優化擴展到任務共享以卸載和用戶之間的云資源分區。

3.1.1最佳解決方案

對于給定的HUE分配δ，式(12)可以變為：

(14)

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

(15)

可以獲得：

(16)

Tk≤Vk∈ρδ

(17)

本文應用迭代技術來最優求解式(16)，對于迭代t，使用式(17)和式(18)將其中的第一約束轉換為單項式：

(18)

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

(19)

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

(20)

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

(21)

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

(22)

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

式(20)k∈ρδ

當|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次優云資源分配

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

(23)

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

3.2 云資源固定分配

(24)

和

(25)

(26)

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

(27)

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

(28)

3.3 HUE最佳分配

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

(29)

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

(30)

(31)

(32)

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

(33)

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

4 實驗結果與分析

表1 模擬參數

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

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

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

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

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

圖4-圖5為不同策略的完成時間對比，其中云的計算能力在4～20 GHz之間變化，圖4中有30個CUE和50個HUE存在網絡中，圖5則將網絡中的CUE和HUE的數量分別增加到70和100。可以發現，卸載到云和HUE的具有極大的優勢，即便HUE是隨機分配的。算法1對計算結果的提升度很小，簡單的“HUE-云BM”方案即可達到理想的結果。

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

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

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

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

5 結 語

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