基于云邊協同多任務計算卸載策略

鐘云峰，宋偉寧

(東華理工大學 信息工程學院，江西 南昌 330013)

0 引 言

近年來，隨著互聯網、無線接入技術和智能終端技術的發展，極大推動了物聯網(Internet of Things，IoT)產業的發展。物聯網垂直應用領域的研究也在快速推進，產生了許多的應用場景[1]。隨著工業4.0、“中國制造2025”的提出，工業互聯網成為解決智能工廠中許多問題的主要方案[2]。作為云計算的拓展和補充，邊緣計算受到越來越多人的重視[3]。針對由于云計算采用集中式計算造成的網絡擁塞以及傳輸時延較大的問題，邊緣計算采用了分布式計算方式，由分布在網絡中的多個服務器接受用戶的計算任務，從而降低設備上傳數據至云服務器的需求，減小了網絡擁塞[4]。邊緣計算是工業互聯中的關鍵技術，云計算和邊緣計算優勢互補，共同促進整個工業IT和OT的深度融合。

目前大多數研究針對的都是移動邊緣計算，計算卸載技術解決了用戶等待時延高和電池電量快速消耗的問題。葉桓宇[5]利用邊緣計算(Edge Computing，EC)和軟件定義網絡(Software Defined Networks，SDN)的技術特點，提出了一種新型SDIN架構，并在該架構的基礎上，設計實現多QoS的優先級隊列計算卸載算法。Liu Juan等人[6]根據建立的模型，使用馬爾可夫決策過程對每個任務的平均能耗和平均時延進行分析，并提出了一種有效的一維搜索算法，以找到最佳的任務調度策略，降低了任務時延。Mao Y等人[7]提出了一種基于Lyapunov優化的動態計算卸載(LODCO)算法，有效降低了時延。還有Jia M、Kao Y H[8-9]也提出了以優化時延為目標的在線任務卸載算法。以上是以優化時延為目標的，還有以權衡時延和能耗為目標的研究。例如，代美玲等人[10]以最小化任務時延和設備能耗為目標，把問題描述為資源約束下的最小化能耗和時延加權和的凸優化問題，提出基于乘子法的計算卸載與資源分配解決該問題。孟陳融[11]提出了權衡時延和能耗的任務卸載模型，設計了一種啟發式算法來解決該問題，有效降低了任務的時延和設備的能耗。Nan Y、Wang W、Liu L Q[12-14]等人也提出了能耗和時延的權衡優化的卸載方案。周鵬等人[15]提出了一種工業物聯網中計算任務跨域卸載模型，將資源分配與計算卸載分為兩個子問題，分別得出兩個子問題的最優解，最終就是整個優化問題的最優解。

以上大多數研究都是針對移動邊緣計算的，在工廠中大多數設備都是有線供電，移動邊緣計算的模型和卸載策略不適用。該文設計了一種基于云邊協同的工業互聯網環境下多任務計算卸載模型和以優化時延為目標的計算卸載策略。首先融合邊緣云與遠端云構建了一種面向多終端的網絡架構，依此建立系統模型；在此模型基礎上，構造了以優化卸載時延的目標函數；最后，設計求解算法，求出最優解，合理實施計算卸載。

1 系統模型及問題描述

1.1 系統模型

基于云邊協同的計算卸載框架如圖1所示，由一個遠端的云計算中心、多個近處的邊緣服務器以及多個工廠中的終端設備組成。在工廠中的邊緣服務器不一定只有一個，可以根據終端設備數量或者任務請求量來劃分出幾個區域，在每個區域放置一個邊緣服務器。遠端云服務中心與邊緣服務中心、邊緣服務中心與終端設備分別存在著一對多的映射關系，邊緣服務器通過互聯網接入云服務中心，終端設備通過有線網或者無線網接入到邊緣服務器。終端設備把要執行的任務信息發送到邊緣服務器，包括任務需要上傳的數據量大小、需要的CPU時鐘周期數、任務的返回數據量大小等信息，服務器根據任務信息和邊緣服務器的資源信息來作出決策，下發至終端。

圖1 基于云邊協同的計算卸載框架

1.2 時延模型

采用邊緣計算的目的就是為了任務能夠快速響應，所以能耗優化不是該文考慮的方面，系統優化的目標是時延。系統時延由計算時延和通信時延組成，計算時延有本地計算時延、邊緣計算時延、云端計算時延；通信時延有數據上傳傳輸時延和結果返回傳輸時延。由于一般回傳的數據量相對較小，所以該文不考慮結果回傳時延。

1.3 終端計算模型

假設一個區域內有N個終端設備，表示為N=[1,2,…,n]，其中每個終端都有M個任務需要執行，表示為M=[1,2,…,m]。每個計算任務定義為元組Ai,j=(Di,j,Wi,j,Ri,j)(i∈N,j∈M)，Di,j表示當前任務的數據量，Wi,j表示當前計算任務所需要的CPU時鐘周期數，Ri,j表示響應數據大小。任務在終端設備上執行的時延為計算時延tlocal，可表示為：

(1)

1.4 邊緣計算模型

任務卸載到邊緣服務器的時延有數據上傳時延、計算時延、等待時延，所以任務在邊緣服務器上執行的時延tedge可表示為：

(2)

其中，twait為基于排隊論的等待時延預測[16]。

根據排隊論的Little法則，在平衡條件下，任務在服務器等待的平均時間為系統的平均等待隊長除以任務的平均進入率，即：

(3)

在時長為t的時間段內，等待的任務數為Nt-S，隨著時間的增加，計算平均等待隊長為：

(4)

其中，Nt為t時刻的全部任務數，S為邊緣服務器同時服務的最大任務數。同時得到任務平均進入率。

(5)

其中，N0為決策開始時系統內的任務數。由此，可以得到排隊等待時間的預測值。

1.5 云端計算模型

任務卸載到云服務中心的時延有數據上傳時延和計算時延，所以任務在云服務器上執行的時延tcloud可表示為：

(6)

1.6 問題描述

一個任務Ai,j有可能在本地執行或者卸載到邊緣服務器、云服務器，設xi,j為1表示在本地執行，xi,j為0表示卸載執行；yi,j為0表示沒有卸載到邊緣服務器，yi,j為1表示卸載到邊緣服務器；zi,j為0表示沒有卸載到云服務器，zi,j為1表示卸載到云服務器。所以任務Ai,j的執行時延ti,j可表示為：

(7)

優化的目標是總時延最小即：

(8)

約束條件為：

xi,j+yi,j+zi,j=1，xi,j,yi,j,zi,j∈0,1

(9)

變量標識如表1所示。

表1 變量標識

續表1

2 卸載策略

根據上面描述，問題變成了一個01整數規劃問題，只需要求得最優解然后按照最優解進行任務卸載。求解01規劃的方法有很多，一般的有分支定界法、枚舉法和模擬退火法，當M和N比較大時分支定界法和枚舉法會出現收斂速度慢的問題。所以該文選取了混合整數線性規劃算法來求解上述問題，混合整數線性規劃算法具有求解速度快且是精確解的優點。

混合整數線性規劃算法求解步驟：

01整數規劃是特殊的整數規劃，這類問題被分類為NP困難問題。混合整數線性規劃算法使用此基本策略來求解混合整數線性規劃。混合整數線性規劃算法可以在任一階段完成問題的求解。如果它在某個階段成功求解了問題，算法不會執行后面的階段。

(1)使用線性規劃預處理縮減問題的規模。預處理步驟旨在消除冗余變量和約束，改善模型的尺度和約束矩陣的稀疏性，加強變量的邊界，檢測模型的原始和對偶不可行性。

(2)使用線性規劃求解初始松弛(非整數)問題。

(3)執行混合整數規劃預處理以收緊混合整數問題的LP松弛。混合整數規劃預處理的主要目標是簡化后續的分支定界計算。預處理包括快速預檢查和消除一些無用的子問題候選項，以免分支定界算法對其進行分析。

(4)嘗試切割生成以進一步收緊混合整數問題的LP松弛。

(5)嘗試使用啟發式方法求得整數可行解。

(6)使用分支定界算法系統地搜索最優解。

最后根據求解出來的最優解來執行卸載策略。

3 仿真結果與分析

為了驗證云邊協同多任務計算卸載策略的有效性，首先比較文中方法與局部卸載方法的差異，即任務只在本地或者邊緣服務器執行，不卸載到云服務中心；再將文中的卸載時延策略與最小時延能耗策略[10]進行比較；然后研究在用上述兩種方法求解的情況下，計算任務總時延和任務數量的關系；最后比較模擬退火算法和混合整數線性規劃算法在計算任務的總時延和算法執行時間方面的差異。

仿真實驗在Matlab環境下進行，系統的各個仿真參數如表2所示。表2中給出了任務數據量大小、任務所需要的CPU時鐘周期數、終端設備的計算能力、邊緣服務器的計算能力、云服務器的計算能力、終端到邊緣服務器的傳輸速率、邊緣服務器到云服務器的傳輸速率。

表2 系統的仿真參數設置

首先，通過設置不同的任務數量，來比較不同卸載策略完成任務的總時延。計算任務總時延與任務數量的關系如圖2所示。圖2比較了云邊協同多任務計算卸載策略(文中方法)與局部卸載方法完成任務的總時延，從圖中可以看出文中方法優于局部卸載方法，相比局部卸載方法時延降低了4%。所以在實際的部署中，將邊緣服務器與云服務器聯動起來能夠有效地降低任務時延，提高服務質量。

圖2 不同卸載策略下任務完成時間的比較

再將文中卸載策略與最小時延和能耗卸載策略進行比較，比較結果如圖3所示。從圖3可以看出，與最小時延和能耗的卸載策略相比，文中的最小時延卸載策略完成任務的時延更低，時延降低了10%。在時延要求很高的情況下，不考慮能耗的卸載策略能夠更好地降低時延。

圖4為不同任務數量下文中策略分配任務的情況。從圖中可以看到任務會卸載到不同的位置，卸載策略會根據任務的數據量大小、計算量大小等信息將任務卸載到最適合的位置來減小時延。隨著任務數量的增加，邊緣設備的壓力會增加，所以會有更多的任務卸載到云端和設備終端。

圖3 不同卸載策略下任務完成時間的比較

圖4 任務卸載位置分配

模擬退火算法與混合整數線性規劃算法的比較如圖5所示。從圖5可以看出，兩種算法中時延都隨著任務數量的增加而增加。混合整數線性規劃算法在不同任務數量下的性能都優于模擬退火算法，這是因為混合整數線性規劃算法能夠求解出01整數規劃的最優解，而模擬退火算法作為啟發式算法，不一定能夠求出最優解。

圖5 模擬退火算法與混合整數線性規劃算法的比較

當設備數量增加時，假設每臺設備有10個任務，比較模擬退火算法與混合整數線性規劃算法的算法執行時間，如表3所示。從表3可以看出，模擬退火算法的執行時間隨著設備數量的增多而增加，隨著設備規模的增加，混合整數線性規劃算法的算法執行時間基本沒太大的增加。因此，仿真結果表明混合整數線性規劃算法明顯優于模擬退火算法。

表3 模擬退火算法與混合整數線性規劃

4 結束語

研究了基于云邊協同的多任務計算卸載問題，設計了基于云邊協同的計算卸載框架；基于此系統模型，以最小化任務時延為目標，設計了一種多任務計算卸載方法。針對現實中任務排隊時延計算問題，采用了一種基于排隊論的等待時延預測方法。針對根據系統模型建立的01整數規劃問題，提出了混合整數線性規劃算法的解法。仿真結果表明，與局部卸載方法和最小時延和能耗卸載方法相比，提出的基于云邊協同的計算卸載方法在時延上有所優化，在算法執行時間上也有很大的提升。