透明计算中用户访问行为特征分析与预测

王 斌，陈 琳，侯翔宇，李伟民，盛津芳

WANG Bin,CHEN Lin,HOU Xiangyu,LI Weimin,SHENG Jinfang

中南大学 信息科学与工程学院，长沙 410083

School of Information Science and Engineering,Central South University,Changsha 410083,China

1 引言

近年来，云计算作为网络计算模式的典型代表，使计算由软硬件为中心转变为面向服务的模式，能够根据终端用户的需求把服务端的存储和计算资源传输到客户端[1]。透明计算是云计算的一个特例，是一种以用户为中心的新型服务模式，旨在为用户提供无处不在的透明服务。

透明服务平台作为透明计算服务端的核心，负责统一存储并管理多个用户的资源，包括操作系统、应用程序和用户数据[2-3]。同时还要快速高效、安全和可靠地处理各用户发送的资源访问请求，以保证用户的服务体验质量。透明服务平台采用基于虚拟磁盘的方案来实现，在终端用户看来，服务端存储的是终端的虚拟磁盘数据，终端对虚拟磁盘的访问请求最终被重定向到服务平台[4]。针对透明服务端如何提高用户的虚拟磁盘数据访问效率和安全可靠性，文献[5]设计了一个局域网中高效可靠的块级存储访问协议NSAP（Network Storage Access Protocol）。文献[6]分析验证了基于虚拟磁盘的透明计算系统性能瓶颈在于服务端，而cache的命中率又是服务端性能表现最关键的因素，最后在服务端和客户端制定了缓存分配策略。文献[7]提出了一个评估透明计算多级高速缓存层次结构以及整个透明计算系统的行为和性能的模拟框架TranSim。通过使用TranSim，系统设计者可以方便快捷地评估缓存策略的有效性和系统性能。

如上所述，目前关于透明计算服务端性能优化和安全可靠性保障的研究侧重于自身的存储架构、调度策略和访问协议，但没有研究工作从透明计算需求的源头：用户以及用户访问行为的特征来分析和预测其对透明服务平台的影响。如文献[8]提出了基于关注关系和用户行为的物品推荐算法。文献[9]通过记录学生学习操作行为，并结合传感器数据，提出一种场景感知分类算法。文献[10]结合访存敏感和用户行为敏感的MPSoC应用映射技术，提出一种混合的动态映射策略。文献[11]分析了多台终端加载相同操作系统过程中数据的访问信息，发现用户行为具有集中和相似的特征。因此，本文在构建基于多层虚拟磁盘存储模型的透明服务平台基础上，首先对大量用户访问服务平台数据块的行为进行统计分析，并利用信息熵策略挖掘出被频繁集中访问块的时序特征。然后利用三次指数平滑方法预测未来一段时间用户对这些块的访问行为。最终结果可以为服务平台制定更高效的缓存策略提供有效的依据，进而帮助透明服务端提高服务性能和体验质量。

2 透明服务平台存储模型及访问机制

透明服务平台位于透明计算服务端，它为用户屏蔽了硬件平台和操作系统的异构性，统一集中管理系统资源，并转化为服务提供给用户。因此，透明计算用户自主可控地按需使用服务的过程本质是对透明服务平台数据访问的行为。透明服务平台的架构和原理决定了用户数据访问的机制，是用户行为分析的基础。

透明服务平台存储了所有透明终端用户的虚拟磁盘数据，但透明计算需要面对大量异构的终端用户，如果数据共享程度不高，会导致大量的数据冗余。为此，本文所构建的透明服务平台中，实现了一个多层树状虚拟磁盘存储模型，如图1所示。虚拟磁盘中数据资源按资源共享程度及性质划分成3类：系统资源、应用群组资源和用户个性化资源。系统资源主要指操作系统以及相关数据，该类资源共享程度最高，能被所有用户共享，所构成的镜像称为系统虚拟磁盘镜像（System Virtual Disk Image，S_VDI）。应用群组资源主要指各种相关的应用软件数据组成的集合，具有相同的应用属性的应用软件通常归为一个群组。该类资源只能被同一群组下的用户共享，所构成的镜像称为群组虚拟磁盘镜像（Group Virtual Disk Image，G_VDI）。用户个性化资源主要指用户的私有数据资源，一般包括用户私有文件或者操作系统、应用软件的个性化配置信息，该资源仅用户自身才能访问，所构成的镜像称为用户虚拟磁盘镜像（User Virtual Disk Image，U_VDI）。

在面对多终端用户对共享层资源同时进行访问时，采用写时重定向（Redirect on Writing，ROW）机制来进行控制。具体做法是：将系统虚拟磁盘镜像S_VDI和群组虚拟磁盘镜像G_VDI以只读的方式存储于服务端，共享给多个终端用户；采用ROW机制将终端用户对共享的虚拟磁盘镜像S_VDI和G_VDI的改写块保存于与用户对应的用户虚拟磁盘镜像U_VDI中，并采用Bitmap[12]来标记各个改写块的位置，从而实现了多个终端用户对共享数据的共同读写。在图1中，当用户i请求第7和8号数据块时，由于用户对应的U_VDI中存储了数据块7的改写块，对7号块的数据访问读请求被定位到用户对应的U_VDI，而数据块8在U_VDI和G_VDI的位图中都没有改写标记，因此其请求定位到了S_VDI，最后将所有读取到的数据块重新排序组合后返回给终端用户。

图1 透明服务平台虚拟磁盘存储模型及访问机制

需要注意的是，如果在有相关缓存机制的情况下，用户对服务平台的数据访问首先会被定向到缓存池。而本文所研究的用户行为是在没有缓存机制的情况下进行的，目的正是为了更好地挖掘和预测用户行为特征，为缓存策略提供依据。整个存储模型和数据访问机制对用户是透明的，用户所独占的一个既包括操作系统，又涵盖应用软件、个人私有数据的“本地磁盘”实际上在服务端被划分成多个部分，S_VDI和G_VDI是多用户共享，仅U_VDI为每个用户独享的私有数据。

由上述描述可以看出，透明服务平台的虚拟磁盘模型具有多层次、高共享和低冗余的特点，因此，其用户数据访问行为模型也会不同于其他虚拟磁盘存储模型。另一方面，透明计算是强调以用户为中心的网络计算服务模式，面对大量的异构终端用户，并且用户的所有资源均存储在服务端，用户在获取服务时会带来大量的与服务端的数据交互行为。因此，分析和预测透明计算用户行为特征具有重要的现实意义。

3 用户访问行为分析

3.1 行为表示

透明计算客户端是一个仅需保留必要的计算和输入/输出硬件的设备，本地不存储任何操作系统和应用软件，通过网络按需从服务平台将其以数据块的形式加载到客户端设备上流式执行。给定时间内，用户对服务平台的数据访问请求作为一次用户访问行为，用户访问行为用块的集合来表示。本文出现的“用户”是指全体用户的集合。基于此，给出下面相关概念。

定义1设某特定时间段Tα内被访问的数据块集合为，若时间点Tm∈Tα，所有用户在Tm时刻对数据块Bi的访问次数为count(Bi,Tm) ，那么数据块Bi在Tα时间区间内被用户访问的频数为：

通过式（1），得出在Tα时间区间内不同数据块被访问的频数集合F={FB1,FB2,…,FBn}。记数据块Bi在Tα时间区间内被访问的概率为P(Bi)，那么：

对不同数据块在Tα时间区间内计算访问概率，得出概率集合P={P(B1),P(B2),…,P(Bn)} 。

3.2 行为熵策略

香农提出的信息熵概念，反映了信源整体的统计特性，是对总体的平均不确定性的度量。

用户的行为表现为：对透明服务平台上不同数据块的访问。对这一信源进行熵运算，可以从宏观上量化用户的操作行为特征[13]。根据信息熵的相关概念与公式，结合3.1节的概率集合P，得出其概率空间表示为：

基于信息熵本身的概念，能够得到如下的推论。

推论1H(B)越大，用户对数据块的访问越平均，即在该区间内，用户行为越分散。反之，H(B)越小，用户对数据块的访问越集中，即在该区间内，用户行为越集中，则越能体现出用户行为偏向和特征。

证明 以各数据块被访问的频数集合{FB1,FB2,…,FBn}为离散信源，依据最大离散熵定理和信息熵的极值性，有即当信源出现的可能性相等时，信源的熵达到最大。由此可得，H(B)越大，用户对数据块的访问行为越分散；H(B)越小，说明用户行为越集中。

推论2H(B)=0具有两种不同的含义。第一种表示在该区间内用户只对某一数据块进行操作，即对该数据块的需求为100%；第二种表示在该区间内用户对所有的数据块都没有进行操作，即所有客户端都没有被使用。

证明 由信息量的非负性可知，当H(B)=0时，对于任意数据块Bi，有如下推导：

P(Bi)=0或lbP(Bi)=0⇒P(Bi)=0或P(Bi)=1

那么，由信息熵的确定性可知，P(Bi)=0即为用户只对数据块Bi进行操作；P(Bi)=1即为用户对所有的数据块都没有进行操作。

在多台透明服务终端设备相继启动时，记录该时间段内对数据块的访问信息，计算对各个数据块的访问次数，访问分布的情况如图2所示。

图2 多台透明服务终端启动时数据块访问分布

这些数据块即为系统共享资源存储层中操作系统启动时需要加载的对象。在这段时间内，68.591%的访问集中在了17.8%的数据块上，呈现为长尾分布。因此利用信息熵量化用户行为并挖掘行为时序特征是可行的。

3.3 行为特征归类

用户在不同的时刻对资源有不同的需求，式（3）计算出来的熵值反映了一段时间内用户宏观上的行为特征。本文根据熵值判断用户当前行为属于集中式还是分散式的特征，因此需要对用户行为熵集合中的熵值进行处理。

（1）根据熵值初步地把用户访问行为分成分散式和集中式两类。记录下熵值所对应的时间T，用二元组HT＜H,T＞来表示不同时间段的熵值。用户行为熵集合HTS={HT1,HT2,…,HTn}，为HT按时间推进的有序集合。选取HTS中熵值最大的点HTj和最小的非零点HTk。借鉴数据挖掘中的K最近邻算法，将HTj和HTk作为种子结点，并且遍历HTS集合，得到两个以HTj和HTk为中心的有序的类集合HTjS和HTkS，集合中元素顺序为HT下标的升序排列。

（2）分别对有序集合HTjS和HTkS进行处理，获得用户行为集中或分散的连续时间段。若其中HT下标为连续的，将这些连续的点归为一个小集合；若HT下标出现断点，则从该点开始，使之与后面下标连续的点归为一个新的小集合。将获得的所有小集合按时序生成特征轨迹，至此便完成了对HTS中熵值的特征归类。

算法1特征归类算法

输入：HTS //用户行为熵集合

输出：Collections //表示用户行为分散或集中的连续时间段集合

1.提取HTS中的最大、最小熵值

pick the max and min H in HTS

2.根据信息熵对用户访问行为分类

i←0

for eachHTinHTS

If|HTi.H-Hmax|＞|HTi.H-Hmin|then

addHTiintoHTSmini←i+1

else

addHTiintoHTSmax

i←i+1

3.对表示访问行为集中的集合按时间连续性进行划分

i←0

for eachHTinHSmin

pickHTj（HTjis the next one ofHTi）

ifj=i+1then

addHTiandHTjinto one Collection

i←i+1

else

addHTiandHTjinto different Collection

i←i+1

4.对表示访问行为分散的集合按时间连续性进行划分

do like step 3 inHSmax

5.return Collections

设算法1返回的集合群体为S1,S2,…,Sn，以时序排列。有这样的特点：（1）同一集合中的熵值是等价的，即使其数值不同，但是含义相同，表示用户在此时间段内的行为是分散的或集中的。（2）两个相邻的集合Si与Si+1，一个处于“峰”，一个处于“谷”，处于“峰”的熵值代表该时间段内用户的操作为分散式，而处于“谷”的熵值代表操作为集中式。

3.4 行为预测

用户对不同应用的操作和对不同文件的读取请求，通过对服务端数据块的访问来实现。本文根据3.3节描述的行为特征归类，选取在一段时间内呈现出被集中访问的数据块作为预测的对象。若数据块在近期访问次数较多，并且预测出在短时间内仍然保持着较高的访问量，说明用户短时间内的操作仍然集中在某些应用和文件上。根据预测结果可以优化服务端缓存替换策略，缩短客户端的响应时间。

指数平滑法[14]是基于时间序列进行预测的重要方法。它认为时间序列的态势具有稳定性或规则性，最近的过去态势，在某种程度上会持续到未来。指数平滑法兼容了全期平均和移动平均所长，不舍弃过去的数据，但是仅给予逐渐减弱的影响程度，适用于中短期趋势[15]。用户的访问行为具有时序性，且本文涉及到的预测是对短时间内仍保持较高访问量的数据块访问次数的预测，因此选用指数平滑法作为预测模型。

指数平滑预测方法有多种模型：

（1）一次指数平滑值

（2）二次指数平滑值

（3）三次指数平滑值

其中，α为平滑系数；yt为t时刻的观测值；为一次、二次、三次指数平滑值。一次指数平滑法只适合于具有水平发展趋势的时间序列分析；二次指数平滑法是对一次指数平滑的再平滑，能够修正滞后偏差，但也只适合于对具有线性特征的模型进行预测[16]；三次指数平滑法是唯一的非线性平滑法，尤其适用于时间序列上呈二次曲线趋势的预测[17]。

随机抽取透明计算服务端的某数据块，图3为其一个小时内被访问的次数，可知数据块访问次数在时序上呈现出非线性的变化特征，因此三次指数平滑法更符合数据块访问量的变化趋势，本文采用三次指数平滑法进行预测。

图3 数据块在各周期的访问量

三次指数平滑法的预测模型为：

其中，̂t+T表示t时刻之后T个周期的预测值。3个预测参数at、bt、ct由一次、二次、三次指数平滑值通过下式计算得出：

4 实验分析

为了验证信息熵与三次指数对用户行为预测的有效性和准确性，本文采用透明服务平台进行实验。该系统包括一个透明服务器、30台瘦终端、5台移动终端。透明服务器采用三层存储模式，分别存储操作系统、组群、用户的数据；瘦终端和移动终端没有硬盘和操作系统，只有运算功能和基本的缓存，分别以有线和无线的形式连接网络。实验中35名用户使用Win7和CentOS6.5两种操作系统各自自由操作90 min。每个终端并行使用多种应用，根据统计分析，平均每隔5 min用户使用的应用和访问的文件极大概率会产生变化。因此，透明服务器将监控到的数据块的访问以5 min为一个时间周期进行统计，将90 min分为18个时间段。

4.1 统计信息熵及行为归类

根据使用Win7和CentOS6.5下的两次实验结果，在35个用户90 min的自由操作中，平均请求数据块1253万次，每个时间段访问到的不同数据块约32000到48000个。使用式（3）计算各个时间段内的信息熵，取前10个周期结果如图4所示。

图4 信息熵时序图

由图4可以看出，两条信息熵曲线在时序上有比较明显的波动，信息熵的数据反映了所有用户的操作行为特点。熵值较高的时间段表示用户使用的应用和读取的文件比较分散；熵值较低的时间段表示用户使用的应用和读取的文件比较集中，即用户的行为更加集中。两条曲线中熵值最低的时间段均为最早的几个周期，数据块的访问最为集中。经过分析，这段时间内，终端大多为启动阶段，主要从透明服务平台三层存储的系统虚拟磁盘层中访问和加载操作系统资源，这一层数据共享程度最高，因此访问最为集中。后续时间周期中，用户自由操作，主要从群组虚拟磁盘层和用户虚拟磁盘层中按需访问数据块，同时也会从系统虚拟磁盘层中加载少量用来支持应用运行的数据块，因此后续时间周期的信息熵整体上大于初始时间段。

信息熵量化了用户的行为，为了对每个时间段内用户行为分类，对得到的熵值做特征归类处理，结果如图5所示。

图5 信息熵特征归类处理

图5显示了图4中两条曲线特征归类后的结果，将反映用户同一行为特征的点归于一类。由图可知，用户在使用CentOS6.5操作系统时，在1、2、3、7、8、10这几个时间周期内，用户使用的应用或访问的文件较为相似，行为较为集中；在其余时间段内行为较为分散。同理可找到使用Win7系统时，用户行为集中和分散的时间段。

根据图5得到的结果，选取两条曲线中熵值较低的时间段内包含的数据块。根据统计，CentOS6.5和Win7两次实验中，用户行为集中的时间段内访问的不同数据块个数分别为4257块和3962块，占整个实验访问过的所有数据块的15.8%和12.3%。

4.2 平滑系数α拟合

本文使用三次指数平滑法对数据块的访问数量进行预测，使用式（4）进行计算。其中平滑系数α是三次指数平滑法拟合效果的关键，如果数据波动较大，α值应取大一些，可以增加近期数据对预测结果的影响。如果数据波动平稳，α值应取小一些。本文在确定α值时采用试算法，即取多个α值进行拟合实验并加以比较。实验α取值范围为[0.1，0.7]，取值步长为0.05，选取Win7、CentOS6.5实验中待预测的数据块各1000个，比较不同α下预测的均方误差MSE，选择误差最小的α值。拟合实验结果如图6所示，实验选取0.35作为α的值。

图6 α拟合实验

4.3 数据块单周期预测

本实验通过比较预测值和观测值的误差衡量预测算法的准确度。随机选取一个数据块，偏移量为1033808，从第5个周期开始，使用式（4），取T=1。根据当前的观测值不断预测下一个周期该数据块的访问次数。结果如表1所示。

表1 单个数据块6～18周期预测情况

根据前10个周期的观测值，对两次实验中的4257个数据块和3962个数据块进行第11个周期的访问预测，使用式（4），同样取T=1。以作为准确率的衡量指标。其中St代表t时刻的预测值，Yt代表t时刻的观测值，E的取值越小代表越精确。预测结果精确度分布如图7所示。

图7 预测结果精确度分布

在误差低于0.1，0.1～0.2，0.2～0.3以及高于0.3的范围内，数据块所占比例分别为：CentOS，65%、18%、10%、6%；Win7，62%、21%、8%、9%。

在上述两个实验中，使用三次指数平滑预测算法预测一个周期后的数据块访问次数。表1证明了此算法可以在时序上根据观测值不断修正预测结果，迅速减小预测误差；图7证明了此算法可以对下一个周期数据块的访问次数给予较为精准的预测。

4.4 中短周期预测精度测试

4.3节证明了三次指数平滑算法在单周期预测精确度较高，但仅仅能预测一个周期是不够的。为了验证此算法在多少周期内预测结果可接受，以前10个周期作为观测值，对所有数据块进行第11～18周期的预测。使用式（4），T分别取1～8，并以平均误差作为衡量指标，实验结果如图8所示。

图8 中短周期预测精确度测试

上述实验表明，在预测1～3个周期时，平均误差分别为0.07、0.12、0.19，从第4个周期开始，误差急剧增加。由此得出结论，使用三次指数平滑预测法可以对数据块在3个周期内给予较为准确的预测。

5 结束语

本文在透明计算背景下，根据透明服务平台三层虚拟磁盘存储的特点，基于信息熵和三次指数平滑对透明计算用户行为特征进行分析和预测。此方法基于信息熵策略从宏观上分析用户行为需求，进而挖掘出被频繁集中访问的数据块的时序特征。在此基础上利用三次指数平滑算法预测将来一段时间内这些块的访问频率。实验表明，此方法能够较为准确地发现集中访问的数据块，并对这些数据块给予较为精确的预测，从而达到对用户行为分析和预测的目的。预测结果为制定更高效的缓存策略提供有效的依据，从而提高透明计算服务质量与性能。