MEC聯合資源分配與計算卸載的效益

楊錦霞，郭榮佐，陳芳瑩

(四川師范大學 計算機科學學院，四川 成都 610101)

0 引 言

移動邊緣計算(mobile edge computing，MEC)作為5G通信的主要應用之一，在更靠近數據源的網絡邊緣為物聯網設備提供低延遲計算和通信服務，能夠有效緩解物聯網終端設備自身能力不足的問題[1,2]。在5G環境下，MEC的任務處理時延占整個卸載時延的最大比例[3]。合理分配有限的計算資源對卸載性能有著至關重要的影響。因此，研究MEC構成的物聯網的資源分配與計算卸載的系統效益問題，對提高物聯網邊緣計算的服務質量(quality of service，QoS)是十分必要的。

針對計算資源分配問題Zhang等[4]提出了一個高效的移動邊緣云計算網絡框架，通過最優定價和云計算資源管理實現MEC和云的利潤最大化。該文聯合移動云計算有效緩解計算資源不足的問題，但是沒有考慮用戶卸載效益。Ning等[5]分別研究了單用戶和多用戶場景下的計算資源分配問題，設計了一種迭代啟發式MEC資源分配算法，以動態地做出卸載決策。針對計算卸載與資源分配聯合優化問題Wang等[6]提出了一個多層數據流處理系統，將任務分配到多個層次處理。Kiran等[7]構建了一種新的MEC軟件定義邊緣云框架，提出了基于強化學習算法的方案來解決計算卸載與資源分配問題。

綜上所述，這些研究都是非常有意義的，為進一步研究物聯網邊緣計算的計算卸載決策與計算資源分配的聯合優化奠定了堅實基礎。首先構建了系統卸載效益模型，提出了保證效益為正的最小計算資源分配閾值，將問題轉化為帶約束的系統卸載效益最大化問題，并利用罰函數解決約束問題。其次引入了遺傳算法優化(genetic algorithm optimization，GAO)，為了適應問題設計了一種兩段式染色體結構和遺傳算子。最后進行仿真實驗，對比分析了隨機卸載決策和平均計算資源分配、全部卸載決策和隨機計算資源分配等4種策略，GAO無論是在時延還是能耗均優于其它方案。同時還分析得出算法在傳輸功率、設備數量等重要參數下均具有較好的靈敏性。

1 系統模型

1.1 系統概述

如圖1所示，考慮一個資源受限的小型移動邊緣計算卸載系統，該系統有多個移動智能設備(smart mobile device，SMD)和一個MEC服務器(mobile edge computing server，MECS)。MECS部署在微蜂窩基站上，基站與MECS通過高帶寬有線直接相連，為用戶提供計算服務[8]。設備通過無線的方式與基站進行交互，只有在可以建立無線連接的情況下，移動設備才能訪問服務器。假設在任意時隙，SMD都有一個計算密集型任務待處理，且任務都具備可分割性，可以部分在本地處理，部分在MECS上處理。MEC服務器可以動態地分配其計算資源來執行從不同的SMD卸載的任務。同時考慮一個準靜態信道模型，即信道的狀態在各個卸載階段保持不變，且一旦開始卸載，用戶將無法停止直到整個卸載完成[9]。

為了方便分析，設系統有K個移動智能設備，K=[1,2,…,k]， 每個用戶的SMD用一個二元組Dk={fk,Pk} 來描述。其中fk， cycles/s表示SMDk的計算能力，Pk表示卸載任務時的傳輸功率；類似的，每個任務用一個三元組τk={dk,ck,ok} 來刻畫。其中dk， bits表示SMDk的任務數據總量，ck表示計算任務1 bit數據需要花費的CPU周期個數，ok∈[0,1] 表任務卸載比例。任務執行的時延由本地計算時延、傳輸時延以及MECS端計算時延3部分組成。由于MECS有持續不斷的供電電源，因此不考慮服務器端的能耗，則能耗僅包含本地執行能耗和數據卸載的傳輸能耗兩部分。

圖1 多用戶MEC系統

1.2 通信模型

計算卸載過程可以簡單描述為：SMD將輸入數據由上行鏈路傳輸到MECS，MECS執行計算，計算完成后再將計算結果由下行鏈路傳回到SMD上。計算卸載過程產生額外的傳輸時延和能耗是影響用戶QoS的重要因素，而傳輸時延和傳輸能耗受數據傳輸速率的影響。

設移動運營商提供的總帶寬為B， MHz，系統的上行鏈路采用正交頻分多址(orthogonal frequency division multiple access，OFDMA)技術，總通信頻帶均分為K個帶寬為B/K， MHz的正交子頻帶。為減少傳輸的信道干擾，每個用戶在卸載周期內分別占用不同的子頻帶。根據香農公式可得出任務卸載到服務器的傳輸速率為

(1)

其中，Bk=B/K，Pk為傳輸功率，Gk為SMDk與基站之間上行鏈路的信道增益，σ2為背景噪聲功率。傳輸時延=傳輸的數據總量/傳輸速度，根據式(1)可得上行鏈路的傳輸時延為

(2)

傳輸過程中設備能量消耗=傳輸時間*傳輸功率，因此根據式(2)的傳輸時間可得上行鏈路任務的傳輸能耗為

(3)

其中，Ln是尾部能量，在數據傳輸完成之后會繼續保持信道狀態一段時間，這種尾能量現象在移動蜂窩網絡中普遍存在[10]。

1.3 本地計算模型

任務在本地執行產生的時延可以表示為

(4)

CPU每周期能量消耗模型E=?f2， ?是與CPU芯片結構相關的能量消耗系數，f， cycles/s是CPU計算頻率[11]。則任務在本地執行消耗的能量可以表示為

(5)

1.4 MECS計算模型

(6)

由于每個用戶計算的數據量以及其它參數之間的差異，MECS應該給每個任務分配不同數量的計算資源。一般來說，計算結果的大小遠小于輸入數據，下行鏈路的數據傳輸速率也遠遠大于上行鏈路。因此，不考慮計算結果回傳的時延[14,15]。

MEC服務器由某個運營商操作和維護，將從提供計算卸載服務中收取一定的費用[16]。設用戶租用MEC服務器計算資源的代價為線性函數cost=αx+β， 其中α≥0，β為代價函數系數，為了便于分析，令β=0。 則SMDk租用計算資源的代價costk為

costk=αfk

(7)

1.5 卸載實體

卸載產生的總時延Tk為本地執行時延、傳輸時延和MEC服務器計算時延之和

(8)

由式(2)、式(4)、式(6)可得SMDk的整體時延開銷為

(9)

SMDk的總能耗為本地執行能耗和傳輸能耗之和

(10)

由式(3)、式(5)可得SMDk的整體能耗為

(11)

計算卸載的目的是增強設備的計算能力從而滿足用戶的時延、能耗需求，此外卸載的費用也影響著用戶的QoS。因此將卸載問題轉化為聯合卸載時延效益、能耗效益以及費用的卸載效益最大化問題。設SMDk的時延效益TRk為

(12)

類似的，能耗效益ERk為

(13)

Uk=ωtTRk+ωeERk+ωccostk

(14)

考慮到效益建模的靈活性，式中ωt、ωe、ωc分別表示時延效益、能耗效益及費用的權重。通過設置權重可分別捕捉用戶在這3方面的偏好，以滿足用戶不同的需求。

1.6 問題制定

(15)

(16)

C2表示每個用戶總卸載時延應該小于完全本地計算的時延，以保證用戶卸載的有效性，避免計算資源的浪費。由C2可進行如下推導

2 基于改進遺傳算法的問題求解

問題P1是一個混合整數非線性(mixed integer nonli-near programming，MINLP)問題，難以用低復雜度算法求得全局最優解。因此，為了便于實驗實現，本文引入改進的低復雜度遺傳算法對問題求解。遺傳算法是一種模仿生物進化論的啟發式算法，能很好的在有效性和復雜度之間取得平衡，為NP難問題求得近似最優解。每條染色體對應問題的一個可能解，為了簡化編碼和解碼過程，采用實數編碼的方法初始化每條染色體。如圖2所示，設計一個兩段式的染色體，即每條染色體由兩組長度均為K的基因序列OD和RA構成，分別對應K個設備的卸載決策和計算資源分配結果。

圖2 染色體結構

遺傳算法的一般過程為初始化、個體適應度評估、選擇、交叉、變異。下面將描述利用改進的遺傳算法求解卸載效益最大化問題的主要過程。

(1)初始化

(2)個體評估

初始化種群后，通過P1對每個個體進行評估。由于該問題含約束條件，可能存在違反約束條件的個體，稱這些個體為不可行解。為了解決約束限制，采用了罰函數求解約束優化問題的思想：可行解優于不可行解，對不可行解進行懲罰，為可行域提供搜索方向。定義如下罰函數

CV=CV1+CV2

(17)

(18)

(19)

CV1和CV2分別解決不等式約束C2、C3。適應度值越大，個體越優秀，則對于任意個體cn適應度函數為

fit(cn)=U(cn)-λCV

(20)

λ為懲罰因子。

(3)選擇

采用輪盤賭選擇方法，該方法根據適應度值大小對個體進行選擇，適應度值較大的優秀個體，被選擇的概率也更大，從而保證優秀個體能保留下來。首先根據式(20)計算出每個個體的適應度值，再根據適應度值計算每個個體的累積概率pn，pn對應輪盤跨度，跨度越大，個體被選中的概率越大。pn的計算公式為

(21)

產生一個[0,1]之間的隨機數r，保留pn>r的第一個個體n。

(4)交叉

(22)

其中，β滿足以下的概率密度函數

(23)

式中：隨機數μ∈[0,1]，ηc為交叉分布指數。

圖3 交叉操作

(5)變異

這一步采用多項式變異算子來產生子代。首先產生一個[0,1]之間的隨機數pm， 若pm

(24)

式中：隨機數v∈[0,1]，ηm為變異分布指數，對于基因序列OD來說xmax，xmin分別為卸載決策的最大值和最小值，對于基因序列RA來說xmax，xmin則分別為資源分配的最大值和最小值。

圖4 變異操作

算法求解的具體過程見表1。

表1 基于改進的GA算法的問題求解

3 實驗仿真與結果分析

3.1 實驗設置

本節將通過Matlab R2017a仿真，參照已有文獻的參數設置模擬MEC系統，分析所提算法的性能。設定服務器的計算能力F=50 GHz，總帶寬B=20 MHz，移動設備的個數N=20，設備輸入數據量dk為 [500,1000] kbi的隨機值，每bit數據的計算強度ck取值范圍為[500,100] cycles/bit。設備的計算能力fk為[0.5,2.0] GHz的隨機值，傳輸功率P=100 mW。設備與基站之間的信道增益Gk服從范圍[-50,30] dBm的隨機分布，噪聲功率譜密度-174 dBm/Hz。

3.2 權重設置分析

系統效益由時延效益、能耗效益和費用3部分構成，這3部分的量級各不相同，為了更好了解模型的各個組成部分對系統效益做出的貢獻，分析不同權重設置下的系統總效益。設置4種不同的權重：

編號1：ωt=1，ωe=1，ωc=1；

編號2：ωt=10，ωe=1，ωc=1；

編號3：ωt=1，ωe=10，ωc=1；

編號4：ωt=1，ωe=1，ωc=10。

編號1為基準，編號2、編號3、編號4分別測試時延效益、能耗效益以及費用對效益的貢獻，由圖5可知，能耗的貢獻最大，時延次之，費用的變化最小。因此在分析不同參數對系統效益的影響時，需要選擇合適的權重設置。

圖5 不同權重設置下的系統總效益

3.3 算法收斂性能分析

圖6顯示出了種群規模大小對算法收斂速度的影響。隨著迭代次數的增加，不同的種群規模幾乎都能收斂到同一最優值。此外，種群規模越大，收斂所需的迭代次數越少。當個體為50時需要100次左右迭代才收斂，而個體數為100時收斂所需的迭代次數減少到75左右。當個體數量為150和200時，收斂只需要50左右的迭代次數。因此，個體數設為100。

圖6 系統效益隨迭代次數的變化

3.4 計算資源分配策略對效益的影響

計算資源分配主要影響卸載時延，在該分析中設定時延效益為主要因素，選擇編號2的權重設置，令ωt=10。如圖7可知，計算資源分配對系統效益的影響十分明顯，GAO、隨機分配和均分3種資源分配策略均能收斂，但是GAO策略下的系統效益明顯高于其它兩種方案。這是由于各個設備的性能以及任務的復雜程度等各有差異，GAO能根據這些差異每次進化都保留優秀的個體，從而得到最佳的計算資源分配結果。

圖7 計算資源分配策略對效益的影響

3.5 設備數量對系統效益的影響

圖8顯示了不同策略下設備數量對系統平均效益的影響。可見隨著設備數量的增多，系統平均效益減少，原因是邊緣服務器的計算資源是有限的，設備數量增多導致分配到的計算資源減少，MEC服務器端的處理時延增大，在本地執行的數據量增多從而時延效益減少。GAO較其它4種方案減少的較為緩慢且效益值最高，能根據當前的設備和服務器的計算資源進行決策調整，做出最佳的策略。

圖8 設備數量對效益的影響

3.6 MECS計算資源總量對效益的影響

由于計算資源是影響時延效益的主要因素，為了便于分析，選擇編號2的權重設置，令ωt=10。從圖9可以看出，在5種不同方案下，系統效益均隨著計算資源的增加而增加。當F較小時系統的平均效益很低，這是因為有限的計算資源無法支持大量設備的計算密集型任務，而當F達到35左右后，效益迅速增加，這是因為這個值滿足了當前設備數量下最低計算卸載資源量。對比其它4種策略，GAO方案下的系統效益值明顯高于其它方案。

圖9 MECS計算資源量對效益的影響

3.7 傳輸功率對效益的影響

傳輸功率影響能耗和上傳時延，而任務的上傳時延遠小于任務在MEC服務器執行的時延，因此設定能耗效益為主要因素，選擇編號3的權重設置，令ωt=10。分析圖10可以得知，傳輸功率越大系統效益越低，原因是傳輸功率增大，傳輸能耗增大，能耗效益減少。隨著功率均勻增加，總效益變化放緩，與其它參數相比，傳輸功率對系統總效益的影響較小。

圖10 傳輸功率對效益的影響

4 結束語

針對物聯網邊緣計算的計算卸載決策與計算資源分配的聯合優化卸載效益并保證卸載的有益性，本文提出了以時延效益、能耗效益以及卸載費用加權和的系統卸載效益這一概念，并將問題轉化為系統效益最大化問題。引入了針對該問題改進的遺傳算法，該算法不僅能在不同參數上有著很好的靈敏性，而且相對于其它卸載決策和資源分配方案能明顯提高系統的平均卸載效益。本文考慮的是單個MEC服務器的情況，未來可以考慮多個MEC服務器以及聯合計算資源更加豐富的云計算服務器。