計算資源受限的移動邊緣計算服務器收益優化策略

黃冬艷，付中衛，王 波*

（1. 深圳大學電子與信息工程學院，廣東深圳518060；2. 認知無線電與信息處理省部共建教育部重點實驗室（桂林電子科技大學），廣西桂林541004）

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

0 引言

隨著物聯網和5G 移動通信技術的發展，在智能手機、傳感器和可穿戴計算設備等移動設備上運行計算密集型和延遲關鍵型應用已經成為趨勢［1-2］。但由于受到自身計算能力和能量的限制，移動設備通常不具備運行這類應用的能力。

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

通過優化任務卸載決策、資源分配或任務執行次序實現MEC 的吞吐量，端到端延遲或能量效率等性能的提升是MEC研究中的熱點。

考慮到頻譜資源受限，為了提高MEC 系統的吞吐量，文獻［5-6］分別提出了相應的接入控制策略、頻譜資源和計算資源聯合優化算法。另一方面，為了降低移動設備的延遲和能耗，有文獻提出通過多用戶博弈［7］、聯合優化子載波和功率的分配［8］等方式實現移動設備延遲最小化，以及結合數據壓縮與頻譜資源分配以降低移動用戶的能耗［9］。

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

文獻［11］提出了一種延遲最小化的計算任務卸載方案，由移動用戶根據MEC 服務器任務緩存區的狀態、本地處理單元的執行狀態和傳輸單元的狀態做出卸載決策。文獻［12-13］則研究了基于定價的分布式計算任務卸載決策，將MEC服務器和移動用戶之間的交互建模為Stackelberg 博弈模型。在該博弈模型中，MEC 服務器依據收益最大化設定服務費。給定服務費后，每個用戶依據延遲最小化［12］或是能耗最小化［13］自主做出卸載決定。此外，文獻［14］通過優化任務執行次序，減小移動用戶和MEC服務器的加權能耗。

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

本文關注于計算資源受限的MEC 服務器收益優化問題。與文獻［12-13］不同，本文研究了存在不同QoS需求的多用戶MEC 系統，提出通過優化任務執行次序提高MEC 服務器的收益。主要貢獻如下:1）將MEC 服務器收益最大化問題建模為以任務執行次序為優化變量的優化問題；2）提出了一種基于分支定界法的排序算法，以獲得收益優化的任務執行次序。

1 系統模型

考慮一個由基站和K個移動用戶組成的多用戶MEC 系統。該系統的每個用戶都有一個計算密集型任務，并請求將任務卸載到MEC 服務器。每個任務都具有嚴格的截止期限。系統模型如圖1所示。

此外，本文采用如下假設:

1）信道狀態信息是已知的；

2）信道狀態在任務卸載期間保持不變；

3）一旦決定將任務卸載到MEC 服務器，移動用戶將不會停止卸載，直到卸載完成。

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

圖1 多用戶MEC 系統Fig. 1 Multi-user MEC system

圖2 MEC系統的任務卸載流程Fig. 2 Task offloading process in MEC system

2 問題建模及優化算法

考慮一個有多個計算密集型任務同時請求卸載的重業務負載場景。首先，將MEC 服務器收益最大化問題建模成以任務執行次序為優化變量的最優化問題；然后，提出了一種基于分支定界法的排序算法來尋找該問題的最優解。

2.1 問題建模

定義 MEC 服務器中一個執行次序為s=(s(1)，s(2)，…，s(k))。 其 中s是1，2，…，K的 一 種 排 列，s(k)∈{1，2，…，K}。舉例說明，當K= 3，s=(2，1，3)，則s(1)=2，表示第2號任務排在次序s的第1個位置。

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

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

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

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

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

3 仿真結果

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

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

如圖3 所示:1）所提算法的平均收益高于其他算法的平均收益。隨著移動用戶數量的增加，所提算法優勢變得更加明顯。給定MEC 服務器的CPU 頻率fc= 10 GHz，當移動用戶數K= 24 時，所提算法的平均收益分別比LTF、LLTF 和FCFS高11%、14%和21%。2）隨著移動用戶數K的增加，每種算法的平均收益均趨于穩定。這是因為在工作負載重的網絡中，fc成為收益增加的瓶頸。

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

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

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

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

4 結語

本文研究了計算資源受限的MEC 服務器收益優化問題。以最大化MEC 服務器收益為優化目標，提出了一種基于分支定界法的算法，以獲得最優的接入策略和任務執行次序。仿真結果表明，在重負載網絡中，該算法能夠有效提高MEC 服務器的平均收益。本文僅討論了每單位CPU 周期的價格固定的情況，未來擬在價格可更改的場景下進一步研究MEC 服務器收益優化問題。