姚政，吳懷宇，陳洋

（1.冶金自動化與檢測技術(shù)教育部工程研究中心，武漢 430081；2.武漢科技大學(xué) 機器人與智能系統(tǒng)研究院，武漢 430081）

0 概述

隨著移動設(shè)備在全國各城市中迅速普及和增長，密集型計算任務(wù)隨之激增［1-2］，這給移動設(shè)備的計算能力和電池壽命提出了更高的要求。然而，由于微芯片架構(gòu)和低功耗設(shè)計，使得移動設(shè)備計算能力有限［3-4］，導(dǎo)致設(shè)備在處理高密集、低延遲任務(wù)時存在較大的延誤。同時，設(shè)備在處理這些任務(wù)時也產(chǎn)生了更多的能耗，這也進一步縮短了設(shè)備的續(xù)航時間。為解決該問題，研究人員提出移動邊緣計算［5］，通過在靠近移動設(shè)備的網(wǎng)絡(luò)邊緣部署計算資源，使移動設(shè)備能夠高效地卸載計算密集型任務(wù)。相比云計算，數(shù)據(jù)傳輸不再需要經(jīng)過核心網(wǎng)絡(luò)，移動設(shè)備即能夠獲得較低的傳輸延遲和較強的續(xù)航能力。

計算卸載是移動邊緣計算中最突出和廣泛討論的問題之一，其為移動邊緣計算的智能核心因素。目前，現(xiàn)有研究工作主要從應(yīng)用拓撲結(jié)構(gòu)、優(yōu)化目標多樣性和計算資源競爭等特性分別展開，然而很少聯(lián)合考慮應(yīng)用拓撲結(jié)構(gòu)、優(yōu)化目標多樣性及計算資源競爭的特性。首先，對于多用戶并發(fā)型數(shù)據(jù)流任務(wù)計算卸載問題，任務(wù)之間不僅會對邊緣服務(wù)器的計算資源產(chǎn)生競爭，而且也會對移動設(shè)備本地計算資源產(chǎn)生競爭，這種雙邊競爭進一步增加了計算資源競爭的復(fù)雜程度。其次，從數(shù)學(xué)建模角度來講，決策變量包括任務(wù)卸載比例（連續(xù)變量）和任務(wù)執(zhí)行順序（離散變量），因此該問題本質(zhì)上是一個多目標混合整數(shù)問題的求解。此外，在多目標優(yōu)化問題中，帕累托前沿包含多個非支配解構(gòu)成的帕累托解集，而在實際應(yīng)用中只需選取代表帕累托前沿特征的少量解。

本文在同時考慮應(yīng)用拓撲結(jié)構(gòu)、優(yōu)化目標多樣性及計算資源競爭的基礎(chǔ)上，設(shè)計一種多目標并發(fā)型數(shù)據(jù)流任務(wù)計算卸載混合整數(shù)模型，并給出基于多目標優(yōu)化和多屬性決策的兩階段優(yōu)化框架進行求解。在多目標優(yōu)化階段，提出一種改進DMP-NSGA-II 算法以解決局部收斂和全局搜索難以平衡的問題，并通過基于混合式求解框架的DMP-NSGA-II 算法求解該模型。在多屬性決策階段，給出一種FCM-GRP 集成方法，在帕累托前沿上采用模糊C-均值聚類（Fuzzy C-Means，F(xiàn)CM）算法獲得不同偏好下的聚類解集，并根據(jù)灰關(guān)聯(lián)投影（GRP）算法選出不同偏好下最優(yōu)折衷卸載決策。

1 相關(guān)工作

現(xiàn)有研究工作大多針對應(yīng)用拓撲結(jié)構(gòu)、優(yōu)化目標多樣性和計算資源競爭的某一特性展開。首先，任務(wù)卸載模型是計算卸載的首要考慮因素，一般分為全部卸載模型和部分卸載模型。全部卸載模型主要針對高度耦合的任務(wù)，只能作為整體在本地執(zhí)行或邊緣執(zhí)行。文獻［6］根據(jù)網(wǎng)絡(luò)信道特性、緩存排隊狀態(tài)、本地及邊緣計算能力來選擇整體卸載決策。文獻［7］采用動態(tài)電壓和頻率縮放技術(shù)在時延允許范圍內(nèi)最小化應(yīng)用執(zhí)行的能量消耗，并優(yōu)化數(shù)據(jù)傳輸以執(zhí)行整體卸載。部分卸載模型通常是指流式數(shù)據(jù)處理任務(wù)，如文件壓縮、視頻分析等，數(shù)據(jù)以任意比例切分在本地和邊緣同時執(zhí)行。文獻［8］采用一種李雅普諾夫優(yōu)化策略對連續(xù)到達的數(shù)據(jù)流進行動態(tài)卸載決策，以最小化移動終端能耗。文獻［9］則采用動態(tài)規(guī)劃方法實現(xiàn)數(shù)據(jù)流卸載決策，在滿足任務(wù)延遲約束的同時最小化移動終端能耗。此外，考慮到邊緣服務(wù)器的計算資源有限，需要合理優(yōu)化計算資源分配。文獻［10］采用無線資源和計算資源聯(lián)合優(yōu)化方法，以實現(xiàn)滿足時延約束下最小化能耗。文獻［11］研究了多車輛多邊緣服務(wù)器場景下計算卸載及資源分配問題，旨在最小化所有任務(wù)延遲。然而，現(xiàn)有研究很少同時考慮應(yīng)用拓撲結(jié)構(gòu)、優(yōu)化目標多樣性及計算資源競爭的特性。

其次，如何高效地處理混合整數(shù)決策變量是多目標混合整數(shù)問題求解的關(guān)鍵。目前，多目標混合整數(shù)問題的主流求解框架包括轉(zhuǎn)換求解框架、分層式求解框架、混合式求解框架［12］。轉(zhuǎn)換求解框架是借助離散化或連續(xù)化方法將其轉(zhuǎn)化為單一變量多目標優(yōu)化問題，然而這種框架存在一定限制性，因為有些問題的混合整數(shù)決策變量難以轉(zhuǎn)換成單一變量類型。分層式求解框架是將離散變量和連續(xù)變量分為上層和下層，獨立評價并相互反饋，然而這種框架具有較高的計算成本，不適合復(fù)雜優(yōu)化問題。混合式求解框架則在同一個層次中同時搜索離散變量與連續(xù)變量，相對分層式求解框架，其在保留求解的通用性的同時簡化了求解流程。因此，在考慮到本文模型中決策變量難以轉(zhuǎn)換的前提下，混合式求解框架是首選的求解框架。

此外，在多目標優(yōu)化問題中，主流選解方法包括先驗方法［13］、后驗方法［14］和交互方法［15］。先驗方法是優(yōu)化前將多個目標組合成單個目標，具有簡單、方便的特性，但其主觀程度較高。在交互式方法中，決策者參與優(yōu)化過程，其過程較為復(fù)雜。后驗方法的搜索和決策過程是分離的，當偏好發(fā)生變化時，無需重復(fù)執(zhí)行優(yōu)化算法，其已被證明是首選的研究方法。目前，相關(guān)研究工作主要是采用多目標優(yōu)化和多屬性決策相結(jié)合的方法從有限組合方案中確定最優(yōu)組合［16-17］。

2 問題建模

2.1 系統(tǒng)模型

本文研究的是多用戶單邊緣服務(wù)器的系統(tǒng)架構(gòu)，邊緣服務(wù)器內(nèi)嵌邊緣智能，負責移動設(shè)備端計算卸載決策。在某物理區(qū)域內(nèi)隨機分布多個移動設(shè)備，并在同一時刻產(chǎn)生并發(fā)型數(shù)據(jù)流任務(wù)，任務(wù)可以任意比例切分為本地和邊緣服務(wù)器同時執(zhí)行。被切分任務(wù)通過無線網(wǎng)絡(luò)傳輸至通信節(jié)點并轉(zhuǎn)發(fā)到邊緣服務(wù)器，邊緣服務(wù)器放置于無線通信節(jié)點旁側(cè)。圖1所示為多用戶并發(fā)型數(shù)據(jù)流任務(wù)計算卸載流程。

圖1 計算卸載流程Fig.1 Procedure of computing offloading

本文以并發(fā)型數(shù)據(jù)流任務(wù)為研究對象，每個移動設(shè)備Mi的并發(fā)型數(shù)據(jù)流任務(wù)可以表示為一個四元組：Si={ni，si，j，li，j，ki，j}，其中，ni表示移動設(shè)備Mi并發(fā)型數(shù)據(jù)流任務(wù)的個數(shù)，si，j表示移動設(shè)備Mi第j個任務(wù)，li，j表示任務(wù)si，j的軟截止時間，表示當前任務(wù)的相對緊急程度，ki，j表示任務(wù)si，j的數(shù)據(jù)容量。

2.2 任務(wù)時間模型

任務(wù)完成時間可以分成在移動設(shè)備本地執(zhí)行和邊緣服務(wù)器邊緣執(zhí)行兩個部分。

首先，任務(wù)si，j在移動設(shè)備本地執(zhí)行的開始時間和結(jié)束時間分別表示為和，其計算公式如下：

本文假設(shè)移動設(shè)備采用正交頻分多址技術(shù)網(wǎng)絡(luò)通信模式，因此：

其中：B表示固定最大信道帶寬；σ2表示固定信道噪聲功率；hi表示移動設(shè)備Mi的信道狀態(tài)信息；ρ表示信道功率增益；η表示路徑損耗指數(shù)。

由于返回數(shù)據(jù)量較小，本文不考慮數(shù)據(jù)回傳時間，因此任務(wù)taski，j的完成時間Ti，j表示為：

2.3 設(shè)備能耗模型

移動設(shè)備能耗分為移動設(shè)備計算能耗和傳輸能耗兩個部分。

首先，移動設(shè)備計算模塊包括運行和空閑兩種狀態(tài)。當計算任務(wù)時處于運行狀態(tài)，當停止計算任務(wù)時處于空閑狀態(tài)，其計算公式如下：

其中：表示運行狀態(tài)下的計算能耗；表示空閑狀態(tài)下的計算能耗；表示移動設(shè)備Mi的總計算能耗。

然后，移動設(shè)備傳輸部分包括發(fā)送和空閑兩種狀態(tài)。由于返回數(shù)據(jù)量較小，本文不考慮數(shù)據(jù)返回能耗，其傳輸能耗計算如下：

因此，移動設(shè)備Mi的總能耗Ei可以表示為：

2.4 優(yōu)化目標

為了更好地平衡任務(wù)時間延誤和設(shè)備能耗，本文設(shè)計了以下的優(yōu)化目標：

其中：f1是所有移動設(shè)備總延誤之和；f2是所有移動設(shè)備總能耗之和。其他約束包括：邊緣卸載比例變量0 ≤xi，j≤1 約束任務(wù)卸載比例變量以任意的百分比進行切分，本地排序變量yi，j≤ni約束移動設(shè)備本地排序變量不超過該設(shè)備的任務(wù)總數(shù)量，邊緣排序變量zi，j≤約束移動設(shè)備邊緣排序變量不超過所有設(shè)備的任務(wù)總數(shù)量。

3 兩階段優(yōu)化框架

為了求解本文提出的模型，本文設(shè)計一種基于多目標優(yōu)化和多屬性決策的兩階段優(yōu)化框架。在多目標優(yōu)化階段，提出一種改進DMP-NSGA-II 算法，并設(shè)計一種基于混合式求解框架的DMP-NSGA-II 算法求解多目標混合整數(shù)規(guī)劃模型；在多屬性決策階段，設(shè)計一種FCM-GRP 集成方法來選出不同偏好下最優(yōu)折衷卸載決策。兩階段優(yōu)化求解框架如圖2所示。

圖2 兩階段優(yōu)化求解框架Fig.2 Framework of two stage optimization solution

3.1 多目標優(yōu)化階段

3.1.1 DMP-NSGA-II 算法

NSGA-II 以其計算速度快、復(fù)雜度低等優(yōu)點在多目標優(yōu)化工程領(lǐng)域中得到非常廣泛的應(yīng)用［18-20］，但是該算法仍然存在局部收斂和全局搜索難以平衡的問題［21］。鑒于此，本文在NSGA-II 算法的基礎(chǔ)上提出一種改進動態(tài)多種群并行NSGA-II 算法（DMPNSGA-II），包括多種群多交叉策略、動態(tài)調(diào)整種群規(guī)模、二次局部搜索的改進策略。首先，設(shè)計了基于非支配等級排序的種群劃分方式，將單一種群劃分為精英種群和一般種群，并分配不同性能的交叉算子，以平衡算法局部收斂和全局搜索能力；其次，設(shè)計了非線性種群規(guī)模動態(tài)調(diào)整策略，以提高種群的適應(yīng)性；最后，采用萊維飛行的二次局部搜索策略，以增強局部搜索精度。

3.1.2 多種群多交叉策略

多種群策略可以很好地提高種群多樣性，但也容易導(dǎo)致局部收斂能力不足。為了彌補這一缺陷，本文在NSGA-II 算法基礎(chǔ)上設(shè)計了一種新的多種群多交叉策略，通過在不同種群進化過程中采用不同性能的交叉算子，從而更好地平衡算法局部收斂和全局搜索能力。多種群多交叉策略過程如下：

首先，采用非支配排序方法將種群個體進行分級，并按照不同等級把個體分成兩個子種群，分別為精英種群和非精英種群。其中，精英種群由非支配排序等級第一的個體組成，非精英種群由其他非支配排序等級的個體組成。

然后，精英種群采用模擬二進制交叉算子用于加快收斂速度，以增強局部收斂能力；非精英種群采用算術(shù)交叉算子，用于克服陷入局部最優(yōu)，以增強全局搜索能力。具體來講，隨機選擇兩個父代為x1=(x11，x12，…，x1n)和x2=(x21，x22，…，x2n)，并隨機選擇交叉點。當采用模擬二進制交叉算子時，兩個子代y1和y2交叉方式如下：

其中：β(α)=，α為［0，1］區(qū)間均勻分布的隨機數(shù)。

當采用算術(shù)交叉算子時，兩個子代y1和y2交叉方式如下：

其中：α同樣為［0，1］區(qū)間均勻分布的隨機數(shù)。

3.1.3 動態(tài)調(diào)節(jié)種群規(guī)模

固定子種群規(guī)模劃分方式一定程度上會影響搜索性能，在進化初期應(yīng)采用較大規(guī)模的非精英種群以大范圍搜索，進行全局進化避免過早收斂；在進化后期應(yīng)采用較大規(guī)模的精英種群以小范圍搜索，進行局部進化提高解的精度。鑒于此，本文提出一種基于非線性種群規(guī)模動態(tài)調(diào)整策略，種群規(guī)模變化曲線以生物群體增長Logistic 曲線為基礎(chǔ)，其數(shù)學(xué)表達式如下：

其中：ω(t)表示在t次迭代中精英種群占整個種群的比例；F1(t)表示在t次迭代中非支配排序等級第一的種群數(shù)量；N表示種群總數(shù)；λ為調(diào)節(jié)系數(shù)，可隨環(huán)境不同適當調(diào)整，本文取值為0.2。此外，為了防止搜索停滯，采用最大最小限制方法將精英種群占種群總數(shù)的比例限制在[ωmin，ωmax]的范圍，其中：

其中：ωmin和ωmax分別為精英種群占種群總數(shù)比例的最小值和最大值，可隨環(huán)境不同適當調(diào)整，本文分別取值為0.2 和0.8。

3.1.4 二次局部搜索策略

為了防止精英種群中的個體陷入局部最優(yōu)，增強精英種群個體的局部搜索性能，本文引入了基于萊維飛行的二次局部搜索策略，通過在種群進化過程中周期性地執(zhí)行局部搜索操作，進一步改善對已知搜索區(qū)域的搜索深度。萊維飛行是一種長短步相間的飛行方式，這種隨機的飛行方式使得搜索范圍加大，找到最優(yōu)解的概率也相應(yīng)增加。對當前精英種群采用萊維飛行的個體更新公式為：

其中：α是步長縮放因子，本文取值為1；⊕表示點對點乘法；Levy(λ)表示服從萊維分布的路徑。

3.1.5 DMP-NSGA-II 求解模型流程

對于本文多目標混合整數(shù)問題，如何高效地處理混合整數(shù)決策變量是問題求解的關(guān)鍵。鑒于混合式求解框架的優(yōu)勢，本文設(shè)計了一種基于混合式求解框架的DMP-NSGA-II 方法求解本文模型，離散變量和連續(xù)變量并行執(zhí)行交叉、變異的進化操作。基于混合式求解框架的DMP-NSGA-II 算法求解模型具體步驟如下：

1）變量編碼與解碼。以邊緣卸載比例變量xi，j、本地排序變量yi，j和邊緣排序變量zi，j作為決策變量采用混合編碼，xi，j采用連續(xù)編碼方式，yi，j和zi，j采用離散編碼方式，通過編碼拼接可得完整染色體編碼(xi，j，yi，j，zi，j)。

2）生成初始種群。邊緣卸載比例變量xi，j?。?，1］之間的任意數(shù)值，本地排序變量yi，j取1～ni之間的任意一種排序值，邊緣排序變量zi，j取1～之間的任意一種排序值，設(shè)定初始種群個體的規(guī)模，同時隨機產(chǎn)生初始種群，其中每個個體對應(yīng)一種卸載決策。

3）個體適應(yīng)度計算。計算每個個體的所有目標函數(shù)值，同時采用快速非支配排序方法計算個體的非支配排序等級和基于個體目標域局部擁擠距離計算個體的擁擠度，個體適應(yīng)度評價取決于個體的非支配排序等級和擁擠度。

4）多種群劃分和動態(tài)調(diào)整。按照不同等級把個體分成兩個子種群，分別為精英種群和非精英種群。其中，精英種群由非支配排序等級第一的個體組成，非精英種群由其他非支配排序等級的個體組成。同時，種群規(guī)模變化曲線以生物群體增長Logistic 曲線為基礎(chǔ)，對種群規(guī)模進行動態(tài)調(diào)整。

5）二元錦標賽選擇。從種群中等概率隨機選擇兩個個體，篩選出其中適應(yīng)度較好的個體，循環(huán)執(zhí)行直到種群規(guī)模達到初始種群規(guī)模。

6）種群進化。在種群迭代進化過程中，不同種群分配不同進化能力的交叉算子，而連續(xù)編碼和離散編碼也分別采用匹配度更好的交叉算子。具體來講，精英種群的連續(xù)編碼采用模擬二進制交叉算子，離散編碼順序排序交叉算子；非精英種群的連續(xù)編碼采用算術(shù)交叉算子，離散變量采用順序排序交叉算子。其中，順序排序交叉算子已被證明在求解離散的排序問題性能較為突出。同時，對于精英種群的連續(xù)編碼采用基于萊維飛行的二次局部搜索策略，進一步改善對已知搜索區(qū)域的搜索深度。

7）精英保留。將父代和子代個體重新組成新種群，并基于個體適應(yīng)度從新種群個體篩選出優(yōu)良個體進入下一代種群。

8）帕累托解集。經(jīng)過步驟3）～步驟7 循環(huán)直到滿足迭代結(jié)束，再采用快速非支配排序和擁擠度得到帕累托解集，即計算卸載決策最優(yōu)集合?；诨旌鲜角蠼饪蚣艿腄MP-NSGA-II 算法求解模型流程如圖3所示。

圖3 模型求解流程Fig.3 Procedure of model solution

3.2 多屬性決策階段

為進一步給出不同偏好下最優(yōu)折衷卸載決策，在多屬性決策階段設(shè)計了一種FCM-GRP 集成方法。首先，采用FCM 算法對獲得的帕累托解集進行聚類處理，以獲得不同偏好下的帕累托子集；然后，對不同偏好下的帕累托子集采用GRP 算法，以選出最優(yōu)折衷卸載決策。

3.2.1 FCM 算法

FCM 算法是一種基于函數(shù)最優(yōu)方法的聚類算法［22］，通過優(yōu)化目標函數(shù)獲得每個樣本點對于類中心的隸屬度，從而決定樣本點的類屬以實現(xiàn)樣本點分類。FCM 算法的目標函數(shù)和約束條件如下：

其中：J是聚類損失函數(shù)；S是帕累托最優(yōu)解集；Np是解集的個數(shù)；C={c1，c2，…，cNclu}是聚類中心的集合；Nclu是聚類中心的個數(shù)；ηi，j是第i個樣本對于第j類的隸屬度，取值范圍為［0，1］。本文采取三類不同決策偏好，因此聚類中心的個數(shù)取值為3。

3.2.2 GRP 算法

灰關(guān)聯(lián)投影法（GRP）是基于灰色系統(tǒng)理論和矢量投影原理的集成方法，兼具了兩者優(yōu)點的同時在多屬性決策領(lǐng)域有很好的應(yīng)用［23-24］。為此，本文選取基于GRP 的多屬性決策方法對多目標優(yōu)化得到的卸載決策集合進行評估，根據(jù)優(yōu)屬度大小找到最優(yōu)折衷卸載決策。最優(yōu)折衷卸載決策選取過程如下所示：

首先，第m個卸載決策的第k個評價指標可以表示成二元組Sm，k={decisionm，indexk}，其中：decisionm表示第m個卸載決策，m∈[1，M]，M為卸載決策總數(shù)；indexk表示第k個評價指標，k∈[1，N]，N為評價指標總數(shù)。因此，Sm，k的灰關(guān)聯(lián)度系數(shù)為：

其中：Vm，k為標準化處理后的Sm，k；為標準化處理后的理想（負理想）卸載決策下的第k個評價指標；γ為分辨系數(shù)，通常γ取0.5。

然后，decisionm在理想（負理想）卸載決策上的投影值為：

其中：φk為第k項評價指標權(quán)重，表示該指標的相對重要程度，本文取0.5。

理想（負理想）卸載決策的模值L0為：

最后，decisionm的優(yōu)屬度δm為：

其中：0 ≤δm≤1，其值越大表示與理想卸載決策越接近，與負理想卸載決策越遠，反之亦然。因此，優(yōu)屬度最大的卸載決策即最優(yōu)折衷卸載決策。

4 實驗仿真與結(jié)果分析

實驗編程軟件為MATLABR2020b，運行環(huán)境Intel?CoreTMi7-2700QCPU_2.6 GHz_16 GB_Windows10，并分別設(shè)計了測試函數(shù)和模型實例兩個對比實驗。

4.1 數(shù)值實驗

4.1.1 參數(shù)設(shè)置

本文選取了測試函數(shù)ZDT 系列中的ZDT1、ZDT2、ZDT3、ZDT4 和ZDT6 作為基準測試函數(shù)［25］，并選用了兩個性能評估指標HV 以及SP 進行評價。HV 用于衡量非支配解集與參照點圍成的目標空間中區(qū)域的體積，HV 定義如下：

其中：di表示第i個解到PF 中其他解的最小距離；表示所有di的均值；|P|代表所有解的個數(shù)。SP的值越小越說明算法所求解的分布越均勻。

4.1.2 算法對比分析

為了驗證提出DMP-NSGA-II算法的性能，選取NSGA-II算法、MOEA/D算法［26］及MOEA/D-DE算法［27］3種應(yīng)用較為廣泛的多目標算法進行對比。涉及到這4 種算法共同參數(shù)設(shè)置包括：種群個數(shù)為100，最大迭代次數(shù)為200，交叉概率為0.9，變異概率為0.1，其他參數(shù)設(shè)置與上述算法保持一致。此外，為每個算法設(shè)置相同的初始種群，獨立運行10 次，以實現(xiàn)對比公平性。HV 指標和SP 指標的均值（方差）結(jié)果如表1 和表2 所示，其中加粗標注為最優(yōu)表現(xiàn)。

表1 HV 指標的均值（方差）Table 1 Mean（variance）of HV index

表2 SP 指標的均值（方差）Table 2 Mean（variance）of SP index

從表1和表2中可以看出，在ZDT1、ZDT2、ZDT3、ZDT6 中，DMP-NSGA-II 的HV 指標均值和方差、SP 指標均值都優(yōu)于其他3 個算法，具有非常明顯的優(yōu)勢。而在ZDT4 問題中，雖然DMP-NSGA-II 的HV 指標均值表現(xiàn)弱于MOEA/D，但SP 指標均值仍然能夠獲得最好的表現(xiàn)。此外，DMP-NSGA-II 的SP指標方差雖然沒有表現(xiàn)出很明顯的優(yōu)勢，但是相較NSGA-II 仍然有較大提升。綜上，DMP-NSGA-II 的改進預(yù)期目標已經(jīng)基本達到，即通過多種群多交叉、動態(tài)調(diào)整種群規(guī)模、二次局部搜索的改進策略，增強NSGA-II 算法局部收斂和全局搜索能力。

4.2 模型算例

4.2.1 數(shù)據(jù)準備

本文實驗仿真了一個真實的計算卸載應(yīng)用場景，并從文獻［28-30］中選擇相應(yīng)參數(shù)的值范圍。首先，采用路由節(jié)點提供的傳輸網(wǎng)絡(luò)，其固定最大信道帶寬為5×106Hz，固定信道噪聲功率為10-13，信道功率增益為2，路徑損耗指數(shù)為10-4，網(wǎng)絡(luò)半徑為200 m。單個邊緣服務(wù)器位于無線路由旁側(cè)，其計算能力為5×106MIPS，每個移動設(shè)備通過無線網(wǎng)絡(luò)連接到路由節(jié)點并轉(zhuǎn)發(fā)到邊緣服務(wù)器。其次，3 個移動設(shè)備隨機部署在網(wǎng)絡(luò)中，其計算能力范圍為0.1×106MIPS～0.2×106MIPS，計算模塊在工作和空閑狀態(tài)下的功率范圍分別是100～300 mW 和5～10 mW，通信模塊在傳輸和空閑狀態(tài)下的功率范圍分別是50～150 mW和8～15 mW。最后，假設(shè)每個移動設(shè)備任務(wù)并發(fā)數(shù)均為3，每個并發(fā)型任務(wù)軟截止時間范圍為0.1～2.0 s，每個并發(fā)型任務(wù)數(shù)據(jù)量范圍為10～200 KB。

4.2.2 算法性能比較

為了求解多目標并發(fā)型任務(wù)計算卸載混合整數(shù)規(guī)劃模型，分別采用基于混合式求解框架的NSGAII 算法和DMP-NSGA-II 算法進行對比求解。同時為了全面衡量算法在模型求解上的有效性，在HV 和SP 優(yōu)化指標的基礎(chǔ)上增加了平均延誤Meantime 和平均能耗Meanenergy 兩個模型評價指標。兩個算法的種群規(guī)模為100，最大迭代次數(shù)為200，交叉概率為0.9，變異概率為0.1。表3 所示為兩種算法求解模型10 次得到的HV、SP、Meantime 和Meanenergy指標的均值（方差）結(jié)果，其中加粗標注為最優(yōu)表現(xiàn)。從表3 可以直觀地看出，DMP-NSGA-II 算法在HV、SP、Meantime 和Meanenergy 平均值、方差上的表現(xiàn)全面要優(yōu)于NSGA-II 算法，這表明基于混合式求解框架的DMP-NSGA-II 算法在求解模型時具有更優(yōu)的求解精度和穩(wěn)定性。

表3 模型求解的均值（方差）結(jié)果Table 3 The mean（variance）results of the model solution

4.2.3 模型參數(shù)分析

為研究任務(wù)的數(shù)據(jù)量對于時間延誤和能耗的影響，圖4仿真了不同任務(wù)數(shù)據(jù)量下時間延誤和能耗的變化情況，包括數(shù)據(jù)量為0.1～0.5MB、0.5～1.0MB、1～2MB和2～4MB這4種情況。從圖4可以直觀地看出，隨著任務(wù)數(shù)據(jù)量的不斷增加，對應(yīng)的時間延誤和能耗呈明顯增加趨勢，其原因可能是較大的任務(wù)數(shù)據(jù)量會增加本地執(zhí)行時間、數(shù)據(jù)傳輸時間和邊緣執(zhí)行時間，從而導(dǎo)致任務(wù)整體執(zhí)行時間的延長，而較大的任務(wù)數(shù)據(jù)量也會帶來計算模塊和通信模塊更多的能耗。此外，不同數(shù)據(jù)量規(guī)模下其帕累托曲線仍然可以保持很好的收斂性和多樣性，這表明提出的DMP-NSGA-II 算法可以很好地適應(yīng)不同任務(wù)數(shù)據(jù)量的計算卸載問題。

圖4 不同任務(wù)數(shù)據(jù)量下參數(shù)變化情況Fig.4 Parameter changes under different task data volumes

為研究任務(wù)并發(fā)數(shù)對于任務(wù)競爭程度的影響，圖5 仿真了不同任務(wù)并發(fā)數(shù)下時間延誤和能耗的變化情況，包括任務(wù)并發(fā)數(shù)3、4、5 和6 這4 種情況。從圖5 可以直觀地看到，隨著任務(wù)并發(fā)數(shù)的不斷增大，對應(yīng)的時間延誤和能耗呈上升趨勢，尤其是時間延誤顯著增加，其原因可能是較大的并發(fā)數(shù)會增加任務(wù)在本地和邊緣排隊時間，排隊靠后的任務(wù)時間延誤會顯著增加，進一步增加了整體時間延誤，這也表明并發(fā)數(shù)增加會惡化任務(wù)之間競爭程度，而能耗的增加是因為任務(wù)個數(shù)增加也會帶來計算模塊和通信模塊更多的能耗。在不同任務(wù)并發(fā)數(shù)下，其帕累托曲線仍然可以保持很好的收斂性和多樣性，這表明提出的DMP-NSGA-II 算法可以很好地適應(yīng)不同任務(wù)并發(fā)數(shù)下的計算卸載問題。

圖5 不同任務(wù)并發(fā)數(shù)下參數(shù)變化情況Fig.5 Parameter changes under different task concurrencys

為研究邊緣計算卸載對于并發(fā)型計算任務(wù)的重要性，圖6 仿真了不同邊緣服務(wù)器計算能力下時間延誤和能耗的變化情況，分別包括邊緣計算能力為0.5、1、5、10 和50 MIPS 這5 種情況。從圖6 可以直觀地看出，隨著邊緣服務(wù)器計算能力的不斷增大，對應(yīng)能耗和時間延誤呈下降趨勢，其原因可能是當邊緣計算能力遠遠大于本地計算能力時，會將更多的數(shù)據(jù)量卸載到邊緣側(cè)執(zhí)行，以減少本地執(zhí)行數(shù)據(jù)量，從而縮短了任務(wù)執(zhí)行時間。同時，由于傳輸功率遠遠小于計算功率，隨著卸載的數(shù)據(jù)量增加，計算能耗的減少遠遠大于傳輸能耗的增加，從而減少了設(shè)備整體能耗。當邊緣計算能力為50 MIPS 時只存在一個解，即全部并發(fā)型任務(wù)卸載到邊緣端執(zhí)行的完全卸載方案，其計算時間和能耗都趨近于零，該解相當于一個極限點。同樣，不同任務(wù)并發(fā)數(shù)下其帕累托曲線仍然可以保持很好的收斂性和多樣性，這表明提出的DMP-NSGA-II 算法可以很好地適應(yīng)不同邊緣計算能力下的計算卸載問題。

圖6 不同邊緣計算能力下參數(shù)變化情況Fig.6 Parameter changes under different edge computing power

4.2.4 不同偏好下最優(yōu)折衷解分析

通過上述分析可以看出，時間延誤和能耗兩個優(yōu)化目標之間是矛盾的，時間延誤改善有可能會引起能耗降低，難以使時間延誤和設(shè)備能耗同時達到最優(yōu)值，只能選取具有代表性的少量計算卸載方案。為此，本文分別選取3 種代表性的偏好，包括偏好時間延誤、偏好設(shè)備能耗和無偏好，并采用FCM-GRP集成方法選取出具有代表性的折衷解。

首先，采用FCM 算法對卸載方案集合進行聚類處理，得到的3 種偏好下聚類結(jié)果如圖7（a）所示。從圖中可以直觀地看到，卸載方案集合被分為3 類，三角形DM-1 表示偏好能耗，圓圈DM-2 表示無偏好，五角星DM-3 表示偏好時間延誤。

然后，采用GRP 方法計算相應(yīng)的優(yōu)屬度，得到的3 種偏好下選解結(jié)果如圖7（b）所示。其中，實心的點表示不同偏好下最優(yōu)折衷卸載方案。

圖7 不同偏好下的選解過程Fig.7 Solution selection process under different preferences

5 結(jié)束語

本文針對移動邊緣計算場景下的并發(fā)型數(shù)據(jù)流任務(wù)計算卸載及資源競爭問題，設(shè)計一種基于并發(fā)型數(shù)據(jù)流任務(wù)的多目標計算卸載混合整數(shù)模型，為對模型進行求解，給出一種基于多目標優(yōu)化和多屬性決策的兩階段優(yōu)化框架，并分別在多目標優(yōu)化階段和多屬性決策階段提出改進動態(tài)多種群并行NSGA-II（DMPNSGA-II）算法與基于模糊C 均值聚類和灰關(guān)聯(lián)投影法的后驗選解方法。實驗結(jié)果表明，在ZDT 系列測試函數(shù)上，DMP-NSGA-II 算法的HV 和SP 指標表現(xiàn)明顯優(yōu)于NSGA-II、MOEA/D 和MOEA/D-DE 對比算法，在模型實例上，DMP-NSGA-II 算法的Meantime 和Meanenergy指標相較于NSGA-II算法分別提升了30.1%和8.9%。由于本文研究重點為并發(fā)型數(shù)據(jù)流任務(wù)的計算卸載，下一步將對柔性依賴性任務(wù)的計算卸載問題進行研究。同時，高維多目標計算卸載問題也是后續(xù)將要關(guān)注的研究方向。