一种移动流媒体分层协同缓存系统

杨大武，李泽平

(1.贵州大学计算机科学与技术学院,贵州 贵阳 550025; 2.普定县第一中学,贵州 普定 562100)

0 引 言

当前越来越多的移动用户正接入网络消费各种服务，预计到2022年，每月全球移动用户的总流量将会达到77.5艾字节[1]。据统计，现今我国网络视频用户已达6.09亿[2]。因为音视频内容的传输流量大，用户位置分散，常常造成网络拥塞。如果骨干网络(backhaul)出现大量的音视频流量，其他业务的数据流将会受到严重影响。降低backhaul网络中的音视频数据量和提高用户观影体验已成为网络运营商、内容提供商和技术专家研究的重要课题。

在当前的流媒体技术中，HLS(HTTP Live Streaming)在市场中占据主体地位[3]。HLS以TS文件格式对内容进行封装，将TS文件直接保存在Web服务器中，用户端可通过80端口直接进行访问。如果预先将用户请求的TS文件缓存到网络中邻近节点的存储设备上，可大大降低用户访问资源的代价。随着存储设备价格的下降，缓存技术对音视频服务的改善受到了许多研究者的关注[4]。本文综合考虑文件流行度、缓存空间大小、网络带宽等因素，把资源分配问题转化成集合划分的问题，提出一种全新的主动资源分配算法和被动资源调整算法，并对算法进行数值验证。主动算法基于子模函数对资源进行合理的划分，将用户请求的资源预先放置在基站的缓存空间内，以最快地本地响应用户的请求。被动算法在资源流行度发生变化后对缓存内容进行适时调整，保证用户对网络中资源的访问效率。

1 相关工作

网络环境中缓存的应用很普遍，在移动内容分发网络中，移动核心网络和用户接入网络节点配备了缓存空间，用户之间共享缓存空间内的存储资源[5-7]。通过一定的策略，把资源库中的视频文件保存在节点缓存空间中，可缓解用户从远程服务器上获取资源所造成的网络拥塞、时延过大等问题。怎样对资源进行分配，缓存资源采用什么替换策略，已成为近年来音视频缓存应用的研究热点[4-10]。

文献[8]提出了一种协作内容缓存模型。该模型把基站上的缓存空间分割成公共部分和独有部分共2个部分。基站上的公共部分缓存的内容相同，保存了流行度较高的音视频资源，为基站本地用户直接提供服务。各基站上的独有部分缓存的内容互不相同，通过协同机制在各基站之间为用户提供服务。结合内容流行度，文献[8]给出了缓存资源分割算法。但是该方案对资源的划分方式过于简单，资源文件要么处于公共部分，要么处于独有部分，而在实际中，有些资源却并不能做出这样的划分。

文献[9]提出了基于效用值最大化的缓存分配方案，将用户的请求代价量化为远程服务器响应与本地响应的代价的差，基于贪心思想设计了启发式算法，求出全局效用值最大的分配方案。在缓存替换时，考虑了效用值最大的问题，从全局出发，降低用户资源的获取代价。文献[9]并没有对缓存分配的方案作出系统的分析，当网络结构不同时，需要对算法做出相应的调整。

文献[10]基于用户的位置首先对基站进行聚类，用贪婪内容放置算法将资源保存在聚类区域内的基站缓存中，最后用喷泉编码[11]将用户请求的资源编码后推到用户的设备中。由于采用了喷泉编码，用户不用确认收到的每一个分组，节约了带宽。喷泉编码主要适合于广播，需要对内容进行预先编码，而网络中的数据流主要是直播或点播[2]，所以应用上有一定限制。

本文首先介绍移动分发网络的缓存模型结构及资源流行度，然后对现有的缓存协同方式进行分析，最后基于子模函数提出资源的主动分配方案和被动调整方案。

2 移动分发网络的缓存模型结构及资源流行度

2.1 移动分发网络的缓存模型结构

移动内容分发网络在传统CDN基础上，将缓存节点部署到移动核心网，接入网侧的基站[5-6]，缩小了用户与资源的距离。如图1所示，移动核心网上增加了一个缓存节点EPC，并在边缘基站(eNodes)也配备一定容量的存储设备，这样便形成了由远程资源服务器、EPC、各eNodes组成的多层缓存系统[7]。

图1 移动分发网络缓存系统结构图

若干个微基站和一个EPC站点共同形成一个协同服务的域。域内用户对音视频资源可以从本地eNode缓存、邻居eNode缓存、EPC缓存获取，或通过backhaul从远程服务器中获取。访问代价可用节点到用户之间的往返时延(RTT)来度量。从图1的组网链路来看，用户与本地eNode的距离最近，资源传输代价最小，为c0；eNodes之间的通讯链路距离较近，传输代价次之，为c1；eNode到EPC之间的距离较大，传输代价为c2；EPC到远程服务器的距离更大，传输代价为c3；eNode到远程服务器的距离最远，传输代价最大，为c4。比较传输代价有:

c4>c3>c2>c1>c0

(1)

考虑各eNode到EPC和各eNode到远程服务器的通讯代价为一常量，且没有多节点同时通讯的情况。如果用户从所属的eNode上直接获取所需资源，没有协同调度的开销；当用户从其他eNode或者EPC上获取资源时，则会带来协同调度传输的代价。

2.2 资源流行度

资源流行度用来描述用户对不同文件需求程度，一个音视频文件具有较高的流行度，表明用户对其有较强的访问需求。一般用MandelbrotZipf[12-13]分布来表示音视频文件的访问需求，假设域内所有用户的访问行为相同，并且不对排名靠前的文件进行调整，则MandelbrotZipf退化为zipf分布[14]。设有一音视频文件库，包含了一个音视频文件序列f1…fj…,其中fj表示流行度由高到低的第j个文件。用zipf分布进行描述：

(2)

其中，pj表示对文件fj请求发生的概率；N为资源库中的文件数；公式中的α为zipf分布的偏斜指数，其取值范围在0.6～1.0之间，α越大，则访问请求越集中在排名前面的资源，反之则访问请求越分散。

3 缓存内容协同方式及资源放置问题

3.1 缓存内容协同方式

缓存内容的协同方式包括2个方面，一方面是资源请求的查讯方式，另一方面是资源的分享方式。

本文采用缓存交换协议ICP[15](Internet Cache Protocol)作为资源请求的查讯方式。缓存节点用自身缓存的资源响应用户的请求，如果请求的资源不存在，则通过广播向邻居节点发出查讯的消息,再由缓存了该资源的节点提供服务。由于ICP方式在请求命中失败时会产生大量广播查讯包，当节点数较多时，每个节点都会对外广播查讯，网络的效率会有所下降[16]，必须考虑资源查讯的命中率。文献[17]提出了summary Cache方式，summary Cache方式在节点上保留了其他节点的资源目录，查讯可以在目录中进行而不用广播。资源数量较大时，可采用布隆过滤器将目录保存在内存中，提高查讯速度。

缓存的分享方式采用Single-Copy Cache sharing[17]，即当某节点为用户从其他节点上获取资源时，不在本节点上缓存该资源，但是要改变资源访问流行度，以便为下个周期的缓存调整提供流行度计算的依据。由于资源查讯只传递少量的信息，其代价可以忽略不计。

总的来说，缓存的协同分为2步,首先根据流行度将资源主动缓存到节点中,然后根据Single-Copy Cache sharing方式的引导获得请求的内容。为了保证用户对资源的获取代价最小，用户访问的顺序应该是:自身所属的基站，相邻的基站，EPC节点，远程服务器。如图2所示，访问代价从上到下依次为c0、c1+c0、c2+c0、c4+c0。

图2 响应用户请求的流程

3.2 资源文件的放置问题

(3)

用一个向量ψ={ψ1,ψ2, …，ψM+1}的各分量表示各节点资源缓存的情况。假定：

1)所有缓存节点上均没有资源，用ψ=0表示其各分量均为0，并用state0表示系统的状态，则所有用户的请求R将会导向远程服务器，backhaul链路的带宽压力达到最大，系统的性能最差。

2)当ψ≠0时，表示基站或EPC的缓存中有用户请求的资源。如将资源按流行度降序保存到各节点缓存中，直至所有的缓存空间用完，系统的状态用state1表示，此时用户的请求将最大限度地在域内节点得到响应，请求对backhaul链路的压力达到最小，系统的状态和文献[8]中提到的完全协作缓存策略相同。由于资源在本域内只缓存了一份，对一些极热的资源，除了缓存该资源的基站小区的用户外，其他小区的用户必须经过协同调用机制来获取，效率也不高。也就表明当主干链路的压力最小时，因为存在节点间资源的协同调度，访问代价也不是最小。

3)当各基站缓存的内容相同，均缓存了热度最大的音视频资源，此时的状态和文献[8]中所提到的贪婪缓存策略相同，用state2表示，有ψi=ψj;i,j=1,2，…，M，这时高流行度的资源请求将会在各基站缓存中命中，基站之间没有协同访问的代价；对于流行度较低的资源，所有基站都没有缓存该资源，响应请求只能发生在EPC节点或远程服务器上，用户访问的代价较大。

4)假定存在某个缓存放置方案，用户的总访问代价最小，设为State，此时状态一定处于state1与state2之间。

某个缓存节点下用户对资源的访问代价可描述如下：

(4)

全域内的用户访问资源的代价为：

令：

(5)

则：

(6)

资源文件的放置问题转化成求解集函数φ(ψ)，使得目标函数c最小。

求式(6)最小值等价于求式(5)最大值，而式(5)是一个0、1整数规划问题，求解方法一般用隐枚举法，但在实际应用中N一般很大，求解规模为M×N的问题实际上是不现实的。

4 求解问题的分析

对ψ向量的各分量所代表的基站的ψi进行赋值，实际上是一个缓存资源分配的问题，怎样分配方案使得系统达到State是一个NP完全问题[18-19]，无法在多项式时间内求出最佳的缓存分配方案。但是，这样的一个缓存分配问题可以转化成一个最大化子模函数的问题[20-21]，对音视频服务来说，小规模的系统约有一两千个资源，中、大规模的系统约有几万或十几万个资源，而且缓存分配算法也不会频繁地调用。求解一个总访问代价最小的分配策略，找到一个实用的缓存分配算法是可行的。

4.1 子模函数

在一个有限集中，如果有2个子集A、B，存在一个集合ν的函数g:2v→R，满足:

则g为一个子模函数[22]。

如有集合函数gA(Y)=g(A∪Y)-g(A)，则gA也是一个子模函数。

证明：有3个子集A、T、W，

g(A∪T)+g(A∪W)≥g((A∪T)∪(A∪W))+g((A∪T)∩(A∪W))

=g(A∪T∪W)+g((T∩W)∪A)

(7)

又因为：

gA(T∪W)+gA(T∩W)=g(T∪W∪A)+g((T∩W)∪A))-2g(A)

gA(T)+gA(W)=g(A∪T)+g(A∪W)-2g(A)

产后抑郁症（postpartum depression，PPD）是指产褥期女性出现明显的抑郁症状，与产后精神病、心绪不宁均属于产褥期精神综合征，其发病率在15%搭配30%之间[1]。通常表现为自责、焦虑、悲伤、沮丧等，进一步发展会导致不同程度处事能力丧失、无法履行母亲义务等等，严重的还会有自杀倾向。现阶段对PPD诱发因素还没有形成系统的解释，普遍认为是由心理、社会及遗传等多种因素造成的。本次研究采用藏医霍尔麦疗法对PPD进行治疗，获得了较好的效果。现报告如下。

由式(7)得gA(T)+gA(W)≥gA(T∪W)+gA(T∩W)，则gA是子模函数。

子模函数的性质：边际效应递减。

如果i∈V,i∉B;A⊆B,B⊆V，则gA({i})≥gB({i})。

证明：

gA({i})-gB({i})=g(A∪{i})+g(B)-g(B∪{i})-g(A)

g(A∪{i})+g(B)≥g(A∪{i}∪B)+g((A∪{i})∩B)

=g(B∪{i})+g(A)

两式结合：

g(A∪{i})+g(B)-g(B∪{i})-g(A)≥0

所以gA({i})≥gB({i})。

利用φA函数，资源的分配问题转化成对一个拟阵的有限集进行划分的问题[20，23]。

4.2 主动资源分配方案

当系统处于state1时，节点缓存中资源文件只有一份，除了基站所属用户以c0代价直接获取，其他用户的访问均需要协同访问。假如对state1状态进行调整，使得某些资源文件有多份副本，当调整到最佳状态State时，文件数量一定小于state1所含的资源文件数，而state1所含的文件数只与系统内节点的缓存空间的总和有关，因此求解问题的复杂度与缓存空间的容量大小相关。

令资源集为F，zipf分布的偏斜指数为α，节点所属用户人数向量为u，访问代价向量c，节点缓存容量为C，求解问题分2步：

1)根据流行度求出state1所用的资源文件集Fn，n为state1时所用到的资源文件按流行度降序排列的最大下标。

2)在文件集Fn上进行迭代，求出资源分配方案ψ。

下面给出最小访问代价资源分配算法。

算法1最小访问代价资源分配算法

输入：Fn,α,u,c,C

输出:ψ

2)ψ={ψ1,ψ2,…，ψM+1},ψi=0//输出变量设为空

3) do

4) forj=1 ton

5) fori=1 toM+1

9) untilψm={∅} //资源分配结束

10) returnψ//返回资源分配方案

4.3 被动资源分配方案

当系统运行一段时间后，新的音视频资源需要加入缓存系统，旧的资源也需要下线，需要及时对各节点上缓存的资源进行调整，以保证缓存方案最优。设新资源文件为fk,下面给出最小代价保证调整算法。

算法2最小代价保证调整算法

输入：ψ,fk

输出：ψ

1)ψ={ψ1,ψ2,…，ψM+1} //原资源分配赋值

2) forj=1 ton

3) fori=1 toM+1

7) returnψ

5 性能评估

数值仿真采用Matlab对6000个音视频文件、5个eNodes节点和一个EPC节点进行，其中所有节点上的缓存空间为2000 MB，总的缓存空间为12000 MB,访问次数设定为30次,并就缓存系统对减轻骨干网络带宽压力、降低用户获取资源的代价、缓存资源的利用率进行说明。

对视频库的6000个文件先作一个流行度排序，假设一个文件为10 MB，系统最大能缓存1200个文件，基站上共有1000个文件，EPC上有200个文件，在state1状态下，缓存文件集的最大下标n=1200。先对系统的命中率和骨干网络带宽压力的影响进行仿真，结果如图3、图4所示。

图3 不同资源分配策略下用户访问的命中率

图4 不同资源分配策略下骨干网带宽争用压力

α为流行度的偏斜指数。作为对比，引入贪婪缓存策略(贪婪策略)、完全协作缓存策略(完全策略)和总访问代价最小策略(最小策略)。

可以看到偏斜指数越大，3种缓存分配方案的命中率均会提高，表明用户对资源的访问倾向集中在流行度较高的文件资源上；由于完全协作方案缓存的文件没有重复，可以最大限度地在区域内响应用户的请求，骨干网络的带宽争用也是最小的；而贪婪策略的文件有重复，这些冗余的文件占用一些缓存空间，区域内的命中率最小，骨干网络的带宽收益最差。而总访问代价最小策略的命中率和骨干网络带宽压力则界于两者之间。缓存内的资源命中时，用户的访问资源由缓存来提供，所以命中率也反应了缓存资源的利用率。可见，完全协作方案的缓存利用率也最大。但是完全协作方案存在一定的节点间协作代价，用户的体验也因此不是最好。

下面估算用户的访问代价，假定用访问获取资源的时间来衡量代价，设c4=80 ms，c3=60 ms，c2=30 ms，c1=15 ms；u1=850，u2=700，u3=550，u4=400，u5=250； 可求出无缓存时用户访问资源的总代价为220000，而缓存有资源文件时，用户的访问代价有所降低，如图5所示。

图5 不同资源分配策略下用户总的访问代价

可以看出最小代价的缓存分配方式有最小访问代价，同时偏斜指数α趋向1时，缓存的命中率和用户的访问代价均呈现较好。当域内用户的访问代价较小时，用户终端设备的播放启动时间、播放抖动问题及播放码率均可以得到改善。

6 结束语

本文基于拟阵中子模函数的理论，把缓存分配问题转化成在约束条件下求最佳资源划分的问题，把不同流行度的资源文件分配到不同的缓存节点上，而算法中优先分配那些能明显降低访问代价的资源，所以得到的分配结果也是用户访问代价达到最小。由于需要分配的资源和节点上的缓存空间有关，所以不必计算整个资源库中的文件，这样就大大降低了算法的复杂度。