計(jì)算資源受限的移動(dòng)邊緣計(jì)算服務(wù)器收益優(yōu)化策略

黃冬艷，付中衛(wèi)，王 波*

（1. 深圳大學(xué)電子與信息工程學(xué)院，廣東深圳518060；2. 認(rèn)知無線電與信息處理省部共建教育部重點(diǎn)實(shí)驗(yàn)室（桂林電子科技大學(xué)），廣西桂林541004）

（*通信作者電子郵箱glbluewind@126.com）

0 引言

隨著物聯(lián)網(wǎng)和5G 移動(dòng)通信技術(shù)的發(fā)展，在智能手機(jī)、傳感器和可穿戴計(jì)算設(shè)備等移動(dòng)設(shè)備上運(yùn)行計(jì)算密集型和延遲關(guān)鍵型應(yīng)用已經(jīng)成為趨勢(shì)［1-2］。但由于受到自身計(jì)算能力和能量的限制，移動(dòng)設(shè)備通常不具備運(yùn)行這類應(yīng)用的能力。

移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）［3］通過將計(jì)算任務(wù)從移動(dòng)設(shè)備卸載到具有相對(duì)豐富計(jì)算資源的邊緣服務(wù)器上執(zhí)行，實(shí)現(xiàn)了在移動(dòng)設(shè)備上運(yùn)行計(jì)算密集型和延遲關(guān)鍵型應(yīng)用的愿景。與移動(dòng)云計(jì)算不同，MEC 服務(wù)器通常部署在網(wǎng)絡(luò)邊緣（例如，基站和無線局域網(wǎng)接入點(diǎn)），因此可以避免移動(dòng)用戶和遠(yuǎn)程云中心之間的長(zhǎng)距離數(shù)據(jù)傳輸，從而顯著降低延遲和移動(dòng)用戶的能量消耗。因此，MEC是5G網(wǎng)絡(luò)的關(guān)鍵技術(shù)，獲得了業(yè)界的廣泛關(guān)注［4］。

通過優(yōu)化任務(wù)卸載決策、資源分配或任務(wù)執(zhí)行次序?qū)崿F(xiàn)MEC 的吞吐量，端到端延遲或能量效率等性能的提升是MEC研究中的熱點(diǎn)。

考慮到頻譜資源受限，為了提高M(jìn)EC 系統(tǒng)的吞吐量，文獻(xiàn)［5-6］分別提出了相應(yīng)的接入控制策略、頻譜資源和計(jì)算資源聯(lián)合優(yōu)化算法。另一方面，為了降低移動(dòng)設(shè)備的延遲和能耗，有文獻(xiàn)提出通過多用戶博弈［7］、聯(lián)合優(yōu)化子載波和功率的分配［8］等方式實(shí)現(xiàn)移動(dòng)設(shè)備延遲最小化，以及結(jié)合數(shù)據(jù)壓縮與頻譜資源分配以降低移動(dòng)用戶的能耗［9］。

但在文獻(xiàn)［5-9］的分析中均假設(shè)MEC 服務(wù)器具有無限的計(jì)算能力。事實(shí)上，受到部署場(chǎng)地和成本的制約，MEC 服務(wù)器的計(jì)算能力相比大型云計(jì)算中心是有限的。這導(dǎo)致任務(wù)在服務(wù)器的處理時(shí)間以及任務(wù)在MEC 服務(wù)器任務(wù)緩存區(qū)內(nèi)的排隊(duì)延遲不可忽略，特別是在負(fù)載密集的網(wǎng)絡(luò)中。據(jù)研究表明，在5G 場(chǎng)景下，任務(wù)在MEC 服務(wù)器的處理時(shí)間遠(yuǎn)大于其上傳時(shí)間［10］。以圖像識(shí)別為例，對(duì)于569 KB 大小的圖像，在4G網(wǎng)絡(luò)下的傳輸時(shí)間為1.24 s，在5G 網(wǎng)絡(luò)下的傳輸時(shí)間為0.001 s，而在MEC 服務(wù)器處理時(shí)間為1.12 s［10］。可見，在5G網(wǎng)絡(luò)中，MEC 處理時(shí)間比上傳時(shí)間高了3 個(gè)數(shù)量級(jí)。因此，MEC 面臨的挑戰(zhàn)從頻譜資源和計(jì)算資源受限轉(zhuǎn)變?yōu)橛?jì)算資源受限，需要在計(jì)算資源受限的情況下，進(jìn)一步研究MEC 的性能優(yōu)化問題［11-14］。

文獻(xiàn)［11］提出了一種延遲最小化的計(jì)算任務(wù)卸載方案，由移動(dòng)用戶根據(jù)MEC 服務(wù)器任務(wù)緩存區(qū)的狀態(tài)、本地處理單元的執(zhí)行狀態(tài)和傳輸單元的狀態(tài)做出卸載決策。文獻(xiàn)［12-13］則研究了基于定價(jià)的分布式計(jì)算任務(wù)卸載決策，將MEC服務(wù)器和移動(dòng)用戶之間的交互建模為Stackelberg 博弈模型。在該博弈模型中，MEC 服務(wù)器依據(jù)收益最大化設(shè)定服務(wù)費(fèi)。給定服務(wù)費(fèi)后，每個(gè)用戶依據(jù)延遲最小化［12］或是能耗最小化［13］自主做出卸載決定。此外，文獻(xiàn)［14］通過優(yōu)化任務(wù)執(zhí)行次序，減小移動(dòng)用戶和MEC服務(wù)器的加權(quán)能耗。

在重業(yè)務(wù)負(fù)載的場(chǎng)景下，由于計(jì)算能力有限，為保證卸載任務(wù)的QoS（例如，在線游戲、增強(qiáng)現(xiàn)實(shí)（Augmented Reality，AR）、虛擬現(xiàn)實(shí)（Virtual Reality，VR）等延遲敏感型應(yīng)用需要保證延遲需求），MEC 服務(wù)器只能進(jìn)行接入控制，為部分用戶提供計(jì)算服務(wù)。另一方面，為了收回設(shè)備部署和維護(hù)成本并實(shí)現(xiàn)盈利，MEC 服務(wù)器非常關(guān)注如何利用有限的資源最大化自身的收益。因此，為了確保卸載任務(wù)的QoS，同時(shí)最大化自身的收益，服務(wù)器必須合理地確定允許哪些任務(wù)卸載并確定卸載任務(wù)的執(zhí)行次序。

本文關(guān)注于計(jì)算資源受限的MEC 服務(wù)器收益優(yōu)化問題。與文獻(xiàn)［12-13］不同，本文研究了存在不同QoS需求的多用戶MEC 系統(tǒng)，提出通過優(yōu)化任務(wù)執(zhí)行次序提高M(jìn)EC 服務(wù)器的收益。主要貢獻(xiàn)如下:1）將MEC 服務(wù)器收益最大化問題建模為以任務(wù)執(zhí)行次序?yàn)閮?yōu)化變量的優(yōu)化問題；2）提出了一種基于分支定界法的排序算法，以獲得收益優(yōu)化的任務(wù)執(zhí)行次序。

1 系統(tǒng)模型

考慮一個(gè)由基站和K個(gè)移動(dòng)用戶組成的多用戶MEC 系統(tǒng)。該系統(tǒng)的每個(gè)用戶都有一個(gè)計(jì)算密集型任務(wù)，并請(qǐng)求將任務(wù)卸載到MEC 服務(wù)器。每個(gè)任務(wù)都具有嚴(yán)格的截止期限。系統(tǒng)模型如圖1所示。

此外，本文采用如下假設(shè):

1）信道狀態(tài)信息是已知的；

2）信道狀態(tài)在任務(wù)卸載期間保持不變；

3）一旦決定將任務(wù)卸載到MEC 服務(wù)器，移動(dòng)用戶將不會(huì)停止卸載，直到卸載完成。

任務(wù)卸載過程如圖2 所示。 首先，移動(dòng)用戶k(k∈{1，2，…，K})向MEC 服務(wù)器發(fā)送卸載請(qǐng)求消息。卸載請(qǐng)求消息包括客戶端中間件收集的任務(wù)信息。收到一批卸載請(qǐng)求后，MEC 服務(wù)器做出卸載決定并將該決定反饋給用戶。如果MEC服務(wù)器同意卸載，那么用戶將任務(wù)上傳并向MEC服務(wù)器支付相應(yīng)的費(fèi)用；否則，用戶不需要支付費(fèi)用。

圖1 多用戶MEC 系統(tǒng)Fig. 1 Multi-user MEC system

圖2 MEC系統(tǒng)的任務(wù)卸載流程Fig. 2 Task offloading process in MEC system

2 問題建模及優(yōu)化算法

考慮一個(gè)有多個(gè)計(jì)算密集型任務(wù)同時(shí)請(qǐng)求卸載的重業(yè)務(wù)負(fù)載場(chǎng)景。首先，將MEC 服務(wù)器收益最大化問題建模成以任務(wù)執(zhí)行次序?yàn)閮?yōu)化變量的最優(yōu)化問題；然后，提出了一種基于分支定界法的排序算法來尋找該問題的最優(yōu)解。

2.1 問題建模

定義 MEC 服務(wù)器中一個(gè)執(zhí)行次序?yàn)閟=(s(1)，s(2)，…，s(k))。 其 中s是1，2，…，K的 一 種 排 列，s(k)∈{1，2，…，K}。舉例說明，當(dāng)K= 3，s=(2，1，3)，則s(1)=2，表示第2號(hào)任務(wù)排在次序s的第1個(gè)位置。

若將任務(wù)s(k)卸載到MEC 服務(wù)器執(zhí)行，則完成該任務(wù)的所需時(shí)間包括任務(wù)上傳時(shí)間，在MEC 服務(wù)器的隊(duì)列等待時(shí)間，服務(wù)器處理時(shí)間和計(jì)算結(jié)果下載時(shí)間。由于計(jì)算結(jié)果的大小通常遠(yuǎn)小于計(jì)算任務(wù)本身，因此可以合理地認(rèn)為計(jì)算結(jié)果的下載時(shí)間遠(yuǎn)小于任務(wù)上傳時(shí)間。為簡(jiǎn)化分析，在接下的分析中主要關(guān)注總時(shí)間的3 個(gè)主要部分:上傳時(shí)間、隊(duì)列等待時(shí)間和執(zhí)行時(shí)間。

令ls(k)（單位:bit）表示任務(wù)s(k)的大小，Gs(k)（單位:cycle/bit）表示計(jì)算強(qiáng)度，ds(k)（單位:s）表示任務(wù)的截止期限，MEC服務(wù)器的CPU時(shí)鐘頻率為fc（單位:Hz）。

1）任務(wù)上傳時(shí)間tu，s(k)為:

其中rs(k)是傳輸速率。根據(jù)香農(nóng)定理，可知:

其中:Bs(k)為分配給移動(dòng)用戶s(k)的傳輸帶寬，N0為噪聲功率譜密度，hs(k)是介于移動(dòng)用戶s(k)和基站之間的信道增益，ps(k)為傳輸功率。

3 仿真結(jié)果

本章通過仿真驗(yàn)證所提算法的性能。仿真設(shè)定參照5G環(huán)境設(shè)定［10，12］。仿真設(shè)定每個(gè)任務(wù)的大小均勻分布在100～500 Kbit，計(jì)算強(qiáng)度均勻分布在1 000～2 000 cycle/bit，截止期限均勻分布在30～150 ms。此外，可用帶寬B= 20 MHz，信道增益在［-50，-30］dBm 范圍內(nèi)均勻分布，用戶的傳輸功率設(shè)置為200 mW，噪聲功率譜密度為-174 dBm/Hz，MEC 服務(wù)器單位收益為每CPU周期1×10-8元。

首先比較了本文算法（Proposed algorithm）、低延遲任務(wù)優(yōu)先（Low-Latency Task First，LLTF）算法、大任務(wù)優(yōu)先（Large Task First，LTF）算法和先到先服務(wù)（First Come First Served，F(xiàn)CFS）算法的平均收益。具體而言，LLTF 算法和LTF 算法分別優(yōu)先考慮具有更高延遲要求和更高計(jì)算資源要求的任務(wù)，F(xiàn)CFS 算法則優(yōu)先考慮上傳時(shí)間最小的任務(wù)。在相同的仿真參數(shù)下，獨(dú)立運(yùn)行所提算法與對(duì)比算法各10 000 次并記錄每種算法的平均收益。然后，將所提算法的平均收益與對(duì)比算法的平均收益進(jìn)行比較。

如圖3 所示:1）所提算法的平均收益高于其他算法的平均收益。隨著移動(dòng)用戶數(shù)量的增加，所提算法優(yōu)勢(shì)變得更加明顯。給定MEC 服務(wù)器的CPU 頻率fc= 10 GHz，當(dāng)移動(dòng)用戶數(shù)K= 24 時(shí)，所提算法的平均收益分別比LTF、LLTF 和FCFS高11%、14%和21%。2）隨著移動(dòng)用戶數(shù)K的增加，每種算法的平均收益均趨于穩(wěn)定。這是因?yàn)樵诠ぷ髫?fù)載重的網(wǎng)絡(luò)中，fc成為收益增加的瓶頸。

圖3 不同算法的MEC服務(wù)器平均收益Fig. 3 Average revenue of MEC server in different algorithms

本文還比較了不同算法的任務(wù)完成率，即MEC 服務(wù)器能夠接受的任務(wù)數(shù)占任務(wù)總數(shù)的百分比。任務(wù)完成率體現(xiàn)了MEC 服務(wù)器容納用戶的能力。任務(wù)完成率越高意味著可以滿足更多用戶的需求。如圖4 所示，當(dāng)用戶數(shù)較少時(shí)，所提算法的平均任務(wù)完成率高于LTF 和FCFS，并且該算法的平均任務(wù)完成率接近LLTF。隨著用戶數(shù)量的增加，當(dāng)fc= 20 GHz，K= 24 時(shí)，所提算法的平均完成率低于LLTF 約4%，比FCFS低約3%，高于LTF。采用所提算法可以完成近32%的任務(wù)，但采用LTF僅完成18%的任務(wù)。

從圖3 和圖4 中，還可觀察到:1）隨著用戶數(shù)量的增加，LLTF 和FCFS 具有較高的完成率但是這兩種算法的平均收益均低于所提算法。這意味著收益并不完全等價(jià)于已完成任務(wù)的數(shù)量。2）所提算法的平均收益高于其他對(duì)比算法；同時(shí)，該算法的任務(wù)平均完成率略低于LLTF 與FCFS。因此，所提算法在優(yōu)化收益同時(shí)也很好地兼顧容納用戶的能力。

圖4 不同算法的平均任務(wù)完成率Fig. 4 Average task completion rate of different algorithms

4 結(jié)語

本文研究了計(jì)算資源受限的MEC 服務(wù)器收益優(yōu)化問題。以最大化MEC 服務(wù)器收益為優(yōu)化目標(biāo)，提出了一種基于分支定界法的算法，以獲得最優(yōu)的接入策略和任務(wù)執(zhí)行次序。仿真結(jié)果表明，在重負(fù)載網(wǎng)絡(luò)中，該算法能夠有效提高M(jìn)EC 服務(wù)器的平均收益。本文僅討論了每單位CPU 周期的價(jià)格固定的情況，未來擬在價(jià)格可更改的場(chǎng)景下進(jìn)一步研究MEC 服務(wù)器收益優(yōu)化問題。