融合虛擬機(jī)分簇與休眠機(jī)制的MEC任務(wù)卸載策略

王 穎，李 偉，陳夢(mèng)盼，陳 利，金順福,*

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

0 引言

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

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

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

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

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

1.1 MEC任務(wù)卸載策略

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

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

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

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

3) 備用模塊中的虛擬機(jī)在活躍狀態(tài)與休眠狀態(tài)之間自適應(yīng)切換。當(dāng)備用模塊虛擬機(jī)中的所有任務(wù)服務(wù)完畢后，若緩存隊(duì)列中沒(méi)有等待的任務(wù)，立即啟動(dòng)休眠定時(shí)器，全部虛擬機(jī)同時(shí)進(jìn)入第一個(gè)休眠期。一旦備用模塊虛擬機(jī)處于休眠狀態(tài)，新到達(dá)的任務(wù)只能進(jìn)入緩存隊(duì)列中等待。一個(gè)休眠期結(jié)束后，若緩存隊(duì)列中沒(méi)有等待的任務(wù)，則全部備用模塊虛擬機(jī)同時(shí)開(kāi)始下一個(gè)休眠期；否則，關(guān)閉休眠定時(shí)器并進(jìn)入活躍狀態(tài)，依次服務(wù)等待在緩存隊(duì)列中的任務(wù)。

1.2 系統(tǒng)模型

將t時(shí)刻備用模塊中的任務(wù)總數(shù)稱(chēng)為t時(shí)刻的系統(tǒng)水平，表示為N(t)=i(i=0,1,…)。將t時(shí)刻主模塊中的任務(wù)總數(shù)稱(chēng)為t時(shí)刻的系統(tǒng)階段，表示為L(zhǎng)(t)=j(j=0,1,…,c1+H)。將t時(shí)刻備用模塊虛擬機(jī)所處的狀態(tài)稱(chēng)為t時(shí)刻的系統(tǒng)相位，表示為J(t)=k(k=0,1)，其中k=0,1分別表示備用模塊虛擬機(jī)處于休眠狀態(tài)和活躍狀態(tài)。{(N(t),L(t),J(t),t≥0)}構(gòu)成一個(gè)三維連續(xù)時(shí)間馬爾科夫鏈[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}的轉(zhuǎn)移率矩陣表示為Q，系統(tǒng)水平從i(i=0,1,…)跳轉(zhuǎn)到i′(i′=0,1,…)的轉(zhuǎn)移率子陣表示為Qi,i′[12]。為了描述方便，引入符號(hào)Iu(u≥1)，表示u×u維單位陣。

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

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

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

當(dāng)i≥2時(shí)，備用模塊虛擬機(jī)既可能休眠也可能活躍。只有在備用模塊虛擬機(jī)處于活躍狀態(tài)的條件下，當(dāng)虛擬機(jī)服務(wù)完成一個(gè)任務(wù)后，系統(tǒng)水平才可能下降到i-1，此時(shí)，虛擬機(jī)仍保持在活躍狀態(tài)。在2≤i≤c2和i≥c2+1的情況下，一步轉(zhuǎn)移率分別為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)水平保持不變的轉(zhuǎn)移率子陣。

當(dāng)i=0時(shí)，備用模塊中的虛擬機(jī)一定處于休眠狀態(tài)，只需分析主模塊的變化規(guī)律。當(dāng)主模塊中到達(dá)一個(gè)任務(wù)時(shí)，一步轉(zhuǎn)移率為nλ(1-p)。當(dāng)1≤j≤c1時(shí)，若主模塊服務(wù)完成一個(gè)任務(wù)，一步轉(zhuǎn)移率為jμ1；若主模塊中既無(wú)任務(wù)到達(dá)也無(wú)任務(wù)離去，一步轉(zhuǎn)移率為-nλ(1-p)-jμ1。當(dāng)c1+1≤j≤c1+H時(shí)，若主模塊服務(wù)完成一個(gè)任務(wù)，一步轉(zhuǎn)移率為c1μ1；若主模塊中既無(wú)任務(wù)到達(dá)也無(wú)任務(wù)離去，一步轉(zhuǎn)移率為-nλ(1-p)-c1μ1。

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

當(dāng)i≥1時(shí)，備用模塊中的虛擬機(jī)處于休眠狀態(tài)或者活躍狀態(tài)。當(dāng)1≤j≤c1時(shí)，若主模塊服務(wù)完成一個(gè)任務(wù)，一步轉(zhuǎn)移率為jμ1；當(dāng)c1+1≤j≤c1+H時(shí)，若主模塊服務(wù)完成一個(gè)任務(wù)，一步轉(zhuǎn)移率為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。

當(dāng)備用模塊虛擬機(jī)處于休眠狀態(tài)時(shí)，若休眠定時(shí)器到期，一步轉(zhuǎn)移率為θ；若主模塊中無(wú)任務(wù)到達(dá)，無(wú)任務(wù)離去，休眠定時(shí)器未到期，在0≤j≤c1和c1+1≤j≤c1+H的情況下，一步轉(zhuǎn)移率分別為-nλ(1-p)-jμ1-θ與-nλ(1-p)-c1μ1-θ。當(dāng)備用模塊虛擬機(jī)處于活躍狀態(tài)且主模塊中無(wú)任務(wù)到達(dá)，無(wú)任務(wù)離去，備用模塊中無(wú)任務(wù)離去時(shí)，若1≤i≤c2，在0≤j≤c1和c1+1≤j≤c1+H的情況下，一步轉(zhuǎn)移率分別為-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的情況下，一步轉(zhuǎn)移率分別為-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表示為

當(dāng)主模塊中到達(dá)一個(gè)任務(wù)時(shí)，一步轉(zhuǎn)移率為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的轉(zhuǎn)移率子陣。

當(dāng)i=0時(shí)，備用模塊中的虛擬機(jī)一定處于休眠狀態(tài)。當(dāng)主模塊中的可用容量為零時(shí)，新到達(dá)的任務(wù)進(jìn)入備用模塊，備用模塊虛擬機(jī)仍處于休眠狀態(tài)，一步轉(zhuǎn)移率為nλ(1-p)。

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

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

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

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

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

構(gòu)造矩陣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列向量。

運(yùn)用高斯—賽德?tīng)柕?，求解方程組(1)，可得π0,π1,…,πc2的數(shù)值解，利用矩陣幾何解形式πk=πc2Rk-c2,k≥c2+1進(jìn)一步得到πk(k≥c2+1)的數(shù)值解。

3 性能指標(biāo)與系統(tǒng)實(shí)驗(yàn)

3.1 性能指標(biāo)

任務(wù)平均延時(shí)及系統(tǒng)節(jié)能率是評(píng)估MEC任務(wù)卸載策略的兩個(gè)重要指標(biāo)。

任務(wù)平均延時(shí)定義為任務(wù)從進(jìn)入系統(tǒng)直到離開(kāi)系統(tǒng)平均消耗的時(shí)間，即平均等待時(shí)間與服務(wù)時(shí)間的和。

任務(wù)在本地處理器接受服務(wù)的平均延時(shí)E[T0]為

(2)

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

(3)

若主模塊中的可用容量為零時(shí)，新到達(dá)的任務(wù)將進(jìn)入緩存容量無(wú)限的備用模塊中。在備用模塊中接受服務(wù)的任務(wù)平均延時(shí)E[T2]為

(4)

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

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

(5)

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

(6)

3.2 系統(tǒng)實(shí)驗(yàn)

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

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

基于數(shù)學(xué)理論分析的數(shù)值實(shí)驗(yàn)獲得的是樣本空間為無(wú)窮大時(shí)的極限結(jié)果。該結(jié)果的準(zhǔn)確性與所采用高斯—賽德?tīng)柕ㄇ蠼夥匠探M的精度有關(guān)?；跈C(jī)理模型的仿真實(shí)驗(yàn)獲得的是樣本空間有限條件下的統(tǒng)計(jì)結(jié)果。該結(jié)果的準(zhǔn)確性與樣本空間的大小有關(guān)。

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

表1 系統(tǒng)參數(shù)Tab.1 System parameters

圖2刻畫(huà)了卸載策略下任務(wù)平均延時(shí)E[T]的變化趨勢(shì)。

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

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

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

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

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

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

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

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

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

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

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

傳統(tǒng)的鴿群算法[16]容易陷入局部最優(yōu)。為了改善這一問(wèn)題，提出一種融合“教與學(xué)”過(guò)程的改進(jìn)的鴿群算法?；凇敖膛c學(xué)”過(guò)程能夠引導(dǎo)鴿群的飛行方向，改善候選解的質(zhì)量，避免陷入局部最優(yōu)。使用改進(jìn)的鴿群算法，以成本最小為目標(biāo)，優(yōu)化本地分配概率。改進(jìn)的算法步驟如下：

Step 1:初始化鴿群位置(本地分配概率)的左邊界pmin與右邊界pmax，鴿群數(shù)量X，地圖和指南針?biāo)阕拥淖畲蟮螖?shù)Y1，地標(biāo)算子的最大迭代次數(shù)Y2，指南針因子φ。設(shè)地圖和指南針?biāo)阕拥漠?dāng)前迭代次數(shù)t1=1，地標(biāo)算子的當(dāng)前迭代次數(shù)t2=1。

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

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

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

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

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

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

Step 5:執(zhí)行地圖和指南針?biāo)阕樱?jì)算鴿群速度vi(i=1,2,…,X)與鴿群位置pi(i=1,2,…,X)，基于“教與學(xué)”過(guò)程更新鴿群位置pi(i=1,2,…,X)。

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

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

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

隨機(jī)選取兩個(gè)鴿子位置pa與pb；%a,b= 1, 2, …,X

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

Step 6:檢查地圖和指南針?biāo)阕拥牡鷹l件。

ift1

t1=t1+1，goto Step 5；

endif

Step 7:執(zhí)行地標(biāo)算子，更新鴿群位置pi，找出最優(yōu)的鴿子位置p*。

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

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

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:檢查地標(biāo)算子的迭代條件。

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為例，利用改進(jìn)的鴿群算法找出最優(yōu)的本地分配概率p*以及最小系統(tǒng)成本F(p*)，結(jié)果如表2所示。

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

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

5 結(jié)論

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