一种离散分布的移动感知缓存策略

杨崇旭，陈正勇，杨 坚

(中国科学技术大学 未来网络实验室，合肥 230022)

1 引 言

近年来，随着各种网络应用的迅猛发展，业务模式向移动端倾斜，移动设备与通讯正在逐渐取代自互联网诞生以来主导互联网的fixed-host/server通讯模型，根据《2016年爱立信移动市场报告》[1]，移动数据流量从2016年到2021年间将以47%的复合年增长率(CAGR)增长.便携式移动终端的日益普及和物联网终端数量的爆炸式增长对网络的移动性提出了更高要求，用户终端移动性导致数据传输路径频繁变换，严重破坏了上层应用服务的连续性，影响了IP网络用户的服务质量，亟需在新型智慧网络中对移动数据进行优化.

本文核心思路是在新型智慧网络中搭建用户感知层，通过用户集体行为与个体移动特征相结合，分析用户移动行为，从而有针对性地对用户请求的文件进行分布式部署.结合当前已有的新型网络架构方案，选择在小基站网络[2]中进行移动感知的分布式缓存策略研究，因为小基站网络是一种新型3G/4G宏蜂窝性能补充的网络架构，特点是体积小、能耗低，是目前网络研究领域的一个主流方向，且对移动数据处理的需求极高.本文策略是通过感知用户的移动规律，将其需求的内容提前部署在合适基站上，从而大幅度提高缓存部署的命中率，降低对骨干网的回程压力，减少用户下载文件的时延.

在目前已有的缓存部署策略中，如Femto caching[3]，虽然做了很多关于缓存部署策略的研究，但是都没有考虑用户的移动特征；在Sprinkler中[4]，考虑了移动特征进行缓存部署，提出了不少启发性的想法，比如沿着用户轨迹将文件分割部署在多个基站上，但是其也忽略了很多问题，比如它假设了轨迹已知，也忽视了在每个基站中逗留时间的问题；在Mobicacher中[5]，它的思路是假设已知用户请求的文件或网络须向其主动推送的文件，然后对多个用户的轨迹进行预测，考虑文件的重复使用，对文件进行部署，但其缺点是过多地依赖马尔可夫位置预测算法的准确性，而事实上这个准确性并不可靠，并且Mobicacher试图一次预测之后多个时刻的位置，其误差会变得更大，因此在其基础上做出的缓存部署策略并不可靠，另外，Mobicacher存在一个很大的弊端，其部署策略是非在线不能更新，仅仅能部署一次，无法根据用户轨迹的变化及时更新部署方式.

针对以上问题，本文针对性提出了一种离散分布的移动感知缓存策略(Distributed Mobility-Aware Cacher，DMACacher)，策略流程如、所示，主要思路是结合集体的移动轨迹特征，分析用户下一步可能到达的位置集，用集合的概念代替单一位置保证基于马尔科夫预测的准确性，另一方面分析用户在当前基站的逗留时间，尽可能地按逗留时间将文件分布在多个基站上.

图1 离散分布的移动感知策略流程图

首先，利用数据挖掘分析人类的行为模式，从大规模的移动轨迹数据库中挖掘出用户移动趋势和逗留时间特征分别建立轨迹特征预测模型(Predictive Trajectory Feature Model，PTF-Model)和逗留特征拟合模型(Sojourn Time Fitting Model，STF-Model).其中，利用PTF模型分析用户的移动轨迹特征，计算出一系列可能到达的位置，按照概率大小排列组成可达位置集；根据STF模型，预测出发生移动的具体时间，用于决策推送到当前基站的文件大小.当在任意时刻，服务器收到用户文件下载的请求(或根据流行度等决定向用户主动推送文件)，远端服务器用RaptorQ码编码该文件，将编码符号集并依概率部署在多个小基站上，用户从基站群中接收并解码文件，通过网络编码保证用可达位置集代替单一位置缓存的可行性.在用户到达新的位置后，将其添加到轨迹信息中，迭代更新预测下一个可达位置集，并等待用户下一次的文件请求.这里一次部署的文件尺寸限定在经过两个基站可下载完毕的约束下，如文件过大，将其分割，剩余部分在用户到达下一个位置后，调用DMACacher重新对其进行部署.

在下文中，将具体介绍讨论DMACacher的每一步实现方式，并对其进行理论上的性能分析，最后进行仿真实验与Mobicacher等方法比较.

2 建立轨迹特征预测模型

随着移动终端规模地日益增大，建立具有移动感知功能的新型智慧网络愈显重要，而本文的第一项工作就是建立PTF模型.关于位置预测，目前已有一些基于离散时间马尔科夫链的成果，比如马尔科夫模型(Markov Model)[6]，隐马尔科夫模型(Hidden Markov Model)[7,8]，混合马尔科夫模型(Mixed Markov Model)[9,10].结合本文场景，分析三种方法可以发现，MM仅仅简单地将所有移动用户考虑为一类人，未考虑不同人群间的移动差异性；HMM将用户所在位置设为可观状态，将用户的目标位置设为不可观状态，而在不可观状态的转移过程中无法满足不同位置在地理上的连续性约束；MMM则是在MM的基础上，考虑到了不同人群间的差异性，为每一类人群单独建立一个马尔科夫链，而对每个个体考虑了其归属于不同人群的可能性.综上考虑，选择用MMM建立PTF模型.

第一步，考虑所有可以接入的无线基站组成基站集S={S1，…，Sssum}，将移动用户z所接入的无线基站s∈S当做可观状态，用户在不同基站间的移动过程描述为一阶马尔科夫链的状态转移过程.令矢量tracez表示用户的的移动轨迹，trz，x表示轨迹tracez中经过的第x个基站，则有

tracez=trz，1→…→trz，|tracez|

(1)

trz，x∈S，x=2，…，|tracez|

(2)

第二步，将所有移动用户组成的集合Z={1，2，…，Zz-sum}依据人群间的移动特征相似性进行分类，令类别总数为K，即有

Z1∪Z2∪…∪ZK=Z

(3)

Zk∩Zk′=φ

(4)

值得注意的是，对于每一类人群都有一个特定的转移概率矩阵进行描述，在模型初建之时，并不需要指定某一个用户归属于某一类别，也不需要指定每个类别的段尺寸P(Zk)，其中段尺寸的定义是随机挑选的某个移动用户恰好归属于类别Zk的概率.

第三步，将每一个类别的转移概率矩阵表示成：

i，j∈{1，…，ssum}，k∈{1，…，K}

(5)

第四步，针对含未知参数的转移概率矩阵求解问题，选择用最大期望算法(Expectation-maximization algorithm，EM)[11]进行计算.

(6)

③用②求得的最大似然估计值更新参数：

(7)

(8)

其中用Sij表示从状态Si转移到状态Sj的次数.

④将③中更新的参数代入②中重复计算，不断迭代直至收敛.

1≥ρ1≥ρ2≥ρ3≥…

(9)

Ψ1≤∑ρi≤1

(10)

3 逗留特征拟合模型

根据上文所述，已经获得了可达位置集和对应的转移概率集，然而据此作缓存部署还需解决逗留时间问题，因为PTF模型得到的结果是时间离散的，它只能预测出可能到达的位置，而无法同时估测出发生移动转移的时间点.逗留时间所带来的误差也是目前大部分移动缓存部署策略所忽视的问题.目前已有一些工作针对用户逗留特征进行了研究，文章[12]通过大量实验发现用户的逗留特征符合幂次定律，文章[13]则进一步地从理论上论证了该规律.结合本文缓存部署的场景，考虑使用幂次定律来拟合逗留特征，按逗留特征将文件大致分割成两部分部署在当前基站和可达位置集中.定义函数G(t)表示用户在t时刻依然逗留在该基站的概率，其中t=0表示用户接入基站的时刻，则STF模型可以表示为：

G(t)=a×tb+c

(11)

用t0表示用户向远端服务器请求文件M的时刻，当然也可以理解为由主动推送服务器决策向用户推送文件M的时刻，至于具体请求/推送内容的不是本文重点分析的对象，不在此处赘述.假设用户的文件下载速率为常数V MB/S，则理论上用户如果不离开该基站所需的下载完成时间tend满足.

(tend-t0)×V=M

(12)

设用户真实离开时间为tl，理论离开时间为tl′.用事件A和事件B分别表示用户离开基站发生在时间点tl′前和时间点t0前，则用户在时间t0到tl′之间离开的概率ρ0的计算公式为：

(13)

其中Ψ2是判定离开是否发生的阈值，借此可以计算出用户理论离开时间tl′：

tl′=G-1[G(t0)×(1-Ψ2)]

(14)

4 分布式缓存缓存

4.1 RaptorQ编码文件

考虑到要将文件分割部署在多个基站上，并可以使用户从多个基站中恢复源文件，因此选择用网络编码的方式对文件进行分割.而在编码理论中，喷泉码是最高效的编解码算法，其可以从任意N′个编码符号中恢复原始的N个源符号从而提供可靠传输[14].而目前的喷泉码中性能最好的是Raptor码，它的编解码过程仅需要很少的常数量级的XOR操作，即在线性时间内即可完成[15]，其中RaptoQ码是Raptor码中目前性能设计最好的一个版本[16]，它有诸多优点比如：

①只要用户接收到任意足够多的编码符号，即可恢复出源文件，并且恢复概率极高如表1所示.

表1 RaptorQ编解码恢复概率表

②RaptorQ属于系统码，它的源符号是包含在编码符号中的，而恢复概率和接收到的编码符号具体归属于哪一部分无关.

图2 RaptorQ编码示意图

结合本文所需编码的文件M来分析，如图3所示，首先计算单次DMACacher所能处理的文件尺寸阈值M′，

(15)

图3 文件编码流程图

4.2 依概率分布式缓存

如果tend≤tl′，则认为文件可以在用户离开基站之前完成传输，即将全部的N个编码符号部署在基站tracez，x中.

如果tend≥tl′，则认为文件无法在用户离开基站之前完成传输，需要将全部编码符号分别部署在多个基站上.其中，先产生的N0个编码符号部署在基站tracez，x上，

N0≜[(tl′-t0)×ν]

(16)

N′=N-N0=N1+N2+N3+…Nζ

(17)

Ni=「ρi×N′⎤

(18)

(19)

4.3 缓存部署命中率

(20)

②当t0≤tl≤tend≤tl′时，N个编码符号全部部署在tracez，x中，且离开基站发生在完成传输之前，此时命中率为

(21)

(22)

④当t0≤tl′≤tend≤tl时，部署在trz，x中的编码符号个数为N0，且传输完成发生在真实离开之前，此时命中率为

(23)

⑤当t0≤tend≤tl′≤tl或t0≤tend≤tl≤tl′时，N个编码符号全部部署在trz，x中，且在离开基站前完成了传输，此时命中率为

R=1

(24)

5 实验验证与分析

实验中，首先挑选合适的用户移动轨迹数据库，根据轨迹数据训练轨迹特征预测模型，然后根据轨迹提取出时间信息并拟合逗留特征模型，通过Matlab仿真对本文提出的策略进行性能验证，并与其它多种算法进行性能比较.

5.1 实验数据集

实验中采用的原始数据是微软亚洲研究院从2007年到2012年间采集的182位用户的GPS轨迹信息，共17621条原始数据.该数据集的轨迹是遍布在中国、美国和欧洲，其中大部分集中在北京市区，为了更好建立模型，选取东经116.25°到116.5°，北纬39.85°到40.05°区域之间(大致范围属于北京市区)的8181条轨迹数据，每条轨迹长度不大于10.将选取出的区域按照经度间隔0.01°，纬度间隔0.01°均分成多个方形小网格，除去所有轨迹都未经过的网格，共获得106个小网格区域，而这里将每一个小网格抽象为一个基站的覆盖范围.

5.2 训练轨迹特征预测模型

从采集到的8181条轨迹中，随机挑选4000条用来训练轨迹特征预测模型.综合考虑实验效果和计算性能，将训练中需要预先设计好的用户类别总数K设为100.

表2 可达位置集的命中数和命中率

训练好模型后，另外随机挑选500条轨迹对模型预测能力进行验证.对每条轨迹，输入前3个基站，预测第4个基站，并与真实的到达第4个基站比较；再输入前4个基站，继续预测下去直至轨迹结束.其中每一次预测获得一个大小为5的可达位置集.统计全部可达位置集的命中率如表2所示，可以发现，可达位置集总命中率可以达到88.8%，一号预测的命中率达69.6%.而五号预测的命中率为0，表示MMM的方法在本实验中已经达到了其预测能力的上限.

5.3 拟合逗留规律

计算并统计出8181条轨迹所包含的每个基站的逗留时间，按照公式(11)拟合.拟合结果如图4所示，拟合函数为

G(t)=1.742×t-0.3091-0.1206

(25)

和方差为4.178，标准差为0.032.

5.4 缓存部署与性能分析

这里采用Matlab进行仿真实验，设定网络传输速率固定为1M/S，而1M大小文件可以用RaptorQ编码为1000个编码符号，考虑用户在任意时刻请求不同大小的文件，文件尺寸小于单次部署的尺寸限额，采用离散分布的移动感知缓存策略进行编码符号的部署，分析其部署的命中率，并与其他几种部署方法比较命中率和开销.选择的对比算法包括：

图4 逗留特征拟合模型

①Mobicacher，即将请求的文件全部推送在按马尔科夫方法计算出的最大概率的下一个基站上.由于此处比较的是部署性能的优缺，故实验中用本文的轨迹特征预测模型获得的最大概率预测位置替代了Mobicacher中的马尔科夫方法，而事实上本文模型所基于的混合马尔科夫的准确率远高于马尔科夫方法.

②Sprinkler，即将文件分割部署在沿途的基站上.但Sprinkler方法是假设已知固定轨迹并且没有考虑逗留时间，因此在实验中简化为将文件前一半部署在当前基站，后一半部署在下一个预测位置上.

③Noon-strategy，不采用任何部署策略，即服务器收到用户请求后将文件全部推送到用户当前所在基站上.

5.4.1 命中率分析

比较四种部署方法在请求不同大小文件时的命中率如图5所示，其中，Mobicacher在请求较小文件时命中率极低，因为它将文件全部部署在了下一个位置，而用户逗留在当前基站所需的数据包全部未命中，随着请求的文件变大，其部署在下一位置的命中比例也随之升高，但由于马尔科夫提供的下一个位置的准确度只有69.6%，所以基于马尔科夫方式的Mobicacher的命中率无法超过69.6%，而在实验限定了文件小于1000MB的场景下，最高只能达到60.6%的命中率.Sprinkler 本质上是一种折中的部署策略，在没有分析逗留时间的情况下，将文件固定拆分成两部分押注在两个基站上，所以其命中率的峰值出现在文件大小恰好适合对半拆分的时候，而其中押注的一个基站还要受约于马尔科夫的准确度限定，所以其命中率稳定且较低，均值为49.3%.而仅将文件全部推送到用户当前所在基站上的部署方式，会随着文件尺寸变大而不断减小，直至逼近于0，实验中由于用户请求文件的时刻是随机的，所以始终保持着一定的命中率，最低为15.7%.

而本文的DMACacher算法是将文件按逗留特征拟合模型分割成两部分，前一部分部署在当前基站上，后一部分借助RaptorQ编码部署在可达位置集上，前一部分的误差主要由于逗留特征拟合模型的误差导致，当文件较小时，该部分误差较小，文件大部分都部署在了当前基站，故其命中率较高，当文件变大时，拟合误差随之增大导致DMACacher算法整体命中率下降；而后一部分的误差决定于马尔科夫准确性，这里由于采用可达位置集替代单一的位置预测，因此，其马尔科夫准确性约束为整个可达位置集的总命中率88.8%，在实验中最低命中率为67%，远大于其他几种算法.通过命中率的比较，反映出DMACacher算法可以更加合理地部署缓存资源.

图5 四种算法的缓存命中率比较

5.4.2 资源开销分析

在这一部分，考虑转发造成的资源损耗进一步地分析不同算法间的性能差异，这里的资源损耗主要代表对骨干网的回程压力和用户的下载时延.

图6 四种算法的资源开销比较

四种算法资源开销如图6所示，可见四种算法在实验场景下随着下载文件变大，开销呈近线性增加，通过线性拟合可知DMACacher的斜率为288500，Mobicacher斜率为303600，Sprinkler斜率为429000，Non-strategy的斜率为622800，可见DMACacher的资源消耗量和消耗增长速率远低于其他三种算法.分析其本质原因是，DMACacher通过RaptorQ使多端存储转发成为可能，在数据包未命中时无须向远端服务器请求数据包从而大大降低了网络资源的开销.

6 结 论

本文针对当前移动数据流量爆炸式增长的现状，在小基站网络中，搭建对用户移动行为的智能感知层，通过集体行为与个体移动特征相结合的方式建立轨迹特征预测模型，对用户轨迹进行预测，并采用统计学的方式分析用户在基站中的逗留特征，拟合逗留特征模型.然后通过RaptorQ的编码，将文件智能化地分割部署在多个基站上.最终完整实现本文提出的离散分布的移动感知缓存策略.

通过理论分析部署策略的命中率，并结合实验与多种典型缓存部署算法进行性能比较，可以得出结论：本文提出的离散分布的移动感知缓存策略可以通过分析用户移动行为和逗留特征有针对性地进行智能化地缓存部署，大幅度地提高缓存部署的命中率，降低对骨干网的回程压力，减少用户的下载时延.