移動邊緣計算場景下基于免疫優化的任務卸載

朱思峰，孫恩林，柴爭義

(1.天津城建大學 計算機與信息工程學院，天津 300384；2.天津工業大學 計算機科學與技術學院，天津 300387)

5G技術提出了三大應用場景[1]：增強型移動帶寬(enhance Mobile Broad Band，eMBB)、海量接入(massive Machine Type of Communication，mMTC)、超高可靠和低延遲通信(ultra Reliable & Low Latency Communication，uRLLC)。隨著低時延低能耗移動終端應用需求的大量涌現，滿足低時延低能耗的移動計算模式成為了熱點研究領域[2-3]。邊緣計算通過把云服務中心的計算資源和存儲移到移動終端的附件(即移動網絡的邊緣)，可減少云服務的通信時延，支持低時延應用服務，滿足低延遲應用場景需求。移動邊緣計算(Mobile Edge Computing，MEC)，即將云計算的服務器從核心網絡下沉到靠近移動終端的網絡邊緣，已經成為一種有效的計算模式[4]。與傳統云計算相比，邊緣計算具有明顯的優勢：① 大量數據在MEC服務器進行處理，不需要將全部數據傳輸到中心服務器上進行存儲，一方面降低了云計算服務中心的計算壓力和存儲壓力；另一方面緩解了網絡的帶寬壓力。② 數據處理在移動邊緣計算服務器上執行，減少了數據上傳到計算中心處理的高時延，從而提高系統的響應能力。③ 用戶產生的隱私數據不需要上傳到云數據中心，使得用戶的隱私得到保障。④ 用戶的大部分數據在邊緣執行，使得計算中心的能耗大大降低。

目前，移動邊緣計算場景下的卸載決策問題引起了國內外學者廣泛關注：文獻[5]把執行時延和任務成功率作為性能指標，提出了一種卸載動態優化方案；文獻[6]研究了基于延時機制的多目標工作流調度算法，該算法使用遺傳算法作為優化方法，結合了工作流之間的依賴關系，在編碼的時候充分考慮了工作流中的任務執行位置和執行順序，極大地降低了移動設備的能耗，縮短了任務執行的時延；文獻[7]通過研究二進制卸載模型，考慮移動終端的計算模式選擇、系統傳輸時延分配的聯合優化問題，給出了一種最大化所有移動終端計算速度的優化方案；文獻[8]研究了各個任務之間的依賴關系，提出了一種結合工作流調度的卸載策略，并設計了基于遺傳算法的卸載策略；文獻[9]將卸載任務構建成圖結構，使用快速啟發式算法尋找最優解決方案；文獻[10]研究物聯網環境中邊緣計算問題，給出了一種基于遺傳算法的任務卸載方案來提升物聯網設備的通信效率；文獻[11]提出一種緩存輔助邊緣計算的卸載決策制定與資源優化方案，以進一步降低移動邊緣計算系統中移動終端的能量消耗；文獻[12]給出了一種移動邊緣環境下能夠聯合優化多用戶時延與移動邊緣計算服務器資源分配平衡度的計算卸載方法；文獻[13]研究了物聯網移動邊緣計算場景下基于時延約束感知的任務卸載策略。

上述文獻所提方案從系統響應時延或移動終端能耗等方面進行考慮，給出了相應的任務卸載策略。不同于上述文獻，筆者對系統響應時延和移動終端能耗進行綜合考慮，給出了一種最小化系統響應時延和移動終端能耗的任務卸載方案。主要貢獻是：(1)提出一種基于任務切分的邊緣計算卸載優化模型；(2)給出了一種基于免疫優化方法的任務卸載解決方案。

1 移動邊緣計算場景下任務卸載的系統模型

在移動邊緣計算場景下，為了把云計算服務器從核心網絡下沉到靠近移動終端的網絡邊緣，在移動基站附近部署移動邊緣計算服務器。另外，為了縮短基站與移動邊緣計算服務器之間的通信時延，移動基站與移動邊緣計算服務器之間通過光纖相連接。移動終端處于基站的覆蓋范圍內，并通過無線與基站相連。移動終端把任務發送給基站，再由基站通過光纖傳輸到移動邊緣計算服務器。筆者建立的系統模型如圖1所示。在該系統模型中，假設某基站覆蓋范圍內有一臺需要任務卸載的移動終端，基站通過光纖連接有一臺移動邊緣計算服務器。

筆者做的一些基本假設：

(1) 只考慮一個執行任務，并且執行任務是可切分。

(2) 每個任務均可以切分為多個子任務(進程)。每個子任務之間的依賴關系只有依賴于前一個子任務，或不依賴于前一個子任務。

(3)子任務上傳到移動邊緣計算服務器可以并行執行。

(4) 任務上傳期間或者計算結果下載期間，通道的信號質量是穩定的。

(5) 移動終端執行計算任務和傳輸數據時的能耗是遠遠高于待機時的能耗。

(6) 移動終端和移動邊緣計算服務器在執行任務時具有穩定的計算能力，并且MEC服務器的計算能力遠遠高于移動終端的計算能力。

圖1 系統模型

1.1 任務切分模型

假設移動終端上的任務T可切分成多個子任務，即任務T可以被劃分為N個子任務的切片T={t1，t2，…，tN}。任務T可分為4部分，即T={Din，W，Z，Dout}。其中，Din表示將任務部署到MEC服務器時所需上傳的數據量；W表示該任務的計算量；Z表示執行該任務需要的計算資源；Dout表示任務在MEC服務器上計算完成后，將計算結果下載到移動終端的數據量。

1.2 時延模型

假設移動終端的計算能力是恒定的，即移動終端的的計算能力為一個固定的值clocal；假設第i個計算子任務在本地執行，該子任務的計算時延為

(1)

假設移動邊緣計算服務器的計算資源為ZMEC，計算能力在進行計算處理時是穩定的，記為CMEC；移動終端上傳的傳輸速率是固定值為rup，移動移動終端下載數據任務的傳輸速率為rdown。若將第i個子任務上傳到移動邊緣計算服務器上進行計算，則第i個子任務的執行時延為

(2)

將第i個子任務卸載到邊緣服務器執行時，除了考慮MEC服務器完成計算工作量產生的時延外，還需要考慮其前后兩個子任務的卸載情況及其產生的相關時延。式(2)中對應了其前后兩個子任務的卸載情況的4種組合。xi-1=0，xi=1，xi=0：第i-1個子任務和第i+1個子任務都沒有卸載，此時要考慮了當前子任務的數據上傳時延和計算結果下載時延；xi-1=1，xi=1，xi+1=0：第i-1 個子任務進行了卸載但第i+1個子任務沒有卸載，此時要考慮當前子任務的計算結果的下載時延；xi-1=0，xi=1，xi+1=1：第i-1 個子任務沒有卸載但第i+1個子任務進行了卸載，此時要考慮當前子任務的數據上傳時延；xi-1=1，xi=1，xi+1=1：第i-1 個子任務和第i+1個子任務都執行了卸載，此時不需要考慮當前子任務的數據上傳時延和計算結果下載時延。

每個子任務要么在本地執行，要么卸載到移動邊緣計算服務器上執行。設決策變量xi表示第i個子任務卸載情況，xi=1表示第i個子任務卸載到移動邊緣計算上執行，xi=0表示第i個子任務在本地執行，則執行任務T的總時延為

(3)

1.3 能量消耗模型

假定移動終端的能耗與執行任務的時延成正比，這個能耗系數與移動終端的組織結構有關，將其設為λ，則第i個子任務在本地執行的能耗模型為

(4)

當把第i個子任務卸載到移動邊緣計算服務器上執行時，只需考慮數據上傳過程和結果數據下載過程移動終端的能耗模型，如下所示：

(5)

其中，λ2是移動移動終端上傳數據時的能耗系數，λ3是移動終端下載數據時的能耗系數。

每個子任務要么在本地執行，要么卸載到移動邊緣計算服務器上執行。設決策變量xi表示第i個子任務卸載情況，xi=1 表示第i個子任務卸載到移動邊緣計算上執行，xi=0 表示第i個子任務在本地執行，則移動終端執行第i個子任務的能耗模型如下所示，

(6)

移動終端執行任務T的總能耗模型如下所示：

(7)

其中，ECi代表執行第i個子任務的能耗。

1.4 優化模型

移動邊緣計算場景下，最小化時延和最小化移動終端設備的能耗是待優化的2個目標。對系統響應時延和移動終端能耗進行綜合考慮，使用權重系數平衡計算時延和能耗之間的比重，通過加權處理后把2個目標轉化為一個綜合代價目標，建立了一個最小化綜合代價的約束優化模型，

(8)

2 基于免疫優化的任務卸載方案

近年來，仿生類智能優化算法獲得了很大進展。模擬生物免疫系統的免疫調節、免疫識別、克隆選擇、免疫記憶等機制而研制的免疫算法(Immune Algorithm，IA)在單目標優化、多目標優化、動態優化等方面性能表現優異，在資源調度、頻譜資源優化、圖像分類與識別等多個領域得到了廣泛應用[14-18]。對于優化問題，純數學方法的優點是理論上能找到問題的最優解。但當問題規模很大時，求解變得非常困難；另外，純數學方法難以實現并行處理。相比于傳統純數學算法[19-20]，免疫算法具有結構簡單高效和能夠并行處理等優點。在工程上，側重考慮方案的有效性，即在滿足性能要求的前提下，找到較優的可行解決方案就可以了。對于大規模問題，純數學方法難以勝任，而IA可以在滿足性能要求的前提下找到較優的可行解決方案。對于實時性要求高的場景(在線處理)，IA方法比純數學方法具有優勢。基于此，文中采用IA方法來求解任務卸載問題。

2.1 抗體編碼

將移動終端中的一個計算任務切分為多個子任務，子任務之間的依賴關系：每個子任務只依賴于前一個子任務，移動終端在同一時刻只能有一個子任務進行處理；當子任務傳輸到移動邊緣計算服務器時，多個子任務可以并行執行。下面假設為一個任務可以切分為5個子任務，只有切片間依賴關系不同，執行位置相同，用來闡述依賴關系對執行時延的影響，如圖2所示。

圖2 子任務之間的依賴關系

圖3 子任務的執行時延

子任務之間的依賴關系對任務執行時延的影響如圖3所示。假設子任務T2在移動邊緣計算服務器上執行，子任務T1、T3、T4和T5在本地執行；假設每個子任務執行的時延相同，每個操作都占用一個時延片單位，任務的執行和上傳以及下載都占用一個時延片單位。當子任務T1和T2之間存在依賴關系時，只有執行完子任務T1，才能上傳T2；反之，當子任務T1和T2之間不存在依賴關系時，可以在執行子任務T1時，將T2上傳到MEC服務器上進行處理。任務T1比任務T2執行時延多一個時延片。

免疫優化算法求解問題時，把待求解的問題抽象為抗原，把問題的候選解抽象為抗體，通過在編碼空間中進行啟發式搜索來尋找最優抗體，解碼最優抗體輸出問題的最優解。文中對子任務執行的位置采用二進制編碼方式，使用抗體X={x1，x2，…，xi，…，xN}表示子任務的調度結果的位置，其中，xi表示第i個子任務是否卸載到移動邊緣計算服務器上進行執行，當xi=0時，表示該子任務在移動終端上執行；當xi=1時，表示移動終端需要將子任務卸載到移動邊緣計算服務器上執行。

2.2 初始化

初始化模型的參數，如邊緣設備和移動終端的計算能力、計算功率和傳輸速率等；初始化任務相關的矩陣，如各個子任務的計算量的大小、任務計算所需要上傳的數據量、各個子任務之間的依賴關系和子任務執行位置的矩陣；初始化免疫算法的一些基本參數，如種群規模、變異概率、激勵度系數、相似度閾值等；隨機產生若干個抗體，對抗體種群進行初始化。

2.3 抗體親和度評價函數

在免疫算法中，親和度表征抗體與抗原的結合強度，與遺傳算法中的適應度相對應。親和度算子通常是表示為函數的形式，如f(X)，在文中采用的親和度評價函數為

(9)

其中，X是抗體(問題的候選解)。

2.4 變異算子

對抗體采用二進制編碼，對抗體進行變異操作的方法是對抗體的某一位進行隨機取反，具體操作如圖4所示。使用變異算子對得到的抗體方案進行變異操作，以增加抗體種群的多樣性，實現局部范圍內搜索。

圖4 子任務計算位置變異操作

2.5 抗體濃度評價算子

抗體濃度的大小可以表示抗體種群多樣性的好壞。當某種抗體濃度過高時，就說明抗體種群中的抗體趨于過度集中，可能會出現局部最優化，降低全局搜索能力。因此需要對濃度過高的抗體進行抑制，保證抗體種群的多樣性。抗體濃度計算公式為

(10)

其中，den(Xi)為種群的抗體濃度；N為種群中的抗體個數；S(Xi，Xj)代表兩個抗體之間的相似度，其表達式為

(11)

其中，δ表示相似度閾值，aff(Xi，Xj)是抗體之間的親和度函數。采用海明距離作為抗體間親和度的計算函數，

(12)

(13)

其中，xi，k和xj，k分別表示為抗體i和抗體j的第k個決策變量；N表示任務可切分的子任務的總數。

2.6 激勵度算子

對抗體的質量進行評價需要綜合考慮抗體的親和度和抗體濃度兩個方面。通過對激勵度的排序，選出前N/2個抗體進行變異和克隆抑制等免疫操作。在一般情況下，親和度較大而濃度較低的抗體應該具有較高的激勵度。激勵度函數計算公式為

sim(Xi)=αaff(Xi)-βd(Xi)，

(14)

其中，sim(Xi)代表方案Xi的激勵度；α，β分別代表抗體親和度和抗體濃度的權重系數。在文中令α=2，β=1。

2.7 求解任務卸載的免疫算法流程

(1) 初始化模型的參數，如邊緣服務器的計算資源和計算能力、移動終端的計算能力、計算功率和傳輸速率等；

(2) 初始化任務相關的矩陣，如各個子任務的計算量、需要上傳的數據量、下載的數據量、需要的計算資源、各個子任務之間的依賴關系和子任務執行位置的矩陣；

(3) 初始化免疫算法的一些基本參數，如種群規模、變異概率、激勵度系數、相似度閾值等；

(4) 對抗體種群進行初始化；

(5) 進行抗體濃度、抗體間親和度和抗體激勵度的計算；

(6) 根據抗體激勵度對抗體進行按升序排列；

(7) 選取前N/2個抗體進行變異和克隆抑制等免疫操作，生成新的種群；

(8) 計算新生成種群的激勵度，將新的種群與免疫種群進行合并，更新種群；

(9) 判斷是否滿足循環結束條件，如果是，則結束循環，對抗體種群中的最優抗體進行解碼，輸出最優的任務卸載方案；否則返回步驟(5)。

3 仿真實驗及分析

采用Matlab軟件進行系統仿真，其中，每個子任務的計算量在[1，100]區間上隨機生成；每個子任務上傳和下載數據量在[1，25]區間上隨機生成；移動終端的計算能力、計算功率、數據上行功率與速率、數據下行功率與速率以及移動邊緣計算服務器計算能力等，如表1所示。

表1 移動終端和MEC服務器性能參數

把基于免疫算法(IA)的方案，與文獻中基于遺傳算法(Genetic Algorithm，GA)的方案和基于LOCAL Execution(LOCALE)的方案進行對比實驗。基于GA的方案對子任務的執行位置使用遺傳算法進行計算處理，不考慮子任務之間依賴關系。基于LOCALE的方案將所有任務都放在移動終端上進行處理計算。免疫算法的種群規模N=50；GA算法和LOCALE算法設置的初始候選解的個數均為50個；隨機工作流的子任務數為50。

把任務時延和終端能耗的加權和作為執行任務的綜合代價，在相同的條件下，比較IA方案、GA方案和LOCALE方案的綜合代價。下面從子任務數量變化、子任務執行時所需要的上傳和下載的數據量的變化、子任務計算量的變化、權重系數變化等方面進行對比實驗。

3.1 子任務數量變化對綜合代價的影響

觀察圖5可知：隨著子任務數量的不斷增加，綜合代價明顯增加。這是因為計算量的增加，必然導致執行任務會消耗更多的時延和能量。通過對比不同卸載方案可以發現，當任務數量較小時，3種方案的綜合代價相差不大，但隨著任務量的增加，筆者提出方案的綜合代價增長緩慢，優于GA方案和LOCALE方案。

3.2 傳輸數據量(Din+Dout)變化對綜合代價的影響

考察綜合代價隨數據傳輸量(數據上傳)的變化情況，將數據傳輸量取值區間限定在5個區間，3種方案的綜合代價(ω=0.5，時延和能耗同等重要)隨數據傳輸量增加的變化情況如圖6所示。

從圖6可以看出：隨著傳輸數據量的增加，3種方案的綜合代價都在增加；LOCALE方案是本地執行，系統時延主要與計算量有關，與傳輸數據量關聯度很小，所以系統時延和終端能耗加權和生成的綜合代價與傳輸數據量關聯度不大；在相同的數據量區間，IA方案比GA方案具有更小的綜合代價，但是相差較小。

圖5 綜合代價隨子任務數量增加變化情況

圖6 綜合代價隨傳輸數據量增加的變化情況

3.3 計算量變化對綜合代價的影響

考察綜合代價隨計算量的變化情況，將計算量取值區間限定在5個區間，3種方案的綜合代價(ω=0.5，時延和能耗同等重要)隨計算量增加的變化情況如圖7所示。

從圖7可以看出：LOCALE方案是本地執行，隨著計算量的增加，其綜合代價增幅最大，綜合代價與計算量呈正相關；GA方案和IA方案增幅緩慢，明顯優于LOCALE方案；在相同的計算量區間，IA方案略優于GA方案，但是相差較小。

3.4 權重系數(ω)對綜合代價的影響

考察綜合代價隨權重系數的變化情況，將權重系數(ω)分別取0.3、0.4、0.6、0.7，3種方案的綜合代價隨權重系數的變化情況如圖8所示。

圖8比較了4種不同權重狀態下的綜合代價平均值，可以看出權重對每種方案都有所影響。在每種權重下，筆者所提方案均不輸于其他的方案。但是隨著權重的增加，筆者所提方案在保持優勢的情況下，具有最小的波動，受權重的影響比較小。

圖7 綜合代價隨計算量增加的變化情況

圖8 權重系數對綜合代價的影響

3.5 單獨考察系統時延和終端能耗

為了進一步比較3種方案，單獨考察系統時延和終端能耗隨子任務數量變化情況。圖9展示了僅考察系統時延(ω=1)時，3種方案的時延隨子任務數量的變化情況。

從圖9可以看出：LOCALE方案在本地執行，隨著子任務的增多，系統時延增長很快；文中方案通過優化卸載策略，在系統時延性能上表現優于GA方案和LOCALE方案。

圖10展示了僅考察終端能耗(ω=0)時，3種方案的能耗隨子任務數量的變化情況。

從圖10可以看出：LOCALE方案在本地執行，隨著子任務的增多，終端能耗增長很快；文中方案在終端能耗性能上略遜色于GA方案，原因是文中方案側重于把子任務卸載到MEC服務器，數據上傳和下載產生了較多的能耗。

圖9 子任務數量對系統時延的影響

圖10 子任務數量對終端功率的影響

4 結束語

筆者研究了移動邊緣計算場景下單個移動終端任務可切分的卸載問題，綜合考慮系統時延和移動終端能耗，把移動終端的計算任務進行切分，設計了任務卸載優化模型，并用免疫優化算法求解該模型。仿真實驗表明，與本地執行(不進行卸載)方案和基于遺傳算法的卸載方案相比，筆者提出的基于免疫算法的卸載方案具有更好的性能，具有較好的應用價值。

下一步工作，將研究存在多個移動終端、多個邊緣服務器、邊緣計算場景下多約束(如：時延約束、移動終端能耗約束等)條件下的任務卸載問題。