基于主動緩存的云邊端協同卸載策略

張蘇豫，江凌云

(南京郵電大學 通信與信息工程學院，江蘇 南京 210003)

0 引 言

隨著移動設備(MDs)和移動通信技術的發展，出現了越來越多的計算密集和延遲敏感的應用程序。如果MDs在本地執行這些計算任務，由于移動設備有限的計算能力，將消耗大量的能量同時產生很大的延遲。為了解決這個問題，移動云計算(MCC)應運而生。它通過將計算任務轉移到云端，可以緩解移動終端的能耗問題。但由于用戶與云端之間的距離較遠，可能會引起網絡抖動[1]和較長的延遲，不能滿足延遲敏感的應用程序的需求。因此，移動邊緣計算(MEC)被提出，以解決MCC在計算卸載方面的不足。由于邊緣服務器被部署在無線網絡的邊緣，相對于云端距離用戶更近，因此數據傳輸延遲大大降低。近年來，邊緣服務器的緩存能力也受到了學術界和工業界的廣泛關注。由于邊緣服務器可以同時提供計算和存儲功能[2]，一些研究考慮將緩存和計算卸載結合起來以進一步提高系統性能。

最近的一些研究通過部署云端和邊緣服務器形成一個三層的邊緣計算架構。每個任務都可以在邊緣服務器、云端或本地處理。將任務卸載到邊緣服務器或云端將不可避免地產生額外的通信延遲，而在本地執行任務可能導致更大的計算延遲。所以，移動用戶在三層計算架構中針對不同的計算需求做出正確的卸載決策是至關重要的。以前的許多研究表明，來自鄰近社區的任務請求中有相當一部分是相同的。如果所有重復的任務請求都被計算一次，將會導致計算資源和網絡資源的巨大浪費和嚴重的網絡擁塞。為了避免這種情況，有必要找到一種有效的緩存算法來解決任務的重復請求問題。在網絡邊緣(如網關、基站和終端用戶設備)緩存流行內容可以避免重復計算，因此會大大減少延遲[3]，從而提高用戶體驗質量。目前主流的緩存方案為內容緩存和任務結果的主動緩存。與內容緩存不同，任務結果的主動緩存是根據當前用戶的計算請求進行實時調整的，而不是預先放置在服務器中。因此，它可以大大提高緩存命中率，減輕計算負擔并提高卸載效率。

1 相關工作

在移動邊緣計算中，已經提出了一些任務計算結果緩存策略。文獻[4]提出整數規劃，以確定將哪些計算任務集中緩存到MEC服務器，哪些不緩存到MEC服務器。文獻[5]采用智能優化算法，設計了MEC服務器和云端聯合下的計算分流和數據緩存模型。將資源約束延遲最小化問題轉化為優化問題，提出了一種基于遺傳算法和模擬退火算法的啟發式算法。文獻[6]提出了多用戶場景下移動邊緣計算的緩存增強方案(OOCS)和最優卸載，分別最小化整體執行延遲。此外，還出現了許多策略和架構，如基于博弈論的文獻[7]和基于MVR的文獻[8,9]，他們都以減少MDs的響應延遲和能耗為目標。在多用戶卸載場景中，緩存問題、資源分配和云協作通常是相關的。文獻[10]聯合考慮了分流、內容緩存和資源分配，以最大限度地提高整體網絡收益。文獻[11]研究了支持全雙工(FD)的小蜂窩網絡中的內容緩存和計算卸載。文獻[12]通過結合計算分流和數據緩存來優化調度計算請求，以最小化總延遲。文獻[13]考慮了異構云場景中任務卸載的靈活調度策略，其中MEC服務器和云端可以協作處理具有不同延遲需求的應用程序。

但是以上提出的緩存算法和計算卸載算法只適用于單一MEC服務器或單目標函數場景，而且沒有考慮到任務流行度的動態變化。因此本文首先提出多MEC服務器和云端聯合緩存算法，在此基礎上用線性回歸模型進行任務預測，找出最優的云邊端協同卸載方案，最小化總時延。

2 云邊端協同卸載策略

本節首先給出了邊緣計算系統結構，然后提出了多MEC服務器與云端聯合的主動緩存算法，在此基礎上介紹了用于任務預測的線性回歸模型，最后給出了基于上述主動緩存算法的云邊端協同卸載策略。

2.1 系統結構

圖1給出了邊緣計算系統結構，它由云端、MEC服務器和多個移動設備組成。MEC服務器和云端通過有線回程鏈路連接，而MEC服務器和移動設備通過無線鏈路連接。首先，將一個復雜的計算任務按優先級或QoS級別進行粒度劃分，劃分成多個子任務，每個子任務可以被卸載到適當的節點。移動用戶可以選擇在本地計算任務，也可以選擇從MEC服務器和云端直接獲取已經緩存的任務結果，或者將任務轉移至MEC服務器和云端進行計算。

圖1 系統結構

2.2 主動緩存算法

本節提出的主動緩存算法，是云邊端協同卸載策略(CEECO)的核心。由于MEC服務器的緩存能力有限，但傳輸延遲小；而云有足夠的緩存能力，但傳輸延遲大。所以我們利用云端和MEC服務器的聯合緩存來確定任務結果的最佳緩存狀態。我們假設在每個時隙中，所請求的計算任務服從Zipfs分布，我們定義第i個計算請求任務結果為Reqi，i∈N，該計算任務歷史總請求次數為nReqi，近一周內的請求次數為nWeeki。每個MEC服務器都會通過一個計數器記錄所有計算任務的歷史總請求次數和近一周內的請求次數。假設MEC服務器緩存的任務結果集合為Ωe,云緩存的任務結果集合為Ωc。一開始Ωe和Ωc都為Φ。提出的緩存算法分為3個階段。

第一階段：MEC服務器的存儲空間沒有被填滿。一些MDs將計算任務卸載到MEC服務器進行計算，MEC服務器計算完成后將任務結果緩存下來，同時記錄每個任務歷史總請求次數和近一周內請求次數，它們決定了該任務的流行度。隨著計算任務的逐漸增加，進入下一階段。

第二階段：此時MEC服務器存儲空間已滿。如果新請求的任務具有更高優先級排名，那么已經緩存的任務結果將被新請求的任務結果替換掉。簡單來說，流行度越高，任務結果占用存儲空間越小，則優先級越高。比較后刪除優先級最低的任務結果，并將該任務結果告知云端，然后進入下一階段。

第三階段：云端處理被MEC服務器刪除的任務結果。如果云端緩存中沒有被MEC服務器刪除的任務結果，則將它緩存下來，否則丟棄。該算法的具體流程如圖2所示。

圖2 主動緩存算法流程

具體的算法如下所示：

算法1：主動緩存算法

(1)Initialize Ωe= Φ,Ωc= Φ,

(2)for i = 1： |N| do

(3)MEC gets Reqiby Zipf popularity;

nReqi=nReqi+1;

(4) if there is Reqiin Ωethen

(5) delete Reqi；

(6) else

(7) if Ωeis not full,then

(8) Reqi→Ωe；

(9) else

(10)Rank nReqiand nWeekiin descending order respectively,

(11) TotalRank=Rank(nReqi)+Rank(nWeeki);

(12) if exists a task na∈Ωe, with lower TotalRank than Reqior with same TotalRank as Reqibut larger than nReqithen

(13) Reqi→ Ωe;

(14) if no nain Ωcthen

(15) na→Ωc；

else

(16) delete na;

(17) else

(18) if no Reqiin Ωcthen

(19) Reqi→Ωc;

(20) else

(21) delete Reqi;

(22)end for

(23)Output Ωe，Ωc

2.3 云邊端協同卸載策略

2.3.1 任務預測

我們準備用訓練好的線性回歸模型對任務計算時間進行預測。線性回歸是一種對因變量y和自變量x之間的關系進行建模的監督學習方法，它利用線性預測函數建立線性回歸方程，是第一個被廣泛研究和應用的回歸技術。當自變量x1,x2,x3,x4的值與因變量y的值密切相關時，可以用線性回歸模型具體地描述他們之間的關系。在我們的模型中，輸入為T_CPU，T_Mem，M_CPU，M_Mem，輸出為Time(s)。

T_CPU，T_Mem表示處理任務所需的CPU和內存資源。M_CPU，M_Mem表示一個處理器(MEC，云或本地)當前所擁有的CPU和內存資源。Time(s)為任務計算時間。具體的模型建立過程見第三節。

2.3.2 卸載策略

基于以上提出的主動緩存算法，我們得出了5種云邊端卸載執行策略。每種策略的總延遲由計算延遲和傳輸延遲相加得到。其中計算延遲均由線性回歸預測模型預測得到。計算卸載參數見表1。

表1 計算卸載參數

(1)MEC緩存模型：我們將MEC服務器的緩存向量定義為Y={y1,>y2,>…,>yN}，其中yi∈{0,1}。如果yi=1，則表示MEC服務器已經緩存了第i個任務結果并直接傳輸給MD，否則yi=0。此外，由于MEC服務器的傳輸功率遠大于MD，而任務結果大小遠小于任務本身的大小，可以忽略無線下行鏈路上的傳輸延遲。因此，我們認為MEC緩存模型的總延遲為0。

(2)云緩存模型：云緩存向量為X={x1,>x2,>…xN}，其中xi∈{0,1}。xi=1表示云端已經緩存了第i個任務結果并傳輸給MEC服務器，然后MEC服務器通過無線下行鏈路傳輸給MD；否則xi=0?？紤]到云與基站之間的距離較長，回程延遲是不容忽視的。

云緩存模型總延遲由式(1)得到

(1)

(3)本地計算模型：本地計算向量定義為α={α1,α2,>…,>αN}，αi∈{0,1}。如果αi=1，表示在本地執行第i個計算任務，否則αi=0。由于沒有傳輸延遲，本地計算模型總延遲TLocal直接由線性回歸模型預測得到。

(4)MEC計算模型：MEC計算向量定義為β={β1,β2,>…βN}，βi∈{0,1}。如果βi=1，表示在MEC服務器計算第i個計算任務，否則βi=0。MEC計算模型總延遲(Tc_MEC)由線性回歸模型預測得到。

MEC計算模型總延遲由式(2)得到

(2)

(5)云計算模型：云計算向量定義為θ={θ1,θ2,…,θN}，θi∈{0,1}。如果θi=1，表示在云上計算第i個計算任務，否則θi=0。云計算延遲(Tc_CLOUD)由線性回歸模型預測得到。

云計算模型總延遲由式(3)得到

(3)

第i個計算任務的執行延遲可以簡化為

綜上所述，卸載策略為：

(1)當MEC服務器緩存了當前任務的計算結果(yi=1)，直接從MEC服務器獲取任務結果，此時時延近似為0，這是優先級最高的方案。

(2)當MEC服務器沒有緩存當前任務的計算結果(yi=0)，但是云端緩存了任務結果(xi=1)，此時比較本地計算任務、將任務卸載到MEC服務器進行計算、直接從云端緩存獲取任務結果的時延，取最小時延方案。其中本地計算和卸載到MEC服務器進行計算的時延通過訓練好的線性回歸模型預測得到。

(3)當MEC服務器和云端都沒有緩存當前任務的計算結果(yi=0，>xi=1)，此時比較本地計算任務、將任務卸載到MEC服務器進行計算、云端計算的時延，并取最小時延方案。三者的時延都可以通過訓練好的線性回歸預測模型預測得到。

3 評 估

本節對提出的算法進行了仿真。先利用數據集訓練并驗證了線性回歸預測模型的有效性，再將主動緩存算法(ACA)與其它緩存算法進行對比，結果顯示了ACA算法有著更小的任務響應時延。最后，將提出的基于主動緩存算法的云邊端協同卸載策略(CEECO)與其它相關卸載策略進行對比，結果顯示CEECO有著更好的時延優化。

3.1 線性回歸預測模型的有效性

3.1.1 訓練數據收集

為了準確預測每個子任務的處理時間，我們使用Google-cluster-2011-2數據集跟蹤訓練我們的線性回歸模型，該數據集是在一個擁有大約12.5 k個云節點的集群上收集的，時間跨度為2011年5月以來的29天，是進行任務調度研究常用的數據集。雖然是以前的數據集，服務器性能在不斷提高，但是只要衡量服務器性能的單位保持一致，就不影響訓練模型的正確性。為了方便處理，首先我們對數據進行歸一化。部分訓練數據見表2。

表2 訓練數據

T_CPU，T_Mem通過查閱數據集中《任務事件表》的“所需CPU核心資源”和“所需內存資源”字段得到。他們都是通過程序分析得到。

M_CPU，M_Mem通過查閱數據集中《處理器事件表》的“資源：CPU”，“資源：內存”字段和云端資源監視器監控的處理器當前負載百分比聯合得到。最后，Time(s)是某節點當前狀態下執行某任務的時間，這個數據可以由《任務資源利用表》中“任務計算起始時間”和“任務計算終止時間”字段得到。利用這些數據，我們訓練了一個線性回歸模型。

3.1.2 模型訓練

我們選取了2000組數據進行訓練，并隨機選出一個預測值與標簽值進行對比。訓練環境為python 3.5 Tensorflow and Keras。模型訓練參數見表3。

表3 模型訓練參數

模型訓練結果如圖3所示。

圖3 預測模型結果

MSE(均方損失)為0.0183，說明擬合效果比較理想。圖中W為權重矩陣。可知執行任務時延與T_CPU，T_Mem正相關，與M_CPU，M_Mem負相關，與實際情況相符合。

綜上所述，我們提出的線性回歸預測算法準確率高，與實際執行時延相差很小。

3.2 云邊端協同卸載策略(CEECO)的性能評估

3.2.1 主動緩存算法的有效性

在本節中，我們將通過實驗仿真首先來驗證所提主動緩存算法的有效性。隨機生成20個MDs和5個MEC服務器，同時包含一個遠程云服務器。每個MD請求的計算任務來自固定子任務集k。該任務集中子任務文件的大小服從高斯分布，(平均值,方差)為(10,2)MB。子任務文件的流行度符合Zipf分布[14]。每個MEC服務器都有100 MB緩存空間。為了進行比較，我們引入了3個基準緩存算法：任務流行緩存算法(TPC)、最優任務緩存算法(OPTC)和遠程云緩存算法(RCSR)。

最優任務緩存算法(OPTC): MDs請求的所有子任務結果都緩存到其訪問最頻繁的MEC服務器中，即MD可以直接從MEC服務器獲取相應的子任務結果，即所有的子任務請求都可以獲得最低的延遲響應，這是一種理想狀態。

任務流行緩存算法(TPC)：不考慮其它影響因素，所有的MEC服務器都緩存流行度最高的子任務結果。在這種情況下，任務流行度是唯一的影響條件，同時也忽略了流行度不高的子任務。

遠程云緩存算法(RCSR)：只有遠程云緩存所有子任務結果，MEC服務器不緩存任何子任務結果。

圖4顯示了所利用的MEC服務器緩存空間與子任務平均響應時間之間的關系。總的來看，所利用的服務器緩存空間越大，子任務的響應時間越短。因為隨著緩存越來越滿，子任務請求就越容易命中。當緩存空間固定時，我們需要合理地將子任務結果部署到邊緣服務器和云端，以提高子任務的命中率，減少子任務的響應時間。由于OPTC意味著所有子任務請求總是以最佳方式完成，所以性能也與MEC服務器的緩存空間無關。從圖4可知，在這種情況下，子任務響應延遲始終保持在0.25 s以下。RCSR只在遠程云中緩存最流行的子任務結果，傳輸延遲大，所以會造成最大的響應延遲。TPC的響應延遲約為1.5 s，提出的主動緩存算法(ACA)的性能總是優于TPC。而當緩存空間足夠大時，ACA算法性能幾乎和OPTC一樣。

圖4 子任務響應時間隨緩存空間的變化

這是因為：①我們提出的主動緩存算法屬于動態緩存算法，將最流行的子任務結果優先緩存到MEC服務器，傳輸延遲小。同時又考慮了子任務結果大小對緩存空間的影響。②由于MEC服務器的緩存空間有限，我們還結合了云端緩存，云端有充足的緩存空間，所以基本覆蓋最近流行的所有子任務，特別是流行度不高但仍然有訪問量的子任務。

3.2.2 云邊端協同卸載策略的性能評估

在本節中，我們將通過實驗仿真來評估基于上述主動緩存算法的云邊端協同卸載策略(CEECO)的性能。同樣隨機生成20個MDs和5個MEC服務器，同時包含一個遠程云服務器。仿真時將CEECO與隨機卸載策略和本地計算做對比，對比結果如圖5所示?？梢钥吹奖镜赜嬎愕目傃舆t最大，總延遲隨著需要處理的子任務數量呈線性增長。這是因為客戶端設備計算能力小，基本一直處于滿負載狀態，所以只能一個一個串行完成。在子任務數量不多的情況下，隨機卸載策略的總延遲和CEECO相差不大，但是隨著等待處理的子任務數量增多，隨機卸載策略的總延遲增長速度越快，這是因為隨機卸載策略沒有考慮到設備的實時負載情況，將子任務卸載給滿負載狀態的設備會造成更多的等待時延。而由于CEECO實時監測上下文信息(設備的負載狀態、信道條件)，所以總能做出最優的卸載選擇，表現是最好的。另外，由于一開始預測過程耗費的時延不可忽視，以及緩存還沒滿未達到最佳緩存狀態，所以與隨機卸載策略相比優勢并不明顯。但是隨著子任務數量的增多，每個子任務的處理幾乎都能選擇時延最小的方案，總時延表現相對其它策略優勢越來越大。

圖5 總延遲隨子任務數量的變化

4 結束語

隨著物聯網的飛速發展，新興的應用比如AR、VR對時延要求很高，而且當下很多任務卸載存在重復計算問題。解決這些問題，首先提出了一個云端和MEC服務器聯合的主動緩存算法，以確定任務結果的最佳緩存狀態。該算法是考慮到任務流行度的動態緩存算法。我們將該算法與現在流行的任務結果緩存算法作比較，結果表明我們提出的主動緩存算法時延響應更低。在此基礎上，我們訓練了線性回歸模型進行任務預測，結果驗證了該模型的有效性。最后，提出了基于上述主動緩存算法的云邊端協同卸載策略(CEECO)來解決資源分配和任務執行模式的選擇問題。仿真驗證了所提出策略的最優性和有效性，與隨機卸載策略和本地計算相比時延收益最好。并且隨著執行的子任務數量增多，累積的時延收益越來越大。

未來，我們將繼續探索優化任務緩存算法和卸載策略，比如通過增加訓練數據樣本來繼續優化預測模型，進一步完善主動緩存算法，以實現更小的應用程序執行時延。