雾无线接入网中深度强化学习下带有推荐的缓存方法转让专利
申请号 : CN202010102408.5
文献号 : CN111314862B
文献日 : 2022-01-28
发明人 : 蒋雁翔 , 闫洁
申请人 : 东南大学
摘要 :
权利要求 :
1.一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:包括以下步骤:
步骤1:在当前时隙开始时,雾接入点以广播的形式向其覆盖范围内的所有用户进行内容推荐,推荐内容为雾接入点中当前所有缓存文件所对应的摘要信息;
步骤2:在当前时隙内,利用用户偏好候选集、推荐内容、用户行为、用户移动模式对雾接入点覆盖范围内的每个用户的用户偏好矢量进行建模;每一个用户在当前时隙中尝试进行文件请求,其每一个请求的产生过程可分为两种情况:用户冲动性请求情况和基于用户偏好矢量的用户请求情况,基于这两种情况,对当前时隙内的每一个用户的文件请求进行建模,得到时隙t内的所有用户的文件请求集合 其中,且reqt,u=
步骤3:在当前时隙结束时,在深度强化学习框架下,采用贪婪算法计算得到缓存动作向量,所述深度强化学习框架包括动作值函数相关神经网络Q(st,at;θ),其中,st为系统状态,at为缓存动作向量,参数θ;根据计算得到的缓存动作向量和当前时隙缓存命中情况对应得到下一个系统状态,所述系统状态为雾接入点中当前缓存的文件的索引集合;所述索引为被缓存文件在云服务器上的文件集合中的编号,雾接入点中的本地缓存文件根据得到的下一个系统状态进行相应的更新操作;
步骤4:根据当前时隙中缓存命中情况和请求文件传输成本得到奖励函数;
步骤5:将当前时隙的系统状态、缓存动作向量、下一个系统状态、奖励函数记录为一个经验元组,并将该经验元组存储在经验重放区;
步骤6:以步骤2得到的用户请求集合 作为深度强化学习框架中与雾接入点在t时隙进行交互的外部环境,随机抽取经验重放区中的一组经验元组对动作值函数相关神经网络进行训练并更新该动作值函数相关神经网络的相关参数;
步骤7:判断是否达到最终时隙,若是,则雾接入点内的当前缓存文件为最终的缓存结果,否则进入下一个时隙,并执行步骤1。
2.根据权利要求1所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:在执行步骤1之前,还包括初始化过程:初始化云服务器上的文件集合C={1,2,…c,…,C},从文件集合C中抽取F个文件作为雾接入点的原始本地缓存,将F个文件按照文件序号顺序降序进行排列,抽取的F个文件的有序的索引集合作为系统初始状态s0;
T
初始化用户偏好候选集P={p1,p2,…,pg,…,pG},其中pg=[pg,1,pg,2,…, pg,C ]为一个初始用户偏好矢量,满足Zipf分布,每个用户偏好矢量中包含 C 个偏好值,对应文件集合C中的 C 个文件;
初始化深度强化学习框架,包括初始化动作值函数相关神经网络Q(st,at;θ)对应参数θ,其中,st为系统状态,at为缓存动作向量。
3.根据权利要求1或2所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:所述深度强化学习框架还包括目标动作值函数相关神经网络所述动作值函数相关神经网络和目标动作值函数相关神经网络的结构完全相同。
4.根据权利要求1所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:所述步骤2具体包括以下子步骤:S210:利用用户偏好候选集、推荐内容、用户行为、用户移动模式对雾接入点覆盖范围内的每个用户的用户偏好矢量pt,u进行建模;
S220:设定用户冲动请求概率 其中时隙t内,当第u个用户尝试进行第n次文件请求时,有 的概率,该用户直接从文件集合C中随机请求一个文件,有 的概率,用户按照当前的用户偏好矢量进行文件请求;
当用户按照当前的用户偏好矢量进行文件请求时,从文件集合C中抽取一个待请求文件,通过伯努利分布对请求过程进行建模,以确定所选文件是否被真正请求,如下面公式(1)所示:
式中, 为被选择的文件ft,u,n所对应的用户偏好值,Nt,u为用户u在时隙t内的文件请求数目,其满足Nt,u∈[0,Nmax],被选择的文件有 的概率被真正请求,请求数目加
1;反之,有 的概率,该被选择文件没有被真正请求,请求数目不变;
依次对当前时隙内的每一个用户的文件请求进行建模,得到时隙t内的用户请求集合
5.根据权利要求4所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:所述S210的具体操作如下:S211:根据用户运动模式,对时隙t内雾接入点覆盖范围内的所有用户进行分类得到在时隙t内新到达的新用户和在时隙t之前便已存在的老用户,新用户记为 老用户记为Ut={1,2,…,u,…, Ut}为时隙t内雾接入点覆盖范围内的所有用户;每个新用户的初始用户偏好矢量是从用户偏好候选集P={p1,p2,…,pg,…,pG}中随机抽取并进行适量修改后得到;每个老用户在当前时隙的用户偏好矢量继承上一时隙的用户偏好矢量;
S212:根据雾接入点在时隙t内的推荐内容对雾接入点覆盖范围内的所有用户的用户偏好矢量进行更新:
pt,u为第t时隙内第u个用户的用户偏好矢量,rect=[rect,1,rect,2,…,rect,c,…, T
rect,C ] 为当前雾接入点的内容推荐向量,若第c个文件被推荐,则rect,c=β,β≥1,否则rect,c=1,Φ()为归一化函数;
S213:根据每个用户的行为对雾接入点覆盖范围内的所有用户的用户偏好矢量进行更新,所述用户的行为为用户在当前文件请求之前的所有文件请求状况。
6.根据权利要求5所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:所述S213具体操作如下:在时隙t中,对于第u个用户的第n个请求reqt,u,n=
7.根据权利要求1所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:在所述步骤3中,根据下式得到时隙t内的缓存动作向量:式中,at为缓存动作向量。
8.根据权利要求1或7所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:所述的根据计算得到的缓存动作向量和当前时隙缓存命中情况对应得到下一个系统状态的具体步骤包括:
首先,根据时隙t内所有用户的请求,对雾接入点中当前所缓存的文件的被请求次数进行累加更新并将当前所缓存的文件按照更新后的被请求次数进行降序排列;
之后,所述当前时隙缓存命中情况分为当前时隙内所有用户的文件请求都能从当前雾接入点直接获得和存在无法从雾接入点中获得的被请求文件,定义判决变量m(t),当存在无法从雾接入点中获得的被请求文件时,判决变量m(t)=1,且将该被请求文件填充至集合M中;当当前时隙内所有用户的文件请求都能从当前雾接入点直接获得时,判决变量m(t)=
0,且集合 在每个时隙开始时,需对集合M进行清空;
所述缓存动作向量at和判决变量m(t)共同决定下一个系统状态:若at=0,则下一个系统状态为雾接入点中进行降序排列后的所有缓存文件所对应的索引;
若at=1且m(t)=0,则下一个系统状态为雾接入点中进行降序排列后的所有缓存文件所对应的索引;
若at=1且m(t)=1,则从集合M中随机抽取一个文件来替换当前雾接入点缓存空间中位于末尾处的文件,新更新的文件的被请求次数默认为0,取降序排列和替换操作后的所有缓存文件的索引为下一个系统状态。
9.根据权利要求8所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:
所述步骤4中的奖励函数表示时隙t内雾接入点所能获得的净利润,表示为:其中,rt为奖励函数,θt()用以判断被请求文件ft,u,n是否在时隙t内被缓存在雾接入点中,若被缓存在雾接入点中,则θt(ft,u,n)=1,否则θt(ft,u,n)=0,s表示用户直接从邻近雾接入点中获取被请求文件ft,u,n的传输成本,b表示从云服务器中获取被请求文件ft,u,n的传输成本,b‑s表示雾接入点从云服务器中进行一个文件的更新所消耗的传输成本,η表示用户进行一次请求所要花费的费用。
10.根据权利要求3所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:
‑
每隔K个时隙,目标动作值函数相关神经网络 的参数θ复制动作值函数相关神经网络Q(st,at;θ)的参数θ进行延时更新。
11.根据权利要求10所述的一种雾无线接入网中深度强化学习下带有推荐的缓存方法,其特征在于:所述步骤6具体包括以下步骤:T
随机抽取经验重放区中的一组经验元组[sj,aj,rj,s′j] 对动作值函数相关神经网络Q(st,at;θ)进行训练:
式中,γ为折扣因子,第j时隙的系统状态sj、动作向量aj、下一系统状态s′j、奖励函数rj;
2
执行一个梯度下降的步骤(yj‑Q(sj,aj;θ)) 更新参数θ。
说明书 :
雾无线接入网中深度强化学习下带有推荐的缓存方法
技术领域
背景技术
因此越来越受到研究人员和工程技术人员的关注。在雾无线接入网中,雾无线接入点是配
备有限缓存和计算资源的边缘设备。由于波动的用户请求和有限的存储限制,每个雾无线
接入点需要确定以什么方式在什么时间缓存什么内容,以获得更高的缓存效率。
果能使雾接入点持续缓存热点内容,从而实现逼近理想缓存策略的缓存命中率,提高净利
润,从而最大程度降低回传负载和通信时延。
发明内容
策,从而使雾接入点的长期净利润最大化,且缓存命中率高。
试进行文件请求,其每一个请求的产生过程可分为两种情况:用户冲动性请求情况和基于
用户偏好矢量的用户请求情况,基于这两种情况,对当前时隙内的每一个用户的文件请求
进行建模,得到时隙t内的所有用户的文件请求集合
其中, 且 其中
reqt,u为第u个用户在时隙t中的请求集合,Nt,u为用户u在时隙t内的文件请求数目,满足Nt,u
∈[0,Nmax],Nmax为时隙t内每个用户的最大的文件请求数目,ft,u,n为被请求的文件,tu,n为具
体的文件请求发生的时间;
统状态,at为缓存动作向量,参数θ;根据计算得到的缓存动作向量和当前时隙缓存命中情
况对应得到下一个系统状态,所述系统状态为雾接入点中当前缓存的文件的索引集合;所
述索引为被缓存文件在云服务器上的文件集合中的编号,雾接入点中的本地缓存文件根据
得到的下一个系统状态进行相应的更新操作;
组经验元组对动作值函数相关神经网络进行训练并更新该动作值函数相关神经网络的相
关参数;
件的有序的索引集合作为系统初始状态s0;
合C中的C个文件;
同。
的概率,该用户直接从文件集合C中随机请求一个文件;有 的概率,用户
按照当前的用户偏好矢量进行文件请求;
式(1)所示:
目加1;反之,有 的概率,该被选择文件没有被真正请求,请求数目不变;
为 为时隙t内雾接入点覆盖范围内的所有用户;每
个新用户的初始用户偏好矢量是从用户偏好候选集P={p1,p2,…,pg,…,pG}中随机抽取并
进行适量修改后得到;每个老用户在当前时隙的用户偏好矢量继承上一时隙的用户偏好矢
量;
rect,C] 为当前雾接入点的内容推荐向量,若第c个文件被推荐,则rect,c=β,β≥1,否则
rect,c=1,Φ()为归一化函数;
化:
存在无法从雾接入点中获得的被请求文件时,判决变量m(t)=1,且将该被请求文件填充至
集合M中;当当前时隙内所有用户的文件请求都能从当前雾接入点直接获得时,判决变量m
(t)=0,且集合 在每个时隙开始时,需对集合M进行清空;
所有缓存文件的索引为下一个系统状态。
雾接入点中获取被请求文件ft,u,n的传输成本,b表示从云服务器中获取被请求文件ft,u,n的
传输成本,b‑s表示雾接入点从云服务器中进行一个文件的更新所消耗的传输成本,η表示
用户进行一次请求所要花费的费用。
‑
优决策,从而能够更好地适应用户波动的需求。
附图说明
具体实施方式
的大小,从上述文件集合中抽取F个文件作为雾接入点的原始本地缓存,此时,由于未与用
户请求集合进行交互,所有缓存文件的被请求次数应该都是0,故将F个文件按照序号顺序
降序进行排列,抽取的F个文件的有序的索引集合作为系统初始状态s0;
个文件,每个偏好值都是一个概率,相加之和为1,即用户偏好矢量各项累加之和为1,这也
是后面修改用户偏好矢量后,要进行归一化操作的原因。
作值函数相关神经网络 在使用前,对动作值函数相关神经网络Q(st,at;θ)和目
‑
标动作值函数相关神经网络 进行参数θ和θ的初始化,其中,st为系统状态,at为
缓存动作向量,该系统状态具体为当前雾接入点中缓存的文件的索引集合;
束,在时隙t开始时,雾接入点以广播的形式向其覆盖范围内的所有用户进行内容推荐,推
荐内容即雾接入点中当前所有缓存文件所对应的摘要信息,该摘要信息包括标题或者缩略
图,当缓存文件更新后,推荐内容也进行了相应的更新;
个偏好值,对应文件集合C中的C个文件,每个偏好值都是一个概率,相加之和为1,且每个用
户的用户偏好矢量都是在不断变化的,不断受到推荐内容、用户行为、用户移动模式的影
响;用户的行为指的是每个用户之前的所有文件请求状况;
生过程可分为两种情况:一、用户冲动性请求,用于刻画现实生活中的一些冲动性或者由于
外界命令而产生的文件请求行为,这些往往是不符合用户偏好矢量的,其发生的概率,即用
户冲动请求概率,也较低:此时用户随机请求文件集合C中的一个文件,即此时一定有一个
文件被请求;二、基于用户偏好矢量的用户请求,发生概率为:1‑用户冲动请求概率,这种请
求的发生过程分为两步:首先进行请求文件的选择,之后再决定是否要请求该被选择的文
件,这种情形下,不一定会有一个文件被请求;比如,用户在当前时隙内共先后请求了2个文
件,其中,第一个是基于用户偏好矢量的请求,请求完成之后,立刻作为用户行为修改了当
前的用户偏好矢量,第二个是冲动性请求,文件请求完成后也需要立刻修改当前的用户偏
好矢量,上述修改均对其他用户的偏好矢量没有影响;在这其中,或许该用户还试图进行其
他的基于用户偏好矢量的文件请求(一个或多个),但是都只进行了文件的选择,最终,被选
择的文件并没有被真正请求,这种情况就不会对当前的用户偏好矢量造成任何影响。
且 其中reqt,u为第u个用户在时隙t中的请求集合,Nt,u为
用户u在时隙t内的文件请求数目,其满足Nt,u∈[0,Nmax],考虑到用户对于文件的请求及使
用均需要时间,Nmax为时隙t内每个用户的最大的文件请求数目,当前时隙中,该用户请求的
文件数目达到最大的文件请求数目Nmax时,在该时隙内,该用户将不再进行任何文件请求,
ft,u,n为被请求的文件,tu,n为具体的文件请求发生的时间,用户请求集合
即为深度强化学习中与雾接入点在t时隙进行交互的
外部环境;
用户数量;每个新用户的初始用户偏好矢量是从用户偏好候选集P={p1,p2,…,pg,…,pG}
中随机抽取并进行适量修改后得到,适量修改包括随机交换一些项的顺序,其中交换的项
的个数也是随机的;考虑到现实的用户偏好之间具有相似性和特异性。因此,首先将用户偏
好矢量分为G个大类,即对应G个用户偏好候选矢量,对于新用户,其每个用户偏好矢量从中
进行随机抽取;之后,考虑到用户偏好的特异性,对抽取到的用户偏好矢量再进行适量修
改,这比直接根据Zip分布生成每个新用户的偏好矢量要更符合实际,运算量也更小;每个
老用户在当前时隙的用户偏好矢量继承上一时隙的用户偏好矢量,基于用户移动模式,考
虑到内容推荐的影响可能会有延迟,且为了避免后续时隙内发生对之前已请求文件的重复
性请求,对于老用户,保留他们的所有偏好修改,即每个老用户在当前时隙的用户偏好矢量
继承上一时隙的用户偏好矢量,直到他们离开当前雾接入点覆盖范围;
rect,C] 为当前雾接入点的内容推荐向量,若第c个文件被推荐,则rect,c=β,β≥1,否则
rect,c=1,例如,若C=7,F=3,时隙t内,当前雾接入点中缓存文件对应的索引号为6、2、5
(索引号为文件在文件集合C中的编号,从0开始,0~6,而此时的顺序为请求次数降序排
序),则文件集合C中的索引号为6、2、5的三个文件的标题或者缩略图作为推荐内容以广播
的形式被推荐给当前雾接入点覆盖范围内的所有用户,则此时的内容推荐向量为[1,1,β,
T
1,1,β,β] ,上述向量可以非常直观的标示出被推荐文件在整个文件集合C中的位置,在与
用户偏好矢量pt,u进行哈达玛积计算后,可以使得用户偏好矢量pt,u在被推荐文件位置的偏
好值变为原有偏好值乘以推荐系数β,而其余的文件所对应的偏好值不变,Φ()为归一化
函数,用以保证经过修改后的用户偏好值相加之后仍然为1,这种方式使得推荐对偏好值的
影响,不仅仅与推荐系数β有关,还与被推荐文件原有的偏好值呈正比,即推荐受欢迎的文
件可以取得更好的推荐效果。
一个文件发出重复请求:在时隙t中,对于第u个用户的第n个请求reqt,u,n=
请求完成后,将被请求文件ft,u,n的偏好值设置为一个极小值μ,即 并将修改
后的用户偏好矢量pt,u进行归一化,以确保其所有项的和仍然为1。此外,用户请求文件的顺
序(文件请求发生的时间tu,n先后)也会影响上述偏好矢量的修改,即reqt,u,n造成的偏好矢
量修改(置μ和归一化过程)必须在reqt,u,n‑1造成的偏好矢量修改之后,其可以表示为一个
函数An:
表示,第n个请求对于用户偏好矢量pt,u的修改(请求文件对应的偏好值置μ,整体用户偏好
矢量pt,u归一化)应该在前面n‑1次请求的修改之后进行。且文件请求过程一旦完成,必须要
在前面已经有的请求导致的用户偏好矢量的修改的基础上,立刻进行用户偏好矢量pt,u的
相应修改(请求文件对应的偏好值置μ,整体用户偏好矢量pt,u归一化)。
且有 其中reqt,u为第u个用户在时隙t中的请求集合,ft,u,n
为被请求的文件,tu,n为具体的请求时间;
导致一个文件被请求,用于刻画现实生活中的一些冲动性或者由于外界命令而产生的文件
请求行为,其往往是不符合用户当前的偏好矢量的,其发生的概率即用户冲动请求概率较
低,但当其发生时,用户有很大概率必须去请求上述文件,比如上级对下级的指令,下级必
须要去请求被要求请求的文件;有 的概率用户按照当前的用户偏好矢量进行文
件请求,在这种情况下,文件请求可分为两步:(a)从文件集合C中抽取一个待请求文件,每
一个文件被选中的概率与该用户当前的用户偏好矢量中该文件所对应的偏好值成正比,但
并不是说文件对应的偏好值大就一定可以被选中,偏好值大只是说明其被选中的概率相应
较大;(b)通过伯努利分布对请求过程进行建模,以确定所选文件是否被真正请求,如下面
公式(1)所示:
Nmax];如公式(1)所示,该被选择的文件有 的概率被真正请求,此时,请求数目加1;
反之,有 的概率,该被选择文件没有被真正请求,则该用户在时隙t内的请求数
目不变。综上,在这种情形下,不一定会有一个文件被请求,但是,被抽取的文件所对应的偏
好值越高,其被真正请求的概率也就越高。这也是冲动性请求不能并入(b)中的一个原因,
冲动性请求的文件所对应的偏好值一般不高,若冲动性只体现在文件抽取上,其在(b)中被
真正请求的概率就会极低。
件请求。
雾接入点在t时隙内进行交互的外部环境。
述用户请求模型所产生的时变的用户请求即充当了强化学习的外部环境,若此时有真实的
用户请求数据集合,也可以随时引入训练过程中,成为新的外部环境,或者外部环境的一部
分。
后的被请求次数进行降序排列;这里的降序排序,一是为了系统状态st的唯一性,雾接入点
中的缓存文件顺序也就是时隙t内,索引的排序,即系统状态st,对其排列顺序进行规定之
后,可以保证系统状态st的唯一性,若不进行排序,系统状态st可能会有多种排列组合方式。
二、这种方式可以使得雾接入点中访问次数多的文件在前,这样后面雾接入点中文件更新
时,可以直接替换掉位于最后的访问次数较少的文件。
具体包括:
清空,然后根据当前时隙中的文件请求情况来决定是否进行文件的填充。判断时隙t内所有
用户的文件请求是否都能从当前雾接入点直接获得,定义判决变量m(t),如果m(t)=1,一
些被请求的文件(其可能来自不同的用户)不能从雾接入点中获得,则将这些文件填充至集
合M中,反之,m(t)=0,且
为雾接入点中进行降序排列后的所有缓存文件所对应的索引,若m(t)=1,则从集合M中随
机抽取一个文件来替换当前雾接入点缓存空间中位于末尾处的文件,新更新的文件的被请
求次数默认为0,取降序排列和替换操作后的所有缓存文件的索引为下一个系统状态;
雾接入点中获取待请求文件ft,u,n的传输成本,b(b>>s)表示从云服务器中获取被请求文
件ft,u,n的传输成本,b‑s表示雾接入点从云服务器中进行一个文件的更新所消耗的传输成
本,η表示请求一个文件所要花费的费用,由于在每个时隙,雾接入点只需要向用户广播其
所有缓存文件的“摘要”信息,这部分传输成本忽略不计;
‑
标动作值函数相关神经网络 的参数θ只需复制前者的参数每隔K个时隙进行延
时更新。具体包括:
发明所述的基于深度强化学习框架下带有内容推荐的边缘缓存方法(β=1.5)的单个用户
请求的平均奖励(净利润)明显更优,与传统方法相比增加了近一半;此外,与不带有内容推
荐的相同方法(β=1)相比,缓存效率和收敛性能也得到了提高。