蒋雁翔，夏骋宇,2

（1.东南大学移动通信国家重点实验室，江苏 南京 210096；2.香港科技大学电子与计算机工程系，香港 999077）

1 引言

近年来，移动网络中对于多媒体业务的需求呈现爆炸式增长，由此带来的传输链路负载，尤其是无线接入网络和后传链路中的负载成为移动运营商们亟待解决的问题[1-2]。为了解决这些问题，研究者们提出了许多适用于未来新一代移动通信系统的新型网络架构及创新的文件传输方式[3-7]，其中一种比较流行的方法就是将流行文件缓存在离用户较近的地方，这种方法主要包括以下2 种方案。

1)在基站部署缓存，以有效降低用户对于流行内容的重复下载而带来的后传链路负担，同时还可以提高移动网络的服务质量，如降低时延等[2-7]。

2)采用新型网络的架构，将基站小型化，使整个通信网络都更加靠近用户。在雾无线接入网中，有较为分散部署的云节点（CU,cloud unit）、大量密集部署的小型雾接入点（F-AP,fog access point）等，形成了一种多层的拓扑结构。由于减小了接入节点和用户的距离，雾无线接入网架构可以很有效地提高无线网络的区域频谱效率及网络容量[4-6]。

然而，在对雾网缓存布置的研究中，始终有2 个很重要的问题[4-6]，一是底层的F-AP 缓存容量都较小，无法缓存大量的流行文件；二是F-AP 覆盖的用户很少，导致他们产生的文件请求无法反映文件的聚集效应，因此无法准确估计出在本地流行的文件。考虑到上述2 个问题，本文基于F-AP 成簇的场景，提出了一种多层协作缓存方法。单个F-AP覆盖用户很少，但是一个F-AP 簇可以覆盖拥有相似文件喜好的一群用户（例如一幢写字楼中的员工、一个体育场中的观众等），将F-AP 适当成簇，可以通过更多的文件请求更准确地估计出文件的本地流行度；而多层的协作缓存则可以提高系统的协作度，弥补F-AP 缓存容量小的问题。

本文考虑了在F-AP 成簇的雾无线接入网中的多层协作缓存，提出了一种有效的缓存布置策略和层间、层内的协作策略。本文的贡献如下。

1)相对于其他文献考虑每个F-AP 单独缓存，本文考虑F-AP 成簇场景下的多层缓存布置，优化问题更为复杂，但更加具有实际意义。

2)综合考虑了传输信道容量及多层缓存的协作机制，提出了高效的缓存布置及协作算法，降低整个网络尤其是后传链路的负载。

3)将缓存布置优化问题分解为每层内的缓存布置子问题，从而简化了问题求解的复杂度，并将每层的优化问题都转化成背包问题，进而采用贪心算法求解。

4)仿真结果表明，本文提出的多层协作缓存算法可以显著降低雾无线接入网中的后传链路负载及提高缓存命中率。

2 系统建模

2.1 多层缓存架构

图1 展示了一种雾无线接入网中的多层缓存的网络模型，其中，CU 为云节点，ue 为用户设备。最顶端为云端，存储整个系统中的文件库。CU 有一定容量的缓存，并通过后传链路和云端相连，通过前传链路与网络边缘的F-AP 相连。网络边缘的F-AP 也带有一定大小的缓存，且形成了很多簇。由于CU 的覆盖范围较广，同一个CU 可以覆盖多个F-AP 簇。本文将同一个簇中的F-AP 定义为相邻的，相邻F-AP 之间可以通过簇头实现协作缓存。而同一个CU 覆盖下的F-AP 簇间可以通过CU 实现协作缓存。如前文所述，网络中的CU 和F-AP 都能缓存一些文件，以此来降低用户下载文件的时延及重复从云端下载流行文件所带来的链路负载。由于CU 和F-AP 的缓存，以及F-AP 簇的存在，整个网络形成了一种三层的缓存拓扑结构，Tire 0 为CU 层，Tire 1 为F-AP 簇间（通过CU 控制协作），Tire 2 为F-AP 簇内（通过簇头控制协作）。

网络中每个簇头都存有一个本簇内其他F-AP的缓存文件表，每个CU 都存有一个它所覆盖的所有簇的缓存文件表，根据相关研究，由此带来的负载可以忽略不计。这样，簇头就能为簇内的其他F-AP 做出缓存决定。CU 则可以为每个簇做出缓存决定，并控制簇间的协作。用户向F-AP 申请文件时，F-AP 首先检查本地缓存，如果文件在本地缓存中，则直接发送给用户；如果本地没有缓存，F-AP 则会将申请发送到簇头，如果簇头仍没有缓存，簇头会控制簇内其他F-AP 协作；若整个簇内都没有缓存此文件，则簇头会将申请发送到CU，如果在CU 仍没有命中，则CU 会控制其他簇的协作；如果CU 覆盖的所有簇内都没有缓存这个文件，则从云端下载。

图1 雾无线接入网中的多层缓存网络模型

本文假设文件的流行度变化很慢，系统可以在负载较低的时候（例如深夜）缓存那些流行文件。由于一段时间内文件的流行度可以看成是固定不变的，本文不考虑更新文件所带来的负载。文件的流行度可以通过机器学习及分析用户的行为或偏好等得到[4]，因此本文假设文件流行度是已知的。

2.2 系统模型

本文在建模中考虑只有一个CU 的系统，包括一个CU、M个簇，第m个簇中有Nm个F-AP。Q0表示CU 的缓存容量，{Q1,Q2,Q3,…,Qm,…,QM}表示M个簇的缓存容量，{Qm1,Qm2,Qm3,…,}表示第m个簇中的F-AP 的缓存容量。表示第m个簇中的第n个F-AP，和簇头之间的链路容量，Cm为第m个簇和CU 之间的链路容量。

假设系统中共有F个文件，用{o1,o2,o3,…,of,…,oF}表示。考虑到实际情况，所有文件的大小都是不相同的，用{s1,s2,s3,…,sf,…,sF}表示文件的大小。第m个簇中的F-AP 的缓存布置由一系列二值数表示，例如=1表示文件of缓存在没有缓存。类似地，表示M个簇头中的缓存布置。一旦F-AP 层的缓存布置确定后，F-AP 簇内的缓存布置也就确定了。定义λmn、λm、λ0分别为文件请求到达、第m个簇头及CU 的平均到达率。需要注意的是，到达第m个簇头的文件请求可能来自簇头本身覆盖的用户或者簇内的F-AP。因此，本文定义mβ为簇头m的用户发送的文件请求的平均到达率。对文件of的请求在及簇头m的到达率分别为。考虑到簇头m处对文件of的请求可能来自直接相连的用户，也可能来自簇内的F-AP，因此定义为簇头m的用户对文件of的请求的到达率。定义文件of在处的流行度和归一化流行度分别为，类似地，簇头m的用户申请文件of的流行度定义为。因此，可以得到

本文假设文件的全局流行度{P1,P2,P3,…,Pf,…,PF}满足Zipf 分布，显然有。

3 优化问题

本节研究文件的最优缓存策略，从而减小网络后传链路的负载。由于整个系统涉及文件在三层缓存中的纵向分布及每层内的横向分布，较为复杂，因此，考虑将优化问题分解为三层内的缓存分布问题，并分别求解。

3.1 F-AP 簇内协作缓存

对于用户发出的文件请求，如果本地的F-AP正好缓存了被请求的文件，则请求可以被立即满足；如果簇内其他F-AP 缓存了这个文件，则文件请求会被发送到簇头，再由簇头控制簇内协作，实现用户的下载。

在不同F-AP 簇中的协作是可以同时进行、互不干扰的，因此，得到如式(6)所示的优化问题来表示第m个簇中的协作。

式(7)限制了每个F-AP 中缓存的文件大小；式(8)和式(9)限制了F-AP 和簇头之间的信道容量；式(10)限制了若本地F-AP 缓存了被请求文件，则协作不会发生；式(11)限制了每次最多只会有一个F-AP 与请求文件的F-AP 协作，而不会出现多个F-AP 同时向请求文件的F-AP 传输，避免了重复传输带来的资源浪费。

式(10)和式(11)可以分别通过放缩转化为线性不等条件，而且可以证明，这种转化是等价的，即式(10)和式(11)分别等价于式(12)和式(13)。

证明如附录所示。

这样，优化问题就变成了一个整数线性规划问题，这是一个NP-hard 问题，考虑到其指数式的复杂度不可能求得它的最优解。因此，本文参考主元的思想，提出一种较为简单的算法，希望求得该优化问题的次优解。首先，将优化问题分成2 个子问题，具体如下。

算法1解决子问题1 的贪心算法

算法2解决子问题2 的贪心算法

3.2 F-AP 簇间协作缓存

簇头处的文件请求包含了簇头用户发送的文件请求及簇内F-AP 发送的文件请求。

因此，定义增益函数的表达式为

其中，η（0≤η≤1 ）是本文引入的一个系数，用于表征CU 所控制协作的成功率，η越小，则越大，表示协作的成功率越高。例如，当η=0时，有，这时簇头m能与所有请求此文件的簇协作；而当η=1 时，，簇间没有协作发生。由此可得簇间协作的优化问题为

其中，式(21)限制了簇头的缓存容量；式(22)和式(23)保证了当本簇中已经缓存了被请求文件时，就不会再向其他簇请求文件。显然式(20)也是一个整数线性规划问题，同样也是NP-hard 问题。与3.1 节类似，本文依然希望采用贪心算法求出次优解。

首先，式(20)所示的问题可以展开为

式(20)可以进一步被分解成2 个子问题，即子问题3 和子问题4。

与3.1 节类似，提出求解子问题3 和子问题4的贪心算法，如算法3 和算法4 所示。算法3 和算法4 的总体复杂度为O(FM2lb(FM2))。

算法3解决子问题3 的贪心算法

算法4解决子问题4 的贪心算法

3.3 CU 层缓存分布

通过上述的分析，得到了F-AP 簇内的缓存分布、协作方式，以及簇头的缓存分布和簇间协作方式。因此，可以得到从簇层到达CU 层的文件请求到达率，如式(28)所示。

类似地，对于CU 层的缓存分布同样可以找到优化问题来最大化链路容量，如式(29)所示。

其中，xf表示CU 层的缓存分布，xf=1表示文件of被缓存在CU 中，否则表示没有被缓存在CU 中。CU 层的优化问题是一个简单的背包问题，本文用复杂度很低的背包算法[8]来解决。

4 仿真结果与分析

首先，假设有500 个文件，网络中有一个CU，它通过前传链路连接到2 个簇的簇头，每个簇中有5 个F-AP。同时，假设F-AP、簇头、CU 的缓存大小关系为Qmn:Qm:Q0=1:4:10；假设每层之间的链路容量为=1Gbit/s，Cm=2 Gbit/s，系数η=0.9。

为了便于仿真，假设每个簇中有50 个用户，共100 个用户。在每个簇中，簇头覆盖了30 个用户，5 个F-AP 中的每一个覆盖5 个用户，并且其覆盖区域互不重叠。文件of的流行度可以通过机器学习的办法获得，为了便于仿真，假设和服从Zipf 分布。

为了便于横向比较算法性能，本文选取了另外2 种缓存分布算法：部分协作的多层缓存算法[9]和基于BP（belief propagation）算法的分布式缓存算法[10]，具体如下。

1)部分协作的多层缓存算法。这种算法也是一种多层缓存布置算法，与本文所提算法的区别在于这种算法没有考虑层内的缓存协作，只有层间的协作。

2)基于BP 算法的分布式缓存算法。这种算法中只有最底层的F-AP 带有缓存，采用了置信度传播算法，使每个F-AP 可以独自做出缓存决定。根据其主要思想，将这种算法应用到本文的模型中，并进行仿真，便于同本文算法进行比较。

4.1 缓存总容量和缓存命中率的关系

本文分别改变缓存布置算法中缓存总容量的大小，对于本文算法、本文算法中只有某一层协作、部分协作式多层缓存、基于BP 算法的单层缓存分别绘制了缓存命中率和缓存总容量的关系曲线，如图2 所示。在本文算法中，当缓存总容量只占到文件总大小的10%时，命中率就已经达到了51.8%，此时，对于部分协作式多层缓存和基于BP 算法的单层缓存，本文提出的算法分别有16.5%和11.5%的提高，这是由于本文的缓存中同时存在垂直方向和水平方向的协作。而观察本文算法中只有某一层协作时的性能曲线，可以发现，最底层F-AP 层（Tire 2）的协作对于系统命中率的增益最大，而簇间（Tire 1）协作的增益较小，但相对于部分协作式多层缓存，在缓存总容量为10%时都至少有12.4%的增益。仿真结果显示，当缓存容量在较小的范围内增长时，本文算法的命中率提高速率也是最快的，这是因为本文算法通过整个簇内用户的申请来估算流行度，这样得到的流行度要比另外2 种算法更为精确。

图2 各算法缓存总容量与缓存命中率关系

4.2 缓存容量和后传链路负载关系

本文分别改变3 种算法中缓存容量的大小，绘制了后传链路负载与缓存容量的关系曲线，如图3 所示。在本文算法中，当缓存总容量为总文件大小的 15%时，后传链路负载已经降低为40.9%，增益明显高于另外2 种算法，这主要是因为本文的算法引入了更高的协作度，因此，更充分地利用了CU 到簇的前传链路，有效降低了后传链路的负载。

图3 缓存总容量和后传链路负载关系

4.3 链路使用率和申请次数的关系

本文将缓存总容量固定为文件总大小的5%，通过改变用户的申请次数，绘制了不同申请次数下，不同层内的链路占用率和申请次数的关系，如图4 所示。从图4 中可以看出，簇内传输链路的占用率始终高于簇间传输链路占用率，这是因为簇内F-AP 层的水平协作、簇头和F-AP 的垂直协作及簇间协作后传输到F-AP 都需要占用簇内传输链路。在申请数量在1.0×104次以上时，两层的链路使用率都在90%以上，这表示这种算法的协作机制十分有效；当申请数量继续增加时，两层的链路占用率最终都达到了100%，协作度达到最大。但是由于缓存总容量只有文件总大小的5%，无法缓存所有流行文件，所以，此后后传链路的负载将会快速增加。

图4 链路使用率和申请次数关系

5 结束语

本文主要研究了雾无线接入网中的缓存布置问题。为了降低网络的后传链路负载以及提高链路利用率，本文提出了CU 层、F-AP 簇间、F-AP 簇内的多层协作缓存方法，使F-AP 簇内缓存可以在簇头的指导下协作，F-AP 簇间可以在CU 的指导下协作，而CU 能分布式地做出缓存决定，并提出了缓存布置策略。特别地，为了简化问题，在考虑了层内协作、层间协作、链路容量的基础上，本文将优化问题分解为三层内的缓存布置问题，并分别转化为背包问题，采用贪心算法求解。仿真结果显示，所提出的多层协作缓存方法可以显著降低后传链路负载。

附录 式(10)、式(11)与式(12)、式(13)等价的证明

证明式(10)、式(11)到式(12)、式(13)的转化是等价的。