边缘云计算中联合缓存和路由策略优化研究

王 锦

边缘云计算中联合缓存和路由策略优化研究

王 锦

（安徽电子信息职业技术学院 信息与智能工程系，安徽 蚌埠 233000）

边缘云计算能够为无线用户提供云服务，同时不会造成较大的通信延迟。针对边缘云计算中联合服务缓存和请求路由的问题，提出一个两阶段的优化框架。该框架在存储、通信、计算和预算约束下共同优化服务的缓存和请求路由。通过将该联合问题转化为集合函数优化，设计了高效的多项式时间算法。最后采用真实的数据集进行仿真实验，结果表明，本算法的性能接近最佳的性能。

边缘云计算；缓存；路由；联合优化

引言

移动边缘计算的新兴技术[1]使无线用户可以在称为边缘云[2]的小型服务器群集上运行资源密集型且对延迟敏感的应用程序。该技术虽利用了云计算的计算能力，却不会因为访问远程云而造成较大的通信延迟。要充分发挥移动边缘计算的潜力，需要合理的服务缓存和请求路由策略，即将服务缓存至资源有限的边缘云，并将请求路由到相应的边缘云处。关于边缘云计算中的请求调度路由问题，有部分研究考虑将用户的请求路由到靠近用户的边缘服务器上，但这种做法会造成负载极度不均衡[1,3]。另外，还有部分研究假设用户所请求的资源是独享的[4~5]，而在实际应用场景中，不同的服务请求是可以共享资源。关于边缘云计算中的缓存问题，现有的缓存策略大多数只考虑了存储资源（即缓存空间），却忽略了其他类型的资源（例如CPU、带宽资源）[6~8]。因此，针对边缘云计算的缓存和路由问题，我们建立服务缓存和请求路由的联合优化模型，提出高效的优化算法进行问题求解。

1 问题建模

1.1 系统模型

图1 系统模型

服务可以在边缘云之间进行迁移或复制，也可以从远程云迁移到边缘云。每个边缘云的通信、计算和存储资源均有限。在每帧中，在边缘云之间或从远程云到边缘云之间进行服务的迁移和复制的成本预算为。假设所有边缘云都是通过可用于云间通信的回程链路连接的。因此，请求可以在非本地的边缘云得到服务。

为了控制系统稳定性和放置副本的成本，我们将在每个帧的开头执行缓存策略，在每个时隙中执行路由策略。

1.2 联合优化问题

2 优化算法

2.1 请求路由算法

2.2 服务缓存近似算法

然后，将服务缓存问题重写为以下形式：

联合服务缓存和请求路由的算法流程如算法1所示。

3 多帧优化

4 性能评估

为了评估算法的性能，使用以下基准：a. 使用混合整数规划求解器[9]对问题（1）的最佳解决方案；b. 带舍入的线性松弛，首先解决进行线性松弛后的问题（1），然后将缓存变量舍入为0或者1。

性能评估所采用的实验平台是ONE（Opportunistic Networking Environment）网络模拟器，ONE模拟器是基于java语言编写的开源软件，是一个基于离散时间的模拟引擎[10~11]。在实验中，从真实的数据集中提取用户和边缘云的位置。使用出租车数据集[12]，在520分钟的时间内提取36个用户的移动轨迹，并每10分钟更新一次位置。每帧包含4个时隙，每个时隙持续10分钟。根据从AntennaSearch网站（http://www.antennasearch.com）获得的蜂窝网络基站位置将用户分配到Voronoi基站中，从中选择6个基站子集，以表示边缘云的位置。用户请求是从无线数据集[13]中生成的，其中包含由36个无线设备的5个不同应​​用程序生成的传输时间戳。在出租车数据集中将每个设备与一个用户相关联。对于每个边缘云，其容量从3~6 TB中进行随机选择，其通信容量为16~48 Mbps和其计算容量为50~100 Gflops每秒。

图2 三种算法的请求服务率对比结果

图3 F=2时本文算法的性能

结论

本研究在网络通信、节点计算和存储约束下，针对联合服务缓存和请求路由提出了两阶段的解决方案。通过将贪婪启发式算法与请求路由相结合，设计了多项式时间的服务缓存算法。仿真结果表明，本文的算法能接近最优的性能。

[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]. 计算机应用研究, 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

〔责任编校：吴侃民〕