汪海霞 趙志峰 張宏綱

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

關(guān)鍵詞： 移動(dòng)邊緣計(jì)算；計(jì)算遷移；數(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

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

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

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

1 系統(tǒng)模型

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

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

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

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

2 改進(jìn)的遺傳算法

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

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

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

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

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

3 仿真設(shè)計(jì)與分析

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)

[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