多設(shè)備多任務(wù)場(chǎng)景下基于改進(jìn)粒子群優(yōu)化的計(jì)算卸載策略

蔣鵬，富爽，丁晨陽(yáng)

（黑龍江八一農(nóng)墾大學(xué)信息與電氣工程學(xué)院，大慶 163319）

隨著移動(dòng)互聯(lián)網(wǎng)和芯片技術(shù)的發(fā)展，終端設(shè)備及其應(yīng)用數(shù)據(jù)不斷增多，用戶(hù)對(duì)計(jì)算資源的需求也越來(lái)越大。針對(duì)本地設(shè)備計(jì)算資源不足的問(wèn)題，業(yè)界引出了移動(dòng)云計(jì)算（Mobile cloud computing，MCC）這一解決方案，移動(dòng)云計(jì)算通過(guò)將任務(wù)傳輸?shù)皆朴?jì)算中心，經(jīng)計(jì)算能力充足的遠(yuǎn)程數(shù)據(jù)中心計(jì)算后，再將計(jì)算結(jié)果返回到本地設(shè)備上，有效地解決了本地設(shè)備計(jì)算資源缺乏的問(wèn)題[1]。但近年來(lái)，本地設(shè)備上新型計(jì)算任務(wù)不斷增加，如虛擬現(xiàn)實(shí)、增強(qiáng)現(xiàn)實(shí)，以及自動(dòng)駕駛和在線(xiàn)游戲等[2-3]，對(duì)計(jì)算能力和網(wǎng)絡(luò)傳輸時(shí)延提出了更高的要求，通常需要強(qiáng)大的計(jì)算能力處理，并以極低的時(shí)延返回結(jié)果[4]。對(duì)于移動(dòng)云計(jì)算方案，雖然運(yùn)行穩(wěn)定可靠[5]，但由于其服務(wù)器部署于遠(yuǎn)程數(shù)據(jù)中心，網(wǎng)絡(luò)傳輸時(shí)延高，因此無(wú)法處理這類(lèi)任務(wù)[6-7]。在2014 年，針對(duì)新型任務(wù)，業(yè)界提出了移動(dòng)邊緣計(jì)算（Mobile edge compute，MEC）這一最新解決方案[8-9]，其核心思想是將計(jì)算資源部署于網(wǎng)絡(luò)邊緣，以獲得更低的網(wǎng)絡(luò)傳輸時(shí)延[10-11]，從而滿(mǎn)足新型任務(wù)的運(yùn)行要求。

移動(dòng)邊緣計(jì)算作為第五代移動(dòng)通信技術(shù)（5 th ceneration mobile communication technology，5 G）的關(guān)鍵技術(shù)[12-13]，解決了計(jì)算與傳輸?shù)臅r(shí)延問(wèn)題，同時(shí)降低了本地設(shè)備的能量消耗。計(jì)算卸載技術(shù)是移動(dòng)邊緣計(jì)算的關(guān)鍵技術(shù)，如何合理卸載任務(wù)以及合理進(jìn)行資源分配，以降低MEC 系統(tǒng)的卸載成本，提升用戶(hù)的邊緣計(jì)算體驗(yàn)，是MEC 網(wǎng)絡(luò)中需要解決的關(guān)鍵問(wèn)題。為降低MEC 的卸載成本，如能耗和時(shí)延，學(xué)者們對(duì)此進(jìn)行了深入的研究。余翔等[14]聯(lián)合優(yōu)化任務(wù)卸載決策和設(shè)備傳輸功率，使用非合作博弈論優(yōu)化卸載決策，使用二分搜索法優(yōu)化傳輸功率，此方法提高了系統(tǒng)的卸載性能，文獻(xiàn)的模型建立在多用戶(hù)單任務(wù)場(chǎng)景下，暫未對(duì)計(jì)算資源進(jìn)行優(yōu)化。Lan X 等[15]在多設(shè)備單服務(wù)器場(chǎng)景下聯(lián)合優(yōu)化資源分配、設(shè)備傳輸功率和帶寬，使得時(shí)延和能耗的加權(quán)和最小，利用拉格朗日對(duì)偶分解將原問(wèn)題分解為多個(gè)子問(wèn)題，并逐一解決，還證明時(shí)延和能耗之間存在內(nèi)在的權(quán)衡關(guān)系，如果放寬時(shí)延要求，則本地設(shè)備可以得到更低的能量消耗。Liu J 等[16]將卸載和功率優(yōu)化問(wèn)題建模，為計(jì)算開(kāi)銷(xiāo)最小化的混合整數(shù)非線(xiàn)性規(guī)劃問(wèn)題，并使用提出的功率控制和卸載子算法求解該問(wèn)題，仿真結(jié)果證明了該方法的有效性，但文獻(xiàn)暫未考慮MEC 系統(tǒng)中的計(jì)算資源分配問(wèn)題。Fang F 等[17]通過(guò)優(yōu)化傳輸功率和任務(wù)在本地設(shè)備與服務(wù)器執(zhí)行的分配比來(lái)最小化延遲，并將該非凸問(wèn)題轉(zhuǎn)化為等價(jià)的擬凸問(wèn)題，使用二分搜索迭代算法求解，與文獻(xiàn)［16］相同，文獻(xiàn)假設(shè)MEC 服務(wù)器的資源是沒(méi)有限制的，暫未考慮計(jì)算資源分配，同時(shí)忽略了任務(wù)在服務(wù)器上的執(zhí)行時(shí)延。羅斌等[18]提出了一種基于粒子群優(yōu)化算法的計(jì)算卸載策略，將計(jì)算卸載問(wèn)題建模為能耗約束下的時(shí)延最小化問(wèn)題，并使用粒子群優(yōu)化算法對(duì)卸載決策變量進(jìn)行求解，降低了MEC 系統(tǒng)的時(shí)延，但該文獻(xiàn)僅優(yōu)化了計(jì)算卸載位置，沒(méi)有考慮任務(wù)MEC 計(jì)算資源的分配問(wèn)題。朱思峰等[19]綜合考慮任務(wù)時(shí)延和本地設(shè)備的能耗，對(duì)計(jì)算卸載問(wèn)題進(jìn)行建模，并采用改進(jìn)的粒子群算法來(lái)求解，仿真表明其卸載決策結(jié)果優(yōu)于標(biāo)準(zhǔn)粒子群算法以及遺傳算法，文獻(xiàn)對(duì)單個(gè)用戶(hù)的計(jì)算卸載位置進(jìn)行優(yōu)化，將MEC 服務(wù)器資源全部分配至某一任務(wù)。在以上研究中，學(xué)者們對(duì)任務(wù)的卸載策略進(jìn)行了優(yōu)化，能夠達(dá)到降低系統(tǒng)時(shí)延或能耗的目的，但仍有需要進(jìn)一步研究考慮的地方。文獻(xiàn)［14，16，17，18］通過(guò)最小化計(jì)算開(kāi)銷(xiāo)，得到了較好的卸載策略，但暫未考慮計(jì)算卸載中的計(jì)算資源分配問(wèn)題。文獻(xiàn)［14，15，19］降低了計(jì)算卸載時(shí)延，但缺少對(duì)多用戶(hù)、多任務(wù)或多服務(wù)器場(chǎng)景的模型建立。在實(shí)際的邊緣計(jì)算場(chǎng)景中，MEC 服務(wù)器必定部署于設(shè)備較多的地方，以提高其使用率，因此單用戶(hù)并不符合實(shí)際部署場(chǎng)景。此外，由于多種新型任務(wù)的出現(xiàn)，本地設(shè)備上需要處理多個(gè)計(jì)算任務(wù)，對(duì)于大型任務(wù)，也可將其拆解為多個(gè)子任務(wù)，因此單任務(wù)不符合本地設(shè)備上的任務(wù)實(shí)際情況。綜上所述，對(duì)于多用戶(hù)、多任務(wù)、多服務(wù)器場(chǎng)景下的任務(wù)卸載和資源分配問(wèn)題，目前的研究較少。如何建立其系統(tǒng)模型，并得到合理的卸載決策和資源分配策略，降低MEC系統(tǒng)的卸載成本，是移動(dòng)邊緣計(jì)算領(lǐng)域中亟待解決的問(wèn)題。

研究對(duì)于多設(shè)備、多任務(wù)場(chǎng)景下的計(jì)算卸載問(wèn)題，主要貢獻(xiàn)如下：

（1）結(jié)合本地設(shè)備的能量信息及充電狀態(tài)信息，綜合考慮能耗和時(shí)延卸載成本，通過(guò)充電狀態(tài)與能量信息自適應(yīng)調(diào)整時(shí)延能耗權(quán)重，結(jié)合服務(wù)器任務(wù)均衡，設(shè)置總代價(jià)數(shù)學(xué)表達(dá)式，建立多用戶(hù)、多任務(wù)、多服務(wù)器場(chǎng)景下的MEC 計(jì)算卸載系統(tǒng)模型。

（2）對(duì)傳統(tǒng)粒子群算法中的慣性因子和學(xué)習(xí)因子進(jìn)行了改進(jìn)，各粒子獨(dú)立更新因子數(shù)值，而不是所有粒子使用相同的因子，在算法迭代過(guò)程中按照一定的方法動(dòng)態(tài)更新因子數(shù)值，采用改進(jìn)的粒子群算法對(duì)卸載決策和資源分配變量進(jìn)行求解，最終獲得最優(yōu)的卸載決策和資源分配方案。

1 系統(tǒng)模型

系統(tǒng)模型如圖1 所示。在一個(gè)多個(gè)用戶(hù)和多個(gè)MEC 服務(wù)器的MEC 網(wǎng)絡(luò)中，有多個(gè)用戶(hù)，即本地設(shè)備有任務(wù)計(jì)算需求，多個(gè)MEC 服務(wù)器可為用戶(hù)提供計(jì)算服務(wù)。本地設(shè)備同時(shí)有多個(gè)計(jì)算任務(wù)需要計(jì)算，任務(wù)可在本地設(shè)備執(zhí)行或卸載到MEC 服務(wù)器進(jìn)行計(jì)算。本地設(shè)備通過(guò)無(wú)線(xiàn)的方式連接到基站，MEC 服務(wù)器部署于基站處，本地設(shè)備與基站通過(guò)無(wú)線(xiàn)直連，此種部署方式可使得任務(wù)數(shù)據(jù)傳輸?shù)椒?wù)器的跳數(shù)最少，有利于減少通信延時(shí)。

圖1 多用戶(hù)多服務(wù)器場(chǎng)景下的系統(tǒng)模型Fig.1 System model in multi-user and multi-server scenarios

假設(shè)場(chǎng)景模型中包含N 個(gè)本地設(shè)備，本地設(shè)備序號(hào)n∈｛1，2，…，N｝，M 個(gè)MEC 服務(wù)器，MEC 服務(wù)器序號(hào)m∈｛1，2，…，M｝。在一個(gè)決策周期內(nèi)，每個(gè)本地設(shè)備產(chǎn)生一個(gè)或多個(gè)需要計(jì)算的任務(wù)。設(shè)本地設(shè)備n 共產(chǎn)生Kn個(gè)任務(wù)需要計(jì)算，任務(wù)數(shù)Kn∈｛1，2，…，K｝，K 為產(chǎn)生任務(wù)最多的本地設(shè)備產(chǎn)生的任務(wù)數(shù)。設(shè)第n 個(gè)設(shè)備的第i 個(gè)任務(wù)為K｝，其屬性可表示為一個(gè)二元組其中代表該任務(wù)的數(shù)據(jù)量代表該任務(wù)的計(jì)算量。每一任務(wù)可以分配到某一MEC 服務(wù)器或在本地進(jìn)行計(jì)算，則每個(gè)任務(wù)共M+1 種分配選擇，所有任務(wù)的分配選擇構(gòu)成卸載決策向量表示著第n 個(gè)設(shè)備上第i 個(gè)任務(wù)是否卸載到MEC 服務(wù)器表示任務(wù)卸載到MEC 服務(wù)器m 執(zhí)行=0，表示任務(wù)沒(méi)有卸載到MEC 服務(wù)器m，此時(shí)任務(wù)可能在本地設(shè)備上執(zhí)行，也可能卸載到了其他MEC 服務(wù)器。若任務(wù)分配到MEC 服務(wù)器，則需要為任務(wù)分配CPU 計(jì)算資源。各MEC 服務(wù)器為各任務(wù)分配的CPU 資源數(shù)量，構(gòu)成資源分配向量為表示MEC 服務(wù)器m 為第n 個(gè)設(shè)備上第i 個(gè)任務(wù)所分配的CPU 資源大小，單位為GHz。表1 詳細(xì)列出了參數(shù)符號(hào)含義。

表1 參數(shù)符號(hào)及意義Table 1 Parameter symbols and meanings

1.1 本地計(jì)算模型

當(dāng)某一任務(wù)在本地執(zhí)行時(shí)，任務(wù)的本地計(jì)算時(shí)延等于任務(wù)本地執(zhí)行時(shí)間，任務(wù)的計(jì)算能耗為任務(wù)本地執(zhí)行時(shí)所消耗的能量。

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

1.1.2 本地計(jì)算能耗

本地設(shè)備的能耗主要為任務(wù)計(jì)算期間設(shè)備自身的CPU 能量消耗，采用經(jīng)典能耗計(jì)算模型來(lái)計(jì)算CPU 能耗，即E=εf3t[20]，其中ε 為與本地設(shè)備芯片架構(gòu)有關(guān)的能耗因子，則任務(wù)在本地執(zhí)行的本地計(jì)算能耗為：

1.2 邊緣計(jì)算模型

當(dāng)任務(wù)卸載到MEC 服務(wù)器執(zhí)行時(shí)，任務(wù)的計(jì)算總時(shí)延分為任務(wù)傳輸時(shí)延、MEC 服務(wù)器執(zhí)行時(shí)延和結(jié)果傳輸時(shí)延。由于結(jié)果數(shù)據(jù)往往不大，其傳輸時(shí)延遠(yuǎn)遠(yuǎn)小于上載任務(wù)傳輸時(shí)延和MEC 服務(wù)器執(zhí)行時(shí)延，因此忽略結(jié)果傳輸時(shí)延[21-22]。任務(wù)的邊緣計(jì)算能耗為任務(wù)傳輸時(shí)所消耗的能量。

1.2.1 邊緣計(jì)算時(shí)延

其中，W 為帶寬大小，σ2為信道噪聲功率。

1.2.2 邊緣計(jì)算能耗

當(dāng)任務(wù)數(shù)據(jù)卸載到服務(wù)器上計(jì)算時(shí)，能耗主要包括本地設(shè)備的上傳能耗和服務(wù)器計(jì)算能耗。由于服務(wù)器是電纜供電，不考慮服務(wù)器能耗，只考慮大多數(shù)采用電池供電的用戶(hù)端能耗，則任務(wù)的邊緣計(jì)算能耗為：

1.3 卸載問(wèn)題模型

1.3.1 性能模型

其中，λn為設(shè)備n 的時(shí)延權(quán)重因子，1-λn為設(shè)備n 的能耗權(quán)重因子，λn∈｛0，1｝。λn一般為固定參數(shù)，可表示系統(tǒng)對(duì)時(shí)延和能耗的敏感程度，若對(duì)時(shí)延敏感，則λn較大，反之較小。

1.3.2 結(jié)合充電狀態(tài)的權(quán)重自適應(yīng)

對(duì)于反映時(shí)延和能耗的權(quán)重因子λn，與能量的敏感度和本地設(shè)備的剩余電量有關(guān)[24]。當(dāng)本地設(shè)備剩余電量較低時(shí)，用戶(hù)更希望降低處理任務(wù)的能耗，而放寬時(shí)延要求，對(duì)能量更敏感，則λn較小。當(dāng)剩余電量較高時(shí)，用戶(hù)希望處理任務(wù)的時(shí)延降低，而放寬能耗要求，以達(dá)到最好的用戶(hù)體驗(yàn)，此時(shí)λn較大。因此，λn與設(shè)備的剩余電量比 成正比。設(shè)用戶(hù)本地設(shè)備n 的當(dāng)前電量為Bn，電池能容納的總電量為，則本地設(shè)備當(dāng)前的剩余電量比為，令：

其中，φ 為比例系數(shù)，用于調(diào)整λn與設(shè)備的剩余電量比 的比例偏好。

此外，設(shè)備的充電狀態(tài)也會(huì)影響時(shí)延和能耗的權(quán)重。若本地設(shè)備處于充電狀態(tài)，則不太注重設(shè)備的能耗，此時(shí)時(shí)延權(quán)重因子λn增大；若本地設(shè)備未處于充電狀態(tài)，則不做任何處理。假設(shè)本地設(shè)備n 的充電狀態(tài)定義為，若=1 時(shí)，設(shè)備處于充電狀態(tài)，反之設(shè)備處于未充電狀態(tài)。結(jié)合之前的剩余電量比，令：

1.3.3 問(wèn)題描述

綜上，問(wèn)題可描述為在時(shí)延能耗權(quán)重自適應(yīng)的情況下，如何聯(lián)合優(yōu)化卸載決策和資源分配，使系統(tǒng)總代價(jià)最低，問(wèn)題可表示如下。

如果MEC 服務(wù)器m 性能較好，大量用戶(hù)的任務(wù)都卸載到MEC 服務(wù)器m，會(huì)造成服務(wù)器m 的負(fù)載過(guò)高，因此需要考慮任務(wù)分配至各服務(wù)器的公平性問(wèn)題，以讓其他服務(wù)器來(lái)均衡負(fù)載。對(duì)于每一臺(tái)MEC服務(wù)器m，令分配到服務(wù)器上的總計(jì)算量與其計(jì)算能力相匹配，將分配到服務(wù)器的任務(wù)計(jì)算量占所有任務(wù)總計(jì)算量的比值，與服務(wù)器m 的計(jì)算能力占所有服務(wù)器計(jì)算能力的比值之差定義為公平度，公平度應(yīng)盡可能小。定義blance（A）為公平修正函數(shù)，表示卸載策略與公平度的關(guān)系，如式（16）所示：

由此，用公平修正函數(shù)來(lái)修正系統(tǒng)總代價(jià)，問(wèn)題P1 更新為：

2 改進(jìn)的PSO 算法優(yōu)化求解

問(wèn)題P2 是一個(gè)混合整數(shù)非線(xiàn)性規(guī)劃問(wèn)題，由于卸載策略變量和資源分配變量耦合，是一個(gè)NP 難問(wèn)題，無(wú)法用傳統(tǒng)的凸優(yōu)化理論解決。對(duì)于此類(lèi)問(wèn)題，智能群體算法能夠通過(guò)啟發(fā)式搜索解空間得到問(wèn)題的較優(yōu)解[25]。采用改進(jìn)的粒子群算法（Particle swarm optimization，PSO）來(lái)解決以上問(wèn)題。PSO 算法向大自然中鳥(niǎo)群捕食行為學(xué)習(xí)，將鳥(niǎo)群抽象為粒子群，將食物源表征為要尋找的最優(yōu)解，在一個(gè)空間范圍內(nèi)，粒子間共享信息，每一個(gè)粒子根據(jù)自我認(rèn)知和社會(huì)經(jīng)驗(yàn)搜索解空間，得到最優(yōu)解。

2.1 粒子編碼

設(shè)粒子的個(gè)數(shù)為L(zhǎng)，粒子序號(hào)l∈｛1，2，3，…，L｝，本地設(shè)備個(gè)數(shù)為N，本地設(shè)備n 所產(chǎn)生的任務(wù)個(gè)數(shù)為Kn，n∈｛1，2，…，N｝，用矩陣A=［an，i］N×K和F=［fn，i］N×K表示粒子的運(yùn)動(dòng)位置，其中矩陣A 描述任務(wù)卸載決策，矩陣F 描述任務(wù)的資源分配情況。矩陣A 的元素值an，i表示任務(wù)的卸載決策，an，i∈｛0，1，2，…，M｝，當(dāng)an，i=m 時(shí)，代表本地設(shè)備n 的第i 個(gè)任務(wù)分配的MEC服務(wù)器編號(hào)為m，當(dāng)an，i=0 時(shí)，代表將任務(wù)分配到本地設(shè)備。矩陣F 的元素值表示資源分配數(shù)量，矩陣F的元素值fn，i代表MEC 服務(wù)器給第i 個(gè)任務(wù)分配的計(jì)算資源量，單位為GHz?？紤]到每個(gè)本地設(shè)備產(chǎn)生的任務(wù)數(shù)不一定相同，將設(shè)備最大任務(wù)數(shù)K 作為矩陣A 和F 的列數(shù)，若Kn＜K，令an，i=-1，fn，i=-1，其中Kn＜i≤K，表示此處并無(wú)相關(guān)任務(wù)。

在卸載決策矩陣A 中，粒子采用整數(shù)編碼，在資源分配矩陣F 中，采用實(shí)數(shù)編碼。如圖2 所示，若A矩陣中an，i=［0 3 3 1］，i=1，2，3,4，即表示第n 個(gè)設(shè)備上第1～4 個(gè)任務(wù)的執(zhí)行位置，“0”代表此任務(wù)在本地設(shè)備執(zhí)行，“3 3 1”分別代表第2～4 個(gè)任務(wù)在第3、3、1 號(hào)MEC 服務(wù)器上執(zhí)行。

圖2 編碼矩陣示意圖Fig.2 Schematic diagram of coding matrix

用矩陣V1=［v1，n，i］N×K和V2=［v2，n，i］N×K分別表示粒子的卸載決策和資源分配運(yùn)動(dòng)趨向。矩陣V1的值v1，n，i表示為任務(wù)分配的MEC 服務(wù)器編號(hào)的運(yùn)動(dòng)趨向，矩陣V2的值v2，n，i代表服務(wù)器給任務(wù)分配的計(jì)算資源量的運(yùn)動(dòng)趨向。

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

將問(wèn)題P2 的目標(biāo)函數(shù)作為算法的適應(yīng)度函數(shù)，表示系統(tǒng)總代價(jià)Y 的大小。

2.3 算法詳情

在粒子群算法中，粒子的位置代表一個(gè)可行解。在粒子搜索解的過(guò)程中，通過(guò)每次迭代計(jì)算各粒子運(yùn)動(dòng)的下一位置，直到收斂到最優(yōu)位置。粒子位置的更新由上次位置和粒子的速度決定，算法核心是粒子位置和速度的迭代更新方法。速度更新受慣性速度、自身認(rèn)知經(jīng)驗(yàn)和社會(huì)經(jīng)驗(yàn)三大方面影響，每一方面對(duì)應(yīng)一個(gè)因子，即慣性因子w 和學(xué)習(xí)因子c1、c2。改進(jìn)的粒子群算法通過(guò)在迭代過(guò)程中動(dòng)態(tài)改變各因子的值，達(dá)到優(yōu)化粒子群算法的目的。

若粒子第t+1 次迭代的速度為Vt+1，其更新公式為：

其中，t 表示更新迭代次數(shù)，rand（）為隨機(jī)函數(shù)，Pbest為粒子當(dāng)前搜索到的最優(yōu)解，Gbest為全體粒子當(dāng)前搜索到的最優(yōu)解。為保證算法的前期全局收斂能力和后期局部收斂能力，應(yīng)在算法迭代過(guò)程中減小慣性因子w 的數(shù)值。令慣性因子w 動(dòng)態(tài)更新，其更新公式為：

其中，t 和tmax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)，L 為粒子個(gè)數(shù)，α，β 均為系數(shù)，可以根據(jù)w 的最優(yōu)初值來(lái)調(diào)整。更新公式能夠?qū)崿F(xiàn)在粒子運(yùn)動(dòng)前期慣性因子w 較大，使算法具有較強(qiáng)的全局收斂能力，而隨著運(yùn)動(dòng)中后期迭代次數(shù)的增加，w 非線(xiàn)性減小，使得算法具有較強(qiáng)的局部收斂能力。同時(shí)，將粒子數(shù)量L 作為影響w 的因素，當(dāng)粒子數(shù)量較大時(shí)，適當(dāng)減小w 的值，以防止粒子路徑重復(fù)，當(dāng)粒子數(shù)量較小時(shí)，適當(dāng)增大w 的值，增加全局收斂能力，防止粒子路徑長(zhǎng)度不夠，導(dǎo)致算法局部收斂。

學(xué)習(xí)因子c1、c2分別描述自身認(rèn)知經(jīng)驗(yàn)和社會(huì)經(jīng)驗(yàn)對(duì)粒子速度的影響程度，動(dòng)態(tài)更新c1、c2，根據(jù)每次迭代中粒子適應(yīng)度值的比較，動(dòng)態(tài)減小或增加粒子下一次迭代中c1、c2的值。其更新公式分別為：

其中，Yt、Ypbest和Ygbest分別為粒子第t 次更新時(shí)的適應(yīng)值、粒子當(dāng)前最優(yōu)解的適應(yīng)值和全局最優(yōu)解對(duì)應(yīng)的適應(yīng)值，t 表示更新次數(shù)，η，θ 均為系數(shù)，可以調(diào)整增量比例。公式21 表示，當(dāng)粒子第t 次更新時(shí)的適應(yīng)值比上一次的個(gè)體最優(yōu)解的適應(yīng)值小時(shí)，適當(dāng)增加粒子第t+1 次更新時(shí)的c1，即反之適當(dāng)減小此操作表示優(yōu)良粒子會(huì)增加粒子自身經(jīng)驗(yàn)影響力，其他粒子則依賴(lài)粒子群的社會(huì)經(jīng)驗(yàn)。公式22 表示當(dāng)粒子第t 次更新時(shí)，若個(gè)體最優(yōu)解的適應(yīng)值小于全局最優(yōu)解對(duì)應(yīng)的適應(yīng)值，適當(dāng)減小粒子l 的第t+1次更新時(shí)的c2，即，反之增加此操作表示優(yōu)良粒子會(huì)減小社會(huì)經(jīng)驗(yàn)對(duì)粒子下一次速度的影響程度，信任自身認(rèn)知經(jīng)驗(yàn)，而其他粒子的社會(huì)經(jīng)驗(yàn)影響程度也會(huì)增加，使得粒子靠向全局最優(yōu)解。為了防止粒子過(guò)度自信或者過(guò)度依賴(lài)，設(shè)置c1和c2的變化范圍，即

粒子的位置更新公式為：

為了避免公式計(jì)算得到的粒子速度過(guò)大或過(guò)小，對(duì)于V1，將粒子最小速度限制為，最大速度限制為；對(duì)于V2，將粒子最小速度限制為最大速度限制為。而在根據(jù)速度公式計(jì)算粒子下一次的位置時(shí)，可能會(huì)超過(guò)位置邊界，其數(shù)值不一定合理，為避免越界現(xiàn)象的發(fā)生，對(duì)于A，將粒子的最小位置限制為Amin，將粒子的最大位置限制為Amax；對(duì)于F，將粒子的最小位置限制為Fmin，粒子最大位置限制為Fmax。

用改進(jìn)PSO 算法求解卸載策略與資源分配問(wèn)題，算法流程圖如圖3 所示。

圖3 粒子群算法流程圖Fig.3 Flow chart of particle swarm optimization

算法具體流程如下：

（1）初始化，在解空間內(nèi)隨機(jī)產(chǎn)生L 個(gè)粒子的粒子群，包含位置矩陣A、F 和速度矩陣V1、V2。

（2）按照公式14 計(jì)算每個(gè)粒子的適應(yīng)值。

（3）更新個(gè)體歷史最優(yōu)位置Pbest和全局最優(yōu)粒子位置Gbest。

（4）更新粒子群位置矩陣A 和F，對(duì)卸載決策矩陣A 中越界的元素值，使其位于Amin和Amax之間，使F 中越界的元素值位于Fmin和Fmax之間。

（7）若兩次迭代的適應(yīng)度差異小于定值，或迭代次數(shù)r 達(dá)到設(shè)定值，算法結(jié)束，并輸出全局最優(yōu)粒子位置Gbest，否則返回到第2 步繼續(xù)迭代。

3 仿真與結(jié)果分析

采用Matlab 軟件對(duì)改進(jìn)的PSO 算法進(jìn)行仿真分析，試驗(yàn)采用蒙特卡洛方法，結(jié)果由1 000 次仿真求平均得到。設(shè)場(chǎng)景中有N=30 個(gè)本地設(shè)備，M=11 個(gè)MEC 服務(wù)器，其他參數(shù)設(shè)置如表2 所示。

表2 仿真參數(shù)設(shè)置Table 2 Simulation parameter settin

對(duì)以下4 種算法進(jìn)行比較和分析：

（1）方法一，改進(jìn)的PSO 算法。

（2）方法二，遺傳算法：經(jīng)典的遺傳算法采用精英策略，以防種群退化，設(shè)置交叉概率為0.80，變異概率為0.10。遺傳算法將可行解視為帶有遺傳信息的染色體，通過(guò)對(duì)染色體進(jìn)行選擇、交叉和變異操作，不斷迭代搜索最優(yōu)解。首先，根據(jù)公式14 計(jì)算各個(gè)染色體的適應(yīng)度值，選適應(yīng)度值最小的染色體為精英染色體，該染色體直接進(jìn)入到下一代染色體中，以防止種群退化。然后對(duì)剩下的染色體通過(guò)輪盤(pán)賭法進(jìn)行選擇操作，并隨機(jī)選擇一對(duì)染色體以指定概率進(jìn)行單點(diǎn)交叉。最后對(duì)染色體進(jìn)行變異操作，以一定概率隨機(jī)選擇部分染色體，并在取值范圍內(nèi)隨機(jī)設(shè)置其數(shù)值。選擇、交叉和變異均完成后，計(jì)算種群的適應(yīng)度值，開(kāi)始下一次遺傳迭代，直到兩次迭代的適應(yīng)度差異小于定值，或迭代次數(shù)r 達(dá)到設(shè)定值。

（3）方法三，全部本地計(jì)算：任務(wù)全部在本地設(shè)備計(jì)算，即A 中的所有元素值均設(shè)置為0。

3.1 不同本地設(shè)備數(shù)下的總代價(jià)

圖4 為不同本地設(shè)備數(shù)下的總代價(jià)對(duì)比，可以看出，隨著本地設(shè)備數(shù)量的增加，總代價(jià)隨之上升。其中本地計(jì)算的總代價(jià)最高，在設(shè)備數(shù)量為30 時(shí)達(dá)到75.34，而本方法總代價(jià)僅為24.92。與本文方法相比，本地計(jì)算的總代價(jià)高出202%，因?yàn)樗腥蝿?wù)均在本地執(zhí)行，而本地設(shè)備計(jì)算能力有限，會(huì)產(chǎn)生較高時(shí)延，導(dǎo)致總代價(jià)最高，因此本地計(jì)算不適合用來(lái)處理新型任務(wù)，這也是移動(dòng)邊緣計(jì)算存在的意義所在，移動(dòng)邊緣計(jì)算將部分任務(wù)卸載到距離較近的服務(wù)器上進(jìn)行處理，以降低系統(tǒng)代價(jià)，提升本地用戶(hù)的體驗(yàn)。隨機(jī)算法對(duì)任務(wù)執(zhí)行位置進(jìn)行隨機(jī)決策，任務(wù)是否卸載以及卸載到哪里均隨機(jī)決定，其處理過(guò)程具有盲目性，無(wú)法取得最小總代價(jià)，但隨機(jī)卸載算法也會(huì)將部分任務(wù)卸載到服務(wù)器，因此仍會(huì)優(yōu)于本地計(jì)算方法，在設(shè)備數(shù)量為30 時(shí)，隨機(jī)卸載算法相對(duì)于本地計(jì)算減小了47%總代價(jià)。遺傳算法通過(guò)對(duì)染色體進(jìn)行選擇、交叉和變異等操作，能得到較好的解，僅次于本文方法。本文方法取得的總代價(jià)最低，優(yōu)于其他三種算法，這是因?yàn)榱Ｗ尤涸诘蠼膺^(guò)程中，通過(guò)適應(yīng)度函數(shù)的反饋，能不斷通過(guò)自身經(jīng)驗(yàn)和社會(huì)經(jīng)驗(yàn)向最優(yōu)解靠近，最終取得較低的總代價(jià)。

圖4 不同本地設(shè)備數(shù)下的總代價(jià)對(duì)比Fig.4 Comparison of total cost under different number of local devices

3.2 不同任務(wù)計(jì)算量下的總代價(jià)

圖5 為不同每任務(wù)計(jì)算量下的總代價(jià)對(duì)比，可以看出，隨著任務(wù)計(jì)算量的不斷增加，4 種方法的總代價(jià)都隨之增高，這是因?yàn)殡S著任務(wù)計(jì)算量增加，無(wú)論任務(wù)在何處執(zhí)行，任務(wù)的處理時(shí)延和能耗都會(huì)增加，因此總代價(jià)增加。由于本地計(jì)算將任務(wù)全部安排到本地設(shè)備上執(zhí)行，而本地設(shè)備的處理能力有限，因此總代價(jià)是最高的。隨機(jī)卸載方法能夠卸載一部分任務(wù)到MEC 服務(wù)器上，因此優(yōu)于本地計(jì)算，但由于隨機(jī)卸載方法不依靠任何迭代和經(jīng)驗(yàn)，無(wú)法最小化總代價(jià)，也無(wú)法得到較優(yōu)解，在計(jì)算量為1.1 GHz 時(shí)，隨機(jī)卸載總代價(jià)為97.9，本文方法總代價(jià)為62.17，隨機(jī)卸載總代價(jià)高出57%，因此隨機(jī)卸載算法無(wú)法得到合適的可行卸載方案。本文方法總代價(jià)增長(zhǎng)趨勢(shì)和其他方法相同，但在4 種方法中總代價(jià)是最低的，優(yōu)于其他算法，這是因?yàn)殡S著任務(wù)計(jì)算量增加，粒子群算法通過(guò)迭代搜索并共享社會(huì)經(jīng)驗(yàn)，得到了任務(wù)的最優(yōu)執(zhí)行位置與資源分配方案，較多的計(jì)算任務(wù)都被分配到了MEC 服務(wù)器，降低了任務(wù)的總代價(jià)。

圖5 不同每任務(wù)計(jì)算量下的總代價(jià)對(duì)比Fig.5 Comparison of total cost under different computations per task

3.3 不同任務(wù)數(shù)據(jù)量下的總代價(jià)

圖6 為不同每任務(wù)數(shù)據(jù)量下的總代價(jià)對(duì)比，可以看出，除本地計(jì)算外，其他算法的任務(wù)總代價(jià)均隨著任務(wù)數(shù)據(jù)量的增加而上升。這是因?yàn)槌镜赜?jì)算外，其他算法均會(huì)將部分任務(wù)分配到服務(wù)器進(jìn)行執(zhí)行，隨著任務(wù)數(shù)據(jù)量的增加，任務(wù)的傳輸時(shí)延會(huì)增加，執(zhí)行時(shí)延不變，從而影響到總時(shí)延，而本地設(shè)備在發(fā)送這些數(shù)據(jù)時(shí)，能量消耗也隨即增加，因此總代價(jià)增加。由圖6 還可以看出，在4 種方法中，改進(jìn)的粒子群算法取得的總代價(jià)最低，本地計(jì)算的總代價(jià)較高，且不隨任務(wù)數(shù)據(jù)量的增加而變化，這是由于本地計(jì)算不需要傳輸卸載數(shù)據(jù)，其代價(jià)只與任務(wù)計(jì)算量有關(guān)系，因此數(shù)據(jù)量改變不會(huì)導(dǎo)致總代價(jià)的改變。從圖6 的總體趨勢(shì)還可以看出，較計(jì)算量而言，數(shù)據(jù)量對(duì)總代價(jià)的影響較小，總體走勢(shì)平緩，斜率較小，這是因?yàn)閿?shù)據(jù)量的變化只會(huì)在任務(wù)上傳階段增加上傳時(shí)延，對(duì)時(shí)延和能耗產(chǎn)生的影響較小，最終對(duì)總代價(jià)產(chǎn)生較小影響。

圖6 不同每任務(wù)數(shù)據(jù)量下的總代價(jià)對(duì)比Fig.6 Comparison of total costs under different data volumes per task

3.4 不同帶寬大小下的總代價(jià)

圖7 為不同帶寬大小下的總代價(jià)對(duì)比。圖7 中，除本地計(jì)算外，其他3 種算法的總代價(jià)都隨著帶寬的增加而降低，這是由于任務(wù)在進(jìn)行卸載時(shí)，會(huì)首先將任務(wù)上傳到服務(wù)器，所以帶寬較大時(shí)會(huì)獲得較小的傳輸時(shí)延，從而減少任務(wù)的時(shí)延成本。本地計(jì)算由于不進(jìn)行任務(wù)上傳操作，任務(wù)直接在本地進(jìn)行處理，沒(méi)有使用帶寬，因此總代價(jià)不因?yàn)閹挼母淖兌兓瑤捲龃髸r(shí)對(duì)總代價(jià)不會(huì)產(chǎn)生影響，在圖7 中表現(xiàn)為一條水平直線(xiàn)。由圖7 還可以看出，總代價(jià)仍然是最低的，這是因?yàn)閷?duì)傳統(tǒng)粒子群算法的慣性權(quán)重參數(shù)和學(xué)習(xí)因子進(jìn)行了優(yōu)化，使尋優(yōu)能力得到提升。

圖7 不同帶寬大小下的總代價(jià)對(duì)比Fig.7 Comparison of total cost under different bandwidth sizes

4 結(jié)論

研究建立了移動(dòng)邊緣計(jì)算中多用戶(hù)、多服務(wù)器的計(jì)算卸載模型，將時(shí)延和能耗的加權(quán)和定義為任務(wù)執(zhí)行代價(jià)，同時(shí)考慮了服務(wù)器任務(wù)的分配均衡問(wèn)題。通過(guò)聯(lián)合優(yōu)化卸載策略和資源分配變量，使得MEC 系統(tǒng)的總代價(jià)最低。為解決此問(wèn)題，使用粒子群算法進(jìn)行優(yōu)化，并改進(jìn)了傳統(tǒng)粒子群算法的慣性權(quán)重和學(xué)習(xí)因子，最終得到較優(yōu)的卸載決策和資源分配結(jié)果。仿真結(jié)果表明，相比于其他比較算法，能有效降低系統(tǒng)總代價(jià)，獲得較優(yōu)的計(jì)算卸載策略。但當(dāng)前研究暫未考慮異構(gòu)計(jì)算資源的分配問(wèn)題，以及設(shè)備移動(dòng)性問(wèn)題，這將是下一步的研究方向。