移动边缘计算中收益最大化的缓存协作策略

王亚丽，陈家超，张俊娜

移动边缘计算中收益最大化的缓存协作策略

王亚丽1，2*，陈家超1，张俊娜1，2

（1.河南师范大学 计算机与信息工程学院，河南 新乡 453007；

2.智慧商务与物联网技术河南省工程实验室（河南师范大学），河南 新乡 453007）（∗通信作者电子邮箱661687811@qq.com）

移动边缘计算（MEC）通过将资源部署在用户的近邻区域，可以减少移动设备的能耗，降低用户获取服务的时延；
然而，大多数有关缓存方面的研究忽略了用户所请求服务的地域差异特性。通过研究区域所请求内容的特点和内容的动态性特性，提出一种收益最大化的缓存协作策略。首先，考虑用户偏好的区域性特征，将基站分为若干协作域，使每一个区域内的基站服务偏好相同的用户；
然后，根据自回归移动平均（ARIMA）模型和内容的相似度预测每个区域的内容的流行度；
最后，将缓存协作问题转化为收益最大化问题，根据存放内容所获得的收益，使用贪心算法解决移动边缘环境中缓存的内容的放置和替换问题。仿真实验表明，与基于MEC分组的协作缓存算法（GHCC）相比，所提算法在缓存命中率方面提高了28%，且平均传输时延低于GHCC。可见，所提算法可以有效提高缓存命中率，减少平均传输时延。

移动边缘计算；
缓存协作；
用户偏好；
内容流行度；
缓存命中率

近年来，互联网技术快速发展，便携式设备大规模普及使用，无线网络中数据呈指数级增长。传统的集中式计算模式将所有请求迁移到云中心，移动设备和云数据中心之间由于长距离传输会造成巨大传输时延，这会大幅降低移动设备的服务质量，损害用户的服务体验，甚至无法满足实时性要求较高的应用需求。移动边缘计算（Mobile Edge Computing， MEC）通过将计算能力“下沉”到分布式基站［1-2］，为近邻用户提供计算服务。在MEC中，用户所请求的数据被缓存在边缘基站，用户可以直接从附近的边缘基站获取内容，而无需请求云中心，从而减少数据传输时延，减轻骨干网络的压力。

然而，边缘服务器的存储容量有限，只能缓存部分内容，而移动设备数量巨大，用户请求多样且随时间变化。在这种情况下，缓存内容的放置与替换以及边缘服务器之间缓存协作对于减少传输时延、提高缓存性能至关重要。

大多数研究是在缓存大小有限的情况下优化缓存内容放置。在这类研究中，边缘节点通常缓存最流行的内容，这样可以获得较好的命中率。传统的缓存策略如最近最少使用（Least Recently Used， LRU）、最不频繁使用方法（Least Frequently Used ， LFU）已经得到广泛研究［3-4］；
文献［5］中提出了一种基于Zipf的移动边缘主动缓存算法。然而，这些研究大多将流行度设置为静态参数。实际上，内容的流行度会随时间不断变化。边缘服务器也可使用机器学习方法以更好地预测内容的流行度。文献［6］中应用Q‑learning算法进行用户偏好预测和内容普及预测，进而提出了一种分布式内容缓存方案；
文献［7］中提出了一种基于进化学习的内容缓存策略，可以自适应地学习随时间变化的内容流行度。然而这些研究方法均忽略了用户偏好的地域差异特性。在实际应用场景中，局部流行度与全局流行度差异很大。而且在缓存过程中也会出现一些新的内容被用户请求，但上述这些缓存策略因内容设置不变，导致一些流行的新内容没有被缓存，使得缓存命中率下降。

本文综合考虑用户偏好的区域性以及内容的动态性，提出了一种分区协作的缓存放置和替换策略。主要工作如下：

1）通过基站间所服务用户的类型以及所请求内容的类型，分析其相似度；
根据相似度，采用谱聚类构建协作域，使一个协作域中的基站服务一类或几类用户。

2）通过差分自回归移动平均（Auto‑Regressive Integrated Moving Average， ARIMA）模型分别预测不同区域中的内容流行度；
对于新的内容根据内容特征求解与现有流行内容的相似度，进而预估其流行度。

3）将缓存放置问题转化为收益最大化问题，并通过贪心算法求解。仿真结果表明，本文提出的分区协作缓存算法可以显著降低平均传输时延以及提高缓存命中率。

内容缓存旨在研究利用缓存技术达到节省带宽、减少网络时延和降低访问花费等目的。MEC已经有许多关于内容缓存方面的工作。Gu等［8］提出了一种基于学习的算法以解决MEC节点的缓存替换问题。该算法通过将问题形式化为马尔可夫决策过程，以分布式的方式解决该问题。Güven等［9］提出了一种基于线性整数问题的设备到设备（Device‑to‑ Device， D2D）的网络内容分发和资源分配方案。以上缓存方式都是通过非合作方式完成的，但其实边缘基站的协作可以提高缓存策略的性能。Wang等［10］考虑了基站缓存内容的多样性和冗余性之间的权衡，提出了一个边缘缓存节点之间的协作缓存方案，利用粒子群优化算法获得了最优的冗余度，极大地降低了总传输成本。Jiang等［11］提出了一种用于异构蜂窝网络的协作缓存策略，将最优内容缓存策略设计转化为整数线性规划问题，并通过次梯度方法求解。

上述缓存策略都是在内容流行度已知的情况下实现的，但在实际应用中，每个内容未来受欢迎的程度是未知的。因此，任务流行度的预测也是一个重要的问题。Zhong等［12］采用强化学习的多智能体框架预测内容流行度，将最流行的内容预缓存在边缘基站上，并通过协作实现最小的总传输时延。Yang等［13］提出了一种缓存辅助的NOMA MEC框架，该框架研究了任务卸载决策、计算资源分配和缓存决策的联合优化问题。首先，采用长短期记忆（Long Short‑Term Memory， LSTM）网络来预测任务流行度；
接着根据所预测的任务流行度，使用一个单智能体Q‑learning算法来解决该联合优化问题，最小化长期总能耗。Tan等［14］提出了一种利用矩阵补全（Matrix Completion， MC）技术进行内容流行度预测的方法来解决MEC的任务卸载和缓存问题，通过分析每个任务的流行度误差，对预测误差较低的任务进行提前估计；
然后利用MC技术对剩余流行度进行估计；
最后通过缓存与卸载带来的收益决定所缓存的内容。Jeon等［15］提出了一种混合式机器学习方法来预测视频内容的流行度，根据内容特征将整个数据集分为两类，并使用XGBoost算法或带有类别嵌入的神经网络进行流行度预测。此外，用户请求存在地域差异，但大多数内容放置策略都只考虑了内容的全球流行度［16］。针对此问题，Zhong等［17］提出了一种基于协作簇划分的缓存放置策略，通过集群内小型基站的下载历史日志判断流行度，以提高基站的内容命中率。Ren等［18］根据用户分布特点和MEC的位置，提出了一种基于分组的分层协作缓存策略，但没有考虑内容的区域流行度和全局流行度的差异。本文综合考虑了用户的地域差异以及内容的动态性，提出了一种基于收益最大化的协作内容缓存策略。

图1　MEC协作场景

2.1　SBS相似度分析

用户具有移动性的特点，但大部分用户每天就在有限的基站间活动；
不同基站服务的用户所偏好的内容也有差异，这导致不同的区域用户群请求的内容类别也会有差别。例如，用户在住宅区会倾向于请求一些娱乐类信息，在公司会请求与工作相关的信息，这导致区域流行度与全局流行度之间存在差异。本文假定区域内用户位置相对稳定，移动范围较小，不考虑用户跨区域移动的情况。

定义1 基站的内容相似度。基站和基站的相似度定义为两个基站所请求内容的相似度，表示如下：

2.2　传输时延分析

由于本地服务器到用户的传输时延总是存在的且通常很小，所以本文暂不进行讨论。

2.3　内容的流行度预测

根据内容流行度确定SBS中存储的内容至关重要。SBS中存储的高流行度文件越多，用户的请求命中率越高，获取内容的相应时延也越少。内容流行度与内容的放置副本数、放置位置等都有关系。

用户所请求内容的流行度存在地域差异特性，造成区域流行度和全局流行度有很大不同［18］。本文根据历史访问记录计算每个协作域中请求最频繁的内容，而不是全局请求最频繁的内容，以提高缓存命中率。由于新内容无法根据历史访问记录计算流行度，所以本文根据新内容与现有内容的相似度计算其流行度。

1）已有内容流行度计算：通过时隙中历史请求可以得到流行度为：

其中：为协作域中热点内容的数量。

2.4　问题形式化

在所缓存内容总量不超过缓存容量的情况下，可将缓存放置优化问题转化为所有请求内容的传输时延最小化问题，表示为：

缓存协作研究利用内容主动缓存技术达到节省带宽、减少网络时延和降低访问花费等方面的目的，研究内容包括缓存资源分配、缓存内容替换、缓存协作等。缓存协作研究在协同环境下一组相互合作的边缘计算节点如何协同工作以便高效地存储内容和响应用户请求的问题；
缓存资源分配研究在哪个边缘计算服务器放置什么内容的问题；
缓存替换研究什么时机采用何种策略替换何种内容的问题。

3.1　协作域的构建

由于用户所请求内容存在地域差异，通过构建协作域将具有不同兴趣偏好的用户所属的服务基站进行划分，使同一个协作域中的基站可以服务具有相同或相似兴趣偏好的用户。协作域的划分需要确保协作域中的每个SBS彼此位置相对邻近，并且所缓存的内容类别高度相似。因此联合考虑基站间的内容相似度和用户相似度来描述不同基站间的综合相似度。

两个SBS的相似度越大，说明这两个SBS所接收到的相同的内容请求越多，或者这两个基站相似的用户越多，这两个SBS就可以互相成为协作基站。当用户在本地基站无法获取文件时，就从和本地基站相似度最大的基站开始依次寻找协作基站以获取内容。

算法1 协作域构建算法。

7） END FOR

8） END FOR

3.2　缓存放置策略

本文的目标是设计一个缓存协作方案来最小化用户获取内容的时延，其优化目标已由式（14）给出。本文将此问题转化为收益最大化问题，使用效益值来描述缓存某指定内容使平均传输时延减少的量，通过贪心算法寻找效益值最大的内容进行存放，解决内容放置问题。

算法2 基于效益值的缓存放置方法。

8） END FOR

9） END FOR

14） END FOR

15） END FOR

3.3　缓存替换策略

算法3 基于效益值的缓存替换方法。

9） END IF

10） END IF

对本文算法与随机置换（Random Permutation， RR）、最近最少使用（LRU）以及基于MEC分组的协作缓存（Grouping‑based and Hierarchical Collaborative Caching， GHCC）［19］等三种缓存算法进行评估比较。RR通过随机选择内容进行替换；
LRU算法记录最后两次使用之间的间隔，如果请求的内容未缓存，则替换间隔较长的内容；
GHCC算法是一种基于用户位置和MEC分布的协作缓存策略。

图2显示了前20个时隙中不同算法的缓存命中率。从图2可以看出：RR算法的缓存命中率最低；
与GHCC相比，本文算法在命中率方面提高了28%，且在所有时隙上都优于其他三种方案。

图2　前20个时隙中不同算法的缓存命中率

图3　不同内容相似度权重下的缓存命中率

图4描述了不同文件总量对四种不同缓存算法的缓存命中率和平均传输时延的性能影响。该实验中，单个基站的容量控制为10，总文件数量在50～500。在图4（a）中，当用户可以请求比缓存容量更多的内容时，命中率将降低；
此外，随着文件数量的增加，缓存命中率下降的速度减慢。在图4（b）中，平均传输时延随着文件总量的增多而增加，这是因为文件数量变多，用户请求被分散开，用户通过宏基站获取内容的概率升高，总体传输时延增多。

图5描述了不同缓存容量下的性能比较。通过控制文件数量为500，将每个SBS的容量调整为10～30。在图5（a）中，缓存命中率随着边缘基站缓存容量的增加而增加，而在图5（b）中平均传输时延呈下降趋势。这是因为随着缓存容量的增加，更多的请求内容可以缓存在SBS内存中，总命中率会增加，通过宏基站传输的概率会减少。可以看出，本文算法优于其他三种算法，在容量限制或文件基数大的情况下，本文提出的缓存方案优于其他缓存方案，可以降低平均传输时延。

图4　文件总量与缓存命中率和平均传输时延的关系

图5　缓存容量与缓存命中率和平均传输时延的关系

针对内容请求的区域性和动态性，本文提出了一种内容动态情况下的协作缓存策略，用来最小化平均传输时延，根据用户访问记录中内容和用户的异同将基站间的协作区域进行划分，并按照内容的新旧用不同的方式对内容的流行度进行预测，最后将优化函数转化为收益最大化问题并求解得出最优的缓存放置和替换策略。实验表明，该方案具有较高的缓存命中率和较低的平均传输时延。

本文提出的缓存协作策略虽然取得了较好的效果，但尚有需要完善的地方。比如：1）缓存内容放置算法的更新频率需要根据具体情况确定，过快会消耗更多功率，过慢则会降低整体命中率；
2）还可以考虑所缓存的内容大小不同，对于不同大小的内容，可以对文件大小进行归一化处理，此时内容流行度需要取一个相对于内容大小的比值，这样如果有相同流行度但大小不同的内容时，小内容的缓存收益会大于大内容；
3）本文构建协作域时假定用户的移动相对固定，下一步还可考虑用户在协作域间动态移动场景下的协作缓存策略。

[1] 张开元，桂小林，任德旺，等. 移动边缘网络中计算迁移与内容缓存研究综述［J］. 软件学报， 2019， 30（8）：
2491-2516.（ZHANG K Y， GUI X L， REN D W， et al. Survey on computation offloading and content caching in mobile edge networks［J］. Journal of Software， 2019， 30（8）：
2491-2516.）

[2] SAFAVAT S， SAPAVATH N N， RAWAT D B. Recent advances in mobile edge computing and content caching［J］. Digital Communications and Networks， 2020， 6（2）：
189-194.

[3] MARKAKIS E K， KARRAS K， SIDERIS A， et al. Computing， caching， and communication at the edge：
the cornerstone for building a versatile 5G ecosystem［J］. IEEE Communications Magazine， 2017， 55（11）：
152-157 .

[4] IOANNOU A， WEBER S. A survey of caching policies and forwarding mechanisms in information‑centric networking［J］. IEEE Communications Surveys and Tutorials， 2016， 18（4）：
2847-2886.

[5] YAN M， CHAN C A， LI W W， et al. Assessing the energy consumption of proactive mobile edge caching in wireless networks［J］. IEEE Access， 2019， 7：
104394-104404.

[6] JIANG F， YUAN Z， SUN C Y， et al. Learning‑based content caching with update strategy for fog radio access networks［C］// Proceedings of the 2019 IEEE/CIC International Conference on Communications in China. Piscataway：
IEEE， 2019：
484-489.

[7] FAN Q L， LI X H， LI J， et al. PA‑Cache：
evolving learning‑based popularity‑aware content caching in edge networks［J］. IEEE Transactions on Network and Service Management， 2021， 18（2）：
1746-1757.

[8] GU J X， WANG W， HUANG A P， et al. Distributed cache replacement for caching‑enable base stations in cellular networks［C］// Proceedings of the 2014 IEEE International Conference on Communications. Piscataway：
IEEE， 2014：
2648-2653.

[9] GÜVEN C， BAYHAN S， GÜR G， et al. Optimal resource allocation for content delivery in D2D communications［C］// Proceedings of the IEEE 28th Annual International Symposium on Personal， Indoor， and Mobile Radio Communications. Piscataway：
IEEE， 2017：
1-5.

[10] WANG S， ZHANG X， YANG K， et al. Distributed edge caching scheme considering the tradeoff between the diversity and redundancy of cached content［C］// Proceedings of the 2015 IEEE/CIC International Conference on Communications in China. Piscataway：
IEEE， 2015：
1-5.

[11] JIANG W， FENG G， QIN S. Optimal cooperative content caching and delivery policy for heterogeneous cellular networks［J］. IEEE Transactions on Mobile Computing， 2017， 16（5）：
1382-1393.

[12] ZHONG C， GURSOY M C， VELIPASALAR S. Deep multi‑agent reinforcement learning based cooperative edge caching in wireless networks［C］// Proceedings of the 2019 IEEE International Conference on Communications. Piscataway：
IEEE， 2019：
1-6.

[13] YANG Z， LIU Y W， CHEN Y， et al. Cache‑aided NOMA mobile edge computing：
a reinforcement learning approach［J］. IEEE Transactions on Wireless Communications， 2020， 19（10）：
6899-6915.

[14] TAN J W， LIU W， WANG T， et al. A high‑accurate content popularity prediction computational modeling for mobile edge computing using matrix completion technology［J］. Transactions on Emerging Telecommunications Technologies， 2021， 32（6）：
No.e3871.

[15] JEON H， SEO W， PARK E， et al. Hybrid machine learning approach for popularity prediction of newly released contents of online video streaming services［J］. Technological Forecasting and Social Change， 2020， 161：
No.120303.

[16] ZHU X D， QI W N， WANG J L， et al. A popularity‑based collaborative caching algorithm for content‑centric networking［J］. Journal of Communications， 2016， 11（10）：
886-895.

[17] ZHONG N， ZHANG H M， ZHANG X L. Collaborative partition caching with local popularity［C］// Proceedings of the IEEE 20th International Conference on Communication Technology. Piscataway：
IEEE， 2020：
514-518.

[18] REN J Z， TIAN H， NIE G F. Proactive caching scheme with local content popularity prediction［J］. Journal of Beijing University of Posts and Telecommunications， 2020， 43（1）：
80-91.

[19] REN D W， GUI X L， LU W， et al. GHCC：
grouping‑based and hierarchical collaborative caching for mobile edge computing［C］// Proceedings of the 16th International Symposium on Modeling and Optimization in Mobile， Ad Hoc， and Wireless Networks. Piscataway：
IEEE， 2018：
1-6.

Cache cooperation strategy for maximizing revenue in mobile edge computing

WANG Yali1，2*， CHEN Jiachao1， ZHANG Junna1，2

（1，，453007，；
2（），453007，）

Mobile Edge Computing （MEC） can reduce the energy consumption of mobile devices and the delay of users’ acquisition to services by deploying resources in users’ neighborhood；

however， most relevant caching studies ignore the regional differences of the services requested by users. A cache cooperation strategy for maximizing revenue was proposed by considering the features of requested content in different regions and the dynamic characteristic of content. Firstly， considering the regional features of user preferences， the base stations were partitioned into several collaborative domains， and the base stations in each collaboration domain was able to serve users with the same preferences. Then， the content popularity in each region was predicted by the Auto‑Regressive Integrated Moving Average （ARIMA） model and the similarity of the content. Finally， the cache cooperation problem was transformed into a revenue maximization problem， and the greedy algorithm was used to solve the content placement and replacement problems according to the revenue obtained by content storage. Simulation results showed that compared with the Grouping‑based and Hierarchical Collaborative Caching （GHCC） algorithm based on MEC， the proposed algorithm improved the cache hit rate by 28% with lower average transmission delay. It can be seen that the proposed algorithm can effectively improve the cache hit rate and reduce the average transmission delay at the same time.

mobile edge computing; cache cooperation; user preference; content popularity; cache hit rate

This work is partially supported by National Natural Science Foundation of China （61902112）.

WANG Yali， born in 1979， Ph. D.， associate professor. Her research interests include edge computing， software defined networking.

CHEN Jiachao， born in 1998， M. S. candidate. His research interests include edge computing.

ZHANG Junna， born in 1979， Ph. D.， associate professor. Her research interests include edge computing， service computing.

1001-9081（2022）11-3479-07

10.11772/j.issn.1001-9081.2022020194

2022⁃02⁃22；

2022⁃04⁃10；

2022⁃04⁃15。

国家自然科学基金资助项目（61902112）。

TP393.0

A

王亚丽（1979—），女，河南三门峡人，副教授，博士，CCF会员，主要研究方向：边缘计算、软件定义网络；
陈家超（1998—），男，河南洛阳人，硕士研究生，主要研究方向：边缘计算；
张俊娜（1979—），女，河南扶沟人，副教授，博士，主要研究方向：边缘计算、服务计算。

猜你喜欢 命中率时延边缘 基于文献回顾的罚球命中率与躯干稳定性影响因素研究体育科技文献通报(2022年5期)2022-06-05计算机网络总时延公式的探讨电脑知识与技术(2021年22期)2021-09-14《舍不得星星》特辑：摘颗星星给你呀花火B(2019年3期)2019-04-27基于GCC-nearest时延估计的室内声源定位电子制作(2019年23期)2019-02-232015男篮亚锦赛四强队三分球进攻特点的比较研究长江丛刊(2018年31期)2018-12-05基于移动站的转发式地面站设备时延标校方法宇航计测技术(2018年3期)2018-09-08投篮的力量休斯敦火箭NBA特刊(2017年8期)2017-06-05一张图看懂边缘计算通信产业报(2016年44期)2017-03-13在边缘寻找自我雕塑(1999年2期)1999-06-28走在边缘雕塑(1996年2期)1996-07-13

推荐访问:最大化 缓存 协作