張先超，任天時(shí)，趙 耀，樊 銳

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

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

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

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

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

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

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

1 問題描述

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

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

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

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

若任務(wù)An選擇在用戶終端處理，終端設(shè)備的計(jì)算時(shí)延與能耗為：

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

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

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

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

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

同樣，用時(shí)延和能耗的加權(quán)和，表征任務(wù)分配至MEC 服務(wù)器處理所需代價(jià)：

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

3 分支定界算法

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

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

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

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

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

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

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

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

6) 全局下界更新L←C

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

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

9) 否則，將解、目標(biāo)函數(shù)值與約束參數(shù)放入隊(duì)列Q

10) whileQ不為空 do

11) 以廣度搜索取出當(dāng)前問題

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) 尋找解中第一個(gè)不為0 或1 的分量，取其下標(biāo)idx，帶入其已確定的節(jié)點(diǎn)值，構(gòu)建兩個(gè)新的線性規(guī)劃問題r1和r2

23) ifr1計(jì) 算成功 andr2計(jì)算失敗

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

25) elifr2計(jì) 算成功 andr1計(jì)算失敗

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

27) elifr2計(jì) 算成功 andr1計(jì)算成功

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

29) end if

30) end if

31) end while

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

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

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

4 仿真分析

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

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

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

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

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

圖2 代價(jià)與用戶設(shè)備數(shù)的關(guān)系

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

圖3 用戶設(shè)備數(shù)為8 時(shí)代價(jià)與MEC 服務(wù)器計(jì)算容量關(guān)系

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

圖4 不同CPU 頻率下代價(jià)與用戶設(shè)備數(shù)的關(guān)系

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

圖5 擴(kuò)大MEC 服務(wù)器容量時(shí)代價(jià)與用戶設(shè)備數(shù)關(guān)系

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

圖6 分支定界法計(jì)算時(shí)間與用戶數(shù)的關(guān)系

5 結(jié) 束 語

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