移動邊緣計算中數據緩存和計算遷移的智能優化技術

汪海霞 趙志峰 張宏綱

摘要：針對移動邊緣計算（MEC），設計了計算遷移和數據緩存的聯合優化模型，并基于改進的遺傳算法（GA）對該模型的時延優化特性進行了優化。仿真表明：提出的方案比傳統方案更能有效地降低用戶請求的時延，對移動邊緣網絡的部署和應用具有一定的參考意義。

關鍵詞： 移動邊緣計算；計算遷移；數據緩存；遺傳算法

Abstract： In this paper， a combined optimization model for computing migration and data caching is designed. Particularly， an improved genetic algorithm （GA） is put forward to analyze the time delay optimization of the proposed model， which surely has certain significant values to the deployment and applications of mobile edge network.

Key words： mobile edge computing； computation offloading； data caching； genetic algorithm

隨著移動互聯網和物聯網（IoT）的快速發展以及各種新型業務（如虛擬現實（VR）、增強現實（AR）和視頻會議等）的不斷涌現[1]，用戶對網絡服務質量（QoS）的要求越來越高。因此，為了有效解決移動互聯網發展帶來的高負荷、低時延等要求的挑戰，移動邊緣計算（MEC）概念得以提出，并得到了學術界和產業界的廣泛支持，被認為是下一代網絡的關鍵技術之一[2-6]。

通過將相關的計算任務和請求數據遷移到近端（本地）MEC服務器上，可以減少網絡設備能耗和傳輸時延，并大大提高用戶體驗。一般來說，計算遷移的關鍵技術就是充分利用MEC的優點（比如：縮短執行時延，降低能耗等），為此業務卸載過程決定合適的決策過程。文獻[7]的工作表明：將MEC與云計算相結合可以減少遷移任務的相關時延。文獻[8]中，作者認為可以通過最小化任務的執行時延來實現最佳的遷移決策。在文獻[9]中，作者提出了一種通過最小化能耗來進行決策的方法，其中優化問題被表述為一定約束條件下的馬爾可夫決策過程（MDP）。此外，文獻[10]和[11]分別分析了移動終端的能量消耗與多用戶系統的相關時延間的關系。在文獻[12]中，作者考慮在單個宏小區的微基站（BS）上進行數據緩存，通過最小化宏基站服務的請求數量來優化緩存方案。文獻[13-18]中，作者也都研究分析了基站緩存中的存儲分配問題。

雖然MEC具有較強的計算和數據傳輸能力，但相對于現在急速增加的移動終端數量與業務，MEC的相關資源仍然十分有限。本文基于MEC與數據中心（DC）的相互配合機制，根據排隊理論分析了每個任務的平均執行時延[19]，然后提出了一定緩存空間約束下的時延最小化問題，并通過改進的遺傳算法解決該優化問題，從而有效降低了用戶請求時延，提高了緩存性能和效率。

1 系統模型

如圖1所示，MEC系統有B個BS（每個BS配備有一個MEC服務器）和M個用戶設備（UE）。在這里我們可以把MEC服務器看作是一個具有計算和存儲能力的小型數據中心，通過部署與邊緣交換機關聯的虛擬機，將相關的計算任務遷移在MEC服務器上，也可以將用戶所請求的內容數據緩存在MEC服務器上。假設來自UE的業務請求的到達過程遵循泊松分布，則UE i的請求速率被表示為[λi]。[ci]為UE i所請求的計算任務，[di]表示UE i所要訪問的數據量，[εj]表示MEC服務器j的數據緩存容量。把BS覆蓋范圍內每個UE當做M / M / 1排隊系統進行處理，則MEC服務j和UE i的服務速率分別可以定義為[μj]和[θj]。

通常情況下，移動終端發送請求，然后由BS接受處理或將請求發送往遠程云端進行處理，這個過程涉及BS和云，以及UE和BS之間的傳輸。為了簡單起見，將BS與云之間傳輸的單位時延表示成[eMC]，將UE與BS傳輸過程中的單位時延表示為[eUM]。用變量[xij]表示服務器 j是否緩存了用戶i 所請求的內容，如果服務器內緩存了用戶請求的內容，則變量[xij]為1，否則為0。同樣地，如果將用戶i產生的計算任務遷移到MEC 服務器j上進行處理，變量[yij]為1；反之，若進行本地處理，則為0。

以上是對用戶產生的計算任務，在不同的處理方式下計算的執行時延。對于在數據傳輸過程中產生的傳輸時延，如果MEC服務器緩存了用戶所請求的數據，則用戶和服務器之間的傳輸時延表示為[TUMi=j∈BeUMyijci+di]；若服務器緩存中沒有用戶所請求的內容數據，則服務器和數據中心之間傳輸數據所得的時延為[TMCi=j∈BeMC1-xijdi]，其中[1-xij=0]意味著用戶所請求的內容緩存在服務器里，而無需訪問數據中心。

其中，約束條件（4）限制了緩存在服務器的數據總量不應該超過服務器的總容量。其他的約束條件上文都有提到，不再贅述。

2 改進的遺傳算法

遺傳算法（GA）[20]是模擬自然界生物進化過程與機制求解優化問題的一類自適應的啟發式智能搜索算法。該算法通過將初始個體進行選擇、交叉和變異等操作來更新種群。其最主要的特征是種群搜索策略和種群個體之間的信息交換，非常適用于處理傳統方法不容易解決的非線性以及復雜的問題，其應用領域非常廣。模擬退火算法（SA）[21]是一種貪心算法，它在搜索過程中加入了隨機因子，并且以一定的概率來接受比較差的解，這樣就有可能會避免陷入局部最優。

為了更加有效地解決上述優化問題，與傳統的遺傳算法相比，我們提出了如下改進遺傳算法（算法1）：

（1）在交叉過程中，對新的種群進行了模擬退火操作，使得一些適應值較低的個體也有一定的概率遺傳到下一代，這樣可以有效防止算法收斂到局部最優，并使算法更加穩定。

（2）在種群進行交叉操作和變異操作之后，分別計算新種群里面個體的適應度函數。這樣就可以防止一些優秀的個體在種群進化過程中被遺棄掉。

在改進的算法1中，種群個體是指上述優化問題中的變量[xij，yij]，即前M維的值為[xij]的取值，后M維的值為[yij]的取值，所以個體是一個用0和1填充的[2×M]維的向量。值得注意的是：在所改進的算法中給出的可行解都滿足約束方程（4）、（5）和（6），適應度函數就是所要優化的目標函數。

3 仿真設計與分析

為了評估本文提出的基于改進遺傳算法的聯合計算和緩存優化方法，我們將其與其他兩種策略進行了性能對比：一種是不考慮邊緣的計算和存儲資源的傳統策略，即本地執行所有的計算任務并且所有請求的數據都存儲在數據中心；另一種是隨機策略，它雖然考慮了移動邊緣網絡的相關資源，但采用隨機方式來決定是在終端還是在服務器上執行計算任務，并且數據也是隨機存儲在邊緣服務器或數據中心。隨機策略在一定程度上犧牲了服務質量，從而降低了數據緩存過程的復雜性。

在仿真過程中，除非文中明確說明，否則所有主要參數值均基于表1進行設置。

圖2描述了當用戶數M = 200時，在不同策略下總時延隨著服務器緩存容量（從500增加到3 500）的變化關系。可以觀察到傳統策略完全不受服務器緩存容量的變化，當緩存容量從500增加到1 000時，我們提出的策略的總時延從510.2 ms急劇下降到320.1 ms。這是由于隨著服務器的緩存容量的增加，通過改進的遺傳算法的自適應調節使得數據傳輸時間變短。但當容量達到一定的閾值之后，由于用戶請求數量是一定的，所以總時延減少的較為緩慢。

圖3描述了當用戶數M從50增加到400時，不同策略的總時延變化情況。我們可以觀察到：與其他策略相比，我們所提出的策略實現了較低的延遲，并且可以減少超過50%的執行延遲。特別是當用戶數量很少時，邊緣服務器有足夠的資源用較少的時間來處理大部分任務。隨機策略利用了邊緣網絡的計算和存儲資源，因此其性能優于傳統策略。另外，不同策略下的總時延間的差距也隨著用戶數目的增加而增大，意味著當MEC系統的規模較大時，所提出的策略具有較大的性能提升。這是由于提出的策略可以根據用戶請求數據大小的不同來提前緩存，從而使得數據的傳輸時延較低。

4 結束語

在MEC中，計算遷移和數據緩存是很重要的特性，緩存決策策略的優劣直接影響移動邊緣計算系統的性能。本文中我們通過聯合分析執行時延和傳輸時延，用改進的遺傳算法來建立優化的計算遷移和數據緩存模型，有效提高了緩存空間的使用效率，性能方面也有較大程度的提升。

參考文獻

[1] MACH P， BECVAR Z. Mobile Edge Computing： A Survey on Architecture and Computation Offloading [J]. IEEE Communications Surveys & Tutorials， 2017， （99）： 1-1

[2] WANG X， CHEN M， TALEB T， et al. Cache in the Air： Exploiting Content Caching and Delivery Techniques for 5G Systems [J].IEEE Communications Magazine， 2014， 52（2）：131-139. DOI： 10.1109/MCOM.2014.6736753

[3] European Telecommunications Standards Institute （ETSI）. Mobile Edge Computing Introductory Technical White Paper[R]， 2014

[4] HU Y C， PATEL M， SABELLA D， et al. Mobile Edge Computing： A Key Technology towards 5G[J]. ETSI White Paper， 2015，11（11）：1-16

[5] KUMAR K， LIU J， LU Y H， et al. A Survey of Computation Offloading for Mobile Systems[J].Mobile Networks and Applications， 2013，18（1）：129-140

[6] BASTUG E， BENNIS M， DEBBAH M. Living on the Edge： The Role of Proactive Caching in 5G Wireless Networks[J]. IEEE Communications Magazine， 2014， 52（8）：82-89.DOI： 10.1109/MCOM.2014.6871674

[7] RIMAL B P， VAN D P， MAIER M. Mobile-Edge Computing vs. Centralized Cloud Computing in Fiber-Wireless Access Networks[C]//2016 IEEE Conference on Computer Communications Workshops （INFOCOM WKSHPS）. USA：IEEE，2016： 991-996

[8] LIU J， MAO Y， ZHANG J， et al. Delay-Optimal Computation Task Scheduling for Mobile-Edge Computing Systems[C]//2016 IEEE International Symposium on Information Theory （ISIT）.USA：IEEE， 2016： 1451-1455. DOI： 10.1109/ISIT.2016.7541539

[9] KAMOUN M， LABIDI W， SARKISS M. Joint Resource Allocation and Offloading Strategies in Cloud Enabled Cellular Networks[C]//2015 IEEE International Conference on Communications （ICC）.USA：IEEE， 2015： 5529-5534

[10] JIANG Z， MAO S. Energy Delay Tradeoff in Cloud Offloading for Multi-Core Mobile Devices[J].IEEE Access， 2015， 3：2306-2316. DOI： 10.1109/ACCESS.2015.2499300

[11] KWAK J， KIM Y， LEE J， et al. Dream： Dynamic Resource and Task Allocation for Energy Minimization in Mobile Cloud Systems[J].IEEE Journal on Selected Areas in Communications， 2015， 33（12）：2510-2523. DOI： 10.1109/JSAC.2015.2478718

[12] POULARAKIS K， IOSIFIDIS G， TASSIULAS L. Approximation Algorithms for Mobile Data Caching in Small Cell Networks[J].IEEE Transactions on Communications， 2014， 62（10）：3665-3677. DOI： 10.1109/TCOMM.2014.2351796

[13] GU J， WANG W， HUANG A， et al. Proactive Storage at Caching-Enable Base Stations in Cellular Networks[C]//2013 IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications （PIMRC）. USA：IEEE， 2013：1543-1547. DOI： 10.1109/PIMRC.2013.6666387

[14] BASTU E， BENNIS M， KOUNTOURIS M， et al. Cache-Enabled Small Cell Networks： Modeling and Tradeoffs[C]// Wireless Communications Systems （ISWCS）， 2014 11th International Symposium on.USA：IEEE， 2015.DOI： 10.1109/ISWCS.2014.6933434

[15] BLASCO P， GUNDUZ D. Learning-Based Optimization of Cache Content in A Small Cell Base Station[C]//2014 IEEE International Conference on Communications （ICC）. USA：IEEE， 2014：1897-1903. DOI： 10.1109/ICC.2014.6883600

[16] GOLREZAEI N， SHANMUGAM K， DIMAKIS A G， et al. Femtocaching： Wireless Video Content Delivery through Distributed Caching Helpers[C]// Proceedings of IEEE INFOCOM 2012.USA：IEEE， 2012： 1107-1115.DOI： 10.1109/TIT.2013.2281606

[17] POULARAKIS K， IOSIFIDIS G， SOURLAS V， et al. Multicastaware Caching for Small Cell Networks[C]//2014 IEEE Wireless Communications and Networking Conference （WCNC）. USA：IEEE， 2014：2300-2305.DOI： 10.1109/WCNC.2014.6952688

[18] POULARAKIS K， IOSIFIDIS G， TASSIULAS L. Approximation Caching and Routing Algorithms for Massive Mobile Data Delivery[C]//2013 IEEE Global Communications Conference （GLOBECOM）.USA： IEEE， 2013. DOI： 10.1109/GLOCOM.2013.6831621

[19] COOPER R B. Introduction to Queueing Theory[M]. New York： North Holland， 1981

[20] DAVIS L. Handbook of Genetic Algorithms[R]. Van Nostrand Reinhol， 1991

[21] KIRKPATRICK S， GELATT C D， VECCHI M P， et al. Optimization by Simulated Annealing[J]. Science， 1983， 220（4598）：671-680