D2D集成雾无线接入网中的双层分布式缓存

夏骋宇，蒋雁翔

（东南大学，江苏 南京211189）

1 引言

近年来，高质量的无线视频、社交网络等业务和智能应用呈现爆炸式增长。可以预见，未来的 5G/B5G网络中这些业务还将继续增长，如何在指数增长的业务中为用户提供低时延的体验，是 5G/B5G移动通信的重要问题。雾无线接入网（fog-radio access network，F-RAN）作为新型的无线传输架构，已经引起了学术界和产业界的关注。虽然F-RAN能够将缓存和计算功能下放到边缘节点（F-AP）[1]，但由大量用户下载少数流行文件时产生的通信负担以及随之而来的时延依然是其亟待解决的问题[2]。此外，F-AP本身缓存容量较小也带来缓存命中率不高的问题[1]。因此，雾无线接入网需要一种有效的缓存布置算法来缓解用户时延和提高命中率。同时，D2D通信近来已经受到学术界和产业界的关注，但是已有的研究大都关注D2D通信如何有效实现及避免干扰[3-6]。将D2D通信和雾无线接入网结合，提出一种在F-AP层和用户设备层中的分布式缓存布置。由此带来两个主要的问题：和传统蜂窝基站（cellular base station）相比，F-AP和用户设备的缓存容量都要小得多，因此决定某一个文件应不应该被缓存变得越发重要；如何在用户设备层实现D2D通信也至关重要。

在本文中，希望用分布式算法来解决上面的问题，对于用户设备层的缓存分布，将其转化为背包问题，采用贪心算法求解。文件权重就是它的流行度，而一个用户设备可以通过搜集周围的信息计算出流行度，从而让所有用户设备分布式地做出缓存决定。将F-AP的缓存分布转化为因子图问题，使用置信度传播算法（belief propagation algorithm）求解。对于如何实现UE间D2D传输，也通过分布式的方式求解。为了降低算法复杂度，在本文的研究中，UE和 F-AP都不会预先缓存（proactively cache）任何文件来提高命中率，并且整个网络中UE间的文件交换全部都是单跳通信，不依赖任何多跳通信。这样分布式的解决方案将更简单，更有利于在现实雾无线接入网中的应用。

图1 雾无线接入网中的二维缓存

2 系统模型

如图1所示，考虑一个集成了D2D通信的雾无线接入网，并且假设一个 F-AP覆盖范围内的UE不会被其他F-AP覆盖的UE影响[7]。在这种情况下，一个UE既可以从F-AP下载文件，也可以向其周围的 UE获取文件。同时，假设只有同一个F-AP覆盖区域内的UE之间可以进行D2D传输[7]。参考文献[8]已经研究了无线资源分配机制，因此可以假设F-AP和D2D通信不会互相干涉。正交频分多址（OFDMA）技术以及参考文献[8,9]研究的其他技术可以避免D2D通信的互相干扰。参考文献[10]对于全双工通信的研究使得可以假设每个UE可以在向一个UE发送文件的同时从另一个 UE接收文件。此外，为了降低算法复杂度，假设F-AP和UE都不会预先缓存某些文件，也就是每个 UE只会缓存它自己申请过的文件，并将这些文件传输给相邻UE。每个F-AP的缓存一开始也为空，并通过自己收集的本地信息决定缓存。

3 方程建立

基于图1所示的模型，先考虑缓存在用户层内的分布。假设每一个用户也有一个缓存容量Qu。再定义znk表示文件fn是否缓存在uk的相邻UE中。这样，F-AP中的UE向F-AP申请文件fn的概率为式（1）：

也就是说，如果某个 UE的周围已经缓存有文件fn，则它不需要向 F-AP请求文件；若周围没有此文件，则它仍然要向F-AP请求文件。这样就得到了用户向F-AP申请文件的概率。同时，用户向相邻用户申请文件fn的概率为

这样，通过D2D下载的总的时延就可以写为：

其中，dD2D为D2D通信的平均时延。

从而F-AP层下载的总时延为：

其中，dnk为设备uk从F-APam下载文件的时延，且其中h为 UE与 F-AP间的信道增益，mγ为F-APam的等效传输信噪比（equivalent transmit SNR）。

这样，就得到总时延的闭式解，为：

类似地，可以得到双层缓存对单纯的 F-AP层缓存的时延增益的闭式解为：

3.1 UE层缓存分布

3.1.1 文件流行度

首先研究 UE层。假设不同 F-AP覆盖下的UE不会互相干扰[7]，因此只需要研究一个 F-AP覆盖下的UE。UE层的缓存问题可以看作一个典型的背包问题：每个文件的流行度可以看作背包问题中每个物品的权重；背包容量就是 UE的缓存容量Qu。为了让UE可以分布式地估计每个文件的流行度，设备uk要记住相邻设备向自己请求文件fn的次数，记为tnk，这样，就能定义某个文件 fn的本地流行度，为：

考虑到突发新闻等因素，用户的兴趣可能会在短时间内突变，为了提高D2D传输利用率，让F-AP也能通过上述类似的方法计算某个文件的全局流行度，并使UE从F-AP下载文件的同时也获得该文件的全局流行度。而全局流行度会在相邻UE间快速传播，这样每个UE都能了解到最新的流行文件，并缓存它。

总之，对本地流行度可以这样估计：每次一个相邻 UE向ui请求文件 fn，ui就会将自己的tni加 1。ui从相邻的uj那里获取一个文件 fn的同时，tnj也会一起传送给ui。这样，ui就能更新自己的tni：

当ui从F-AP下载1个文件时，这个文件的全局流行度nP也会一并传送给ui。ui将nP折算成申请次数，并更新自己的tni：

3.1.2 优化缓存利用率

然而随之而来的问题是：经过一段时间后，每个UE都会保存最流行的文件，导致每个UE缓存内容相同，浪费了缓存资源。为了解决这个问题，UE不能简单地缓存流行度大的文件。规定UE将流行度和缓存率的差作为判断是否缓存的标准，优先缓存差值大的文件。为了做到这一点，ui每次缓存fn之前都要向相邻 UE发送广播信号，询问周围有多少UE已经缓存了fn，然后计算 fn的缓存率P'ni和，最后缓存Gni最大的文件。这样，ui每次就能缓存周围 UE较少缓存的但流行度又较高的文件。

其中，缓存率P'ni定义为ui周围已缓存 fn的UE个数与UE总数的比值，即：

3.1.3 UE层分布式缓存算法

拥有了Gni，就能求解缓存分布的背包问题。前面已经提到，每个UE的缓存容量为Qu。当缓存未满时，UE总是保存接收到的文件；如果缓存已满，则根据Gni的大小，替换缓存中Gni最小的文件。假设ui已经缓存了Qu个文件，这时它从别处（F-AP或别的UE）获得了第个文件，记为在收集所有必要信息之后，ui可以计算出所有个文件的G，进而可以替换缓存中的文件。

用贪心算法来解决这个背包问题，算法的复杂度由将每个文件的G降序排列的过程决定，为

算法1 UE层分布式算法

将Hk降序排列

3.2 D2D通信的实现

前文已经提到，在D2D网络中，每个UE每次最多只能向一个 UE发送或接收文件，因此定义状态变量Sk表示uk是否正在发送文件表示 uk正在发送文件，反之表示没有发送。定义表示uk是否正在接收文件，显然只有当时，uk才能发送文件请求。ui向uj发出文件申请的同时会查询Rj的值，只有时，ui和uj才能进行D2D通信。

3.3 F-AP层缓存分布

上文已经得到了uk向 F-AP申请文件fn的概率以 及 F-AP层 的 下 载 总 时 延那么F-AP层内缓存优化问题可以表示为：

上文已经提到，这也是一个 NP难问题。为了分布式地解决这个问题，根据 BP（belief propagation）理论提出一种分布式算法。参考文献[11]阐述了BP算法中的信息传递理论和因子图理论。

3.3.1 缓存分布的因子图

为了应用BP算法，必须先将上面带边界条件的优化问题转化为下面的无边界优化问题。可以证明，原问题等价于求解：

其中，ηnk和gm是缓存策略X的两个函数，分别等价于uk下载 fn的时延以及 F-AP缓存容量的限制。

这样就能把图2所示的因子图应用于求解式（10）。因为要求解X，所以将变量节点iμ设为xnm，而和为X的函数，因此将它们设为函数节点Fj：

其中，Fk是用户uk所请求的文件的集合，是集合Fk中的元素数量，ζ (n,k)指的是集合Fk中文件fn的下标。因子图中每个变量节点iμ都和函数节点Fj相连，因此共有NM个变量节点、个函数节点。

图2 F-AP层因子图模型

3.3.2 因子图中的置信度传播

在因子图中，每个变量节点将一个更新后的信息送到一个与它相邻的函数节点中，并收到一个更新后的、发送自该函数节点的信息，在多次迭代之后，就可以计算出寻找优化问题的最优解。而要做的就是设计一个信息传递算法。用表示从变量节点发送到函数节点的信息，用表示从函数节点发送到变量节点的信息。根据BP算法，信息可以根据式（16）更新为：

因为式（17）均为连乘，因此为了便于计算，将其化为对数域：

当Fj=ηnk时，信息由式（20）获得：

当Fj=gm时，信息可按式（21）更新：

然后，就能得出指数域中的置信度比率：

至此，已经得到了置信度，只需根据式（23），就能得出变量节点的值，为：

算法2 F-AP层分布式算法

设tmax为足够大

4 仿真结果及分析

假设场景中有M个F-AP，M=10，有K=50个 UE，它们均匀分布在 10个 F-AP范围内。总共有 N个文件，N=100。如前文所述，假设每个F-AP能够缓存Qm个文件，每个用户能够缓存Qu个文件。

取F-AP到UE的通信链路带宽为30 MHz[12]，每个时隙长度为20 ms，文件平均大小为1 GB。F-AP到UE信道增益在每个时隙上符合标准指数分布。F-AP和用户层间传输平均信噪比为SNR=10 dB，D2D通信平均信噪比SNR=20 dB，从云端下载时延D*=40 s[12]。使用MATLAB软件进行仿真，结果如下。

4.1 下载平均时延和F-AP缓存容限Qm

取Qm=10,20,…,90，并保持Qu=10不变，得到图3。图3中选择了基于贪心算法的单层集中式缓存[13]、基于 BP算法的单层分布式缓存（即本文的双层缓存去掉UE层，将UE层缓存容量加入F-AP层）与本文的双层缓存对比，设定3种缓存分布的总容量都相同，做出了时延性能曲线。双层缓存对于F-AP的容量要求并不是很高，在Qm较小时也能获得较大的时延增益。效果明显优于单层缓存布置。同时可以看出，基于BP算法的分布式缓存时延特性基本上与集中式算法相当，这得益于BP算法优异的性能。

图3 3种缓存方式的时延性能曲线

4.2 算法复杂度

为了研究算法的收敛特性，设Qu=5不变，得到不同Qm的平均时延曲线如图4所示。从图4中可以看出，平均时延一开始有一个初始值，接着在迭代过程中不断改变，最终收敛。算法迭代次数与Qm取值没有明显关系，在Qu不变时，对于所有的Qm，算法都能在10次左右完成收敛。考虑到UE网络的贪心算法复杂度为，n为UE缓存的文件个数，通常UE缓存不会太大，因而总的复杂度依然不高。

图4 不同Qm的平均时延曲线

4.3 UE缓存容限Qu和时延性能

本文取Qm=40，Qu=1,5,10,15,20，作出了双层缓存对于基于BP算法的F-AP单层分布式缓存的时延增益，如图5所示。

图5 双层缓存对于基于BP算法的F-AP单层分布式缓存的时延增益

从图5中可以看出，在Qu很小的情况下，时延增益也能提高 25%～50%，这主要得益于 D2D传输的低时延以及D2D层中的分布式背包算法以及对于权重的优化提高了命中率。

5 结束语

本文主要研究了集成了D2D通信的雾无线接入网中的缓存分布问题，提出双层缓存布置的分布式算法，仿真结果显示该双层分布式缓存布置可以显著降低用户的下载时延。在将来的研究中，可以考虑实际信道条件或针对链路负载、信令开销等进行优化，最终提出可以工程应用的缓存分布算法。

参考文献：

[1] PENG M, YAN S, ZHANG K, et al.Fog Computing based radio access networks：issues and challenges[J].IEEE Network,2016, 30(4)： 46-53.

[2] LIU J, BAI B, ZHANG J, et al.Cache placement in fog-RANs：from centralized to distributed algorithms[J].IEEE Transactions on Wireless Communications, 2017, PP(99)： 1.

[3] DOPPLERK, RINNEM, WIJTINGC, et al.Device-to-device communication as an underlay to LTE-advanced networks[J].Modern Science & Technology of Telecommunications, 2010,47(12)： 42-49.

[4] DOPPLER K, YU C H, RIBEIRO C B, et al.Mode selection for device-to-device communication underlaying an LTE-advanced network[C]//2010 IEEE Wireless Communications and Networking Conference (WCNC), April 18-21, 2010, Sydney,NSW, Australia.Piscataway： IEEE Press, 2010： 1-6.

[5] YU C H, TIRKKONEN O, DOPPLER K, et al.Power optimization of device-to-device communication underlaying cellular communication[C]//2009 IEEE International Conference onCommunications, June 14-18, 2009, Dresden, Germany.Piscataway： IEEE Press, 2009： 1-5.

[6] JANIS P.Interference-aware resource allocation for device-to-device radio underlaying cellular networks[C]//2009 IEEE Vehicular Technology Conference (VTC), April 26-28,2009, Barcelona, Spain.Piscataway： IEEE Press, 2009： 1-5.

[7] GOLREZAEI N, MOLISCH AF, DIMAKISAG.Base-station assisted device-to-device communications for high-throughput wireless video networks[C]//IEEE International Conference on Communications, June 10-15, 2012, Ottawa, ON, Canada.Piscataway： IEEE Press, 2012.

[8] ZHU H, WANG J.Chunk-based resource allocation in OFDMA systems-part I： chunk allocation[J].IEEE Transactions on Wireless Communications, 2009, 57(9)： 2734-2744.

[9] ZHU H, WANG J.Chunk-based resource allocation in OFDMA systems-part II： joint chunk, power and bit allocation[J].IEEE Transactions on Wireless Communications, 2012, 60(2)： 499-509.

[10] CHOI J, JAIN M, SRINIVASAN K, et al.Achieving single channel, full duplex wireless communication[C]//2010 IEEE International Conference on Mobile Computing and Networking (MobiCom), September 20-24, 2010, Chicago, Illinois,USA.Piscataway： IEEE Press, 2010： 1-12.

[11] YIN C, YANG D, ZHAO X, et al.State estimation of active distribution system based on the factor graph analysis and belief propagation algorithm[C]//2017 IEEE International Conference on Environment and Electrical Engineering and IEEE Industrial and Commercial Power Systems Europe (IEEE/I&CPS Europe),June 6-9, 2017, Milan, Italy.Piscataway： IEEE Press, 2017： 1-6.

[12] BAS E, BENNIS M, DEBBAH M, et al.Living on the edge： the role of proactive caching in 5G wireless networks[J].IEEE Communications Magazine, 2015, 52(8)： 82-89.

[13] BASTUG E, BENNIS M, KOUNTOURIS M, et al.Cache-enabled small cell networks： modeling and tradeoffs[J].EURASIP Journal on Wireless Communications and Networking, 2015(1)： 41.