汪海霞 趙志峰 張宏綱

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

關(guān)鍵詞： 移動邊緣計算；計算遷移；數(shù)據(jù)緩存；遺傳算法

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

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

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

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

1 系統(tǒng)模型

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

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

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

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

2 改進的遺傳算法

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

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

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

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

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

3 仿真設計與分析

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

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

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

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

4 結(jié)束語

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

參考文獻

[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