基于兩階段優(yōu)化的并發(fā)流任務(wù)計(jì)算卸載策略

姚政，吳懷宇，陳洋

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

0 概述

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

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

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

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

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

2 問題建模

2.1 系統(tǒng)模型

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

圖1 計(jì)算卸載流程Fig.1 Procedure of computing offloading

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

2.2 任務(wù)時(shí)間模型

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

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

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

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

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

2.3 設(shè)備能耗模型

移動(dòng)設(shè)備能耗分為移動(dòng)設(shè)備計(jì)算能耗和傳輸能耗兩個(gè)部分。

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

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

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

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

2.4 優(yōu)化目標(biāo)

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

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

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

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

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

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

3.1.1 DMP-NSGA-II 算法

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

3.1.2 多種群多交叉策略

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

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

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

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

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

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

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

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

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

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

3.1.4 二次局部搜索策略

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

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

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

對(duì)于本文多目標(biāo)混合整數(shù)問題，如何高效地處理混合整數(shù)決策變量是問題求解的關(guān)鍵。鑒于混合式求解框架的優(yōu)勢(shì)，本文設(shè)計(jì)了一種基于混合式求解框架的DMP-NSGA-II 方法求解本文模型，離散變量和連續(xù)變量并行執(zhí)行交叉、變異的進(jìn)化操作?；诨旌鲜角蠼饪蚣艿腄MP-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è)定初始種群個(gè)體的規(guī)模，同時(shí)隨機(jī)產(chǎn)生初始種群，其中每個(gè)個(gè)體對(duì)應(yīng)一種卸載決策。

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

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

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

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

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

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

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

3.2 多屬性決策階段

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

3.2.1 FCM 算法

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

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

3.2.2 GRP 算法

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

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

其中：Vm，k為標(biāo)準(zhǔn)化處理后的Sm，k；為標(biāo)準(zhǔn)化處理后的理想（負(fù)理想）卸載決策下的第k個(gè)評(píng)價(jià)指標(biāo)；γ為分辨系數(shù)，通常γ取0.5。

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

其中：φk為第k項(xiàng)評(píng)價(jià)指標(biāo)權(quán)重，表示該指標(biāo)的相對(duì)重要程度，本文取0.5。

理想（負(fù)理想）卸載決策的模值L0為：

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

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

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

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

4.1 數(shù)值實(shí)驗(yàn)

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

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

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

4.1.2 算法對(duì)比分析

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

表1 HV 指標(biāo)的均值（方差）Table 1 Mean（variance）of HV index

表2 SP 指標(biāo)的均值（方差）Table 2 Mean（variance）of SP index

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

4.2 模型算例

4.2.1 數(shù)據(jù)準(zhǔn)備

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

4.2.2 算法性能比較

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

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

4.2.3 模型參數(shù)分析

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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