近年来，激增的数据流量[1]给网络带来巨大的负载压力，使用户体验受到严重影响．边缘内容缓存[2]技术将网络中的流行内容缓存在靠近用户的边缘服务器中，可极大缩短用户获取内容服务的时延，降低网络回程链路的压力[3]．此外，高速有线网络连接的边缘服务器所组成的连通边缘网络可协作缓存并分发网络流行内容[4]．与非协作的方式相比，协作内容缓存不仅可以扩展边缘服务器的缓存空间，还可以降低用户访问远程中心网络的频率，进一步提升用户的服务体验[5]．有关协作内容缓存的问题受到广泛研究，文献[6]从经济角度出发，设计了一种多内容提供商的缓存资源拍卖机制．文献[7-9]分别提出高效的协作内容缓存算法以优化用户获取内容服务的平均时延．同时文献[9]利用用户对内容的历史请求记录，提出一种增大用户对内容访问命中率的强化学习算法．文献[10]设计一种基于深度学习的协作内容缓存方法，降低了回程链路的数据压力．文献[11]提出一种基于李雅普诺夫优化的在线算法以减小内容迁移等系统代价．文献[12]在内容提供商存储预算的约束下提出一种最大内容提供商利益的近似算法．以上研究主要集中在优化用户的平均时延及网络的平均性能等方面，存在因用户获取内容服务质量失衡引发的用户公平性问题，即部分用户获取内容服务的时延很短，而部分用户获取内容服务的时延较长．本研究在用户对内容服务时延敏感度存在差异的情况下，研究保证用户公平性的内容缓存策略．提出一种快速高效的启发式算法，该算法能根据单位预算提升的最小效用和总效用定义内容及边缘服务器组合的优先级，贪心选择高优先级组合更新缓存策略．为进一步优化解，定制了一个以启发式算法的解为初始解的模拟退火算法．实验证明所提出的两种算法可有效保证用户的公平性．1 系统模型与问题定义1.1　网络模型系统模型如图1所示，边缘网络中有n台边缘服务器通过高速有线网络连接，服务器之间构成连通网络，边缘服务器为其覆盖范围内的用户提供网络服务．用户只能选择一个边缘服务器(通常是最近的)连接网络，被选择的边缘服务器为用户的本地服务器．设N={1,2,⋯,n}，集合V={v1,v2，⋯,vn}表示边缘服务器的集合，其中vi (i∈N)为第i台边缘服务器，设ci为vi的存储空间大小．中心网络中有一个内容提供商为用户提供内容服务．由于边缘服务器与内容提供商之间通信须要经过很多网络设备(如路由器)，因此边缘服务器与内容提供商之间的通信链路是低速的．为提高用户的服务体验，内容提供商须将内容缓存至靠近用户的边缘服务器中．内容提供商的存储预算表示为B．设M=1,2,⋯,m，内容提供商持有的内容集合为F={f1,f2,⋯,fm}，其中fj (j∈M)为第j份内容．10.13245/j.hust.220221.F001图1系统模型1.2　缓存模型令向量X=(x11,x12,⋯,x1m,x21,x22,⋯, x2m,⋯,xn1,xn2,⋯,xnm)表示内容的缓存策略，其中xij∈{0,1}表示fj是否缓存在vi中，xij=1表示vi中缓存了fj，xij=0表示vi中未缓存fj．设Vj表示所有缓存fj的边缘服务器集合，则有Vj={vi|xij=1,∀i∈N}．每个内容的大小是不相同的，设sj表示fj的大小．令ai表示vi所缓存内容占据的总空间，则有ai=∑j=1mxijsj．(1)令pi表示vi单位存储空间的价格，R表示内容提供商用于内容缓存的总花费，则有R=∑i=1n∑j=1mxijsjpi．(2)1.3　时延模型用户获取内容服务的时延大小为经过路由器的个数[11-12]．图1中用户1访问本地服务器v1没有经过路由器，时延为0跳；访问v2经过一个路由器，时延为1跳；访问v3经过两个路由器，时延为2跳．当本地服务器缓存了请求内容时，用户可在本地服务器获取内容服务；当本地服务器未缓存请求内容，但有其他边缘服务器缓存了请求内容时，用户可从缓存了请求内容的边缘服务器集合及内容提供商中选择时延最小的方案获取内容服务；当所有边缘服务器都未缓存请求内容时，用户将通过本地服务器直接从内容提供商获取内容服务．设Di为vi与中心网络的时延，dik为vi与vk的时延，其中i,k∈N．设tij为vi的用户获取fj的时延，则有tij=min{min{dik|∀vk∈Vj},Di}．1.4　用户效用模型用户获取内容服务质量的好坏(主要与时延有关)视为用户的效用．假设用户获取内容服务的效用满足函数H(s,t)，其中s和t分别为内容的大小和用户获取内容服务的时延，随着t增大，效用减小．由于用户对内容服务的时延敏感度存在差异，因此不同内容会对应不同的效用函数．设Hj(sj,tij)为vi的用户获取fj的效用函数，uij为vi的用户获取fj的效用大小，则有uij=Hj(sj,tij)．(3)设Ui为vi的用户获得的效用，根据式(3)有Ui=∑j=1muij．设函数Umin(X)为缓存策略为X时用户的最小效用，则有Umin(X)=min{Ui,i∈N}．(4)函数U(X)为缓存策略为X时用户获得的总效用，U(X)=∑i=1nUi．1.5　问题定义为保证用户获取内容服务的公平性，构建了一个协作内容缓存问题，目标是最大化用户的最小效用．问题𝒫的形式化表达为：(𝒫) maxUmin(X);s.t. (1),  (2),  (4),R≤B，(5)ai≤ci，(6)xij∈{0,1}．式中B为存储预算．约束(5)表示内容提供商缓存内容的花费不能超过存储预算，约束(6)表示边缘服务器缓存内容占据的空间不能超过自身的存储空间．定理1 问题𝒫是NP难解的．证明 不考虑边缘服务器的存储约束且用户只能从本地服务器获取内容服务．为最大化用户最小效用，内容提供商的存储预算应按照存储价格的比值分配到各个边缘服务器．于是问题转换为在存储预算约束下往一个边缘服务器中缓存内容以最大化用户的效用．若将存储预算视为背包容量，内容的存储花费视为物品体积，内容带给用户的效用视为物品价值，则问题可以归约为背包问题．由于背包问题是NP难解的[13]，因此问题𝒫也是NP难解的．2 算法设计由于问题𝒫是NP难解问题，若采用蛮力法等经典算法求解问题𝒫的最优解，算法的时间复杂度将极高．此外，由于目标函数是分段函数，函数取值的不同会导致目标函数呈线性与非线性变化，因此难以将问题𝒫的约束条件线性松弛后，采用随机舍入方法构造通用求解算法．本研究设计了快速高效的启发式算法(HA)和模拟退火算法(SA)来解决所提出的问题，模拟退火算法将启发式算法的结果作为初始解，进一步优化解的质量．2.1　启发式算法为在存储预算的约束下尽可能增大用户的最小效用，启发式算法采用迭代求解的方式来更新内容缓存策略．每次迭代，算法都做出使单位预算提升的最小效用量最大的决策．定义1 (候选组合)给定缓存策略X，如果将fj缓存到vi后仍满足约束(5)和(6)，那么记〈vi,fj〉为X的一个候选组合．定义2 (优先级)给定缓存策略X，其候选组合〈vi,fj〉的主优先级为将fj缓存到vi后用户最小效用的增量与缓存花费的比值，次优先级为将fj缓存到vi后用户总效用的增量与缓存花费的比值．设向量Yij=(y11,y12,⋯,y1m,y21,y22,⋯, y2m,⋯,yn1,yn2,⋯,ynm)表示在X的基础上将fj缓存到vi后的内容缓存策略，yi'j'∈{0,1} (i'∈N，j'∈M)表示fj'是否缓存在vi'中，并满足当i'=i∧j'=j时，yi'j'=1，其余情况yi'j'=xi'j'，其中xi'j'为X的元素，表示fj'是否缓存在vi'中．令lij和gij分别表示〈vi,fj〉的主优先级和次优先级，由定义2可得：lij=Umin(Yij)-Umin(X)pisj；(7)gij=U(Yij)-U(X)pisj．(8)每次迭代过程中，算法首先计算候选组合的集合，然后计算每个候选组合的主优先级和次优先级，贪心地选择主优先级或次优先级最大的候选组合更新缓存策略．算法核心步骤的具体描述如下．步骤1 初始化缓存策略X为0．步骤2 求出X的候选组合集合，若候选组合的个数为0，则输出缓存策略X，算法终止．根据式(7)和(8)计算所有候选组合的优先级lij和gij．步骤3 找出主优先级的最大值lijmax及次优先级的最大值gijmax．若lijmax和gijmax均为0，则输出缓存策略X，算法终止；若lijmax0，则选择lijmax对应的候选组合，否则选择gijmax对应的候选组合．设被选择的候选组合为〈vi,fj〉，则更新缓存策略X，将xij置为1，转步骤2．定理2 启发式算法的时间复杂度为O(mn)．证明 候选组合的数目最多为mn，每次迭代的时间复杂度为O(mn)．因为迭代次数最多为常数B，所以启发式算法的时间复杂度为O(mn)．2.2　模拟退火算法启发式算法得到的只是一个优质近似解，算法容易陷入局部最优．模拟退火算法是一种元启发式算法，常用于解决难解的组合优化问题．该算法通过一定概率接受劣解，可有效避免陷入局部最优．相比其他元启发式算法，模拟退火算法具有参数量少、收敛性好、鲁棒性强等特点；因此，为避免所得结果陷入局部最优，采用定制的模拟退火算法对启发式算法的解进一步优化．模拟退火算法的各个要素定义如下．a. 编码方法：编码方式为缓存策略X组成的0～1序列．b. 目标函数：以用户的最小效用作为目标函数．c. 移动与邻域：在X中随机选择1个元素的值进行改变来获得X的邻域，即把0变成1，或把1变成0．d. 参数设置：初始温度λ为1 000，终止温度T为0.01，冷却因子ε为0.99，降温方式为λε，内循环次数为1 000次．e. 停止准则：当λT时，算法终止．设cx为当前解，cr为当前解对应的目标函数值，bx为历史最优解，br为目标函数的历史最优值．算法核心步骤的具体描述如下．步骤1 给定模拟退火算法的初始参数，利用启发式算法得到的解X作为初始当前解cx，将X对应目标函数的值作为cr．步骤2 初始化bx的值为cx，br的值为cr．步骤3 从cx的邻域中随机选择一个邻域解nx，判断nx是否满足问题𝒫的约束(5)和(6)，若不满足，则转步骤6．步骤4 根据式(4)计算nx对应的目标函数值nr，设Δr=nr-cr，若Δr0，则更新cx为nx，否则以e-Δr/λ的概率接受nx．步骤5 若nrbr，则更新bx的值为nx，br的值为nr．步骤6 若已经达到内循环的次数，则转步骤7，否则转步骤3．步骤7 λ=λε，若满足停止准则，则输出历史最优解bx，算法终止，否则转步骤3．3 实验结果与分析使用Java编程语言进行仿真数值实验．考虑到边缘服务器所属厂商和型号存在区别，实验中不考虑存储价格、存储空间及存储预算的单位，只考虑它们的相对大小[12]．设置参数n从10增至30，步长为5，默认大小为20，m从5增至25，步长为5，默认大小为15．ci服从正态分布N(μ,σ2)，其中：μ为边缘服务器的平均存储空间，从5增至25，步长为5，默认大小为20；σ为标准差，取值为1[12]．B从40增至120，步长为20，默认大小为120，pi为[1,3]范围内的随机整数，sj为[1,5]范围内的随机整数，Di=10．针对每个内容服务，从以下三种函数中等概率地选择一种作为用户对应的效用函数[14]，其中系数z为其在相应效用函数给定取值区间内的随机整数．实验结果都是在相同的配置下重复100次后取平均值得到．a. 效用函数1：H(s,t)=zs(3-t)    (t≤3,z∈[1,3]);0    (t3,z∈[1,3]).b. 效用函数2：H(s,t)=zs    (t≤3,z∈[1,9]);0    (t3,z∈[1,9]).c. 效用函数3：H(s,t)=zset+1    (t≤3,z∈[12,20]);0    (t3,z∈[12,20]).将HA算法和SA算法与最小总时延算法(MDA)及CEDC-A算法[12]进行比较．MDA算法会优先将内容缓存在使用户总时延减少量与存储花费比值最大的边缘服务器中，而CEDC-A算法会优先将内容缓存在使用户总效用增幅最大的边缘服务器中．为衡量用户获取内容服务的公平度，引入Raj Jain's公平指数[15]作为性能对比指标，根据Raj Jain's公平指数的定义并结合研究的问题，用户的公平指数定义为𝒥(U1,U2,⋯,Un)=∑i=1nUi2/n∑i=1nUi2．(9)实验中根据式(9)得到的用户公平指数取值范围为[1/n,1]，值越大说明用户之间越公平．图2和3分别给出了在不同参数设置下各缓存策略的最小效用(Umin)和公平指数(J)两项性能指标的差异．由图2(a)和图3(a)可知：当服务器的平均存储空间变化时，在用户的最小效用上，HA算法和SA算法相比两个对比算法表现更佳，SA算法表现最好．随着平均存储空间的增大，单个边缘服务器中可以缓存更多的内容，用户的最小效用会逐渐提升．与MDA算法和CEDC-A算法相比，HA算法平均提升了101.3%和78.5%，SA算法平均提升了106.3%和87.3%．在用户的公平指数上，HA算法和SA算法也同样优于MDA算法和CEDC-A算法，HA算法平均提高0.06和0.03，SA算法平均提高0.08和0.05，并且HA算法和SA算法的公平指数均保持在0.92以上．10.13245/j.hust.220221.F002图2不同参数设置下各策略的最小效用对比10.13245/j.hust.220221.F003图3不同参数设置下各策略的公平指数对比由图2(b)和图3(b)可知：随着服务器数目增多，用户的公平性更加难以保证，用户的最小效用及公平指数会逐渐降低．尽管如此，在用户的最小效用上，HA算法和SA算法依然表现更佳．相比MDA算法和CEDC-A算法，HA算法平均提升102.9%和121.8%，SA算法平均提升116.9%和137.8%．在用户的公平指数上，相比MDA算法和CEDC-A算法，HA算法平均提高0.04和0.03，SA算法平均提高0.07和0.05．由图2(c)和图3(c)可知：随着存储预算的增加，内容提供商在服务器中可缓存的内容数变多，用户的最小效用有上升趋势．在用户的最小效用上，相比MDA算法和CEDC-A算法，HA算法至少分别提升120.1%和104.3%，SA算法至少分别提升123.2%和115.0%．在用户的公平指数上，相比MDA算法和CEDC-A算法，HA算法平均提高0.09和0.04，SA算法平均提高0.14和0.08．由图2(d)和图3(d)可知：随着内容数目增多，HA算法和SA算法可从内容集合中选择使用户效用提升大的内容缓存到服务器中，因此用户的最小效用会逐渐增大，而MDA算法和CEDC-A算法一直处于较低的水平．在用户的最小效用上，相比MDA算法和CEDC-A算法，HA算法平均提升96.8%和95.4%，SA算法平均提升108.6%和107.0%．在公平指数上，由于内容数目增多，用户的公平性更加难以保证，因此公平指数会逐渐降低．尽管如此，HA算法和SA算法的公平指数仍都保持在0.9以上，相比MDA算法和CEDC-A算法，HA算法平均提高0.04和0.03，SA算法平均提高0.06和0.05．总的来说，在多种不同参数设置的情况下，提出的HA算法和SA算法均表现更佳．MDA算法和CEDC-A算法为减小用户总时延和增大用户总效用，可能会在连接其他服务器较多的单个服务器中缓存较多的内容，从而导致用户获得的效用产生严重的两极分化，造成用户获取内容服务的极度不公平．与MDA算法和CEDC-A算法相比，HA算法总是做出提升用户最小效用的缓存决策，使各个用户获得的效用均衡增长；因此，在实验结果中，HA算法会优于MDA算法和CEDC-A算法的表现，能更好地保证用户获取内容服务的公平性．SA算法将HA算法求得的结果作为初始解，然后进行模拟退火过程，通过以一定概率接受劣质解跳出局部最优，进一步优化了解的质量．4 结语在用户对不同内容服务时延敏感度存在差异的情况下，为保证用户获取内容服务的公平性，提出一个协作内容缓存问题，目标是在内容提供商存储预算及边缘服务器存储空间的约束下，最大化用户的最小效用．设计了快速高效的启发式算法和以启发式算法的解为初始解的模拟退火算法．研究结果表明：相比现有内容缓存方法，提出的两种算法可以显著提升用户的最小效用，并能更好地保证用户的公平性．