基于内容流行度的移动CCN缓存策略研究

唐 红，韩 健，段 洁，赵国锋,2，高江明

(1.重庆邮电大学 未来网络研究中心，重庆 400065; 2.重庆市光通信与网络高校重点实验室，重庆 400065)

0 引 言

内容中心网络[1](content-centric networking，CCN)是一种以内容为中心的下一代互联网架构，该架构通过分布式内容缓存机制实现以内容为核心的数据传输[2]。CCN最主要的特点之一是网络内置缓存，所以，研究人员对缓存技术产生了广泛的兴趣，并针对不同方向进行了研究，如缓存策略、缓存替换策略等问题。

CCN中的内容缓存问题受到国内外的广泛关注，但是大多数缓存方案针对固定网络[3]，即只考虑有线场景下的内容缓存。而据Cisco公司统计[4]，在2016年，全球移动数据流量较2015年增长了63%，其中移动视频流量占移动数据流量总量的60%，并且移动数据流量和移动视频流量在未来几年内还将呈现持续增长趋势。同样，CCN网络也将面临着大量移动用户接入的问题。当移动设备对内容发出请求，在接收所请求的数据之前断开或移动到新的附接点时，将会增加接收数据的时延，此外用户的移动可能会对内容流行度造成影响，流行度的动态性将导致缓存内容的动态性。因此，CCN缓存方案的研究应该考虑移动性对内容缓存造成的影响，并设计出合理的缓存方案有效地提供移动性支持。

针对CCN网络中用户移动的问题，研究人员已经提出了部分移动性缓存策略。文献[5]对客户端的移动性支持是基于移动服务代理实现的，当客户端到达其目的地时，它使用移动接口与本地代理(称为“移入代理”)联系，与其分离的远程代理(称为“移出代理”)进行交互，将所有订阅和缓存的消息从远程站点传输到本地站点，然后传送到客户端库，该方案需要对客户端进行设计，所以并不具有普适性，并且整个方案需要大量服务代理，将进一步加大开销，时延可能会更长。文献[6]提出一种选择性邻居缓存方法，主动将请求的内容缓存在距离当前代理一跳的邻居节点子集中，文中通过时延和缓存成本二者的折中来选出合适的邻居子集。文献[7]提出一种完全主动的最优方案，采用位置和数据模式预测来主动支持消费者在网络中的移动。实质上，该方案将最优的缓存接近消费者的预测内容，使其将在切换之前得到满足并避免兴趣重传。文中方案利用位置估计来预测用户切换时间，利用请求模式预测来预测将要请求的内容，但是文中并没有针对此进行相应数学模型的建立和相关方法的设计。文献[8]提出一种分布式主动缓存方法来支持用户无缝移动，并且方案中采用拥塞定价方案来有效利用本地路由器的缓存空间，但是文中并没有给出方案的具体算法，并且该方法会在满足用户的移动请求之后会马上删除本地的内容，可能会造成内容重复利用率低的问题。文献[9]方案引入地理位置，即基于用户当前位置提供相关的内容服务。

本文提出了一种基于用户移动性和内容流行度预测的缓存策略，利用半马尔科夫模型表征用户移动性，采用多元线性回归理论进行内容流行度预测，结合用户移动性与内容流行度对问题进行数学建模。通过仿真证明，该策略能较好地提高内容缓存命中率，进而减少了用户的请求时延，提升缓存系统的整体效用。

1 移动CCN网络场景

介绍了具有移动用户的CCN网络场景，网络由多个能缓存内容的CCN路由器组成，用户在某些转移概率之后在无线网络中移动。

1.1 问题描述

无线网络中，用户通过无线接入点(access point,AP)访问互联网，同时用户可能在不同无线覆盖区域之间进行移动。访问互联网时，用户根据自己需求下载不同内容，内容从下载开始到下载结束一直在同一区域完成的过程称作完全下载，当用户移动时，完全下载可能不会在同一个区域上满足，在一个区域处的不完整下载可以由移动用户携带到另一个区域，引起对相同内容的新请求。因此，用户的移动性将会对其他区域处内容源的静态流行度产生影响。

1.2 网络场景

网络模型需要选择一个能提供内容分发服务的场景，以校园网为例，网络场景如图1所示。在校园网中，将校园划分为不同区域，例如图书馆、餐厅、学生宿舍等，称每个无线覆盖区域为一个站点，记站点为RH，提供Wi-Fi服务，用户可在校园的不同站点间移动，并且这些站点将向具有不同兴趣的用户分发各种内容。所有站点通过具有CCN功能的有线本地网络相互连接。网络中还存在来自外部网络的集中式服务器(见图1)，以提供所请求内容的全部源。

图1场景中，站点内的用户在餐厅区域请求内容，并发生了移动，如果用户在餐厅区域没有进行完全下载，等到达新站点(图书馆或宿舍)后将对内容重新发起请求，将会对新站点的内容流行度造成影响。因此，站点RH缓存策略设计需考虑用户移动性。

图1 具有用户移动性的CCN网络场景Fig.1 CCN network scene with user mobility

2 方法描述

基于上述问题描述，用户以某些转移概率在站点间进行移动，可能在新站点产生对某些内容的新请求。因此，需要对移动过程中用户的转移概率进行分析，同时CCN网络中，CCN路由器基于内容的流行度对内容进行缓存，因此，需要对网络中内容的静态流行度进行分析。

2.1 用户移动性

无线网络中移动用户常有基于时延行动的过程，且通常具有较大尺度的时间范围。因此，本文采用半马尔科夫模型[10-11]来描述用户的移动性，半马尔可夫过程与一般马尔可夫过程不同的是，与状态逗留时间t有关，是马尔可夫链的推广，不再局限于马尔可夫链中的假设。半马尔可夫过程的意义更接近现实中用户移动方式，所以针对位置预测的半马尔可夫模型得出的结论更精确。

设{X(t),t>0}是一个连续时间参数t的随机过程，取值于状态空间Sn(k)，其中，Sn(k)是{X(t),t>0}的状态转移时刻，令Xn是tn时刻用户发生状态转移后过程所处的状态。设定本文模型是离散时间的半马尔可夫过程，状态的逗留时间t为离散时间变量，移动用户在某一站点的逗留时间不少于一个时间单位，在每一个站点内只能是单步转移并且至少需要一个单位的时间。因此，t大于N始终成立，在N步转移花费的时间最少为t=N。其中，单步半马尔可夫核为

(1)

(1)式中，逗留时间条件概率mi,j(t)为

mi,j(t)=p{tn+1-tn=t|Xn+1=j,Xn=i}

(2)

则N步转移概率核为

(3)

(4)

(5)

2.2 内容流行度预测

多数内容流行度的研究都是对文件流行度的定性描述，缺乏针对内容流行度的定量分析，而多元线性回归[12]能对内容流行度进行定量分析。当研究对象受到多个自变量的影响，并且自变量间无准确的线性关系，即无多重共线性时，可建立多元线性回归模型进行系统分析和预测。多元线性回归技术可用于研究一个因变量与多个自变量之间的线性关系。

多元线性回归理论是用多个自变量的数值估计另一个因变量的数值，数学表达式为

y=β0+β1x1+β2x2+…+βmxm+ε

(6)

(6)式中：x1，x2，…，xm为实际观测的一般变量；y为实际观测的随机变量，并且随变量x1，x2，…，xm而变化；ε为影响y的修正因子；βi表示因变量x的变化对自变量y的直接影响。

对内容流行度的预测，可以根据最近M个时间段的流行度统计值估计未来流行度：选取L组内容的观测值，每组有m+1个流行度统计值，在站点i处内容k的第m+1个周期的统计值记为Pk,i，则未来统计周期的流行度值Pk,i关于最近m个周期流行度的m元回归方程为

Pk.i=β0+β1P1k,i+β2P2k,i+…+βmPmk,i+ε

(7)

要应用上式估计流行度预测值，需求解回归参数的估计值，求解回归参数估计值最常用的方法是最小二乘估计与极大似然估计。由于极大似然估计是基于ε正态分布假设的，而最小二乘估计对ε分布假设不作要求，故本文采用最小二乘估计进行方程求解。求出回归系数估计值b1，b2，…，bm，从而可以得到关于过去M个周期流行度统计值的流行度预测方程

Pk,i=b0+b1P1k,i+b2P2k,i+…+bmPmk,i

(8)

根据用户在不同站点之间的停留时间，完全下载可能不会在一个站点上满足。因此，当用户在一个站点具有不完整的下载并且进入新站点时，可以在新站点处请求内容。因此，新站点i上的内容k的流行度Pk,i可能不反映实际的请求率，因为从具有不完整下载站点转移过来的移动用户将发送对站点i处的相应内容的请求，影响静态内容流行度Pk,i。

3 缓存策略

为最小化服务器成本、流量负载和响应时间，需要最大化RH处的缓存命中率，即尽可能多的在本地处理内容请求。本节研究了支持用户移动性的缓存策略，提出了基于用户移动性和内容流行度预测推导的移动性缓存策略。

3.1 缓存方案

整个缓存方案的设计主要由2个部分组成：稳态情况下的缓存和突发情况下的缓存，如图2所示。在稳态情况下，方案建立用户移动性和内容流行度之间的逻辑关系，利用用户移动性对静态内容流行度的影响，重新计算新的内容流行度等级表，缓存节点根据新内容流行度等级表进行内容缓存；在突发情况下，主要针对突发事件的内容缓存，如某娱乐新闻、某新电影上映、某最新单曲发布等。当对某一内容的请求次数大于设定阈值时，将直接在缓存节点对内容进行缓存。本文仅对稳态情况下的缓存进行了研究。

3.2 缓存模型

用户在某个站点没有完成当前下载的原因可能是由于内容过大，例如，持续1 h或更长时间的视频。对于未完成的下载，用户将在新站点上生成对相同内容的请求[13]。在这种情况下，这些请求取决于在先前站点的下载，并且由于用户移动，每个站点处的内容请求率受到其他站点的影响。传统的CCN缓存方案通过内容本身的静态流行度来缓存内容，在这种情况下，一个站点产生的请求不会影响用户下一个站点的请求率，因为请求率只由本地流行度决定。为了考虑用户移动对本地内容流行度的影响，缓存方案需要同时考虑本地内容流行度的预测与站点间的转移矩阵，已获得用户通过某种转移概率到达新站点后产生的额外用户请求。缓存模型的网络符号及定义如表1所示。

图2 移动性-内容流行度的缓存方案Fig.2 Caching scheme for mobility-content popularity

表1 符号及定义Tab.1 Symbols and definitions

i=1,2,…，Ns

(9)

对每个站点的人口分布进行归一化处理

(10)

加入用户移动性后内容k在站点i处的流行度计算为

设Ci表示站点i处所有缓存内容集合，如果站点i处含有内容k，则Ek,i为1，否则为0，表达式为

k=1,…，Nc

(13)

由此可得，在站点i处的平均缓存命中率Hi为

(14)

因此，目标函数的表达式为

(15)

i=1,2,…，Ns

(16)

Rk,i<1,k=1,2,…，Nc;i=1,2,…，Ns

(17)

(16)式中，Bi表示站点i上的总缓存大小限制；(17)式表示站点i中新的内容请求率小于1的限制。

3.3 缓存算法

基于上述移动性缓存模型分析，提出基于用户移动性-内容流行度预测的缓存算法。该算法利用半马尔科夫模型来描述用户的移动性，利用多元线性回归模型来进行内容流行度的预测，然后通过用户移动性对内容流行度的影响计算出新的内容流行度，根据新的内容流行度对内容进行缓存。算法步骤如下。

步骤1初始化：网络图划分为Ns个区域，网络总用户数为Nu；

步骤2当前网络中用户在站点的逗留时间设为服从参数为η,β的威布尔分布。计算转移概率分布矩阵d={di,j}，计算逗留时间分布矩阵m={mi,j(t)}；

步骤4站点i处内容k的第m+1个周期的流行度统计值记作Pk,i，第m个周期的流行度统计值记作Pmk,i，计算Pk,i=b0+b1P1k,i+…+bmPmk,i，其中k=1,2…，Nc，i=1,2,…，Ns，当t=T时，进行下个周期的内容流行度预测；

步骤6计算Rk,i，从新的流行性等级列表{Rk,i}中选择缓存的内容。

该算法不仅考虑了内容流行度，而且加入了用户移动性对内容流动的影响，因此，该算法具有更强的适用性和实用性。

4 仿真结果与分析

本节对所提出的缓存算法进行了仿真分析，并在相同条件下与未加入移动性的算法进行了比较。仿真条件为站点数量Ns为8，内容数量Nc为200～1 000个，用户数量Nu为100，Zipf[14]参数α为0.8。由于CCN网络架构研究目前尚处于学术研究与试验阶段，本文主要基于理论分析的结果进行仿真验证。仿真拓扑如图3所示。

图3 仿真网络环境拓扑Fig.3 Simulation network environment topology

首先仿真某用户在时间t内的转移概率，基于半马尔科夫理论虚拟一些转移概率参数值和转移的逗留时间参数，逗留时间参数依然服从威布尔分布。仿真结果如图4所示。图4中的仿真曲线表示随着不同的连续时间周期特定转移的可能性结果。在初始时间周期的1个单位，网络中预测当前位置2的用户转移到位置1的可能性最大，而在之后的时间周期内移动用户转移到站点6的概率反而最大。可得出结论，该移动用户最终从站点2移动到站点6。

图4 站点2处某用户的转移概率分布Fig.4 Transfer probability distribution of a user at No.2 site

然后，图5对某些内容的请求率进行了仿真，对比了加入移动性与不加入移动性时的仿真结果。对站点2处的内容请求率进行验证，设Zipf参数α为0.8，内容数量为200～1 000个，仿真结果如图5所示。从图5中可明显发现，基于流行度的请求率不能准确地反映实际的用户请求行为，在模拟中纯流行性和实际内容请求速率之间存在较大的差距。在一个站点，从用户接收的请求不仅包括发起内容下载的用户发送的请求，而且包括从其他站点带来的继续下载。这表明用户移动性对内容请求速率具有影响，大大偏斜原始内容流行度，使得基于静态流行度的缓存策略的性能较差。

图5 站点2处某内容请求率分布Fig.5 Content request rate distribution at No.2 site

然后，图6对内容大小对缓存性能的影响进行了仿真，对比了加入移动性与不加入移动时的仿真结果，仿真结果如图6所示。从图6中可明显发现，随着内容大小的增加，2种策略的缓存命中率都会下降，因为缓存大小固定，缓存内容的数量会减少。并且加入移动性后的缓存方案在大尺寸内容上表现更好，因为由于内容过大造成未完成的下载过多，所以站点之间的用户移动性必须被考虑。

图6 内容大小-内容缓存率分布Fig.6 Content size-content hit rate distribution

最后为了检验算法的准确性，对加入移动性与不加入移动性后的缓存命中率进行了仿真比较。图7显示了加入移动性和不加入移动性之间的性能差距。加入移动性后的高速缓存命中率高得多，并且当CCN中的内容数量逐渐增多时，性能改进变得更加明显，并且高速缓存命中率将随着内容数量的增加而变高，这是因为当内容数目增加时能更多地缓存流行度较高的内容。

图7 网络中内容缓存命中率分布Fig.7 Content hit rate distribution in network

5 结束语

本文研究了一种在CCN无线网络环境下适用于用户移动性的缓存算法，算法包括用户移动性分析和内容流行度预测2部分。采用半马尔科夫模型对用户的转移概率进行分析，同时利用多元线性回归模型对内容流行度进行定量分析，结合用户移动性与内容流行度推导出移动性缓存策略。仿真结果显示，移动性会对内容流行度产生较大影响，并且基于用户移动性与内容流行度预测的缓存方案可以有效提高网络中内容的缓存命中率。未来研究工作将考虑缓存容量及内容大小对移动CCN缓存策略的影响。

[1] PERESINI P, KUZNIAR M, KOSTIC D. Monocle: dynamic, fine-grained data plane monitoring [C]// Proceedings of the 11th International Conference on Emerging Networking EXperiments and Technologies. Heidelberg: ACM Press , 2015 :1-13.

[2] 朱轶,糜正琨,王文鼐.一种基于内容流行度的内容中心网络缓存概率置换策略[J].电子与信息学报, 2013, 35(6):1305-1310.

ZHU YI, MI Zhengkun, WANG Wennai. A Cache Probability Replacement Policy Based on Content Popularity in Content Centric Networks[J]. Journal of Electronics & Information Technology, 2013, 35(6):1305-1310.

[3] ZHANG M, LUO H, ZHANG H. A Survey of Caching Mechanisms in Information-Centric Networking[J]. IEEE Communications Surveys & Tutorials, 2015, 17(3):1473-1499.

[4] VNI Cisco, Cisco Visual Networking Index: Global Mobile Data Traffic Forecast Update [EB/OL]. (2017-03-28) [2017-05-11].http://www.cisco.com/c/en/us/solutions/collateral/service-provider/visual-networking-index-vni/mobile-white-paper-c11-520862.html.

[5] CAPORUSCIO M, CARZANIGA A, WOLF A L. Design and Evaluation of a Support Service for Mobile, Wireless Publish/Subscribe Applications[M]. LOS ALAMITOS, USA: IEEE Press, 2003.

[6] VASILAKOS X, SIRIS V A, POLYZOS G C, et al. Proactive selective neighbor caching for enhancing mobility support in information-centric networks[C]// Proceedings of the second edition of the ICN workshop on Information-centric networking. New York, NY, USA: ACM Press, 2012:61-66.

[7] FARAHAT H, HASSANEIN H S. Supporting Consumer Mobility Using Proactive Caching in Named Data Networks[C]//2016 IEEE Global Communications Conference (GLOBECOM). Washington, DC USA: IEEE Press, 2016: 1-6.

[8] SIRIS V A, VASILAKOS X, POLYZOS G C. Efficient proactive caching for supporting seamless mobility[C]//2014 IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks. Sydney, Australia: IEEE Press, 2014:1-6.

[9] GUAN J, HE Y, WEI Q, et al. A Classification-Based Wisdom Caching scheme for Content Centric Networking[C]//2016 IEEE INFOCOM Conference on Computer Communications Workshops. San Francisco, CA, USA: IEEE Press, 2016:822-827.

[10] 张艳,王玫,王俊义.Femtocell网络中移动用户位置和网络容量的预测[J].桂林电子科技大学学报, 2014(2):87-90.

ZHANG Yan, WANG Mei, WANG Junyi. Preliminary Prediction of Mobile User Location and Network Capacity in Femtocell Networks [J]. Journal of Guilin University of Electronic Technology, 2014 (2): 87-90.

[11] YU F, LEUNG V. Mobility-based Prediction Call Admission Control and Bandwidth Reservation in Wireless Cellular Networks [J]. Computer Networks, 2002, 38(5): 577-589.

[12] 董美姣，黄韬.基于内容流行度预测的CCN缓存策略研究[EB/OL].(2014-12-05)[2017-05-11].http://www.paper.edu.cn/releasepaper/content/201412-154.

DONG Meijiao, HUANH Tao. Study on CCN Caching Strategy Based on Content Popularity Forecasting [EB / OL]. (2014-12-05)[2017-05-11].http://www.paper.edu.cn/releasepaper/content/201412-154.

[13] WEI T, CHANG L, YU B, et al. MPCS: A mobility/popularity-based caching strategy for information-centric networks[C]// 2014 IEEE Global Communications Conference. Austin, TX, USA: IEEE Press, 2014:4629-4634.

[14] HASSLINGER G, NTOUGIAS K, HASSLINGER F. Performance and Precision of Web Caching Simulations Including a Random Generator for Zipf Request Pattern[M]. Münster, German: Springer Intemational Publishing, 2016.

(编辑：刘 勇)