基于蟻群算法的移動邊緣服務器收益優化策略

黃冬艷 付中衛 李 浪

(桂林電子科技大學廣西無線寬帶通信與信號處理重點實驗室 廣西 桂林 541004)

0 引 言

隨著5G網絡的普及，依靠其衍生出來的新型應用，如車聯網、遠程醫療、虛擬現實、增強現實等得到快速發展。但由于移動設備和物聯網設備計算能力和電池容量受限，這些新型應用和服務難以部署。為了解決這個問題，近年來研究人員提出了移動邊緣計算[1]。

在移動邊緣計算的架構中，邊緣計算服務提供商在無線接入網邊緣為移動設備提供云計算能力[2]，從而創造出一個具備高性能、低延遲與高帶寬的電信級服務環境。用戶通過將應用程序的計算任務卸載到邊緣服務器端進行計算，可實現超低計算延遲。

在移動終端進行計算任務卸載時，為實現如能耗、延遲等性能的優化，需要判斷是否將計算任務全部或部分卸載至邊緣服務器執行，這被稱為計算分區問題[3]。很多文獻以移動設備的能耗[4]、應用延遲[5-7]和網絡上的數據傳輸量等因素中的一個或多個的組合作為優化目標，提出了不同的計算分區問題模型。

在文獻[4]中，為使設備能耗或任務延遲達到最小，作者分別提出了能耗最小、延遲最小的卸載算法，對移動設備的計算資源、傳輸功率和任務卸載比例進行聯合優化。文獻[5]在雙時間尺度的情況下，采用馬爾可夫決策過程方法，提出一個一維搜索算法，搜索出最優調度策略，實現了在設備能耗約束下的計算延遲最小化。文獻[8]以用戶的QoE作為優化目標，提出一個近似動態規劃算法，找出任務最佳卸載策略。

然而，文獻[4-5，8]主要研究用戶獨立模型下的計算分區問題，只針對單個用戶進行計算分區，而不考慮其他用戶的分區結果。在實際過程中，通常會出現多個用戶共同占用邊緣服務器計算資源的現象。由于移動邊緣服務器計算資源受限，不能同時接受多個用戶的卸載請求，因此多用戶分區問題也是移動邊緣計算的研究熱點。

文獻[3]考慮了如SIFT算法這類子任務執行關聯性的情況下，多用戶計算任務的劃分以及云計算資源的調度，根據云服務器的資源占用情況，提出了SearchAdjust算法來解決多用戶分區問題，使得用戶的平均完成時間最小化。文獻[6]考慮了如何對延遲敏感型應用計算分區和對移動邊緣服務器資源分配，使得用戶整體延遲達到最小。為解決該問題，設計了一種多維搜索和調整算法(MDSA)。文獻[7]研究了多用戶的網絡感知環境下，通過對用戶任務的計算分區和邊緣服務器的帶寬資源分配，使用戶的平均吞吐量(應用程序每秒處理的數據單元數)最大化。

以上文獻主要考慮通過計算分區技術使得用戶獲得最大的收益(如最小化計算延遲或能耗)。事實上，為了收回設備的部署和維護成本并盈利，MEC服務提供商如何利用有限的計算資源來最大化其利潤，也是一個亟待解決的問題，但是以MEC服務器收益為優化目標的研究較為少見。

本文研究多個用戶對邊緣服務器端計算資源存在競爭且每個用戶會在本地做出最小化自身成本(計算延遲和花費加權和)的卸載決策的情況下，MEC服務器提供商通過采用合適的資源分配策略實現其收益(利潤)的最大化。本文的主要貢獻如下：1) 在用戶子任務具有順序執行的關聯性及用戶之間對金錢和延遲的偏好程度不同的場景下，建立以服務器端任務執行次序為變量的服務器收益最大化模型；2) 提出基于蟻群算法求解任務最佳分區及服務器端任務最佳執行次序的算法。

1 系統模型及問題建模

1.1 系統模型

為了獲得更好的用戶體驗，當執行某些延遲敏感型應用時，如無人駕駛、增強現實、人臉識別等，用戶會將程序中的某些進程卸載至云端執行以獲得更小的計算延遲。

如圖1所示，考慮多個計算密集型任務占用單個MEC服務器的重業務場景，然后建立多用戶MEC系統模型。該MEC系統由兩部分組成：移動邊緣服務器和移動客戶端。任務卸載具體流程如圖2所示。在移動客戶端處，客戶端中間件的監視代理程序收集設備的計算能力、任務大小等信息，當用戶向邊緣服務器發送卸載請求時，這些信息隨請求一起發送到邊緣服務器端，服務器端在接收到用戶的請求后，將空閑計算資源分配給請求用戶并為請求卸載任務進行執行排序，然后將資源分配信息反饋至終端設備，終端設備在本地做出最小化自身成本的卸載決策。本文中的符號和含義如表1所示。

圖1 多用戶MEC系統

圖2 MEC系統任務卸載流程

表1 符號及其含義

(1)

本地計算花費為：

(2)

令xi,j=1表示任務(i,j)在服務器端計算，其計算時間為：

(3)

(4)

任務(i,j)在服務器端計算花費為：

(5)

為保證任務之間的執行順序，令z(i,j),(i′,j′)=1表示任務(i,j)在任務(i′,j′)前執行，z(i,j),(i′,j′)=0表示任務(i′,j′)在(i,j)前執行。

1.2 問題建模

(6)

IN×(2-xs(o)-xs(k)),k≠o,1≤o≤K；

式中：約束條件C1保證單個用戶各個子任務間執行順序；約束條件C2保證兩個不同用戶子任務的服務器端執行次序；IN表示正無窮大的數；約束條件C3保證卸載任務在服務器端執行時開銷小于在本地執行開銷；約束條件C4限制卸載變量xs(k)取值0或1，保證子任務的本地計算時間、服務器端等待時間、服務器端計算時間大于0；約束條件C5保證在邊緣服務器端閑置的時候，卸載至邊緣服務器端的計算花費要小于本地計算花費。

2 算法設計

為求解問題P1，需要在K個任務的K!個排列集合中，找出令邊緣服務器端獲得最大收益的一個排列，因此問題P1為組合優化問題[10]。解決該類問題可以使用啟發式算法、近似算法和枚舉法。當問題規模較大時，枚舉法求解時間過長，近似算法難以找出精確解，因此本文采用啟發式算法中具有較強的全局尋優能力和較強的魯棒性的蟻群算法[11]尋找多個請求卸載任務的最佳執行次序。本文算法流程如圖3所示。

圖3 本文算法流程

本文算法具體步驟：

1) 計算在服務器端資源未被占用時，各個任務的子任務最佳分區決策。

2) 計算服務器資源占用列表Lcro。

3) 從Lcro中搜索服務器端的沖突的任務集合Lcon，其搜索步驟為：

(1) 搜索在Lcro中，最先在服務器端完成任務。

(2) 搜素出與此任務在服務器端執行時間相互沖突的任務。

(3) 將此任務與其沖突的任務放在集合Lcon中。

4) 應用蟻群算法搜索出Lcon中沖突任務執行的最佳次序，其執行步驟為：

(1) 對相關參數進行初始化，信息啟發式因子α=1、期望啟發因子β=5、信息素揮發系數ρ=0.1、信息素強度Q=100、最大迭代次數N=500、螞蟻個數為Lcon中沖突任務個數m。

(4) 當所有螞蟻經過一輪路徑選擇后，對路徑上的信息素濃度進行更新。

(5) 判斷是否達到最大迭代次數N，若否，返回步驟(3)繼續循環；若是，結束蟻群算法程序循環，輸出沖突任務Lcon最終執行次序Scon及其收益。

6) 服務器端任務執行次序S中所包含的任務為卸載計算任務，剩余任務為本地計算任務，得到各用戶的分區策略。

算法步驟2)中所述的云端資源占用列表Lcro為包含每個用戶子任務在云端的開始時刻和完成時刻。

算法步驟4)中螞蟻k隨機選擇下一任務的概率：

(7)

式中：τi1j1,i2j2(t)為邊(i1j1,i2j2)上的信息素；ηi1j1,i2j2(t)為啟發式函數，alloweCk為螞蟻k待訪問的任務集合。

啟發式函數ηi1j1,i2j2(t)的更新規則為：

ηi1j1,i2j2(t)=revenuei1j1,i2j2/max(revenue)

(8)

式中：revenue為各個子任務需交付費用集合；

步驟4)中，m只螞蟻完成一次循環后，各個任務連接路徑上的信息濃度更新為：

τi1j1,i2j2(t+1)=(1-ρ)×τi1j1,i2j2(t)+Δτi1j1,i2j2(t)

(9)

式中：Δτi1j1,i2j2(t)為所有螞蟻在子任務(i1,j1)與子任務(i2,j2)連接路徑上釋放信息素而增加的信息素濃度。Δτi1j1,i2j2(t)的計算為：

(10)

(11)

3 仿真結果及分析

假設每個用戶有5個待卸載子任務，子任務之間存在順序執行的關聯性；服務器端有兩個收費標準可供用戶選擇，每個用戶從兩個收費標準中隨機選擇一個。參照文獻[12-13]，具體參數設置如下：向服務器端發送請求的用戶總數在[5，90]范圍內；兩收費標準分別為(CPU的單個時鐘周期內)u0=1×10-9元,u1=0.5×10-9元，每個子任務所需要的CPU周期在0.1～1 GHz隨機取值，每個設備的計算能力在1～2 GHz隨機取值。然后，對SearchAdjust算法改進，使得其優化目標函數為邊緣服務器收益，在相同參數下對改進的SearchAdjus[3]算法與本文算法進行仿真對比。

仿真時，設置蟻群的數量為沖突任務的個數大小、迭代的最大次數為500，信息啟發式因子為1，期望啟發因子為5，信息素揮發系數為0.1，信息素強度為100，使用MATLAB R2012a版進行仿真。

圖4比較了在邊緣服務器計算能力為fc=4 GHz和fc=12 GHz的條件下，本文算法與基準算法的邊緣服務器收益。從仿真圖可得，兩種算法所獲得的收益都隨著用戶的增多而增多，但本文算法的收益增速要大于基準算法。當用戶數目為90、fc=4 GHz時，本文算法的收益相比基準算法提高了33.6%；當用戶數目為90、fc=12 GHz時，本文算法的收益相比基準算法提高了49.9%。這是因為隨著計算能力的提高，相比較SearchAdjust算法，本文算法在各任務可容忍執行期限內可以處理更多的任務。

圖4 不同算法的MEC服務器收益對比

圖5比較了在邊緣服務器計算能力fc=4 GHz和fc=12 GHz的條件下，本文算法與基準算法在用戶數目不同的情況下的每用戶平均延遲。從仿真圖中可得，兩種算法中每用戶平均延遲都隨著用戶增多而增多。當用戶數目為90、fc=4 GHz時，本文算法的每用戶平均延遲相比基準算法增加1.6%；當用戶數目為90、fc=12 GHz時，本文算法的每用戶平均延遲相比基準算法增加了6%。結合圖4，可以得出本文算法是以犧牲較低的用戶的平均延遲為代價，極大提高了MEC服務器的收益。

圖5 兩種算法每用戶平均計算延遲

4 結 語

本文研究了5G網絡中移動邊緣計算的多用戶分區問題，以最大化MEC服務器收益為優化目標，提出基于蟻群算法求解服務器端任務最佳執行次序的算法，以獲得最優的任務分區策略和最佳任務執行次序。仿真結果表明，在用戶子任務具有順序執行的關聯性及用戶之間對金錢和延遲的偏好程度不同的場景下，本文算法能夠明顯提高MEC服務器的平均收益。下一步工作將在多個邊緣服務器相互協作的場景下，研究用戶QoE約束下的多個邊緣服務器的收益最大化策略。