多缓存容量场景下的D2D内容缓存布设优化方案

龙彦汕，吴 丹，蔡跃明，王 萌，郭继斌

0 引言

终端直传(Device-to-Device，D2D)通信由于允许邻近的通信双方可以不经过基站直接通信，成为缓解蜂窝回程压力的关键技术之一［1］。更进一步地，借助于网络中大量分散的用户终端缓存资源，基于分布式缓存的D2D通信技术更利于减轻基站负载，确保用户的服务体验，使得内容分发具有高可扩展性和低成本优势［2－3］。但是，由于用户设备的缓存容量有限以及用户对于不同内容的偏好不同，缓存什么内容、由哪个位置的用户来缓存，即缓存布设方案，成为影响缓存效率的关键因素，也是想要获取缓存增益必须解决的问题。近年来，考虑到移动用户的移动性和空间随机分布的特点，越来越多的研究者开始利用随机几何理论来建模动态的网络拓扑结构以及在D2D缓存网络中内容的可获得性［4－9］。

文献［4］假设缓存用户和请求用户服从相互独立的齐次泊松点过程，将分布式缓存的布设优化问题建模为平均缓存命中率的最大化问题，提出了低复杂度的最优对偶搜索算法;文献［5］在此基础上进一步考虑内容传输过程中信道衰落的影响，对每个文件的覆盖概率进行分析，在假设每个节点只能缓存一个文件的条件下，以网络中文件总的覆盖概率为目标函数进行缓存方案优化;文献［6］利用随机几何理论得到D2D缓存网络中缓存辅助的网络吞吐量，并通过数值仿真获得最优缓存概率;文献［7－8］根据用户对内容的不同偏好将网络用户分组并得到最大化网络收益的缓存策略，但是两者依然假设所有用户缓存容量相同，而且后者只考虑一个文件的情况。在实际的蜂窝网络中，移动用户所携设备的缓存容量大小是不同的，而每个终端缓存已使用情况的特殊性使得这一情况更加突出。上述文献都假设所有缓存节点具有相同的缓存容量的情况，由此获得的最优缓存布设方案并不能直接应用于缓存容量多样的情况。此外，虽然文献［9］在静态网络拓扑的假设下研究小蜂窝基站缓存容量不同以及文件大小不同的情况下最小化回程链路速率的编码缓存方案，但该方案并不适用于D2D缓存网络。如上文所述，在D2D缓存网络中，用户移动性导致的位置不确定性，使得网络拓扑结构是动态变化的;加之用户对不同内容的偏好程度不同以及具体请求内容的不确定性，使得在静态拓扑结构下得到的最优缓存布设方案只适用于某一时刻的网络需求。为了满足时变的动态网络需求，则需要频繁地更新最优缓存策略，势必带来较高的复杂度并且较难实现［11］。因此，如何设计在动态网络拓扑环境下的多用户多缓存容量的内容缓存布设方案仍亟待研究。

因此，针对D2D缓存网络中用户缓存能力异质的特点，本文利用随机几何理论建模不同缓存容量大小的用户位置分布，分析了多用户多缓存容量情况下的缓存命中率。在此基础上以最大化缓存命中率为目标设计了适用于任意多种缓存容量大小的缓存布设方案，提出了基于坐标梯度优化的联合缓存布设(Joint Cache Placement，JCP)算法。仿真结果表明，与现有的几种缓存布设方案相比，通过JCP得到的缓存布设方案可以获得更高的缓存命中率。

1 系统模型

考虑如图1所示的D2D缓存网络，网络中所有用户的位置服从密度为λ的齐次泊松点过程(Homogeneous Poisson Point Process，HPPP)Φ［4］。在现实情况中，移动用户手持终端的缓存容量大小不等，例如，常见的智能手机有32 GB、64 GB、128 GB等硬盘容量大小，常见的笔记本电脑有256 GB、512 GB、1 TB等硬盘容量大小。显然，终端缓存容量大小与用户位置之间相互独立，并且持有不同缓存容量终端的用户位置之间也相互独立。因此，假设网络中共有K种不同缓存容量的移动用户终端，终端缓存容量为Mk的用户个数占总用户数的比例为0＜τk＜1。根据HPPP的稀释定理，可知对于k∈{1，2，…，K}，缓存容量为Mk的用户位置分布服从密度为λk=τkλ的齐次泊松点过程Φk，称为第k类用户。显不同缓存容量的用户位置之间相互独立。考虑拥有N个文件的数据库，假设所有文件具有归一化大小，在内容请求方面，用户总是对当下最流行的多媒体内容感兴趣，即大部分的用户频繁地请求少部分的内容;而且一个内容越流行，被用户请求的概率越大。文献［10］研究了计算机网络中网页请求的分布情况，表明网页请求的分布可以用Zipf分布来近似;更进一步，在文献［11］中，作者通过对YouTube等视频点播平台上大量用户的请求数据，分析了视频文件的请求分布统计特性，结果表明，视频文件的请求分布也可以由Zipf分布来近似。因此，假设每个用户按照Zipf分布独立地从N个文件中请求文件，则流行度排名第i的文件被请求的概率可以表示为:其中，ν为内容流行度参数，表征文件被请求的密集程度。ν越大，大部分用户集中请求的流行文件数越少。显然q1＞q2＞… ＞qN。与传统的服务器-客户模式不同，在D2D缓存网络中，终端用户既是缓存提供者又是文件请求者。因此，当请求用户发起文件请求，有3种方式获得所需文件:1)自卸载:当用户已经缓存该文件，可以立即从本地缓存获得该文件;2)D2D卸载:当本地未缓存所需文件时，由距离请求用户R范围内已缓存目标文件的缓存用户通过D2D通信发送该文件;3)蜂窝卸载:当前两者都无效时，该请求将转由其服务基站通过回程链路从核心网络获取。由于本文是以最大化D2D缓存网络的缓存命中率为目标来优化缓存布设方案，因此暂不考虑蜂窝卸载的情况。

图1 多缓存容量下的D2D缓存网络示意图Fig．1 Schematic diagram of D2D caching network with heterogeneous cache capacities

由于用户位置的随机分布以及请求内容的不确定性，本文考虑基于概率的缓存布设方案［11］。假设第k类缓存用户的缓存方案为 bk= ［ck1，ck2，…，ckN］，其中0≤cki≤1 表示缓存容量为Mk的用户缓存文件Fi的概率。所有用户的缓存方案表示为A［cki］K×N。根据HPPP的稀释定理可知，缓存用户Φk中缓存文件Fi的用户服从密度为λki=λkcki的齐次泊松点过程Φki。此外，在半双工模式下，用户不能同时作为D2D通信的发送者和接收者，因此，假定某个时刻网络中发起D2D请求的用户比例为β∈［0，1］，余下的用户成为潜在的D2D发送者。因此，Φki中潜在的D2D发送者服从密度为=(1－β)λ=(1－β)λc的齐次泊松点过程kikki

2 缓存命中率分析

缓存命中率定义为任意请求用户可以在自己的缓存或者周边R范围内找到目标文件的概率，主要由自缓存命中率和D2D缓存命中率两部分构成［6］:

2．1 自缓存命中率分析

当第k类用户请求文件Fi时，如果该用户已经缓存文件Fi，那么他可以立刻通过自卸载获得该文件。这一事件发生的概率为。进而，考虑请求用户缓存容量以及被请求文件的不同可能性，根据全概率公式可以得到自缓存命中率为:

2．2 D2D缓存命中率分析

当请求用户没有缓存自己需要的文件时，则向邻近的缓存用户发送请求。如果在请求用户半径为R的区域内存在缓存该文件的用户，D2D缓存命中。当第k类的用户向周边用户请求文件Fi时，D2D缓存命中的概率为:

其中，ak=πR2(1－β)λk表示请求用户半径R范围内的第k类缓存用户的平均个数。将式(5)代入式(4)中，并根据全概率公式，可得D2D缓存命中率为:

与只有一种缓存容量的情况［6］相比，多种缓存容量带来的影响主要体现在:1)请求用户的缓存容量是不相同的，从而导致其自卸载概率的不同，在式(7)中主要体现在对第j类请求用户出现概率τj的全概率求和;2)请求用户半径R内缓存目标文件的缓存用户的缓存容量大小不确定，在式(7)中主要体现在指数项中对K种情况的全概率求和。当K=1时，式(7)可以退化成与文献［6］相吻合的结论，即:

当K=1并且不考虑自卸载情况时，式(7)进一步退化成文献［4］的结论，即:

3 最优缓存布设方案

如上所述，本文的目标是在考虑多缓存容量的情况下获得最大化缓存命中率phit的最优缓存布设方案A。

上述问题可以表示为:

其中，第一个约束表示每一类用户缓存的平均文件个数不能超过其缓存容量大小。

网络拓扑的随机性以及用户终端缓存能力互异的特点使得缓存命中率的求解需要对多个随机变量进行全概率求和，而不同缓存容量用户的缓存布设方案之间的耦合关系使得目标函数关于A是非凹的。因此，为了解决不同缓存容量用户策略相互耦合的问题，本文将退而求其次，分析当给定其他类用户策略时，针对某类用户的缓存策略是否具有凹性。将除了第k类缓存用户策略bk以外的其他类用户的缓存分布策略{b1，…，bk－1，bk+1，…，bK} 表示为 A－k= ［cji］(K－1)×N。那么，对于任意k，当给定A－k时，phit的表达式可以重新表示为:

经过两次求导计算，可得phit关于bk的二阶偏导数为由此可知phit的海森矩阵是负定矩阵，这说明phit是关于第k类用户缓存布设方案bk的严格凹函数。

根据这一特性，把原问题转化为对每种缓存容量大小的用户缓存策略的序列迭代求解。对于任意给定的缓存分布策略A－k，原问题转化为对第k类用户缓存策略优化的子问题，表示为:

其中，μk为保证缓存容量约束的拉格朗日乘子。根据phit的局部凹性可知，利用Karush-Kuhn-Tucker最优化条件可以得到子问题的最优解并经过整理后，可以得到:

从式(18)可以看出，不同缓存容量的缓存策略与对应的用户密度有关，对于固定的某种缓存容量来说，不同文件的缓存概率与其流行度qi有关。由于Lambert-W函数在非负区间是关于变量的单调增函数，因此μk越小以及qi越大，则cki越大。为得到D2D网络中所有缓存用户缓存布设方案，提出基于坐标梯度的联合缓存布设算法，具体步骤如下:

算法中，ξ1是外部循环用于判断算法是否达到最大缓存命中率的误差精度，ξ2是内部循环用于判断缓存的内容总数是否达到缓存容量的误差精度。一般情况下，误差精度越小，对应的该循环收敛所需要的迭代次数越多，反之亦然。Tmax是为防止算法陷入无限循环而设置的迭代次数门限。由于原问题的可行集合为闭集并且目标函数有下界，可知通过该算法至少可以得到一个原问题的局部最优解。通过第5)步到第13)步的判断，如果算法收敛，将立刻跳出外部循环。因此，算法外部循环的实际迭代次数主要通过第5)步到第13)步来决定。假设外部循环实际的最大迭代次数为T(T≤Tmax)，算法第5)步到第13)步通过二分法来寻找以及对应的最优缓存方案的最大迭代次数是I，那么上述算法的计算复杂度为O(KNIT)。

4 仿真结果及分析

本章主要通过数值仿真对所提JCP算法进行有效性验证。

根据前文可知，JCP算法可以保证至少收敛到一个局部最优解，但是由于原问题的非凹性，不同初始值可能会导致JCP算法收敛到不同的局部最优解［8］。因此，为了评估初始值设置对算法收敛性的影响，图2描绘了在不同文件数以及不同缓存容量的用户占比等多种场景下，算法采用不同缓存布设初始值A0时的收敛曲线。以 K=2 为例，Zero Init．表示 A0=0K×N为零矩阵;Unif．Init．表示对于每个 k通过图中多条曲线对比可知，即使采用不同的A0，JCP算法都可以用几次迭代收敛到相同的局部最优解，这说明JCP算法对A0的不同取值并不敏感。

为了评估JCP算法的性能，将JCP与另外三种缓存布设方案进行对比并分析系统参数对算法有效性以及网络缓存命中率的影响。三种对比算法分别为:1)针对不同的缓存容量用户，各自独立地计算最优缓存布设方案(Separate Cache Placement，SCP)［6］;2) 根据内容流行度进行缓存(Adaptive cache placement，ADA)［15］;3)根据缓存容量大小，等概率地缓存不同文件(Uniform cache placement，UNI)［16］。为了使仿真结果更具说服力，以下仿真均考虑K=2和K=3两种情况。考虑到现实场景中用户终端容量大小均以2的幂次方呈现，因此，当 K=2 时，M1=1，M2=2，τ1= τ2=0．5;当 K=3时，M1=1，M2=2，M3=4，τ1= τ2= τ3=1/3。此外，除非特殊说明，以下仿真参数设置不变:N=5，λ=0．01(users/m2)，ξ1=10－4，ξ2=10－4［16］，β =0．5，ν =0．8，Rd=10 m。

图2 缓存布设方案初始值对算法收敛性的影响Fig．2 Effect of cache placement initialization on convergence

图3描绘了不同内容流行度参数ν情况下，JCP与其他三种基准算法的缓存命中率曲线。由图可知，均匀缓存方案由于不受请求概率影响，因此其对应的缓存命中率不随ν变化，而其他方案的缓存命中率均随ν的增加而提高。纵向对比四种缓存方案，不难发现，JCP始终要优于其他三种方案。值得一提的是，根据理论分析可知，JCP的优越性主要来源于多种缓存容量共存的网络中，不同缓存策略的耦合关系对D2D卸载方式产生影响。通过图3中JCP与SCP的对比可见:当ν=0时，用户对所有文件的兴趣相同，因此在每种缓存容量的用户缓存内肯定都会均匀缓存各个文件，此时JCP与SCP效果相同;随着ν的增大，JCP优越性先变大再缩小，在ν=1．8时，只有少量的优势，这是因为此时用户集中请求的文件很少，这种情况下每个请求用户都主要以自卸载方式来满足文件需求。

图4描绘了不同请求用户比例β情况下，JCP算法与其他三种算法的缓存命中率曲线。由图可知，请求用户比例越大，系统缓存命中率越小，这是因为β越大，潜在的D2D发送者越少，缓存用户之间无法充分利用邻近用户的缓存资源。当β=1时，所有的用户都发送文件请求，此时他们只能采用自卸载模式，而无法参与D2D内容分发，此时，缓存命中率等于自卸载概率。由于文件的自给自足使得此时所有用户的缓存和请求之间都是相互独立的，因此JCP算法与SCP算法性能相同。除此以外，在整个β的区间，JCP算法都可以获得相比其他三种算法更高的缓存命中率。

图3 缓存命中率随内容流行度参数ν的变化曲线Fig．3 Cache hit ratio versus content popularity factor ν

图4 缓存命中率随请求用户比例β的变化曲线Fig．4 Cache hit ratio versus requesters’proportion β

图5进一步分析了不同的D2D通信距离约束R情况下，四种算法的性能比较。由图可知，随着R变大，每个请求用户周围能够为其提供D2D服务的缓存用户数据增多，缓存命中率也随之增大。通过不同算法的对比可知，不同R条件下，JCP仍然始终保持优于其他三种方案。

图5 缓存命中率随D2D通信距离约束R的变化曲线Fig．5 Cache hit ratio versus D2D communication distance constraint R

综上所述，图2从侧面说明算法的低复杂度，图3到图5则从不同的角度揭示了JCP算法相比已有方案的优势，即在多用户多缓存容量场景下，本文所提JCP算法可以获得更高的缓存命中率。

5 结语

本文针对D2D缓存网络中用户存在多种不同缓存容量的实际情况，以最大化网络缓存命中率为目标，优化不同缓存容量用户的缓存布设方案。为了达到这一目的，提出了基于坐标梯度的联合缓存布设算法并通过仿真证明了该算法的优越性以及对现实缓存网络中缓存布设的指导意义。但是本文假设D2D通信在一定距离范围内可以无差错传输，但在实际传输过程中，信号无疑会受到信道衰落和干扰的影响，因此在考虑信道条件的情况下优化多缓存容量情况的缓存布设方案是下一步要解决的问题。