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

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

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

0 引言

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

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

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

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

1 MEC任務卸載策略及系統(tǒng)模型

1.1 MEC任務卸載策略

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

圖1 MEC系統(tǒng)任務卸載Fig.1 Task offloading in MEC system

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

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

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

1.2 系統(tǒng)模型

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

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

令πi,j,k表示穩(wěn)態(tài)下系統(tǒng)水平為i，系統(tǒng)階段j及系統(tǒng)相位為k的概率分布。πi,j,k表示為

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

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

2 系統(tǒng)模型的穩(wěn)態(tài)解析

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

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

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

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

當i≥2時，備用模塊虛擬機既可能休眠也可能活躍。只有在備用模塊虛擬機處于活躍狀態(tài)的條件下，當虛擬機服務完成一個任務后，系統(tǒng)水平才可能下降到i-1，此時，虛擬機仍保持在活躍狀態(tài)。在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為系統(tǒng)水平保持不變的轉移率子陣。

當i=0時，備用模塊中的虛擬機一定處于休眠狀態(tài)，只需分析主模塊的變化規(guī)律。當主模塊中到達一個任務時，一步轉移率為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時，備用模塊中的虛擬機處于休眠狀態(tài)或者活躍狀態(tài)。當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。

當備用模塊虛擬機處于休眠狀態(tài)時，若休眠定時器到期，一步轉移率為θ；若主模塊中無任務到達，無任務離去，休眠定時器未到期，在0≤j≤c1和c1+1≤j≤c1+H的情況下，一步轉移率分別為-nλ(1-p)-jμ1-θ與-nλ(1-p)-c1μ1-θ。當備用模塊虛擬機處于活躍狀態(tài)且主模塊中無任務到達，無任務離去，備用模塊中無任務離去時，若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為系統(tǒng)水平由i增加到i+1的轉移率子陣。

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

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

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

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

由以上分析可知，轉移率子陣Qi,i-1及Qi,i從系統(tǒng)水平c2開始重復，Qi,i+1從系統(tǒng)水平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)。可將三維連續(xù)時間馬爾科夫鏈{(N(t),L(t),J(t)),t≥0}的轉移率陣Q表示為

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

構造矩陣B[R]如下

由系統(tǒng)穩(wěn)態(tài)方程及歸一化約束條件[14]得出方程組如下

(1)

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

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

3 性能指標與系統(tǒng)實驗

3.1 性能指標

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

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

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

(2)

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

(3)

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

(4)

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

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

(5)

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

(6)

3.2 系統(tǒng)實驗

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

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

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

參考文獻[12]，同時考慮系統(tǒng)穩(wěn)定條件，設置實驗所用系統(tǒng)參數(shù)如表1所示。

表1 系統(tǒng)參數(shù)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]先呈現(xiàn)出下降趨勢，在任務平均延時E[T]到達最低點之后，又呈現(xiàn)出上升趨勢。當本地分配概率較小時，大多數(shù)的任務卸載到MEC服務器，隨著本地分配概率逐漸變大，去往本地的任務數(shù)量逐漸變多，緩解了MEC服務器的負載壓力，任務平均延時減小。當本地分配概率較大時，大多數(shù)的任務去往本地，隨著本地分配概率逐漸變大，一方面，本地負載壓力變大，使得任務平均延時增大；另一方面，MEC服務器因頻繁休眠，服務能力減弱，也使得任務平均延時增大。

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

圖3刻畫了卸載策略下系統(tǒng)節(jié)能率S的變化趨勢。

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

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

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

由上述分析可知，任務到達率及本地分配概率對任務平均延時和系統(tǒng)節(jié)能率有很大影響。對于給定的任務到達率，合理設置本地分配概率，能夠?qū)崿F(xiàn)響應性能與節(jié)能水平的合理均衡。

4 策略參數(shù)優(yōu)化

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

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

傳統(tǒng)的鴿群算法[16]容易陷入局部最優(yōu)。為了改善這一問題，提出一種融合“教與學”過程的改進的鴿群算法。基于“教與學”過程能夠引導鴿群的飛行方向，改善候選解的質(zhì)量，避免陷入局部最優(yōu)。使用改進的鴿群算法，以成本最小為目標，優(yōu)化本地分配概率。改進的算法步驟如下：

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

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

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

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

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

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

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

Step 5:執(zhí)行地圖和指南針算子，計算鴿群速度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:執(zhí)行地標算子，更新鴿群位置pi，找出最優(yōu)的鴿子位置p*。

按系統(tǒng)成本值由小到大排列鴿群位置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；%更新最優(yōu)的鴿子位置p*

endif

endfor

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

if(t21)

t2=t2+1，goto Step 7；

endif

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

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

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

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

5 結論

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