移動邊緣環境下面向工作流管理的計算遷移方法

伏舒存 付章杰 邢國穩 劉慶祥 許小龍

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

關鍵詞：能源消耗;計算遷移;邊緣計算;工作流;截止時間

中圖分類號：TP338.6

文獻標志碼：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.

英文關鍵詞Key words： energy consumption; computation offloading; edge computing; workflow; deadline

0 引言

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

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

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

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

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

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

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

1 系統模型

1.1 基本概念

在本文中，移動應用由工作流構建，并且使用加權有向無環圖（Directed Acyclic Graph， DAG）來定義，表示為Af（T，R），式中T={t1f，t2f，…，tNff}表示計算任務的集合，R=（r（tif，tjf），di， j）表示計算任務之間的依賴關系，其中Nf表示第f個工作流中的任務數量，di， j表示計算任務之間傳輸的數據量。

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

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

1.2 時間計算模型

本節給出三種時間的計算模型，分別是：計算任務在邊緣設備中平均等待的時間、計算任務在不同服務終端執行消耗的時間，以及計算任務之間數據傳輸所花費的時間。

1.2.1 平均等待時間

假設邊緣設備中的虛擬機數量為V。任務到達時間的間隔服從參數λ的負指數分布，并且邊緣設備中的服務時間受到參數μ的負指數分布的影響。根據排隊論建立M/M/V/∞模型。設βn是邊緣設備在穩定狀態下，運行時隊列長度為l的概率。

2.2 基于NSGAⅢ的計算遷移方法

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

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

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

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

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

3 實驗評估

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

3.1 實驗環境

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

4 結語

為了優化邊緣環境下的計算遷移中移動設備的能源消耗，本文提出了一種能耗感知的工作流計算遷移方法。基于排隊論在邊緣計算平臺中建立了移動設備的能量消耗模型。在方法上本文提出了基于NSGAⅢ的節能計算遷移方法，不再是集中處理計算任務，而是合理將任務分配，以優化所有移動設備的能源消耗。最后，實驗結果驗證了本文方法的有效性。將用戶的移動性和邊緣網絡變化考慮到計算遷移中是筆者未來的工作目標。

參考文獻 （References）

[1] 張文麗，郭兵，沈艷，等.智能移動終端計算遷移研究[J].計算機學報，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].計算機學報，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].計算機研究與發展，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].計算機學報，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.