基于能耗與延遲優(yōu)化的移動(dòng)邊緣計(jì)算任務(wù)卸載模型及算法

戰(zhàn)俊偉，莊 毅

(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106)

0 引 言

隨著移動(dòng)互聯(lián)網(wǎng)的發(fā)展，出現(xiàn)了越來越多的新型應(yīng)用，例如虛擬現(xiàn)實(shí)、人臉識(shí)別、物聯(lián)網(wǎng)等。這些新興應(yīng)用和設(shè)備往往對(duì)延遲和能耗具有較高的要求，若使用傳統(tǒng)的云計(jì)算將任務(wù)上傳到云端處理，具有較高的時(shí)延，影響執(zhí)行效率。為了應(yīng)對(duì)這一巨大的挑戰(zhàn)，許多研究人員提出不同的解決辦法，通過靈活分配計(jì)算，增加存儲(chǔ)、帶寬等手段來實(shí)現(xiàn)低延遲和低能耗[1]。

移動(dòng)邊緣計(jì)算作為一種新的5G網(wǎng)絡(luò)架構(gòu)，是指在移動(dòng)終端附近部署高性能的邊緣服務(wù)器，將邊緣設(shè)備產(chǎn)生的任務(wù)部分卸載到邊緣服務(wù)器執(zhí)行，與本地計(jì)算相比具有節(jié)能作用，但同時(shí)也增加網(wǎng)絡(luò)負(fù)載和傳輸延遲[2]；與云服務(wù)器相比，邊緣服務(wù)器具有更好的靈活性以及較低的延遲[3]。當(dāng)前，學(xué)者們針對(duì)移動(dòng)邊緣計(jì)算任務(wù)卸載方面已有一些研究工作，主要包括對(duì)時(shí)延、能耗的優(yōu)化以及考慮卸載代價(jià)和服務(wù)質(zhì)量，同時(shí)也提出一系列任務(wù)卸載系統(tǒng)模型，主要有一對(duì)多、多對(duì)一、多對(duì)多卸載模型，一些學(xué)者結(jié)合啟發(fā)式算法、機(jī)器學(xué)習(xí)算法進(jìn)行求解[4]?？紤]到邊緣服務(wù)器的計(jì)算能力有限，并且在超密集網(wǎng)絡(luò)中的邊緣計(jì)算任務(wù)卸載會(huì)相互產(chǎn)生干擾，增大傳輸延遲，因此不能把所有的計(jì)算任務(wù)都卸載到邊緣服務(wù)器上[5]。雖然本地計(jì)算不會(huì)產(chǎn)生傳輸延遲，但處理計(jì)算量較大的任務(wù)耗時(shí)過多，能耗較大，不宜將計(jì)算密集任務(wù)放在本地計(jì)算[6]。且本地移動(dòng)設(shè)備電量有限，在不同電量下采用相同的卸載策略可能造成卸載失敗。結(jié)合啟發(fā)式算法求解的任務(wù)卸載決策時(shí)，算法收斂較快，易陷入局部最優(yōu)解，具有局限性[7]。因此，有必要研究相關(guān)的任務(wù)卸載算法和模型，以提高卸載效率和可靠性。

本文的主要研究工作如下：

1)針對(duì)移動(dòng)邊緣計(jì)算系統(tǒng)建模問題，提出一個(gè)基于能量延遲優(yōu)化的移動(dòng)邊緣計(jì)算任務(wù)卸載模型，包括網(wǎng)絡(luò)、通信、時(shí)延和能耗等要素。本文采用加權(quán)和的方式來計(jì)算系統(tǒng)的總開銷，并且將設(shè)備剩余電量引入到加權(quán)因子的定義中，用來改進(jìn)設(shè)備在不同電量下的卸載決策。該模型具有延長設(shè)備使用時(shí)間，同時(shí)優(yōu)化任務(wù)卸載時(shí)延和能耗的優(yōu)點(diǎn)。

2)針對(duì)求解移動(dòng)邊緣計(jì)算任務(wù)卸載決策的算法問題，提出一種基于改進(jìn)遺傳算法的移動(dòng)邊緣計(jì)算任務(wù)卸載算法。該算法結(jié)合傳統(tǒng)遺傳算法，改進(jìn)其交叉變異操作，以尋找最優(yōu)卸載決策，改進(jìn)了傳統(tǒng)遺傳算法交叉變異行為單一、前期收斂過快的缺點(diǎn)。改進(jìn)后的任務(wù)卸載算法求解范圍更大，能夠避免局部最優(yōu)解，利于尋找最優(yōu)任務(wù)卸載決策。

最后，本文構(gòu)建仿真實(shí)驗(yàn)平臺(tái)，通過提出的模型和算法對(duì)比實(shí)驗(yàn),驗(yàn)證本文算法的優(yōu)越性；使用改進(jìn)后的算法可計(jì)算不同場(chǎng)景下的系統(tǒng)時(shí)延、能耗以及總開銷；為解決移動(dòng)邊緣計(jì)算任務(wù)卸載問題提供一種有效的方法。

1 相關(guān)研究工作

現(xiàn)有的移動(dòng)邊緣計(jì)算任務(wù)卸載問題，針對(duì)不同的卸載指標(biāo)，可以分為最小化時(shí)延、最小化能耗以及時(shí)延能耗權(quán)衡等。

在移動(dòng)邊緣計(jì)算任務(wù)卸載中，以最小化時(shí)延為目標(biāo)，已有Kiran等人[8]研究移動(dòng)邊緣計(jì)算中的資源分配和任務(wù)卸載問題，其提出減少邊緣計(jì)算系統(tǒng)的延遲的模型，使用基于Q學(xué)習(xí)的強(qiáng)化學(xué)習(xí)方法來解決最小化時(shí)延問題，與傳統(tǒng)強(qiáng)化學(xué)習(xí)方法相比，具有大幅減少時(shí)延的優(yōu)點(diǎn)。Chen等人[9]建立超密集網(wǎng)絡(luò)下的邊緣計(jì)算模型，提出將最小化時(shí)延問題轉(zhuǎn)化為2個(gè)子問題求解的方法，使用凸優(yōu)化方法進(jìn)行求解。該算法和傳統(tǒng)隨機(jī)卸載方案相比，優(yōu)點(diǎn)是可以減少20%的任務(wù)時(shí)間，節(jié)省30%的能量消耗。Yang等人[10]研究多用戶計(jì)算卸載和邊緣云資源的調(diào)度，目標(biāo)是為所有用戶實(shí)現(xiàn)最小時(shí)延，設(shè)計(jì)一種離線啟發(fā)式算法，優(yōu)點(diǎn)在于算法復(fù)雜度不高易于實(shí)現(xiàn)，且性能較經(jīng)典作業(yè)調(diào)度算法平均高10%。

以最小化能耗為目標(biāo)，Zhao等人[11]研究異構(gòu)云的移動(dòng)邊緣計(jì)算任務(wù)卸載，目標(biāo)是在時(shí)延限制內(nèi)最小化系統(tǒng)總能耗。其提出的離散化近似算法與任務(wù)在本地設(shè)備執(zhí)行相比，可以減少82.9%能耗，不足之處在于卸載時(shí)延較大。Yu等人[12]研究基于移動(dòng)邊緣計(jì)算任務(wù)卸載和資源分配策略，提出一種基于梯度下降的迭代算法，與固定卸載比例算法相比優(yōu)勢(shì)明顯，可以節(jié)約40%～60%的能耗。FANG等人[13]研究多用戶隨機(jī)任務(wù)邊緣計(jì)算系統(tǒng)的任務(wù)卸載問題，提出通過合理分配本地資源來減少能耗的任務(wù)卸載的方法，該方法的優(yōu)點(diǎn)在于考慮了CPU頻率縮放以及設(shè)備發(fā)射功率分配，能耗較小，而且節(jié)約本地資源。

目前已有一些學(xué)者同時(shí)考慮能量消耗和執(zhí)行延遲，如Dinh等人[14]提出聯(lián)合優(yōu)化任務(wù)卸載決策和SMD的CPU周期頻率的方案，考慮了固定CPU頻率和彈性CPU頻率2種情況，使總?cè)蝿?wù)執(zhí)行延遲和邊緣設(shè)備的能耗最小。Wang等人[15]提出同時(shí)優(yōu)化計(jì)算卸載決策、物理資源塊分配和MEC計(jì)算資源分配3個(gè)方面，在時(shí)間和能耗上使整個(gè)系統(tǒng)的總消耗最小。其優(yōu)點(diǎn)在于考慮多方面因素，采用加權(quán)因子來定義能量消耗和延遲的加權(quán)總和作為研究目標(biāo)。劉繼軍等人[16]綜合考慮資源分配與卸載決策聯(lián)合優(yōu)化的問題，采用信道分配算法為卸載任務(wù)分配信道資源，并對(duì)卸載任務(wù)采用資源競爭算法來分配計(jì)算資源，能有效提高卸載任務(wù)的傳輸速率。然而以上文獻(xiàn)的不足之處在于沒有考慮設(shè)備剩余電量與時(shí)延與能耗權(quán)重因子之間的關(guān)系。

在移動(dòng)邊緣計(jì)算系統(tǒng)建模方面，可以分為一對(duì)多、多對(duì)一、多對(duì)多、D2D(Device to Device)等多種方式。Zhang等人[17]提出了建立多對(duì)一的移動(dòng)邊緣計(jì)算模型，考慮了多用戶之間的網(wǎng)絡(luò)干擾，權(quán)衡系統(tǒng)時(shí)延和能耗來以獲取最優(yōu)卸載決策。Liu等人[18]建立了多用戶單服務(wù)器的移動(dòng)邊緣計(jì)算模型，考慮了多用戶網(wǎng)絡(luò)之間的干擾，將問題歸納為最小化用戶代價(jià)和最大化MEC計(jì)算收益，并使用博弈論方法求解，有效解決任務(wù)卸載決策問題。Saleem等人[19]建模采用D2D的方式，考慮了邊緣設(shè)備之間的任務(wù)卸載問題，提出聯(lián)合任務(wù)卸載和資源分配的解決方式，其優(yōu)勢(shì)在于可以充分利用邊緣設(shè)備上的閑置資源，但現(xiàn)實(shí)場(chǎng)景中較難實(shí)現(xiàn)。

在算法方面，Ezhilarasie等人[20]將粒子群算法和遺傳算法相結(jié)合來求解任務(wù)卸載問題，提出新的慣性權(quán)重，利用遺傳算法的探測(cè)能力和粒子群算法的開發(fā)能力，使算法較易實(shí)現(xiàn)且求解結(jié)果更加精確。Huang等人[21]提出了使用改進(jìn)的遺傳算法進(jìn)行求解，考慮任務(wù)執(zhí)行順序、位置和安全性，并設(shè)計(jì)了相應(yīng)的SEECO任務(wù)卸載策略，能夠提高移動(dòng)應(yīng)用的能效和安全性。Wang等人[22]使用深度強(qiáng)化學(xué)習(xí)算法進(jìn)行求解，優(yōu)點(diǎn)是算法復(fù)雜度適中且求得的解較傳統(tǒng)啟發(fā)式算法好，但缺少訓(xùn)練模型。Zhuo等人[23]提出了一種基于改進(jìn)遺傳模擬退火算法的任務(wù)卸載策略,將遺傳算法與模擬退火算法相結(jié)合，有效改善單一算法的不足，但該方法求解迭代次數(shù)較多。

綜上所述，雖然以往任務(wù)卸載模型和算法研究較多，但仍存在不足，一方面模型未考慮部分場(chǎng)景邊緣服務(wù)器較多，單用戶的任務(wù)可選擇多個(gè)服務(wù)器進(jìn)行任務(wù)卸載的場(chǎng)景；另一方面任務(wù)卸載算法存在收斂過快、易陷入局部最優(yōu)解的缺點(diǎn)。因此本文提出一種基于時(shí)延能耗優(yōu)化的一對(duì)多的任務(wù)卸載模型，并設(shè)計(jì)基于改進(jìn)遺傳算法的任務(wù)卸載算法來進(jìn)行求解。

2 系統(tǒng)模型和問題公式

移動(dòng)邊緣計(jì)算的關(guān)鍵是解決邊緣設(shè)備產(chǎn)生的任務(wù)流，其中，對(duì)時(shí)延要求較高的任務(wù)適合留在本地處理，對(duì)能耗要求較高的任務(wù)可以卸載到邊緣服務(wù)器處理。本文采用邊緣服務(wù)器(Mobile Edge Computing， MEC)處理任務(wù)卸載，其不僅具有通信能力，還提供邊緣計(jì)算能力?，F(xiàn)有的任務(wù)卸載模型大多只考慮任務(wù)卸載的時(shí)延和能耗，忽略本地設(shè)備剩余電量對(duì)任務(wù)卸載的影響[24]。因此本文提出一種根據(jù)設(shè)備剩余電量動(dòng)態(tài)改變權(quán)重因子的任務(wù)卸載模型，可減少任務(wù)卸載的總開銷并提高設(shè)備的使用時(shí)長。

2.1 網(wǎng)絡(luò)模型

考慮一個(gè)有N個(gè)獨(dú)立任務(wù)的移動(dòng)邊緣設(shè)備(Mobile Device, MD)，這些任務(wù)中的每一個(gè)都可以由移動(dòng)邊緣設(shè)備的CPU本地處理或者卸載到附近的任意一個(gè)邊緣服務(wù)器上進(jìn)行計(jì)算，并將計(jì)算產(chǎn)生的結(jié)果返回給設(shè)備,任務(wù)卸載框架如圖1所示。

圖1 任務(wù)卸載框架圖

在用戶的邊緣設(shè)備上產(chǎn)生某一任務(wù)集tasks={1,2,3，…，N}，各子任務(wù)之間相互獨(dú)立，任務(wù)可卸載設(shè)備的CPU集合為CPUs={0,1,2,3，…，M}，其中M為0時(shí)表示移動(dòng)邊緣設(shè)備的本地CPU，當(dāng)M不為0時(shí)表示邊緣服務(wù)器的CPU。邊緣設(shè)備產(chǎn)生的任務(wù)集中的每一個(gè)任務(wù)需要決定留在本地計(jì)算還是卸載到MEC計(jì)算。

本文用元組{di,ci,timax}表示子任務(wù)i的各項(xiàng)數(shù)據(jù)，其中di為任務(wù)數(shù)據(jù)大小(bit)，ci為處理任務(wù)所需的CPU周期數(shù)，timax表示每個(gè)子任務(wù)的最大容忍時(shí)延。假設(shè)在任何執(zhí)行之前，要處理的數(shù)據(jù)量是已知的，數(shù)據(jù)量大小不規(guī)則，每個(gè)邊緣服務(wù)器向邊緣設(shè)備提供固定的CPU頻率fk。本文中，使用二進(jìn)制變量xik表示任務(wù)卸載決策，xik=1，任務(wù)在CPUk處理，若xik=0，任務(wù)不在CPUk處理。

卸載的任務(wù)需要通過無線傳輸?shù)竭吘壏?wù)器執(zhí)行，在本文中假設(shè)用戶采用彼此正交的無線信道，因此用戶在計(jì)算卸載過程中不同的邊緣服務(wù)器之間的信號(hào)不會(huì)互相干擾。邊緣設(shè)備與邊緣服務(wù)器之間的傳輸速率為rk表示如式(1)[25]所示：

(1)

其中，Bk是第k個(gè)邊緣服務(wù)器分配給邊緣設(shè)備的上行通道帶寬，P為邊緣設(shè)備的傳輸功率，hk為邊緣服務(wù)器和邊緣設(shè)備之間的上行通道增益，σ2是噪聲功率。

2.2 時(shí)延模型

定義ti為某一任務(wù)的時(shí)延，fk(k∈(O,M))為CPU計(jì)算頻率，當(dāng)k=0時(shí),f0為本地設(shè)備的CPU計(jì)算頻率，當(dāng)k≠0時(shí)，fk表示邊緣服務(wù)器的計(jì)算頻率。

因此，本地計(jì)算時(shí)延tl為：

(2)

當(dāng)任務(wù)卸載到邊緣服務(wù)器計(jì)算時(shí)，邊緣服務(wù)器可以在接收完全部任務(wù)后開始處理所有任務(wù)，也可以在接收前幾個(gè)任務(wù)后開始處理部分任務(wù)，同時(shí)可接收更多任務(wù)。第2種情況將使分析更加困難，因?yàn)槿蝿?wù)在邊緣服務(wù)器上的到達(dá)順序極大地?cái)U(kuò)大決策域。因此，為了簡單起見，本文假設(shè)MEC在接收完所有任務(wù)后開始處理任務(wù)。其中，任務(wù)卸載時(shí)延包括傳輸時(shí)延和MEC計(jì)算時(shí)延，計(jì)算時(shí)延tc為：

(3)

由于任務(wù)在邊緣服務(wù)器計(jì)算后產(chǎn)生的結(jié)果通常很小，因此在本文中，忽略結(jié)果返回本地設(shè)備的時(shí)延，只考慮任務(wù)上傳產(chǎn)生的傳輸時(shí)延tu為：

(4)

分子任務(wù)在本地處理的同時(shí)，剩余子任務(wù)會(huì)卸載到邊緣服務(wù)器執(zhí)行，因此，總的時(shí)延T為本地計(jì)算時(shí)延和卸載產(chǎn)生時(shí)延的最大值，可表示為：

T=max(tl,tc+tu)

(5)

2.3 能耗模型

任務(wù)在本地計(jì)算時(shí)，不同的CPU頻率會(huì)影響本地計(jì)算的功率從而影響到本地能耗。在本文中，假設(shè)本地設(shè)備采用固定的CPU頻率進(jìn)行計(jì)算，本地計(jì)算能耗ei表示如式(6)[26]所示：

ei=κ(f0)2ci

(6)

其中，能耗系數(shù)κ是與移動(dòng)設(shè)備的芯片結(jié)構(gòu)相關(guān)的常數(shù)。本地任務(wù)的總能耗el為所有在本地處理的子任務(wù)產(chǎn)生的能耗之和，表示如式(7)所示：

(7)

由于本文忽略了任務(wù)結(jié)果返回的時(shí)延，因此也應(yīng)忽略計(jì)算結(jié)果返回接收時(shí)的能耗，只需考慮任務(wù)卸載產(chǎn)生的能耗，傳輸能耗ec表示如式(8)所示：

(8)

本文中，假設(shè)無需考慮卸載任務(wù)在邊緣服務(wù)器產(chǎn)生的計(jì)算能耗，只考慮本地計(jì)算能耗和傳輸能耗。因此，總能耗E為本地能耗與傳輸能耗之和，表示如式(9)所示：

E=el+ec

(9)

在任務(wù)執(zhí)行過程中，邊緣設(shè)備的執(zhí)行延遲和能量消耗都是至關(guān)重要的，這與用戶體驗(yàn)和邊緣設(shè)備電池的能量限制有關(guān)，因此一般使用加權(quán)因子來研究能量消耗和延遲之間的權(quán)衡。加權(quán)因子可以由用戶自行定義，以滿足用戶特定的需求。通過調(diào)整權(quán)重因子可以節(jié)省更多的能量或減少延遲。本文將電池的剩余能量率帶入本文模型的權(quán)重因子中，定義見式(10)：

(10)

其中，eres是邊緣設(shè)備的剩余電量，etotal是總的電池容量。

本文使用時(shí)延能耗加權(quán)和來描述任務(wù)卸載的總開銷，權(quán)衡時(shí)延和能耗對(duì)任務(wù)卸載的影響。定義時(shí)延能耗加權(quán)因子可使設(shè)備在電量充足時(shí)更多考慮時(shí)延因素，將多數(shù)任務(wù)在本地處理，充分發(fā)揮本地計(jì)算低延遲的優(yōu)點(diǎn)，當(dāng)設(shè)備電量不足時(shí)提高卸載任務(wù)的數(shù)量，減少邊緣設(shè)備的能耗，提高設(shè)備的使用壽命。其中，剩余電量影響的時(shí)延加權(quán)因子wt定義為：

wt=ln[λ(ew-1)+1]

(11)

式(11)中，w是用戶自定義的時(shí)延權(quán)重因子，例如當(dāng)w=0.5時(shí)，表示時(shí)延和能耗因素對(duì)用戶同等重要，wt則為考慮剩余電量因素后的修正時(shí)延權(quán)重因子，由于時(shí)延能耗權(quán)重之和為1，則能耗加權(quán)因子we為：

we=1-wt

(12)

系統(tǒng)總開銷W即時(shí)延能耗加權(quán)和如式(13)所示：

W=wtT+weE

(13)

加權(quán)和法作為求解多目標(biāo)優(yōu)化的方法之一，因其簡單易懂、易于實(shí)現(xiàn)而得到廣泛應(yīng)用。本文的邊緣計(jì)算任務(wù)卸載問題可以看作求解多目標(biāo)優(yōu)化問題，本文中優(yōu)化的目標(biāo)是時(shí)延和能耗，使卸載方案在同時(shí)滿足時(shí)延能耗需求的前提下達(dá)到總開銷最小化。其中，時(shí)延和能耗的權(quán)重系數(shù)反映系統(tǒng)偏好，當(dāng)系統(tǒng)對(duì)時(shí)延要求較高時(shí)，可以適當(dāng)提高時(shí)延權(quán)重系數(shù)，當(dāng)系統(tǒng)對(duì)節(jié)能要求較高時(shí)，可以提高能耗權(quán)重系數(shù)。例如，當(dāng)用戶只關(guān)心設(shè)備電量消耗時(shí)，可以設(shè)置wt=0,we=1。

本文的邊緣計(jì)算任務(wù)卸載問題是尋找到最小化總開銷的卸載策略，可以轉(zhuǎn)化為公式(14)的求解：

C3:xik∈{0,1}

(14)

約束C1保證每個(gè)任務(wù)的執(zhí)行時(shí)間不大于任務(wù)的最大容忍延遲；約束C2保證總的能耗不超過設(shè)備的剩余能量；約束C3表示任務(wù)只能卸載到邊緣服務(wù)器或在本地執(zhí)行。

由于本文移動(dòng)邊緣計(jì)算任務(wù)卸載問題是多目標(biāo)組合優(yōu)化問題，復(fù)雜度較高，可以采用啟發(fā)式算法[23]求解該類問題，本文中采用改進(jìn)的遺傳算法求解。

3 基于改進(jìn)遺傳算法的任務(wù)卸載算法

移動(dòng)邊緣計(jì)算任務(wù)卸載可以結(jié)合傳統(tǒng)啟發(fā)式算法，遺傳算法是常用算法之一。為了得到任務(wù)延遲滿足任務(wù)要求、能量消耗較小、總開銷較小的任務(wù)卸載算法，本文對(duì)傳統(tǒng)的遺傳算法進(jìn)行改進(jìn)，改進(jìn)交叉變異行為，減緩遺傳算法前期的收斂速度，從而提高解空間的搜索范圍，并且有利于在種群進(jìn)化后期跳出局部最優(yōu)解，能更好地解決移動(dòng)邊緣計(jì)算任務(wù)卸載問題。

3.1 染色體編碼與解碼

染色體編碼有很多種方式，可以采用二進(jìn)制編碼，也可采用實(shí)數(shù)編碼。本文采用十進(jìn)制的實(shí)數(shù)編碼方式，若一個(gè)種群大小為s，任務(wù)總數(shù)為N，邊緣服務(wù)器總數(shù)為M個(gè)，則初始化種群如下：隨機(jī)生成s個(gè)染色體，染色體長度為N，每個(gè)染色體上的基因隨機(jī)取，取值范圍為[0,M]。

染色體C={c1,c2,ci，…，cN}，其中當(dāng)xik=1時(shí)ci=k，表示當(dāng)任務(wù)i卸載到第k個(gè)邊緣服務(wù)器時(shí)，染色體第i個(gè)位置的基因?yàn)閗。例如C={1,0,2,…,1}，表示任務(wù)1卸載到1號(hào)邊緣服務(wù)器,任務(wù)2在本地計(jì)算，任務(wù)3卸載到2號(hào)邊緣服務(wù)器，以此類推。

3.2 適應(yīng)度評(píng)估

在遺傳算法中，適應(yīng)度是評(píng)價(jià)個(gè)體基因優(yōu)劣的標(biāo)準(zhǔn)，通常選取適應(yīng)度值較大的個(gè)體進(jìn)行交叉變異從而將優(yōu)秀的基因遺傳到下一代，實(shí)現(xiàn)種群進(jìn)化。

本文中評(píng)價(jià)邊緣計(jì)算任務(wù)卸載策略的性能指標(biāo)是所有任務(wù)的完成時(shí)間和邊緣設(shè)備能耗的加權(quán)和，對(duì)于一種卸載策略，其總時(shí)延為T,總的能耗為E，總開銷為W,因此總開銷越小的個(gè)體其適應(yīng)度越大，適應(yīng)度li如式(15)所示：

(15)

3.3 選擇操作

在進(jìn)行交叉操作前，需要選擇父代個(gè)體。本文采用基于適應(yīng)度的輪盤賭選擇法從父代中選取個(gè)體遺傳到下一代，適應(yīng)度越大的染色體被選擇的概率越高，適應(yīng)度較低的個(gè)體也有機(jī)會(huì)遺傳自己的基因。

在本文的邊緣計(jì)算任務(wù)卸載方法中，適應(yīng)度越大的種群個(gè)體代表其任務(wù)卸載的總開銷越小。假設(shè)種群中有s個(gè)個(gè)體，首先需要根據(jù)適應(yīng)度函數(shù)計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度，然后計(jì)算出每個(gè)個(gè)體被選擇的概率q(s)，計(jì)算方式如式(16)所示：

(16)

3.4 交叉、變異操作

交叉的作用是保持種群的穩(wěn)定性并使種群朝著最優(yōu)解的方向進(jìn)化，變異的作用是避免種群陷入局部最優(yōu)解，提高種群的多樣性。但是，傳統(tǒng)的遺傳算法交叉變異操作過于簡單，前期收斂較快，種群容易陷入“早熟”，且算法局部尋優(yōu)能力較差，難以尋找到全局最優(yōu)解，使得進(jìn)化結(jié)果并不理想。本文中，對(duì)交叉變異操作進(jìn)行一系列改進(jìn)，提出4種不同的交叉變異行為，并設(shè)置隨種群進(jìn)化動(dòng)態(tài)變化的交叉變異概率來減緩種群前期收斂速度以提高解空間搜索范圍，并提高種群后期尋優(yōu)能力以尋找更優(yōu)的卸載方案。

3.4.1 單體分解

發(fā)生單體分解的染色體分解后產(chǎn)生2個(gè)染色體，在原染色體C中隨機(jī)選擇一個(gè)分解點(diǎn)h1,新染色體C1保留原染色體C的{c0,c1，…，ch1}部分的基因,新染色體C2保留原染色體的{ch1,ch1+1，…，cN}部分的基因，C1和C2剩余的基因位隨機(jī)生成,從而得到2個(gè)新的染色體，即產(chǎn)生2種新的卸載策略,如圖2所示。單體分解隨個(gè)體適應(yīng)度的動(dòng)態(tài)執(zhí)行概率p1如式(17)所示：

圖2 單體分解示意圖

(17)

其中，lmax和lmin分別表示種群中的最大和最小適應(yīng)度，表示當(dāng)前個(gè)體的適應(yīng)度。

新的染色體與原染色體在基因結(jié)構(gòu)上差別較大，使得該過程能搜索更大的解空間，避免算法陷入局部最優(yōu)解。

3.4.2 雙體組合

雙體組合是2個(gè)染色體進(jìn)行染色體組合操作，選擇2個(gè)染色體C1和C2，隨機(jī)生成一個(gè)組合點(diǎn)h2，新染色體繼承原染色體C1的{c0,c1,…,ch2}部分的基因和原染色體C2的{ch2,ch2+1，…，cN}部分的基因，生成一個(gè)新的染色體如圖3所示。雙體組合隨種群進(jìn)化的動(dòng)態(tài)執(zhí)行概率p2如式(18)所示：

圖3 雙體組合示意圖

(18)

其中，ps2為初始執(zhí)行概率值，pe2為結(jié)束執(zhí)行概率值，Iter為當(dāng)前種群進(jìn)化代數(shù)，Itermax為算法最大迭代次數(shù)。

新染色體C極大地破壞原染色體的基因結(jié)構(gòu)可產(chǎn)生染色體突變，這有利于使種群呈現(xiàn)多樣化，極大地?cái)U(kuò)大解空間的搜索范圍。

3.4.3 間隔互換

間隔互換是指2個(gè)染色體相互間交叉易位的操作過程。從原染色體C1和C2中選擇多個(gè)交叉易位點(diǎn)h31、h32，交換對(duì)應(yīng)點(diǎn)的基因，生成2個(gè)新的染色體,得到2種新的卸載策略，如圖4所示。間隔互換隨種群進(jìn)化的動(dòng)態(tài)執(zhí)行概率p3如式(19)所示：

圖4 間隔互換示意圖

(19)

其中，l1與l2分別表示2個(gè)染色體的適應(yīng)度。

交叉易位的染色體個(gè)數(shù)u1計(jì)算如式(20)所示：

(20)

新染色體與原染色體在結(jié)構(gòu)上具有相似性，又吸收不同的基因，有利于在鄰域空間內(nèi)搜索最優(yōu)解，跳出局部最優(yōu)解，使得種群進(jìn)化。

3.4.4 雙體交叉

雙體交叉是2個(gè)染色體相同位置連續(xù)的若干基因發(fā)生交叉換位。對(duì)于2個(gè)染色體C1和C2，隨機(jī)選擇一個(gè)交叉點(diǎn)h4,對(duì)交叉點(diǎn)后的基因位置互換，生成2個(gè)新的染色體如圖5所示。雙體交叉的動(dòng)態(tài)執(zhí)行概率p4如式(21)所示：

圖5 雙體交叉示意圖

p4=1-p1-p2-p3

(21)

交叉易位的染色體個(gè)數(shù)計(jì)算如式(22)所示：

(22)

新生成的染色體包含原染色體的大部分的基因，并加入其它染色體的少數(shù)基因，有利于生成更好的個(gè)體，利于種群的進(jìn)化，形成更好的卸載策略，但也有可能使新生成的個(gè)體適應(yīng)度更差。

3.5 移動(dòng)邊緣計(jì)算任務(wù)卸載算法

基于改進(jìn)遺傳算法，本文設(shè)計(jì)移動(dòng)邊緣計(jì)算任務(wù)卸載算法，算法具體步驟如下：

Step 1初始化。

Step 1.1生成移動(dòng)邊緣設(shè)備產(chǎn)生任務(wù)的數(shù)據(jù)量大小，計(jì)算所需的CPU周期數(shù)、最大時(shí)延；

Step 1.2用戶輸入自定義時(shí)延權(quán)重因子和設(shè)備剩余電量；

Step 1.3初始化遺傳算法，用戶自定義遺傳算法種群大小、迭代次數(shù)；隨機(jī)初始化種群，生成一批任務(wù)卸載策略。

Step 2計(jì)算任務(wù)卸載策略時(shí)延。分別計(jì)算本地計(jì)算時(shí)延、邊緣服務(wù)器計(jì)算時(shí)延、傳輸時(shí)延，根據(jù)式(5)求出總時(shí)延。

Step 3計(jì)算任務(wù)卸載策略能耗。分別計(jì)算本地能耗、傳輸能耗，根據(jù)式(9)求出總能耗。

Step 4計(jì)算系統(tǒng)總開銷。分別計(jì)算時(shí)延、能耗加權(quán)因子，根據(jù)式(13)求出任務(wù)卸載總開銷。

Step 5計(jì)算每個(gè)卸載策略是否滿足式(14)的限制條件，若滿足則保留對(duì)應(yīng)的種群個(gè)體。

Step 6計(jì)算所有種群個(gè)體的適應(yīng)度大小，并計(jì)算種群個(gè)體被選擇的概率。

Step 7按輪盤賭選擇法選出種群個(gè)體，計(jì)算各種交叉變異操作概率，根據(jù)概率選擇要執(zhí)行的操作。

Step 7.1對(duì)于選出個(gè)體，根據(jù)式(17)計(jì)算單體分解概率，根據(jù)式(18)計(jì)算雙體組合的概率，根據(jù)式(19)計(jì)算間隔互換的概率，根據(jù)式(21)計(jì)算雙體交叉的概率；

Step 7.2進(jìn)行間隔互換的個(gè)體，根據(jù)式(20)計(jì)算互換基因個(gè)數(shù)；進(jìn)行雙體交叉的個(gè)體，根據(jù)式(22)計(jì)算交叉的基因個(gè)數(shù)。

Step 8循環(huán)Step7直到生成新的種群，更新邊緣計(jì)算任務(wù)卸載策略。

Step 9重復(fù)執(zhí)行Step2～Step8，達(dá)到算法迭代次數(shù)后，輸出最終的移動(dòng)邊緣計(jì)算任務(wù)卸載決策和系統(tǒng)總開銷。

算法1移動(dòng)邊緣計(jì)算任務(wù)卸載算法

輸入：di,ci,timax,w,eres

輸出：mobile edge computing task offloading strategy and the total overhead

1.initialize the popsize and iteration, generate the first chromosome population,then generate task offloading strategy

2.whilei

3.calculate total time based on(5)

// local compute time,MEC compute time and transmission time

4.calculate total energy based on(9)

// local and transmission energy

5.calculate total cost based on(13)

6.estimate the rationality of the offloading strategy by(14)

7.calculate the fitness of all chromosomes and calculate

selectionprobabilities

8.whilei

9.select chromosomes by probabilities

10.calculate the probability ofp1by(17)

11.calculate the probability ofp2by(18)

12.calculate the probability ofp1by(19)

and the value ofu1by(20)

13.calculate the probability ofp4by(21)

and the value ofu2by(22)

14.crossover and variation based on probabilities to genarate new populations

15.end while

16.update the task offloading strategy

17.end while

18.return Strategies //Output the offloading strategy

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

本文考慮一個(gè)多任務(wù)-多邊緣服務(wù)器的場(chǎng)景，某用戶的設(shè)備上隨機(jī)產(chǎn)生一批任務(wù)，任務(wù)大小在500～1000 kB,任務(wù)的最大容忍時(shí)延為0.3 s,任務(wù)可以留在本地設(shè)備上處理，也可以卸載到邊緣服務(wù)器進(jìn)行計(jì)算，其中本地設(shè)備計(jì)算能力為1.2 GHz,邊緣服務(wù)器計(jì)算能力為6 GHz,網(wǎng)絡(luò)帶寬為30 MHz，具體實(shí)驗(yàn)參數(shù)如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)

設(shè)計(jì)共有5種實(shí)驗(yàn)方案，方案1、方案2、方案3分別表示當(dāng)時(shí)延權(quán)重為0.2、0.5、0.8的任務(wù)卸載策略，方案4為任務(wù)全部卸載到邊緣服務(wù)器執(zhí)行，方案5為任務(wù)全部在本地執(zhí)行。

圖6為時(shí)延與任務(wù)卸載方案的關(guān)系，圖中橫坐標(biāo)表示系統(tǒng)隨機(jī)產(chǎn)生的任務(wù)數(shù)量，縱坐標(biāo)表示卸載方案的總時(shí)延。可以看出當(dāng)所有任務(wù)都在本地執(zhí)行或都卸載到邊緣服務(wù)器執(zhí)行時(shí)，時(shí)延較部分卸載方案大，這是由于部分卸載方案為并行計(jì)算，時(shí)延取本地和邊緣計(jì)算時(shí)延的最大值，因此時(shí)延會(huì)比其它2種卸載方案小。在所有的部分卸載方案中，當(dāng)任務(wù)數(shù)相同時(shí)，隨著時(shí)延權(quán)重的增大，系統(tǒng)總的時(shí)延不斷減小，權(quán)重越大，時(shí)延越小。

圖6 時(shí)延與卸載方案關(guān)系圖

圖7為系統(tǒng)能耗與任務(wù)卸載方案的關(guān)系，可以看出當(dāng)任務(wù)全部在本地執(zhí)行時(shí)能耗最大，全部卸載的能耗最少。在所有的部分卸載方案中，隨著能耗權(quán)重的增大，任務(wù)卸載能耗不斷減少。當(dāng)部分卸載能耗權(quán)重為0.8時(shí)，所有任務(wù)的能耗接近于全部卸載的能耗。用戶可以通過調(diào)大能耗權(quán)重參數(shù)，來減少系統(tǒng)總能耗。

圖7 能耗與卸載方案關(guān)系圖

本文提出的邊緣計(jì)算任務(wù)卸載模型中，引入剩余電量對(duì)任務(wù)卸載的影響，考慮一個(gè)有80個(gè)任務(wù)的邊緣計(jì)算任務(wù)卸載過程，任務(wù)對(duì)時(shí)延的要求較高，因此用戶初始自定義時(shí)延權(quán)重為0.8，設(shè)備的剩余電量為20%～80%。

在圖8中，當(dāng)設(shè)備剩余電量為80%時(shí)，任務(wù)處理的時(shí)延較低而能耗較高，符合用戶最初對(duì)時(shí)延要求較高的期望。隨著電量的降低，系統(tǒng)總的時(shí)延逐漸提高而能耗降低，設(shè)備電量越少時(shí)，能耗越低，滿足設(shè)備在低電量下的運(yùn)行需求。可以看出，時(shí)延權(quán)重因子的引入雖然使系統(tǒng)損耗部分時(shí)延性能，但可使設(shè)備更加節(jié)約能量。

圖8 總代價(jià)與剩余電量關(guān)系圖

在本文中，設(shè)計(jì)一種基于改進(jìn)遺傳算法的任務(wù)卸載算法，將本文算法與季子豪等人[27]算法比較，其使用基于精英策略的遺傳算法求解任務(wù)卸載問題。圖9顯示本文任務(wù)卸載算法在種群進(jìn)化時(shí)的優(yōu)勢(shì)，可增大種群進(jìn)化前期的交叉變異概率，減緩算法收斂速度，增大解空間搜索范圍。在幾乎相同的迭代次數(shù)下，本文改進(jìn)后的算法后期尋優(yōu)能力更強(qiáng)，可避免傳統(tǒng)遺傳算法前期收斂較快，較早地收斂于局部最優(yōu)解，難以尋找到全局最優(yōu)解的缺點(diǎn)。

圖9 適應(yīng)度與迭代次數(shù)關(guān)系圖

5 結(jié)束語

本文針對(duì)多任務(wù)多邊緣服務(wù)器的移動(dòng)邊緣計(jì)算任務(wù)卸載問題，構(gòu)建移動(dòng)邊緣計(jì)算任務(wù)卸載模型，研究邊緣計(jì)算的時(shí)延和能耗優(yōu)化問題，并考慮設(shè)備剩余電量對(duì)任務(wù)卸載的影響。為了使得系統(tǒng)總開銷最小，本文提出一種基于改進(jìn)遺傳算法的任務(wù)卸載算法。該算法能夠擴(kuò)大解空間搜索范圍，避免陷入局部最優(yōu)解。仿真結(jié)果表明，改進(jìn)后算法能夠合理權(quán)衡時(shí)延和能耗，時(shí)延和能耗隨著任務(wù)數(shù)增大而增大，隨著權(quán)重因子的增大而減小。驗(yàn)證通過用戶自定義權(quán)重因子，可以改變系統(tǒng)對(duì)時(shí)延或能耗的偏重程度，不同的權(quán)重在不同數(shù)量的任務(wù)下都能求出系統(tǒng)總開銷最小的任務(wù)卸載方法。改進(jìn)后的算法在迭代求解時(shí)，前期探索空間大，曲線波動(dòng)較大，后期趨于穩(wěn)定且能夠?qū)さ酶鼉?yōu)解。

本文為解決移動(dòng)邊緣計(jì)算任務(wù)卸載問題提供了一種合理的解決方案，可以幫助用戶減少時(shí)延并節(jié)約能量。但本文未考慮多用戶場(chǎng)景下的任務(wù)卸載問題，需要進(jìn)一步研究，繼續(xù)探索網(wǎng)絡(luò)傳輸干擾以及資源分配等對(duì)任務(wù)卸載的影響。