章呈瑞，柯 鵬，尹 梅

1.武漢科技大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，武漢 430065

2.智能信息處理與實時工業(yè)系統(tǒng)湖北省重點實驗室，武漢 430065

隨著5G通訊技術(shù)與物聯(lián)網(wǎng)技術(shù)的發(fā)展，用戶對AR、VR等計算密集型、時延敏感型應(yīng)用的需求越來越高。根據(jù)思科2020年度互聯(lián)網(wǎng)報告統(tǒng)計，預(yù)計到2023年全球移動設(shè)備將從2018年的88億增長到2023年的131億，連接到IP網(wǎng)絡(luò)的設(shè)備數(shù)量將達到293億高于2018年的184億[1]。傳統(tǒng)的云計算作為一種集中式計算，已難以在短時間內(nèi)處理需要大量資源的應(yīng)用程序。此外，由于云計算中心往往距離用戶較遠，也帶來了數(shù)據(jù)傳輸時延高、能耗高等一系列問題。

為了應(yīng)對這些問題，移動邊緣計算（mobile edge computing，MEC）應(yīng)用而生[2]，該模式通過云計算下沉，端計算上移來將移動智能終端及物聯(lián)網(wǎng)設(shè)備的計算任務(wù)卸載至邊緣云中，解決了傳統(tǒng)云計算模式算力有限、時延較高的不足。

MEC計算卸載作為一個重要的研究方向，受到了國內(nèi)外學(xué)者的廣泛研究。目前對于計算卸載策略的研究主要包括三個方向，最小化時延、最小化能耗以及時延和能耗加權(quán)后最小化該代價函數(shù)[3]。

文獻[4-7]側(cè)重于對最小化時延的研究。文獻[4]研究了多用戶計算的劃分以及云資源上卸載計算，設(shè)計了一個離線啟發(fā)式算法，來解決計算卸載所面臨的時延問題。文獻[5]采用馬爾可夫決策方法，根據(jù)任務(wù)緩沖區(qū)的排隊狀態(tài)、本地處理單元的執(zhí)行狀態(tài)以及傳輸單元的狀態(tài)來動態(tài)卸載計算任務(wù)。文獻[6]構(gòu)建了一個帶有能量收集設(shè)備的MEC系統(tǒng)，并提出了一種基于李雅普諾夫優(yōu)化的動態(tài)計算卸載算法用以最小化時延。文獻[7]提出了一種在MEC中使用排隊網(wǎng)絡(luò)和遺傳算法的有效卸載策略，并與粒子群算法對比在最小化任務(wù)響應(yīng)時延上取得了較好的效果。

文獻[8-10]側(cè)重于對最小化能耗的研究。文獻[8]考慮了前向鏈路和反向鏈路的鏈路狀況，運用離散的人工魚群算法，在時延約束下，最小化能耗。文獻[9]提出了一種車聯(lián)網(wǎng)中的霧云計算卸載算法以最小化車輛和計算設(shè)施的能耗。文獻[10]設(shè)計了一個考慮任務(wù)延遲的MEC系統(tǒng)，提出了一種聯(lián)合優(yōu)化資源分配和任務(wù)卸載分配的策略，用于最小化能耗。

文獻[11-14]側(cè)重于對時延和能耗進行聯(lián)合優(yōu)化。文獻[11]通過為用戶任務(wù)設(shè)置優(yōu)先級，采用均衡傳輸性能的信道分配算法為卸載任務(wù)分配信道資源，實現(xiàn)計算資源最優(yōu)配置，優(yōu)化系統(tǒng)總增益。文獻[12]研究了超密集邊緣網(wǎng)絡(luò)中的依賴關(guān)系任務(wù)卸載問題，提出一種啟發(fā)式算法，在保證子任務(wù)之間依賴關(guān)系的同時，共同優(yōu)化時延和能耗。文獻[13]通過拉格朗日對偶分解將原問題分解成若干個子問題，在通信和計算資源約束下最小化執(zhí)行時延和能耗的加權(quán)和。文獻[14]考慮工業(yè)環(huán)境下的應(yīng)用，采用離散的粒子群算法，使用懲罰函數(shù)來平衡時延與能耗。

通過分析以上研究，不難發(fā)現(xiàn)，文獻[4-7]雖能夠獲得一個較好的時延，但并未充分考慮移動終端的能耗情況，這就會導(dǎo)致低電量設(shè)備仍可能會為滿足最小時延要求，選擇在本地計算，導(dǎo)致電量消耗更快。文獻[8-10]能夠?qū)δ芎倪M行較好的優(yōu)化，延長終端設(shè)備的使用時間，但可能會導(dǎo)致某些對時延敏感的應(yīng)用得不到及時的處理。文獻[11]聯(lián)合考慮了計算時延和能耗，側(cè)重于對單一邊緣服務(wù)器的優(yōu)化，未能充分考慮系統(tǒng)整體的全局優(yōu)化。文獻[12-13]則難以解決多MEC多終端設(shè)備的卸載問題。文獻[14]選用離散的粒子群算法求解時延與能耗的代價函數(shù)，取得了較好的效果，但由于粒子群算法的限制，在迭代后期仍然采用全維度更新策略，在高維問題上難以取得更好的收斂精度，且較容易陷入局部最優(yōu)。

本文則在以上研究的基礎(chǔ)上，考慮到真實環(huán)境中多移動設(shè)備多MEC服務(wù)器的情況，引入云服務(wù)器，從整體角度考慮，將能耗作為懲罰項構(gòu)造代價函數(shù)，使用人工蜂群算法（artificial bee colony algorithm，ABC）[15]聯(lián)合優(yōu)化時延與能耗。

啟發(fā)式算法在MEC卸載領(lǐng)域得到了很好的應(yīng)用[7-8，14]，ABC作為經(jīng)典啟發(fā)式算法，被證明具有良好的全局收斂性[16]，具有收斂精度高，易于跳出局部最優(yōu)等良好性質(zhì)，近年來也在云計算卸載、霧計算卸載等領(lǐng)域獲得較好表現(xiàn)。文獻[17]提出一種混合隊列蟻群和人工蜂群算法以解決移動云計算環(huán)境的任務(wù)分配及卸載，文獻[18]針對智能電網(wǎng)的云霧計算場景，提出了一種混合人工蜂群優(yōu)化算法（HABACO）進行仿真實驗，獲得較好的負載平衡效果。文獻[19]在霧計算場景下利用ABC優(yōu)化適應(yīng)度函數(shù)來優(yōu)化能耗、調(diào)度運行時間等，提升網(wǎng)絡(luò)服務(wù)質(zhì)量。以上研究均取得了較好的表現(xiàn)，但并不適用于MEC環(huán)境下高維、高并發(fā)的計算卸載。

由于蜂群的單維更新策略，導(dǎo)致算法前期在高維問題上收斂速度較慢，后期難以依靠個體本身的位置更新跳出局部最優(yōu)，僅能依靠向偵察蜂轉(zhuǎn)化來增強探索能力，對個體的開發(fā)能力有一定的損失[20]。故本文引入多維更新種群解決此問題，并通過種群間的轉(zhuǎn)化平衡算法的探索和開發(fā)能力，使得算法能夠在任意最大容忍時間限度內(nèi)，獲得較好的卸載方案。

1 系統(tǒng)模型

本文構(gòu)建了一個云服務(wù)器輔助的多設(shè)備移動邊緣計算卸載系統(tǒng)，移動終端設(shè)備或者物聯(lián)網(wǎng)設(shè)備可以通過無線網(wǎng)絡(luò)與MEC服務(wù)器或云服務(wù)器的基站進行通信。假定有M個移動設(shè)備。N個MEC服務(wù)器，1個云服務(wù)器，每一個移動終端產(chǎn)生任務(wù)后，可以在本地進行計算，也可以選擇將任務(wù)卸載至邊緣服務(wù)器或云服務(wù)器，即每一個任務(wù)會有N+2種可能的卸載結(jié)果，其卸載模型如圖1所示。

圖1 卸載系統(tǒng)模型Fig.1 Offloading system model

1.1 本地計算模型

當移動設(shè)備或者物聯(lián)網(wǎng)設(shè)備在本地計算時，其任務(wù)執(zhí)行時間為：

其中Wi表示第i個設(shè)備產(chǎn)生任務(wù)的數(shù)據(jù)量，F(xiàn)local表示該設(shè)備本地計算的能力（每秒CPU周期數(shù)，單位為GHz），Tlocal表示在本地完成任務(wù)所需花費的時間。

本地計算的能耗為：

其中，Tlocal為本地計算的時間，Plocal為本地計算的功率，Elocal為本地計算的能耗。

1.2 卸載計算模型

每一個邊緣移動設(shè)備產(chǎn)生的任務(wù)除了在本地計算外，還可以選擇在邊緣服務(wù)器或者云服務(wù)器進行計算。

當其卸載至邊緣服務(wù)器時，其時延為：

卸載至邊緣服務(wù)器的能耗為：

當其卸載至云服務(wù)器時，其時延為：

卸載至云服務(wù)器的能耗為：

假設(shè)，最終卸載結(jié)果為有a個任務(wù)在本地計算。則在本地計算的最大時延為：

在邊緣端服務(wù)器計算的最大時延為：

則該系統(tǒng)最終時延為：

能耗為：

1.3 代價函數(shù)

將該問題轉(zhuǎn)化為在能耗約束下最小化時延的問題，其總代價計算公式為：

其中g(shù)為懲罰系數(shù)，將當前系統(tǒng)總能耗作為一個懲罰項，以避免系統(tǒng)為最小化時延全部采用本地卸載，從而導(dǎo)致移動設(shè)備電量消耗增多。

2 基于ABC的優(yōu)化

2.1 基本的人工蜂群算法

人工蜂群算法（ABC）是由Karaboga[15]于2005年根據(jù)蜜蜂的采蜜行為提出的一種群智能優(yōu)化算法，ABC算法分為四個階段：初始化階段、雇傭蜂階段、觀察蜂階段、偵察蜂階段。

（1）初始化階段：設(shè)定蜜源數(shù)量SN，問題維度D，最大迭代次數(shù)Gmax，允許最大失敗嘗試次數(shù)limit，然后根據(jù)如下公式隨機初始化一組蜜源位置：

（2）雇傭蜂階段：每只雇傭蜂占據(jù)一個蜜源Xi，并根據(jù)下式進行一維鄰域搜索產(chǎn)生新的位置（候選蜜源）：

其中k∈{1,2,…,SN} ，j為隨機選擇的一個維度，φij是[-1,1]均勻分布的隨機數(shù)[21-22]。所有雇傭蜂完成搜索后，通過搖擺舞[15]的方式向觀察蜂傳遞蜜源位置及蜜源質(zhì)量（適應(yīng)度值）。

（3）觀察蜂階段：觀察蜂根據(jù)雇傭蜂傳遞的信息按下式計算跟隨每一個雇傭蜂的概率，隨后采用輪盤賭來選擇跟隨對象，其概率計算公式如下：

其中fitness i表示第i個蜜源的適應(yīng)度值，適應(yīng)度值越大，表明該蜜源的質(zhì)量越高，其被選擇的概率也越大。而對于最小化問題，其函數(shù)值越小，蜜源越優(yōu)秀，其適應(yīng)度應(yīng)越大，故須按下式轉(zhuǎn)化：

其中f(X i)即表示最小化問題的函數(shù)值，當其為非負數(shù)時應(yīng)取其倒數(shù)，而為避免函數(shù)值趨于0適應(yīng)度趨于無窮的情況發(fā)生，在其前加1后取倒；當其為負數(shù)時應(yīng)取其絕對值，而對于最小化問題，負數(shù)顯然比非負數(shù)更好，非負數(shù)最好的適應(yīng)度為1，則負數(shù)的適應(yīng)度應(yīng)大于1，故在其絕對值前加1。

（4）偵察蜂階段：若蜜源位置超過lim it次循環(huán)都沒有更新，則雇傭蜂會放棄該蜜源轉(zhuǎn)化為偵察蜂，按照公式（12）重新初始化。

2.2 基于邊緣計算模型的編碼調(diào)整

為使人工蜂群算法能夠應(yīng)用于邊緣計算卸載問題，需要建立以下映射關(guān)系，以蜜源位置代表卸載決策，將尋找卸載決策的過程轉(zhuǎn)化為人工蜂群算法尋找蜜源的過程，故需對人工蜂群算法進行離散處理。

假設(shè)移動終端數(shù)量為M，MEC服務(wù)器數(shù)量為N，云服務(wù)器數(shù)量為1，以0號位表示本地計算，1號位，2號位，…，N號位表示在對應(yīng)編號的MEC服務(wù)器中卸載計算，N+1號位表示在云服務(wù)器中卸載計算。對初始化公式（12）進行離散處理得到：

其中randi(N+2)表示隨機產(chǎn)生[1,N+2]上的整數(shù)，此時X ij即為在[0,N+1]的整數(shù)。每一個蜜源X i表示一個1行M列的卸載決策向量，向量中元素的數(shù)值即表示該設(shè)備需要將任務(wù)卸載的位置。

對位置更新公式（13）進行離散處理得到：

其中Y ij表示位移的增量，即位置更新公式中除Xij之外的其他項，[Y ij]表示對Y ij進行四舍五入取整，%為取余，對于公式（13）：

由于X ij和X kj均為[0,N+1]的整數(shù)，且φij在[-1,1]之間，故Y i j在[-N-1,N+1]之間。若[Y ij]=0，則表示仍然在原位置卸載，若[Y ij]＞0，則表示需要將該設(shè)備的計算位置向后移動[Y ij]位，然后對N+2取余，構(gòu)造循環(huán)結(jié)構(gòu)以保證更新后仍然為[0,N+1]的整數(shù)。若[Y ij]＜0則相應(yīng)前移[Y i j]位，最終如公式（17）所示。

例如某一時刻有5個設(shè)備的任務(wù)需要卸載，有3臺邊緣服務(wù)器及一臺云服務(wù)器。則以0表示本地計算，1、2、3分別表示在對應(yīng)編號的邊緣服務(wù)器計算，4表示在云服務(wù)器計算。

首先按式（16）初始化卸載決策向量（蜜源），假設(shè)其中一組卸載決策向量如圖2的A圖，即第一臺設(shè)備將任務(wù)放在本地計算，第二臺設(shè)備將任務(wù)卸載至云服務(wù)器計算，第三臺設(shè)備將任務(wù)卸載至3號邊緣服務(wù)器計算，第四臺設(shè)備將任務(wù)卸載至2號邊緣服務(wù)器計算，第五臺設(shè)備將任務(wù)卸載至1號邊緣服務(wù)器計算。假設(shè)在迭代過程中隨機到第3維（第三臺設(shè)備）進行更新，且[Y ij]=3，代入式（17），則更新后的卸載決策向量如圖2的B圖，第三臺設(shè)備將會在1號邊緣服務(wù)器計算。此時代入代價函數(shù)計算代價，擇優(yōu)選擇，如果更新后的卸載決策更優(yōu)則會替代原卸載決策。

圖2 位置更新演示Fig.2 Location update demo

假設(shè)在下一次迭代時，隨機到第5維（第五臺設(shè)備）更新，且[Y ij]=-3，代入式（17），則更新后的卸載決策向量如圖2的C圖，第五臺設(shè)備將會把任務(wù)卸載至3號邊緣服務(wù)器計算，后續(xù)的過程以此類推。

這樣就完成了對人工蜂群算法的編碼調(diào)整，使得其能夠適用于本系統(tǒng)。

2.3 改進的人工蜂群算法

在MEC系統(tǒng)中，某一時刻需要卸載的任務(wù)數(shù)一般較多，對應(yīng)的問題維度較高，針對高維復(fù)雜問題中人工蜂群算法收斂速度慢，開發(fā)能力弱的缺點，引入多維更新種群，利用種群優(yōu)秀程度差異實現(xiàn)種群的轉(zhuǎn)化，以此動態(tài)調(diào)整兩種群規(guī)模。

2.3.1 單多維更新策略

為了平衡人工蜂群算法的探索與開發(fā)能力，并加快算法前期的收斂速度，在原有單維更新種群的基礎(chǔ)上引入多維更新種群。

對于種群1在雇傭蜂和觀察蜂階段，采用一種精英引導(dǎo)的單維更新策略，文獻[21]將全局最優(yōu)解融入到搜索方程中提出了一種GABC算法，其位置更新公式如下：

其中，Gbest j是全局最優(yōu)個體的第j個元素，ψij是在[0,1.5]上均勻分布的隨機數(shù)。

該算法取得了良好的收斂速度和收斂精度，但在復(fù)雜多模態(tài)問題上易陷入局部最優(yōu)，本文將公式中的最優(yōu)個體更改為精英個體，改進后的公式如下：

其中，Ebest j是從精英個體從隨機選擇的，定義種群中適應(yīng)度前5的個體（最好的5個卸載決策向量）為精英個體。通過向精英個體的學(xué)習(xí)，在迭代前期，精英個體分布較為分散，有利于全局搜索，在迭代后期，精英個體較為集中，有利于局部搜索，提高收斂精度。

基本的人工蜂群算法迭代過程中都基于單一維度進行更新，而單維搜索策略也是限制ABC收斂速度以及后期收斂精度的主要原因，為了解決這一問題，對種群2在雇傭蜂階段引入多維更新策略，觀察蜂階段仍使用式（13），更新的維度數(shù)設(shè)置為D up，按下式進行更新：

其中，φ是一個1行D列的矩陣，其中每一個元素都在[-1,1]之間，根據(jù)更新維度隨機設(shè)置φ中D-Dup個元素為0，此時即表示更新Dup個維度，其余維度不更新，其中Dup會在執(zhí)行動態(tài)種群策略時遞減，·表示矩陣的點乘運算，Y ij的計算與公式（18）相同。

設(shè)定boundary為種群1和種群2的分界，兩種群雇傭蜂總規(guī)模為SN，則編號1到boundary為種群1，boundary+1到SN為種群2，為保證在種群轉(zhuǎn)化后，較差種群仍有一定的搜索能力，設(shè)定一個最小的種群規(guī)模Poplimit，在執(zhí)行動態(tài)種群策略時兩種群的規(guī)模都不得小于這一限制，在每一次迭代過程中其位置更新偽碼如下：

1.fori=1∶boundary

2. 根據(jù)公式（17）和（21），生成新蜜源V i

3. iff(V i)＜f(X i)

4.Xi=V i；count(i)=0

5. else

6.count(i)=count(i)+1

7. end if

8. end for

9.根據(jù)公式（15）計算每一個個體的適應(yīng)度值，并根據(jù)公式（14）計算每一個個體被選中的概率

10.form=1∶boundary

11.輪盤賭選擇跟隨對象，根據(jù)公式（17）和（21），更新位置并重復(fù)步驟3到7

12.end for

13.fori=boundary+1∶SN

14.隨機選擇D up個維度根據(jù)公式（17）和（18），生成新蜜源V i，并重復(fù)步驟3到7

15.end for

16.重復(fù)步驟9

17.form=bound ary+1∶SN

18.輪盤賭選擇跟隨對象，根據(jù)公式（17）和（18），更新位置信息并重復(fù)步驟3到7

19.end for

2.3.2 動態(tài)種群策略

設(shè)定種群優(yōu)秀程度因子（degree of excellence，DOE）用于判斷當前種群的好壞，DOE1和DOE2分別表示種群1和種群2的優(yōu)秀程度。

在算法每一次迭代結(jié)束前進行評估，記錄當前代最優(yōu)個體的索引值index。

若index≤boundary，表明當前代最優(yōu)個體在種群1中，種群1優(yōu)秀程度增加，種群2優(yōu)秀程度減小，即：

若ind ex＞boundary，則當前代最優(yōu)個體在種群2中，種群2優(yōu)秀程度增加，種群1優(yōu)秀程度減小，即：

記錄兩種群優(yōu)秀程度差異difference：

當 |difference|＞d limit時，認為兩種群差異較大，此時執(zhí)行種群轉(zhuǎn)化，此處d lim it取1/4×Gmax。

對于最小化問題，不失一般性，若difference＞0，則表明單維更新種群1更優(yōu)秀，此時將種群2的一部分轉(zhuǎn)化為種群1。為最大化種群轉(zhuǎn)化的收益，對種群2按目標函數(shù)值降序排序，此時種群2排在前面的個體即為較差個體，可以直接進行種群轉(zhuǎn)化，即：

同理，若difference＜0，則表明多維更新種群2更優(yōu)秀，此時將種群1的一部分轉(zhuǎn)化為種群2，對種群1按目標函數(shù)值升序排序，此時種群1排在后面的個體即為較差個體，可以直接進行種群轉(zhuǎn)化，即：

同時在每次轉(zhuǎn)化過程中較差的種群需要向較好的種群進行學(xué)習(xí)，以保證較差種群在后續(xù)迭代過程的尋優(yōu)能力。其學(xué)習(xí)策略如下：

根據(jù)公式（17），則卸載模型中：

rand i為從較差種群中隨機選擇的一個個體，m、n為較好種群中隨機的兩個個體。偽代碼如下：

1.ifind ex≤boundary

2.DOE1=DOE1+1；DOE2=DOE2-1；

3.else

4.DOE1=DOE1-1；DOE2=DOE2+1；

5.end if

6.diff er ence=DOE1-DOE2

7.if |difference|＞dlimit

8.DOE1=0；DOE2=0；

9. ifdifference＞0

10.Dup=round(0.8×Dup)

11. 對種群2按目標函數(shù)值降序排列，并根據(jù)公式（26）更新boundary

12. 從種群2中隨機選擇一個個體根據(jù)公式（17）、（29）、（30）向種群1學(xué)習(xí)

12.else

13. 對種群1按目標函數(shù)值升序排列，并根據(jù)公式（27）更新boundary

14. 從種群1中隨機選擇一個個體根據(jù)公式（17）、（29）、（30）向種群2學(xué)習(xí)

15.end if

16.end if

2.4 算法復(fù)雜度分析

文獻[24]給出ABC算法一次迭代的時間復(fù)雜度為O(SN·D)，其中SN為蜜源數(shù)量，D為問題維度。與ABC算法相比，基于單多維動態(tài)種群策略的人工蜂群算法（artificial bee colony algorithm based on onedimensional and multi-dimensional dynamic population strategy，OMABC）在選擇精英個體、多維更新以及動態(tài)種群轉(zhuǎn)化時引入了額外的計算，為此給出本文算法的時間復(fù)雜度分析。OMABC在一次迭代過程中，選擇精英解（對蜜源質(zhì)量進行排序）的時間復(fù)雜度為O(SN·log(SN))，多維更新的時間復(fù)雜度為O(SN·D)，動態(tài)種群轉(zhuǎn)化（對較差種群的蜜源質(zhì)量進行排序）的時間復(fù)雜度為O(S N·log(SN))，則本文算法的時間度為O(SN·D+SN·log(SN))，而針對高維復(fù)雜問題，D通常遠大于log(SN)，故改進算法的時間復(fù)雜度可簡化為O(SN·D)與ABC算法時間復(fù)雜度相同。

2.5 有效性驗證

為驗證該算法在高維問題上的有效性，使用IEEE CEC 2017中29個測試函數(shù)分別在50維、100維進行實驗，其中F1、F3為單峰函數(shù)，F(xiàn)2因不穩(wěn)定已被CEC官方刪除，F(xiàn)4～F10為簡單多峰函數(shù)，F(xiàn)11～F20為混合函數(shù)，F(xiàn)21～F30為復(fù)合函數(shù)。算法尋優(yōu)結(jié)果越接近各測試函數(shù)最優(yōu)值，表明算法尋優(yōu)能力越強。

將OMABC與經(jīng)典最優(yōu)引導(dǎo)改進算法GABC[21]、ABC/best/1[22]和近些年提出多策略混合算法Modified-ABC[23]、MHABC[24]，進行對比實驗。實驗環(huán)境：處理器AMD Ryzen 7-4700U CPU@2.0 GHz，RAM 16 GB，Windows10 64位操作系統(tǒng)，MATLAB R2018b。設(shè)置50維時Gmax=5 000次，100維時Gmax=8 000次，為保證公平，采用統(tǒng)一方式初始化，每個算法獨立求解29個測試函數(shù)，并記錄最終尋優(yōu)結(jié)果。重復(fù)上述過程30次，計算各算法在29個測試函數(shù)上最終尋優(yōu)結(jié)果的平均值及標準差。OMABC的具體實現(xiàn)步驟如下：

1.初始化算法參數(shù)，包括SN、D、Gmax、limit、boundary等；

2.根據(jù)公式（12）初始化蜜源；

3.按單多維更新策略偽代碼部分，使用式（20）和（22）完成雇傭蜂階段及觀察蜂階段；

4.若蜜源連續(xù)limit次都沒有得到更新，則雇傭蜂放棄該蜜源轉(zhuǎn)化為偵察蜂按式（12）重新初始化；

5.按動態(tài)種群策略部分偽代碼實現(xiàn)種群轉(zhuǎn)化，較差種群通過式（28）向較好種群學(xué)習(xí)；

6.記錄全局最優(yōu)值，判斷是否滿足算法終止條件（是否達到最大迭代次數(shù)），若滿足，則返回最優(yōu)結(jié)果，否則返回步驟3繼續(xù)迭代。

得到的結(jié)果如表1、2所示，加粗部分為最優(yōu)值，表中存在數(shù)值相同但未被加粗的情況，這是因為數(shù)據(jù)采用科學(xué)計數(shù)法統(tǒng)計時存在四舍五入的情況，其真實值會略大于加粗值。實驗結(jié)果表明，在50維時OMACB在15個測試函數(shù)取得最好的收斂的精度。除在F26、F30兩個測試函數(shù)外，OMABC的表現(xiàn)均比原始的ABC效果優(yōu)異，在F4、F5、F7、F8、F16、F20、F21、F22、F25、F28、F30上與對比算法相差不大。

表1 50維ABC及其變種算法結(jié)果比較（平均值±標準差）Table 1 Comparison of 50-dimensional ABC and its variant algorithm results（mean±std.）

而在100維時，29個測試函數(shù)的收斂精度均超過基本的ABC。這是因為，基本ABC的單維更新方式難以在高維問題上發(fā)揮作用，而OMABC的單維與多維更新相互配合的方式，更能適應(yīng)高維復(fù)雜問題，最終在16個測試函數(shù)上取得最優(yōu)，在F4、F8、F16、F20、F23、F24、F27、F28上與對比算法差距不大。這說明單多維動態(tài)種群策略的確能夠提高的算法的尋優(yōu)能力，且在高維問題上更有優(yōu)勢。

圖3為在100維的測試函數(shù)F1中OMABC單維更新種群的種群規(guī)模變化曲線及ABC與OMABC的收斂曲線，其中虛線boundary表示種群1的種群規(guī)模，可以看到在迭代前期，單維更新種群表現(xiàn)更為優(yōu)異，OMABC會相應(yīng)的擴大單維更新種群的規(guī)模，同時由于采用了精英引導(dǎo)策略，在迭代速度方面有更多的優(yōu)勢，而在迭代后期，單一維度的更新已經(jīng)無法滿足算法跳出局部最優(yōu)的需要，此時多維更新種群的表現(xiàn)更好，更多的個體將執(zhí)行多維更新策略，幫助算法跳出局部最優(yōu)，并提高收斂精度。

圖3 收斂曲線及種群1規(guī)模變化曲線Fig.3 Convergence curve and populationa 1 boundary change curve

表2 100維ABC及其變種算法結(jié)果比較（平均值±標準差）Table 2 Comparison of 100-dimensional ABC and its variant algorithm results（mean±std.）

3 仿真實驗

3.1 參數(shù)設(shè)置及算法流程

在驗證改進策略有效性后，將OMABC算法應(yīng)用于第1節(jié)的MEC系統(tǒng)模型上仿真。

同樣選擇在處理器AMD Ryzen 7-4700U CPU@2.0 GHz RAM 16 GB，Windows 10 64位操作系統(tǒng)下使用MATLAB R2018b進行實驗。

MEC系統(tǒng)各項參數(shù)設(shè)置為：移動設(shè)備個數(shù)M={50,100,150,200,250,300}，MEC服務(wù)器個數(shù)N=10，云服務(wù)器個數(shù)為1，算法最大迭代次數(shù)設(shè)置Gmax=100，其他參數(shù)設(shè)置如表3。

表3 MEC系統(tǒng)參數(shù)設(shè)置Table 3 MEC system parameters setting

PSO算法參數(shù)：nPop=50，c1=c2=1.5，ω=0.5；ABC算法參數(shù)設(shè)置為：SN=50，limit=100；OMABC算法參數(shù)設(shè)置為：SN=50，limi t=100，D up=0.8×M，boundary=4/5×SN。

在設(shè)置好系統(tǒng)各項參數(shù)后，還需要確定代價函數(shù)中懲罰系數(shù)g的取值。由于T與E的量綱、數(shù)量級存在差異，故需根據(jù)實驗條件設(shè)置合適的g以平衡代價函數(shù)中時延與能耗的關(guān)系。當任務(wù)全部在本地卸載時，會對移動設(shè)備的性能有較高的要求且會帶來相當高的能耗，減少移動設(shè)備使用時間，此時代價函數(shù)應(yīng)該有一個相當高的代價。

當任務(wù)全部在服務(wù)器上卸載時，將會獲得一個較低的能耗和較高的時延，也應(yīng)有一個較高的代價。這兩個代價應(yīng)盡可能的接近，以使得卸載算法能夠得到合理的卸載決策。此處采用二分法確定g的取值范圍，起始時設(shè)置g分別為0和1，隨機設(shè)置30組全部在本地卸載與30組全部不在本地卸載的決策向量，代入代價函數(shù)后獲取其平均值。隨后逐步縮小g的范圍至[0，0.5]、[0，0.25]、[0，0.125]一直到[0.046 875，0.050 781 25]附近時兩代價曲線已幾乎重合，限于篇幅僅展示部分曲線如圖4所示，故確定g的范圍應(yīng)在0.050 781 25附近，此值可根據(jù)實際情況自行調(diào)整其大小，當希望能耗影響更大時適當取較大值，當希望時延影響更大時則取較小的值，此處取g=0.05以使得時延與能耗具有相近的影響。確定好懲罰系數(shù)g的取值后即可開始仿真實驗，OMABC的具體卸載流程如圖5所示。

圖4 不同g時的代價曲線Fig.4 Cost curve at different g

圖5 算法流程圖Fig.5 Algorithm flow chart

3.2 結(jié)果分析

在上述參數(shù)設(shè)置下，獨立重復(fù)實驗30次，選擇隨機卸載算法（Random）、粒子群算法（PSO）、基本的人工蜂群算法（ABC）與本文的改進算法（OMABC）進行對比。

圖6為在迭代次數(shù)均為100次時，不同卸載算法的收斂曲線，為保證實驗公平，所有算法統(tǒng)一初始化位置。

圖6 不同卸載算法的收斂曲線圖Fig.6 Convergence curves of different offloading algorithms

可以觀察到，各種卸載算法在前20次迭代中都有較快的收斂速度；Random算法，由于采用隨機卸載策略，具有盲目性，在M為50時尚能依賴隨機性尋優(yōu)，但在更高維度（150維度及以上）時，已幾乎趨于直線，喪失尋優(yōu)能力。這是由于高維問題更為復(fù)雜，隨機尋找缺乏目標，有利維度的信息無法保留導(dǎo)致的。

PSO算法通過向個體最優(yōu)以及全局最優(yōu)學(xué)習(xí)，在前10次迭代中取得了更好的表現(xiàn)，在M為50、100、150、250、300時具有較快的收斂速度，超過了基于的ABC的卸載算法；觀察PSO的迭代曲線不難發(fā)現(xiàn)，粒子群算法由于每次位置更新均為全維度更新，迭代曲線呈現(xiàn)階梯狀，這就對算法的迭代次數(shù)有很高的要求，需要設(shè)置合適的迭代次數(shù)以最大化收益，且由于其沒有跳出局部最優(yōu)的操作，算法后期也很難跳出局部最優(yōu)位置。

ABC算法則有較為平滑的迭代曲線，沒有明顯的階梯狀，這是由算法的單維更新策略以及偵察蜂階段所保證的，算法一維一維的緩慢向最優(yōu)位置附近挪動，有效利用了優(yōu)秀位置的維度信息，且不易陷入局部最優(yōu)，能夠較為平穩(wěn)的尋優(yōu)。同時單維更新策略也是制約算法在高維問題上收斂速度的主要因素，如在M為250、300時，算法在第30次迭代后尋優(yōu)精度才高過PSO算法。

而OMABC除擁有較強跳出局部最優(yōu)的能力外，還具有較快的收斂速度，在迭代后期仍具備較強的尋優(yōu)能力，這是由于OMABC采用了動態(tài)種群策略以及精英引導(dǎo)學(xué)習(xí)，能夠自適應(yīng)判斷種群的好壞從而實現(xiàn)單維更新種群以及多維更新種群之間的相互轉(zhuǎn)換，平衡算法的探索和開發(fā)能力，提高收斂速度和收斂精度。在迭代前期，兩種群經(jīng)歷一定時間的獨立尋優(yōu)后，能夠自適應(yīng)的擴大優(yōu)秀種群的規(guī)模，從而加快算法前期收斂速度。在迭代后期，OMABC又具有人工蜂群算法不易陷入局部最優(yōu)的良好性質(zhì)，同時又可以自適應(yīng)的判斷當前尋優(yōu)的狀態(tài)，若距離最優(yōu)位置較近，則擴大單維更新種群，提高收斂精度；若所處位置為局部最優(yōu)位置，則擴大多維更新種群，進一步提高算法跳出局部最優(yōu)的能力。

從圖6中可以看出M=50時，Random算法優(yōu)化后系統(tǒng)總代價降低了7.43%，PSO算法優(yōu)化后系統(tǒng)總代價降低了12.37%，ABC算法優(yōu)化后系統(tǒng)總代價降低了18.76%，OMABC算法優(yōu)化后系統(tǒng)總代價降低了21.60%。

在M=100時，Random算法優(yōu)化后系統(tǒng)總代價降低了1.85%，PSO算法優(yōu)化后系統(tǒng)總代價降低了9.61%，ABC算法優(yōu)化后系統(tǒng)總代價降低了15.80%，OMABC算法優(yōu)化后系統(tǒng)總代價降低了18.28%。

在M=150時，Random算法優(yōu)化后系統(tǒng)總代價降低了0.21%，PSO算法優(yōu)化后系統(tǒng)總代價降低了5.81%，ABC算法優(yōu)化后系統(tǒng)總代價降低了10.79%，OMABC算法優(yōu)化后系統(tǒng)總代價降低了11.29%。

在M=200時，Random算法優(yōu)化后系統(tǒng)總代價降低了1.86%，PSO算法優(yōu)化后系統(tǒng)總代價降低了8.66%，ABC算法優(yōu)化后系統(tǒng)總代價降低了10.98%，OMABC算法優(yōu)化后系統(tǒng)總代價降低了12.53%。

在M=250時，Random算法優(yōu)化后系統(tǒng)總代價降低了2.25%，PSO算法優(yōu)化后系統(tǒng)總代價降低了9.20%，ABC算法優(yōu)化后系統(tǒng)總代價降低了11.71%，OMABC算法優(yōu)化后系統(tǒng)總代價降低了14.29%。

在M=300時，Random算法優(yōu)化后系統(tǒng)總代價降低了1.13%，PSO算法優(yōu)化后系統(tǒng)總代價降低了7.55%，ABC算法優(yōu)化后系統(tǒng)總代價降低了9.45%，OMABC算法優(yōu)化后系統(tǒng)總代價降低了11.16%。

除M=50外，其他情況下各算法降低的代價都相對穩(wěn)定，這是由于50維的問題較為簡單，各算法均能獲得更好的解，而其他情況下問題維度更高，尋優(yōu)難度提升導(dǎo)致的。同時，不難看出OMABC在各情況均取得了最好的效果。

如圖7為在相同的迭代次數(shù)下獨立運行30次得到的箱線圖，箱體中位線表示算法30次運行的中位數(shù)，反應(yīng)了數(shù)據(jù)的一般水平，箱體的上下邊界稱為內(nèi)限，分別表示數(shù)據(jù)的上四分位和下四分位，因此箱體的寬度可以在一定程度上反應(yīng)算法的穩(wěn)定性。超出箱體上方和下方的之外的界限稱為外限，分別表示樣本數(shù)據(jù)剔除異常值后的最大值和最小值（1.5 IQR內(nèi)的范圍）。

圖7 不同卸載算法的箱線圖Fig.7 Box plots of different offloading algorithms

可以看出OMABC算法，在設(shè)備數(shù)為50、100、150、200、300時箱體寬度均比對比算法小，具有較好的穩(wěn)定性，在設(shè)備數(shù)為250時，OMABC的箱體寬度與ABC近似，表明穩(wěn)定性與ABC算法近似。綜上可以證明OMABC在解決此類問題上具有較好的穩(wěn)定性。從整體上看，OMABC箱體所處位置較其他算法更低具有較好的收斂精度。

如圖8為在不同設(shè)備個數(shù)的情況下，30次獨立運行后不同卸載策略的平均代價柱狀圖，其中Local表示在本地計算。實驗中設(shè)備個數(shù)M分別為50、100、150、200、250、300，可以觀察到隨著設(shè)備數(shù)量的增加本地卸載策略的系統(tǒng)總代價增加較為明顯，這是任務(wù)數(shù)量增多而又沒有得到有效卸載導(dǎo)致的。采用Random、PSO、ABC、OMABC算法卸載后的系統(tǒng)總代價較本地計算更低，減少了系統(tǒng)的時延與能耗。

圖8 不同設(shè)備數(shù)下各算法代價Fig.8 Cost of each algorithm under different M

OMABC與本地計算的差異也隨著設(shè)備數(shù)的增加在逐漸增大，在M為50時，系統(tǒng)代價平均降低了113.87；M為100時，系統(tǒng)代價平均降低了134.02；M為150時，系統(tǒng)代價平均降低了153.95；M為200時，系統(tǒng)代價平均降低了170.49；M為250時，系統(tǒng)代價平均降低了199.39；M為300時，系統(tǒng)代價平均降低了218.86；在不同設(shè)備數(shù)M下均能取得更為優(yōu)秀的效果，驗證了OMABC算法在解決此類問題上的優(yōu)越性。

4 結(jié)束語

本文針對多設(shè)備MEC系統(tǒng)中計算任務(wù)的執(zhí)行時間以及終端設(shè)備的能耗最小化問題，構(gòu)建了一個云服務(wù)器輔助的多MEC服務(wù)器計算卸載模型，并提出了一種改進的人工蜂群算法（OMABC），通過單維更新種群和多維更新種群的相互轉(zhuǎn)化與配合，提高算法的收斂精度，并在CEC 2017進行測試，驗證了算法的有效性。通過添加懲罰因子，設(shè)計代價函數(shù)，將OMABC運用在移動邊緣計算卸載問題上，實現(xiàn)了在能耗約束下最小化時延的目標。仿真結(jié)果表明，與Random、PSO、ABC相比，本文的OMABC算法具有更好的卸載性能。未來的研究將進一步優(yōu)化人工蜂群算法，考慮任務(wù)的前驅(qū)和后繼結(jié)點，將其運用在MEC中基于工作流的任務(wù)卸載問題上。