移動邊緣計算中的卸載決策與資源分配策略

楊 天，楊 軍

（寧夏大學(xué)信息工程學(xué)院，銀川 750021）

0 概述

隨著通信技術(shù)的發(fā)展和智能化終端設(shè)備的普及，以物聯(lián)網(wǎng)和移動互聯(lián)網(wǎng)為核心的網(wǎng)絡(luò)服務(wù)及應(yīng)用應(yīng)運而生，特別是5G網(wǎng)絡(luò)的出現(xiàn)，顯著提高了交互式游戲、增強現(xiàn)實（AR）、虛擬現(xiàn)實（VR）和車聯(lián)網(wǎng)等計算密集型應(yīng)用的滲透率［1］。此類應(yīng)用需要在用戶設(shè)備上消耗大量的計算資源和能耗來滿足低時延需求，但由于用戶設(shè)備計算能力和電池能量有限，因此很難滿足這些要求［2］。為緩解這一矛盾，研究者提出移動邊緣計算（Mobile Edge Computing，MEC）作為一種新型且可行的解決方案［3］。MEC是云化無線接入網(wǎng)（Cloud Radio Access Network，C-RAN）的一種新型范式，其通過在移動用戶附近部署高性能服務(wù)器來增強移動網(wǎng)絡(luò)邊緣的計算能力［4］，這將有助于滿足5G業(yè)務(wù)的超低時延、超高能效以及超高可靠性等需求［5］。

計算卸載是MEC中的關(guān)鍵技術(shù)，主要包含卸載決策和資源分配兩個部分［6］，其通過有效的卸載決策和資源分配方案合理安排用戶設(shè)備，將計算任務(wù)卸載至MEC服務(wù)器，同時分配資源進行任務(wù)計算，以降低系統(tǒng)的時延和能耗。

近年來，國內(nèi)外已有較多關(guān)于MEC卸載決策和資源分配的研究，研究者從不同角度提出了可行的解決方案。在卸載決策方面：文獻［7］基于任務(wù)緩沖區(qū)以及本地傳輸模塊與計算模塊的狀態(tài)，利用馬爾科夫決策過程找到最佳的任務(wù)調(diào)度策略以降低能耗和時延；文獻［8］針對綠色能源（太陽能）與電網(wǎng)能源雙向支持的邊緣計算系統(tǒng)，基于Lyapunov優(yōu)化技術(shù)提出一種在線卸載算法，通過權(quán)衡平均響應(yīng)時間與平均能耗成本生成最優(yōu)卸載方案；文獻［9］研究了超密集無線網(wǎng)絡(luò)中單用戶多基站情況下的MEC卸載問題；文獻［10］針對MEC卸載系統(tǒng)，提出基于博弈論的功率分配算法，其在服務(wù)器計算資源的約束條件下，采用二分搜索法優(yōu)化傳輸功率減小傳輸時延和能耗，利用非合作博弈論解決多用戶卸載決策問題，降低系統(tǒng)開銷；文獻［11］通過引入移動云計算（Mobile Cloud Computing，MCC）輔助MEC，進一步降低了系統(tǒng)時延和能耗；文獻［12］將執(zhí)行任務(wù)劃分為可遷移和不可遷移兩個部分，結(jié)合改進的Q學(xué)習(xí)算法和深度學(xué)習(xí)算法最小化移動設(shè)備的能耗和時延；文獻［13］提出一種計算切換策略以優(yōu)化卸載決策。在資源分配方面：文獻［14］在有執(zhí)行延遲約束的條件下應(yīng)用優(yōu)先級隊列分配邊緣節(jié)點與云端節(jié)點，以滿足約束，提高服務(wù)質(zhì)量；文獻［15］采用一種可分離的半定松弛算法聯(lián)合優(yōu)化了多用戶情況下任務(wù)卸載的決策方案和通信資源分配方案；文獻［16］提出一種基于深度強化學(xué)習(xí)算法對計算資源進行分配，以減少能量消耗；文獻［17］提出一種激勵拍賣機制用于移動用戶（買家）和服務(wù)提供者（賣家）之間的資源交易，以有效分配計算資源，滿足移動設(shè)備的服務(wù)需求。

然而，目前多數(shù)研究未考慮在MEC服務(wù)器計算資源有限的情況下如何更好地進行卸載決策和資源分配，進一步減少時延并降低能耗。本文針對此類情況提出一種多用戶卸載決策與資源分配的聯(lián)合優(yōu)化策略。對基于精英選擇策略的遺傳算法（e-GA）進行改進，設(shè)計聯(lián)合卸載決策與資源分配的improve-eGA算法，從而最小化系統(tǒng)總成本。

1 系統(tǒng)模型

本文考慮如圖1所示的系統(tǒng)模型，其中包含1個eNodeB（eNB）和N個用戶設(shè)備，使用eNB部署MEC服務(wù)器。假設(shè)模型中每個用戶設(shè)備都有一個需要完成的計算密集型任務(wù)，每個用戶設(shè)備都可以通過無線方式將任務(wù)卸載至MEC服務(wù)器或者在本地執(zhí)行。但需要注意的是，MEC服務(wù)器的計算資源是有限的，可能不足以完成所有的計算任務(wù)。

圖1 多用戶設(shè)備的系統(tǒng)模型Fig.1 System model with multiple user devices

假設(shè)任務(wù)不能被劃分，即每個用戶設(shè)備只能通過本地計算或卸載計算來執(zhí)行其任務(wù)。將xn∈{0，1}表示為用戶設(shè)備n的卸載決策，并將卸載決策向量定義為Χ=[x1，x2，…，xn，…，xN]。如果用戶設(shè)備n通過本地計算執(zhí)行其任務(wù)，則xn=0，否則xn=1。

1.1 本地計算模型

若用戶設(shè)備n選擇在本地執(zhí)行其任務(wù)Wn，則用戶設(shè)備n的本地執(zhí)行時延為，定義為：

其中，Cn為完成Wn所需的CPU周期數(shù)，fn為用戶設(shè)備n的計算能力。需要注意的是，本地執(zhí)行時延僅包括本地CPU的處理時延，并且不同用戶設(shè)備之間的計算能力可能不同。

用戶設(shè)備n在本地執(zhí)行Wn的能耗定義為：

其中，EJ為完成Wn每個CPU周期的能耗。根據(jù)文獻［18］，本文設(shè)定：

1.2 卸載計算模型

如果選擇通過卸載計算來執(zhí)行任務(wù)Wn，則整個卸載過程可分為以下三步：1）通過無線方式向eNB上傳輸入數(shù)據(jù)（即程序代碼和參數(shù)），eNB將數(shù)據(jù)轉(zhuǎn)發(fā)給MEC服務(wù)器；2）MEC服務(wù)器分配部分計算資源代替執(zhí)行計算任務(wù)，此時用戶設(shè)備n在等待計算結(jié)果；3）MEC服務(wù)器將執(zhí)行結(jié)果返回給用戶設(shè)備n，卸載過程結(jié)束。

根據(jù)上述過程，定義傳輸時延為：

其中，Dn為計算Wn所需輸入數(shù)據(jù)的大小，包括程序代碼和輸入?yún)?shù)，rU為系統(tǒng)模型無線信道中用戶設(shè)備n的上行鏈路速率。

相應(yīng)地，第1步中能耗定義為：

其中，PU為用戶設(shè)備n的上傳功率。

1.3 優(yōu)化問題模型

本文將MEC系統(tǒng)的任務(wù)卸載和資源分配公式化為一個優(yōu)化問題，目的是使MEC系統(tǒng)總成本（所有用戶執(zhí)行時延與能耗的加權(quán)和）G最小化。該優(yōu)化問題以公式描述如下：

其中，Χ表示卸載決策方案，f表示計算資源分配方案，Tn與En分別是Χ與f下Wn的時延和能耗，α和β是權(quán)重系數(shù)，分別表示系統(tǒng)對時延與能耗的關(guān)注程度，兩者取值范圍為0～1且總和為1，具體數(shù)據(jù)可根據(jù)應(yīng)用的實際需要或設(shè)備的實際情況進行設(shè)定。對于時延敏感性應(yīng)用，可適當調(diào)高α、降低β，而對于用戶設(shè)備能耗不足的情況，則可適當調(diào)高β、降低α。本文同等重視時延與能耗，因此，將α和β均設(shè)定為0.5。

2 卸載決策與資源分配策略

本文考慮MEC服務(wù)器計算資源有限的情況，對基于精英選擇策略的遺傳算法（e-GA）進行部分改進，優(yōu)化其任務(wù)執(zhí)行位置和資源分配過程，從而實現(xiàn)MEC系統(tǒng)總成本G的最小化。

2.1 編碼

本文采用改進的二進制編碼法，將卸載決策方案Χ與計算資源分配方案f聯(lián)合表示為一個個體，具體如圖2所示。需要注意的是，當xn=0時=0 GHz且f應(yīng)當滿足式（7）所示的限制條件，以保證計算資源分配的合理性。

圖2 編碼示意圖Fig.2 Schematic diagram of encoding

2.2 適應(yīng)度函數(shù)

本文提出的聯(lián)合優(yōu)化卸載決策與資源分配方案將適應(yīng)度函數(shù)定義為：

其中，H為常數(shù)，其取值根據(jù)實際情況而確定。系統(tǒng)總成本越小，適應(yīng)度值越大，算法通過F進行迭代，逐步找到最優(yōu)解決方案。

2.3 初始化

對N個任務(wù)的執(zhí)行位置進行初始化，即對每個任務(wù)隨機產(chǎn)生0或1，表示在本地或MEC服務(wù)器上執(zhí)行，然后對需要在MEC服務(wù)器上執(zhí)行的計算任務(wù)進行計算資源分配。此處假設(shè)MEC服務(wù)器可分配的計算資源是預(yù)先規(guī)定的。例如，MEC服務(wù)器總的計算資源FS=5 GHz，每個任務(wù)可被分配的計算資源設(shè)A、B、C分別對應(yīng)每種可分配資源的個數(shù)，因此，首先要統(tǒng)計進行卸載計算的任務(wù)個數(shù)NO，然后對A、B、C進行求解，如式（19）所示，并將求解得到的結(jié)果隨機分配到初始的卸載方案中。需要注意的是，本地計算任務(wù)的MEC分配資源為0 GHz。

2.4 種群選擇

為防止當前種群的最優(yōu)個體在下一代發(fā)生丟失，導(dǎo)致遺傳算法不能收斂到全局最優(yōu)解，本文采用精英選擇策略，即對當前種群里的最優(yōu)基因個體與下一代最優(yōu)基因個體的適應(yīng)度值進行比較，如果前者值大，則將當代的最優(yōu)基因個體不進行交叉變異直接復(fù)制到下一代種群中。精英選擇策略有兩種方式：一種是將最優(yōu)基因個體（elitist）直接加入到下一代種群中，擴大種群數(shù)目；另一種是將下一代種群中適應(yīng)度值最小的基因個體與elitist進行代換，保持種群數(shù)目。本文策略使用第二種方式，具體算法描述如下：

算法1種群選擇算法

2.5 交叉

本文采用多點交叉法，以產(chǎn)生更高質(zhì)量的基因個體。首先根據(jù)交叉概率隨機生成一條長度為N的布爾值列表，列表中的每一項表示該點是否進行交叉，假設(shè)True代表交叉點，F(xiàn)alse代表非交叉點。卸載決策方案和計算資源分配方案都要進行交叉操作，具體如圖3所示。

圖3 交叉操作示意圖Fig.3 Schematic diagram of crossover operation

需要注意的是，若交叉后的計算資源分配方案不滿足式（7）所示的限制條件，則交叉失敗。交叉算法描述如下：

算法2交叉算法

2.6 變異

根據(jù)變異概率隨機產(chǎn)生任務(wù)的變異序號n，然后對Wn的執(zhí)行位置進行如下操作：

算法3變異算法

3 仿真實驗

通過仿真對比實驗來驗證本文策略的有效性。在仿真模擬中，假設(shè)每個任務(wù)的數(shù)據(jù)規(guī)模即傳輸數(shù)據(jù)量D（n以Kb為單位）服從（300，500）之間的均勻分布，對應(yīng)所需的任務(wù)周期數(shù)Cn服從（800 Megacycles，1 200 Megacycles）之間的均勻分布。MEC服務(wù)器的計算能力FS為5 GHz，可分配計算資源與2.3節(jié)中一致，信道上傳速率為2 Mb/s。為方便起見，假設(shè)N個用戶設(shè)備是一樣的，計算能力均為0.8 GHz，傳輸功率和空閑功率分別為500 mW和100 mW。模擬全部本地執(zhí)行算法ALL_Local、全部卸載算法ALL_Offload、隨機卸載分配算法RANDOM、標準遺傳算法CGA以及文獻［13］中的MET、MCT算法，并與本文提出的improve-eGA算法進行對比。在ALL_Offload算法中，MEC服務(wù)器為每個任務(wù)平均分配計算資源。

3.1 迭代次數(shù)對算法性能的影響

假設(shè)MEC系統(tǒng)一次處理6個任務(wù)，具體參數(shù)如表1所示。設(shè)種群數(shù)目為60，交叉概率為0.8，變異概率為0.05，迭代次數(shù)從1遞增至100，迭代次數(shù)對系統(tǒng)總成本的影響如圖4所示?？梢钥闯觯篈LL_Local與ALL_Offload算法曲線不隨迭代次數(shù)的增加而改變，且始終保持在較高數(shù)值；RANDOM算法曲線在整個迭代過程中震蕩，不能收斂；CGA、MET、MCT與improve-eGA算法曲線隨著迭代次數(shù)的增加逐步遞減，逐漸收斂。CGA、MET、MCT及improved-eGA算法的具體對比如圖5所示?？梢钥闯觯篊GA算法曲線前期震蕩，在55次迭代后逐步收斂至局部最優(yōu)解，但收斂趨勢緩慢，這是因為算法中交叉、變異的操作可能導(dǎo)致當前種群中的最優(yōu)基因個體在下一代種群中發(fā)生丟失，而且這種最優(yōu)基因個體丟失的現(xiàn)象會重復(fù)出現(xiàn)在進化過程中；MET、MCT和improve-eGA算法分別在38次、76次與17次迭代時收斂，三者的系統(tǒng)總成本相較于CGA算法分別降低1.5%、1.95% 與2.86%，因為MET與MCT算法過多關(guān)注于系統(tǒng)任務(wù)的計算時延和完成時延，所以這兩種算法的系統(tǒng)總成本略低于improve-eGA。綜上可知，improve-eGA在迭代次數(shù)影響下系統(tǒng)總成本低于對比算法。

表1 模擬數(shù)據(jù)Table 1 Simulation data

圖4 迭代次數(shù)對系統(tǒng)總成本的影響Fig.4 Influence of iterations on total system cost

圖5 CGA、MET、MCT與improve-eGA的系統(tǒng)總成本對比Fig.5 Comparison of total system cost of CGA，MET，MCT and improve-eGAs

3.2 任務(wù)數(shù)量對算法性能的影響

分別模擬20～100的累計任務(wù)數(shù)量（以10遞增），比較7種算法的系統(tǒng)總成本，其中迭代次數(shù)設(shè)定為100。如表2所示，可見系統(tǒng)總成本隨著任務(wù)數(shù)量的增加而增加，這是由于任務(wù)數(shù)量的增大，導(dǎo)致系統(tǒng)需要更大的時延與能耗開銷，從而使得系統(tǒng)總成本增加。從表2中可以看出：ALL_Local、ALL_Offload與RANDOM算法系統(tǒng)總成本較高，其余4種算法在任務(wù)數(shù)量小于70時差距較??；當任務(wù)數(shù)量大于等于70時，improve-eGA算法的實驗結(jié)果更優(yōu)。由此表明，在大規(guī)模任務(wù)計算卸載中，improve-eGA算法具有較大優(yōu)勢。

表2 7種算法在不同任務(wù)數(shù)下的系統(tǒng)總成本Table 2 Total system cost of seven algorithms under different task numbers

3.3 任務(wù)周期數(shù)對算法性能的影響

比較7種算法在任務(wù)周期數(shù)為800 Megacycles～1 200 Megacycles時（以100遞增）系統(tǒng)總成本的變化，其中任務(wù)數(shù)量為70。如圖6所示：隨著任務(wù)周期數(shù)的增加，系統(tǒng)總成本也逐漸增加，這是因為任務(wù)周期數(shù)的增加會帶來任務(wù)計算時間的增加，從而導(dǎo)致系統(tǒng)總成本增高；在不同任務(wù)周期數(shù)下，improve-eGA、MET和MCT算法系統(tǒng)總成本都低于其他4種算法，且improve-eGA算法結(jié)果更優(yōu)。

圖6 任務(wù)周期數(shù)對系統(tǒng)總成本的影響Fig.6 Influence of task cycle number on total system cost

3.4 任務(wù)傳輸數(shù)據(jù)量對算法性能的影響

比較7種算法在不同任務(wù)傳輸數(shù)據(jù)量下系統(tǒng)總成本的變化，其中任務(wù)數(shù)量為70。如圖7所示：隨著數(shù)據(jù)量從300 Kb增長到500 Kb，ALL_Local算法保持不變，這是因為所有任務(wù)在本地執(zhí)行，不需要傳輸成本，但其系統(tǒng)總成本依然很高；其余6種算法系統(tǒng)總成本逐漸增高，這是因為數(shù)據(jù)量的增長，導(dǎo)致傳輸?shù)臅r間成本增高，進而系統(tǒng)總成本增高；而improve-eGA算法在不同傳輸數(shù)據(jù)量下系統(tǒng)總成本最低。

圖7 任務(wù)傳輸數(shù)據(jù)量對系統(tǒng)總成本的影響Fig.7 Influence of task transfer data size on total system cost

4 結(jié)束語

本文針對MEC計算資源有限的情況，研究多用戶任務(wù)卸載決策和計算資源分配的聯(lián)合優(yōu)化問題。通過將研究問題轉(zhuǎn)換為數(shù)學(xué)模型，提出一種MEC多用戶卸載決策和資源分配策略。對基于精英選擇策略的遺傳算法進行改進，優(yōu)化其編碼、交叉、邊緣等操作，在此基礎(chǔ)上設(shè)計聯(lián)合卸載決策與資源分配的improve-eGA算法。實驗結(jié)果表明，該算法性能優(yōu)于RANDOM、CGA、ALL_Local、AL_Offload、MET和MCT算法。下一步將設(shè)計一種考慮多個MEC服務(wù)器、任務(wù)可分割并可解決無線干擾問題的卸載決策和資源分配策略。