彭璧瑩，李陶深,2**，陳 燕

(1.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西南寧 530004；2.南寧學(xué)院，廣西中國-東盟綜合交通國際聯(lián)合重點(diǎn)實(shí)驗(yàn)室，廣西南寧 530200)

隨著無線通信技術(shù)的快速發(fā)展，越來越多的移動(dòng)設(shè)備有了無線網(wǎng)絡(luò)訪問需求。雖然將計(jì)算密集型應(yīng)用卸載到云端可以克服移動(dòng)設(shè)備資源受限的弊端，但是對(duì)于時(shí)延敏感型應(yīng)用而言，移動(dòng)設(shè)備與云端的無線網(wǎng)絡(luò)連接帶來的較長延時(shí)卻并不能使用戶滿意[1]。移動(dòng)邊緣計(jì)算(Mobie Edge Computing,MEC)將計(jì)算節(jié)點(diǎn)布置到網(wǎng)絡(luò)邊緣，可以滿足用戶低時(shí)延的需求。當(dāng)前MEC中的計(jì)算卸載技術(shù)主要包括卸載決策、資源分配和卸載系統(tǒng)實(shí)現(xiàn)等3個(gè)方面，其中卸載決策主要解決的是移動(dòng)終端決定如何卸載、卸載多少以及卸載什么的問題[2]。該類研究主要集中于考慮多用戶環(huán)境和多服務(wù)器環(huán)境下的卸載決策問題[3,4]。

目前，一些研究人員利用粒子群優(yōu)化 (Particle Swarm Optimization,PSO) 算法來解決計(jì)算卸載問題。Wei等[5]采用基于貪心策略的PSO算法和動(dòng)態(tài)PSO算法，提出了基于動(dòng)態(tài)PSO算法的單用戶多邊云設(shè)備任務(wù)分配策略，考慮了任務(wù)的相互依賴性。Bi等[6]使用基于遺傳模擬退火和PSO的啟發(fā)式算法來解決非線性約束優(yōu)化問題，聯(lián)合優(yōu)化了每個(gè)移動(dòng)設(shè)備的任務(wù)卸載比、CPU速度和傳輸功率，以及可用通道的帶寬，進(jìn)而實(shí)現(xiàn)更低能耗。Li等[7]建立了時(shí)延、能耗和多目標(biāo)優(yōu)化模型，增加了平衡延遲和能量消耗的懲罰函數(shù)，提出了改進(jìn)PSO算法的卸載策略(Improved Optimization Algorithm based on Particle Swarm,EIPSO)。Al-Habob等[8]則考慮了一組需要調(diào)度到服務(wù)器的相互依賴的子任務(wù)，并基于遺傳算法和沖突圖模型解決了調(diào)度問題，使卸載延遲和失效概率最小化。羅斌等[9]對(duì)邊緣云的MEC服務(wù)器進(jìn)行編碼，最后通過PSO算法確定每個(gè)任務(wù)對(duì)應(yīng)的服務(wù)器編號(hào)，實(shí)驗(yàn)結(jié)果表明，該算法使系統(tǒng)總成本降低了20%?？娫Ｇ嗟萚10]引入壓縮因子，并運(yùn)用模擬退火算法思想改進(jìn)PSO算法，以此實(shí)現(xiàn)任務(wù)卸載，其中粒子的編碼對(duì)應(yīng)車輛任務(wù)分配方案，仿真結(jié)果表明其代價(jià)是傳統(tǒng)PSO算法的53.8%。

也有研究人員在計(jì)算卸載時(shí)采用緩存技術(shù)來提高優(yōu)化效果，如利用移動(dòng)邊緣緩存將內(nèi)容放置在用戶邊緣，這樣可以有效降低用戶請(qǐng)求延遲和能耗，并且避免數(shù)據(jù)通過回程鏈路傳輸，從而降低回程流量[11]。郭煜[1]將任務(wù)緩存與卸載決策最優(yōu)化問題分為兩個(gè)子優(yōu)化問題，任務(wù)卸載策略可轉(zhuǎn)變?yōu)橥棺顑?yōu)化問題，通過內(nèi)點(diǎn)法求解；任務(wù)緩存可轉(zhuǎn)變?yōu)?-1整數(shù)規(guī)劃問題，使用分支限界法獲取最優(yōu)解，仿真實(shí)驗(yàn)表明該策略在動(dòng)態(tài)異構(gòu)的任務(wù)執(zhí)行環(huán)境下可以實(shí)現(xiàn)更好的能效優(yōu)化。Nath等[12]開發(fā)了一種基于深度學(xué)習(xí)的動(dòng)態(tài)調(diào)度策略，該策略將流行任務(wù)緩存到MEC服務(wù)器中避免重復(fù)卸載，以此最小化代價(jià)函數(shù)的長期平均值。Lan等[13]利用隨機(jī)理論提出了一個(gè)任務(wù)緩存優(yōu)化問題，并采用基于遺傳算法的任務(wù)緩存算法進(jìn)行求解。

分析以上的研究工作可以發(fā)現(xiàn)，對(duì)于MEC場景中基于PSO算法的計(jì)算卸載問題，現(xiàn)有的工作大多集中在粒子編碼或融合其他算法的研究上，從時(shí)延或能效優(yōu)化的角度對(duì)算法優(yōu)劣進(jìn)行評(píng)估。此外，與其他算法結(jié)合的PSO算法的優(yōu)化結(jié)果優(yōu)于傳統(tǒng)算法，且加入任務(wù)緩存策略的卸載比無緩存的卸載時(shí)延的優(yōu)化更勝一籌。基于此，本文提出一個(gè)基于遺傳-粒子群優(yōu)化算法(Genetic-Particle Swarm Optimization Algorithm,GA-PSO)和緩存機(jī)制的卸載策略，在邊緣云上進(jìn)行緩存，以便有效降低移動(dòng)邊緣計(jì)算的時(shí)延。最后通過仿真實(shí)驗(yàn)，證明所提算法的收斂性和有效性。

1 系統(tǒng)模型

本文研究的目標(biāo)是在邊緣云緩存能力受限且存在移動(dòng)設(shè)備能耗約束的情況下，實(shí)現(xiàn)最優(yōu)的任務(wù)緩存和卸載，最小化系統(tǒng)時(shí)延。為此主要解決兩個(gè)問題，即哪些任務(wù)需要緩存在邊緣云上，以及多少比例的任務(wù)需要卸載到邊緣云上執(zhí)行。本文的系統(tǒng)模型如圖1所示。

圖1 多設(shè)備系統(tǒng)模型Fig.1 Multi-equipment system model

1.1 場景描述

如圖1所示，本文的MEC場景由多個(gè)移動(dòng)設(shè)備和一個(gè)MEC邊緣云組成。假設(shè)移動(dòng)設(shè)備(用戶)數(shù)量為N={1,2,…,n}，計(jì)算任務(wù)數(shù)量為I={1,2,…,i}，用戶發(fā)出任務(wù)請(qǐng)求后，移動(dòng)設(shè)備可通過無線信道與其邊緣云連接。對(duì)于移動(dòng)設(shè)備的任務(wù)Un,i，用二元組對(duì)其定義，即Un,i={Ci,di}，其中Ci是完成任務(wù)i所需要的計(jì)算資源數(shù)，也就是CPU周期總數(shù)；di是任務(wù)i的數(shù)據(jù)量大小，以bit為單位。

1.2 時(shí)延模型

不同的設(shè)備運(yùn)行任務(wù)會(huì)導(dǎo)致時(shí)延有所不同。本文考慮兩種情況，即當(dāng)前任務(wù)在本地執(zhí)行的情況以及卸載至邊緣云的情況。這兩種情況涉及的時(shí)延有本地計(jì)算時(shí)延、移動(dòng)設(shè)備上傳數(shù)據(jù)時(shí)延、MEC服務(wù)器計(jì)算時(shí)延、反饋時(shí)延。因?yàn)榉答仌r(shí)延遠(yuǎn)小于上傳時(shí)延，故可忽略不計(jì)。

①本地計(jì)算時(shí)延。

(1)

②傳輸時(shí)延。

在計(jì)算移動(dòng)設(shè)備上傳數(shù)據(jù)所耗費(fèi)的時(shí)延之前，需要先計(jì)算出上傳速率Rn。根據(jù)香農(nóng)公式可得：

(2)

其中，B為移動(dòng)設(shè)備與邊緣云之間的無線信道帶寬，Pn為移動(dòng)設(shè)備n的發(fā)射功率，Hn為無線信道增益，σ2為噪聲功率消耗。

(3)

③MEC計(jì)算時(shí)延。

(4)

其中，fs為MEC服務(wù)器的CPU計(jì)算能力。

(5)

1.3 能耗模型

①本地計(jì)算能耗。

(6)

②傳輸能耗。

(7)

1.4 問題形式化

對(duì)于任務(wù)緩存問題，可定義一個(gè)決策變量X1i∈{0,1}。當(dāng)X1i=1時(shí)，表示任務(wù)i緩存到邊緣云執(zhí)行；該值為0則表示不緩存，且任務(wù)緩存至邊緣云這種情況只需要考慮邊緣云執(zhí)行任務(wù)的時(shí)延。此處存在邊緣云緩存資源約束，即緩存的任務(wù)數(shù)據(jù)總量需小于邊緣云的緩存大小。對(duì)于任務(wù)卸載問題，可定義卸載比例為X2i∈[0,1]。當(dāng)X2i=0表示在本地執(zhí)行任務(wù)；當(dāng)X2i=1則表示全部卸載到邊緣云執(zhí)行；X2i∈(0,1)時(shí)表示卸載X2i的部分任務(wù)到邊緣云執(zhí)行；剩余1-X2i部分的任務(wù)在本地執(zhí)行。

綜上所述，總時(shí)延Ti為

(8)

移動(dòng)設(shè)備總能耗Ei為

(9)

本算法的優(yōu)化目標(biāo)是在邊緣云資源與移動(dòng)設(shè)備最大能耗約束的限制下，找到系統(tǒng)時(shí)延最小的卸載比例以及緩存決策，因此優(yōu)化問題可以形式化為

C2:X1i∈{0,1},?i∈I

C3:X2i∈[0,1],?i∈I

C4:Ei≤Emax,?i∈I，

(10)

其中，Ec表示邊緣云緩存容量，Emax表示最大能耗約束，約束C1表明緩存任務(wù)的數(shù)據(jù)總量不能大于邊緣云的緩存能力；約束C2表明任務(wù)緩存決策變量為二進(jìn)制變量，1與0分別代表緩存與否；約束C3表明可分割部分任務(wù)在本地執(zhí)行，而其余部分在邊緣云上執(zhí)行；約束C4表明移動(dòng)設(shè)備能耗需不超過最大能耗約束。顯然，目標(biāo)函數(shù)表示通過任務(wù)緩存與對(duì)卸載比例的決策，使得系統(tǒng)時(shí)延代價(jià)最小化。

2 卸載策略

基于式(10)的優(yōu)化目標(biāo)，本文提出帶有緩存機(jī)制的GA-PSO卸載策略。該策略將遺傳算法和PSO算法融合起來，以便求取邊緣計(jì)算卸載中的最優(yōu)卸載比例和緩存決策。策略的核心思想與PSO算法一致，即將待優(yōu)化問題的搜索空間類比為鳥類的飛行空間，將每一只鳥抽象為一個(gè)粒子，每個(gè)粒子表征問題的一個(gè)可行解，優(yōu)化問題所要搜索到的最優(yōu)解等同于鳥類尋找的食物源。其中每個(gè)粒子的特征都由適應(yīng)度、位置和速度來表示，而適應(yīng)度的好壞決定了粒子的優(yōu)劣[9]。

基于本文策略實(shí)現(xiàn)的算法是在PSO算法的基礎(chǔ)上引進(jìn)生物學(xué)的進(jìn)化思想，加入遺傳、突變、自然選擇以及雜交等操作，利用群體中的個(gè)體對(duì)信息的共享使整個(gè)群體的運(yùn)動(dòng)在問題求解空間中產(chǎn)生從無序到有序的演化過程，在狀態(tài)空間中對(duì)每一個(gè)粒子的位置進(jìn)行搜索評(píng)估，得到局部最優(yōu)位置(本文中的粒子位置代表卸載比例和緩存決策)；然后再從該位置進(jìn)行搜索，重復(fù)以上過程直到得到全局最優(yōu)位置。此時(shí)，適應(yīng)度也達(dá)到收斂狀態(tài)，該適應(yīng)度值即為系統(tǒng)時(shí)延代價(jià)。因?yàn)檫z傳算法收斂速度慢但全局搜索能力強(qiáng)，PSO算法局部搜索能力強(qiáng)但容易陷入早熟，故兩者的融合恰好可以彌補(bǔ)彼此的缺陷與局限性。

本文策略算法的設(shè)計(jì)思路如下：先對(duì)粒子進(jìn)行編碼，粒子元素值代表卸載比例與緩存決策；接下來設(shè)置需要優(yōu)化的目標(biāo)為適應(yīng)度函數(shù)，由于本文主要是針對(duì)時(shí)延敏感型的任務(wù)，所以選取的是系統(tǒng)總時(shí)延為適應(yīng)度值，而總時(shí)延的求解公式已在上一節(jié)的式(8)中給出。該策略算法實(shí)現(xiàn)時(shí)，通過進(jìn)化迭代直至適應(yīng)度值收斂，從而獲得其全局最優(yōu)解。算法使用罰函數(shù)將有約束最優(yōu)化問題轉(zhuǎn)化為求解無約束最優(yōu)化問題，在不滿足線性約束時(shí)讓適應(yīng)度函數(shù)值無窮大即可，并采用雙循環(huán)變量法對(duì)最優(yōu)卸載比例與緩存決策進(jìn)行求解，再根據(jù)適應(yīng)度函數(shù)計(jì)算出系統(tǒng)時(shí)延代價(jià)。下面介紹算法的具體實(shí)現(xiàn)。

2.1 粒子編碼

粒子個(gè)體采用浮點(diǎn)數(shù)編碼，每一個(gè)粒子元素可以取0到1.000 1之間的任意浮點(diǎn)數(shù)，粒子編碼維度與任務(wù)總數(shù)相同。如若粒子元素值pop=1.000 1時(shí)，表明任務(wù)緩存到邊緣云，而pop∈[0,1]則表示該值為卸載比例。粒子的速度表示任務(wù)部分卸載到邊緣云趨勢的快慢，記作V={v1,v2,…,vi}，粒子速度初始化為-0.1到0.1的隨機(jī)浮點(diǎn)數(shù)，粒子速度編碼的維度也應(yīng)該與任務(wù)總數(shù)相同。每一個(gè)粒子在進(jìn)化迭代過程中最優(yōu)位置為Gbest，而所有粒子中出現(xiàn)的最優(yōu)位置為Zbest，是使得系統(tǒng)代價(jià)最小的分配方式。

2.2 適應(yīng)度函數(shù)

(11)

其中，函數(shù)包含了需要求解的兩個(gè)變量，X1即緩存決策，X2即卸載決策。

2.3 算法流程

基于GA-PSO和緩存機(jī)制的卸載策略的算法可以描述為以下7個(gè)步驟。

步驟1：設(shè)置交叉概率、變異概率、學(xué)習(xí)因子、慣性權(quán)重、最大迭代次數(shù)、粒子群規(guī)模數(shù)、粒子的最大速度、位置邊界等算法控制參數(shù)，在速度區(qū)間和搜索空間上隨機(jī)初始化粒子的速度和位置;

步驟2：定義適應(yīng)度函數(shù)，根據(jù)初始值計(jì)算公式(8)所求的時(shí)延，再通過公式(11)的累加計(jì)算出初始適應(yīng)度值;

步驟3：循環(huán)開始，根據(jù)所求出的粒子位置計(jì)算出個(gè)體極值與全局極值。個(gè)體極值為每個(gè)粒子找到的最優(yōu)解，再從這些最優(yōu)解可找到全局最優(yōu)解;

步驟4：使用粒子群公式更新每個(gè)粒子的位置與速度，并依據(jù)交叉、變異概率進(jìn)行相應(yīng)的染色體操作，得到新的種群;

步驟5：如若新種群符合約束條件就求更新后的適應(yīng)度值，不符合約束條件則將適應(yīng)度值設(shè)為無窮大，使其自然淘汰;

步驟6：將全局最優(yōu)方案代入公式(8)，累加后計(jì)算出新的適應(yīng)度值。如果新求出的適應(yīng)度值比歷史值小，則返回步驟3并更新個(gè)體和全局最優(yōu)分配方案;

作為神經(jīng)系統(tǒng)免疫細(xì)胞，小膠質(zhì)細(xì)胞當(dāng)在神經(jīng)受損以后被激活，從而將大量的白細(xì)胞介素釋放出來，同時(shí)還會(huì)釋放出趨化因子，對(duì)周圍神經(jīng)元產(chǎn)生作用，促使NeP的中樞敏化加劇，從而將“膠質(zhì)免疫-神經(jīng)元”的神經(jīng)病理性疼痛機(jī)制形成。有研究人員通過開展實(shí)驗(yàn)研究[13]，將JNK阻滯劑應(yīng)用到結(jié)扎脊神經(jīng)的NeP模型中，可以對(duì)疼痛有效抑制并能夠取得較為明顯的阻滯效果，星形膠質(zhì)細(xì)胞激活被阻滯劑抑制是得以獲得顯著鎮(zhèn)痛效果的關(guān)鍵原因。有研究顯示，星形膠質(zhì)細(xì)胞上JNK的磷酸化，NR2B亞基參與，可以對(duì)神經(jīng)損傷誘導(dǎo)的JNK磷酸化進(jìn)行抑制，通過注射7-硝基吲唑鈉與神經(jīng)元一氧化氮合酶nNOS選擇性抑制劑。

步驟7：判斷循環(huán)結(jié)束的條件是目標(biāo)函數(shù)的適應(yīng)度達(dá)到期望值或者進(jìn)化到預(yù)先設(shè)定的代數(shù)，算法結(jié)束的判定是進(jìn)化到預(yù)先設(shè)定的代數(shù)即可終止，算法結(jié)束時(shí)輸出全局最優(yōu)解與適應(yīng)度值，前者表示最優(yōu)卸載比例與緩存決策，后者則表示該方案下的時(shí)延。

該算法的偽代碼如下。

輸入：

①本地任務(wù)集合：I={1,2,…,i}；

②算法控制參數(shù)：粒子群規(guī)模par_num=100，迭代次數(shù)maxgen=100，位置邊界popmin與popmax分別為粒子編碼的最小值與最大值，學(xué)習(xí)因子c1=c2=1.5，慣性權(quán)重w=0.5，交叉概率pc=0.7，變異概率pm=0.3。

輸出： 最優(yōu)卸載比例與緩存決策，以及最小時(shí)延

算法的主要過程：

① 初始化:popsize,maxgen,popmin,popmax,c1,c2,w,oc,pm,V,pop

②fori=1tomaxgendo

③forj=1topopsizedo

④V(j,:)=V(j,:)+c1*rand*(gbest(j,:)-pop(j,:))+c2*rand*(zbest-

pop(j,:));

⑤pop(j,:)=pop(j,:)+w*V(j,:);

⑥r(nóng)epeat

⑦mpick,cpick←rand

⑧ifmpick>pmthen

⑨ Randomly select where to mutate

⑩ Mutation operation

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 仿真環(huán)境及參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果與性能分析

本文實(shí)驗(yàn)的目的有二：一是驗(yàn)證本算法的有效性和收斂性，二是通過一些仿真實(shí)驗(yàn)從多角度比較和評(píng)估在不同參數(shù)下本文提出的卸載策略的性能。實(shí)驗(yàn)中，假設(shè)本地設(shè)備也可處理高計(jì)算量的任務(wù)，且任務(wù)到達(dá)即可執(zhí)行，不考慮任務(wù)排隊(duì)導(dǎo)致的時(shí)延增長。

首先對(duì)本文的GA-PSO卸載策略的收斂性進(jìn)行評(píng)估，設(shè)置設(shè)備數(shù)I=100，其余參數(shù)設(shè)置如3.1節(jié)所示。圖2給出了GA-PSO卸載策略收斂性的實(shí)驗(yàn)結(jié)果。從圖2可以觀察到，本算法在前25次進(jìn)化迭代過程中收斂速度較快，而后其適應(yīng)度值保持不變，說明已找到全局最優(yōu)解。

圖2 收斂性分析圖Fig.2 Graph of convergence analysis

接著比較本文帶緩存機(jī)制的GA-PSO卸載算法、不帶緩存機(jī)制的GA-PSO卸載算法、本地計(jì)算和將所有任務(wù)卸載到MEC服務(wù)器這4種方案的系統(tǒng)時(shí)延，實(shí)驗(yàn)對(duì)比結(jié)果如圖3所示。從圖3可以看出，當(dāng)設(shè)備數(shù)為25，50，75，100，125時(shí)，這4種策略的系統(tǒng)總延遲均隨著設(shè)備數(shù)增長呈增加趨勢，而本文策略的系統(tǒng)時(shí)延小于其他3種方案的時(shí)延。由于設(shè)備數(shù)越多，任務(wù)量也會(huì)隨之增加，從而導(dǎo)致時(shí)延上升。但是，本文策略加入了緩存機(jī)制并使用改進(jìn)的算法，使得緩存的任務(wù)只需要考慮邊緣云執(zhí)行任務(wù)的時(shí)延，不存在上傳時(shí)延，所以耗費(fèi)時(shí)間比需要卸載的非緩存任務(wù)的執(zhí)行時(shí)間短，從而使得系統(tǒng)時(shí)延達(dá)到最小化。

圖3 設(shè)備數(shù)對(duì)系統(tǒng)時(shí)延的影響Fig.3 Impact of device number on system delay

第3個(gè)實(shí)驗(yàn)是測試分析邊緣云緩存容量與設(shè)備能耗、時(shí)延之間的關(guān)系，實(shí)驗(yàn)的目的是分析緩存與否以及緩存容量的大小對(duì)設(shè)備總能耗與系統(tǒng)時(shí)延產(chǎn)生的影響。圖4給出了使用本文的GA-PSO卸載策略、本地計(jì)算和將所有任務(wù)卸載到MEC服務(wù)器這3種方案后邊緣云緩存容量與系統(tǒng)能耗、時(shí)延之間的關(guān)系。圖4使用了雙坐標(biāo)軸圖，左邊的縱坐標(biāo)是系統(tǒng)能耗，右邊的縱坐標(biāo)為時(shí)延。從圖4可以看出，隨著緩存資源的增加，能耗有降低的趨勢，也就是邊緣云可以緩存的任務(wù)數(shù)據(jù)越多，移動(dòng)設(shè)備的耗能就越低；此外，本地計(jì)算的能耗明顯比本文的GA-PSO卸載策略的能耗高，表明本文卸載策略在一定程度上降低了移動(dòng)設(shè)備的能耗。這是因?yàn)椴糠秩蝿?wù)的相關(guān)數(shù)據(jù)已經(jīng)緩存到邊緣云，執(zhí)行此類任務(wù)移動(dòng)設(shè)備不產(chǎn)生能量消耗。從圖4還可以看出，邊緣云緩存容量越大，系統(tǒng)時(shí)延就越小，說明緩存對(duì)時(shí)延有較大影響。這是因?yàn)榫彺嫒萘吭酱螅删彺嫒蝿?wù)的數(shù)量越多，而緩存任務(wù)的執(zhí)行時(shí)間比需要卸載的非緩存任務(wù)的執(zhí)行時(shí)間短。

圖4 邊緣云緩存能力對(duì)系統(tǒng)時(shí)延及能耗的影響Fig.4 Impact of edge cloud caching capability on system delay and energy consumption

4 結(jié)束語

本文提出了一個(gè)基于GA-PSO和緩存機(jī)制的卸載策略，該策略兼具遺傳算法的全局搜索優(yōu)勢與PSO算法的局部搜索優(yōu)勢，搜索速度快，可以得到最優(yōu)的卸載比例與緩存決策。仿真實(shí)驗(yàn)結(jié)果分析表明，與本地計(jì)算、全部卸載以及無緩存的卸載策略相比，本文的GA-PSO卸載策略使得本地設(shè)備與邊緣云協(xié)作計(jì)算，可以降低移動(dòng)邊緣計(jì)算的時(shí)延代價(jià)。未來還可將PSO算法與其他優(yōu)化算法結(jié)合，尋求一個(gè)可靠性更高的卸載策略。