劉雨忻，馬占飛，林繼祥，鞏傳勝，李克見

（1.內(nèi)蒙古科技大學(xué)信息工程學(xué)院，包頭 014010；2.內(nèi)蒙古科技大學(xué)包頭師范學(xué)院計(jì)算機(jī)系，包頭 014030）

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的創(chuàng)新和發(fā)展，物聯(lián)網(wǎng)的應(yīng)用場景越來越多樣化，如智慧交通、智慧農(nóng)場、智慧醫(yī)療等。這些物聯(lián)網(wǎng)的應(yīng)用領(lǐng)域會產(chǎn)生大量的計(jì)算密集型和時(shí)延敏感型任務(wù)，如果將這些任務(wù)上傳到云端執(zhí)行不僅會增加傳輸鏈路和云端的負(fù)擔(dān)，還會造成一定的時(shí)延。為了解決上述問題，2014年，歐洲電信標(biāo)準(zhǔn)化協(xié)會ETSI提出了一個(gè)新的概念，即移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC），并指出移動(dòng)邊緣計(jì)算區(qū)別于云計(jì)算，是一種在移動(dòng)網(wǎng)絡(luò)邊緣的位置提供IT服務(wù)環(huán)境和計(jì)算能力的新型架構(gòu)。后來隨著研究的不斷深入，邊緣計(jì)算也用于Wi-Fi、固網(wǎng)接入等多種接入網(wǎng)絡(luò)架構(gòu)，因此其概念也被擴(kuò)展成為多接入邊緣計(jì)算（Multiaccess Edge Computing，MEC）。邊緣計(jì)算遷移卸載最早由文獻(xiàn)［3］提出，是指將資源受限的移動(dòng)設(shè)備或終端上的任務(wù)交由計(jì)算和存儲能力強(qiáng)的其它設(shè)備處或者邊緣服務(wù)器處執(zhí)行，從而減小終端的壓力，提高終端的使用壽命，增強(qiáng)用戶體驗(yàn)。

1 相關(guān)工作

文獻(xiàn)［4］提到邊緣計(jì)算已經(jīng)成為解決物聯(lián)網(wǎng)（Internet of Things，IoT）和本地計(jì)算的一種新范式，將各種計(jì)算任務(wù)或存儲任務(wù)遷移到終端用戶附近的網(wǎng)絡(luò)“邊緣”位置，在貼近網(wǎng)絡(luò)邊緣處完成數(shù)據(jù)的處理和存儲等操作，從而減少數(shù)據(jù)傳輸?shù)皆贫藞?zhí)行的成本和時(shí)間。因?yàn)檫吘壴O(shè)備的計(jì)算能力和存儲資源相對于大型服務(wù)器是有限的，所以無法支持復(fù)雜任務(wù)的執(zhí)行，因此需要將這些任務(wù)遷移到其他資源比較豐富的終端去執(zhí)行。文獻(xiàn)［5］將計(jì)算遷移分為4個(gè)階段，分別為分布式計(jì)算階段、普適計(jì)算階段、云計(jì)算階段和邊緣計(jì)算階段，并說明計(jì)算遷移的目標(biāo)是根據(jù)某一種決策方式，把當(dāng)前節(jié)點(diǎn)存在的某些任務(wù)遷移到其他節(jié)點(diǎn)的一種優(yōu)化方案。文獻(xiàn)［6］認(rèn)為計(jì)算遷移屬于邊緣計(jì)算原生性技術(shù)之一，并將計(jì)算遷移技術(shù)分為計(jì)算遷移決策機(jī)制設(shè)計(jì)和計(jì)算遷移資源優(yōu)化調(diào)度機(jī)制，其中計(jì)算遷移決策要解決的關(guān)鍵問題為是否要進(jìn)行遷移、要進(jìn)行哪些任務(wù)遷移以及要將任務(wù)遷移到哪里的問題。文獻(xiàn)［7］提出一種新型的動(dòng)態(tài)分布式異構(gòu)任務(wù)卸載算法，利用分布式博弈機(jī)制并結(jié)合李雅普諾夫優(yōu)化理論，設(shè)計(jì)了一種動(dòng)態(tài)報(bào)價(jià)機(jī)制，這種機(jī)制可以實(shí)現(xiàn)對不同資源的按需分配。文獻(xiàn)［8］通過考慮影響任務(wù)執(zhí)行時(shí)間的因素，應(yīng)用遺傳算法以簡單有效的方式分配邊緣設(shè)備上的任務(wù)，使得任務(wù)執(zhí)行的時(shí)間最小。文獻(xiàn)［9］提到邊緣設(shè)備的物理資源是有限的，其物理資源一般要遠(yuǎn)小于云計(jì)算中心的資源，因此如果有大量的、較復(fù)雜的并發(fā)任務(wù)被分配到某一邊緣設(shè)備上時(shí)，會有一部分任務(wù)不能及時(shí)執(zhí)行，此時(shí)這些任務(wù)只能在邊緣設(shè)備處排隊(duì)等候執(zhí)行。文獻(xiàn)［10］首先利用非支配排序遺傳算法將任務(wù)遷移的時(shí)間和負(fù)載情況進(jìn)行聯(lián)合優(yōu)化，找到比較有效的遷移策略，再利用多目標(biāo)決策準(zhǔn)則和逼近理想解排序法選擇最優(yōu)遷移策略。文獻(xiàn)［11］建立了節(jié)點(diǎn)服務(wù)質(zhì)量可信模型，并且從3個(gè)維度對任務(wù)遷移節(jié)點(diǎn)進(jìn)行了綜合評價(jià)，篩選出一些可以遷移的節(jié)點(diǎn)，最后利用灰色關(guān)聯(lián)分析法選擇出最終可以遷移的節(jié)點(diǎn)。文獻(xiàn)［12］提出了一種節(jié)能的計(jì)算遷移方法，該方法既優(yōu)化了任務(wù)卸載問題，同時(shí)也解決了無線資源分配問題，以便在時(shí)延約束下使得能量消耗最小。文獻(xiàn)［13］綜合考慮了計(jì)算資源、帶寬，構(gòu)建了一個(gè)最小化時(shí)延和能耗的問題，并利用異步云邊協(xié)同的深度強(qiáng)化學(xué)習(xí)方法進(jìn)行求解。

在移動(dòng)邊緣計(jì)算中，任務(wù)卸載遷移的方式有兩種，一是將任務(wù)遷移到MEC服務(wù)器上；二是將任務(wù)遷移到周圍閑置的邊緣設(shè)備中，本文考慮將任務(wù)卸載遷移到MEC服務(wù)器中。文中首先根據(jù)各個(gè)邊緣設(shè)備的負(fù)載情況篩選出需要遷移的任務(wù)，然后構(gòu)建時(shí)延模型、任務(wù)匹配度模型和負(fù)載模型，對蟻群算法進(jìn)行改進(jìn)，應(yīng)用改進(jìn)的蟻群算法求解出最優(yōu)的遷移策略，以保證在進(jìn)行遷移后任務(wù)的執(zhí)行時(shí)間和邊緣設(shè)備的負(fù)載都處于一個(gè)較低的水平。

2 邊緣計(jì)算任務(wù)遷移模型

2.1 問題模型

本文首先給出了邊緣計(jì)算任務(wù)遷移系統(tǒng)模型圖，如圖1所示。在一定區(qū)域內(nèi)有許多邊緣設(shè)備，由邊緣服務(wù)器對這些邊緣設(shè)備進(jìn)行統(tǒng)一管理，邊緣服務(wù)器與上層云端直接相連，其中邊緣服務(wù)器分為邊緣管理服務(wù)器和邊緣計(jì)算服務(wù)器。邊緣管理服務(wù)器負(fù)責(zé)實(shí)時(shí)收集邊緣設(shè)備的信息并做出遷移決策，將決策結(jié)果返回給邊緣設(shè)備，各個(gè)設(shè)備按照決策結(jié)果將任務(wù)直接發(fā)送到相應(yīng)的邊緣計(jì)算服務(wù)器中，由邊緣計(jì)算服務(wù)器執(zhí)行計(jì)算任務(wù)，文中將邊緣計(jì)算服務(wù)器和邊緣管理服務(wù)器統(tǒng)稱為MEC服務(wù)器。進(jìn)行任務(wù)遷移的目的是減少任務(wù)執(zhí)行的時(shí)間，并平衡此區(qū)域內(nèi)MEC服務(wù)器的負(fù)載。

圖1 邊緣計(jì)算任務(wù)遷移系統(tǒng)模型圖

2.2 問題定義

假設(shè)在一定區(qū)域內(nèi)的邊緣設(shè)備中產(chǎn)生了個(gè)任務(wù)，這些任務(wù)可以表示為T ={,,…,t }，每一個(gè)任務(wù)都包含如下幾個(gè)屬性，t ={,,,,}，表示任務(wù)編號，、、、依次表示任務(wù)需要的cpu資源、內(nèi)存資源、帶寬資源和任務(wù)大小。假定在此區(qū)域內(nèi)有個(gè)MEC服務(wù)器可以提供計(jì)算和通信服務(wù)，邊緣計(jì)算服務(wù)器的集合表示為{,,…,d }，每一個(gè)MEC服務(wù)器自身能提供的可用資源如下，d ={,,,}，表示邊緣計(jì)算服務(wù)器的編號，表示MEC服務(wù)器中可用cpu資源、表示MEC服務(wù)器中可用內(nèi)存資源、表示MEC服務(wù)器中可用帶寬資源。用表示任務(wù)是否要遷移到MEC服務(wù)器執(zhí)行，的取值是∈{0,…,}，=0表示任務(wù)在本地執(zhí)行；=表示任務(wù)遷移到第個(gè)MEC服務(wù)器處執(zhí)行。

2.2.1 任務(wù)時(shí)延模型

首先定義任務(wù)在MEC服務(wù)器執(zhí)行的時(shí)間矩陣：

其中，time 表示第個(gè)任務(wù)遷移到第個(gè)MEC服務(wù)器的總期望執(zhí)行時(shí)間，總執(zhí)行時(shí)間分為任務(wù)傳輸時(shí)間tr 、任務(wù)在MEC服務(wù)器處的執(zhí)行時(shí)間ex ，因?yàn)槿蝿?wù)執(zhí)行完成后將結(jié)果回傳到本地設(shè)備的時(shí)間很短，可以忽略不計(jì)，所以任務(wù)遷移到MEC服務(wù)器的期望執(zhí)行總時(shí)間為：

=0表示任務(wù)在本地執(zhí)行，=表示任務(wù)遷移到第個(gè)MEC服務(wù)器執(zhí)行。

當(dāng)任務(wù)在本地設(shè)備執(zhí)行而不需要進(jìn)行遷移時(shí)，只存在任務(wù)執(zhí)行時(shí)間而不存在任務(wù)在鏈路中的傳輸時(shí)間。其中將任務(wù)傳輸時(shí)間定義為：

2.2.2 任務(wù)匹配度模型

在選擇MEC服務(wù)器時(shí)，不同任務(wù)對資源的需求程度不同，且每一個(gè)MEC服務(wù)器能夠提供的資源類型不同，比如一個(gè)任務(wù)是計(jì)算消耗型任務(wù)，則需要選擇計(jì)算能力較強(qiáng)的MEC服務(wù)器。因此如果想讓任務(wù)高效執(zhí)行，那么就需要將任務(wù)需求的類型與邊緣設(shè)備能夠提供的資源類型進(jìn)行匹配，用匹配度來表示任務(wù)和邊緣設(shè)備的匹配結(jié)果，將匹配度定義為當(dāng)前任務(wù)的資源請求量與邊緣設(shè)備提供的資源量的差值。

、、分別為各個(gè)差值的權(quán)重，m 的值越小，說明任務(wù)需求的資源與MEC服務(wù)器所能提供的資源越匹配，匹配度越高，任務(wù)更偏向于在匹配度高的MEC服務(wù)器中執(zhí)行。

2.2.3 任務(wù)負(fù)載模型

進(jìn)行任務(wù)遷移時(shí)，要考慮當(dāng)前設(shè)備和MEC服務(wù)器的負(fù)載情況，如果當(dāng)前設(shè)備負(fù)載較高，則應(yīng)對當(dāng)前設(shè)備上的任務(wù)進(jìn)行遷移操作，以降低設(shè)備負(fù)載，同時(shí)需要選擇負(fù)載較低的MEC服務(wù)器作為任務(wù)遷移的目的地。邊緣設(shè)備負(fù)載函數(shù)定義為：

其中，T 表示第個(gè)邊緣設(shè)備已經(jīng)執(zhí)行任務(wù)的時(shí)間，T 表示所有邊緣設(shè)備平均執(zhí)行任務(wù)的時(shí)間。T 的值越小，說明邊緣設(shè)備執(zhí)行任務(wù)的時(shí)間較短，負(fù)載較小，Load 的值也較小。反之，邊緣設(shè)備執(zhí)行任務(wù)時(shí)間較長，負(fù)載較大，Load 的值也較大。

2.2.4 目標(biāo)函數(shù)構(gòu)建

針對多目標(biāo)優(yōu)化問題，利用線性加權(quán)方式將其轉(zhuǎn)換成為單目標(biāo)問題，進(jìn)行歸一化處理后，構(gòu)建時(shí)間和匹配度的目標(biāo)函數(shù)。

、分別表示時(shí)間和匹配度所占的權(quán)重，+=1且＞0，＞0。

3 基于改進(jìn)蟻群算法的邊緣計(jì)算任務(wù)遷移

蟻群算法是一種典型的群智能優(yōu)化算法，常被用于解決路徑選擇、資源調(diào)度等一些常見問題，文獻(xiàn)［14］為了提升蟻群算法的收斂速度，引入動(dòng)態(tài)更新?lián)]發(fā)系數(shù)，在信息素更新過程中引入負(fù)載權(quán)重系數(shù)來平衡負(fù)載。文獻(xiàn)［15］提出一種測試任務(wù)并行任務(wù)調(diào)度優(yōu)化方法，并對蟻群算法進(jìn)行改進(jìn)，包括對啟發(fā)式函數(shù)和信息素更新規(guī)則的改進(jìn)，提出了一種資源均衡度評價(jià)標(biāo)準(zhǔn)，最終求得了測試時(shí)間最短、資源最均衡的任務(wù)調(diào)度序列。

3.1 改進(jìn)的蟻群算法

在螞蟻搜索過程中，螞蟻為每一個(gè)任務(wù)選擇合適的MEC服務(wù)器，將狀態(tài)轉(zhuǎn)移函數(shù)、信息素更新過程進(jìn)行了改進(jìn)，具體改進(jìn)方法如下。

3.1.1 初始化

首先對螞蟻個(gè)數(shù)、迭代次數(shù)、信息素矩陣進(jìn)行初始化操作，其中用每個(gè)MEC服務(wù)器的固有屬性作為信息素矩陣的初始化值，如公式（11）所示：

3.1.2 選擇下一個(gè)節(jié)點(diǎn)

根據(jù)公式（12）中的信息素濃度和啟發(fā)因子來綜合考慮，得出相應(yīng)的概率值，并采用輪盤賭方式進(jìn)行選擇。

其中()代表每一條路徑上的信息素濃度，()代表螞蟻對某個(gè)路徑傾向程度。本文針對公式（12）中啟發(fā)式因子η()做出如下改進(jìn)：

Load 代表MEC服務(wù)器的負(fù)載情況，L oad 越小，表明此設(shè)備的負(fù)載值越小，η()的值越大，啟發(fā)函數(shù)值越大，螞蟻越容易選擇此邊緣設(shè)備。

3.1.3 信息素更新

信息素的濃度是指導(dǎo)螞蟻搜索的關(guān)鍵，螞蟻在搜索時(shí)會偏向信息素濃度高的地方，因此為了讓信息素更好地指引螞蟻搜索，需要不斷地對每一個(gè)路徑進(jìn)行信息素更新，這樣可以防止信息素過多積累而過早收斂，同時(shí)也可以防止信息素?fù)]發(fā)過快而錯(cuò)過最優(yōu)解。信息素更新公式如下：

式中τ()為更新前信息素濃度矩陣，記錄了進(jìn)行信息素更新之前每條路徑上的信息分布情況，為信息素?fù)]發(fā)系數(shù)，因?yàn)樾畔⑺夭粩鄵]發(fā)的原因，導(dǎo)致在每一次迭代中，每條路徑上的信息素也會隨著迭代次數(shù)的增加而逐漸下降。Δτ是每一次更新過程中信息素增量的定義，也就是信息素改變了多少。Δτ分為局部信息素的更新和全局信息素的更新，即：

當(dāng)一只螞蟻完成了一次搜索后，對該螞蟻的匹配路徑進(jìn)行局部信息素的更新，定義信息素更新公式中的Δ為：

其中，為信息素常量，為目標(biāo)函數(shù)的值，越小，路徑上增加的信息素就越多。

當(dāng)所有螞蟻都完成了一次搜索后，即所有螞蟻都找到一組分配結(jié)果，此時(shí)記錄本次迭代中最優(yōu)的分配結(jié)果，然后進(jìn)行全局信息素更新操作，即：

是一次迭代中的最佳分配結(jié)果。

3.2 算法總體流程

算法詳細(xì)步驟如下：

Step 1：根據(jù)公式（9）判斷邊緣設(shè)備上的任務(wù)是否超過平均負(fù)載，將超過負(fù)載的邊緣設(shè)備上的任務(wù)加入到待遷移隊(duì)列中。

Step 2：初始化蟻群算法的相關(guān)參數(shù)，包括螞蟻個(gè)數(shù)、最大迭代次數(shù)MaxCycle等，并根據(jù)公式（11）對信息素濃度進(jìn)行初始化。

Step 3：將螞蟻隨機(jī)放置在邊緣設(shè)備上。

Step 4：根據(jù)公式（12）和公式（13），計(jì)算螞蟻為任務(wù)選擇邊緣設(shè)備的概率，并采用輪盤賭算法進(jìn)行選擇。

Step 5：當(dāng)一只螞蟻對所有任務(wù)都選擇了相應(yīng)的邊緣設(shè)備，根據(jù)公式（14）和公式（15）進(jìn)行局部信息素更新。

Step 6：當(dāng)所有螞蟻都完成了任務(wù)與邊緣設(shè)備的分配操作，則應(yīng)保留下最優(yōu)的分配策略，并根據(jù)公式（14）和公式（16）對全局最優(yōu)分配策略的信息素進(jìn)行更新操作。

Step 7：判斷當(dāng)前迭代次數(shù)是否超過最大迭代次數(shù)，若沒有，則跳轉(zhuǎn)至Step 3繼續(xù)進(jìn)行迭代；若超過了最大迭代次數(shù)，則輸出最優(yōu)的分配策略。

圖2 算法流程圖

4 實(shí)驗(yàn)分析

通過CloudSim平臺對本文改進(jìn)的蟻群算法進(jìn)行仿真實(shí)驗(yàn)，并與輪循算法和標(biāo)準(zhǔn)的蟻群算法結(jié)果進(jìn)行對比。

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

將任務(wù)數(shù)量設(shè)為50、100、150、200，任務(wù)長度設(shè)為5000MI～10000 MI，所有任務(wù)隨機(jī)生成。將MEC服務(wù)器的數(shù)量設(shè)置為6個(gè)，其具體參數(shù)設(shè)置見表1。

表1 MEC服務(wù)器的參數(shù)配置

本文改進(jìn)的蟻群算法和標(biāo)準(zhǔn)蟻群算法設(shè)置了相同參數(shù)，具體參數(shù)設(shè)置見表2。

表2 蟻群算法的參數(shù)設(shè)置

4.2 結(jié)果分析

首先隨機(jī)生成一定數(shù)量的任務(wù)，判斷本文算法產(chǎn)生的遷移策略與任務(wù)執(zhí)行時(shí)間的關(guān)系。在執(zhí)行相同數(shù)量任務(wù)時(shí)，三種算法產(chǎn)生不同的遷移結(jié)果，執(zhí)行完每種遷移策略后任務(wù)的完成時(shí)間與任務(wù)數(shù)量的關(guān)系如圖3所示。

圖3 三種算法的完成時(shí)間

從圖3可以看出，隨著任務(wù)數(shù)量的增多，輪循算法和標(biāo)準(zhǔn)蟻群算法的任務(wù)執(zhí)行時(shí)間增長迅速，但是兩種算法做出的遷移策略使得任務(wù)執(zhí)行的時(shí)間相差不大。而隨著任務(wù)數(shù)量的增加，本文算法的任務(wù)執(zhí)行時(shí)間雖然也在增長，但是增長幅度不是很大，并且遠(yuǎn)小于輪循算法和標(biāo)準(zhǔn)的蟻群算法，顯然本文做出的遷移策略相較于其他兩種算法在執(zhí)行任務(wù)花費(fèi)的時(shí)間上是相對較優(yōu)的。

對于負(fù)載均衡的判斷，本文采用了文獻(xiàn)［16］的負(fù)載均衡度判斷方法，即用負(fù)載均衡標(biāo)準(zhǔn)差作為負(fù)載均衡度的判斷依據(jù)。

L 表示所有MEC服務(wù)器的平均負(fù)載，表示單個(gè)MEC服務(wù)器的負(fù)載情況，即MEC服務(wù)器已經(jīng)執(zhí)行任務(wù)的時(shí)間，表示MEC服務(wù)器的總數(shù)，負(fù)載均衡標(biāo)準(zhǔn)差用表示，即MEC服務(wù)器的負(fù)載均衡度，的值越大，負(fù)載均衡度越大，說明MEC服務(wù)器的負(fù)載越不均衡。

保持MEC服務(wù)器的數(shù)量一定，不斷增加任務(wù)數(shù)量，根據(jù)遷移之后負(fù)載均衡度對不同任務(wù)數(shù)下的邊緣設(shè)備負(fù)載情況進(jìn)行判斷，結(jié)果如圖4所示。任務(wù)數(shù)量一定而邊緣設(shè)備數(shù)量不同時(shí)，每個(gè)邊緣設(shè)備的負(fù)載也會有所不同，將任務(wù)數(shù)量固定為200，將邊緣設(shè)備數(shù)量置為4、6、8、10時(shí)，邊緣設(shè)備的負(fù)載均衡度如圖5所示。

圖5 不同MEC服務(wù)器數(shù)量的負(fù)載均衡度對比

由圖4可知，隨著任務(wù)數(shù)量增加，各個(gè)MEC服務(wù)器的負(fù)載均衡度也逐漸上升，但本文算法對應(yīng)的每個(gè)MEC服務(wù)器的負(fù)載均衡度都要優(yōu)于其他兩個(gè)算法中的負(fù)載均衡度。當(dāng)任務(wù)數(shù)量相同時(shí)，輪循算法和標(biāo)準(zhǔn)蟻群算法計(jì)算得出的負(fù)載均衡度高于本文算法，這是因?yàn)楸疚乃惴ㄔ谶x擇目標(biāo)設(shè)備時(shí)考慮到了負(fù)載的影響，因此負(fù)載均衡度相對其他兩種算法較低。

圖4 不同任務(wù)數(shù)下的負(fù)載均衡度對比

由圖5可以看出，當(dāng)任務(wù)數(shù)量固定時(shí)，MEC服務(wù)器的負(fù)載均衡度隨著服務(wù)器的增多而下降，因?yàn)槿蝿?wù)都被均勻分配到了每一個(gè)服務(wù)器上，因此服務(wù)器的負(fù)載均衡度呈現(xiàn)下降趨勢。由于本文算法考慮了負(fù)載的影響，所以無論邊緣設(shè)備的數(shù)量如何變化，負(fù)載均衡度相較于輪循算法和標(biāo)準(zhǔn)蟻群算法總是較低的。

5 結(jié)語

本文針對邊緣設(shè)備的計(jì)算遷移工作展開了研究，構(gòu)建了任務(wù)與邊緣服務(wù)器間的時(shí)延模型、任務(wù)匹配度模型和負(fù)載模型，利用構(gòu)建的模型對標(biāo)準(zhǔn)蟻群算法進(jìn)行改進(jìn)。利用設(shè)備的固有屬性作為信息素初始化依據(jù)，利用設(shè)備負(fù)載信息改進(jìn)狀態(tài)轉(zhuǎn)移函數(shù)，使得任務(wù)更容易找到負(fù)載較低的邊緣服務(wù)器，其次將所構(gòu)建的目標(biāo)函數(shù)作為信息素更新規(guī)則，仿真結(jié)果表明改進(jìn)的算法既減少了任務(wù)執(zhí)行的時(shí)間、也降低了邊緣服務(wù)器的負(fù)載均衡度。