移动云计算是一种将移动互联网与云计算相结合的新技术，用户可将数据的计算和存储等工作迁移至云端来克服其移动终端处理能力弱、存储空间小等缺点.从移动互联网和云计算的特征看，可以将移动终端和云计算设备两者结合起来，手机的任务是交互，复杂的计算则由云端来完成，利用云计算改善移动端的局限性.因此，用户将移动云计算的云端作为服务中心，移动终端不需要拥有强大计算存储能力便可为用户提供所需的服务.研究结果表明，移动云计算中与服务器建立数据连接、数据传输时能量消耗较多，这是导致智能手机能耗过快的主要原因.笔者将相似用户访问数据的相似性和用户行为数据的可预测性这2个因素考虑在内，提出了基于用户交互行为最大化的链路预测方法(LP-MUIB, link prediction method based on maximum user interaction behavior).

1 相关工作

针对电池耗电过快的问题，国内外专家学者从不同的角度对移动终端节能技术展开了研究.

Muharum等^[1]提出了Android操作系统的节能应用程序接口(API, application programming interface)，将应用程序转变为能量感知应用程序以实现节能. Eom等^[2]研究了云环境下能源消耗与各种编码类型之间的相关性，并提出了一种基于功率感知的编码方案，最大限度地延长移动终端的续航时间.

为了改善移动应用的性能，一些学者引入计算迁移的概念. Mazza等^[3]在移动终端满足执行时间合理的基础上实现了最小化耗能的目的. Gu等^[4]开发了一个自适应的迁移系统，但是需要修改Java虚拟机来支持对象在智能手机和服务器的透明迁移.

殷波等^[5]针对当前虚拟机迁移方法考虑了迁移成本或者由应用相关性带来的虚拟机之间的通信成本，提出了一种虚拟机迁移策略，以实现数据中心节能的目标，并且综合考虑了迁移成本和通信成本.王安^[6]将移动终端节能技术与移动网络技术相结合，对移动终端数据传输过程中的能量消耗进行了深入分析.

2 LP-MUIB

所提出的LP-MUIB方法分为2个阶段：①交互行为最大化阶段.提出基于用户交互行为的影响最大化方法. ②链路预测阶段.提出一种基于互动关系随机游走的算法.

2.1 基于LP-LUIB节能框架模型

移动云计算下用户访问数据预测的手机节能模型框架如图 1所示，在现有云服务器中增加交互关系最大化和社交网络链路预测模块.框架的核心是服务器端用户数据预测模块，它的主要任务是：当用户通过手机向云服务器查询数据时，通过服务器数据预测模块查询出用户的历史访问数据和社交活动，再利用所提出的LP-MUIB方法预测当前用户将未来可能再次访问的数据预存到手机端，降低因通信环境差与云端进行的多次交互.

2.2 基于用户交互行为的影响最大化方法

步骤1 构建邻居组，计算交互度

当用户u向服务器发起请求时，根据该用户和邻居用户交互次数历史数据信息Inter，构建邻居组.采用改进的交互度方法计算邻居组中各个邻居对目标用户的交互度.用户u与v的互动次数表示为I(u, v).

基于用户间相互影响力和接触次数(W)的考虑，给出用户交互度的计算公式：

$ T(u,v) = \sqrt {{W_{uv}} + {W_{vu}}} + \sqrt {{W_{uv}} + {W_{vu}} - |{W_{uv}} - {W_{vu}}|} $

(1)

文中朋友关系是无向的，则用户之间交互度的公式为

$ T(u,v) = 2{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sqrt {I(u,v)} $

(2)

步骤2  计算基于交互行为的社交影响力

基于式(1)得出的邻居组中邻居用户与目标用户的交互度，不能直接用于评估用户之间的影响力.因为在实际情况下，邻居用户对目标用户的影响力不只是互动关系，还包括朋友关系.一般情况下，好友的数目与互动次数I(u, v)之间的关系不具规律性，而且不是一个量级，因此无法直接计算朋友关系和互动关系对目标用户的影响，需要对互动次数做一定比例换算，即

$ S(u,v) = T(u,v)\frac{{{W_{uv}}}}{{\sum\limits_{w \in N(v)} {{W_{wv}}} }} = T(u,v)\frac{{I(u,v)}}{{{W_v} + {W_u}}} $

(3)

其中：S(u, v)表示用户u与用户v之间通过交互行为对彼此的影响力，T(u, v)表示式(2)计算的交互度，N(v)表示用户v的邻居集，W_uv为2个用户的交互次数.

从式(3)中可以看出，W_uv代表的2个用户的交互次数对S(u, v)起决定作用，能够计算出具体的S(u, v)数值，衡量用户之间基于交互行为的影响力. S(u, v)越大，表示u、v之间关系亲密度越高，用户u就越可能访问到用户v的历史数据；S(u, v)越小，表示u、v之间的亲密度越低，用户u访问用户v的历史数据的可能性越低. S(u, v)对用户历史访问数据信息进行归一化计算后，基于用户交互行为的影响最大化算法如算法1所示.

算法1 交互影响力算法

输入：用户交互行为信息Q={id, data, Inter, friend}

输出：S

1  for Q do

2  G = (V, E, W)undirected graph ←Inter, friend;

3   for q_i∈Q, I_i∈Inter

4    if I_i>0

5    构建邻居组Q_k；

6   for u_i∈U do

7    for u_j∈Q_k do

8     T(u_i, u_j)←I(u_i, u_j);

9    for u_i∈U do

10     for u_j∈Q_k do

11    calculate S(u_i, u_j)←T(u_i, u_j);

12  return S

首先根据数据库中用户历史互动行为信息Q构造社交网络无向图G，进而通过Q中Inter寻找各用户与目标用户之间的互动次数.若I_i>0，代表用户与目标用户之间存在互动关系，将用户u_j加入邻居组Q_k中；若I_i = 0，代表用户与目标用户之间不存在互动关系，放弃用户u_j.算法第6~11行表示利用邻居组Q_k中各个邻居与目标用户之间的互动次数I(u_i, u_j)计算各个邻居与目标用户的交互度T(u_i, u_j)以及相应的交互影响力S(u_i, u_j)，为下一阶段基于互动关系随机游走的方法做准备.

2.3 基于互动关系随机游走的链路预测 2.3.1 基本思想

链路预测推荐方法的关键是计算用户间的相似度，相似度越高的邻居用户的访问数据越可能作为目标用户下一步要访问的数据.用户间的相似性具有媒介性、衰弱性、共同好友性和发散性等特征，如图 2所示.

针对朋友选择问题，通过对社交网络FriendLink方法进行分析，基于用户行为引入互动关系，以识别社交网络中的不同相关强度的朋友，形成权重社会网络，提出一种基于互动行为局部随机游走的推荐方法，其基本流程如图 3所示.

随机游走包括2个步骤：①通过朋友关系与互动行为，分析出带权的关系网络；②在包含互动次数的关系网络上，利用基于互动行为改进的偏向相似度高节点游走方法计算邻居与目标用户u的相似度，取得TOP K个用户数据作为用户u即将要访问的数据.

2.3.2 方法描述

步骤1 分析相关强度

根据图的连接理论定义社会网络为G = (U, E).其中u_i、u_j∈U，若2个顶点u_i和u_j之间存在朋友关系，即通过边建立连接，(u_i，u_j)∈E，则a_ij = 1；否则为0.因此能够用对称的邻接矩阵A = (a_ij)∈{0, 1}表示无向无权重社交网络. u_i的邻居集合表示为Γ(u_i) = {u_j|(u_i，u_j)∈E}，u_i与u_j的互动次数表示为I(u_i, u_j).

具体地，仅仅考虑朋友网络，用户u_i和u_j的朋友关系强度W_ij如式(4)所示.用户u_i和u_j间的共同朋友数量起决定作用.

$ {W_{ij}} = \left\{ {\begin{array}{*{20}{l}} {|\varGamma ({u_i}) \cap \varGamma ({u_j})| + 1,({u_i},{u_j}) \in E}\\ {0,({u_i},{u_j}) \notin E} \end{array}} \right. $

(4)

根据用户间共同朋友数目的多少和互动次数来表示他们之间朋友关系的强弱，改善网络拓扑结构的实际准确性.通常情况下，若用户更加关注某用户的数据信息，则该用户更可能会选择此数据作为接下来要访问的数据.若考虑用户个性化行为的互动次数，关系强度会向用户行为方向变化.如式(5)所示，用户u_i和u_j的相关强度W_ij由两者间媒介数量与基于交互行为的相互影响力之和共同决定.

$ {W_{ij}} = \left\{ {\begin{array}{*{20}{l}} {|\varGamma ({u_i}) \cap \varGamma ({u_j})| + 1 + S({u_i},{u_j}),{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} ({u_i},{u_j}) \in E}\\ {S({u_i},{u_j}),{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} ({u_i},{u_j}) \notin E} \end{array}} \right. $

(5)

这样，基于交互行为的互动关系影响力强弱会对相关性产生较大影响，更加符合实际用户行为.因此能够用对称的邻接矩阵A′ = (a′_ij)_n×n表示本研究的无向权重社交网络，其中a′_ij = w_ij.

步骤2  计算相似度

如图 2所示，根据数据库中历史互动次数I(u, v)计算出S(u, v)，即S(u₁, u₂) = 1; S(u₁, u₃) = 3;S(u₁, u₄) = 4; S(u₂, u₃) = 2;S(u₂, u₄) = 1; S(u₃, u₄) = 2，则此局部权重社会网络的对称邻接矩阵A′应表示为

$ {\mathit{\boldsymbol{A}}^\prime } = \left[ {\begin{array}{*{20}{l}} 0&2&4&4\\ 2&0&4&3\\ 4&4&0&4\\ 4&3&4&0 \end{array}} \right] $

由于在社会网络中，比起认识的朋友，用户更可能选择相关强度高的朋友的历史访问数据作为将要访问的数据.关系亲密的朋友可能不是直接朋友，有可能是互动关系强的潜在朋友，因而游走者需要考虑互动行为影响力，不再像简单拓扑结构那样等概率地游走.局部随机游走过程可以使用转移概率矩阵来描述，其元素为

$ q_{ij}^\prime (t) = \frac{{{w_{ij}}}}{{\sum\limits_{{u_k} \in \varGamma ({u_i})} {{w_{ik}}} }} $

(6)

表示随机游走者选择从顶点u_i到u_j的概率，等比于基于互动关系的相关强度.这样，游走者选择方向的概率更偏向互动关系强的用户，进而u_i、u_j的相似度可以通过游走者从起始点u_i经历多次路径到达u_j的概率来计算，称之为sim(u_i, u_j).

$ {\rm{sim}} ({u_i},{u_j}) = \sum\limits_{a = 1}^b {\prod\limits_{t = 2}^l {q_{ij}^\prime } } (t) $

(7)

其中：b为u_i与u_j之间可能的路径个数；t为在某一路径内第t个步骤；l为游走者游走路径长度，即总步骤数.

例如，图 2(a)中，目标用户是u₂，通过对称邻接矩阵A′计算转移概率矩阵Q′的元素q′_ij(t)，得到sim(u₂, u₁) = 2/(2+4) = 0.3，sim(u₂, u₃) = (2/2+4)/(4/2+4) = 0.83.

与u₃相比，u₁与u₂的相似性更强，u₁的访问数据更有可能作为目标用户u₂的预测访问数据.因此，核心算法只涉及用户历史访问数据，互动关系是用户相似性的基础.根据用户间互动次数分析得出用户之间基于交互行为的影响力相对数值S(u_i, u_j)；再根据用户朋友关系对相关强度进行归一化数值计算，得到相关强度W_ij，进而分析用户与目标用户的相似度，预存储相似度高的用户数据.基于交互关系的随机游走算法如算法2所示.

算法2 基于交互关系的随机游走算法

输入：U_n: The known user set；I: User interactions

输出：Top K

1  for u_i∈U, I_i∈I do

2   UI undirected graph ←I_i.u_i;

3  while true do

4   for u_i∈U do

5    for u_j∈U do

6  w[i][j]←Γ(u_i)∩Γ(u_j)+S(u_i, u_j);

7    for u_i∈U do

8     for u_j∈U do

9      q[i][j]←w_ij, Γ(u_i);

10      calculate q′_ij(t)

11  sim[i][j]←w_ij;

12   calculate $\sum\limits_{a = 1}^b {\prod\limits_{t = 2}^l {q{\prime _{ij}}\left(t \right)} } $;

13  return Top K sim[i][j]

算法2中，第1~2行表示根据云数据库中用户历史访问数据信息得到带权值的社交网络无向图；第3~6行表示若S(u_i, u_j)>0，结果是true时，代表用户与目标用户之间存在互动关系，结合朋友关系Γ(u_i)和Γ(u_j)计算相关强度；第7~11行表示利用随机游走到不同邻居的概率q′_ij(t)计算各个邻居与目标用户的相似度sim(u_i, u_j)，将取得的相似度最高的Top K个用户的访问数据作为目标用户的预访问数据存储到本地缓存器中.

3 手机终端预存储模型 3.1 移动终端预存储模块

云端数据预测模块预测出目标用户可能感兴趣的数据，存入手机端数据预存储模块中.手机内部API搜索数据预存储模块中的关键字算法如算法3所示.

算法3 数据预存储模块中的数据匹配算法

输入：K: Search keyword; Map〈key, word〉: Data set in data pre-storage modular

输出：Relevant data RD with keyword

1  if Map contains Key K then

2   internal API;

3   search RD by local k;

4   if Map. get(K) then

5    RD←GetRD(K);

6  else

7    external API;

8    select data RD from the Server;

9  return RD

当用户再次通过客户端访问相似数据时，执行算法3.第1~5行表示查找数据预存储模块的本地文件，若能匹配到关键字K，则通过getRD将查找到的数据直接返回；第6~8行表示若本地文件中查询不到关键字K，则需要再到云服务器中查找相关信息.

3.2 预存储数据容量与手机耗能关系

为了使本地缓存既能满足预存储又能实现节能的目的，找到手机耗能与预存取数据量大小之间的关系非常重要.

根据基于用户交互行为的最大化模型，可以得到邻居组Q_k中各用户对目标用户u的影响力S(v_n, u)，v_n表示目标用户u的n个邻居朋友. S(v_n, u)越大，代表邻居用户v_n与目标用户之间受到彼此影响越大，目标用户越可能访问邻居用户的历史数据.因此，使用S(v_n, u)衡量预存储数据选择方向就有合理性，满足预存储命中率高的要求.

每个v_n用户在服务器端数据库中的访问数据量不尽相同，用Size_n表示.依据算法3，用户再次访问App，通过关键字Map〈key, word〉从缓存中查询所需要的数据.若用户v_n已被选作目标用户u的预存储数据用户，但其访问数据量Size_n较大，全部预存储数据会有不必要的能耗，因此，需要对TOP K用户的Size_n添加约束，实现节省预存储能耗的目的.这样，将朋友对目标用户的社交影响力S(v_n, u)与其朋友访问数据量大小Size_n相结合，使数据预测模型的实现更具有准确性和合理性.计算公式如下：

$ {\rm{Date}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{Size}}(u) = \sum\limits_{n \in \bar K} \mu \times S({v_n},u) \times {\rm{Siz}}{{\rm{e}}_n} $

(8)

其中：K为根据随机游走算法得到的相似度最高的Top K个用户，μ为对TOP K用户的Size_n约束系数，v_n为相似用户.预存储模块的数据量大小Data Size(u)取决于TOP K中朋友关系的社交影响力和每个Top K用户访问数据量大小的乘积.

4 实验分析

实验数据集选用腾讯微博中的部分数据，包括朋友关系、互动关系及用户访问数据.本实验使用的测量耗能的工具是PowerTutor软件. Android实验机型号是Letv X500，系统版本为6.0.

依据数据集，从输入目标用户开始，只考虑用户之间的好友关系，采用宽度优先策略收集用户好友关系.通过用户表中relation字段首先模拟一个小型的社交网络；随后根据好友列表分别从用户互动行为和用户访问信息中提取出节点用户interaction和data字段数据，获得相关用户的社交行为.根据拓扑结构获得用户间媒介点数量，结合互动行为的最大化影响，利用媒介和交互影响力计算相似度，获得相似度最高的TOP K个用户.

4.1 TOP K数据分析

如何确定K的值是解决预存取数据量大小与手机耗能之间关系的关键. Top K推荐中评价指标如下：

$ {\rm{准确率 = }}\frac{{K{\rm{中已经是好友的用户数}}}}{K} $

(9)

$ {\rm{召回率 = }}\frac{{K{\rm{中已经是好友的用户数量}}}}{{{\rm{目标用户的好友数量}}}} $

(10)

所提出的LP-MUIB方法通过改变K值可得出TOP K与准确率和手机耗能关系曲线，如图 4所示.

4.2 预存储模块容量的数据分析

确定TOP K的值还不能确定预存储数据容量和手机耗能之间的关系，需要确定预存储值的大小与移动端耗电关系.根据式(8)所示的预存储数据容量与手机耗能之间的数量关系，在本实验中，目标用户所有朋友的访问数据容量设为10 MB，获得的缓存数据量如图 5所示.由图 4和图 5得出，K取5，缓存的数据量为60，为本实验中的最佳值.

4.3 对比实验 4.3.1 比较方法

1) LP-MUIB.基于以上设定的预存储模块的容量开展实验对比.一组直接从服务器获取数据，另一组增加手机数据预存储模型，模拟正常网络和不稳定2种环境，其中第4次为通信不稳定环境.

2) 手机节能策略^[7](SP-EES, smartphone energy-efficiency strategy).该方法基于混合变量属性k- means算法对已知用户进行聚类分组，建立相似用户群，利用模型对用户连续搜索进行预测.

3) 应用层传输协议^[8](APPATP, application-layer transmission protocol).该方法受到预取友好和延迟容忍应用普及的推动，Liu等^[8]设计并实现了APPATP.该协议利用云计算管理移动应用数据的传输，以节能的方式，与移动设备进行数据的互传.

4.3.2 实验评估

将LP-MUIB与SP-EES方法进行比较，如图 6所示.该实验为手机耗能与访问次数的关系，其中横轴为访问的次数，纵轴为耗电量.由图 6可以看出，所提出的LP-MUIB方法可进一步节约能耗，能耗降低了15%~25%.

将LP-MUIB与APPATP方法进行了比较，如图 7所示，其中横轴为手机预存储量，纵轴为耗电比，w/o-APPATP为APPATP的基准实验.由图 7可以看出，所提出的LP-MUIB方法较APPATP在节能方面有一定的提高.

5 结束语

针对预存储数据选择方面，提出LP-MUIB方法，在原有数据预存储节能模型基础上增加社交网络与互动关系，用以提高用户下次访问的命中率.为了不涉及用户背景等隐私信息，提出一种基于用户交互行为的影响最大化方法，利用基于互动关系改进的交互度方法对已知用户访问数据预测，并在该方法的基础上提出一种基于互动关系随机游走的算法，对预测数据进行筛选，为用户返回尽可能准确的预测结果.最后通过实验验证该方法在节能方面有一定效果.下一步工作将研究重点放在预存储模块缓存期存活时间设置上，如何计算相应的阈值，实现数据更新，进一步提高预测的准确率.