移動邊緣環(huán)境下面向工作流管理的計(jì)算遷移方法

伏舒存 付章杰 邢國穩(wěn) 劉慶祥 許小龍

摘 要：針對移動邊緣環(huán)境下移動設(shè)備大量的能源消耗問題，為了優(yōu)化移動設(shè)備的能源消耗，提出一種能耗感知的工作流計(jì)算遷移（EOW）方法。首先，基于排隊(duì)論分析邊緣設(shè)備中計(jì)算任務(wù)的平均等待時間，建立了移動設(shè)備的時間模型和能耗模型;然后，基于非支配排序算法（NSGAⅢ）提出對應(yīng)的計(jì)算遷移方法，對工作流的計(jì)算任務(wù)進(jìn)行合理的分配，將一部分計(jì)算任務(wù)留在移動設(shè)備處理，或者遷移到邊緣計(jì)算平臺和遠(yuǎn)程云端，實(shí)現(xiàn)每個移動設(shè)備的節(jié)能目標(biāo);最后，通過CloudSim仿真平臺對提出的計(jì)算遷移方法進(jìn)行仿真和對比實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果表明，EOW方法能夠明顯地減少每個移動設(shè)備的能源消耗，同時滿足每一個工作流的截止時間的要求。

關(guān)鍵詞：能源消耗;計(jì)算遷移;邊緣計(jì)算;工作流;截止時間

中圖分類號：TP338.6

文獻(xiàn)標(biāo)志碼：A

Abstract： The problem of high energy consumption for mobile devices in mobile edge computing is becoming increasingly prominent. In order to reduce the energy consumption of the mobile devices， an Energyaware computation Offloading for Workflows （EOW） was proposed. Technically， the average waiting time of computing tasks in edge devices was analyzed based on queuing theory， and the time consumption and energy consumption models for mobile devices were established. Then a corresponding computation offloading method， by leveraging NSGAⅢ （Nondominated Sorting Genetic Algorithm Ⅲ） was designed to offload the computing tasks reasonably. Part computing tasks were processed by the mobile devices， or offloaded to the edge computing platform and the remote cloud， achieving the goal of energysaving for all the mobile devices. Finally， comparison experiments were conducted on the CloudSim platform. The experimental results show that EOW can effectively reduce the energy consumption of all the mobile devices and satisfy the deadline of all the workflows.

英文關(guān)鍵詞Key words： energy consumption; computation offloading; edge computing; workflow; deadline

0 引言

移動設(shè)備由于其便捷性和擴(kuò)展性被人們廣泛地使用，移動支付、定位導(dǎo)航、自然語言處理等移動應(yīng)用已經(jīng)完全融入到人們生活的各個方面[1]。在用戶使用移動應(yīng)用時，應(yīng)用程序的執(zhí)行通常需要一定的物理資源，但是，由于移動設(shè)備的物理資源有限，很難運(yùn)行復(fù)雜且計(jì)算需求大的應(yīng)用，結(jié)果導(dǎo)致移動應(yīng)用很難滿足用戶的服務(wù)質(zhì)量需求。

為了緩解移動設(shè)備物理資源受限的壓力，為移動用戶提供更高質(zhì)量的服務(wù)，云計(jì)算技術(shù)被引入到了移動環(huán)境[2]。移動應(yīng)用中的一部分計(jì)算任務(wù)可以借助計(jì)算遷移技術(shù)，把這些計(jì)算任務(wù)通過無線網(wǎng)絡(luò)或者蜂窩網(wǎng)絡(luò)從移動終端遷移到遠(yuǎn)程云數(shù)據(jù)中心執(zhí)行[3-4]。

移動云計(jì)算技術(shù)擴(kuò)展了移動設(shè)備的資源，并且很大程度上降低了移動設(shè)備在執(zhí)行移動應(yīng)用時產(chǎn)生的能源消耗[5];然而，由于云數(shù)據(jù)中心往往是集中式的，它們通常遠(yuǎn)離移動用戶，因此通過廣域網(wǎng)（Wide Area Network， WAN）在移動設(shè)備和云平臺之間進(jìn)行計(jì)算遷移而導(dǎo)致的傳輸延遲是不可忽視的。這種傳輸延遲導(dǎo)致設(shè)備產(chǎn)生額外的能量消耗[6]。

移動邊緣計(jì)算是一種減少傳輸延遲和移動設(shè)備額外能源消耗的方法。邊緣計(jì)算平臺將移動用戶附近分散的資源（包括計(jì)算資源、存儲資源等）統(tǒng)一的管理，為移動用戶提供高效的服務(wù)。邊緣計(jì)算設(shè)備（例如朵云等）作為部署在用戶附近的服務(wù)器集群，可以構(gòu)建成一個移動邊緣計(jì)算平臺同時為周圍的移動設(shè)備提供訪問接口，為用戶提供服務(wù)[7]。但是邊緣設(shè)備的物理資源相對于云數(shù)據(jù)中心是有限的，當(dāng)大量并發(fā)的應(yīng)用被遷移到平臺上，其中一部分計(jì)算任務(wù)必須在邊緣設(shè)備中排隊(duì)等待執(zhí)行[8]。隨著用戶需求的不斷增加，越來越多的計(jì)算密集型應(yīng)用出現(xiàn)，這些應(yīng)用可以被構(gòu)建成由任務(wù)和數(shù)據(jù)依賴的工作流[9-10]。當(dāng)大量并發(fā)的工作流任務(wù)被遷移到邊緣設(shè)備時，邊緣設(shè)備只能夠提供相對有限的計(jì)算和數(shù)據(jù)存儲資源，因此如何在移動設(shè)備端、邊緣設(shè)備、遠(yuǎn)程云計(jì)算平臺部署移動應(yīng)用，設(shè)計(jì)合理的計(jì)算遷移方案，是當(dāng)前面臨的一個重要的技術(shù)挑戰(zhàn)。

針對移動應(yīng)用計(jì)算遷移問題，國內(nèi)外學(xué)術(shù)界以及工業(yè)界都展開了很多深入的研究。基于移動云的計(jì)算遷移的出現(xiàn)為移動設(shè)備提供了一種滿足移動應(yīng)用需求的方法。計(jì)算任務(wù)被遷移到遠(yuǎn)程云中執(zhí)行，從而延長移動設(shè)備的電池壽命[11]。Elgazzar等[12]提出了一種云輔助移動服務(wù)框架，可以根據(jù)移動應(yīng)用的資源需求和網(wǎng)絡(luò)狀況動態(tài)分配計(jì)算資源，提供強(qiáng)大的計(jì)算遷移能力; Shi等[13]設(shè)計(jì)了基于移動設(shè)備的計(jì)算遷移系統(tǒng)，為移動設(shè)備提供計(jì)算遷移服務(wù)，此系統(tǒng)能夠有效地管理云資源來應(yīng)對來自于移動設(shè)備的計(jì)算任務(wù)，提高移動設(shè)備卸載性能并降低向提供商發(fā)送每個請求的成本; Liu等[14]設(shè)計(jì)了一個針對于應(yīng)用內(nèi)容的計(jì)算遷移框架，按照應(yīng)用程序的需求對計(jì)算任務(wù)進(jìn)行遷移，同時又提出了一個估計(jì)模型用于自動選擇云資源來進(jìn)行計(jì)算遷移。

將計(jì)算任務(wù)遷移到移動邊緣平臺以優(yōu)化通信和能量消耗同樣得到了許多的研究：文獻(xiàn)[15]中研究一個綠色的移動邊緣計(jì)算（Mobile Edge Computing， MEC）系統(tǒng)，結(jié)合基于李雅普諾夫（Lyapunov）優(yōu)化的復(fù)雜度低的動態(tài)計(jì)算遷移算法，開發(fā)一種有效的計(jì)算遷移策略，有效降低了設(shè)備的執(zhí)行成本;Zhang等[16]結(jié)合5G異構(gòu)網(wǎng)絡(luò)的多址特性設(shè)計(jì)了5G異構(gòu)網(wǎng)絡(luò)中MEC的節(jié)能計(jì)算遷移方法，該方法聯(lián)合優(yōu)化卸載和無線資源分配，以在延遲約束下獲得最小的能量消耗;文獻(xiàn)[17]中根據(jù)移動用戶的分布特征和計(jì)算任務(wù)，提出了軟件定義的協(xié)同遷移模型，然后設(shè)計(jì)了一種在線任務(wù)調(diào)度算法，實(shí)現(xiàn)設(shè)備間均衡的能源消耗;Wang等[18]開發(fā)了一種最佳資源分配方法，該方法根據(jù)用戶的計(jì)算延遲約束最小化無線訪問節(jié)點(diǎn)的總能量消耗，利用優(yōu)化技術(shù)以半閉合的形式推導(dǎo)出最優(yōu)解，有效降低了無線訪問節(jié)點(diǎn)能源消耗和服務(wù)延遲。

但是，現(xiàn)存的研究還存在一些問題尚未解決：首先在邊緣計(jì)算環(huán)境下，如何針對能耗、延遲等多個目標(biāo)進(jìn)行優(yōu)化;接著邊緣平臺的資源都是有限的，當(dāng)計(jì)算任務(wù)遷移到平臺上需要排隊(duì)，如何分析任務(wù)到達(dá)的頻率以及任務(wù)排隊(duì)的時間也是一個問題;然后，針對密集型移動應(yīng)用通常要用工作流來模擬，工作流中的計(jì)算任務(wù)相互都存在數(shù)據(jù)和控制約束，此時如何考慮這些任務(wù)的遷移問題，又是一個巨大的挑戰(zhàn)。本文將針對移動邊緣環(huán)境，對工作流應(yīng)用的計(jì)算任務(wù)進(jìn)行遷移來達(dá)到移動設(shè)備能耗和移動應(yīng)用時間的優(yōu)化。

1 系統(tǒng)模型

1.1 基本概念

在本文中，移動應(yīng)用由工作流構(gòu)建，并且使用加權(quán)有向無環(huán)圖（Directed Acyclic Graph， DAG）來定義，表示為Af（T，R），式中T={t1f，t2f，…，tNff}表示計(jì)算任務(wù)的集合，R=（r（tif，tjf），di， j）表示計(jì)算任務(wù)之間的依賴關(guān)系，其中Nf表示第f個工作流中的任務(wù)數(shù)量，di， j表示計(jì)算任務(wù)之間傳輸?shù)臄?shù)據(jù)量。

邊緣設(shè)備虛擬化出多個虛擬機(jī)，用于并行處理計(jì)算任務(wù)，表示為CL=（V，ccl，LAN），其中V是邊緣設(shè)備中虛擬機(jī)的數(shù)量，ccl是邊緣平臺的計(jì)算能力，LAN是局域網(wǎng)（Local Area Network， LAN）的傳輸延遲。

計(jì)算任務(wù)表示為tif=（wif，xif），其中wif是任務(wù)tif的工作負(fù)載，xif是遷移策略。一個工作流中所有計(jì)算任務(wù)的遷移策略表示為Xf={xif|xif∈T}，其中xif=0表示計(jì)算任務(wù)tif在移動設(shè)備中執(zhí)行，xif=1或2表示tif分別被遷移到邊緣設(shè)備和遠(yuǎn)程云端。對所有工作流進(jìn)行全局的計(jì)算遷移表示為Y= {X1， X2， …， XF}。

1.2 時間計(jì)算模型

本節(jié)給出三種時間的計(jì)算模型，分別是：計(jì)算任務(wù)在邊緣設(shè)備中平均等待的時間、計(jì)算任務(wù)在不同服務(wù)終端執(zhí)行消耗的時間，以及計(jì)算任務(wù)之間數(shù)據(jù)傳輸所花費(fèi)的時間。

1.2.1 平均等待時間

假設(shè)邊緣設(shè)備中的虛擬機(jī)數(shù)量為V。任務(wù)到達(dá)時間的間隔服從參數(shù)λ的負(fù)指數(shù)分布，并且邊緣設(shè)備中的服務(wù)時間受到參數(shù)μ的負(fù)指數(shù)分布的影響。根據(jù)排隊(duì)論建立M/M/V/∞模型。設(shè)βn是邊緣設(shè)備在穩(wěn)定狀態(tài)下，運(yùn)行時隊(duì)列長度為l的概率。

2.2 基于NSGAⅢ的計(jì)算遷移方法

與傳統(tǒng)遺傳算法相比，NSGAⅢ不僅可以快速準(zhǔn)確地找到可行解中的全局最優(yōu)解，同時在多目標(biāo)的情況下優(yōu)化效果要明顯優(yōu)于其他基因算法，因此，本文采用NSGAⅢ來解決多目標(biāo)的計(jì)算遷移問題?；谶z傳算法，本文考慮如下的編碼方法：每一個染色體代表F個工作流的計(jì)算遷移策略，本文考慮對每一個工作流，最小化其對應(yīng)的每一個移動設(shè)備的能源消耗，因此，每一條染色體均有F個適應(yīng)度函數(shù)，由式（12）給出。

對于每一個工作流，使用算法1根據(jù)計(jì)算遷移策略求出實(shí)際的完成時間，如果不滿足式（13）和（14）中的時間約束和策略約束，則該遷移策略所表示的染色體在選擇的過程中不予考慮，滿足約束的被稱作有效染色體，種群中有效染色體的個數(shù)為S，每一代的染色體數(shù)為G。對S個染色體進(jìn)行交叉變異操作，生成2G-S個染色體，當(dāng)前的染色體數(shù)為2G。不同于普通的遺傳算法，本文使用NSGAⅢ來進(jìn)行下一代的選擇。

1）非支配劃分。基于有效染色體中包含的工作流計(jì)算遷移策略，計(jì)算相應(yīng)的移動設(shè)備能源消耗。根據(jù)這F個適應(yīng)值進(jìn)行非支配性選擇，將2G個染色體劃分成若干非支配性層。

2）初始選擇。從最高非支配層開始，每次隨機(jī)選擇一個染色體進(jìn)入下一代，直至選出G個遷移策略。記最后一個染色體所在的非支配層為第l層：如果l層的所有染色體均被選擇進(jìn)入下一代，則選擇操作結(jié)束;否則進(jìn)行優(yōu)化選擇。

3）優(yōu)化選擇。記l層共有m個染色體被選擇。首先除去這m個染色體。對于每一個工作流，一共有S個計(jì)算遷移策略，在這2G個遷移策略對應(yīng)的適應(yīng)值中選擇最小值，其余的適應(yīng)值均減去該最小值，然后根據(jù)相應(yīng)的權(quán)值計(jì)算每個移動應(yīng)用適應(yīng)值的極值。將每個適應(yīng)值作為一個坐標(biāo)軸，基于極值計(jì)算出每個坐標(biāo)軸的截距。對所有的適應(yīng)值進(jìn)行歸一化操作。每一個染色體對應(yīng)F個坐標(biāo)軸組成的超平面的一個點(diǎn)，其各坐標(biāo)軸的坐標(biāo)即為對應(yīng)的歸一化后的適應(yīng)值?；趨⒖键c(diǎn)選擇：在截距均為1的F個坐標(biāo)軸進(jìn)行等值劃分，在超平面上生成若干參考點(diǎn)，將歸一化后的染色體與參考點(diǎn)關(guān)聯(lián)。根據(jù)關(guān)聯(lián)的參考點(diǎn)的個數(shù)將第l非支配層的染色體進(jìn)行劃分。從關(guān)聯(lián)的參考點(diǎn)的個數(shù)的最高層開始，隨機(jī)選擇一個個染色體，直至選出所有的m個染色體。

3 實(shí)驗(yàn)評估

本文將EOW和三種不同的計(jì)算遷移方法進(jìn)行比較，包括：將所有計(jì)算任務(wù)留在移動設(shè)備處理的方法，記作Benchmark;將所有計(jì)算任務(wù)遷移到邊緣設(shè)備的方法，記作為CLO;以及將所有任務(wù)都遷移到云端的方法，記作為CO[19-20]。

3.1 實(shí)驗(yàn)環(huán)境

本文采用CloudSim仿真工具進(jìn)行了邊緣設(shè)備中的計(jì)算遷移模擬實(shí)驗(yàn)，來評估提出的計(jì)算遷移方法。實(shí)驗(yàn)所需的工作流實(shí)例和數(shù)據(jù)部分來源于文獻(xiàn)[10]，本文使用移動設(shè)備能源消耗計(jì)算遷移結(jié)果、工作流的完成時間和移動設(shè)備各部分能耗的對比來評估提出的遷移方法。實(shí)驗(yàn)所需的參數(shù)的設(shè)置如表1所示。

4 結(jié)語

為了優(yōu)化邊緣環(huán)境下的計(jì)算遷移中移動設(shè)備的能源消耗，本文提出了一種能耗感知的工作流計(jì)算遷移方法?；谂抨?duì)論在邊緣計(jì)算平臺中建立了移動設(shè)備的能量消耗模型。在方法上本文提出了基于NSGAⅢ的節(jié)能計(jì)算遷移方法，不再是集中處理計(jì)算任務(wù)，而是合理將任務(wù)分配，以優(yōu)化所有移動設(shè)備的能源消耗。最后，實(shí)驗(yàn)結(jié)果驗(yàn)證了本文方法的有效性。將用戶的移動性和邊緣網(wǎng)絡(luò)變化考慮到計(jì)算遷移中是筆者未來的工作目標(biāo)。

參考文獻(xiàn) （References）

[1] 張文麗，郭兵，沈艷，等.智能移動終端計(jì)算遷移研究[J].計(jì)算機(jī)學(xué)報(bào)，2016，39（5）：1021-1038. （ZHANG W L， GUO B， SHEN Y， et al. Computation offloading on intelligent mobile terminal [J]. Chinese Journal of Computers， 2016， 39（5）： 1021-1038.）

[2] 崔勇，宋健，繆蔥蔥， 等.移動云計(jì)算研究進(jìn)展與趨勢[J].計(jì)算機(jī)學(xué)報(bào)，2017，40（2）：273-295. （CUI Y， SONG J， MIAO C C， et al. Mobile cloud computing research progress and trends [J]. Chinese Journal of Computers， 2017， 40（2）： 273-295.）

[3] ??? BARBERA M V， KOSTA S， MEI A， et al. To offload or not to offload？ The bandwidth and energy costs of mobile cloud computing [C]// Proceedings of the 2013 IEEE International Conference on Computer Communications. Piscataway， NJ： IEEE， 2013： 1285-1293.

[4] ??? SHI W， CAO J， ZHANG Q， et al. Edge computing： vision and challenges [J]. IEEE Internet of Things Journal， 2016， 3（5）： 637-646.

[5] ??? DENG S， HUANG L， TAHERI J， et al. Computation offloading for service workflow in mobile cloud computing [J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（12）： 3317-3329.

[6] ??? XU X， DOU W， ZHANG X， et al. EnReal： An energyaware resource allocation method for scientific workflow executions in cloud environment [J]. IEEE Transactions on Cloud Computing， 2016， 4（2）： 166-179.

[7] ??? 趙梓銘，劉芳，蔡志平，等.邊緣計(jì)算：平臺、應(yīng)用與挑戰(zhàn)[J].計(jì)算機(jī)研究與發(fā)展，2018，55（2）：327-337. （ZHAN Z M， LIU F， CAI Z P， et al. Edge computing： platforms， applications and challenges [J]. Journal of Computer Research and Development， 2018， 55（2）： 327-337.）

[8] ??? JIA M， LIANG W， XU Z， et al. Cloudlet load balancing in wireless metropolitan area networks[C]// Proceedings of the 35th Annual IEEE International Conference on Computer Communications. Piscataway， NJ： IEEE， 2016： 1-9.

[9] ??? 曾廣周，黨妍.基于移動計(jì)算范型的遷移工作流研究[J].計(jì)算機(jī)學(xué)報(bào)，2003， 26（10）：1343-1349.（ZENG G Z， DANG Y. The study of migrating workflow based on the mobile computing paradigm[J]. Chinese Journal of Computers， 2003， 26（10）： 1343-1349.）

[10] ?? ZHU Z， ZHANG G， LI M， et al. Evolutionary multiobjective workflow scheduling in cloud [J]. IEEE Transactions on Parallel and Distributed Systems， 2016， 27（5）： 1344-1357.

[11] ?? RIMAL B P， van PHAM D， MAIER M. Cloudlet enhanced fiberwireless access networks for mobileedge computing[J]. IEEE Transactions on Wireless Communications， 2017， 16（6）： 3601-3618.

[12] ?? ELGAZZAR K， MARTIN P， HASSANEIN H. Cloudassisted computation offloading to support mobile services[J]. IEEE Transactions on Cloud Computing， 2016， 4（3）： 279-292.

[13] ?? SHI C， HABAK K， PANDURANGAN P， et al. COSMOS： computation offloading as a service for mobile devices[C]// Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing. New York： ACM， 2014： 287-296.

[14] ?? LIU Z， ZENG X， HUANG W， et al. Framework for contextaware computation offloading in mobile cloud computing[C]// Proceedings of the 15th IEEE International Symposium on Parallel and Distributed Computing. Piscataway， NJ： IEEE， 2016： 172-177.

[15] ?? MAO Y， ZHANG J， LETAIEF K B. Dynamic computation offloading for mobileedge computing with energy harvesting devices[J]. IEEE Journal on Selected Areas in Communications， 2016， 34（12）： 3590-3605.

[16] ?? ZHANG K， MAO Y， LENG S， et al. Energyefficient offloading for mobile edge computing in 5G heterogeneous networks[J]. IEEE Access， 2016， 4：5896-5907.

[17] ?? CUI Y， SONG J， REN K， et al. Software defined cooperative offloading for mobile cloudlets[J]. IEEE/ACM Transactions on Networking， 2017， 25（3）： 1746-1760.

[18] ?? WANG F， XU J， WANG X， et al. Joint offloading and computing optimization in wireless powered mobileedge computing systems [J]. IEEE Transactions on Wireless Communications， 2018， 17（3）： 1784-1797.

[19] ?? KUMAR K， LU Y H. Cloud computing for mobile users： can offloading computation save energy？ [J]. Computer， 2010， 43（4）： 51-56.

[20] ?? YANG Z， NIYATO D， PING W. Offloading in mobile cloudlet systems with intermittent connectivity [J]. IEEE Transactions on Mobile Computing， 2015， 14（12）： 2516-2529.