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

王 麗，王曉凱

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

0 引 言

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

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

1 相關(guān)工作

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

2 系統(tǒng)建模

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

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

圖1 任務卸載模型

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

2.1 工作負載

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

2.2 延 遲

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

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

(1)

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

(2)

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

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

(3)

(3)邊緣服務器i中工作負載處理延遲：邊緣服務器i中工作負載處理延遲表示為di。如果li分配給邊緣服務器i，需要lini個CPU周期。將li位發(fā)送到邊緣服務器i，并且在處理之后將結(jié)果返回給終端節(jié)點，處理結(jié)果通常以小數(shù)據(jù)包和控制信號的形式出現(xiàn)，不需要考慮向終端節(jié)點發(fā)送最終結(jié)果的延遲。fi是邊緣服務器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ā)射器的傳輸功率。如果使用當前帶寬W將li位分配給邊緣服務器i，傳輸能量將根據(jù)式(7)可以計算得出[10]。在向終端節(jié)點發(fā)送最終結(jié)果時不考慮其消耗的能量

(7)

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

Ei=liniθi

(8)

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

(9)

2.4 電池狀態(tài)

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

P1：minDtotal

(10)

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

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

3 基于遺傳算法的任務卸載算法

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

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

3.1 基于遺傳算法的任務卸載方法

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

3.1.1 染色體編碼

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

圖2 染色體編碼示例

3.1.2 適應度函數(shù)

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

(11)

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

3.1.3 種群初始化

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

3.1.4 選擇

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

(12)

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

3.1.5 交叉

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

3.1.6 變異

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

圖4 染色體編碼示例

3.1.7 遺傳終止條件

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

3.2 算法流程

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

算法1：基于遺傳算法的任務卸載算法

Begin

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

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

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

(4)foreach iter inNiterdo

(5)ifrand()

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

(7)end

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

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

(10)ifrand()

(11)gene1=random index

(12)gene2=random index

(13)gene1和gene2交換基因

(14)end

(15)end

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

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

End

3.3 時間復雜度

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

4 實驗與分析

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

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

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

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

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

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

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

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

在這種情況下，終端節(jié)點以其一半的容量將數(shù)據(jù)包發(fā)送給中央控制器。終端節(jié)點向中央控制器發(fā)送數(shù)據(jù)包所消耗的能量大于以全功率發(fā)送數(shù)據(jù)包時所消耗的能量。如圖7所示，橫軸表示終端節(jié)點的最大傳輸量，分別設置為2 MB、4 MB、6 MB和8 MB，縱軸表示總延遲。從圖中可以看出，當傳輸?shù)浇K端節(jié)點的工作負載為2 MB時，幾種方法總延遲將保持在2 s左右。當傳輸?shù)浇K端節(jié)點的工作負載增加到4 MB、6 MB和8 MB時，幾種方法的總延遲也隨之遞增。圖8表示終端節(jié)點最大傳輸量為2 MB、4 MB、6 MB和8 MB時邊緣服務器的總能耗。根據(jù)圖8中的結(jié)果，當傳輸?shù)浇K端節(jié)點的工作負載為2 MB時，幾種方法總延遲將保持在4 J上下。當傳輸?shù)浇K端節(jié)點的工作負載增加到4 MB、6 MB和8 MB時，幾種方法的總能耗也隨之遞增。綜合來看，所提方法在邊緣服務器的功耗和延遲之間進行了折衷，總延遲與文獻[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時邊緣服務器的總能耗

5 結(jié)束語

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

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