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

楊 天，楊 軍

（寧夏大學信息工程學院，銀川 750021）

0 概述

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

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

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

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

1 系統模型

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

圖1 多用戶設備的系統模型Fig.1 System model with multiple user devices

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

1.1 本地計算模型

若用戶設備n選擇在本地執行其任務Wn，則用戶設備n的本地執行時延為，定義為：

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

用戶設備n在本地執行Wn的能耗定義為：

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

1.2 卸載計算模型

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

根據上述過程，定義傳輸時延為：

其中，Dn為計算Wn所需輸入數據的大小，包括程序代碼和輸入參數，rU為系統模型無線信道中用戶設備n的上行鏈路速率。

相應地，第1步中能耗定義為：

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

1.3 優化問題模型

本文將MEC系統的任務卸載和資源分配公式化為一個優化問題，目的是使MEC系統總成本（所有用戶執行時延與能耗的加權和）G最小化。該優化問題以公式描述如下：

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

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

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

2.1 編碼

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

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

2.2 適應度函數

本文提出的聯合優化卸載決策與資源分配方案將適應度函數定義為：

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

2.3 初始化

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

2.4 種群選擇

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

算法1種群選擇算法

2.5 交叉

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

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

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

算法2交叉算法

2.6 變異

根據變異概率隨機產生任務的變異序號n，然后對Wn的執行位置進行如下操作：

算法3變異算法

3 仿真實驗

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

3.1 迭代次數對算法性能的影響

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

表1 模擬數據Table 1 Simulation data

圖4 迭代次數對系統總成本的影響Fig.4 Influence of iterations on total system cost

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

3.2 任務數量對算法性能的影響

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

表2 7種算法在不同任務數下的系統總成本Table 2 Total system cost of seven algorithms under different task numbers

3.3 任務周期數對算法性能的影響

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

圖6 任務周期數對系統總成本的影響Fig.6 Influence of task cycle number on total system cost

3.4 任務傳輸數據量對算法性能的影響

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

圖7 任務傳輸數據量對系統總成本的影響Fig.7 Influence of task transfer data size on total system cost

4 結束語

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