一种基于合作缓存的D2D通信缓存策略∗

虞新颖 谭 冲 刘 洪 郑 敏 卜智勇

（1.中国科学院上海微系统与信息技术研究所 上海 200050）（2.中国科学院大学 北京 100049）

1 引言

全球移动数据流量在2016年至2021年间将以47%的年复合率增长，在2021年达到每月49艾字节［1］。移动数据流量如此爆炸性增长主要是超高清晰度流媒体视频、基于云的应用逐渐爆发以及智能终端的海量接入［2］。在传统的蜂窝网络中，移动终端之间的数据通信必须通过基站的中继转发。因此，在无线通信数据业务日益增长、用户对移动通信网络服务质量的要求不断提高的情况下，基站承载压力越来越大。终端直通（Device-to-Device，D2D）技术作为5G通信关键技术之一，允许临近终端在基站的控制下，互相之间直接进行数据共享，形成数据共享网络，复用蜂窝网络的信道资源以达到减轻基站负载、提升频谱利用率、提高系统吞吐量的目的［3］。

在D2D无线缓存网络中，借助于网络中大量分散的终端存储资源，数据可以在非高峰通信期提前被缓存到终端。在通信高峰期，用户便可以从自身缓存或者通过D2D通信从临近节点的缓存中得到所需数据，使流量本地化，大大减轻基站负载。大量学者已针对D2D通信中的缓存技术展开了研究，主要集中在缓存策略的优化上。文献［4］以最小化数据服务提供商所需付出的代价为目标进行系统建模，将终端缓存空间分为Duplicate和Unique两部分，前者缓存部分最流行的数据，后者只存储剩余的从未被缓存过的数据。该策略从数据服务提供商的角度出发，并未完全利用终端有限的内存空间，易产生数据冗余。文献［5］从博弈论的角度出发将D2D数据共享描述为一种交易行为，数据请求用户是买方，数据提供用户是卖方，已缓存数据是待售物品，以最大化所有用户收益为目标对缓存网络进行建模求解。仿真表明该缓存策略具有较好的鲁棒性，但是缓存命中率不高。文献［6］通过分析终端与数据之前的请求关系提出了基于终端偏好（Interest-based）的缓存策略，该策略只考虑终端本身有潜在需求的数据。文献［7］针对数据请求用户以最大化平均缓存命中概率为目标建立缓存模型，提出两种次优缓存策略。这两种策略的前提是将一部分较不流行的数据从缓存数据库中撤除，比较受限于特定场景。因此，如何设计有利于基站卸载、能充分利用终端内存而不受限于特定场景的缓存策略仍亟待研究。

针对D2D缓存策略的优化，多数文献基于用户角度出发进行研究，从基站角度出发的研究还比较少。本文针对D2D无线缓存网络中的缓存问题，以最大化蜂窝网络流量卸载为优化目标，结合临近节点缓存情况，提出一种基于合作缓存的缓存策略，根据数据单位价值的大小从高到低进行缓存。最大化蜂窝网络流量卸载的同时保证终端有限的内存资源得到高效利用。

2 系统模型和问题描述

首先描述D2D无线缓存网络中终端与数据分布的情况以及一些假设条件，然后讨论具体的问题描述。

2.1 系统模型

考虑LTE网络下一个单蜂窝小区，小区内存在一个中心基站、n个具备D2D通信能力的智能终端，终端集合为，所有终端均匀分布在小区内。假设D2D通信距离最大为R，则用户 Di的临近节点集合为。每个终端的数据请求都是相互独立的。假设所有请求数据来自一个数据集合，包含m个数据。数据大小不完全相同，符合正态分布，可被分块缓存。

D2D无线缓存网络如图1所示，网络中存在两种通信:传统蜂窝通信与D2D通信，后者以Underlay模式存在于蜂窝网络中［8］。D2D用户复用蜂窝用户的频谱资源，中心基站负责D2D通信与蜂窝通信之间的无线资源分配与干扰管理［9］。为了保证多址接入，蜂窝网络采用正交频分复用（Orthogonal Frequency Division Access，OFDM）系统以提升频谱利用效率［10］。

图1 D2D无线缓存网络

用户获取数据时，首先采用文献［11］提出的一种软件定义无线电的设备间信号机制询问临近节点是否已缓存该数据，若已缓存，则选择一个空闲节点配对，两者匹配成功后进行D2D通信，否则用户进行蜂窝通信，即通过基站获取数据。假设用户可以同时发送和接受数据，但是建立的发送链路最多一条，接收链路也最多一条。

2.2 问题描述

首先，终端通常基于自身意愿缓存最新接收的数据信息（比如最新的视频、音乐文件等），如果恰好也有临近节点所请求的数据，那么当临近节点发起请求后，经过会话建立等一系列过程，两者之间可通过D2D通信进行数据共享。小区内成功进行D2D数据共享的终端越多，蜂窝网络流量卸载越多［12］。因此，终端缓存的数据应尽可能满足临近节点的需求，使流量本地化。然而，由于本身内存的限制，终端不可能对全部数据进行缓存，只能选择性缓存。

其次，当出现某一热点消息（比如爆炸性新闻等）时，大多数终端将请求并缓存该消息，导致短时间内基站负荷过大，同时造成终端内存数据冗余，浪费了有限的终端存储资源［13］。

解决上述问题，既要保证临近节点的数据需求，又要兼顾终端内存高效的利用率。为此本文以最大化蜂窝网络流量卸载为目标，提出一种基于合作缓存的D2D通信缓存策略，具体如下:

定义1定义一个n×m的缓存矩阵H=[hij]n×m，表示用户缓存数据的情况。其中0≤hij≤1，当 hij=1时，表示用户 Di对数据 Mj全部缓存；当hij=0时，表示不缓存，介于两者之间表示部分缓存。

定义2定义数据请求概率Pij，表示Di的临近节点集合Ni请求数据Mj的概率。

Pij可反映出临近节点的数据需求，Pij越大，表示临近节点对该数据需求越大。若终端缓存数据的请求概率越大、体积越大，则越有利于蜂窝网络流量卸载。因此，将缓存问题转化为以下最优化问题:

进一步观察式（1）可知，反映临近节点需求的Pij是时刻改变、无法确定的，上述优化问题是NP-hard问题。

3 缓存策略

对于式（1），目标是最大化蜂窝网络流量卸载，即终端所缓存的数据力求最大化满足临近节点的共享请求以进行D2D通信。为了求解缓存矩阵H，需确定数据请求概率Pij。为解决这个问题，可对Pij进行预测。考虑到用户Di可记录其临近节点的共享请求，包括请求数据的种类和次数，因此，根据Zipf定律——事物请求概率与其出现频次相关［14］，对 Pij进行预测如下:

其中:tij表示过去某段时间临近节点集合Ni向Di请求数据Mj的次数。

事物流行趋势一般不会出现突变，式（2）实质上是根据历史请求情况预测数据未来被请求的概率。但是，对于突然出现的某一热点消息，其请求概率非常大，而终端并未来得及缓存，导致短时间内蜂窝通信次数剧增，造成网络负担。由于终端都选择缓存，也会造成数据冗余。针对该现象，考虑引入合作缓存，不仅考虑数据请求概率，也考虑其他用户的缓存情况。合作缓存具体如下:

定义3定义缓存比例为Bij，表示数据Mj相对于终端Di的缓存比例，其值等于缓存Mj的临近节点数占已进行缓存的临近节点数的百分比。

在合作缓存中，用户将结合缓存比例，重新预测数据请求概率，如式（3）所示:

即更新后的请求概率等于原请求概率与缓存比例之差。

以图2为例说明如何进行合作缓存:假设D2D无线缓存网络中有4个具有相同内存的终端，2个具有单位大小的数据M1和M2，对于4个终端的请求概率分别是0.6和0.4。若终端独立缓存，则都会选择请求概率较高的M1进行缓存，易造成基站负担和数据冗余。若终端合作缓存:

1）D1缓存前，询问临近节点缓存情况，此时另外三个节点缓存全为空，显然M1和M2缓存比例都为0，则请求概率不变，D1选择M1进行缓存；

2）D2缓存前，同样询问临近节点缓存情况，发现一个已缓存的节点，且其缓存数据为M1，则M1的缓存比例为100%，M2的缓存比例为0，根据式（3）更新 M1和 M2请求概率，变为（0.6-1）和（0.4-0），因此D2选择M2进行缓存；

3）D3缓存前，发现两个已缓存的节点，且分别缓存了M1和M2，则M1和M2的缓存比例都为50%，因此更新请求概率为（0.6-0.5）和（0.4-0.5），选择缓存M1；

4）同理，对于D4，更新后的请求概率分别为（0.6-0.67）和（0.4-0.33），选择缓存 M2。最终两个终端缓存M1，两个终端缓存M2。实际上，这和数据原先的请求概率（0.6和0.4）是比较对应的。

图2 合作缓存图

对Pij进行有效定义后，对于优化问题（1），可将其视为背包问题，用经典的贪心算法求解。缓存策略具体步骤如下:

1）初始化。对于终端Di，背包大小即终端内存Ci，物品大小即数据大小。

2）Di缓存前，收集 tij及 Bij，根据式（2）和式（3）求出数据请求概率Pij，则物品价值等于数据请求概率与数据大小的乘积。

3）排序。将数据的单位价值进行降序排列。

4）缓存。将单位价值最高的数据缓存进内存，若将该种数据全部缓存完毕后，未超过Ci，则选择单位价值次高的数据并尽可能缓存。依此策略一直进行下去，直到Ci满为止，即得到选择矩阵。

4 仿真结果及分析

仿真实验中，我们测试了一个单蜂窝小区中D2D无线缓存网络的性能，简单起见，不考虑终端的移动性，并且假设终端每秒提出请求的概率为0.5，数据大小符合正态分布，其他性能参数如表1所示。

表1 仿真参数设置

网络性能由缓存命中率和卸载率表示:缓存命中率指临近节点提出的数据请求正好是终端已缓存数据的比例，数值越高意味着缓存策略越有效；卸载率指D2D通信次数占通信总次数（D2D通信+蜂窝通信）的百分比，数值越高表明蜂窝网络流量卸载越大。如无特别说明，终端内存大小为100KB，数据个数为100，大小均值为10KB。

图3比较了有合作缓存和无合作缓存两种情况下的网络总体性能指标。开始时，终端还未缓存，内存为空，无法满足临近节点的数据共享请求，所有数据通过基站获取，所以缓存命中率和卸载率为0。总体上看，不管有没有合作缓存，随着终端逐渐缓存数据，缓存命中率和卸载率都在缓慢提升。经过20s左右，引入合作缓存的网络中，缓存命中率和卸载率开始大幅度上升，50s左右接近于60%，而未引入合作缓存的网络中，性能指标稳定在40%，可以看出引入合作缓存带来的好处。

图3 网络总体性能指标

为了更好分析本文所提策略的优点，仿真结合对比了现有最为普遍的等概率缓存策略（Equal Probability Caching，EPC）和最流行缓存策略（Most Popular Caching，MPC）的缓存命中率。在EPC策略中，所有数据被终端缓存的概率是相等的，并不考虑终端的偏好和数据的差异［15］。在MPC策略中，数据请求概率遵循齐普夫分布，终端优先考虑缓存热点数据，易造成数据冗余［16］。由图4可以看出，开始时由于终端并未缓存大量数据，MPC策略和本文所提缓存策略的差别并不明显，到缓存后期，在MPC策略中大多数终端都拥有最流行数据，造成终端内存数据冗余，MPC策略的劣势突显，而本文所提缓存策略的缓存命中率稳定在55%左右，比MPC策略高30%左右，比EPC策略高13%左右。

最后，为了更好地分析D2D无线缓存网络的性能细节，进一步分析了数据因素的影响。在图5仿真结果中，网络性能随着数据个数的增多而下降。这是由于数据个数越多，意味着可供终端缓存的选择越多，分散了用户的喜好，导致缓存命中率和卸载率的下降。在图6仿真结果中，网络性能随着数据平均大小的提高而下降，这是由于数据越大，在终端内存固定的前提下，意味着可缓存的数据种类变少，满足临近节点请求的概率降低。

图4 不同缓存策略下的缓存命中率

图5 数据个数对系统性能的影响

图6 数据平均大小对系统性能的影响

5 结语

D2D通信作为未来通信网络的重要支撑技术之一，可应用于本地终端数据共享，使流量本地化，有助于减轻蜂窝网络流量负载、改善用户体验等。针对D2D无线缓存网络，本文以最大化蜂窝网络流量卸载为优化目标，提出一种基于合作缓存的D2D通信缓存策略。首先从终端本身及临近节点需求出发，预测数据请求概率，再结合当前数据缓存比例，引入合作缓存。最后将缓存问题视为背包问题，用经典贪心算法求解。仿真结果表明该策略能最大化蜂窝网络流量卸载，同时能高效利用终端有限内存。