移動邊緣計算中帶有緩存機制的任務卸載策略

郭 煜

(廣東國防科技技師學院 廣東 廣州 510515)

0 引 言

當前，隨著無線通信技術和物聯網技術的迅速發展，越來越多的移動設備(如智能手機、穿戴設備)對于帶寬與計算能力有了更多的無線網絡訪問需求。未來的移動設備將變得更加智能，而部署于移動設備上的應用將需要更多的計算能力和數據訪問[1]。然而，這些新型應用和服務的部署受到移動設備有限計算能力和電池容量的限制。雖然將數據饑餓型和計算密集型任務卸載至云端執行可以克服移動設備計算能力受限的弊端，但移動設備與云端間的無線網絡連接帶來的較長延時會導致延時敏感型應用的執行無法達到用戶的滿意[2]。

近年來，移動邊緣計算通過將計算節點部署于網絡邊緣的方式為用戶滿足延時敏感型任務的需求提供了低延時和高性能計算的保證[3,4]。邊緣云具備的優勢在于：1)比較移動設備的本地計算[5]，移動邊緣計算克服了移動設備的計算能力受限的不足；2)比較遠程云端計算[6]，盡管邊緣云部署范圍較小，且資源能力受限制，但可避免任務卸載至遠程云端的高延時問題。因此，移動邊緣計算可以在延時敏感和計算密集型任務的執行上得到更好的平衡。

當前移動邊緣計算中的卸載問題主要包括：頁面卸載，即邊緣緩存，頁面提供者將常用頁面緩存于邊緣云上，以降低用戶請求頁面時的延時和能耗[7-8]。相關研究中已有考慮頁面分布[9]和用戶移動性[10]的緩存策略。任務卸載，該問題即是決定何時、何地、多少任務應從移動設備卸載至邊緣上執行，以降低計算延時和節省能耗。該類研究中主要集中于考慮多用戶環境[11]和多服務器環境[12]下的卸載決策問題。頁面卸載主要關心邊緣云的存儲能力，不同步考慮計算能力。而在任務卸載的相關研究中，是以邊緣云具有足夠的軟硬件資源支持任務計算為常態假設的，這與邊緣云資源受限以及無法支持所有類型的任務是相違背的。

本文將設計更加實際且注重能效的移動邊緣計算卸載策略。首先引入任務緩存的概念，即將多次請求的任務及相關數據緩存于邊緣云的操作。由于任務同時需要存儲與計算資源，任務緩存需要同時考慮邊緣云的計算和存儲能力。在此基礎上，設計基于邊緣云的任務緩存與卸載聯合優化策略，目的是通過最優的任務緩存與卸載決策，實現滿足用戶延時需求的情況下最小化移動設備總能耗達到最小。

1 系統模型

系統目標是在滿足用戶延時需求的同時最小化移動設備的總體能耗，系統模型如圖1所示。

圖1 系統模型

移動設備擁有五個計算任務，每個任務擁有不同的請求次數(即任務分布不同)、數據量以及計算能力需求。以虛擬現實應用為例，其場景渲染任務擁有更多分布，會重復多次執行，而追蹤目標任務則擁有更大的數據量，需要更多的數據傳輸，而目標識別任務則需要更高性能的計算資源。通過任務緩存和卸載可以在滿足用戶延時需求的同時降低移動設備的能耗。對于在考慮任務異構和邊緣云資源受限的情況下實現最優的任務緩存和卸載，重點需要解決：1) 哪些任務需要緩存，即決定是否任務需要緩存于邊緣云上；2) 多少任務需要卸載，即決定多少任務在本地執行，多少任務在邊緣云上執行。

1.1 場景描述

移動邊緣計算場景由多個移動設備和一個邊緣云組成，假設移動設備(用戶)數量為N，計算任務數量為K，用戶n={1,2,…,N},任務k={1,2,…,K}，且假設用戶數量大于任務數量，即N≥K，這是由于某些計算任務具有更高的分布，使得這些任務需要重復請求并多次執行。假設任意用戶一次僅能進行一個任務請求，且不同用戶可根據其偏好進行同一任務的請求。定義un,k表示用戶n請求任務k，移動設備通過無線信道與邊緣云連接，邊緣云為擁有計算和存儲資源的小規模數據中心，計算資源為移動設備提供任務處理資源，存儲資源為任務代碼處理提供存儲資源。

對于異質計算任務，利用三元組定義計算任務模型，將用戶un,k定義為un,k={wk,sk,Dn}，wk表示任務un,k請求的計算資源數量，以每bit的CPU周期數表示，即完成該任務需要的CPU周期總數，sk表示任務un,k的數據量，單位為bit，Dn表示用戶n的任務完成截止時間。由于邊緣云計算和存儲能力受限，假設邊緣云的緩存大小和計算能力分別為ce和cs。

1.2 通信模型

令Hn表示用戶n與邊緣云間的信道增益，假設用戶在將任務卸載至邊緣云時不發生移動，則為常量。令Pn表示用戶n的移動設備的發送功率，則用戶n的上傳數據速率可定義為：

(1)

式中：σ2表示噪聲功耗，B表示移動設備與邊緣云間的無線信道帶寬。本文不考慮邊緣云處理后的數據下載延時，由于處理后的數據量通常遠小于任務處理前的數據量，且邊緣云至移動設備的下載速率是遠高于移動設備至邊緣云的上傳速率的。

1.3 計算模型

1) 本地任務計算的延時和能耗代價。

對于本地任務計算，定義fln為移動用戶n的CPU計算能力，則任務un,k的本地執行時間為：

(2)

單個CPU計算周期的能耗可表示為：ε=κf2，則在本地執行時的能耗代價為：

(3)

式中：κ表示能量因子，大小取決于CPU芯片工藝，本文在實驗中將該值設置為10-25。

2) 邊緣云計算的延時和能耗代價。

對于邊緣云上的任務計算，定義fcn為分配給用戶n的CPU計算能力，此時任務執行延時包括：(1) 移動用戶卸載任務的時間，即任務上傳時間Ttran,k；(2) 邊緣云執行任務的時間，即任務處理時間Tpron,k。因此，任務un,k在邊緣云上的處理延時為：

(4)

若任務卸載至邊緣云，移動設備的能耗僅為任務卸載時間通信能耗，因此，發送skbit的任務至邊緣云時的傳輸能耗代價為：

(5)

1.4 任務緩存模型

1.5 問題形式化

對于任務緩存問題，定義一個整型緩存決策變量xk∈{0,1}，表示任務k是否在邊緣云緩存，若是，xk=1；否則，xk=0。因此，任務緩存策略可表示為：x=(x1,x2,…,xk)。對于任務卸載問題，定義卸載決策變量an∈[0,1]，若an=1，則用戶n任務在本地執行，若an=0，則用戶n任務卸載至邊緣云執行，若an∈(0,1)，則用戶n的任務部分an在本地執行，任務部分1-an在邊緣云執行。因此，任務卸載策略可表示為：a=(a1,a2,…,an)。

基于以上定義，考慮任務緩存、任務的本地和邊緣云執行，用戶n任務kun,k的總執行延時為：

(6)

移動設備的能耗代價為：

(7)

算法目標是在確保服務質量的同時最小化移動設備的能耗代價，則問題可形式化為：

C3:Tn,k≤Dn?n∈N,k∈K

C4:xk∈{0,1} ?k∈K

C5:an∈[0,1] ?n∈N

(8)

式中：目標函數表明通過任務的緩存與卸載決策對移動設備的總能耗代價最小化，約束C1表明緩存任務的數據量不能大于邊緣云的緩存能力，約束C2表明卸載任務的總的資源請求不能大于邊緣云的計算能力，約束C3表明用戶n的任務執行需在截止時間前完成，約束C4表明任務緩存決策變量為二進制變量，約束C5表明任務是可分割的，可部分在本地執行，部分在邊緣云上執行。

2 能效任務緩存與卸載

本節求解以上的任務緩存與卸載決策最優化問題，考慮兩個子優化問題：1) 任務卸載問題：當給定任務緩存策略，即x=x0時，初始問題可轉變為關于a的凸最優化問題，可以通過內點法獲得最優解a*。2) 任務緩存問題：當a*固定時，該子優化問題可轉變為0-1整數規劃問題，可利用分支限界法獲得問題的最優解。以下將分別證明以上的結論。

1) 能效任務卸載。

定理：給定x=x0，式(8)中關于a的初始最優化問題為凸最優化問題。

證明：給定x=x0，目標函數變為a的函數。由于目標函數中的xkTpron,k與a無關，因此，可定義關于a的目標函數為f(a)，表示為：

(9)

進一步，式(8)關于a的最優化問題可重寫為：

C2:Tn,k≤Dn?n∈N,k∈K

C3:an∈[0,1] ?n∈N

(10)

其中，目標函數表示給定任務緩存策略時通過制定最優任務卸載決策得到能耗的最小化，約束C1表明卸載任務的總的資源請求不能大于邊緣云的計算能力，約束C2表明用戶n的任務執行需在截止時間內完成，約束C3表明任務是可分割的，可部分在本地執行，部分在邊緣云上執行，an本身是任務在本地執行的比例。

由于目標函數是線性的，且約束條件也均是線性的，故該最優化問題為凸最優化問題。證畢。

凸最優化問題即可利用內點法得到最優任務卸載策略a*，即通過求解一系列KKT條件的修改形式，在等式約束下得到最優解，求解方法可具體參見文獻[13]。

2) 能效任務緩存。

根據以上的討論，可能得到最優任務卸載策略a*。當a=a*時，目標函數可轉變為x的函數，可表示為：

(11)

進一步，式(8)關于x的最優化問題可表示為：

C2:Tn,k≤Dn?n∈N,k∈K

C3:xk∈{0,1} ?k∈K

(12)

其中，目標函數表示給定任務緩存卸載策略時通過制定最優任務緩存決策得到能耗的最小化，約束C1表明卸載任務的總的資源請求不能大于邊緣云的計算能力，約束C2表明用戶n的任務執行需在截止時間內完成，約束C3表明任務緩存決策變量為二進制變量，只有任務緩存或不進行緩存兩種選擇。

因此，目標函數可轉變為關于x的0-1線性規劃問題，利用分支限界法即可得到其最優解，具體過程如下：

(1) 分支步驟。該步驟中，計算任務集合被轉換為一棵樹，代表所有任務在本地或需要緩存的可能性組合。該樹由空節點的樹根開始構建，對于該父節點，每個任務的副本被連接為孩子節點，每個孩子節點代表在本地執行或云端緩存(標記為local或云端服務器編號)。類似地，下一任務節點的副本與樹結構的每一層上與孩子節點相連。重復以上過程直到所有任務被添加至樹結構中，該樹的每條分支即代表一個侯選的任務緩存決策解。

為了減少決策時間，將節點添加至樹結構中時，需要根據任務的能耗代價降序進行添加，這樣得到的樹中主分支將擁有更高的代價，這將使得分支步驟中可以提前遍歷對代價影響更大的節點，從而盡可能早地發現不可行的高代價分支，有利于修剪分支狀態，降低決策空間的搜索時間。

(2) 搜索步驟。該步驟由搜索分支步驟構建的樹、計算每條分支的代價和尋找最小代價分支組成。為了加快決策時間，搜索過程利用一個限界函數修剪樹結構中的某些非最優的分支。每條分支利用深度優先規則DFS計算其代價。同時，若分支的局部代價超過限界函數定義的限制值則修剪該分支。設計的限界函數以完全的本地執行或云端執行得到的能耗代價進行初始化。若一個分支被完整搜索而未被修剪，則將其考慮為當前的最優解，且其代價作為新的限界函數值。當所有分支被搜索后，算法返回最優解。

3 仿真實驗

3.1 實驗配置

考慮一個由邊緣云和移動設備組成的移動邊緣計算系統，移動設備擁有計算密集型任務和數據密集型任務執行需求，假設邊緣云部署于無線訪問點AP的附近，移動設備可通過無線信道將任務卸載至邊緣云執行。假設無線信道帶寬B=20 MHz，移動設備的發送功率Pn=0.5 W，對應的噪聲功耗σ2=2×10-13，無線信道增益Hn=127+30×logd，d表示用戶n與邊緣云間的距離。對于任務un,k，假設請求的計算能力wk和數據量sk由概率分布產生，分別服從正態分布和均勻分布。對于任務的分布，假設任務請求次數服從Zipf分布，同時，設置邊緣云和移動設備的計算能力分別為25 GHz和1 GHz。其他相關參數中，n=100，ce=500 MB，w服從均值為0.8(單個任務的CPU周期數)的均勻分布，s服從均值為100 MB的均勻分布。利用MATLAB進行實驗的驗證分析。

3.2 結果分析

1) 任務卸載影響 將本文提出的基于能效的任務緩存與卸載算法命名為TCO算法，并與以下算法進行性能比較：

緩存+本地執行算法，簡稱CLA。該算法根據本文提出的緩存策略對計算任務進行緩存，然后，未被緩存的任務僅在本地設備上執行，不被卸載至邊緣云處理。

緩存+邊緣云執行算法，簡稱CEA。與CLA不同，該算法中未緩存的任務全部卸載至邊緣云處理。

從圖2看出，TCO算法得到的能耗最低，說明應用最優的緩存部署和任務卸載可以有效降低移動設備的能耗。圖2(a)中，當任務數據量較小時，TCO和CEA的能耗差異較小，而任務數據量較大時，TCO和CLA的能耗差異較小。可以得出，在相同的任務計算能力請求下，當任務數據量較小時，任務應在邊緣云上處理更為有效。比較來說，若任務數據量較大，則任務應在本地執行較好。從圖2(b)可以得出，在相同的任務數據量下，當任務計算能力請求相對較小時，任務應在本地執行較好，而計算能力請求較大時，則在邊緣云執行較優。

(a)任務數據量變化

(b) 任務請求計算能力變化圖2 任務卸載的影響

2) 任務緩存影響 觀察兩種情況下的能耗狀況：任務不被緩存和任務緩存，如圖3所示。當任務被緩存時，移動設備的能耗低于不緩存時的能耗，說明計算任務緩存可以降低能耗。還可以看出，任務數據量越大，計算能力請求越高，能耗將越高。

(a) 任務數據量變化

(b) 任務請求計算能力變化圖3 任務緩存影響

為了評估緩存策略對結果的影響，將TCO與以下算法進行比較：

任務盡力緩存與卸載算法，簡稱TPO。對于邊緣云，它將最大限度地緩存計算任務直到達到邊緣云的緩存能力。

任務隨機緩存與卸載算法，簡稱TRO。邊緣云隨機地進行任務緩存，直到達到邊緣云的緩存能力。

任務有限緩存與卸載算法，簡稱TFO。邊緣云的緩存能力初始設置為空，迭代式增加一個任務至緩存以最小化總能耗，直到達到邊緣云的緩存能力。

由圖4可知，TCO是最優的，TRO相對較差，這是由于隨機緩存策略沒有考慮任務請求數量的原因導致，且該算法在進行任務緩存時也無法考慮任務計算量和計算任務的數據量。TPO僅考慮了任務請求數量，沒有考慮任務數據量和任務計算量，TFO在一定程度上考慮了以上三個量。從圖4(a)還可以看到，邊緣云的緩存能力越大，能耗將越小，這是由于緩存能力越大，緩存任務越多，能耗將降低。從圖4(b)和(c)可以看出，任務數據量對算法的影響要弱于計算能力對算法的影響。

(a) 邊緣云緩存大小變化

(b) 任務數據量變化

(c) 任務請求計算能力變化圖4 任務緩存的影響

4 結 語

移動邊緣計算環境中，延時敏感型應用任務的執行不僅需要滿足用戶時延的約束，還需要考慮移動設備端的能耗問題。為了解決這一問題，基于移動邊緣計算環境提出了一種融入任務緩存機制的任務卸載策略。不同于常規的邊緣計算僅僅關注計算卸載決策問題，該策略設計了一種基于邊緣云的任務緩存機制，降低了重復的任務需求執行時的卸載延時。此外，策略將計算與存儲能力受限的邊緣云中的任務緩存與卸載優化決策問題形式化為混合整數規劃問題，并對其進行了求解。實驗結果證明，帶有緩存機制的任務卸載策略在動態異構的任務執行環境下可以實現更好的能效優化。進一步的研究將集中于面向多個邊緣云的任務卸載環境，在任務緩存與卸載的邊緣云資源的選擇上作出優化。