王 錦

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

王 錦

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

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

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

引言

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

1 問(wèn)題建模

1.1 系統(tǒng)模型

圖1 系統(tǒng)模型

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

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

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

2 優(yōu)化算法

2.1 請(qǐng)求路由算法

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

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

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

3 多幀優(yōu)化

4 性能評(píng)估

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

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

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

圖3 F=2時(shí)本文算法的性能

結(jié)論

本研究在網(wǎng)絡(luò)通信、節(jié)點(diǎn)計(jì)算和存儲(chǔ)約束下，針對(duì)聯(lián)合服務(wù)緩存和請(qǐng)求路由提出了兩階段的解決方案。通過(guò)將貪婪啟發(fā)式算法與請(qǐng)求路由相結(jié)合，設(shè)計(jì)了多項(xiàng)式時(shí)間的服務(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é)校省級(jí)質(zhì)量工程項(xiàng)目（2018jyxm1368）；2019年度高等學(xué)校省級(jí)質(zhì)量工程項(xiàng)目（2019xqsxzx56）

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

TP311

A

2095-9249（2020）03-0063-04

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