賈 覲，暴占彪

(1.河南財(cái)經(jīng)政法大學(xué) 網(wǎng)絡(luò)信息服務(wù)中心，河南 鄭州 450000；2.河南財(cái)經(jīng)政法大學(xué) 現(xiàn)代教育技術(shù)中心，河南 鄭州 450000)

0 引 言

隨著智能應(yīng)用的日益普及，增強(qiáng)型超可靠移動(dòng)寬帶、大規(guī)模數(shù)據(jù)通信以及超低通信延遲3大類業(yè)務(wù)對(duì)運(yùn)營商的傳輸網(wǎng)絡(luò)和核心網(wǎng)都提出了巨大的挑戰(zhàn)[1,2]。雖然5G網(wǎng)絡(luò)可以給用戶帶來更高的帶寬速率、更多的網(wǎng)絡(luò)連接和更低的延遲，但是這也將導(dǎo)致單位時(shí)間內(nèi)核心網(wǎng)需要處理的數(shù)據(jù)量和業(yè)務(wù)請(qǐng)求數(shù)呈爆炸式增長[3,4]。

另一方面，由所有應(yīng)用產(chǎn)生的數(shù)據(jù)都需要通過核心網(wǎng)進(jìn)行交互，所以在業(yè)務(wù)接入高峰期會(huì)給通信網(wǎng)絡(luò)負(fù)載造成很大壓力。與云計(jì)算在網(wǎng)絡(luò)方面的局限性相比，移動(dòng)邊緣計(jì)算集成網(wǎng)絡(luò)通信、數(shù)據(jù)計(jì)算和處理等業(yè)務(wù)，形成一個(gè)開放平臺(tái)，提供給用戶更接近于實(shí)體或數(shù)據(jù)源的服務(wù)，使其應(yīng)用能夠在邊緣端進(jìn)行任務(wù)處理，從而實(shí)現(xiàn)更高效的網(wǎng)絡(luò)服務(wù)響應(yīng)，滿足更多業(yè)務(wù)場景在實(shí)時(shí)處理、智能應(yīng)用、安全和隱私保護(hù)等方面的需求[5,6]。換言之，移動(dòng)邊緣計(jì)算的核心思想是將計(jì)算資源和緩存資源邊緣化和本地化，從而減少網(wǎng)絡(luò)延遲，緩解帶寬的壓力。移動(dòng)邊緣計(jì)算不僅滿足了移動(dòng)設(shè)備擴(kuò)展計(jì)算能力的需要，而且彌補(bǔ)了云計(jì)算中傳輸延遲長的缺點(diǎn)[7]。

由于不同應(yīng)用場景下對(duì)任務(wù)處理具有不同的計(jì)算量和數(shù)據(jù)傳輸量要求，因此為了確保移動(dòng)設(shè)備能夠發(fā)揮其最佳性能，可以通過使用任務(wù)卸載策略來進(jìn)行資源的優(yōu)化分配，制定任務(wù)是在本地處理或是在遠(yuǎn)程服務(wù)器上執(zhí)行的處理方案[8]。同時(shí)，由于移動(dòng)邊緣計(jì)算服務(wù)器在計(jì)算、存儲(chǔ)、帶寬等方面的資源均十分有限，而為了實(shí)現(xiàn)較低的網(wǎng)絡(luò)延，且更好地利用邊緣服務(wù)器集群有限的資源，任務(wù)卸載策略首先需要明確其目標(biāo)服務(wù)器再進(jìn)行任務(wù)卸載[9]。目前，任務(wù)卸載策略主要分為粗粒度任務(wù)卸載和細(xì)粒度任務(wù)卸載兩種類型。粗粒度任務(wù)卸載通常以移動(dòng)應(yīng)用程序?yàn)樾遁d對(duì)象，且不會(huì)根據(jù)其功能劃分為多個(gè)不同的子任務(wù)。該類方法往往沒有充分考慮到整個(gè)應(yīng)用的傳輸延遲和傳輸消耗。細(xì)粒度任務(wù)卸載一般首先會(huì)將一個(gè)移動(dòng)應(yīng)用劃分為多個(gè)具有數(shù)據(jù)依賴關(guān)系的子任務(wù)[10,11]。由于劃分后的子任務(wù)只需要較少的計(jì)算復(fù)雜度和數(shù)據(jù)傳輸量，因此細(xì)粒度任務(wù)卸載可以將部分或全部的子任務(wù)都卸載到多個(gè)遠(yuǎn)程服務(wù)器上進(jìn)行處理，從而節(jié)省了計(jì)算時(shí)間和傳輸時(shí)間，實(shí)現(xiàn)了對(duì)邊緣服務(wù)器集群資源更高效的利用。

因此，針對(duì)大規(guī)模異構(gòu)移動(dòng)邊緣計(jì)算中具有多服務(wù)節(jié)點(diǎn)和多依賴移動(dòng)子任務(wù)的場景，提出了一種移動(dòng)邊緣計(jì)算環(huán)境下基于改進(jìn)遺傳算法的計(jì)算任務(wù)卸載與資源分配算法，利用改進(jìn)遺傳算法來解決細(xì)粒度的任務(wù)決策問題，包括明確卸載內(nèi)容、卸載數(shù)量以及卸載目標(biāo)等問題,從而達(dá)到移動(dòng)邊緣計(jì)算平臺(tái)在時(shí)延、成本、能耗和網(wǎng)絡(luò)使用率多方面降低的目的。

1 相關(guān)工作

為了降低移動(dòng)設(shè)備的能量消耗，提高現(xiàn)有設(shè)備計(jì)算能力，并有效地利用邊緣服務(wù)器和云數(shù)據(jù)中心的計(jì)算資源，近年對(duì)移動(dòng)邊緣計(jì)算中的卸載問題已有了較深入的研究。一般來說，調(diào)度可以定義為在特定時(shí)間內(nèi)將任務(wù)分配給有能力的資源[12]。并且，一個(gè)調(diào)度問題常常需要服從許多必須滿足的約束條件和目標(biāo)。調(diào)度問題可以映射成為一個(gè)最優(yōu)化的問題，比如移動(dòng)邊緣計(jì)算中的計(jì)算卸載與資源分配決策的目標(biāo)可以設(shè)定為延遲的最小化以及資源利用率的最大化。大多數(shù)的調(diào)度問題往往包含資源、任務(wù)、約束以及目標(biāo)4個(gè)基本要素，其中資源是能夠執(zhí)行或處理任務(wù)的物理或邏輯設(shè)備；任務(wù)是需要由資源執(zhí)行的物理或邏輯操作；約束是將任務(wù)調(diào)度到資源中時(shí)必須考慮的條件；而目標(biāo)則是為了評(píng)估調(diào)度的表現(xiàn)而進(jìn)行衡量的評(píng)估標(biāo)準(zhǔn)。

分析相關(guān)研究可以發(fā)現(xiàn)，對(duì)于任務(wù)卸載和資源分配的調(diào)度類技術(shù)通常包含兩大類方法：精確方法和啟發(fā)式方法[13]。精確方法可以找到調(diào)度問題的絕對(duì)最優(yōu)解。文獻(xiàn)[14]采用了混合整數(shù)非線性規(guī)劃方法來解決任務(wù)卸載問題，并最終實(shí)現(xiàn)了用戶成本的降低。但該方案在傳輸延遲性方面還有進(jìn)一步提升的空間[15]。文獻(xiàn)[16]提出了一種面向邊緣計(jì)算的用戶請(qǐng)求數(shù)量預(yù)測模型，并在此基礎(chǔ)上設(shè)計(jì)了一種任務(wù)卸載方案。通過比較該算法與貪婪算法、線性規(guī)劃算法和遺傳算法在任務(wù)卸載方面的性能，驗(yàn)證了該算法的有效性。文獻(xiàn)[17]建立了一種基于移動(dòng)邊緣計(jì)算體系結(jié)構(gòu)的數(shù)學(xué)模型。該數(shù)學(xué)模型通過測量用戶設(shè)備與處于網(wǎng)絡(luò)邊緣的移動(dòng)邊緣計(jì)算服務(wù)器之間的往返時(shí)間實(shí)現(xiàn)了移動(dòng)邊緣計(jì)算卸載策略的最優(yōu)化，并確定了何時(shí)將用戶的計(jì)算任務(wù)卸載到移動(dòng)邊緣計(jì)算服務(wù)器進(jìn)行處理。文獻(xiàn)[18]研究了移動(dòng)邊緣計(jì)算卸載場景下的多用戶服務(wù)延遲問題，并提出了一種部分計(jì)算卸載模型。采用最優(yōu)化策略來優(yōu)化通信和計(jì)算資源的分配。與任務(wù)在只本地執(zhí)行或邊緣執(zhí)行的方案相比，該文所提出的部分卸載策略可以實(shí)現(xiàn)所有用戶設(shè)備的延遲的最小化，從而提高了用戶的服務(wù)質(zhì)量。

而啟發(fā)式方法雖然并不能保證找到最優(yōu)解，但是與采用精確方法所需的時(shí)間相比，啟發(fā)式方法能夠在合理的計(jì)算時(shí)間內(nèi)找到具有某種程度的最優(yōu)解。文獻(xiàn)[19]在提出的啟發(fā)式算法的基礎(chǔ)上，引入了多拓?fù)渎酚?，來確保所分配的出口路由器具有近似最優(yōu)解的性能。實(shí)驗(yàn)結(jié)果表明，與其它方法相比，該算法具有更低的執(zhí)行時(shí)間和更好的服務(wù)質(zhì)量，滿足了云計(jì)算和邊緣計(jì)算中網(wǎng)絡(luò)流量問題的靈活性和效率要求?？紤]到環(huán)境的性質(zhì)，安全性是移動(dòng)邊緣計(jì)算中所面臨的一個(gè)主要挑戰(zhàn)，文獻(xiàn)[20]提出了一個(gè)網(wǎng)絡(luò)安全框架，可識(shí)別出在移動(dòng)邊緣計(jì)算環(huán)境中的惡意邊緣設(shè)備。該框架采用兩階段馬爾可夫模型對(duì)惡意或合法邊緣設(shè)備進(jìn)行早期預(yù)測。并且實(shí)驗(yàn)結(jié)果表明了提出的框架的有效性。

但是啟發(fā)式算法容易陷入只能獲取到局部最小值的困境，從而難以得到整體的最優(yōu)解，并且不適用于移動(dòng)邊緣計(jì)算環(huán)境中海量的數(shù)據(jù)處理，為此，提出了一種移動(dòng)邊緣計(jì)算中基于改進(jìn)遺傳算法的計(jì)算卸載與資源分配算法。其創(chuàng)新點(diǎn)總結(jié)如下：

(1)為了高效處理網(wǎng)絡(luò)中海量的數(shù)據(jù)，構(gòu)建了移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)模型，其中包括能耗、平均服務(wù)延遲、執(zhí)行時(shí)間以及負(fù)載均衡模型，以合理卸載設(shè)備服務(wù)請(qǐng)求且優(yōu)化計(jì)算資源的分配。

(2)由于現(xiàn)有算法存在延遲較大且負(fù)載不均衡的問題，所提算法以能耗、延遲、負(fù)載均衡最小化為優(yōu)化目標(biāo)，利用改進(jìn)的遺傳算法進(jìn)行求解，并且從染色體一維表現(xiàn)形式、交叉和變異算子等方面進(jìn)行改進(jìn)以提高算法的性能。

2 系統(tǒng)建模

移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)通常包括3個(gè)部分，分別為云數(shù)據(jù)中心層、邊緣計(jì)算層和移動(dòng)請(qǐng)求設(shè)備層，其架構(gòu)如圖1所示。移動(dòng)請(qǐng)求設(shè)備層包含了傳感器、筆記本電腦、手機(jī)等處理性能較低的設(shè)備；邊緣計(jì)算層將所有的邊緣服務(wù)器按其相對(duì)距離劃分成為多個(gè)區(qū)域，且每個(gè)區(qū)域均中包含了一些性能中等的異構(gòu)邊緣計(jì)算服務(wù)器；云數(shù)據(jù)中心層包含了可形成一個(gè)群集的大量高性能物理服務(wù)器。

圖1 移動(dòng)邊緣計(jì)算的架構(gòu)

當(dāng)移動(dòng)請(qǐng)求設(shè)備需要通過計(jì)算卸載和資源分配來提高性能時(shí)，那么整個(gè)移動(dòng)請(qǐng)求任務(wù)會(huì)通過分割算法被劃分為若干個(gè)子任務(wù)。其中一些子任務(wù)必須在本地執(zhí)行，例如用戶交互任務(wù)、設(shè)備輸入/輸出任務(wù)和外圍接口任務(wù)，而另一些任務(wù)可以卸載到服務(wù)器上執(zhí)行，通常是計(jì)算量比較大的數(shù)據(jù)處理任務(wù)。

2.1 能耗模型

對(duì)于包括了智能手機(jī)、傳感器和遠(yuǎn)程服務(wù)器在內(nèi)的所有請(qǐng)求設(shè)備，在一定執(zhí)行時(shí)間內(nèi)的總能耗主要由兩個(gè)部分組成，即所有設(shè)備的計(jì)算能耗Ecom和移動(dòng)設(shè)備的卸載能耗Eoff。 其中第m個(gè)計(jì)算資源的能耗模型為

(1)

(2)

式中：taskm表示第m個(gè)計(jì)算資源中所有任務(wù)的數(shù)量，Mn表示部署第n個(gè)子任務(wù)所需的CPU資源，CMm表示第m個(gè)計(jì)算資源內(nèi)的CPU總資源。同時(shí)將第n個(gè)請(qǐng)求設(shè)備在某一信道中的數(shù)據(jù)傳輸速率rn定義為

(3)

(4)

(5)

系統(tǒng)中，計(jì)算資源的總數(shù)量為 (1+M+N)， 以及請(qǐng)求設(shè)備的總數(shù)量是N， 則在單位時(shí)間t內(nèi)產(chǎn)生的計(jì)算能耗與卸載能耗為

(6)

2.2 平均服務(wù)延遲

(7)

(8)

則在單位時(shí)間t內(nèi)，第m個(gè)子任務(wù)的數(shù)據(jù)傳輸延遲Dtr為

(9)

另外，在單位時(shí)間t內(nèi)，第m個(gè)子任務(wù)由于處理數(shù)據(jù)而產(chǎn)生的計(jì)算延遲Dcom為

(10)

式中：vserver(t) 表示遠(yuǎn)程服務(wù)器部署第m個(gè)子任務(wù)的處理速率，vlocal(t) 表示本地設(shè)備部署第個(gè)子任務(wù)的處理速率，xoff用來表示當(dāng)前子任務(wù)是否卸載到遠(yuǎn)程服務(wù)器執(zhí)行。

根據(jù)以上分析，單位時(shí)間t內(nèi)所有請(qǐng)求設(shè)備的平均時(shí)延為

2.2兩組患者治療前后PANSS評(píng)分比較 治療前,觀察組PANSS評(píng)分為(90.11±5.82)分,對(duì)照組PANSS評(píng)分為(89.82±5.79)分,兩組比較差異無統(tǒng)計(jì)學(xué)意義(t=0.215,P=0.830>0.05)。治療后,觀察組PANSS評(píng)分為(42.08±3.11)分,對(duì)照組PANSS評(píng)分為(50.82±3.28)分,兩組比較差異有統(tǒng)計(jì)學(xué)意義(t=11.762,P=0.000<0.05)。

(11)

式中：Dtotal(t0) 表示所有請(qǐng)求設(shè)備的總延遲，表示請(qǐng)求設(shè)備的數(shù)量， Ωn表示在第n個(gè)請(qǐng)求設(shè)備被劃分后的子任務(wù)數(shù)。

2.3 平均執(zhí)行時(shí)間

執(zhí)行時(shí)間指的是子任務(wù)處理數(shù)據(jù)所需的時(shí)間。當(dāng)子任務(wù)可以使用的資源越多時(shí)，那么子任務(wù)所需的處理時(shí)間越短，同時(shí)在單位時(shí)間內(nèi)子任務(wù)可以處理的請(qǐng)求越多。因此，卸載決策需要盡可能減少所有請(qǐng)求設(shè)備的平均執(zhí)行時(shí)間。平均執(zhí)行時(shí)間的計(jì)算如下

(12)

式中：T(t0) 表示在單位時(shí)間內(nèi)所有請(qǐng)求設(shè)備的平均執(zhí)行時(shí)間。

2.4 負(fù)載平衡目標(biāo)

負(fù)載平衡是一種可在網(wǎng)絡(luò)中實(shí)現(xiàn)各種資源有效利用的重要方法，其主要目的是資源最優(yōu)化利用、最大化吞吐量、最小化響應(yīng)時(shí)間，避免過載，增強(qiáng)網(wǎng)絡(luò)數(shù)據(jù)處理能力，以及提高網(wǎng)絡(luò)的靈活性和可用性[22]。網(wǎng)絡(luò)中所有設(shè)備的負(fù)載平衡優(yōu)化目標(biāo)為

(13)

(14)

(15)

3 提出的遺傳算法

由于移動(dòng)邊緣計(jì)算中計(jì)算卸載和資源分配問題在本質(zhì)上存在著復(fù)雜性，精確的最優(yōu)解不充分，因此，采用改進(jìn)的遺傳算法對(duì)問題進(jìn)行求解[23]。遺傳算法是一種由自然選擇過程產(chǎn)生的元啟發(fā)式算法，其屬于一類進(jìn)化算法。在此進(jìn)化算法中，優(yōu)化問題的候選解(染色體)群體可進(jìn)化為更好或更適合的解。

在計(jì)算卸載和資源分配問題中，種群染色體可以用來表示問題的候選解，如果一個(gè)解滿足問題的約束條件，那么其就是可行的；否則是不可行的[24]。提出的遺傳算法中根據(jù)問題需要采用染色體表現(xiàn)形式、交叉和變異算子，用于懲罰不可行的解決方案，使這些不可行的解決方案具有較小的選擇(或生存)概率。所提算法的流程如圖2所示。

圖2 所提改進(jìn)遺傳算法的處理流程

首先定義問題的規(guī)模，即請(qǐng)求設(shè)備的數(shù)量和可用的計(jì)算資源，并且生成種群數(shù)量的候選解(染色體或個(gè)體)，以初始化群體。然后評(píng)估每個(gè)染色體的適應(yīng)度F，F(xiàn)為總潛伏期的倒數(shù)，并且選擇即將進(jìn)行交叉和突變的配偶或親本個(gè)體(染色體)，從當(dāng)前種群中創(chuàng)建新的后代種群。在完成交叉和變異后，該算法根據(jù)適應(yīng)度函數(shù)F來評(píng)價(jià)每個(gè)產(chǎn)生的子代染色體的適應(yīng)度值。最后，使用一個(gè)程序確定不可行的染色體，以及使用另一個(gè)程序懲罰其中的一些染色體。此外，該算法保留了所有產(chǎn)生的種群中的最好染色體，即適應(yīng)值最小的染色體。遺傳算法會(huì)不斷重復(fù)上述步驟，直到滿足一些終止的條件。當(dāng)?shù)K止時(shí)，遺傳算法會(huì)返回代表優(yōu)化問題解決方案的最佳染色體。

在改進(jìn)的遺傳算法中，算子的實(shí)現(xiàn)如下：

(1)染色體表示：在提出的遺傳算法中，問題的候選解決方案(染色體)是一個(gè)0或1個(gè)整數(shù)值Xmn元素(或基因)的二維數(shù)組，其表示考慮到在m個(gè)計(jì)算資源分配給n個(gè)請(qǐng)求設(shè)備的情況下向資源分配請(qǐng)求的可能。如果請(qǐng)求rn被分配給資源sm， 則基因Xmn的值為1；否則為0。為了獲得表示染色體的一維解數(shù)組，二維數(shù)組被垂直拉伸，如圖3所示。

圖3 染色體的二維排列

(2)適應(yīng)度評(píng)價(jià)：對(duì)于群體的每個(gè)染色體，可以通過F=1/LA計(jì)算給定染色體的適應(yīng)度，其中LA由式(15)中的目標(biāo)函數(shù)給出。

(3)交叉和變異：改進(jìn)的遺傳算法使用傳統(tǒng)的輪盤賭方法，從當(dāng)前種群中將兩個(gè)分為一組進(jìn)行選擇，將其交配(交叉)以繁殖新后代種群的雙親。然后，對(duì)于每兩個(gè)被選擇的染色體，會(huì)選擇一個(gè)交叉點(diǎn)?， ?是介于2和請(qǐng)求總數(shù)n之間的整數(shù)值，因此，可以在不混淆請(qǐng)求分配的位置上直接選取交叉點(diǎn)?， 如圖4所示。最后，與請(qǐng)求?到n對(duì)應(yīng)的所有基因被交換，從而產(chǎn)生兩個(gè)新的染色體。這個(gè)過程將一直重復(fù)，直到新一代產(chǎn)生的子代染色體數(shù)目等于當(dāng)前一代的染色體數(shù)目。其中對(duì)于每個(gè)隨機(jī)選擇的基因Xmn進(jìn)行突變，即將數(shù)值翻轉(zhuǎn)到相反的值(如從1翻轉(zhuǎn)到0)。

圖4 染色體內(nèi)交叉點(diǎn)的選取

(4)可行性檢測和不可行性懲罰：提出的遺傳算法會(huì)檢測雜交和突變后的新后代染色體的可行性。準(zhǔn)確地說，明確哪些新染色體是可行的，即它們是否滿足約束條件。換言之，對(duì)于每個(gè)染色體，如果染色體滿足約束條件，將確定其每個(gè)請(qǐng)求設(shè)備都會(huì)被分配到一個(gè)計(jì)算資源。而50%不滿足約束條件的不可行染色體通過增加其適應(yīng)值而受到懲罰，從而降低它們下一代存活的概率。

(5)精英主義和終止準(zhǔn)則：提出的遺傳算法保存了到目前為止所有生成種群中的最優(yōu)染色體(可行且適應(yīng)值最小的染色體)。當(dāng)滿足終止條件時(shí)，算法會(huì)停止。根據(jù)實(shí)驗(yàn)結(jié)果，當(dāng)4次連續(xù)迭代后，最佳適應(yīng)度沒有改變，或者最大迭代次數(shù)達(dá)到30時(shí)，算法滿足終止條件。

4 仿真實(shí)驗(yàn)

4.1 仿真環(huán)境

利用iFogSim對(duì)所提算法進(jìn)行模擬仿真實(shí)驗(yàn)，通過在移動(dòng)邊緣計(jì)算環(huán)境對(duì)比各個(gè)算法在能耗、負(fù)載均衡、服務(wù)延遲、平均執(zhí)行時(shí)間和網(wǎng)絡(luò)使用情況等方面的性能表現(xiàn)。在模擬實(shí)驗(yàn)中，移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)主要由1個(gè)云數(shù)據(jù)中心、80個(gè)邊緣計(jì)算服務(wù)器和許多個(gè)請(qǐng)求設(shè)備組成。其中，所有的邊緣計(jì)算服務(wù)器都被平均分為10個(gè)不同的區(qū)域，且每個(gè)請(qǐng)求設(shè)備在單位時(shí)間內(nèi)只能發(fā)送一個(gè)卸載請(qǐng)求。

為了模擬移動(dòng)應(yīng)用被劃分為不同子任務(wù)后進(jìn)行卸載的過程，構(gòu)造了一個(gè)虛擬現(xiàn)實(shí)游戲，以體現(xiàn)子任務(wù)的相互依賴關(guān)系，如圖5所示。

圖5 虛擬現(xiàn)實(shí)游戲中子任務(wù)的依賴性

該應(yīng)用程序主要由5個(gè)子任務(wù)組成，分別為腦電圖、客戶端、集中計(jì)算器、協(xié)調(diào)器和顯示。腦電圖和顯示必須在本地設(shè)備上執(zhí)行，剩余的子任務(wù)可以根據(jù)策略進(jìn)行卸載和分配。對(duì)延遲敏感的應(yīng)用程序?qū)π遁d決策有著非常高的要求。一方面，將需要高計(jì)算量的模塊卸載到云服務(wù)器上執(zhí)行是十分必要的，這樣可以最大限度地降低移動(dòng)設(shè)備的能耗；另一方面，邊緣計(jì)算模塊需要盡可能靠近數(shù)據(jù)源，從而減少模塊間數(shù)據(jù)傳輸造成的延遲。

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

實(shí)驗(yàn)中從Google數(shù)據(jù)集中選取1000個(gè)應(yīng)用程序?qū)Ω倪M(jìn)的遺傳算法進(jìn)行訓(xùn)練，然后選取部分剩余數(shù)據(jù)對(duì)訓(xùn)練后的網(wǎng)絡(luò)模型進(jìn)行測試，從而論證所提算法的通用性和有效性。執(zhí)行時(shí)間作為評(píng)價(jià)算法性能的關(guān)鍵指標(biāo)，分析其與改進(jìn)遺傳算法的種群規(guī)模與最大迭代次數(shù)的關(guān)系，有助于所提算法中參數(shù)的合理設(shè)置。其中考慮了不同規(guī)模的計(jì)算卸載與資源分配問題N， 且N中的每個(gè)值是包含j請(qǐng)求和i資源的一個(gè)元組 (j/i)， 實(shí)驗(yàn)中將多個(gè)元組的值分別設(shè)為(30/10)，(60/20)，(100/40)和(140/70)。針對(duì)N中的每個(gè)值，進(jìn)行5次不同的實(shí)驗(yàn)。算法執(zhí)行時(shí)間與種群規(guī)模與最大迭代次數(shù)的關(guān)系如圖6、圖7所示。

圖6 執(zhí)行時(shí)間與種群規(guī)模的關(guān)系

圖7 執(zhí)行時(shí)間與最大迭代次數(shù)的關(guān)系

從圖6中可以看出，執(zhí)行時(shí)間隨著種群規(guī)模和問題規(guī)模N的增加而繼續(xù)急劇增加。由于種群規(guī)模增加，算法需要更長的時(shí)間完成算法的運(yùn)算，并且問題規(guī)模增加，意味著有更多的請(qǐng)求設(shè)備需要分配計(jì)算資源，算法更加復(fù)雜，因此執(zhí)行時(shí)間增長。綜合各方面因素考慮，將種群規(guī)模設(shè)為60最為合理，只需花費(fèi)中等運(yùn)行時(shí)間而能獲得高質(zhì)量的解決方案。

從圖7中可以看出，最大迭代次數(shù)的增加會(huì)急劇增加算法的運(yùn)行時(shí)間。通常來說，迭代次數(shù)越多，獲得的最優(yōu)解越理想，算法的性能更佳，但是付出的執(zhí)行時(shí)間成本過高，為此，綜合考慮，將最大迭代次數(shù)設(shè)置為25，此時(shí)，算法可以只花費(fèi)中等運(yùn)行時(shí)間而得到高質(zhì)量的解。

4.3 不同算法的對(duì)比分析

為了論證所提算法在能耗、負(fù)載平衡、延遲、網(wǎng)絡(luò)使用率等方面的性能，將其與文獻(xiàn)[14]、文獻(xiàn)[16]、文獻(xiàn)[18]、文獻(xiàn)[21]進(jìn)行對(duì)比分析，結(jié)果如圖8所示。其中文獻(xiàn)[14]采用了混合整數(shù)非線性規(guī)劃方法解決任務(wù)卸載問題；文獻(xiàn)[16]設(shè)計(jì)了一種面向邊緣計(jì)算的用戶請(qǐng)求數(shù)量預(yù)測模型，并基于此提出任務(wù)卸載方案；文獻(xiàn)[18]提出一種分布計(jì)算卸載模型；文獻(xiàn)[21]基于計(jì)算卸載和任務(wù)分配的聯(lián)合凸優(yōu)化目標(biāo)，采用拉格朗日乘子法進(jìn)行迭代更新得到最優(yōu)解。

圖8 任務(wù)卸載中每種算法產(chǎn)生的資源消耗

從圖8中可以看出，隨著請(qǐng)求設(shè)備數(shù)量的增加，各種算法生成的計(jì)算卸載和資源分配策略在能耗、負(fù)載平衡、延遲、網(wǎng)絡(luò)使用率等方面基本上都是遞增的。所提算法在延遲、網(wǎng)絡(luò)利用率和負(fù)載均衡方面都能取得較好的效果，但在能耗方面表現(xiàn)一般。主要是因?yàn)橐苿?dòng)邊緣計(jì)算更傾向于將子任務(wù)卸載到本地設(shè)備上執(zhí)行，當(dāng)本地設(shè)備處的資源不足時(shí)，子任務(wù)被逐層地卸載到上層設(shè)備當(dāng)中。由于一些子任務(wù)可以在本地執(zhí)行而無需網(wǎng)絡(luò)傳輸，所以所提算法的延遲較低。并且所提算法更傾向于將子任務(wù)卸載到邊緣計(jì)算服務(wù)器中，這使得所有邊緣計(jì)算服務(wù)器的資源利用效率都保持在平均水平，并實(shí)現(xiàn)了負(fù)載均衡值的最小化。與此同時(shí)，邊緣計(jì)算服務(wù)器的性能可以滿足更多子任務(wù)的處理請(qǐng)求，從而減少了子任務(wù)之間的網(wǎng)絡(luò)傳輸，進(jìn)一步降低了整個(gè)系統(tǒng)的網(wǎng)絡(luò)利用率。但由于移動(dòng)邊緣計(jì)算設(shè)備的處理能力和計(jì)算能力遠(yuǎn)遠(yuǎn)小于云服務(wù)器，因此，在本地設(shè)備上處理子任務(wù)將導(dǎo)致更高的能耗。

此外，從圖8中可以看出，隨著應(yīng)請(qǐng)求設(shè)備數(shù)量的增加，由文獻(xiàn)[18]算法生成的計(jì)算卸載和資源分配策略在負(fù)載平衡方面表現(xiàn)得很差，且在其它方面也表現(xiàn)得一般。文獻(xiàn)[21]算法在除了延遲之外的所有方面的表現(xiàn)都比文獻(xiàn)[18]算法要好一些。文獻(xiàn)[21]算法綜合考慮了兩種方法在各個(gè)方面的優(yōu)勢，在能耗、負(fù)載均衡等方面的性能較為理想。當(dāng)設(shè)備數(shù)量較多時(shí)，由文獻(xiàn)[14]算法生成的策略在延遲方面都有很好的效果，但在能耗方面的效果是最差的。同時(shí)，因?yàn)槲墨I(xiàn)[21]算法和文獻(xiàn)[18]算法更傾向于將子任務(wù)卸載到本地設(shè)備，而當(dāng)任務(wù)被卸載到具有更高計(jì)算能力的邊緣計(jì)算服務(wù)器時(shí)，文獻(xiàn)[21]算法的性能優(yōu)于文獻(xiàn)[18]算法。當(dāng)應(yīng)用數(shù)量較多時(shí)，文獻(xiàn)[16]算法和文獻(xiàn)[14]算法的時(shí)延呈下降趨勢，其性能優(yōu)于其它兩種對(duì)比算法。另外，文獻(xiàn)[21]算法和文獻(xiàn)[14]算法在網(wǎng)絡(luò)利用率方面具有相似的性能，其結(jié)果僅次于所提算法。

5 結(jié)束語

由于智能終端設(shè)備和物理環(huán)境之間會(huì)通過傳感和驅(qū)動(dòng)的方式進(jìn)行交互，有著嚴(yán)苛的延遲要求，而設(shè)備本身的計(jì)算能力有限，因此需要根據(jù)需求進(jìn)行計(jì)算卸載，將任務(wù)卸載至云和邊緣計(jì)算服務(wù)器中，以合理分配計(jì)算資源。所提出的移動(dòng)邊緣計(jì)算中基于改進(jìn)遺傳算法的計(jì)算卸載與資源分配算法在完成移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)架構(gòu)設(shè)計(jì)的基礎(chǔ)上，構(gòu)建包括能耗、平均服務(wù)延遲、執(zhí)行時(shí)間以及負(fù)載均衡的系統(tǒng)模型，并以能耗、延遲、負(fù)載均衡最小化為優(yōu)化目標(biāo)，利用改進(jìn)的遺傳算法進(jìn)行求解，以實(shí)現(xiàn)計(jì)算的高效卸載與資源的最優(yōu)分配。此外，利用iFogSim和Google集群對(duì)所提算法進(jìn)行仿真測試，結(jié)果表明，算法種群數(shù)量和最大迭代次數(shù)的合理值分別是60和25，且所提算法得到的計(jì)算卸載和資源分配策略在能耗、負(fù)載均衡、延遲和網(wǎng)絡(luò)使用率方面的表現(xiàn)均優(yōu)于其它算法。

接下來的研究工作是將所提算法應(yīng)用于更大規(guī)模的網(wǎng)絡(luò)，其中考慮關(guān)鍵請(qǐng)求調(diào)度和允許搶占、優(yōu)先處理等方面。并且還可將多個(gè)目標(biāo)函數(shù)擴(kuò)展至該算法，從而進(jìn)一步提高計(jì)算資源的利用率以及減少延遲和能耗等。