随着智能手机的普及和移动应用的丰富，移动网络流量呈爆炸式增长，其中视频流量占主导地位.在这种情况下，移动网络运营商需要不断对网络进行扩容来满足用户日益增长的流量需求，这极大地增加了运营商的投资成本.因此，如何利用有限的网络资源来承载更多的网络流量成为业界广泛关注的热点问题^[1].

在移动网络中部署缓存成为一种有效的解决方案.通过将用户喜欢的内容缓存在离终端用户较近的基站中，来自用户的内容请求可以在基站处就近得到快速响应^[2]. Rezaei等^[3]从时延角度分析了具有缓存功能的异构蜂窝网络的性能. Xie等^[4]提出了一种动态缓存资源分配机制，基站通过动态非合作博弈模型，为多个服务提供商以最优的策略分配缓存资源. Jiang等^[5]通过协同考虑内容缓存和传输策略来提高内容分发效率. Khreishah等^[6]提出了联合缓存、路由和信道分配的机制来优化内容分发. Zhou等^[7]提出了在具有缓存能力的异构蜂窝网络中通过组播调度策略来进行高效的内容传输. Li等^[8]通过博弈论来解决商业环境中的网络服务提供商和视频提供商的收益最大化问题. Al-Habashna等^[9]考虑通过设备到设备通信和缓存能力来提高移动通信网络的视频传输吞吐量.

缓存策略一般分为3类，分别为基于PULL的缓存策略、基于PUSH的缓存策略和混合缓存策略^[10].为了进一步改善内容分发效率，提升移动网络缓存系统的性能，笔者针对基于PUSH的缓存策略，给出了一种基于二分图的内容预缓存机制.在内容预缓存过程中，不仅考虑内容的流行度，还考虑缓存节点之间的链路状态，通过这种方式实现更高效率的内容缓存.最后通过Matlab仿真，验证和分析了该方案在减少传输时延和提高内容分发性能方面的优势.

1 移动网络内容预缓存系统 1.1 系统描述

具有预缓存功能的移动网络内容系统如图 1所示，共有一个内容提供商(CP, content provider)、多个具有缓存能力的小基站(SBSs, small cell base stations)、一个控制器、多个用户终端设备(UEs, user equipments). UEs是发起内容请求的设备. SBSs在现有功能基础上增加缓存能力，并记录每个内容的访问情况(如内容的访问次数)，且每隔一段时间将记录的内容访问情况发送给控制器.控制器汇总从各个SBSs发送来的内容访问信息，并将汇总后的内容访问信息共享给CP；同时，控制器还会根据内容访问信息和收集到的SBSs之间的链路状态信息来决定由哪些SBSs来预缓存新产生的内容. CP是内容的生产提供方，当有新内容产生时，会根据控制器发送的内容访问信息，将用户感兴趣的内容信息发送给控制器，用以预缓存该内容.

内容预缓存的整个过程：当有新内容产生时，CP发送内容更新消息给控制器，控制器根据内容访问信息和SBSs缓存节点之间链路状态信息，决定由哪些SBSs节点来预缓存新产生的内容，之后通知已被选择的SBSs节点从CP获取并缓存该内容.通过这种机制，当有用户请求新内容时，可以就近在SBSs得到满足，降低了内容传输时延，增强了用户体验.

1.2 链路状态信息收集和处理

SBSs节点之间的链路状态信息是由控制器周期性进行收集的，为了降低节点选择的复杂度，节点之间链路状态的优劣以等级或者打分的方式表示.等级或者打分的具体过程如下.

1) 控制器对一段时间内缓存节点之间的链路状态，如时延、带宽等进行统计，找出其中的最大值l_max和最小值l_min.

2) 如果采用等级的方式，可以将l_max和l_min之间分为N个等级区间，某一时刻，控制器对缓存节点之间的链路状态进行监测，测量值落在哪个区间，则其等级即为该区间所在的等级值.

3) 如果采用打分的方式，某一时刻，控制器对缓存节点之间的链路状态进行监测，假设监测值为l_test，则可以通过式(1)对该链路的分值进行计算.

$ s = \frac{{{l_{{\rm{test}}}}-{l_{{\rm{min}}}}}}{{{l_{{\rm{max}}}}-{l_{{\rm{min}}}}}} \times 100 $

(1)

通过上述具体步骤，控制器对监测的链路状态进行计算处理后得到节点之间的链路状态信息矩阵L，再将该矩阵应用到内容预缓存机制中.节点之间的链路状态信息矩阵L为

$ \mathit{\boldsymbol{L = }}\left[\begin{array}{l} {l_{11}}\;\;{l_{12}}\;\; \cdots \;\;{l_{1n}}\;\\ {l_{21}}\;\;{l_{22}}\;\; \cdots \;\;{l_{2n}}\\ \; \vdots \;\;\;\;\; \vdots \;\;\;\;\;\;\;\;\;\;\;\;\; \vdots \\ {l_{n1}}\;\;{l_{n2}}\;\; \cdots \;\;{l_{nn}} \end{array} \right] $

其中l_ij为节点i到节点j的链路状态情况，因此其值为最高等级或最高分值.如果节点之间没有直连链路，则相应的l值为最低等级或者最低分值.

2 基于二分图的内容预缓存算法 2.1 问题描述

网内缓存是为了有效地减少网络中冗余流量的传输，但是将内容缓存在网络中的不同位置对内容分发效率的提升作用是不一样的，因此，如何将内容预缓存在不同的节点，最大限度提升分发效率是研究的重点.

在所提出的内容预缓存机制中，SBSs缓存节点的选择需要综合考虑内容在各个缓存节点的流行度、该内容在本地所有访问中的访问热度以及每个节点与其他节点之间的链路状态等因素.

二分图是图论中的一种特殊模型，主要用来表示2个互不相交的集合中节点之间的关系.在文中2个集合分别为SBSs节点集合和内容集合，节点和内容之间的连线表示节点对内容的访问情况.通过二分图，可以很方便地计算内容对节点的重要程度，在此基础上，控制器可以得到内容预缓存策略.

2.2 算法步骤

在由n个SBSs节点和m个内容组成的基于二分图的内容预缓存系统(见图 2)中，如果节点s_i对内容o_j进行了访问，则用一条边将二者进行连接^[11]. SBSs集合为S={s₁, s₂, …, s_n}，内容集合为O={o₁, o₂, …, o_m}，整个二分图可以用一个矩阵A=[a_ij]_n×m表示，a_ij的数值表示节点相对于内容的感兴趣程度.

所提出的预缓存机制，首先会计算各个节点对于内容的感兴趣程度，即a_ij，然后计算SBSs节点之间的相似度，最后选择对该内容最感兴趣的一定数量的SBSs节点来预缓存该内容.所提出的预缓存机制中的SBSs节点选择算法如图 3所示，具体步骤如下.

1) 计算内容在各个SBSs节点流行度的计算公式为：该内容本地访问量/该内容总的访问量.其中，“该内容本地访问量”是指该内容在相应SBS节点的访问量，“该内容总的访问量”是指该内容在所有SBSs节点的总访问量.

2) 计算内容在本地所有访问中访问热度的计算公式为：该内容本地访问量/本地总的访问量.其中，“该内容本地访问量”是指该内容在相应SBS节点的访问量，“本地总的访问量”是指所有内容在该SBS节点的总访问量.

3) 计算内容与各个节点之间的权重，即各个节点对于内容感兴趣程度的计算公式为：a_ij=b₁×内容在节点流行度+b₂×内容在本地的访问热度+b₃×节点与其他节点的网络状态的平均值，其中b₁+b₂+b₃=1(b₁、b₂、b₃的值可以根据需要进行灵活地调整).需要注意的是，节点与其他节点的网络状态平均值是根据1.2节中的链路状态信息矩阵L计算出来的.举例来说，对于节点k来说，其与其他节点的网络状态平均值可以通过式(2)计算得到.

$ {{\bar l}_k} = \frac{{{l_{k1}} + {l_{k2}} + \cdots+ {l_{kn}}}}{n} $

(2)

4) 根据内容与各个节点之间的权重，计算SBSs节点之间的相似性，节点i和j之间相似性的计算公式为

$ {T_{ij}} = \frac{{\sum\limits_{k = 1}^m {{a_{ik}}{a_{jk}}} }}{{\sum\limits_{k = 1}^m {{a_{ik}}} \sum\limits_{k = 1}^m {{a_{jk}}} }} $

(3)

其中：a_ika_jk表示节点i和j对内容k的权重的乘积，$\sum\limits_{k = 1}^m {{a_{ik}}} $和$\sum\limits_{k = 1}^m {{a_{jk}}} $分别表示节点i和节点j对所有内容权重的总和.由式(3)可以看出，$\sum\limits_{k = 1}^m {{a_{ik}}} \sum\limits_{k = 1}^m {{a_{jk}}} $一定的情况下，$\sum\limits_{k = 1}^m {{a_{ik}}{a_{jk}}} $越大，说明节点i和节点j对内容的访问情况越接近，则节点之间的相似性越高.

5) 选取与要预缓存内容连接的权重最大的SBSs节点，根据与该节点的相似性，对所有的SBSs节点进行排序.

6) 选取特定数量的SBSs节点来预缓存该内容.需要注意的是，这里的特定数量可以由控制器灵活设置.对于流行度很高的内容，控制器可以将其存放在较多的SBSs节点中；而对于不太流行的内容，可以将其缓存在较少的SBSs节点中.同时，如果移动运营商的缓存资源比较丰富，则可以将新产生的内容缓存在更多的SBSs节点中.

2.3 算法分析

所提出的内容预缓存时节点选择算法的复杂度主要来源于对内容访问信息表和链路状态信息表的处理：通过计算内容访问信息统计表，得到内容在各个SBSs节点的流行度以及该内容在本地所有访问中的访问热度；通过计算链路状态信息表，获得每个缓存节点与其他缓存节点之间的链路状态平均值，之后的加权处理过程就比较简单了.因此，本算法的整体复杂度较低，算法复杂度主要跟内容访问信息统计表和网络状态信息表的表项数目以及缓存节点数量有关.

具体来说，基于二分图的内容预缓存算法的计算过程是在网络侧的控制器实施，接入网的缓存节点不需要进行计算，因此计算开销为网络侧控制器运行该算法时的时间复杂度.而在图 3所示的算法中，计算开销主要集中在计算内容在各个SBSs节点的流行度、计算内容在本地所有访问中的访问热度、计算内容与各个节点之间的权重以及计算SBSs节点之间的相似性.而当有n个SBSs节点和m个内容时，其复杂度分别为O(mn)、O(mn)、O(3mn)和O(n²).因此，基于二分图的内容预缓存算法总的时间复杂度近似为O(mn+n²).

总体来说，本算法中控制器在选择缓存节点时，不仅考虑了内容访问信息，还会考虑SBSs缓存节点之间的链路状态信息，根据内容访问信息和链路状态信息选择最优的节点来预缓存新产生的内容，从而可以实现内容的高效分发.

3 仿真结果分析

通过Matlab仿真软件模拟内容分发的通信流程，在仿真中，选择内容传输时延(一种常用的服务质量指标)作为性能评价指标^[2].仿真参数设置：假设有10个具备缓存能力的SBSs节点，每个节点具有相同的缓存空间，缓存空间大小为50 Gbit；网络中总共有5 000个大小相同的内容，每个内容的大小为1 Gbit；内容的流行度服从Zipf分布$\sum\limits_{k = 1}^K {\frac{C}{{{k^\beta }}}} = 1$，其中K为内容的总数，β=0.8^[4]；UEs与SBSs之间的时延、SBSs与源服务器之间的时延、UEs与源服务器之间的时延分别为[10, 30]、[60, 120]、[70, 140]区间的一个随机数.需要注意的是，不同的参数会随着仿真场景的不同而灵活调整.

采用不缓存(Non cache)、最近最少使用(LRU, least recently used)、预缓存(Pre-cache)3种策略得到的内容传输时延随用户请求数的变化情况如图 4所示.从图中可以看出，3种策略获得的内容传输时延均随用户请求数的增加而平滑增加，由于Pre-cache策略可以对用户最喜欢的内容进行预缓存，故较前2种策略性能最优.而LRU可以对内容根据最近访问情况进行缓存，与Non cache策略相比，可以明显减少内容传输时延，但其可能导致对非流行的内容进行缓存，因此与Pre-cache策略相比，缓存空间利用率较差，内容分发的效能略差.

图 5所示为3种缓存策略下，不同缓存空间大小对内容传输时延的影响情况.从图中可以明显看出，Non cache策略得到的内容传输时延不受缓存空间大小的影响，而LRU和Pre-cache策略得到的内容传输时延均随缓存空间的增加而平滑下降.这主要是因为当缓存空间更大时，有更多的内容可以存储在缓存节点内，更多的用户请求可以就近得到满足，所以内容传输时延就越小.

采用不同的缓存策略得到的内容传输时延随总的内容数的变化情况如图 6所示.在用户请求数一定的情况下，Non cache策略得到的内容传输时延不受内容数的影响，而LRU和Pre-cache策略得到的内容传输时延均随内容数的增加而平滑增加.当内容数不断增加时，用户的请求被分散在更多的内容，在缓存空间一定的情况下，会有更多的用户请求不能在缓存节点内得到满足，而需要到源服务器获取内容，因此内容传输时延也随之增加.

综上所述，在移动网络的接入网部署缓存，可以明显降低内容传输时延，提高网络资源利用率，增强服务质量和用户体验.同时，与传统缓存策略(LRU等)相比，所提出的基于二分图的内容预缓存机制使得内容分发过程更加高效.

4 结束语

虽然缓存技术发展迅速，目前可以以很低的价格获得容量很大的缓存空间，但是随着内容的爆炸式增长，缓存空间的增长难以满足海量内容的增长.因此，如何利用有限的缓存资源对内容进行有效缓存来提高内容分发的效率是本研究的主要问题.为了解决上述问题，笔者提出了基于二分图的内容预缓存策略，在选择内容预缓存的节点时，不仅考虑内容在各个SBSs节点的流行度，还考虑SBSs节点之间的链路状态.利用这种机制来选择缓存节点，不仅可以满足更多的用户请求，而且可以利用良好的链路来进行协作式的内容分发，更加有效地利用网内的缓存资源.仿真结果表明，该策略极大地降低了内容传输时延，提高了网内缓存节点的命中率，更加有利于内容的高效分发.