移動邊緣計算時延與能耗聯合優化方法

張先超，任天時，趙 耀，樊 銳

(1. 東南大學移動通信國家重點實驗室 南京 210096；2. 嘉興學院浙江省醫學電子與數字健康重點實驗室 浙江 嘉興 314001；3. 北京理工大學信息與電子學院 北京 海淀區 100081；4. 中國電子科學研究院 北京 石景山區 100041)

移動互聯網的廣泛應用，使得用戶對數據速率和服務質量(quality of service, QoS)的需求呈指數增長。盡管移動終端設備的中央處理器性能不斷提升，但仍無法應對處理任務的急劇增長，移動終端設備計算能力仍顯不足。并且，移動終端設備的計算需要大量能耗，降低了設備的續航時間。這些問題推動了移動云計算概念的出現和發展[1]。

近年來物聯網技術的發展與普及，導致移動云計算的缺點逐漸暴露。首先，云計算無法滿足新興應用場景對更低網絡時延的需求[2]；其次，接入設備數量的急劇增加將導致網絡數據傳輸量呈爆炸性增長趨勢，采用云計算匯聚的網絡流量會使核心網不堪重負[3]。為此，歐洲電信標準化協會(European telecommunications standards institute, ETSI)于2014 年提出了移動邊緣計算(mobile edge computing,MEC)的概念，給出定義[4]：在無線接入網(radio access network, RAN)內和靠近移動用戶的移動網絡邊緣，MEC 能夠提供IT 服務環境和云計算的能力。2017 年，ETSI 將MEC 的概念延伸至Wi-Fi、車聯網等接入網絡，并將其更名為多接入邊緣計算(multi-access edge computing)，簡寫仍為MEC[5]。

移動邊緣計算由移動邊緣服務器、基站、終端用戶、核心網、云等構成，其中，移動邊緣服務器部署在基站附近，為該基站小區內的用戶提供計算資源。通過直接向移動邊緣服務器尋求服務，用戶可以享受低時延、高能效的體驗。當移動邊緣服務器的計算能力不足以支撐用戶需求時，位于核心網的云計算(mobile cloud computing, MCC)才會進一步服務于用戶的計算[6-7]。相比于MCC，MEC 有更低的時延、更低的移動設備能耗[8]，更好的上下文感知能力[9-11]和更強的隱私性與安全性[12]。MEC 技術能夠有效應用的關鍵是計算任務在邊緣服務器與終端之間有效分配[13]。計算任務分配就是將任務分配給合適的任務處理設備，包括本地處理器、臨近的IoT 設備處理器、MEC 服務器、云服務器等，同時，明確應用中任務的依賴關系，給出任務處理的先后順序。

5G 的商用投入和6G 高速發展增強了醫療急救、災害救援等應急場景的處置能力。這些應急場景對現場信息處理有更高的要求。然而，用戶端的計算能力通常難以滿足，如移動急救車輛上的計算能力無法滿足車輛上信息處理的需要，采用邊緣計算是事宜的解決方案。

在應急情景下，單個小區中需要對多達數十個用戶的計算任務進行合理有效的分配，以滿足其低時延、低能耗的應用需求。文獻[14]研究了帶有能量收集設備的綠色MEC 系統，并給出了基于李亞普諾夫優化的動態計算任務分配策略，以最小化執行延遲和任務失敗概率為目標，能夠接近最優來解決任務分配問題。文獻[15]將最優分配表征為在計算延遲約束下，最小化加權能耗和的凸優化問題，證明了對于分配優先級函數，最優策略具有閾值特征，優先級高于和低于給定閾值的用戶將分別執行完整分配和最小值分配。文獻[16]采用了博弈論的方法來實現有效的分布式計算任務分配，將移動設備用戶之間的分布式計算卸載決策問題表述為一個多用戶計算卸載博弈，設計了一種可以實現納什均衡的分布式計算任務分配算法。文獻[17]設計了一種移動邊緣環境下對多用戶時延與移動邊緣計算服務器資源分配均衡性進行聯合優化的計算卸載方法，構造了聯合優化平均卸載時延與資源分配均衡度的目標函數，從而有效地減小多用戶的平均卸載時延，同時平衡各移動邊緣計算服務器的工作負荷。

本文針對5G 場景下超可靠低時延通信(ultrareliable and low-latency communications, uRLLC)典型應用場景中單小區多用戶的移動邊緣計算問題，研究在邊緣服務器與移動用戶終端之間進行計算任務分配，實現時延和能耗聯合優化。

1 問題描述

設有一個包含gNB 節點和N個終端用戶設備的無線接入網絡，gNB 節點上部署著MEC 服務器和MEC 任務管理器，如圖1 所示。gNB 節點可以控制通信流量，MEC 服務器負責對計算任務的處理，MEC 任務管理器模塊與MEC 服務器在相同位置部署，負責MEC 系統中計算任務分配等。用Z={0,1,···n,···,N}表 示N個終端用戶設備。每個終端用戶設備都要完成大量計算任務，任務不能被分割，全部在終端CPU 處理，或全部通過無線信道將任務分配到MEC 服務器處理。MEC 任務管理器獲取終端用戶的狀態、需要分配的任務以及MEC 服務器的可用資源，通過考慮能耗與時延等要求，確定所有終端用戶的任務分配策略，并將任務分配策略反饋給終端用戶設備和基站。

圖1 多用戶移動邊緣計算系統構成

通過求解Z，使得該MEC 系統的Call最小。

2 聯合優化模型

若任務An選擇在用戶終端處理，終端設備的計算時延與能耗為：

若任務An分配至MEC 服務器進行處理，需要將任務An從用戶終端傳輸到MEC 服務器進行處理，處理結果由MEC 服務器傳輸回本地。

由于處理結果傳回用戶設備的數據量通常較小，且MEC 服務器的傳輸功率很大，因此可以忽略處理結果由MEC 服務器傳輸回本地的時延，則任務An由用戶終端傳輸至MEC服務器與在MEC 服務器處理的時延以及移動設備能耗分別為：

式中，Rul是數據從用戶終端傳輸至MEC 服務器的速率；fs表示為該用戶分配的虛擬CPU 頻率(以CPU 周期/s 為單位)；Pul指移動設備傳輸數據的功率；Pi指移動設備空閑時的功率。

考慮只有一個移動基站的系統，忽略其他小區的通信干擾，那么，用戶設備的上傳數據速率為：

式中，W是無線信道的帶寬；Pn是無線信道中第n個 用戶設備的傳輸功率；hn是 無線信道中第n個用戶設備的信道增益；N0為噪聲功率。

同樣，用時延和能耗的加權和，表征任務分配至MEC 服務器處理所需代價：

式(9a)是優化的目標，使得終端用戶的時延和能耗的代價和最小；式(9b)是終端用戶時延約束；式(9c)是終端用戶的功率約束；式(9d)中αn是求解變量，表示任務An在終端用戶或在MEC 服務器處理。

3 分支定界算法

分支定界算法是求解整數規劃問題的常用算法，分支把區域逐次分割成越來越多的小區域，定界在這些小區域內，確定目標函數的上界和下界[20]。

針對模型式(9)，設計如下分支定界算法。

算法1：時延與能耗聯合優化分支定界算法

1) 初始化全局參數，全局上界U=∞，全局下界L=?∞， 全局最優值C?←?, 問題最優解Z?←?，初始化松弛線性規劃問題隊列Q

2) 初始化N個用戶的參數，計算用戶本地計算時延Tnl， 本地計算能耗Enl，MEC 服務器計算時延Tno，MEC 服務器計算能耗Eno

3) 計算初始整數規劃問題求解所需參數

4) 取第一個用戶的任務分配決策α1=0和 α1=1，分作兩個問題

5) 將兩個問題分別松弛求解，得到解Z1、Z2和目標函數值C=min(Z1,Z2)

6) 全局下界更新L←C

7) 若兩問題均無解，則算法失敗，停機

8) 若解 αn∈{0, 1},n=1,···,N，則Z?←Z，算法結束，停機

9) 否則，將解、目標函數值與約束參數放入隊列Q

10) whileQ不為空 do

11) 以廣度搜索取出當前問題

12) ifC>Udo

13) continue

14) if 解αn∈{0, 1},n=1,···,Ndo

15) ifU>Cdo

16)U←C

17) end if

18) ifC?>Cdo

19)C?←C,Z?←Z

20) end if

21) else

22) 尋找解中第一個不為0 或1 的分量，取其下標idx，帶入其已確定的節點值，構建兩個新的線性規劃問題r1和r2

23) ifr1計 算成功 andr2計算失敗

24) 將r2的 解與約束參數放入隊列Q

25) elifr2計 算成功 andr1計算失敗

26) 將r1的 解與約束參數放入隊列Q

27) elifr2計 算成功 andr1計算成功

28) 首先將目標函數值C小的問題加入隊列Q

29) end if

30) end if

31) end while

區別于隨機算法，該算法按照廣度優先的方式對狀態空間樹進行搜索，通過不斷地剪枝操作尋找最優解的子節點，最終獲得模型式(9)的確定性解。具體來說，該算法在獲取所有用戶參數之后，將0-1 整數規劃問題的解松弛為[0,1]之間的連續變量，根據松弛線性規劃問題的解是否為整數，來判斷下一步繼續分支還是停止計算。該算法通過不斷地松弛求解，得到原問題的最優解，且其在數十個用戶的小規模問題下可以適用。

本文算法的復雜度主要取決于對松弛線性規劃問題的求解。在使用分支定界法的過程中，每進行一次分支，就會產生兩個松弛線性規劃問題，即最多會產生 2N個松弛線性規劃問題，因此在最差的情況下，本文算法的復雜度為O(2N)。在進行分支定界法的剪枝操作后，當用戶數為150 個時，計算時間可以控制在0.1 s，因此在幾十個用戶規模的問題下該算法可以適用。

具體來說，算法的1)～3)行為初始化全局參數，將上界和下界均設為極值，將最優解與最優目標函數值設為空，再使用環境模型計算出分支定界算法所需要的參數；算法的4)～8)行進行初次的分支，將第一個用戶的決策分為兩支后對分支后的兩個問題松弛計算。判斷該線性規劃問題的解，若解均為0 或1，則算法結束，找到最優目標函數值；若無解，則算法失敗；否則開始分支。算法的8)～29)行通過不斷將不能求解的子問題和目標函數值已經大于問題上界的節點剪枝，同時對該問題下沒有剪枝的葉子節點分支，直到得到解均為整數0 或1，算法結束。

4 仿真分析

設一個帶寬為W=50 MHz 的gNB 小區，gNB基站部署有MEC 服務器，用戶終端設備隨機分布在距離gNB 基站200 m 的范圍內。MEC 服務器的計算容量為F=10 GHz，每個用戶設備的CPU 頻率為fnl=2 GHz，用戶設備的傳輸功率和空閑功率設置為Pn=500 mW和Pin=100 mW。需要計算分配的數據Bn(單位：Bytes)滿足(300, 500)之間的均勻分布，CPU 周期Dn(單位：Megacycles)滿足(900,1 000)之間的均勻分布，時延要求為2 s。每個用戶設備對時延和能耗分配的權重被設置為Int=Ine=0.5。平均信道增益hn遵循自由空間路徑損耗模型：

式中，Ad=4.11表 示天線增益；fc=915 MHz表示載波頻率；de=2.8表示路徑損耗指數。

根據式(7)，可以計算得到用戶設備的數據上傳速率Rul。設置用戶設備數分別為4、6、8、10、12、14、16 個，根據分支定界法計算該模型的最優解Z={α1,α2,···,αn,···,αN}，如表1 所示。

表1 不同用戶設備數下的最優解

圖2 是不同用戶數的代價曲線。從圖中可以看出，本文優化方法的代價小于全部在用戶終端處理或全部在MEC 服務器處理，且隨著用戶數的增加，本文的優化方法優勢更加明顯。同時，本文將實驗結果與能有效地幫助移動設備實現MEC 系統的節能運行的最大節能優先算法[21](select maximum saved energy first, SMSEF)進行對比，本文算法利用貪婪選擇解決優化問題，為MEC 計算資源分配等問題提供解決方案，相較于傳統方法節能效果更好，在用戶數量增大時，本文方法的優勢也逐漸增大。

圖2 代價與用戶設備數的關系

固定用戶設備數目為8 個，改變MEC 服務器的計算容量為6、8、10、12、14 GHz，代價曲線如圖3 所示。由于用戶終端處理不需要MEC服務器，所以隨著MEC 服務器計算容量地增加，用戶終端所需代價幾乎不變。當MEC 服務器計算容量足夠大時，全部在MEC 服務器處理和本文的優化方法得到的結果相接近。同時，相比于最大節能優先算法，本文方法在MEC 服務器計算容量較小時所需的代價更小。

圖3 用戶設備數為8 時代價與MEC 服務器計算容量關系

不失一般性，改變用戶設備的CPU 頻率fnl為(1,3)之間的均勻分布，使得用戶設備的CPU 頻率各不相同，設置用戶設備數目分別為4、6、8、10、12、14、16 個，其代價曲線如圖4 所示。可以看出，隨著用戶數目的增大，本文的優化方法相較于全部在用戶終端處理、全部在MEC 服務器處理和SMSEF 算法，能取得較低的代價，且趨勢與固定用戶設備CPU 頻率時相同。

圖4 不同CPU 頻率下代價與用戶設備數的關系

提升MEC 服務器的計算容量為100 GHz，并增加用戶數量為50、100、150、200、250、300個，如圖5 所示。將本文的優化方法的代價，與全部在用戶終端處理、全部遷移到MEC 服務器處理、隨機調度和循環調度進行比較(隨機調度指隨機決定任務的分配方式，循環調度指采用循環的方式將任務依次分配到用戶設備或MEC 服務器進行處理)。可以看出，隨著用戶數量的增加，本文方法相較于其他方法的優勢更加顯著。

圖5 擴大MEC 服務器容量時代價與用戶設備數關系

隨著用戶規模的增大，本文方法進行任務分配決策的時間也在增加，如圖6 所示。當用戶數小于150 時，計算時間可以控制在0.1 s；當用戶數為300 時，計算時間在0.4 s 以內。在不超過300 個用戶數的情況下，決策時間可接受。隨著用戶數的大規模增加，需要能夠快速決策的智能優化方法來滿足要求。

圖6 分支定界法計算時間與用戶數的關系

5 結 束 語

本文針對移動邊緣計算中低時延與低能耗兩大要求，研究了時延與能耗聯合優化方法。通過對優化問題的研究，建立了0-1 整數規劃模型，采用分支定界算法對模型予以求解，通過仿真，驗證了本文的優化方法的優越性和適用性。本文方法不僅能夠和5G 技術協同解決VR/AR 應用的不足，還能夠應用于聯合作戰、生命健康、智能制造等多個領域。為了適用超大規模用戶終端的需求，未來還將研究智能優化方法，進一步提升移動邊緣計算任務分配的效率與效果。