路 亞

(重慶電子工程職業(yè)學院人工智能與大數(shù)據(jù)學院 重慶 401331)

0 引 言

隨著移動應用程序和物聯(lián)網(wǎng)的快速增長，對云基礎設施和無線接入網(wǎng)絡(如超低延遲、用戶體驗連續(xù)性和高可靠性)的要求也越來越高[1]。為了將電信、IT和云計算結合起來，直接從網(wǎng)絡邊緣提供云服務，移動邊緣計算概念應運而生[2]。與傳統(tǒng)云計算系統(tǒng)不同，MEC服務器為網(wǎng)絡運營商所有，并直接在蜂窩基站或本地無線接入點通過通用計算平臺實施，這使得MEC可以在靠近最終用戶的地方執(zhí)行應用程序，從而大大減少端到端的延遲，減輕回程網(wǎng)絡的負擔[3-4]。

由于MEC的出現(xiàn)，資源受限的移動設備可以將計算任務卸載到MEC服務器上，從而使其支持各種新的服務和應用，如增強現(xiàn)實、物聯(lián)網(wǎng)、自動駕駛和圖像處理[5]。由于設備與MEC服務器之間在上行鏈路無線信道中的通信需要，任務卸載在延遲和能耗方面會產(chǎn)生額外的開銷。此外，在一個擁有大量卸載用戶的系統(tǒng)中，MEC服務器上有限的計算資源嚴重影響了任務執(zhí)行延遲。因此，卸載決策和執(zhí)行資源分配成為實現(xiàn)高效計算卸載的關鍵問題[6]。

文獻[7]提出一種完全卸載優(yōu)化算法，采用將邊緣設備中的任務全部卸載到MEC服務器上的策略，減少了任務執(zhí)行的時間和能耗。文獻[8]提出一種部分卸載優(yōu)化算法，采取將部分滿足條件的計算任務卸載到云服務器，剩余任務在邊緣設備執(zhí)行的方式實現(xiàn)能耗和時間的優(yōu)化。文獻[9]雖然考慮了多用戶系統(tǒng)中的聯(lián)合任務卸載和資源優(yōu)化問題，但是這種方法只能應用在具有單個MEC服務器的系統(tǒng)上。文獻[10]在移動邊緣計算環(huán)境中提出一種多重資源計算卸載能耗優(yōu)化模型，在計算卸載時綜合考慮邊緣設備、邊緣服務器與云數(shù)據(jù)中心的負載情況，利用粒子群任務調度算法，降低移動終端能耗。文獻[11]提出建立一個設備(D2D)框架，其中網(wǎng)絡邊緣的大量設備利用網(wǎng)絡輔助D2D協(xié)作進行計算和通信資源共享，但是只考慮了任務分配問題。

與上述方法不同，本文在多MEC服務器輔助網(wǎng)絡中設計一個整體的解決方案，對聯(lián)合任務卸載和資源分配進行優(yōu)化，從而最大限度地提高用戶的卸載收益。首先把每個用戶的卸載效用建模為任務完成時間和設備能耗改進的加權和；然后將聯(lián)合任務卸載和資源分配(Joint Task Offloading and Resource Allocation，JTORA)問題作為一個混合整數(shù)非線性規(guī)劃(Mixed Integer Non-linear Program，MINLP)，采用Tammer分解方法將高復雜度的原始問題轉化為等效的主問題和一組復雜度較低的子問題；最后利用本文提出的低復雜度啟發(fā)式算法，以次優(yōu)解的方式解決JTORA問題，實現(xiàn)共同優(yōu)化任務卸載決策和用戶上行鏈路傳輸功率的目標。

1 移動邊緣計算

國際標準組織ETSI提出的移動邊緣計算(MEC)是基于5G 演進架構的一項新技術，為減少網(wǎng)絡延遲，確保高效的網(wǎng)絡運營和服務交付，并提高用戶體驗，通過借助邊緣計算中心在無線接入網(wǎng)(Radio Access Network,RAN)內提供IT服務環(huán)境、云計算和存儲功能。

1.1 MEC基本架構

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

圖1 MEC架構示意圖

1.2 MEC部署方案

由于具備計算和存儲功能的MEC服務器為邊緣計算提供服務，因此MEC服務器在網(wǎng)絡中的部署位置是至關重要的。4G網(wǎng)絡中邊緣服務器部署存在多種方案：小基站云(Small Cell Cloud，SCC)部署方案、移動微型云(Mobile Micro Cloud，MMC)部署方案、快速移動私人云(Fast Move Personal Cloud，F(xiàn)MPC)部署方案和漫游云(Follow Me Cloud，F(xiàn)MC)部署方案。各個部署方案的優(yōu)缺點對比如表1所示。MEC服務器部署方案的選擇是根據(jù)物理部署約束、可擴展性以及性能指標的綜合考慮。圖2給出了FMC部署方案示意圖，該方案主要是通過在分布式的數(shù)據(jù)中心位置部署服務器來提供邊緣服務。

表1 邊緣服務器部署方案對比

圖2 FMC部署方案示意圖

5G網(wǎng)絡在根本架構上不同于4G網(wǎng)絡，所以為了讓MEC更好地融合5G網(wǎng)絡，需要根據(jù)需求重新設計MEC部署方案，如圖3所示。MEC處在接入網(wǎng)與核心網(wǎng)融合的部分，通過NEF接入5G 網(wǎng)絡。該方案根據(jù)平臺應用相關信息，通過5G控制面的應用功能(AF)直接或者間接地將MEC用戶面應用傳遞給策略控制功能模塊(PCF)，控制會話管理功能模塊(SMF)進而影響用戶面功能模塊(UPF)的選擇。

圖3 5G MEC融合架構示意圖

2 多服務器MEC系統(tǒng)的JTORA建模及啟發(fā)式整體優(yōu)化方案

多服務器MEC系統(tǒng)是指在每個基站都配備一個MEC服務器，為資源受限的移動用戶(如智能手機、平板電腦和可穿戴設備)提供計算卸載服務的平臺。每個MEC服務器可以是物理服務器，或者是網(wǎng)絡運營商提供的具有中等計算能力的虛擬機，通過相應的BS提供的無線通道與移動設備連接通信。每個移動用戶都可以通過附近的BS將計算任務卸載到MEC服務器。

本文主要有兩點創(chuàng)新。一是將聯(lián)合任務卸載和資源分配問題表述為一個混合整數(shù)非線性規(guī)劃問題，通過對任務卸載決策、用戶上行鏈路傳輸功率和計算資源分配的共同優(yōu)化來實現(xiàn)卸載效用的最大化；二是提出一種低復雜度啟發(fā)式算法來解決任務卸載最優(yōu)值問題，可以在多項式時間內達到次優(yōu)解。

2.1 多服務器MEC建模

本文將移動系統(tǒng)中的一組用戶和MEC服務器分別表示為u={1,2,…,U}和s={1,2,…,S}。多服務器MEC系統(tǒng)如圖4所示。

圖4 多服務器MEC系統(tǒng)

2.1.1本地計算任務

假設單個用戶u∈U每次只有一個計算任務，即Tu，它是原子的、不可分的。每個Tu由兩個參數(shù)du、cu組成，其中：du表示將程序執(zhí)行(包括系統(tǒng)設置、程序代碼和輸入?yún)?shù)等)從本地設備傳輸?shù)組EC服務器所需的請求數(shù)據(jù)量；cu表示完成任務的計算量。每個任務可以在用戶設備上執(zhí)行本地卸載，或者卸載到MEC服務器。如果將計算任務卸載到MEC服務器，移動用戶能夠節(jié)省執(zhí)行任務的能量，但是將任務請求發(fā)送到上行鏈路需要消耗額外的時間和能量。

(1)

2.1.2任務上載

(2)

(3)

(4)

(5)

2.1.3MEC計算資源

每個BS上的MEC服務器能夠同時向多個用戶提供計算卸載服務。每個MEC服務器提供給關聯(lián)用戶共享的計算資源由計算速率fs進行量化。服務器從用戶接收到卸載的任務后，代表用戶執(zhí)行該任務，完成后返回輸出結果給用戶。將計算資源分配策略定義為F={fu,s|u∈U,s∈S}，其中fu,s>0是BS分配給卸載任務Tu的計算資源量。因此，當?u?Us時，fu,s=0。此外，一個可行的計算資源分配策略必須滿足計算資源約束，表示為：

(6)

給定計算資源分配{fu,s,s∈S}，任務Tu在MEC服務器上的執(zhí)行時間為:

(7)

2.1.4用戶卸載實用程序

(8)

(9)

(10)

2.2 聯(lián)合任務卸載與資源分配啟發(fā)式整體優(yōu)化方案

2.2.1JTORA問題及分解

(11)

式中：λu是權重系數(shù)，可以根據(jù)用戶類型和計算任務的關鍵性來設置。將聯(lián)合任務卸載和資源分配問題轉化成系統(tǒng)效用最大化問題，即：

(12)

式中：第一和第二約束條件表示每個任務可以在本地執(zhí)行或者卸載到子帶j上的至多一個服務器；第三約束條件表示每個BS在子帶j上至多服務一個用戶；第四約束條件表示用戶的傳輸功率預算；最后兩個約束條件表示每個MEC服務器必須為與其相關聯(lián)的每個用戶分配相應的計算資源，并且分配給所有相關用戶的總計算資源不得超過服務器的計算能力。

式(12)中的JTORA問題屬于混合整數(shù)非線性規(guī)劃問題?？紤]到問題中的變量與用戶數(shù)量、MEC服務器數(shù)量和子帶數(shù)量呈線性關系，因此，本文通過設計一個低復雜度、次優(yōu)解決方案，實現(xiàn)聯(lián)合任務卸載與資源分配的優(yōu)化。

(13)

(14)

s.t. 00

式(13)中的問題等同于TO問題；式(14)中的問題等同于RA優(yōu)化問題。

2.2.2JTORA啟發(fā)式解決方案

聯(lián)合任務卸載和資源分配的求解問題等效為分別求解任務卸載和資源分配的優(yōu)化問題，首先解決式(14)中的RA問題，然后使用其解決方案來推導式(13)中TO問題的解決方案。

(15)

(16)

(17)

s.t. 00

由于功率分配pu和計算資源分配fu,s的目標和約束可以彼此分配，因此式(17)可以分解為兩個獨立的問題：上行鏈路功率分配(UPA)和計算資源分配(CRA)。

上行鏈路功率分配問題可以表示為：

(18)

s.t. 0

假設每個BS獨立計算其上行鏈路功率分配，那么

(19)

進而得到了用戶u上傳到子帶j上BS的上行鏈路信噪比的近似值：

(20)

通過式(20)可以將式(18)中目標函數(shù)和對應的用戶發(fā)射功率約束條件實現(xiàn)分離，因此，式(18)中的目標函數(shù)可以近似為：

(21)

s.t. 0

計算資源分配問題可以表示為：

(22)

由于目標函數(shù)的Hessian矩陣是正定的，而且約束條件是凸的，因此，式(22)問題是一個凸優(yōu)化問題，可以采用Karush-Kuhn-Tucker進行求解。

(23)

(24)

根據(jù)式(23)、式(24)，式(13)中的TO問題可以改寫為：

(25)

考慮到TO問題的組合性質，在多項式時間內求解最優(yōu)解是一個非常具有挑戰(zhàn)性的問題。解決式(25)的一個簡單方法是對所有可能的任務卸載決策使用窮舉搜索法。然而，由于候選任務卸載決策的總數(shù)是2n，n=S×U×N，因此窮舉搜索方法顯然是不切實際的。

算法1刪除和交換操作

3.forw∈S,i∈Ndo

5.end for

6.forv∈Udo

8.end for

算法2啟發(fā)式任務卸載調度

6. 返回第4步

9. 返回第4步

10.end if

3 實 驗

3.1 實驗設置

為了評估提出的啟發(fā)式聯(lián)合任務卸載調度和資源分配策略(hJTORA)的性能，本文通過仿真實驗進行測試。所有實驗均在配置為CPU Intel Core i7-4700MQ-2.4 GHz@6 GB RAM的機器上執(zhí)行，通過MATLAB R2017B進行仿真。考慮一個由多個六角形子區(qū)構成的蜂窩網(wǎng)絡系統(tǒng)，每個小區(qū)的中心都配有一個BS，相鄰基站相距1 km。假設用戶和BS分別使用單個天線進行上行鏈路傳輸和接收。本文的測試中用戶的最大發(fā)射功率為Pu=20 dBm，系統(tǒng)帶寬設置為B=20 MHz，背景噪聲方差假設為σ2=-100 dBm。上行鏈路信道增益是使用距離相關的路徑損耗模型生成的，該模型的計算公式為：

L=140.7+36.7lgd[km]

(26)

式中：對數(shù)正常陰影衰落的標準偏差為8 dB。

為了驗證提出算法的優(yōu)越性，本文將與其他優(yōu)秀算法如窮舉搜索法、GOJRA(Greedy Offloading and Joint Resource Allocation)、IOJRA(Independent Offloading and Joint Resource Allocation)和DORA(Distributed Offloading and Resource Allocation)等進行對比。

3.2 實驗結果分析

3.2.1不同算法平均系統(tǒng)效能對比

首先，將本文算法的結果與窮舉法得到的最優(yōu)解以及其他三種算法進行了比較。由于窮舉法搜索所有可能的卸載調度決策，因此對于大量變量，它的運行時間非常長。因此，測試時選擇在一個小的網(wǎng)絡：設置用戶數(shù)U=6，單元數(shù)S=7，每個單元有N=2個子帶。分別設置cu=1 000、1 500和2 000兆周期時，隨機生成500個陰影衰落，得到不同算法95%置信區(qū)間的平均系統(tǒng)效能結果如圖5所示?？梢钥闯?，hJTORA算法與最優(yōu)窮舉算法的性能非常接近，但明顯優(yōu)于其他算法，充分體現(xiàn)算法2得到的hJTORA解的次優(yōu)性。同時，還可以發(fā)現(xiàn)，所有方案的性能都隨著任務工作量的增加而提高。在所有情況下，hJTORA的平均系統(tǒng)效能都在窮盡算法的0.6%以內，而與DORA、GOJRA和IOJRA方案相比，其平均增益分別為33%、43%和96%。

圖5 不同算法的平均系統(tǒng)效能比較

3.2.2用戶數(shù)量對平均系統(tǒng)效能的影響

圖6給出了不同數(shù)量的用戶在卸載任務時的平均系統(tǒng)效能。測試中每個單元的用戶數(shù)從1到10不等，并在三個具有不同任務工作負載的場景中進行比較。而且子帶數(shù)N等于每個單元的用戶數(shù)，因此當系統(tǒng)中有更多的用戶時，為每個用戶分配的帶寬會減少。可以看出，hJTORA算法性能表現(xiàn)最好，而且當任務的工作量增加時，方案的性能也會顯著提高。當用戶數(shù)量較少時，系統(tǒng)效能隨著用戶數(shù)量的增加而增加；但是，當用戶數(shù)量超過某些閾值時，系統(tǒng)效能開始降低。這是由于過多用戶為卸載任務而競爭無線和計算資源，使得MEC服務器上發(fā)送任務和執(zhí)行任務的開銷升高，導致卸載效能降低。

(a)cu=1 000兆周期 (b)cu=1 500兆周期

3.2.3任務配置文件對平均系統(tǒng)效能的影響

本文中的任務配置文件是指請求數(shù)據(jù)量和工作負載兩個方面。根據(jù)請求數(shù)據(jù)量du和工作負載cu來評估系統(tǒng)效能?？紤]兩種MEC服務器的配置：(1)同構服務器—所有服務器的CPU速度是20 GHz；(2)異構服務器—服務器的CPU速度隨機從{10,20,30}GHz中選擇。四個算法在不同cu、du值時的平均系統(tǒng)效能如圖7、圖8所示?？梢钥闯?，所有方案的平均系統(tǒng)效能都隨任務工作量的增加而增加，隨任務請求的增加而減少。這表示，與那些具有大請求量和低工作負載的任務相比，具有小請求量和高工作負載的任務從卸載中獲益更多。同構服務器設置中所有方案的性能與異類服務器設置中所有方案的性能之間的差異是微乎其微的。除此之外，在所有方案中，hJTORA方案的性能是最優(yōu)的。

(a)同構服務器 (b)異構服務器

(a)同構服務器 (b)異構服務器

4 結 語

本文目標是在多MEC服務器輔助網(wǎng)絡中設計一個整體的解決方案，對聯(lián)合任務卸載和資源分配進行優(yōu)化，從而最大限度地提高用戶的卸載收益。首先，為每個用戶的卸載效用建模，將JTORA問題轉化為MINLP問題。然后，采用Tammer分解方法將高復雜度的原始問題轉化為等效的主問題和一組復雜度較低的子問題。最后，利用本文提出的低復雜度啟發(fā)式算法，以次優(yōu)解的方式解決JTORA問題，實現(xiàn)共同優(yōu)化任務卸載決策、用戶上行鏈路傳輸功率的目標。仿真結果表明，本文提出的優(yōu)化策略的平均系統(tǒng)效能明顯優(yōu)于其他方案，提出的啟發(fā)式算法能夠很好地實現(xiàn)最優(yōu)解，顯著提高系統(tǒng)的平均卸載效率。