移動邊緣計算時延與能耗聯(lián)合優(yōu)化方法

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

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

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

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

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

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

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

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

1 問題描述

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

圖1 多用戶移動邊緣計算系統(tǒng)構成

通過求解Z，使得該MEC 系統(tǒng)的Call最小。

2 聯(lián)合優(yōu)化模型

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

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

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

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

考慮只有一個移動基站的系統(tǒng)，忽略其他小區(qū)的通信干擾，那么，用戶設備的上傳數(shù)據(jù)速率為：

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

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

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

3 分支定界算法

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

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

算法1：時延與能耗聯(lián)合優(yōu)化分支定界算法

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

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

3) 計算初始整數(shù)規(guī)劃問題求解所需參數(shù)

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

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

6) 全局下界更新L←C

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

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

9) 否則，將解、目標函數(shù)值與約束參數(shù)放入隊列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，帶入其已確定的節(jié)點值，構建兩個新的線性規(guī)劃問題r1和r2

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

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

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

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

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

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

29) end if

30) end if

31) end while

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

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

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

4 仿真分析

設一個帶寬為W=50 MHz 的gNB 小區(qū)，gNB基站部署有MEC 服務器，用戶終端設備隨機分布在距離gNB 基站200 m 的范圍內。MEC 服務器的計算容量為F=10 GHz，每個用戶設備的CPU 頻率為fnl=2 GHz，用戶設備的傳輸功率和空閑功率設置為Pn=500 mW和Pin=100 mW。需要計算分配的數(shù)據(jù)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表示路徑損耗指數(shù)。

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

表1 不同用戶設備數(shù)下的最優(yōu)解

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

圖2 代價與用戶設備數(shù)的關系

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

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

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

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

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

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

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

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

5 結 束 語

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