基于强化学习的分层协作边缘缓存架构

贾宗璞,郑 帅,任建吉,原永亮

(1. 河南理工大学计算机科学与技术学院,河南 焦作 454003;2. 河南理工大学机械与动力工程学院,河南 焦作 454003)

1 引言

随着5G技术的发展和普及,移动设备和应用程序的数量迅速增加,产生的海量数据给网络带来了巨大的流量压力[1]。传统的内容获取方式是通过回程链路从骨干网下载,这种重复的访问方式会带来大量冗余数据流量[2]。边缘缓存的思想是将内容下沉至边缘节点,实现就近内容服务,来显著提高网络传输效率。它被认为是缓解回程链路和蜂窝网络流量压力的一种有效的方式[3]。通过在网络边缘缓存适当的内容,可以在本地满足用户对相同内容的需求,而不是通过回程网络重复传输[4,5]。

在实际的应用场景中,由于缓存系统所处环境是不断变化的,所以缓存内容不能按照固定的策略来进行。基于强化学习的缓存方法可以更好地适应不断变化的环境,并及时进行缓存策略的更新。Chen等人在文献[6]中使用Wolpertinger架构的强化学习框架研究无线网络边缘的内容缓存,研究内容没有关注内容流行度分布。Sadeghi等人在文献[7]中提出基于Q-Learning的强化学习方案,没有考虑到服务区域扩大的问题。Hu等人在文献[8]中使用迁移学习来解决新增节点的冷启动问题,没有考虑到新增节点最近邻的选取问题。

本文考虑到新增节点最近邻的选取、分层缓存等问题,提出了一种基于A3C强化学习算法的的分层协作边缘缓存架构。使用KNN算法寻找新增节点的最近邻节点,进而通过迁移学习,解决新增节点的冷启动问题。此外设计双层网络模型架构,以减少回程链路负载,进一步降低访问延迟。仿真结果表明,本文提出的HECA架构在提高缓存命中率和解决冷启动问题的有效性。

2 系统模型与问题表述

如图1所示,该架构包括四层:数据中心层、一级缓存层、二级缓存层和用户层。

图1 边缘缓存系统架构图

数据中心层(DC):包含该系统的所有数据,下层缓存层无法满足的内容请求将最终发送到这一层,再将用户请求的内容逐级下发直到最终发回给用户。

一级缓存层(BBS):一级缓存层(BBS)和二级缓存层(SBS)功能类似,都是起到缓存数据的作用,这种分层的缓存模式可以将下层用户的需求控制在一定区域内解决,从而减小数据中心层以及主干网的压力。

二级缓存层(SBS):节点部署在靠近用户的边缘侧。在边缘端部署的每个节点,响应其覆盖区域内所有用户。当用户区域扩大时,则需要新增节点来提供服务。考虑到相邻区域内的用户有着相似的本地内容流行特征。当出现新增节点时,通过KNN算法找到新增节点的最近节点,然后通过迁移学习将找到的最近邻节点的神经网络参数传递给新增节点,从而降低新增节点的训练时间,使其快速收敛到最优策略。

用户层:内容的请求方,用户向SBS层提交他们的内容请求。每个对应的SBS在其存储单元中搜索内容。如果内容存在,则SBS直接将内容提供给用户。否则SBS将用户的请求发送到一级缓存层BBS。每个对应的BBS在其缓存中搜索请求的内容。如果存在,则BBS将其提供给下级SBS。否则,BBS将请求发送到数据中心层。在数据中心层,存储了用户请求所需的全部内容。数据中心在收到请求后将通过回程链路将内容发送到BBS,进而发送到SBS,直至传送给请求相应内容的用户。

缓存系统中的每个SBS、BBS都是基站,容量大小不同。每个单独的基站都有一个缓存控制单元(CCU),目的在控制缓存过程并获取最佳缓存策略[9]。本文定义每个SBS存储E个内容,每个BBS存储M个内容,数据中心共F个内容。考虑到一级缓存和二级缓存的功能类似。在接下来的描述中,本文主要对二级缓存进行详细描述。对于每个SBS以及数据中心的F个内容,定义F×1的动作矩阵。动作矩阵可以表示为a(t)∈A,其中A是所有可行动作的集合,定义为

A={a|a∈{0,1}F,aF1=E}

(1)

在每个时刻的t开始,SBS中的CCU会根据当前环境状态和缓存策略执行相应缓存操作。本地和全局内容流行度分别定义为pl(t)、pg(t)。因为设计的缓存架构总计有四层,所以定义缓存收益由一个成本和三个部分的奖励组成。产生的成本是内容替换产生的,定义为

r1,t(a(t),a(t-1))=λ1aT(t)(1-a(t-1))

(2)

第一种奖励是缓存操作和二级缓存层流行度配置文件之间的匹配,即当用户请求时内容存储在SBS中的奖励,表示为

r2,t(s(t))=λ2aT(t)pl(t)

(3)

第二种奖励是缓存操作和一级缓存层流行度配置文件之间的匹配,表示为

r3,t(s(t))=λ3aT(t)pm(t)

(4)

第三种奖励是缓存操作和全局流行度配置文件之间的匹配,表示为

r4,t(s(t))=λ4aT(t)pg(t)

(5)

因为r1表示为缓存操作产生的成本,即负向收益,r2、r3和r4表示为缓存操作的正向收益。所以t时刻缓存操作a(t)的整体收益可进一步推导为

B(t)=-r1,t(a(t),a(t-1))+r2,t(s(t))+r3,t(s(t))+r4,t(s(t))

=-λ1aT(t)(1-a(t-1))+λ2aT(t)pl(t)+λ3aT(t)pm(t)

+λ4aT(t)pg(t)

(6)

面对当前状态s(t),本文通过缓存策略获得将要执行的缓存操作,缓存操作来指导具体缓存哪些内容。缓存策略的性能由状态值函数判断,状态值函数定义为

(7)

由于缓存策略和s(t)、a(t)和s(t+1)相关联,并且当前的缓存操作对未来是有一定影响的。所以这个状态值函数显示了从当前时间τ到无限时间的总回报,呈现累加的形式,又考虑到当前操作对后续的影响逐渐减小,所以引入因折扣因子γ∈(0,1)来进行计算。基于上述推论,最优缓存策略π*可以定义为

(8)

通过动作a从当前状态s到下一个状态s′的转移概率被定义为[Pa]ss′。通过贝尔曼方程,状态值函数可以进一步推导为

(9)

最佳状态值函数可以表示为

(10)

3 边缘缓存算法设计

通过强化学习算法可以得到最佳缓存策略以及最佳状态值函数。如图2所示,A3C算法是一种异步多线程强化学习算法,它包含一个全局网络和多个actor-critic网络,actor网络产生缓存策略,critic网络提供一种评估机制来评估获得的缓存策略[10]。每个worker定期将新更新的参数上传到全局网络,全局网络经过经验整合及时将更新后的参数分发给所有worker。

图2 A3C架构图

在全局网络中,actor参数表示为θ,critic参数表示为θv。在每个worker中,actor参数表示为θ′,critic参数表示为θ′v。缓存策略表示为π(a|s;θ′)。如算法中所示,提出的基于A3C的边缘缓存算法是N步返回算法,即单个worker步数达到MAX＿STEP时又从初始状态开始。所以本文定义动作状态值函数R为

R=Bi+γBi+1+γ2Bi+2+…+γt-iR

(11)

其中i∈{t-1,t-2,…,t-N},N个连续状态中的动作状态值是相关的。

基于A3C的边缘缓存算法:

输入:初始化值Tmax、tmax,折扣因子γ

输出:缓存策略

初始化参数时刻t=1,总迭代次数T=0

repeat

重置梯度dθ=0,dθv=0

更新worker异步线程参数θ′=θ,θ′v=θv

轨迹中的时间序列tstart=t

获取当前时刻状态St

repeat

根据缓存策略和当前状态选择动作

at=π(at|st;θ′)

根据动作at跳转到状态st+1并获得

即时奖励rt

t=t+1,T=T+1

until st==terminal或者t-tstart==tmax

fori∈{t-1,…,tstart}do

R=ri+γR

累计计算梯度θ′

dθ=dθ+∇θ′logπ(ai|si;θ′)(R-V(si;θ′v))

累计计算梯度θ′v

dθv=dθv+∂(R-V(si;θ′v))2/∂θ′v

end for

将当前worker计算获得的累计梯度异

步更新到全局网络

until T>Tmax

4 实验研究

4.1 实验设置

为了验证所提架构的性能,进行了模拟仿真。测试的实验平台操作系统为Windows10,CPU为2.9GHz,运行内存为16GB。本文对缓存系统中的各部分设置了初始化参数,其中内容总数F=1500、一级缓存容量M=700、二级缓存容量E=300。缓存操作成本及奖励部分公式的参数设置为:λ1=10,λ2=60,λ3=600,λ4=1000。各层Zipf模型的参数分别为ηl=1.2、ηm=1.5、ηg=1.7。

4.2 仿真结果分析

图3显示了缓存命中率和边缘节点缓存容量的关系,在内容总数不变的情况下,边缘节点缓存容量较低时,缓存命中率也比较低。当边缘节点的缓存容量增加时,对于不同的缓存策略,缓存命中率都有不同程度的提高。相比于其它缓存策略,提出的HCEA缓存架构表现出了相对较好的缓存命中率,比较适应于现实中的缓存场景。

图3 缓存命中率与边缘缓存容量

如图4所示,在边缘节点缓存容量和流行度分布等参数不变的情况下。随着迭代次数的增加,缓存命中率刚开始是逐渐增大的,后期随着缓存系统逐渐适应环境,缓存命中率逐渐趋于稳定。提出的HCEA缓存架构几乎满足了用户65%的内容请求,其命中率比Q-Learning、LRU、LFU和FIFO分别高出约4%、10%、13%和17%。

图4 缓存命中率与迭代次数

对于迁移学习解决新增节点的冷启动问题,本文同样做了实验验证,并对比了不使用传递来的神经网络参数和使用传递来的神经网络参数这两种训练。从图5中的训练结果可以看出,在使用迁移学习的情况下,新增节点将更快地达到收敛状态,从而更快找到最佳缓存策略。

图5 迁移学习的A3C性能比较

5 结论

在本文中,为了解决用户在进行内容访问时的延迟问题,提出了一种基于强化学习的分层协作边缘缓存架构HCEA。为了评价架构的性能进行了仿真,将其与Q-Learning、LRU、LFU和FIFO算法进行了比较。仿真结果表明,所提出的架构在缓存命中率及解决冷启动问题方面是有效的。本次工作仍有一些不足之处需要在以后的工作中完善。本研究只考虑了内容的流行性,没有内容的特征。内容之间是有相似性的,接下来的研究中将在缓存架构中考虑到这一点。