王 錦

邊緣云計(jì)算中聯(lián)合緩存和路由策略優(yōu)化研究

王 錦

（安徽電子信息職業(yè)技術(shù)學(xué)院 信息與智能工程系，安徽 蚌埠 233000）

邊緣云計(jì)算能夠?yàn)闊o線用戶提供云服務(wù)，同時不會造成較大的通信延遲。針對邊緣云計(jì)算中聯(lián)合服務(wù)緩存和請求路由的問題，提出一個兩階段的優(yōu)化框架。該框架在存儲、通信、計(jì)算和預(yù)算約束下共同優(yōu)化服務(wù)的緩存和請求路由。通過將該聯(lián)合問題轉(zhuǎn)化為集合函數(shù)優(yōu)化，設(shè)計(jì)了高效的多項(xiàng)式時間算法。最后采用真實(shí)的數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明，本算法的性能接近最佳的性能。

邊緣云計(jì)算；緩存；路由；聯(lián)合優(yōu)化

引言

移動邊緣計(jì)算的新興技術(shù)[1]使無線用戶可以在稱為邊緣云[2]的小型服務(wù)器群集上運(yùn)行資源密集型且對延遲敏感的應(yīng)用程序。該技術(shù)雖利用了云計(jì)算的計(jì)算能力，卻不會因?yàn)樵L問遠(yuǎn)程云而造成較大的通信延遲。要充分發(fā)揮移動邊緣計(jì)算的潛力，需要合理的服務(wù)緩存和請求路由策略，即將服務(wù)緩存至資源有限的邊緣云，并將請求路由到相應(yīng)的邊緣云處。關(guān)于邊緣云計(jì)算中的請求調(diào)度路由問題，有部分研究考慮將用戶的請求路由到靠近用戶的邊緣服務(wù)器上，但這種做法會造成負(fù)載極度不均衡[1,3]。另外，還有部分研究假設(shè)用戶所請求的資源是獨(dú)享的[4~5]，而在實(shí)際應(yīng)用場景中，不同的服務(wù)請求是可以共享資源。關(guān)于邊緣云計(jì)算中的緩存問題，現(xiàn)有的緩存策略大多數(shù)只考慮了存儲資源（即緩存空間），卻忽略了其他類型的資源（例如CPU、帶寬資源）[6~8]。因此，針對邊緣云計(jì)算的緩存和路由問題，我們建立服務(wù)緩存和請求路由的聯(lián)合優(yōu)化模型，提出高效的優(yōu)化算法進(jìn)行問題求解。

1 問題建模

1.1 系統(tǒng)模型

圖1 系統(tǒng)模型

服務(wù)可以在邊緣云之間進(jìn)行遷移或復(fù)制，也可以從遠(yuǎn)程云遷移到邊緣云。每個邊緣云的通信、計(jì)算和存儲資源均有限。在每幀中，在邊緣云之間或從遠(yuǎn)程云到邊緣云之間進(jìn)行服務(wù)的遷移和復(fù)制的成本預(yù)算為。假設(shè)所有邊緣云都是通過可用于云間通信的回程鏈路連接的。因此，請求可以在非本地的邊緣云得到服務(wù)。

為了控制系統(tǒng)穩(wěn)定性和放置副本的成本，我們將在每個幀的開頭執(zhí)行緩存策略，在每個時隙中執(zhí)行路由策略。

1.2 聯(lián)合優(yōu)化問題

2 優(yōu)化算法

2.1 請求路由算法

2.2 服務(wù)緩存近似算法

然后，將服務(wù)緩存問題重寫為以下形式：

聯(lián)合服務(wù)緩存和請求路由的算法流程如算法1所示。

3 多幀優(yōu)化

4 性能評估

為了評估算法的性能，使用以下基準(zhǔn)：a. 使用混合整數(shù)規(guī)劃求解器[9]對問題（1）的最佳解決方案；b. 帶舍入的線性松弛，首先解決進(jìn)行線性松弛后的問題（1），然后將緩存變量舍入為0或者1。

性能評估所采用的實(shí)驗(yàn)平臺是ONE（Opportunistic Networking Environment）網(wǎng)絡(luò)模擬器，ONE模擬器是基于java語言編寫的開源軟件，是一個基于離散時間的模擬引擎[10~11]。在實(shí)驗(yàn)中，從真實(shí)的數(shù)據(jù)集中提取用戶和邊緣云的位置。使用出租車數(shù)據(jù)集[12]，在520分鐘的時間內(nèi)提取36個用戶的移動軌跡，并每10分鐘更新一次位置。每幀包含4個時隙，每個時隙持續(xù)10分鐘。根據(jù)從AntennaSearch網(wǎng)站（http://www.antennasearch.com）獲得的蜂窩網(wǎng)絡(luò)基站位置將用戶分配到Voronoi基站中，從中選擇6個基站子集，以表示邊緣云的位置。用戶請求是從無線數(shù)據(jù)集[13]中生成的，其中包含由36個無線設(shè)備的5個不同應(yīng)??用程序生成的傳輸時間戳。在出租車數(shù)據(jù)集中將每個設(shè)備與一個用戶相關(guān)聯(lián)。對于每個邊緣云，其容量從3~6 TB中進(jìn)行隨機(jī)選擇，其通信容量為16~48 Mbps和其計(jì)算容量為50~100 Gflops每秒。

圖2 三種算法的請求服務(wù)率對比結(jié)果

圖3 F=2時本文算法的性能

結(jié)論

本研究在網(wǎng)絡(luò)通信、節(jié)點(diǎn)計(jì)算和存儲約束下，針對聯(lián)合服務(wù)緩存和請求路由提出了兩階段的解決方案。通過將貪婪啟發(fā)式算法與請求路由相結(jié)合，設(shè)計(jì)了多項(xiàng)式時間的服務(wù)緩存算法。仿真結(jié)果表明，本文的算法能接近最優(yōu)的性能。

[1] Mach P, Becvar Z. Mobile edge computing: A survey on architecture and computation offloading[J]. IEEE Communications Surveys & Tutorials, 2017, 19(3): 1628~1656.

[2] Machen A, Wang S, Leung K K, et al. Live service migration in mobile edge clouds[J]. IEEE Wireless Communications, 2017, 25(1): 140~147.

[3] Ceselli A , Fiore M , Premoli M , et al. Optimized assignment patterns in Mobile Edge Cloud networks[J]. Computers & operations research, 2019, 106(6): 246~259.

[4] Wang S , Tuor T , Salonidis T , et al. When Edge Meets Learning: Adaptive Control for Resource-Constrained Distributed Machine Learning[C]// IEEE INFOCOM 2018. IEEE, 2018: 1~10.

[5] Mao Y , You C , Zhang J , et al. A Survey on Mobile Edge Computing: The Communication Perspective[J]. IEEE Communications Surveys & Tutorials, 2017, 19(4): 2322~2358.

[6] Ozfatura E , Rarris T , Gunduz D , et al. Delay-Aware Coded Caching for Mobile Users[C]// 2018 IEEE 29th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC). IEEE, 2018: 1~10.

[7] Chu W , Dehghan M , Lui J C S , et al. Joint cache resource allocation and request routing for in-network caching services[J]. Computer Networks, 2018, 131: 1~14.

[8] Shukla S , Bhardwaj O , Abouzeid A A , et al. Hold'em Caching: Proactive Retention-Aware Caching with Multi-path Routing for Wireless Edge Networks[C]// ACM International Symposium. ACM, 2017: 1~10.

[9] Zakaria R, Dib M, Moalic L, et al. Car relocation for carsharing service: Comparison of CPLEX and greedy search[C]//2014 IEEE Symposium on Computational Intelligence in Vehicles and Transportation Systems (CIVTS). IEEE, 2014: 51~58.

[10] Cao Y , Song H , Kaiwartya O , et al. Mobile Edge Computing for Big-Data-Enabled Electric Vehicle Charging[J]. IEEE Communications Magazine, 2018, 56(3): 150~156.

[11] 楊玉仁, 張書奎, 龍浩,等. 群智感知中基于社交屬性及有效用戶計(jì)算的任務(wù)分發(fā)機(jī)制[J]. 計(jì)算機(jī)應(yīng)用研究, 2019, 36（5）: 219~225.

[12] Mtibaa A, Harras K A. CAF: Community aware framework for large scale mobile opportunistic networks[J]. Computer Communications, 2013, 36(2): 180~190.

[13] Kumar K, Dalai A K, Panigrahy S K, et al. An ANN based approach for wireless device fingerprinting[C]// 2017 2nd IEEE International Conference on Recent Trends in Electronics, Information & Communication Technology (RTEICT). IEEE, 2017: 1302~1307.

Research on Optimization of Joint Cache and Routing Strategy in Edge Cloud Computing

WANG Jin

（Department of information and intelligent engineering, Anhui Vocational College of Electronics & Information Technology, Bengbu 233000 Cnina）

Edge cloud computing can provide cloud service for wireless users without causing large communication delays. This paper proposes a two-stage optimization framework for the problem of joint service caching and request routing in edge cloud computing. The framework jointly optimizes service caching and request routing under storage, communication, computing, and budget constraints. By transforming the joint problem into a set function optimization, we design an efficient polynomial time algorithm. Finally, we use real data sets for simulation experiments, and the results show that the performance of our algorithm is close to the best performance.

Edge cloud computing; cache; routing; joint optimization

2020-03-07

2018年度高等學(xué)校省級質(zhì)量工程項(xiàng)目（2018jyxm1368）；2019年度高等學(xué)校省級質(zhì)量工程項(xiàng)目（2019xqsxzx56）

王錦（1982—），男，安徽蚌埠人，講師，碩士，研究方向：計(jì)算機(jī)應(yīng)用技術(shù)。

TP311

A

2095-9249（2020）03-0063-04

〔責(zé)任編校：吳侃民〕