一种新的基于推荐的流媒体代理缓存替换机制

胡玉琦，李晓娜（.燕山大学信息科学与工程学院，河北秦皇岛066004；2.河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛066004）

一种新的基于推荐的流媒体代理缓存替换机制

胡玉琦1，2，∗，李晓娜1
（1.燕山大学信息科学与工程学院，河北秦皇岛066004；
2.河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛066004）

摘 要：流媒体代理服务器缓存是有效缓解服务器负载、减少主干网传输的关键技术，而推荐算法是根据用户历史点播行为预测将被点播的可能性。现有的缓存算法没有考虑用户推荐对点播的影响，为此本文首先提出一种融合相异度的协同过滤推荐算法CFCD。其次，针对CFCD算法的推荐结果，定义反映流媒体文件被用户推荐程度的推荐度，并依此定义缓存价值函数，提出基于CFCD的流媒体代理缓存替换算法CRA＿CFCD。仿真实验表明，CFCD算法能够提高流媒体对象的推荐精度，而提出的CRA＿CFCD算法在缓存命中率和启动延迟方面改善了点播系统的性能。

关键词：代理缓存；缓存替换算法；协同过滤推荐算法；相异度；推荐度

0　引言

流媒体技术被广泛应用于许多网络服务中，如视频点播、视频会议和远程教育等。其中，视频点播系统能够允许用户点播观看自己喜爱的视频节目，因此迅速成为最为流行的网络应用之一，仅YouTube每天就吸引了数以千万计的网络用户，产生2 000 TB的流量［1］。然而，网络视频用户规模的迅速扩张和视频资源的不断增多，都给流媒体服务器和传输网络带来巨大的挑战。由于服务器过载和传输网络阻塞等问题，传统的C/S架构很难满足大量用户的点播请求，尤其是在用户访问高峰期。

流媒体代理服务器是部署在网络边缘，配置了一定缓存空间的一种特殊类型的服务器，缓存部分流媒体内容。用户的视频数据请求被定向给代理服务器，如果代理服务器缓存了用户所需数据，代理直接将数据提供给用户。否则，代理服务器首先向流媒体服务器请求该数据，然后再将数据发送给用户。因此，代理服务器承担了部分用户请求，节省了流媒体服务器和主干网络的带宽资源，缓解了服务器过载和传输网络阻塞等问题。由于代理缓存空间有限，缓存替换算法成为流媒体领域的研究热点。

传统的缓存替换算法包括LRU算法、LFU算法和LRU⁃K算法［2］。基于访问最近性的LRU算法将上次访问时间作为影响缓存价值的唯一因素。但是LRU算法容易出现对象刚被替换出缓存又被请求使用的情况。与LRU算法，LFU算法根据对象的访问频率来计算缓存价值，倾向于缓存访问频率较高的数据块。但LFU算法存在缓存污染问题，即访问频率较高的数据对象即使不会再被访问，依然占据缓存空间。LRU⁃K算法将LRU算法和LFU算法相结合，根据上次访问时间和访问频率共同定义数据对象的缓存价值。该算法能够提高代理服务器的性能，同时也避免LRU算法和LFU算法的缺陷。

除了以上介绍的经典缓存替换算法，许多研究者集中到流行度上，因为流行度越高的文件越热门，近期被访问的可能性越大。文献［3］提出的PSU代理缓存策略，首先根据访问频率分别计算整个视频文件和各个视频段的流行度，然后，根据流行度将视频文件划分为不同的等级；最后，综合考虑视频文件的等级和视频段的流行度来进行缓存替换操作。由于视频段的数量过大，该算法中对各个视频段的流行度的统计使系统开销过大。文献［4］提出基于最小代价的缓存替换算法，综合考虑了数据块的流行度和替换该数据块所需的系统开销。

优秀的缓存替换算法需要知道数据块将来的访问情况，以便在缓存替换时保留那些将来被访问的可能性较大的数据。用户的访问行为决定了视频对象的流行程度，间接地决定了数据块将被访问的可能性。因此，用户行为预测成为缓存替换算法研究的重要部分。协同过滤推荐算法是目前应用最为成功的推荐技术，它能够根据用户的历史评分记录，预测出用户的兴趣爱好。因此，本文将协同过滤推荐算法引入到缓存替换算法中。

1　融合相异度的协同过滤推荐算法

目前，协同过滤推荐是所有推荐技术中应用最多的算法之一。基于用户的协同过滤推荐的核心是根据用户评分矩阵计算用户相似度，找到目标用户的最近邻居用户；然后，通过最近邻居用户的兴趣爱好预测目标用户的兴趣爱好。协同过滤推荐技术以其科学性和对社会情境的充分考虑，自从出现后便取得了巨大的成就，尤其是在电影和音乐等非结构化对象的推荐领域。

计算用户相似度来寻找目标用户的最近邻居，是基于用户的协同过滤推荐的关键步骤。然而，传统的相似度计算方法更加重视用户共同评分项目，或多或少地忽视了隐藏在用户非共同评分项目中的、能够反映用户相似或相异关系的潜在信息。大多数情况下，相异度和相似度之间能够相互转化［5］。为了更加准确地计算用户相似度，本文考虑了用户相异度信息，在传统相似度计算的基础上结合相异度，提出结合相异度的协同过滤推荐算法CFCD（Collaborative Filtering Recom⁃mendation Algorithm Combined with Dissimilarity）。

目前，主要有4种相异度计算方法：城市⁃街区距离，欧几里得距离，切比雪夫距离和闵可夫斯基距离。前3种方法均是第4种计算方法的一种特殊形式。为了降低CFCD算法的复杂性，以最简单的城市⁃街区距离（又名为L1范式）为基础，依据不同用户对相同项目的评分差值来定义相异度。

定义1 U代表用户集合，V代表视频集合，u1∈U，u2∈U，v1∈V，用户u1和u2的评分项目集合分别为Iu1和Iu2，且Uu1u2＝Iu1∪Iu2，Ru1，v1和Ru2，v1分别表示用户u1和u2对视频v1的评分值，用户u1和u2的相异度为

由相异度定义，相似度计算公式为Rl（u1，u2）＝Sim（u1，u2）－Dis（u1，u2）·R，（2）其中，R代表相异度Dis（u1，u2）的权重系数，当R＝0时，CFCD退化为传统的协同过滤推荐算法。根据大量实验可知，使用余弦相似度、修正余弦相似度和皮尔逊相似度方法计算用户间相似度时，余弦相似度能够获得更好的效果。因此，选用余弦相似度作为相似度Sim（u1，u2）。那么，

因此，用户u1对视频v2∈V的预测评分计算公式为

为了验证提出的结合相异度的协同过滤推荐算法CFCD算法的性能，选取MovieLens数据集，以平均绝对误差MAE（Mean Absolute Error）作为推荐算法的评价指标。MAE计算方法如下：

其中，n代表预测评分的个数，Pu1，v2表示用户u1对视频项目v2的预测评分值，Ru1，v2表示用户u1对视频项目v2的真实评分值。MAE代表了推荐算法预测评分和真实评分之间差值的平均值，反映了推荐算法预测评分的准确性。MAE值越小，说明推荐算法越精确。

选取R值分别为0，－20，－40，－60时，最近邻居个数分别为5，10，15，20，25，30，35，40，45，50，55，60，65时，实验结果如图1所示。

图1　CFCD与传统算法的平均绝对误差Fig.1　Mean absolute errors of CFCD and traditional algorithm

由图1可知，当R值为－20，－40，－60时，CFCD算法的MAE值虽然几乎一致，但均小于传统的协同过滤推荐算法（即R＝0时），可见改进的CFCD算法的推荐是相对准确的，大约平均绝对误差减小10%以上。

2　推荐度

推荐算法能够预测用户的访问行为，通过对用户访问行为的预测，能够判断流媒体对象的热门程度，因此，本文基于推荐算法来改进缓存替换算法。

2.1流媒体文件的推荐度

协同推荐算法中，预测评分值的高低在一定程度上代表了视频项目被推荐给用户的程度。对于同一个用户来说，不同的预测评分值代表用户不同的喜欢程度。预测评分值越高，喜欢的程度越高，被推荐的程度越高。但是，对不同用户，由于用户的评分尺度不同，不能完全根据预测评分值的大小判断用户对项目的喜欢程度或者项目被推荐的程度。因此，怎样消除用户评分尺度的影响，客观地量化项目被推荐的程度是一个需要解决的问题。本文定义推荐度的概念，表示项目被推荐给用户的程度。

定义2 U代表用户集合，V代表视频集合，u1∈U，v2∈V，Pu1，v2代表用户u1对视频v2的预测评分值，代表用户u1对所有项目的评分平均值，Nu1表示用户u1的最近邻居集合，设u2∈Nu1，则视频v2被推荐给用户u1的程度DoRu1，v2定义为

那么，视频v2被所有用户推荐的程度为

当用户登录到代理服务器时，基于用户的协同过滤推荐算法会将预测评分值较高的视频项目推荐给用户。然后，推荐结果中的预测评分值被转化为用户对各推荐视频的推荐度。最后，本次推荐行为产生的所有推荐度会根据式（8）更新到各视频项目的推荐度中，实现各视频文件推荐度的动态更新。如果视频文件的推荐度越大，说明该视频被推荐的次数越多或者是某几次被推荐的程度越大，那么该视频文件将来被用户访问的可行性越大，被代理服务器缓存的价值越高。

2.2数据块的推荐度

由于流媒体文件数据量大，如果将整个流媒体文件作为代理服务器的缓存单元，缓存空间很快会被耗尽。同时，同一视频文件的不同部分具有不同的流行度，为了提高缓存空间的利用率，将流媒体文件各个分块作为访问的基本单位，根据整个视频文件的推荐度计算各个视频数据块的推荐度。

定理1 V代表视频集合，v2∈V，DoRv2代表视频v2被推荐的程度，视频v2的文件时间长度为L（单位：min），均等分长度为B，视频v2的数据块编号为n（n＝0，1，…）。假设视频播放结束位置均匀分布且不考虑VCR操作影响［5］，那么视频v2的数据块n的推荐度DoRv2（n）为

DoRv2（n）＝DoRv2·（1－n·B/L）。（9）

由分析可知，推荐度越大，说明被观看的概率越大，所以数据块之间的推荐度和被观看的概率成正比关系。因此，

Pv2（n）/Pv2（0）＝DoRv2（n）/DoRv2（0），（12）根据式（10）和（11），式（12）扩展为：

取视频文件的第一个数据块的推荐度为整个视频文件的推荐度，即

因此，由式（13）得由于α服从0到1之间的均匀分布，则P（L·α/B≥n）＝P（α≥n·B/L）＝1－n·B/L，（16）因此，视频文件v2的数据块n的推荐度可以根据式（9）计算。并且，数据块的推荐度是决定该数据块是否被缓存的关键。

3　基于CFCD的缓存替换算法CRA＿CFCD

3.1缓存价值函数（Caching Value Function）

推荐算法能够预测用户的兴趣爱好，获知流媒体数据块被用户访问的可能性。根据从CFCD算法中得出的数据块的推荐度，定义基于数据块推荐度的缓存价值函数：

其中，Cvalue（v2，n）代表视频文件v2中数据块n的缓存价值，它主要和视频文件v2的推荐度和数据块在文件中的位置有关，从而提出基于CFCD的缓存替换算法CRA＿CFCD（Cache Replacement Algorithm Based on CFCD），算法中的参数说明如表1所示。

表1　参数说明Tab.1　Notes of parameters

3.2算法描述

系统的基本工作流程如下：

1）任意用户u∈U，当u登录到代理服务器时，CFCD算法将预测评分值较高，即用户将来观看可能性较大的视频项目推荐给用户。

2）根据步骤（1）的推荐结果，生成用户u的推荐集K（u）。K（u）包含了用户u推荐的各个视频项目v∈V及用户u对视频v的推荐度DoRu，v，构成序偶，集合K（u）的元素表示为k（u）＝（v，DoRu，v）。

3）步骤（2）中得到的用户u的推荐视频k（u）∈K（u），根据式（8），将用户u对视频v的推荐度更新到视频v的推荐度DoRv中，以使所有视频文件的推荐度随着用户的观看行为而动态变化。

4）用户开始视频点播和观看，代理服务器使用CRA＿CFCD算法进行缓存替换操作。CRA＿CFCD缓存替换算法描述如下：算法1 缓存替换算法CRA＿CFCD

4　实验及性能分析

4.1仿真环境

为了真实地模拟代理服务器中缓存策略的性能，需要生成用户的请求序列。一般有两种方法：一种是概率模拟，即根据统计数据中呈现出的规律性来模拟事件发生的概率，另一种是轨迹驱动模拟，是根据现实服务器中记录的访问日志来进行的。这里选择第2种方法，即轨迹驱动模拟，使用流行的数据集MovieLens，并将其以8∶2的比例分割成推荐模块的训练集和缓存替换模块的用户请求序列。Movielens数据集来源于Movielens网站真实的用户访问记录，满足Zipf规律。采用指数分布数据发生器产生前后两个用户访问请求进入系统的时间间隔。设定用户登录到系统选择影片时，接受推荐影片的概率为0.6，并假定被推荐的所有影片中被用户选择的概率相等，并且用户访问强度随时间段而变化。

设缓存比例f为缓存空间大小和流媒体文件总大小的比值，取60%以下。其它的仿真参数如表2所示。

表2　仿真参数取值Tab.2 Values of simulation parameters

4.2结果分析

使用缓存命中率和用户平均启动延迟两个指标来评价缓存替换算法的性能，并选用LRU算法、LFU算法作为对比算法。当缓存比例f分别为0.1，0.15，0.2，0.25，0.3，0.35，0.4，0.45，0.5，0.55时进行实验。

1）缓存命中率（Cache hit ratio）

缓存命中率是代理缓存服务器满足的用户请求个数与用户总的请求个数的比值，反映了代理服务器缓存空间的利用率，缓存命中率越高，缓存空间的利用率越高。

由图2可知，随着缓存比例的增加，代理服务器能够缓存数据块增多，所以缓存命中率提高。当缓存比例较小时，本文提出的CRA＿CFCD算法的命中率明显高于LRU和LFU算法，例如，当25%的媒体数据被缓存时，传统的LRU和LFU缓存替换算法的命中率大约是30%，而改进的CRA＿CFCD算法的命中率是45%。而随着缓存比例的增大，这种差异有渐小的趋势，因为流媒体文件的访问频率满足Zipf规律，即小部分的流媒体文件被大部分的用户访问，所以当缓存比例较大时，缓存空间将满足用户所需的大部分数据，缓存替换算法的作用减弱。

图2　缓存替换算法的命中率比较Fig.2　Comparisons of cache hit ratios of cache replacement algorithms

2）平均启动延迟（Average Start⁃up latency）

启动延迟是指从用户发出请求到接收到请求的数据所需的时间间隔，它反映了用户开始视频观看的等待时间。用户启动延迟越小，用户体验效果越好。

由图3可知，本文提出的CRA＿CFCD算法比LRU和LFU算法能够获得较低的启动延迟。

图3　缓存替换算法的启动延迟比较Fig.3　Comparisons of start⁃up latency of cache replacement algorithms

5　结论

流媒体代理服务器能够缓存将来可能被访问的数据块，承担部分用户请求，减少流媒体服务器和主干网的负载。为了提高缓存空间的利用率，代理服务器删除缓存价值最小的数据块。推荐算法能够预测用户的访问行为，本文基于推荐算法来设计缓存替换算法。首先，对协同过滤推荐算法中的相似度计算方法进行改进，提出了结合相异度的协同过滤推荐算法CFCD。然后，基于CFCD定义了缓存价值函数、提出了改进的缓存替换算法CRA＿CFCD，得出如下结论：

1）从CFCD推荐算法中得出：在传统相似度的基础上结合相异度计算用户关系的方法是有效的，它能够提高推荐算法的精度。

2）在改进的缓存替换算法CRA＿CFCD中，引入协同过滤推荐算法，能够提高缓存替换算法的性能，开辟了改进缓存替换算法的新途径。

3）基于推荐的缓存替换算法的性能和使用的推荐算法的性能是相关的（相关的实验验证由于篇幅限制，未能附上），今后我们将尝试利用各种推荐算法改进缓存替换算法。

参考文献

［1］Neves M Rodrigues M Azevêdo E et al.Selecting the most suited cache strategy for specific streaming media workloads C //2013 IFIP/IEEE International Symposium Ghent 2013 792⁃795.

［2］林子雨 赖明星 邹权 等.基于替换概率的闪存数据库缓冲区替换算法 J .计算机学报 2013 36 8 1568⁃1581.

［3］Ge Yang.A proxy caching algorithm based on popularity for stream⁃ing media C //9th International Conference on Natural Computa⁃tion Shenyang 2013 1520⁃1525.

［4］Keshavarzi M Dehghan M Mashinchi M.Applications of Classifica⁃tion Based on Similarities and Dissimilarities J .Fuzzy Information and Engineering 2012 4 1 75⁃91.

［5］Krishnamoorthi V Carlsson N Eager D et al.Proxy⁃Assisted HTTP⁃Based Adaptive Streaming Performance C //IEEE 21st International Symposium on Modeling Analysis＆Simulation of Computer and Telecommunication Systems San Francisco 2013 182⁃191.

A new proxy cache replacement mechanism of multimedia streams based on recommendation

HU Yu⁃qi1，2，LI Xiao⁃na1
（1.School of Information Science and Engineering，Yanshan University，Qinhuangdao，Hebei 066004，China；2.The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province，Qinhuangdao，Hebei 066004，China）

Abstract：Streaming media proxy cache is the key technology of reducing load of streaming media server and transmission network.Recommendation algorithm is based on the historical access behavior of users to predict which media data would be probably re⁃quested in the further.The traditional cache replacement mechanisms have not concluded user′s recommendation influences.Firstly，CFCD（Collaborative Filtering Recommendation Algorithm Combined with Dissimilarity）algorithm is proposed.Secondly，Recom⁃mended Degree of a media file is defined based on the analysis of the CFCD recommendation result.And then CRA＿CFCD（Cache Replacement Algorithm Based on CFCD）is proposed.Finally，Extensive simulations show that the CFCD algorithm can enhance the accuracy of the recommendations，CRA＿CFCD is more effective in cache hit ratio and start⁃up latency.

Key words：proxy cache；cache replacement algorithm；collaborative filtering recommendation；dissimilarity；recommended degree

作者简介：∗胡玉琦（1964⁃），女，黑龙江齐齐哈尔人，博士，副教授，主要研究方向为多媒体网络、移动多媒体技术，Email：hu＿yuqi＠sina.com。

基金项目：教育部科技发展中心专项研究课题基金资助项目（2011109）

收稿日期：2014⁃09⁃02

文章编号：1007⁃791X（2015）02⁃0139⁃06

DOI：10.3969/j.issn.1007⁃791X.2015.02.007

文献标识码：A

中图分类号：TP939.09