基于遺傳算法的MEC任務(wù)卸載資源優(yōu)化策略

王 麗，王曉凱

(1.晉中學(xué)院 物理與電子工程系，山西 晉中 030619；2.山西大學(xué) 物理電子工程學(xué)院，山西 太原 030006)

0 引 言

近年來，物聯(lián)網(wǎng)(internet of things，IoT)作為一種新的無線通信模式正在迅猛發(fā)展，其主要思想是將智能城市中的傳感器[1，2]、移動邊緣設(shè)備[3]、智能車輛[4，5]、可穿戴設(shè)備[6]和電子醫(yī)療設(shè)備等所有對象都連接到互聯(lián)網(wǎng)中[7]。終端設(shè)備的電池壽命和計算能力有限[8]，因此云服務(wù)器通常用于接收和處理傳統(tǒng)物聯(lián)網(wǎng)網(wǎng)絡(luò)中各種終端卸載的數(shù)據(jù)[9，10]。由于云服務(wù)器中有豐富的能源，所以基于云的網(wǎng)絡(luò)比終端節(jié)點具有更高的處理能力[11]。傳感器和云網(wǎng)絡(luò)之間的數(shù)據(jù)傳輸會造成5G物聯(lián)網(wǎng)的工作負載中產(chǎn)生長時間延遲的問題。與此同時，在移動網(wǎng)絡(luò)邊緣處理這些工作負載也會帶來功耗的顯著增加。為了支持那些對延遲敏感的移動應(yīng)用，移動邊緣計算(mobile edge computing，MEC)應(yīng)運而生，即利用在移動設(shè)備附近的邊緣無線網(wǎng)絡(luò)為其提供計算能力。

目前工作負載分配已成為一個重要的研究問題，其重點是延遲提供QoS從而降低能耗。雖然邊緣服務(wù)器具有相對較小的延遲，但其在網(wǎng)絡(luò)邊緣的高功耗會導(dǎo)致分配給它們的工作負載急劇減少。目前在現(xiàn)有的研究中，在不修改邊緣服務(wù)器能量模型的情況下可以很好地解決工作負載分配問題，但是這會導(dǎo)致終端用戶的延遲增加。因此，本文在邊緣服務(wù)器的功耗和延遲之間進行折衷，通過使用遺傳算法改進邊緣服務(wù)器的能量模型。

1 相關(guān)工作

針對移動邊緣計算架構(gòu)中的任務(wù)卸載問題，文獻[12]提出了一種基于蟻群優(yōu)化算法的移動任務(wù)卸載算法。該算法同時考慮到了負載均衡和利潤最大化。文獻[12]提出了一種協(xié)同終端、邊緣節(jié)點和云中心的計算框架，有效提高了計算效率。文獻[13]提出了一種混合進化算法，用于在邊緣體系結(jié)構(gòu)中分配那些卸載的移動任務(wù)，以實現(xiàn)最小化任務(wù)的平均完成時間的目標。該卸載算法利用了混合人工蜂群算法和蟻群優(yōu)化算法。然而文獻[13]提出的卸載算法更側(cè)重于利用排隊網(wǎng)絡(luò)對邊緣服務(wù)器進行建模，并沒有考慮到異構(gòu)延遲以及其相應(yīng)的傳輸時間。文獻[14]提出了一種基于遺傳算法的卸載方法，用于在單個邊緣服務(wù)器上卸載部分移動任務(wù)。該卸載方法的最終目標是最小化移動任務(wù)的完成時間。然而，該卸載方法的重點在于確定移動任務(wù)如何實現(xiàn)部分卸載，以達到最小化移動任務(wù)完成時間的目標，卻沒有考慮到傳輸?shù)某杀尽Ｎ墨I[15]提出了一種基于強化學(xué)習(xí)的進化博弈卸載方法。然而，該方法沒有考慮到傳輸時間。文獻[16]針對位于霧節(jié)點上物聯(lián)網(wǎng)設(shè)備的任務(wù)提出了一種卸載方法。該卸載方法使用了兩種不同的進化算法，分別為蟻群優(yōu)化算法和粒子群優(yōu)化算法。該卸載方法的主要目標是在考慮霧節(jié)點和物聯(lián)網(wǎng)設(shè)備之間的通信成本的同時，實現(xiàn)霧節(jié)點的負載平衡，并最小化物聯(lián)網(wǎng)任務(wù)的響應(yīng)時間。文獻[17]提出了一種新的工作負載分配算法，稱為能量平衡算法(energy balance algorithm，EBA)。EBA使用兩種優(yōu)化模型來降低網(wǎng)絡(luò)中的能耗。仿真結(jié)果表明，所提出的EBA可以降低網(wǎng)絡(luò)和霧節(jié)點的能耗。與其它研究一樣，該研究僅嘗試優(yōu)化一個標準(能耗)并未提供平衡能耗和延遲的方法。因此，本文在邊緣服務(wù)器的功耗和延遲之間進行折衷，通過使用遺傳算法改進邊緣服務(wù)器的能量模型。

2 系統(tǒng)建模

在本文提出的模型中，工作負載主要由延遲和功耗兩部分組成，其中總延遲包括終端節(jié)點和邊緣服務(wù)器中請求的處理延遲，以及無線網(wǎng)絡(luò)中分組在終端節(jié)點和中央控制器之間的傳輸延遲。因此，決策時應(yīng)該考慮終端節(jié)點和邊緣服務(wù)器的功耗以及終端節(jié)點通過無線網(wǎng)絡(luò)傳輸請求所花費的時間。其中，邊緣服務(wù)器需要定期向控制器報告它們的可用性。

如圖1所示，邊緣服務(wù)器連接到中央控制器，并且根據(jù)設(shè)備可用性的概率將請求均勻地分布在這些設(shè)備之間。工作負載主要來自用戶到終端節(jié)點，節(jié)點要么在本地處理它們，要么將它們分布在可用的邊緣服務(wù)器中。

圖1 任務(wù)卸載模型

本文將從4個模型來研究本文提出的系統(tǒng)，分別為工作負載、延遲、功耗和電池狀態(tài)。首先針對每個模型給出一組方程，然后再使用遺傳算法對這些模型進行模擬。

2.1 工作負載

由于場景是基于離散時間模型的，因此將模擬時間劃分為較小的時間間隔，并在每個時間間隔中指定邊緣服務(wù)器的數(shù)量。l表示整個工作負載到達終端節(jié)點的速率，([lmin，lmax]∈l)。 然后，終端節(jié)點lt決定本地處理多少工作負載。最后，將工作負載l-lt(用li表示)分配給可用的邊緣服務(wù)器，每次分配中可用的邊緣服務(wù)器數(shù)量可能會隨著它們的可用性而變化。

2.2 延 遲

所提模型可以識別3種類型的延遲：

(1)通過無線網(wǎng)絡(luò)傳輸工作負載的延遲：在終端節(jié)點和中央控制器之間傳輸工作負載的延遲表示為dtrans， 并可以通過以下等式計算得出

(1)

其中，W表示終端節(jié)點和控制器之間的帶寬，Bi表示終端節(jié)點和邊緣服務(wù)器i的無線鏈路的頻譜效率。給定信號發(fā)送方的傳輸功率Bi由以下方程式(2)計算

(2)

其中，ri和ki分別是無線鏈路中的信道的丟失率和影響因子。在該等式中，Ii和N0分別表示干擾功率和噪聲功率譜的密度。

(2)終端節(jié)點中工作負載的處理延遲：終端節(jié)點中工作負載本地處理的延遲表示為dt。如果lt被分配給終端節(jié)點，需要ltnt個CPU周期。給定終端節(jié)點的頻率 (ft)， 本地處理的延遲通過以下等式計算得出

(3)

(3)邊緣服務(wù)器i中工作負載處理延遲：邊緣服務(wù)器i中工作負載處理延遲表示為di。如果li分配給邊緣服務(wù)器i，需要lini個CPU周期。將li位發(fā)送到邊緣服務(wù)器i，并且在處理之后將結(jié)果返回給終端節(jié)點，處理結(jié)果通常以小數(shù)據(jù)包和控制信號的形式出現(xiàn)，不需要考慮向終端節(jié)點發(fā)送最終結(jié)果的延遲。fi是邊緣服務(wù)器i的CPU頻率

(4)

因此，總體延遲為

(5)

2.3 功 耗

該系統(tǒng)主要包括以下3種類型的能耗：

(1)終端節(jié)點中處理數(shù)據(jù)包所消耗的能量：終端節(jié)點處理數(shù)據(jù)包所消耗的能量表示為Et，終端節(jié)點的每個CPU周期消耗的能量為θt，終端節(jié)點處理一位數(shù)據(jù)所消耗的能量為ntθt，如果將lt位分配給終端節(jié)點，功耗可以通過以下等式計算得出

Et=ltntθt

(6)

(2)通過無線信道將li位傳輸?shù)街醒肟刂破魉牡哪芰浚和ㄟ^無線信道將li位傳輸?shù)街醒肟刂破魉牡哪芰勘硎緸镋trans。Bi表示無線鏈路的頻譜效率，pi是信號發(fā)射器的傳輸功率。如果使用當(dāng)前帶寬W將li位分配給邊緣服務(wù)器i，傳輸能量將根據(jù)式(7)可以計算得出[10]。在向終端節(jié)點發(fā)送最終結(jié)果時不考慮其消耗的能量

(7)

(3)在邊緣服務(wù)器i中處理數(shù)據(jù)包所消耗的能量：在邊緣服務(wù)器i中處理數(shù)據(jù)包所消耗的能量表示為Ei。邊緣服務(wù)器在每個CPU周期中消耗的能量為θi，終端節(jié)點處理一位數(shù)據(jù)所消耗的能量為niθi，如果將li位分配給邊緣服務(wù)器i，功耗可以通過以下等式計算得出

Ei=liniθi

(8)

因此，l的總體功耗如下所示

(9)

2.4 電池狀態(tài)

間隔內(nèi)網(wǎng)絡(luò)邊緣處電池的最大總?cè)萘縯表示為b(t)∈[0，B]， 這些電池由太陽能和風(fēng)能進行充電。電池電量最初為零，之后再間隔t內(nèi)進行充電。如果在網(wǎng)絡(luò)邊緣使用的電池是空的，則將使用來自電網(wǎng)的電源。如果邊緣服務(wù)器消耗的能量總和Esum小于邊緣電池的電量，則處理數(shù)據(jù)包所需的全部能量將由電池提供。否則，電池消耗量將減少b(t)， 而電網(wǎng)的耗電量將為Esum-b(t)。 如果將電池能量用于處理請求，邊緣服務(wù)器的功耗模型可以得到改善，因為更多的請求會被發(fā)送到這些設(shè)備上，終端用戶的QoS也會有很大提高

P1：minDtotal

(10)

s.t.Etrans0≤li≤l，0≤Pi≤Pmax

在問題P1中，最終目標是根據(jù)能量限制和傳輸?shù)竭吘壏?wù)器的數(shù)據(jù)包數(shù)量來最大限度地減少終端用戶的延遲。Emax是終端節(jié)點的最大功耗。第一個限制表示在向中央控制器傳輸請求期間，終端節(jié)點傳輸請求所消耗的能量不得超過該節(jié)點的最大能量。根據(jù)第二個限制，發(fā)送到中央控制器的請求數(shù)和終端節(jié)點的控制器不得超過傳輸?shù)酱斯?jié)點的負載，終端節(jié)點的傳輸功率必須在0和Emax之間。

3 基于遺傳算法的任務(wù)卸載算法

由于存在多個變量，終端節(jié)點和邊緣服務(wù)器的工作負載分配問題的方法并不簡單。邊緣計算任務(wù)調(diào)度的目標通常是優(yōu)化具體指標，包括服務(wù)質(zhì)量、功耗、延遲和負載均衡性能。本章對提出的面向邊緣環(huán)境的基于進化算法(即改進遺傳算法)的移動卸載算法進行了詳細闡述。

對于具有多個局部最優(yōu)的問題，遺傳算法是首選。遺傳算法根據(jù)“適者生存”的原則確定每個種群的適應(yīng)度函數(shù)，從而對任務(wù)進行調(diào)度。該算法在考慮了傳輸成本和邊緣服務(wù)器負載的同時，以最小化總體延遲為目標，在可用的邊緣服務(wù)器找到分配卸載任務(wù)的位置。

3.1 基于遺傳算法的任務(wù)卸載方法

遺傳算法一種基于生物學(xué)概念中模擬進化論的自然選擇和生成隨機解群體的進化算法。遺傳算法被廣泛地應(yīng)用于解決各種NP完全問題，包括旅行推銷員問題、云計算調(diào)度和負載平衡[18]。在遺傳算法中，每個可能的解都會被編碼為一組由基因組成的染色體。每一組生成的可能解將會被集合成為一個種群。接著，問題的解決方案將從該種群中通過特定的選擇機制獲取選擇到。

3.1.1 染色體編碼

每個染色體代表著一個可能的解決方案，用于在邊緣服務(wù)器上調(diào)度所有卸載的任務(wù)集。每個染色體都是一個大小為Nts的向量，其中Nts為卸載任務(wù)的個數(shù)。染色體中每個元素分別對應(yīng)著編號為1到Nts的一個基因，其順序也與卸載任務(wù)的ID相對應(yīng)，且每個基因的值表示對應(yīng)放置的邊緣服務(wù)器ID。例如，圖2中所示的染色體表示了一個邊緣服務(wù)器上有5個卸載任務(wù)。

圖2 染色體編碼示例

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

適應(yīng)度的值越大的個體染色體在種群進化中越容易存活。即適應(yīng)度值越高，表示總?cè)蝿?wù)響應(yīng)時間越短。因此，適應(yīng)度函數(shù)的公式如式(11)所示

(11)

其中，Dtotal可通過式(5)計算得到。

3.1.3 種群初始化

種群是一組個體解的集合，其中每個個體解都將被編碼到染色體中。同時，每個染色體代表著一個將移動任務(wù)卸載到邊緣服務(wù)器的調(diào)度方案。種群在初始狀態(tài)時，許多個體解將被隨機地生成。

3.1.4 選擇

在選擇運算階段中，為了下一代種群，應(yīng)當(dāng)選擇具有良好特性的個體染色體，以獲得最優(yōu)解。輪盤選擇法可用于選擇個體染色體。在輪盤選擇法中，每個候選解的概率如式(12)所示

(12)

其中，f(ε) 為個體染色體ε的適應(yīng)度值，N為種群中的個體數(shù)。接著，輪盤選擇法將計算累積概率并將其按升序排序。從[0，1]中生成一個隨機數(shù)并與累積概率值進行比較，然后選擇相應(yīng)的個體染色體。通過以上步驟，可以確保在選擇過程中能夠選擇到具有更高適應(yīng)度值的個體和潛在的有效解。

3.1.5 交叉

交叉運算將兩條個體染色體結(jié)合并生成一個新的個體。根據(jù)隨機生成的交叉點，單點交叉將位于染色體交叉點一側(cè)的部分與另一染色體的同一側(cè)的部分交換。如圖3所示，一對新的個體染色體已生成。

3.1.6 變異

在變異運算中，隨機的兩個基因的值將相互替換。此時，如圖4所示，已為下一代種群生成了一個新的個體。變異運算使得生成的下一代種群具有多樣性，避免了染色體之間變得相似。因此，通過避免局部極小值可強化局部搜索能力。

圖4 染色體編碼示例

3.1.7 遺傳終止條件

經(jīng)過上述操作，可以獲得新一代個體種群。然后，根據(jù)式(11)，計算個體群體的適應(yīng)度值以進行評估。如果總體的最大適應(yīng)度值與平均適應(yīng)度值相差不大，或者達到了預(yù)設(shè)的最大迭代次數(shù)，則算法停止并輸出適應(yīng)度值。否則，繼續(xù)執(zhí)行算法，直到滿足停止條件。

3.2 算法流程

如算法1所示，本文提出的基于遺傳算法的卸載算法首先需初始化相關(guān)參數(shù)，包括任務(wù)個數(shù)Nts、邊緣服務(wù)器個數(shù)i、最大迭代次數(shù)Niter、種群Np中的染色體個數(shù)、交叉概率Pc和變異概率Pmu。 接著，該算法將隨機生成初始種群，并計算出每個個體對應(yīng)的適應(yīng)度值。然后，該算法以最大迭代次數(shù)進行迭代。在每次迭代中，通過生成一個隨機數(shù)實現(xiàn)單點交叉運算，并將隨機數(shù)與交叉概率Pc進行比較。如果隨機數(shù)的值小于Pc， 則將使用隨機交叉點執(zhí)行交叉運算操作。其次，對兩個隨機基因之間產(chǎn)生的新染色體進行變異運算操作。最后，通過應(yīng)用輪盤選擇算法對種群和新的個體一起執(zhí)行選擇運算，此時新的種群將應(yīng)用于下一輪迭代。

算法1：基于遺傳算法的任務(wù)卸載算法

Begin

(1) 初始化參數(shù):Nts、i、Niter、Np、Pc和Pmu。

(2) 隨機產(chǎn)生Np條染色體

(3) 使用式(8)計算粒子染色體的適應(yīng)度值

(4)foreach iter inNiterdo

(5)ifrand()

(6) 通過隨機選擇交叉點來執(zhí)行單點交叉, 以創(chuàng)建新的個體

(7)end

(8) 對新染色體應(yīng)用變異算子, 如下所示:

(9)for染色體i上的每個基因do

(10)ifrand()

(11)gene1=random index

(12)gene2=random index

(13)gene1和gene2交換基因

(14)end

(15)end

(16)通過應(yīng)用輪盤賭選擇, 依托舊種群和新個體創(chuàng)建新種群

(17)新的種群將用于下一輪迭代

End

3.3 時間復(fù)雜度

基于遺傳算法的任務(wù)卸載算法的時間復(fù)雜度取決于選擇運算、交叉運算和變異運算的時間復(fù)雜度。選擇運算的時間復(fù)雜度為O(Niter×Np×Nts)。 交叉運算和變異運算的時間復(fù)雜度均為O(Niter×Np)。 因此，該算法的總體時間復(fù)雜度為O(Niter×Np×Nts)。

4 實驗與分析

提出的算法在一個具有5核3.5 GHz CPU和8 GB RAM的系統(tǒng)上進行實驗，本節(jié)對在MATLAB R2016a中實現(xiàn)該算法的結(jié)果進行分析和評估。表1展示了模擬實驗場景的參數(shù)設(shè)置。本節(jié)假設(shè)了一個基于終端節(jié)點和10臺邊緣服務(wù)器的模型，請求在終端節(jié)點或可用邊緣服務(wù)器上處理。

表1 模擬實驗的參數(shù)設(shè)置

路徑損耗因子ri(單位：dB)通過以下方式獲得：-(38.46+20log10(Di))， 其中Di(in m) 是終端節(jié)點和邊緣服務(wù)器i之間的距離。下面，安排兩個不同的場景，考慮到工作負載分配給終端節(jié)點和具有兩個不同傳輸功率值的可訪問邊緣服務(wù)器。在第一個場景中，終端節(jié)點傳輸在另一種情況下，終端節(jié)點以其最大功率將數(shù)據(jù)包發(fā)送給中央控制器，而在另一種情況下，終端節(jié)點以其一半的容量將數(shù)據(jù)包發(fā)送給中央控制器。在后一種情況下，總能耗將增加，但邊緣服務(wù)器的能耗沒有變化。在這些情況下，整體電流功耗超過θi。

4.1 基于最大傳輸功率的工作負載分配

在這種情況下，終端節(jié)點以其最大功率將數(shù)據(jù)包發(fā)送給中央控制器。在圖5中，橫軸表示終端節(jié)點的最大傳輸量，分別設(shè)置為2 MB、4 MB、6 MB和8 MB，縱軸表示總延遲。圖6表示終端節(jié)點最大傳輸量為2 MB、4 MB、6 MB和8 MB時邊緣服務(wù)器的總能耗。在圖6中，橫軸設(shè)置與圖5相同，而縱軸則表示總能耗。從圖5中可以看出，當(dāng)傳輸?shù)浇K端節(jié)點的工作負載為2 MB時，幾種方法總延遲將保持在2 s以下。當(dāng)傳輸?shù)浇K端節(jié)點的工作負載增加到4 MB、6 MB和8 MB時，幾種方法的總延遲也隨之遞增。從圖5中還可以看出，所提方法和文獻[14]方法得到較優(yōu)結(jié)果，總延遲低于文獻[13]和文獻[15]方法。根據(jù)圖6中的結(jié)果，當(dāng)傳輸?shù)浇K端節(jié)點的工作負載為2 MB時，幾種方法總延遲將保持在4 J以下。當(dāng)傳輸?shù)浇K端節(jié)點的工作負載增加到4 MB、6 MB和8 MB時，幾種方法的總能耗也隨之遞增。其中，所提方法和文獻[13]方法得到較優(yōu)結(jié)果，總延遲低于文獻[14]和文獻[15]方法。這是因為文獻[14]和文獻[15]方法的重點在于確定移動任務(wù)如何實現(xiàn)部分卸載，以達到最小化移動任務(wù)完成時間的目標，忽略了傳輸?shù)某杀尽?/p>

圖5 終端節(jié)點最大傳輸量為2 MB、4 MB、6 MB和8 MB時的總延遲

圖6 終端節(jié)點最大傳輸量為2 MB、4 MB、6 MB和8 MB時邊緣服務(wù)器的總能耗

4.2 基于半容量傳輸功率的工作負載分配

在這種情況下，終端節(jié)點以其一半的容量將數(shù)據(jù)包發(fā)送給中央控制器。終端節(jié)點向中央控制器發(fā)送數(shù)據(jù)包所消耗的能量大于以全功率發(fā)送數(shù)據(jù)包時所消耗的能量。如圖7所示，橫軸表示終端節(jié)點的最大傳輸量，分別設(shè)置為2 MB、4 MB、6 MB和8 MB，縱軸表示總延遲。從圖中可以看出，當(dāng)傳輸?shù)浇K端節(jié)點的工作負載為2 MB時，幾種方法總延遲將保持在2 s左右。當(dāng)傳輸?shù)浇K端節(jié)點的工作負載增加到4 MB、6 MB和8 MB時，幾種方法的總延遲也隨之遞增。圖8表示終端節(jié)點最大傳輸量為2 MB、4 MB、6 MB和8 MB時邊緣服務(wù)器的總能耗。根據(jù)圖8中的結(jié)果，當(dāng)傳輸?shù)浇K端節(jié)點的工作負載為2 MB時，幾種方法總延遲將保持在4 J上下。當(dāng)傳輸?shù)浇K端節(jié)點的工作負載增加到4 MB、6 MB和8 MB時，幾種方法的總能耗也隨之遞增。綜合來看，所提方法在邊緣服務(wù)器的功耗和延遲之間進行了折衷，總延遲與文獻[14]方法相近，略低于文獻[13]和文獻[15]方法；而總能耗和文獻[13]方法，略低于文獻[14]和文獻[15]方法。而幾種對比方法僅嘗試優(yōu)化一個標準并未提供平衡能耗和延遲的方法，因此綜合性能略遜于所提方法。

圖7 終端節(jié)點傳輸功率為2 MB、4 MB、6 MB和8 MB時的總延遲

圖8 終端節(jié)點傳輸功率為2 MB、4 MB、6 MB和8 MB時邊緣服務(wù)器的總能耗

5 結(jié)束語

目前工作負載分配已成為一個重要的研究問題，其重點是延遲提供QoS從而降低能耗?？紤]到服務(wù)質(zhì)量和安全性對延遲敏感類請求的重要性，本文提出了一種基于改進遺傳算法的MEC計算資源優(yōu)化策略。仿真實驗結(jié)果表明，提出的方法不僅降低了邊緣服務(wù)器的功耗，而且顯著降低了物聯(lián)網(wǎng)數(shù)據(jù)包處理的延遲問題。與基準策略相比本文提出的方法可以同時降低邊緣設(shè)備的時延和功耗。此外，在使用遺傳算法的兩個模擬場景中，物聯(lián)網(wǎng)請求以全容量和半容量方式發(fā)送給控制器，在這兩種情況下功耗和延遲都得到了較大的改善。

深度學(xué)習(xí)方法包括深度神經(jīng)網(wǎng)絡(luò)等已被驗證是多目標優(yōu)化問題的有效方法，因此未來的研究方向就是將這些方法應(yīng)用于基于MEC的多目標工作負載分配研究中。