边缘节点缓存替换策略研究

崔炳辉 李孜 薛吉 李佳伟

摘要：缓存替换机制是内容中心网络研究的重点，在解决网络时延与网络带宽拥堵等问题中发挥着重要作用。针对目前边缘侧量节点设备缓存空间的有限性，提出一种基于猴群算法的优化方案。该方案可合理地对边缘设备缓存内容进行置换，有效提高边缘量设备请求命中率。通过在猴群算法的猴群爬过程中引入文件流行度等引导因子、在望过程中改进猴群视野范围等方法找到最优解。仿真实验结果显示了不同大小的边缘设备缓存空间请求命中率。与传统算法相比，该方案可有效提高请求命中率。

关键词：缓存替换;边缘设备;猴群算法;请求命中率

DOI： 10. 11907/rjdk.191 825

开放科学（资源服务）标识码（OSID）：

中图分类号：TP301

文献标识码：A

文章编号：1672-7800（2020）004-0131-04

Research on Cache Replacement Strategy for Edge Nodes

CUI Bing-hui，LI Zj，XUE Jj2 . LI Jja-wejl

（1.School of Mechanic.s Engirzeering ， University of .Sh.anghaifor .Science and Technology ， Sh.anghai 200093 ， China ;

2.Sh anghai Electrical Apparatus Re.search Institute（Cro up） Co. . Ltd. ， Sh.anghai 200063 . China ）Abstract： Cache replacement mechanisru is an iruportant part of content-centric network research. It is ，videly used to solve network de-lay and network bandwidth congestion. Aiming at the limitation of the buffer space of' edge detection devices， we propose an optimiza-tion scheme based on iuonkey swarm algorithm "-hich can replace the content of edge detection devices' cache reasonably and effective-ly to improve the hit rate of edge detection devices' requests. In order to find the optimal solution， this paper introduces some guidingfactors such as file popularity into the monkey group cra"-ling process and improves the horizon of the monkey group in the looking pro-cess. Then the simulation experiments are carried out. The experimental results shou-， the hit rate of' each request in different size ofedge device cache space. rinally ， by coruparing with the traditional algorithm， it is proved that this scheme can eff'ectively improve thehit rate of requests.Key Words ： Cache replacement ; edge device ; monkey algorithm ; requ est hit ratio

O 引言

隨着网络的不断发展，嵌入式产品数量逐年增加，感应层海量数据随之产生，传统云计算模式处理能力已不能满足数据实时传输、计算及快速决策需求。因此需要一种新的边缘计算模型，辅助云中心处理海量数据[1-3]。边缘计算利用更靠近数据源的边缘节点设备计算与存储能力，快速处理部分请求，可以有效减少带宽压力与网络延时。

但是，每个边缘节点设备的存储空间有限[4]，只能存储一些具有高访问频率的文件，随着时间变化，各文件请求频率也会发生相应变化，而具有高访问频率的文件不能保持一成不变。因此，当边缘测量设备的缓存空间已满时，需清除价值较小的文件，并根据某种替换策略存储新的、更有价值的数据，以提高缓存空间请求命中率[5]。因此，提升网络整体性能的关键是如何合理地管理和替换缓存内容[6]。

传统缓存替换算法有FIFO（First In First Out）算法、LFU[7] （Least Frequentlv Used）算法、LRU[8]（Least RecentlvUsed）算法、SIZE替换策略[9]。FIFO算法优先替换掉最先进入缓存区的对象，使最新文件替换到缓存区中，该算法比较容易实现，复杂度低，但请求命中率较低;LRU算法将离上一次被访问时间间隔最长的文件对象优先替换掉，将最近访问的文件替换进来，认为最近经常被访问的文件数据在之后一段时间内被访问的概率较高，该算法忽略了在一段时间内客户端访问文件的偶然性对文件的影响，同时当文件流行程度发生改变时也会导致该算法适应度较差;基于对象大小的SIZE替换算法将缓存中所占空间较大的文件替换为较小的文件，认为文件数量越多，被访问概率越高，但没有考虑缓存命中次数，反而将一些较小且价值不高的文件存储在边缘设备上;LFU替换策略认为访问频率越高的资源，被访问价值越大，因此当缓存空间不足时，总是替换客户端访问频率最低的内容。但是有可能文件访问程度越高，占用空间很大，存储内容却太少。以上4种传统缓存替代算法仅考虑单方面影响因素，存在一定缺陷。

猴群算法是Zhao &Tang[10]于2008年提出的新兴智能优化算法。该算法源于对白然界中猴群爬山过程的模拟，其主要思想是模仿猴群爬山的过程[11]。猴子通过爬、望、跳3个基本动作方式向最高山峰前进。它是一种简单有效、随机改变的全局性优化算法，具有寻优能力强、参数少等优点，可有效解决复杂问题，逐渐成为计算研究领域的一大热点。本文结合猴群算法，针对传统算法的不足，综合考虑文件访问次数、文件大小及文件流行度等因素，提出基于猴群算法的优化策略。

1衡量指标

当产生感应层数据请求时，对请求数据的回应如图1所示，如果边缘节点设备的内存空间存储了该请求数据，则此时边缘没备作为一个临时服务器，立即对请求的数据进行回应;如果边缘设备没存储该请求数据，只能上传数据，选择云服务器回应数据请求。但是数据通过网络上传会导致数据决策时延。如何选择合理的文件存入边缘设备中进行缓存替换是本文重点研究内容。 （2）计算厂（y1），如果f（yi）>f（x：），且y=（yl，y2，…，yn）在允许范围内，则更新xi为yi;否则xi保持不变，重复执行上述步骤，直到找到满足条件的y点。

（3）到达更好位置y后，猴子以y为起点重新执行爬过程[19]。

2.3跳过程

跳过程主要是从空翻限制范围[a.b]内随机生成一个空翻控制系数 ，其中 ，为空翻支点。若y在可行范围内，则用y替换掉xi，否则继续执行步骤，直至找到合适的y值。

3基于改进猴群算法的缓存替换问题

用猴群算法解决缓存替换问题是在以公式（2）为目标的基础上寻求最优解的过程。在求解过程中，可行解的集合相当于猴群种群大小，每一只猴子的位置相当于目标函数的一个可行解，文件数量对应维数[20]。在猴群算法设计过程中，由于猴群在爬过程和望过程中的前进方向存在随机性，导致算法复杂程度变大、目标函数无法快速收敛，所以在设计过程中通过加入文件流行度与文件单位存储大小等诱导因素，并改进固定的视野距离，从而对整个算法进行完善。

3.1诱导因子设计

诱导因子是猴群算法在猴子爬过程中给猴子一个前进的方向，让猴群朝着设计的目标前进。针对传统缓存替代算法仅考虑单一因素的不足，综合考虑文件大小与文件访问频率，以及一段时间内文件流行度等综合因素，设计诱导因子改进传统算法。

由于请求命中率只能在用户进行访问时才可计算，并且替换算法需在访问发生之前调整边缘设备存储的缓存内容，因此该算法的目的是基于历史数据预测下一个阶段请求命中率。由于用户对某一个文件数据的请求不是一成不变的，而是随时间改变不断变化，因此该文件的请求命中率也在不停变化。例如，缓存中的一些内容在当前时间段内受到用户高度关注，且请求命中率与文件流行度也非常高，但随着客户端对该文件请求次数的降低，该内容很可能变成用户很少访问的对象，所以相应的请求命中率也会下降，为了对文件进行准确预测，提出可利用文件流行度进行文件性能分析。文件流行度根据上个周期内容流行度及当前周期内该内容命中率计算而来。

其中，pi（t）为当前周期内文件i的文件流行度;hi（t-1）代表文件i上个周期内文件请求命中率; 为衰减因子，表示上个周期文件流行度在当前周期所占比列; 表示文件i在当前周期的请求命中率。

求出每个文件单位存储空间的价值量，第i件物的价值量为：求出每个文件所占存储空间的比列为：由此可设置诱导因子为：

3.2算法步骤

设置种群规模M=30、最大迭代次数Max=1000。算法流程如图2所示。

随机生成二进制向量的一个解 作为猴子的初始位置。其中第x，维度只能为0或者l。当其为1时，代表第i文件被选中;当其为0时，代表第i文件未被选中。执行爬过程计算 ，从而优先选取物品中单位存储空间访问程度最高的文件并存人邊缘设备中，同时引入诱导因子。

选取可行解 、随机选取的文件 及未被选取的文件 ，其中 和 属于0到D，分别计算它们的诱导因子，如果 ，则更新猴子的位置， 为 为O;否则猴子的位置不变。计算 ，如果 ，则 更新为 ，否则xi保持不变。

爬过程之后每只猴子都达到了小范围的局部最优，为实现较大范围的寻优过程，可在望过程中进行搜索。所以视野距离y决定望过程的范围，但由于y值过小，此时望过程与爬过程的区别不大，y值过大的目标函数收敛过慢，可能导致在最大迭代次数之后均无法找到最优值。为了平衡这种情况，对y进行一些改进。

其中p代表当前迭代次数， 代表当前函数值与最近替换前的函数值。因此望过程的视野范围 在视野允许的范围内，随机生成一个向量 ，则 ，其中 为猴群可视距离。计算 ，如果 ， 在允许范围内，则更新 为 。随着函数越来越接近最优值，视野距离的值越来越大，从而可有效降低快速陷入局部最优的可能性。与迭代次数同时进行改变可有效维持函数平衡。

执行跳过程，计算 ，生成一个新的二进制向量 。若v在可行范围中，则用v替换 ;否则继续执行以上步骤直到找到合适的y值。

重复上述步骤直到达到最大的迭代次数，结束算法，输出最优值与最优个体。

4 实验与分析

4.1 实验数据选择

在MATLAB软件上进行仿真实验，客户端用户请求习惯一般符合Zipf规律，为了验证实验合理性，对于实验数据的选择也需符合Zipf正态分布规律。本文选取的基本测试实验数据如表l所示。

为了更契合客户端请求习惯，随机选取其中20个文件作为高频文件并对其进行1600次请求访问，对剩下的80个文件进行400次请求访问。

在仿真中，将改进猴群算法解决边缘设备的缓存替换参数设置为：种群规模M=30，最大迭代次数Max=1000，爬步长a=l，衰减因子^=0.4，视野距离y=0.5，跳区间[a，b]=[-1，1]，常数s=1.2。

4.2实验结果

本文實验基于表1的数据进行仿真。图3对比了改进猴群算法与传统算法在文件总大小为2000MB、边缘设备存储空间大小不同的情况下对应的请求命中率。该图总体反映了改进猴群算法在边缘设备中请求命中率有良好效果。尤其在边缘设备存储空间较小时，明显优于其它算法，但是在边缘储存空间较大时，请求命中率提高幅度不明显。通过分析可知改进的猴群算法可在一定程度上提高请求命中率，本文实验也验证了算法可行性。

5结语

本文主要在猴群算法中通过加入诱导因子，使得到的解朝着设计的方向前进，解决了在边缘设备存储空间一定的情况下，如何选择更合适文件的问题，从而提高了边缘设备请求命中率。但是由于猴群算法是逐步寻优，因此要求边缘设备有一定的计算能力，不适用于边缘没备计算能力较弱的情况。同时，实验结果反映该算法在边缘设备存储空间较大时，得到的效果并不十分明显，该算法更适用于边缘设备存储空间较小的情况。后续研究将进一步优化计算，扩展算法应用范围。

参考文献：

[l]王晓飞，韩溢文边缘智能计算与智能边缘计算[J].张江科技评论，2019（2）：10-12

[2]刘俊奇，范明翔，李潇.大数据时代下的新型计算模型——边缘计算[J].电脑知识与技术，2017，13（19）：182-183

[3]吴大鹏，张普宁，王汝言.“端边云”协同的智慧物联网[J]物联网学报，2018，2（03）：21-28

[4]BEAVERS I.智能边缘：边缘节点[J].中国集成电路，2017，26（11）：53-57+81.

[5]黄丹，宋荣方.基于内容价值的缓存替换策略[J].电信科学，2018，34（11）：59-66.

[6]翟聪聪，邹君妮基于时延和效用的多速率视频的缓存优化[J].电子测量技术，2018，41（15）：66-71

[7]黄贤明.基于LRU改进算法的实时数据库缓存机制[J]工业控制计算机，2015，28（12）：63+77.

[8]CUO J，LIU C C， CHEN J L.et al. S-LRU：a Cache replacement algo-rithm of video sharing system for mobile devices[C].Changchun： Pro-ceedings of 2012 2nd International Conference on Computer Scienceand Network Technology， 2012.

[9]陈建，沈潇军，姚一杨，等.基于密文策略属性基加密系统访问机制的缓存替换策略[J].计算机应用，2017，37（10）：2964-2967

[10]ZHAO R Q，TANG WS. Monkey algorithm for glohal numerical opti-mization[Jl. Journal of Uncertain Svstems. 2008，2（3）： 164-176.

[11] 张东洁猴群算法的改进及其应用[D].西安：西安理工大学，2017.

[12] 黎慧源，易国洪，代瑜，等.贪婪双尺寸频率算法的优化与改进[J].武汉工程大学学报，2018，40（6）：685-690

[13] 肖敬伟.基于数据挖掘的缓存替换算法研究[D].北京：北京交通大学，2015

[14] 王博.同步电机远程数据采集与监视控制系统[D].杭州：浙江大学，2018.

[15] 张元尊.NDN网络中视颊数据缓存问题研究[D].合肥：中国科学技术大学，2017.

[16] 陈海涛.改进的猴群算法在云计算资源分配中的研究[J].计算机系统应用，2015，24（8）：191-196.

[17] 齐艳玉，兰燕飞.一类基于动态优化问题的混沌猴群算法[J]武汉理工大学学报（信息与管理工程版），2013，35（2）：164-167.

[18]徐小平，张东洁.基于猴群算法求解旅行商问题[J].计算机工程与应用，2018，54（2）：144-148.

[19] 杜国璋基于猴群算法的传感器优化布置方法研究[D].兰州：兰州交通大学，2016.

[20]徐小平，师喜婷，钱富才.基于猴群算法求解0-1背包问题[J].计算机系统应用，2018，27（5）：133-138.

（责任编辑：江艳）

收稿日期：2019-06-17

作者简介：崔炳辉（1995-），男，上海理工大学机械工程学院硕士研究生，研究方向为电力电子技术。