王 錦

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

王 錦

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

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

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

引言

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

1 問題建模

1.1 系統(tǒng)模型

圖1 系統(tǒng)模型

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

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

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

2 優(yōu)化算法

2.1 請求路由算法

2.2 服務緩存近似算法

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

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

3 多幀優(yōu)化

4 性能評估

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

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

圖2 三種算法的請求服務率對比結果

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

結論

本研究在網(wǎng)絡通信、節(jié)點計算和存儲約束下，針對聯(lián)合服務緩存和請求路由提出了兩階段的解決方案。通過將貪婪啟發(fā)式算法與請求路由相結合，設計了多項式時間的服務緩存算法。仿真結果表明，本文的算法能接近最優(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] 楊玉仁, 張書奎, 龍浩,等. 群智感知中基于社交屬性及有效用戶計算的任務分發(fā)機制[J]. 計算機應用研究, 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年度高等學校省級質量工程項目（2018jyxm1368）；2019年度高等學校省級質量工程項目（2019xqsxzx56）

王錦（1982—），男，安徽蚌埠人，講師，碩士，研究方向：計算機應用技術。

TP311

A

2095-9249（2020）03-0063-04

〔責任編校：吳侃民〕