基于用户偏好与副本阈值的端到端缓存算法

文凯 谭笑

摘 要：在端到端（D2D）缓存网络中存在大量多媒体内容，而移动终端中缓存空间却相对有限。为了实现移动终端中缓存空间的高效利用，提出了一种基于用户偏好与副本阈值的D2D缓存部署算法。首先，基于用户偏好，设计缓存收益函数，用于判断各文件的缓存价值;然后，以系统缓存命中率最大化为目标，利用凸规划理论设计缓存副本阈值，用于部署系统中文件的副本数量;最后，联合缓存收益函数与副本阈值，提出一种启发式算法实现了文件的缓存部署。与现有缓存部署算法相比，该算法可显著提升缓存命中率及卸载增益，降低服务时延。

关键词：端到端;内容缓存;用户偏好;副本;凸规划

Abstract： In the Device-to-Device （D2D） cache network， the cache space in the mobile terminal is relatively small with many multimedia contents. In order to realize the efficient use of cache space in mobile terminals， a D2D cache deployment algorithm based on user preference and replica threshold was proposed. Firstly， based on the user preference， a cache revenue function to determine the cache value of caching each file was designed. Then， with the goal of maximizing the cache hit ratio of system， the cache replica threshold was designed based on convex programming theory to deploy replica number of the files in the system. Finally， combining the cache revenue function with the replica threshold， a heuristic algorithm was proposed to implement file cache deployment. Compared with the existing cache deployment algorithm， the proposed algorithm can significantly improve the cache hit rate and the offload gain with the reduction of service delay.

Key words： Device-to-Device （D2D）; content caching; user preference; replica; convex programming

0 引言

随着无线网络数据流量指数式增长[1]，为了满足下一代网络高传输速率与低用户侧时延的通信需求，端到端 （Device-to-Device， D2D）通信技術获得了极大的关注。D2D即终端直传技术，可以使两方设备在不经基站的情景下直接通信，利用分散在网络中的D2D终端设备缓存资源，可以减轻基站流量压力，降低用户侧传输时延，提高系统吞吐量及用户体验[2]。许多的学者考虑到D2D用户之间的移动性、空间随机性、社交关系等特点，利用随机几何理论来建立动态的终端动态拓扑模型，在此基础上优化缓存网络结构、更新缓存管理策略，以提升网络缓存成功率和系统效能。

目前一些文献基于信道信息、资源分配、流行度预测以及用户分布模型研究了缓存部署问题。文献[3]通过分配静态缓存和按需中继之间的最佳存储分配权衡，提出了一种缓存分配方案来提升D2D网络的缓存利用率。文献[4]首先对高移动性网络中终端缓存的流量卸载性能进行了研究，将流量卸载最大化问题建模为NP难题，提出了一个分布式流量卸载算法。文献[5]考虑到用户在D2D网络中的地理位置来优化内容缓存分布，以提高缓存命中概率。

一些研究基于用户兴趣偏好与社交关系设计了缓存部署方案。文献[6]分析了社交网络和通信网络的关系，并指出每个数据对象最终都会传递给感兴趣的用户，该文献的研究为社交网络与通信网络的结合提供了依据。文献[7]结合了用户偏好和自私性，提出了一种缓存激励方案，促进设备间合作，降低用户自私性造成的影响。文献[8]在以内容为中心的多跳无线网络中，提出了基于用户兴趣的缓存部署策略。在内容中心网络（Content Centric Network， CCN）中，文献[9]中提出了一种合作缓存策略，它在作出缓存决策时考虑了用户偏好、节点重要性和缓存替换率。然而，CCN更多地关注了路径选择问题，没有考虑网络性能的整体优化。

与机会网络[10]类似，在D2D缓存网络中，流行的资源往往会被多个终端缓存产生多个副本，由于D2D用户终端缓存能力有限、移动性高，这有利于保证其缓存命中率与传输成功率，但过多的副本也会造成系统总体缓存空间的浪费，使其他流行文件无法得到充分的缓存而导致系统缓存命中率以及网络性能下降。为了保证文件缓存成功率与缓存空间利用效率，提高缓存效率与系统性能，本文提出了一种基于用户偏好与文件副本阈值集合的启发式算法PRC（Preference Replicas Caching），旨在提升系统缓存命中率及卸载增益，降低服务时延。

1 系统模型

本文考虑一个单一小区无线D2D网络，网络由一个基站BS和N个D2D终端设备（D2D User Equipment， DUE）组成，系统模型如图1所示。网络中所有用户的位置服从密度为λ 的齐次泊松点过程（Homogeneous Poisson Point Process， HPPP），DUE之间的通信与有效缓存传输距离均为R，网络中缓存文件具有相同大小，且所有的DUE具有相同的缓存功能和存储空间[11]。

在该系统模型中D2D通信采用正交频率，且在传输时不会产生因同频干扰发生的链路冲突，用户n在其通信范围内的其他邻居用户n′构成的集合记为Θn[12]。假设整个缓存网络的文件总数为N，单个DUE不会重复缓存已有文件，那么缓存网络中缓存文件fi的个数也即是已缓存文件fi的用户终端数，均为Ni。

在此模型中，每个文件按照文件被请求概率，也就是文件流行度进行排名，描述文件的集合为F={f1， f2，…， fN}，文件的被访问概率服从zipf分布[13]，则对于排名为i的文件fi的被请求概率为：

其中：γ为流行度分布的偏移指数，γ越大表示流行文件请求越集中。

当用户在请求文件时，考虑以下两种缓存命中事件：

事件一 自卸载。当用户请求文件已在本地缓存时，则直接获取本地缓存文件。

事件二 D2D卸载。当用户请求文件在本地并没有缓存时，用户可在缓存传输距离R内找寻一个空闲的已缓存请求文件的DUE获取该文件。

若用户在本地缓存网络中没有成功请求的需求文件，则通过回程链路将请求文件从核心网络下载到最近的基站，然后再通过基站发送给请求该文件的用户，本文仅考虑事件一和事件二构成的缓存命中事件集。本文缓存算法设计基于被动缓存策略，即缓存动作发生在DUE获得请求文件之后，由于D2D网络中用户具有较强的移动性，被动缓存比主动缓存可以降低系统能耗[14]。

2 PRC算法设计

2.1 基于用户兴趣偏好的缓存收益函数设计

在本节中，首先构建兴趣相关度量，再利用其定义缓存收益函数。根据系统模型，在D2D缓存网中共存在N个文件，包含不同类型的G个主题集合为L={l1，l2，…，lk，…，lG}，则对于文件fi中包含的主题集合为Li={la，lb，…}，LiL，那么用户n对于主题lk的偏好函数可表示为：

其中：X（lk） 表示用户选择lk主题的事件集;Vn 表示用户n选择主题的历史事件;P（X（lk）│Vn）表示用户n选择主题lk的历史概率，P（X（lk））表示全网用户选择主题lk的历史概率。对于文件fi中是否存在主题lk，利用Pi（lk） 来表示：

用户n对文件fi的偏好程度则可以用向量余弦距离[15]来表示：

由于缓存部署与内容分发时间间隔很短，本文考虑在设计缓存收益函数时，利用用户间的物理距离d（n，n′）此处语句不通顺，请作相应调整代替路径损耗，则用户n缓存文件fi的收益函数可表示为：

2.2 基于系统缓存命中率的副本布设方案

系统缓存命中率可以表示为本地缓存命中与D2D缓存命中两个事件发生的概率和：

其中：pselfhit为自卸载缓存命中率;pd2dhit为D2D缓存命中率。

本文首先考虑本地缓存命中事件，用户请求文件fi在本地已缓存的概率为：

则系统的自卸载概率可以表示为每个文件流行度与已缓存概率乘积的累加和：

因为在缓存网络中的DUE满足概率密度为λ的HPPP分布，则在半径为R的方圆范围内有m个DUE的概率表达式为：

根据HPPP稀释理论，已缓存文件qiλ的DUE服从概率密度为qiλ的HPPP，那么对于文件fi的D2D卸载缓存命中率可以表示为：

整理可得，系统总的缓存命中率为：

设文件副本数布设集合为J={N1，N2，…，NN}，则优化问题可表示为：

其中Md为DUE的缓存存储容量空间大小。

下面证明目标优化问题为凸规划问题，首先对phit关于Ni进行二阶偏导数运算，可得到：

由此可知，phit的海森矩阵对角线元素均小于零且其他元素均为零，故函数phit是关于J的严格凹函数。又因为J的定义为凸闭集，可知目标优化问题是一个凸规划问题。

利用次梯度投影的方法可求解该优化问题。首先记拉格朗日函数为：

其中μ≥0，则对偶函数表示为：

对偶问题表示为：

将式（17）整理后得到Ni关于μ的函数表达式为：

因为副本数应为大于等于零的整数，所以在实际副本布设中需取其最接近正整数N^i=[N*i]为文件fi最优副本数，则当系统缓存命中率最大时，最优系统副本数布设表示为：

2.3 缓存算法设计

本文提出了一种启发式算法，其中心思想是在考虑系统缓存命中最优条件下，使用户选择缓存收益更大的文件，放弃缓存收益相对较小的文件，从而最大化系统缓存收益。达到提高回程链路业务卸载量和缓存命中率、降低内容获取时延的目的。

当用户请求文件在本地有缓存时，DUE完成自卸载，若自卸载不成功，用户将从邻居用户和基站获得请求内容。为了部署缓存文件fi，本文采用了联合用户偏好与缓存阈值的启发式算法。具体步骤如下：

其中：Ni表示文件fi当前网络中的缓存副本数量;Cn表示用户n已使用缓存空间大小。伪代码执行条件为用户n请求文件γ，且用户n自卸载未成功。其第一层判断语句用于判断文件γ副本是否已经达到阈值，在未饱和的情况下再进入第二层DUE缓存空间判断;若存在剩余缓存空间则进行缓存动作，否则选择用户n已缓存文件中缓存收益最小的文件，将其缓存收益與文件γ的缓存收益进行比较，选择缓存高的文件进行缓存。

需要说明的是，由于文件流行度的实时性，网络中的文件副本数可能超过文件副本阈值，此时需先行删除缓存收益低的多余副本，再执行算法。

首先对本文所提算法特性进行分析。设置PRC算法参数为表1数值，并利用Matlab仿真可以得出按照文件流行度排名文件的最优副本数的布设方案如图2所示。通过计算得出该副本布设方案下系统缓存命中率为phit=0.668。可以观察到，排名越高，被请求概率越大的文件缓存副本阈值越大，即系统容许其在网络中拥有更多的副本数。

在不同緩存容量Md场景下，三种算法的缓存命中率随缓存文件数量N的变化情况如图3所示。由图3可知，Md越大表示DUE用于缓存的空间越多，系统整体缓存空间随之增大。可以观察到，当缓存容量确定的情况下，缓存命中率随缓存文件数的增加而降低，由于DUE缓存容量有限，无法完全满足文件缓存需求，致使系统缓存命中率降低;而当缓存文件数量一定时，DUE缓存容量越大，能够缓存的文件也就越多，系统缓存命中率也就越高。与其他两种算法相比，本文所提算法有更优的缓存命中效果。

图4（a）显示了三种算法在不同用户密度与缓存容量下的用户时延变化情况，可以观察到本文算法相比GC和RCC平均服务时延更低。结果还表明，考虑到用户偏好的缓存算法，其平均服务时延会随用户密度的增加而增加，这是由于随着用户密度的增大，网络中的用户总数呈线性增长，然而基于偏好的缓存文件数量呈对数式增长，前者增速大于后者，故平均服务时延随用户密度的增大而增加，而随机缓存算法由于没有考虑用户偏好表现基本稳定。

图4（b）比较了不同算法的流量卸载能力，可以看出，本文所提算法相比其他两种算法有更高的卸载增益，且随着用户密度的增大，各算法的流量卸载能力均有不同程度的下降，这是由于更多用户的缓存请求无法被响应，值得一提的是，本文所提算法卸载增益下降程度也明显低于其他两种算法。

图4（c）为系统缓存命中率随用户密度λ的变化情况，可以观察到，本文所提算法与其他两种算法在用户密度逐渐增大的趋势下，系统缓存命中率均随之增长，这是由于随着小区中的用户密度增大，更多的DUE参与进缓存动作中，网络总体缓存空间也随之增多，缓存命中事件也将增长，导致系统缓存命中率增大。

4 结语

针对D2D网络中文件缓存与替换问题，本文提出了一种联合了用户偏好与缓存副本阈值的D2D缓存算法，利用用户偏好判断文件缓存价值，以副本阈值布设优化系统缓存命中率。通过仿真表明，本文所提算法对系统缓存命中率、平均服务时延、流量卸载增益方面较贪心算法与随机算法均有更优性能表现，但在D2D通信网络中，可能还存在链路冲突、信道衰落和干扰等复杂因素制约系统缓存能力，进一步研究可以结合信道模型考虑缓存问题。

参考文献 （References）

[1] Cisco. Cisco visual networking index： global mobile data traffic forecast update， 2016—2021 white paper [EB/OL]. （2017-03-28） [2018-12-05]. https：//www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html.

[2] 钱志鸿，王雪.面向5G通信网的D2D技术综述[J].通信学报，2016，37（7）：1-14.（QIAN Z H， WANG X. Reviews of D2D technology for 5G communication networks [J]. Journal on Communications， 2016， 37（7）： 1-14.）

[3] WANG W， WU X， XIE L， et al. Joint storage assignment for D2D offloading systems [J]. Computer Communications， 2016， 83（C）： 45-55.

[4] 蓝瑞宁.终端直通蜂窝系统中的边缘缓存技术[D].杭州：浙江大学，2017：9-47.（LAN R L. Edge caching for cellular systems with device-to-device communications [D]. Hangzhou： Zhejiang University， 2017： 9-47.）

[5] MALAK D， AL-SHALASH M， ANDREWS G J. Optimizing the spatial content caching distribution for device-to-device communications [C]// Proceedings of the 2016 IEEE International Symposium on Information Theory. Piscataway， NJ： IEEE， 2016： 280-284.

[6] CHEN K， CHIANG M， POOR H V. From technological networks to social networks [J]. IEEE Journal on Selected Areas in Communications， 2013， 31（9） ：548-572.

[7] CHEN Z， LIU Y， ZHOU B， et al. Caching incentive design in wireless D2D networks： a stackelberg game approach [C]// Proceedings of the 2016 IEEE International Conference on Communications. Piscataway， NJ： IEEE， 2016： 1-6.

[8] IQBAL J， GIACCONE P. Interest-based cooperative caching in multi-hop wireless networks [C]// Proceedings of the 2013 IEEE Globecom Workshops. Piscataway， NJ： IEEE. 2013： 617-622.

[9] WU L， ZHANG T， XU X， et al. Grey relational analysis based cross-layer caching for content centric networking [C]// Proceedings of the 2015 IEEE/CIC International Conference on Communications in China. Piscataway， NJ： IEEE， 2015： 643-648.

[10] 熊永平，孫利民，牛建伟，等.机会网络[J].软件学报，2009，20（1）：124-137.（XIONG Y P， SUN L M， NIU J W， et al. Opportunistic networks [J]. Journal of Software， 2009， 20（1）： 124-137.）

[11] KANG H J， PARK K Y， CHO K， et al. Mobile caching policies for Device-to-Device （D2D） content delivery networking [C]// Proceedings of the 2014 IEEE Conference on Computer Communications Workshops. Piscataway， NJ： IEEE， 2014： 299-304.

[12] LIU A， LAU V K N， CAIRE G. Cache-induced hierarchical cooperation in wireless device-to-device caching networks [J]. IEEE Transactions on Information Theory， 2018， 64（6）： 4629-4652.

[13] CHA M， KWAK H， RODRIGUEZ P， et al. Analyzing the video popularity characteristics of large-scale user generated content systems [J]. IEEE/ACM Transactions on Networking， 2009， 17（5）： 1357-1370.

[14] SOURLAS V， PASCHOS G S， FLEGKAS P， et al. Mobility support through caching in content-based publish/subscribe networks [C]// Proceedings of the 10th IEEE/ACM International Conference on Cluster， Cloud and Grid Computing. Piscataway， NJ： IEEE， 2010： 715-720

[15] KHAN E A， SHEIKH Y A， KANADE T. Mode-seeking by medoidshifts [C]// Proceedings of the 11th IEEE International Conference on Computer Vision. Piscataway， NJ： IEEE， 2007： 1-8.