MEC多服務(wù)器啟發(fā)式聯(lián)合任務(wù)卸載和資源分配策略

路 亞

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

0 引 言

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

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

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

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

1 移動(dòng)邊緣計(jì)算

國(guó)際標(biāo)準(zhǔn)組織ETSI提出的移動(dòng)邊緣計(jì)算(MEC)是基于5G 演進(jìn)架構(gòu)的一項(xiàng)新技術(shù)，為減少網(wǎng)絡(luò)延遲，確保高效的網(wǎng)絡(luò)運(yùn)營(yíng)和服務(wù)交付，并提高用戶體驗(yàn)，通過(guò)借助邊緣計(jì)算中心在無(wú)線接入網(wǎng)(Radio Access Network,RAN)內(nèi)提供IT服務(wù)環(huán)境、云計(jì)算和存儲(chǔ)功能。

1.1 MEC基本架構(gòu)

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

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

1.2 MEC部署方案

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

表1 邊緣服務(wù)器部署方案對(duì)比

圖2 FMC部署方案示意圖

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

圖3 5G MEC融合架構(gòu)示意圖

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

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

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

2.1 多服務(wù)器MEC建模

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

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

2.1.1本地計(jì)算任務(wù)

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

(1)

2.1.2任務(wù)上載

(2)

(3)

(4)

(5)

2.1.3MEC計(jì)算資源

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

(6)

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

(7)

2.1.4用戶卸載實(shí)用程序

(8)

(9)

(10)

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

2.2.1JTORA問(wèn)題及分解

(11)

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

(12)

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

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

(13)

(14)

s.t. 00

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

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

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

(15)

(16)

(17)

s.t. 00

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

上行鏈路功率分配問(wèn)題可以表示為：

(18)

s.t. 0

假設(shè)每個(gè)BS獨(dú)立計(jì)算其上行鏈路功率分配，那么

(19)

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

(20)

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

(21)

s.t. 0

計(jì)算資源分配問(wèn)題可以表示為：

(22)

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

(23)

(24)

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

(25)

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

算法1刪除和交換操作

3.forw∈S,i∈Ndo

5.end for

6.forv∈Udo

8.end for

算法2啟發(fā)式任務(wù)卸載調(diào)度

6. 返回第4步

9. 返回第4步

10.end if

3 實(shí) 驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

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

L=140.7+36.7lgd[km]

(26)

式中：對(duì)數(shù)正常陰影衰落的標(biāo)準(zhǔn)偏差為8 dB。

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

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

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

(a)同構(gòu)服務(wù)器 (b)異構(gòu)服務(wù)器

(a)同構(gòu)服務(wù)器 (b)異構(gòu)服務(wù)器

4 結(jié) 語(yǔ)

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