融合虛擬機分簇與休眠機制的MEC任務卸載策略

王 穎，李 偉，陳夢盼，陳 利，金順福,*

(1. 燕山大學 信息科學與工程學院，河北 秦皇島 066004；2. 燕山大學 里仁學院，河北 秦皇島 066004)

0 引言

隨著科技的進步，大量能源密集型和計算密集型的應用程序應運而生[1]。然而，每個移動設備本地的計算資源和存儲容量等有限，傳統的云計算[2]又因高延時及低安全性等缺陷不能滿足網絡用戶需求，移動邊緣計算(Mobile edge computing，MEC)[3]的概念應運而生。面向MEC的任務卸載策略成為該領域關注的焦點。

提高應用程序的響應性能是保證網絡用戶服務質量的重要因素，部分文獻中的任務卸載策略側重于減少任務平均延時。Tang等人[4]提出了一種基于MEC的充放電聯網系統，利用一種求解整數變量的啟發式算法，分析各變量的凸性，以實現充電站等待時間的最小化。Yu等人[5]提出了一種緩存增強的計算卸載問題，基于協作調用圖平衡卸載與緩存之間的關系，最小化移動終端的執行延時。Zhang等人[6]提出了一種分層卸載框架，采用斯塔克爾伯格博弈方法設計了一種多層卸載方案，使用迭代分布算法得到了最優的卸載策略，在保證計算延時的同時最大化收益。這些任務卸載策略的研究忽略了MEC中的能耗水平。

立足于綠色MEC的建立，部分文獻中的任務卸載策略研究專注于減少系統能量消耗的技術。Xu等人[7]提出了一種用于eNodeB緩存的能量消耗模型，使用線性規劃方法分析系統能耗水平，采用拉格朗日對偶分解技術最小化系統能量消耗。Gu等人[8]研究了虛擬機遷移，任務分配及能量調度問題，提出了一種離散時間槽調度優化模型，利用一種基于松弛的啟發式算法，實現能量消耗的最小化。Mehamel等人[9]提出了一種高效能的邊緣設備模糊緩存技術，利用現場可編程邏輯門陣列實現邊緣緩存的模糊決策，以降低邊緣緩存的能耗。這些研究忽略了響應性能對網絡用戶服務質量的影響。

本文基于多用戶應用環境，綜合考慮響應性能及節能水平，研究MEC任務卸載策略。系統中主模塊持續活躍以提高網絡用戶的響應速度，備用模塊中引入休眠機制以實現節能的目的。根據主模塊及備用模塊中的任務數量以及備用模塊虛擬機的狀態，使用擬生滅過程與矩陣幾何解方法進行穩態解析。構建系統成本函數，改進鴿群算法，研究任務卸載策略的參數優化問題。

1 MEC任務卸載策略及系統模型

1.1 MEC任務卸載策略

隨著計算機技術與通信技術的不斷發展，移動設備的計算能力不斷增強，但依然存在短時間內消耗大量資源的問題。云計算因傳輸距離遠等問題，又會造成不可預測的延時[10]。兼顧響應性能及節能水平，融合虛擬機分簇與休眠機制，面向MEC服務器提出一種任務卸載策略，如圖1所示。

圖1 MEC系統任務卸載Fig.1 Task offloading in MEC system

1) 考慮移動設備在計算性能和資源存儲等方面存在的不足，一定比例的任務在移動設備本地執行，而剩余的任務則可以卸載到MEC服務器上接受服務。采用虛擬機分簇技術，在MEC服務器中設置時刻保持活躍的主模塊及在活躍狀態與休眠狀態之間自適應切換的備用模塊。

2) 主模塊虛擬機持續活躍，可以隨時為到達系統的任務提供服務。卸載到MEC服務器上的任務，首選進入緩存容量有限的主模塊。若主模塊中存在空閑虛擬機，新到達的任務立即接受服務。否則，將嘗試進入緩存隊列中排隊等待。若主模塊中的可用容量為零，新到達的任務將進入緩存容量無限的備用模塊中。

3) 備用模塊中的虛擬機在活躍狀態與休眠狀態之間自適應切換。當備用模塊虛擬機中的所有任務服務完畢后，若緩存隊列中沒有等待的任務，立即啟動休眠定時器，全部虛擬機同時進入第一個休眠期。一旦備用模塊虛擬機處于休眠狀態，新到達的任務只能進入緩存隊列中等待。一個休眠期結束后，若緩存隊列中沒有等待的任務，則全部備用模塊虛擬機同時開始下一個休眠期；否則，關閉休眠定時器并進入活躍狀態，依次服務等待在緩存隊列中的任務。

1.2 系統模型

將t時刻備用模塊中的任務總數稱為t時刻的系統水平，表示為N(t)=i(i=0,1,…)。將t時刻主模塊中的任務總數稱為t時刻的系統階段，表示為L(t)=j(j=0,1,…,c1+H)。將t時刻備用模塊虛擬機所處的狀態稱為t時刻的系統相位，表示為J(t)=k(k=0,1)，其中k=0,1分別表示備用模塊虛擬機處于休眠狀態和活躍狀態。{(N(t),L(t),J(t),t≥0)}構成一個三維連續時間馬爾科夫鏈[11]，其狀態空間Ω表示為

Ω={(i,j,k)|i=0,1,…,j=0,1,…,c1+H,k=0,1}。

令πi,j,k表示穩態下系統水平為i，系統階段j及系統相位為k的概率分布。πi,j,k表示為

令πi(i≥0)表示穩態下系統水平為i的概率向量，則馬爾科夫鏈{(N(t),L(t),J(t)),t>0}的穩態概率分布Π表示為

Π=(π0,π1,…)。

2 系統模型的穩態解析

馬爾科夫鏈{(N(t),L(t),J(t)),t>0}的轉移率矩陣表示為Q，系統水平從i(i=0,1,…)跳轉到i′(i′=0,1,…)的轉移率子陣表示為Qi,i′[12]。為了描述方便，引入符號Iu(u≥1)，表示u×u維單位陣。

1)Qi,i-1為系統水平由i減少到i-1的轉移率子陣。

當i=1時，備用模塊虛擬機既可能休眠也可能活躍。只有在備用模塊虛擬機處于活躍狀態的條件下，當其上的虛擬機服務完成一個任務后，系統水平才可能下降到0，此時，虛擬機進入休眠狀態，一步轉移率為μ2。

Q1,0為(2c1+2H+2)×(c1+H+1)階矩陣，表示為

當i≥2時，備用模塊虛擬機既可能休眠也可能活躍。只有在備用模塊虛擬機處于活躍狀態的條件下，當虛擬機服務完成一個任務后，系統水平才可能下降到i-1，此時，虛擬機仍保持在活躍狀態。在2≤i≤c2和i≥c2+1的情況下，一步轉移率分別為iμ2與c2μ2。

Qi,i-1為(2c1+2H+2)×(2c1+2H+2)階方陣。

若2≤i≤c2，Qi,i-1表示為

若i≥c2+1，Qi,i-1表示為

2)Qi,i為系統水平保持不變的轉移率子陣。

當i=0時，備用模塊中的虛擬機一定處于休眠狀態，只需分析主模塊的變化規律。當主模塊中到達一個任務時，一步轉移率為nλ(1-p)。當1≤j≤c1時，若主模塊服務完成一個任務，一步轉移率為jμ1；若主模塊中既無任務到達也無任務離去，一步轉移率為-nλ(1-p)-jμ1。當c1+1≤j≤c1+H時，若主模塊服務完成一個任務，一步轉移率為c1μ1；若主模塊中既無任務到達也無任務離去，一步轉移率為-nλ(1-p)-c1μ1。

Q0,0為(c1+H+1)×(c1+H+1)階方陣，表示為

當i≥1時，備用模塊中的虛擬機處于休眠狀態或者活躍狀態。當1≤j≤c1時，若主模塊服務完成一個任務，一步轉移率為jμ1；當c1+1≤j≤c1+H時，若主模塊服務完成一個任務，一步轉移率為c1μ1。為了描述方便，引入二階方陣αj,j-1。

若1≤j≤c1，αj,j-1表示為

αj,j-1=I2?jμ1，

若c1+1≤j≤c1+H，αj,j-1表示為

αj,j-1=I2?c1μ1。

當備用模塊虛擬機處于休眠狀態時，若休眠定時器到期，一步轉移率為θ；若主模塊中無任務到達，無任務離去，休眠定時器未到期，在0≤j≤c1和c1+1≤j≤c1+H的情況下，一步轉移率分別為-nλ(1-p)-jμ1-θ與-nλ(1-p)-c1μ1-θ。當備用模塊虛擬機處于活躍狀態且主模塊中無任務到達，無任務離去，備用模塊中無任務離去時，若1≤i≤c2，在0≤j≤c1和c1+1≤j≤c1+H的情況下，一步轉移率分別為-nλ(1-p)-jμ1-iμ2與-nλ(1-p)-c1μ1-iμ2；若i≥c2+1，在0≤j≤c1和c1+1≤j≤c1+H的情況下，一步轉移率分別為-nλ(1-p)-jμ1-c2μ2與-nλ(1-p)-c1μ1-c2μ2。為了描述方便，引入二階方陣βj,j。

若1≤i≤c2, 0≤j≤c1，βj,j表示為

若i≥c2+1, 0≤j≤c1，βj,j表示為

若1≤i≤c2,c1+1≤j≤c1+H，βj,j表示為

若i≥c2+1,c1+1≤j≤c1+H，βj,j表示為

當主模塊中到達一個任務時，一步轉移率為nλ(1-p)。

Qi,i為(2×c1+2×H+2)×(2×c1+2×H+2)階方陣，表示為

其中，γj,j+1=I2?nλ(1-p)。

3)Qi,i+1為系統水平由i增加到i+1的轉移率子陣。

當i=0時，備用模塊中的虛擬機一定處于休眠狀態。當主模塊中的可用容量為零時，新到達的任務進入備用模塊，備用模塊虛擬機仍處于休眠狀態，一步轉移率為nλ(1-p)。

Q0,1為(c1+H+1)×(2c1+2H+2)階矩陣，表示為

當i≥1時，備用模塊中的虛擬機處于休眠狀態或者活躍狀態。當主模塊中的可用容量為零時，新到達的任務進入備用模塊，此時，備用模塊虛擬機保持在原狀態，一步轉移率為nλ(1-p)。

Qi,i+1為(2c1+2H+2)×(2c1+2H+2)階方陣，表示為

由以上分析可知，轉移率子陣Qi,i-1及Qi,i從系統水平c2開始重復，Qi,i+1從系統水平1開始重復。令Bi=Qi,i-1(1≤i≤c2-1)，B=Qi,i-1(i≥c2)，Ai=Qi,i(0≤i≤c2-1)，A=Qi,i(i≥c2)，C0=Q0,1及C=Qi,i+1(i≥1)?？蓪⑷S連續時間馬爾科夫鏈{(N(t),L(t),J(t)),t≥0}的轉移率陣Q表示為

轉移率陣Q中的狀態轉移只發生在相鄰系統水平之間，因此，三維連續時間馬爾科夫鏈{(N(t),L(t),J(t)),t≥0}是一種擬生滅過程[13]。該過程正常返的條件之一是矩陣方程R2B+RA+C=0的最小非負解R的譜半徑小于1。

構造矩陣B[R]如下

由系統穩態方程及歸一化約束條件[14]得出方程組如下

(1)

其中，e為(c1+H+1)+2(c2-1)(c1+H+1)階全1列向量，e1為2c1+2H+2階全1列向量。

運用高斯—賽德爾迭代法，求解方程組(1)，可得π0,π1,…,πc2的數值解，利用矩陣幾何解形式πk=πc2Rk-c2,k≥c2+1進一步得到πk(k≥c2+1)的數值解。

3 性能指標與系統實驗

3.1 性能指標

任務平均延時及系統節能率是評估MEC任務卸載策略的兩個重要指標。

任務平均延時定義為任務從進入系統直到離開系統平均消耗的時間，即平均等待時間與服務時間的和。

任務在本地處理器接受服務的平均延時E[T0]為

(2)

卸載到MEC服務器上的任務首選進入緩存容量有限的主模塊。若主模塊中的任務數超過主模塊中的虛擬機數，新到達的任務嘗試進入緩存容量有限的隊列中等待。在主模塊中接受服務的任務平均延時E[T1]為

(3)

若主模塊中的可用容量為零時，新到達的任務將進入緩存容量無限的備用模塊中。在備用模塊中接受服務的任務平均延時E[T2]為

(4)

每個移動設備產生的任務以概率p在本地處理器接受服務，以概率1-p在MEC服務器上接受服務。結合式(2)～(4)給出任務平均延時E[T]為

E[T]=pE[T0]+(1-p)((1-πc1+H)E[T1]+πc1+HE[T2])。

(5)

系統節能率S定義為單位時間內備用模塊虛擬機處在休眠狀態所節省的能量。令ω為空閑狀態下備用模塊的運行功率，ω0為休眠狀態下備用模塊的運行功率。備用模塊在休眠狀態的運行功率低于空閑狀態下的運行功率，即ω>ω0。在所提出的MEC任務卸載策略中，能量節省產生于備用模塊虛擬機的休眠狀態。系統節能率S為

(6)

3.2 系統實驗

為了驗證MEC任務卸載策略的有效性，進行數值實驗與仿真實驗，在不同的任務到達率下，刻畫本地分配概率對系統性能的影響。

基于MATLAB 2016a進行數值實驗，揭示任務平均延時與系統節能率的變化趨勢，驗證MEC任務卸載策略的有效性。在Eclipse 2019環境下進行仿真實驗，使用Java語言模擬200 000個任務的到達與離去過程，驗證系統建模的合理性與模型解析的準確性。

基于數學理論分析的數值實驗獲得的是樣本空間為無窮大時的極限結果。該結果的準確性與所采用高斯—賽德爾迭代法求解方程組的精度有關?；跈C理模型的仿真實驗獲得的是樣本空間有限條件下的統計結果。該結果的準確性與樣本空間的大小有關。

參考文獻[12]，同時考慮系統穩定條件，設置實驗所用系統參數如表1所示。

表1 系統參數Tab.1 System parameters

圖2刻畫了卸載策略下任務平均延時E[T]的變化趨勢。

圖2 任務平均延時隨任務到達率λ及本地分配概率p的變化趨勢Fig.2 Average delay of tasks versus arrival rate of tasks and local allocation probability

固定任務到達率λ觀察圖2，在本地分配概率p從0.05變化到0.95的過程中，任務平均延時E[T]先呈現出下降趨勢，在任務平均延時E[T]到達最低點之后，又呈現出上升趨勢。當本地分配概率較小時，大多數的任務卸載到MEC服務器，隨著本地分配概率逐漸變大，去往本地的任務數量逐漸變多，緩解了MEC服務器的負載壓力，任務平均延時減小。當本地分配概率較大時，大多數的任務去往本地，隨著本地分配概率逐漸變大，一方面，本地負載壓力變大，使得任務平均延時增大；另一方面，MEC服務器因頻繁休眠，服務能力減弱，也使得任務平均延時增大。

固定本地分配概率p觀察圖2，任務平均延時E[T]的變化趨勢與本地分配概率p相關。當本地分配概率較小時，大多數的任務卸載到MEC服務器，隨著任務到達率的逐漸變大，卸載到MEC服務器上的任務數量逐漸變多，降低了MEC服務器的休眠機會，增強了MEC服務器的服務能力，任務平均延時反而減小了。當本地分配概率較大時，隨著任務到達率的逐漸變大，本地和MEC服務器的負載壓力變大，使得任務平均延時增大。

圖3刻畫了卸載策略下系統節能率S的變化趨勢。

圖3 系統節能率隨任務到達率λ及本地分配概率p的變化趨勢Fig.3 Energy saving rate of system versus arrival rate of tasks and local allocationprobability

固定任務到達率λ觀察圖3，在本地分配概率p從0.05變化到0.95的過程中，系統節能率S呈現先上升后不變的趨勢。當本地分配概率逐漸變大時，卸載到MEC服務器上的任務數量變少，提高了MEC服務器的休眠機會，因此，系統節能率增大。當本地分配概率增大到一定程度時，只有少數任務卸載到MEC服務器，備用模塊虛擬機幾乎一直休眠，系統節能率達到極限。

固定本地分配概率p觀察圖3，系統節能率S的變化趨勢與本地分配概率p相關。當本地分配概率較小時，大多數的任務卸載到MEC服務器，隨著任務到達率的增大，MEC服務器的休眠機會降低，因此，系統節能率減小。當本地分配概率較大時，只有極少數的任務卸載到MEC服務器，即使任務到達率增大，也很難將備用模塊虛擬機由休眠狀態喚醒至活躍狀態，因此，系統節能率不變。

由上述分析可知，任務到達率及本地分配概率對任務平均延時和系統節能率有很大影響。對于給定的任務到達率，合理設置本地分配概率，能夠實現響應性能與節能水平的合理均衡。

4 策略參數優化

只研究任務平均延時或者系統節能率，難以給出最優的MEC任務卸載策略[15]。令任務平均延時的影響因子為η1，系統節能率的影響因子為η2，構造成本函數F(p)如下

F(p)=η1(E[T])2-η2S。

傳統的鴿群算法[16]容易陷入局部最優。為了改善這一問題，提出一種融合“教與學”過程的改進的鴿群算法?；凇敖膛c學”過程能夠引導鴿群的飛行方向，改善候選解的質量，避免陷入局部最優。使用改進的鴿群算法，以成本最小為目標，優化本地分配概率。改進的算法步驟如下：

Step 1:初始化鴿群位置(本地分配概率)的左邊界pmin與右邊界pmax，鴿群數量X，地圖和指南針算子的最大迭代次數Y1，地標算子的最大迭代次數Y2，指南針因子φ。設地圖和指南針算子的當前迭代次數t1=1，地標算子的當前迭代次數t2=1。

Step 2:在鴿群位置的約束范圍[pmin,pmax]內，初始化鴿群速度vi(i=1,2,…,X)，計算鴿群位置pi(i=1,2,…,X)。

vi=rand；%rand表示取0到1之間的隨機數

pi=pmin+vi×(pmax-pmin)；

Step 3:計算系統成本函數F(pi)(i=1,2,…,X)，給出鴿群個體適應度值。

F(pi)=η1(E[T])2-η2S；%E[T]與S分別為分配到本地的概率為pi時的任務平均延時和系統節能率

Step 4:找出使系統成本最小的本地分配概率p*。

Step 5:執行地圖和指南針算子，計算鴿群速度vi(i=1,2,…,X)與鴿群位置pi(i=1,2,…,X)，基于“教與學”過程更新鴿群位置pi(i=1,2,…,X)。

vi=vi×exp(-φ×t1)+rand×(p*-pi)；%計算鴿群速度vi

pi=pi+vi；%更新鴿群位置pi

τ=round(1+rand)；% round為四舍五入運算符

隨機選取兩個鴿子位置pa與pb；%a,b= 1, 2, …,X

pi=pi+rand×abs(pa-pb)；%abs為絕對值運算符

Step 6:檢查地圖和指南針算子的迭代條件。

ift1

t1=t1+1，goto Step 5；

endif

Step 7:執行地標算子，更新鴿群位置pi，找出最優的鴿子位置p*。

按系統成本值由小到大排列鴿群位置pi(i=1,2,…,X)；

X=ceil(X/2)；%ceil為向上取整運算符

sum1=0；

sum2=0；

fori=1 :X

sum1=sum1+pi×F(pi)；

sum2=sum2+F(pi)；

endfor

center=ceil(sum1/(X×sum2))；

fori=1 :X

pi=pi+rand×(center-pi)；%更新鴿群位置pi

if(pi>pmax)‖(pi

pi=pmin+rand×(pmax-pmin)；

endif

ifF(pi)

p*=pi；%更新最優的鴿子位置p*

endif

endfor

Step 8:檢查地標算子的迭代條件。

if(t21)

t2=t2+1，goto Step 7；

endif

Step 9:輸出最優的本地分配概率p*及最小系統成本F(p*)。

以參數η1=5，η2=0.100，X=80，pmin=0.001，pmax=0.999，Y1=50，Y2=40及φ=0.700為例，利用改進的鴿群算法找出最優的本地分配概率p*以及最小系統成本F(p*)，結果如表2所示。

表2 本地分配概率的優化結果Tab.2 Optimization results of local allocation probability

相比于MEC服務器，本地移動設備自身處理能力有限，能夠接納的任務不能太多。當系統的任務到達率增加時，為了保證網絡用戶的服務質量，將有更多的任務卸載到MEC服務器，因此，最優本地分配概率下降。另一方面，隨著系統的任務到達率的增加，任務平均延時增大，系統節能率變小，這些都是使系統成本變大的原因。由此可知，表2的數值結果所揭示的最優本地分配概率及最小系統成本的變化規律是合理的。

5 結論

綜合考慮網絡用戶的響應性能及系統節能水平，融合虛擬機分簇與同步周期性休眠機制，面向 MEC 提出了一種任務卸載策略?；趥溆媚K虛擬機周期性休眠機制，建立帶有同步多重休假機制的連續時間排隊模型，給出了任務平均延時及系統節能率等性能指標的解析式。數值與仿真的實驗結果表明，合理的本地分配概率可以同時保證用戶的響應性能和系統的節能水平。構造系統成本函數，引入“教與學”方法，改進鴿群優化算法，給出了本地分配概率的優化方案，實現了系統成本的最小化。