无线网络多基站低时延协作缓存方案研究

于千喻，杨 涛,2，冯 辉,2，胡 波,2,3

(1.复旦大学 信息科学与工程学院 电子工程系，上海 200433; 2.复旦大学 信息科学与工程学院 智慧网络与系统 研究中心，上海 200433; 3. 复旦大学 电磁波信息科学教育部重点实验室，上海 200433)

随着无线通信技术的迅猛发展，移动设备的大量使用以及多媒体服务的不断涌现，移动数据流量呈指数级增长.思科的预测报告[1]表明，2021年全球全年移动数据流量将达到587EB.由于现有网络带宽的限制，以及无线接入网和核心网之间的回程传输瓶颈，故日益增长的数据流量需求无法得到满足.基于此，边缘缓存[2]已成为学术界和产业界关注的热点，即由基站或移动终端等处配置缓存设备以存储部分流行度高的文件，从而减少回程链路之间文件的重复传递数，以减轻核心网络的流量压力.

围绕网络缓存技术学术界开展了广泛的研究.文献[3]中作者提出了一种博弈论方法，使得微基站做决策时能够最大化利用缓存服务的用户数；文献[4]考虑用户的移动性，提出使缓存命中率最大化的动态缓存方案；文献[5]针对组播传输的无线网络，提出使得系统耗能最小的缓存方案.以上研究虽能达到较好的缓存效果，但均未考虑基站之间的合作，鉴于基站之间通常通过高速光纤连接，故也给缓存策略提升效率带来了可优化的空间.即用户请求文件时，如果本地基站未缓存该文件，可首先选择边缘网络及网络中其他缓存有该文件的基站进行传输，否则再通过回程链路从远端文件服务器获取文件.本文考虑基站之间的合作，从网络服务角度讲，可充分利用基站空余的缓存空间，降低传输成本；从用户角度而言，可以减少传输时延，改善用户体验.

针对基站缓存问题，现有文献从不同角度进行了优化建模研究，如用户移动性[4]、能量效率[5]、物理信道状况[6]以及传输时延[7]等.其中，从提升用户体验的角度讲很重要的一个因素是降低获取文件的传输时延.文献[7]假设微基站之间可以合作缓存，作者提出了一种基于分布式最小传输时延模型，但假设相同链路的传输时延相同，即未考虑文件大小对于传输时延的影响；文献[8]提出了一种离线缓存方案，使得所有用户获取文件的时延最小，但假设对不同基站所有文件的流行度(文件被请求次数的期望)均已知并相同；文献[9]中，作者提出了一种贪婪算法，从用户的角度建模，将最小化时延传输问题转化为满足请求最大命中率问题，但是未考虑基站之间的合作.

上述研究文献都假设文件流行度固定且在整个网络中已知，而现实中文件流行度分布并不能事先得到，此时需要对文件的流行度进行动态估计，进而设计更有效的缓存方案.文献[10]用多臂赌博机(Multi-Armed Bandit, MAB)方法，结合更换文件带来的代价，在单个蜂窝网络中，通过更新缓存内容和观察即时请求完成了对文件流行度的估计.文献[11]考虑多个蜂窝网络场景，对传统MAB方法进行改进，进而对文件流行度进行估计，但是并未考虑基站之间的协作缓存.文献[12]针对社交网络利用奇异值分解和协同滤波的方法，结合连接信息完成文件请求概率的估计，文献[13]利用迁移学习对流行度矩阵进行估计.以上文献算法均只使用某段时间窗口内的信息，未利用长时间的在线学习方法.

本文针对上述研究存在的问题，考虑文件流行度未知的多基站协作缓存场景，围绕文件的总传输时延进行了优化问题建模.在组合多臂赌博机(Combinatorial Multi-Armed Bandit, CMAB)[14]框架下，利用文件请求的历史信息进行在线学习，从而生成文件流行度的估计，并进一步给出了启发式文件缓存优化算法.

1 系统模型

假设异构蜂窝网络由一个内容服务器和多个基站构成.内容服务器作为中心节点，文件目录包含了待请求的所有文件；基站可满足部分文件的缓存.服务器可控制、调度和响应基站，配合基站分别对不同区域的用户提供文件服务.为了提高整个网络服务的能力和效率，服务器和基站之间需要联动地设计合理的缓存方案.服务器通过不断接收各个基站缓存特定文件后的反馈，提高对特定文件流行度的认知，进而优化各个基站的文件缓存方案以提高整个网络的服务效率.

图1 协作缓存网络示意图Fig.1 Example of the cache-enabled cooperative networks

如图1所示，网络中多个基站(Base Station, BS)用集合B={1,2,…,b,…,B}表示，每个BS服务于其所覆盖范围内的用户文件请求.不同BS所服务的用户集合使用U={u1,u2,…,ub,…,uB}表示，用户可随机从文件集合K={1,2,…,k,…,K}中选择文件请求，文件的大小由集合S={s1,s2，…,sk,…,sK}表示.不同BS的缓存容量为M={M1,M2,…,Mb,…,MB}.

(1)

假设信道条件平稳，信道平均传输速率恒定[16]，3种传输方式的传输速率定义如下： 基站和用户直接传输的速率为vBD，基站和基站之间的传输速率为vBB，核心网络和基站之间的传输速率为vCB，三者之间满足vBD>vBB>vCB.就系统传输效率而言，首先选择基站直传，其次是基站之间传输，最后为向远端服务器请求.

2 优化问题

本文旨在构建合理的模型来表述异构蜂窝网络服务的时延特性，进而通过缓存优化方案实现低延时的文件下载服务.3种文件传输方案使得用户在周期t请求文件k时存在如下的可能传输时延：

1) 基站b缓存文件k，直接传递给用户，传输时延为

(2)

2) 基站b未缓存文件k，其他基站缓存了该文件，传输时延由基站b从其他基站下载的时延和基站b传输给用户的时延两部分组成，即

(3)

3) 基站b未缓存文件k，且其他基站也未缓存该文件，传输时延由基站b从核心网获取的时延和基站b传输给用户的时延两部分组成，即

(4)

结合式(2)～(4)得出基站b在t周期服务用户请求文件k的时延为

(5)

在t周期定义二元矩阵CB×K={cb,k,t,∀b∈B,∀k∈K,∀t∈T}，其中cb,k,t∈{0,1}代表t周期基站b是否缓存文件k，若cb,k,t=1，则t周期b缓存了文件k，否则t周期b未缓存文件k.式(5)中的c-b,k,t表示t周期除基站b之外其他基站是否缓存文件k.同样，若t周期其他基站缓存了文件k，则c-b,k,t=1，反之，c-b,k,t=0.那么c-b,k,t可以表示为

(6)

基站b每完成一个文件请求都可获得一定的回报.对于某个请求任务，若传输时间长，那么用户体验差，基站单次可获得的回报少，反之若传输时间短，那么基站单次可获得的回报多.假设每个时间周期基站都能完成对于所有请求文件的响应，定义在t周期基站b传递文件k所能获得的回报函数为

rb,k,t=db,k,t(ΔT-lb,k,t)R0,

(7)

其中R0为单位回报常数.由于回报往往是正数，因此ΔT应取lb,k,t的上界.

图2 回报和时延关系图Fig.2 Relaionship between reward and latency

由式(7)，可得到基站b单次请求下的回报rb,k,t和传输时延lb,k,t之间的线性反比关系，如图2所示.因此最大化回报等同于最小化传输时延问题.

(8)

鉴于优化目标希望寻找合理的缓存策略使得在一定时间积累下的期望总回报最大，问题P1可描述为

(9)

式(9)中的约束条件表明基站的存储空间有限，不能将所有文件存储在基站，故基站应尽可能缓存高流行度文件，以获取最大的系统回报.

3 算法原理

对于优化问题P1，若流行度已知，则任意周期下的最优缓存策略都是一致的.由于此处流行度未知，在每个周期t，网络服务器首先需利用对基站缓存文件所得回报的观测更新文件流行度的估计，进而将估计值代入问题P1求解得到优化的缓存方案再配发到各个基站.流行度估计及缓存算法均在网络服务器完成，为集中式算法.算法的迭代可分为流行度估计和NP完全问题求解两步.

3.1 流行度估计

经典的多臂赌博机问题(MAB)[17]是构建未知环境中随机最优决策问题的一类数学工具.赌博机有若干个臂(拉杆)，每个臂对应一定的回报，回报服从固定但是未知的分布.玩家通过拉臂可以观测到即时的回报，通过不断重复调整策略，目的是使得总期望回报最大.MAB的本质是“探索”(尝试更多未尝试的臂)和“利用”(利用当前状态下获得回报最大的臂)之间的权衡问题.若在MAB问题中，每次可有多个臂同时拉下则为组合多臂赌博机(CMAB)问题[14].

CMAB框架下，玩家每次可以选择一个超臂(多个臂的组合)，超臂对应一定回报，玩家通过拉臂可以得到未知分布下的观测，CMAB算法是利用该结果的历史信息决策每轮如何选择最优的超臂以获得最大的回报.在本问题中，可将网络服务器看作玩家，将每个基站-文件对视为赌博机的一个臂，那么在周期t，中心节点决定让基站b存储文件k，表明玩家选择了(b,k)这个臂，对应cb,k,t=1；若决定基站b不存储文件k，则对应的cb,k,t=0.每轮共有B·K个臂可供中心节点在满足公式(9)约束条件的前提下进行多重选择，中心节点每个t周期求解得到的缓存方案At={cb,k,t|cb,k,t=1,∀b∈B,∀k∈K}均为一种超臂方案.在每轮选择超臂方案At后，可观测到超臂中每个(b,k)在周期t所产生的请求db,k,t，据观测结果对流行度的估计进行更新.得到新的流行度的估计后，通过求解优化问题对超臂的选择进行调整，二者相互促进，直到得到最优的超臂.故优化问题P1可等价转化为求解CMAB问题.

参照CUCB算法[14]，本文提出CUCB-PE(Popularity Estimation)算法(见表1).

表1 CUCB-PE算法

为了分析算法CUCB-PE的性能，需要计算损失(regret)，即理论最优收益R(Θ,Copt)和实际收益R(Θ,C)的差值.由于问题P1是NP完全问题，达到理论缓存的最优总收益R(Θ,Copt)计算困难，故考虑算法以β的概率输出最少α倍的最优解，用α·R(Θ,Copt)表示近似的最优总收益.若缓存策略带来的期望收益达不到期望最优总收益，认为该超臂的选择是次优的，定义包含所有可能的次优决策集J={C|R(Θ,C)<α·R(Θ,Copt)}.对于基站b和文件k，定义选取次优决策所带来的最大和最小的损失为[14]

定理2本文提出的CUCB-PE算法经过n轮的迭代后，可以得到损失上界为

证明见参考文献[14].

3.2 NP-完全问题算法求解

优化问题P1是0-1整数规划，求解过程中先用变量替换将其转化为0-1多项式问题，再基于文献[18]转化算法将其转化成0-1线性问题.分析如下：

(11)

(12)

(13)

由上式可见，计算复杂度随着基站数量B和文件数量K呈指数增长.因此为了降低复杂度，本文提出了一种次优的启发式算法.

算法的主要思想是将问题P3松弛为线性规划问题，先求解该线性问题，再把连续的结果映射到{0,1}上，得到近似解.首先将问题P3的最后一个约束条件替换为

(14)

由于问题P3目标函数优化变量的系数均为正数，故问题P3的目标函数是凸函数，故松弛过的线性问题可以在多项式时间内由凸优化方法进行求解，本文选用原始对偶内点法[20]计算方案.算法描述见表2.

由于原始对偶内点法得出的解违背了问题P3中的最后一个约束条件，故不是原问题的可行解.根据松弛后问题的结果，本文提出一种贪婪算法以求得原问题的可行解.将该算法命名为CR(Cache Recover)算法(见表3).

4 仿真对比

本节给出算法的仿真对比分析.参考文献[22]和[23]，通用仿真数据设置见表4.不失一般性，在仿真过程中假设不同基站不同的文件服从无偏移的Zipf分布，即αb设为1，γ设为0.9.

在仿真中，和以下3种算法进行对比：

1) 分支定界算法(B&B)： 得到缓存最优解.

2) 最小频率使用算法(LFU)[24]： 记录文件缓存次数，若请求文件未缓存，则替代掉使用频率最小的文件.

3) 最小最近使用算法(LRU)[24]： 记录最近2次使用次数的间隔，若请求文件未缓存，则替代掉间隔长的文件.

图3见第238页为以上3种算法和本文算法的缓存回报对比图，横轴为迭代次数，纵轴为缓存回报.本文算法初始化阶段对单个文件逐一进行缓存尝试，因此这段周期不具备可比性.从图中可以看出，迭代20次时开始，本文算法与最优解的缓存回报已非常接近且呈现收敛趋势，明显优于另外两个对比算法.对比算法与初始化强相关，且未对文件流行度进行估计，同时未考虑基站之间的合作，故本文提出的算法明显优于对比算法.

图3 不同算法的缓存回报比较Fig.3 Caching reward comparison among different algorithms

图4对3种算法的累计损失性能进行比较，横轴为迭代次数，纵轴为损失的对数.累计损失函数的计算方法为： 每个周期t，将Zipf分布参数固定且已知的最优回报(由分支定界算法确定)与同周期算法回报作差得到当前周期的净损失，并对到t周期为止的净损失进行求和得到t周期的累计损失.为了使效果更加显著，将损失函数取对数，得到对数化损失lg(reg).从仿真图中可以看出，在1000次迭代以后，3条曲线接近平行，但由于对数化损失函数进行了以10为底的对数化处理，故纵坐标的每个刻度之间有着数量级的差别，实际上随时间的增加，本文算法的累计损失绝对值和增速均远远小于对比算法的2条曲线.

图4 不同算法的对数损失比较Fig.4 Logarithm of caching regret comparison of different algorithms

图5 缓存回报和存储容量比的关系Fig.5 Caching reward versus the percentage of caching memory

图6 缓存回报和Zipf分布参数的关系Fig.6 Caching reward versus γ

图7 缓存回报和文件数量的关系Fig.7 Caching reward versus number of contents

图6表征了缓存回报和Zipf分布参数γ之间的关系，γ的范围设定在0.7～1.9之间，纵轴为运行100次回报取平均值.如仿真结果所示，缓存回报随着γ的增加而增大.理由是当γ较大时，更多的请求来自于少数更为流行的文件，则基站缓存同样数目流行度高的文件可满足更多的用户请求，进而获得更高的回报.

图7见第238页显示了缓存回报和文件数量之间的关系，横轴为文件数量，纵轴为运行100次回报的平均值.文件数量K的仿真参数范围设定在10～100之间，每个基站的存储容量调整为300.随着文件数量的增加，同样的缓存容量下缓存回报逐渐减少，这是由于尽管流行度分布的偏度不变，但文件个数的增多使得用户请求被分散在更多不同的文件中，基站的自身缓存就相对更难覆盖用户的请求.

5 结 语

本文研究了流行度确定但未知场景下的多基站缓存问题，基于传输时延最小化进行分析建模，同时考虑基站之间的协作缓存.对于用户请求，若基站未缓存该文件，则从其他基站进行传输，若其他基站未缓存，则通过回程链路传输，由于基站之间的合作大大降低了中心网络的回传压力，降低了传输时延，提升了用户体验.鉴于文件请求的流行度未知，使用CMAB对其进行实时估计.本文提出的文件缓存优化问题本身为0-1多项式问题，将其转化为0-1线性问题后依然是NP完全的，为了减少计算复杂度，提出启发式算法进行求解.仿真部分对本文提出的算法及常用算法在不同环境条件下进行了缓存回报和损失的对比，从存储容量、流行度分布及文件数量等多个角度证明了本文算法应对不同环境的鲁棒性以及接近于最优解的性能和线性的计算复杂度.