基于马尔可夫修正模型的视频预测策略

桂易琪,鞠爽爽

(扬州大学信息工程学院,江苏 扬州 225100)

0 引 言

随着互联网的发展，人们对P2P流媒体的关注越来越密切。在这样的背景下，以热点视频预测为切入点的研究引起了高度的重视，并成为未来的发展趋势。对热点视频的预测是一种多模式的问题，因为正确的预测需要挖掘出很多视频中未给出的潜在信息[1]。对于预测来说，通过用户的行为感知用户的兴趣爱好，起着非常关键的作用。但是，由于用户操作的交互性及网络状态变化的随机性，视频预测的准确性和有效性是一个紧要问题。本文提出一种基于马尔可夫修正模型的视频预测策略。该策略能够在用户和网络随机变化的情况下，自适应地对热点视频进行预测，具有更高的可行性和准确性。相比于使用神经网络，本文算法可避免复杂的训练过程，显著提高视频的播放质量。

1 相关工作

最近几年，为了提升视频软件的播放效率和质量，国内大量的学者对此进行了广泛研究。对热点视频段的选择是P2P流媒体中一个具有挑战性的领域，准确地识别出热门视频至关重要[2]。

由于P2P流媒体中各节点可在服务节点和请求节点之间相互切换，所以用户量的增多也会带来服务节点跟请求节点的增多，这会导致网络流量的增多。因此需要P2P流媒体中的缓存策略选择合适的节点并合理地替换掉该节点中的视频段，通过提高视频段命中率的方式减少请求节点的搜寻时间，进而减少网络压力。文献[3]提出了一种基于访问集中的缓存替换策略。该策略根据视频段的访问次数等指标进行缓存，这种方式类似于选择流行度较高的视频段进行缓存；该策略通过一段时间积累用户访问记录，再运行缓存替换策略，周期性地对节点中的数据进行更新。文献[4]提出了基于预测的网络制造资源访问策略，对用户查找频率实现实时监控，通过多项式回归预测技术进行动态预测，以避免因用户兴趣改变而引起预测的不确定性。文献[5]针对边缘节点缓存空间有限的问题，提出了一种基于猴群算法的优化策略。该策略通过在猴群算法的猴群爬过程中引入文件流行度等引导因子和在望过程中改进猴群视野范围等方法找到最优解，并合理地对边缘节点的缓存内容进行替换，有效提高边缘节点的请求命中率。文献[6]提出了热节点缓存优化方案，提出了基于数据频率的缓存算法。实验结果表明使用数据频率缓存算法来缓存数据比传统置换算法更趋近理论值，数据的请求延时相对较低。

文献[7]提出了一个基于集群的合作缓存机制，即集群内成员节点进行内存共享，在集群中的节点会有重复缓存的内容，为了减少这些重复的内容，所有集群成员的一部分缓存空间相互共享，该机制可以节约节点存储空间，扩大有效缓存。文献[8]提出了一种基于SVC(可扩展视频编码)的分割方法。该策略通过将视频编码分割再传输，可以有效降低数据在P2P流媒体中传输时遇到的复杂情况，减少数据丢失、数据错位等现象，提高了P2P网络中数据传输的稳定性。文献[9]提出了一种基于ABR的激励方案，目的是保证用户的视频播放质量，同时减少云的带宽消耗。文献[10]提出了一种在P2P-VoD流系统中面向QoE的新颖块调度，其中包含基于请求队列的负载平衡(RQLB)策略和基于消除索引的缓存替换(EICR)策略。在提出的RQLB策略中，定义块请求的优先级，使高优先级的请求得到及时处理。在设计EICR策略时，考虑到视频中的块可能具有不同的流行度，因此选择缓存值最低的块进行替换，有效解决P2P-VoD流媒体系统中的块调度问题，保证了观众的QoE。为了使缓存结构的共享性能最大化，文献[11]提出了一种核心感知的重新引用间隔预测替换算法(CA-RRIP)。该算法对部分共享的缓存执行动态虚拟分区，保证了缓存的排他性，并可以减轻使用不同访问模式的内核之间的交互。文献[12]提出了一种P2P-TV流媒体节点上行速率控制算法，该算法对于网络模型的不确定性、网络参数的时变性以及网络抖动具有较强的鲁棒性。文献[13]针对如何使混合型架构流媒体内容分发系统服务容量最大的问题，按照多文件分发的服务容量模型将带宽分配问题映射为背包问题，提出了利用遗传算法进行服务器带宽分配的方法，提高了系统服务容量。

内容中心网络(CCN)是面向未来Internet的新体系结构[14]。CCN依赖于网络内缓存，并且数据的多个副本存储在网络中。任何具有数据的节点都可以满足将来的请求，并有助于减少服务器的负载和网络的拥塞。CCN[15-19]是一种新的客户端/服务器网络体系结构，可通过使用多个服务器提高网络传输效率并增加用户数量。在内容中心网络体系结构中，网络中的每个路由节点都具有缓存功能。通过网络内缓存，CCN避免了当前TCP/IP网络中相同内容的重复传输，因此CCN减少了网络带宽资源消耗，并加快了网络对请求的响应速度。所以，人们提出了一些以内容为中心的网络架构(ICN)。这些架构与传统的服务器缓存不同，其主要利用网络中的节点来缓存，这种无处不在的缓存可以提高内容的分发效率以及避免过于集中的访问，而且缓存对应用透明。这些卓越的功能给ICN缓存技术提出了新的挑战，也是未来需要研究的切入点。

2 系统模型

新视频刚上映时，由于没有大量的用户访问记录，无法通过统计来获得准确的用户观看趋向和视频段的流行度。马尔可夫模型可以通过用户访问记录获得用户初始状态和状态转移矩阵，在不受用户访问记录数量的约束下，获得相比于统计学更为准确的用户趋向，再通过后续到达的用户访问记录不断修正状态转移矩阵，可获得较高的视频段预测命中率。以下介绍本文所提策略。

为了提升用户的观影体验，使用户在观看视频时随意跳转都不需要等待缓冲，本文通过分析用户的历史操作，建立马尔科夫修正模型对用户将要访问的段进行预测，有选择地解决预取问题。由于用户访问段不是随机访问，都具有一定的规律，随着用户访问次数的增加，这种规律越发明显。本文将马尔科夫模型和指数加权平均模型进行融合，在系统迭代过程中，使用指数加权平均模型修正状态转移矩阵。准确缓存用户即将要看的视频段，提高段缓存的命中率。

在马尔科夫预测模型中，根据用户访问记录即先验数据，提取出用户访问规律，得出初始状态转移矩阵以及用户访问初始概率。为便于表达，以下假设用6条数据产生状态转移矩阵。

表1 用户访问记录1

在表1用户访问记录中，用户初始访问第1段的概率为2/15，访问第2段的概率为4/75，则用户初始访问概率矩阵为：

(1)

从以上仅有的6条用户访问记录中可知，当用户访问第1段后，再次访问第1段的概率为0，访问第2段的概率为5/6，访问第3段的概率为1/6，访问其余段的概率为0；用户访问第2段后，访问第1段的概率为1/7，访问第3段的概率为5/7，访问第4段的概率为1/7。以此类推，可得这6条数据的初始状态转移矩阵S0：

(2)

由于用户具有较强的主观意识，在系统迭代过程中，固定不变的状态转移矩阵无法准确描述视频段被访问概率的变化过程。先验概率在系统执行初期能有不错的表现，但随着系统的持续迭代，需要对状态转移矩阵进行修正，使其能更准确预测段的被访问概率。

本文使用指数加权平均模型对状态转移矩阵进行修正，将旧的状态转移矩阵通过加权求和的方式加入到新的状态转移矩阵中。当系统持续迭代时，新的用户访问记录加入到旧的访问记录中，由于会有大量的用户访问记录，使用累加计算的方式求状态转移矩阵的计算量会逐步增大。考虑到用户访问记录之间的时序关系，本文使用滑动窗口的方式，读取用户访问记录，获取“影子状态转移矩阵”。如图1所示。

图1 滑动窗口示意图

再使用指数加权平均模型对模型进行修正，从t0时刻的用户访问记录中获取t0时刻的状态转移矩阵S0；从t1时刻的用户访问记录中获取t1时刻的状态转移矩阵S1；从t2时刻的用户访问记录中获取t2时刻的状态转移矩阵S2。

则当前时刻的状态转移矩阵估计Sn_now为：

(3)

表2为新的用户访问后的用户访问记录表，其中用户编号为7、8、9的记录是新加入的用户访问记录。

表2 用户访问记录2

根据滑动窗口的读取方式，在t1时刻，从第4条～第9条访问记录中提取状态转移矩阵。

则t1时刻的“影子状态转移矩阵”为：

(4)

可得t1时刻的状态转移矩阵估计为：

(5)

为便于本文所提状态转移矩阵的表述，此处设a=0.5，则：

(6)

由此，可以计算每个时间点的视频段被访问概率，下面给出前3个时间点的视频段被访问概率：

P1=P0×S0

(7)

(8)

(9)

本文提出的基于修正马尔科夫预测模型的视频段预测策略中，首先根据修正马尔可夫模型预测出视频段被访问概率， 再选择访问概率较大的段进行缓存。

基于马尔可夫修正模型的视频预测策略如表3所示。

表3 马尔科夫修正预测模型(MMPM)

将基于马尔可夫的视频段预测策略搭载在基于流行度的缓存替换策略中，得出基于马尔可夫链的缓存替换策略(CRA-MMPM)算法如表4所示。

表4 基于马尔科夫修正模型的缓存替换算法(CRA-MMPM)

3 仿真实验

本文生成100,000个数据段，使其满足正态分布，再将这100,000个数据段按图2的分组方式分成10,000条数据，构成用户访问记录数据集。

假设以1000条数据提取视频段被访问概率和初始状态转移矩阵，9000条数据作为后续访问记录，分9批进入系统迭代。

图2 仿真数据排列

具体仿真条件如表5所示。

表5 参数列表

本次实验用户以10个为一组进入系统，直到用户数达到100，观察其命中率变化，并设置计数器，每命中一次，该段计数器加1。

将策略MMPM分别基于缓存替换(CRA)和先进先出(FIFO)算法运行，并与CFCD[20]和PCN[21]进行比较，具体仿真结果如图3～图6所示。

图3和图4分别表示CRA-MMPM和FIFO-MMPM在迭代过程中的命中率变化趋势，并且加入基于流行度的先进先出策略(FIFO-P)和基于流行度的关联规则策略(VOVO-P)进行比较。从图中可看出，随着迭代次数的增加，命中率越来越高，并且一直高于PCN和CFCD算法。由于没有使用高级的流行度评估方式，在70次迭代之前，使用MMPM策略的算法命中率上升较快，随着迭代次数的增加上升趋于缓慢，甚至保持不变。相比于FIFO，CRA具有较为科学的缓存替换方式，所以CRA-MMPM比FIFO-MMPM具有较高的命中率，且一直如此。

图3 CRA-MMPM命中率1

图4 CRA-MMPM命中率2

图5 FIFO-MMPM命中率1

图6 FIFO-MMPM命中率2

图5和图6对使用MMPM模型的算法与未使用MMPM的算法进行比较。FIFO-MMPM相比其他的算法皆具有较高的命中率。由于在MMPM中融入了滑动加权平均的方式将以前的状态转移矩阵进行叠加，使得状态转移矩阵可以包含更多的信息，可以更有效地做出预测，相比于未使用预测策略的模型会取得更好的效果。

4 结束语

本文针对用户的兴趣爱好展开研究，对热点视频进行预测。所谓预测，就是在服务器处理用户请求的同时，利用预测算法对用户下一步可能访问的视频内容进行感知挖掘，将预测内容存放在服务节点中。本文通过构建用户的历史播放记录，进行实时监测，提出了基于马尔可夫修正模型的视频预测算法，实现动态预测，避免了因用户兴趣漂移引起的预取不确定性，提高了命中率及响应速度，验证了算法的有效性、准确性及快速性。