移动云计算环境下基于任务依赖的计算迁移研究

郑利阳 刘茜萍

(南京邮电大学计算机学院江苏省大数据安全与智能处理重点实验室 江苏 南京 210023)

0 引 言

近几年来，移动智能终端技术取得了巨大的进步，可提供满足用户各种需求的移动应用。然而，由于其尺寸的限制，移动终端总是存在诸如计算能力弱、存储空间小和电量不足等问题。资源受限的问题同时也限制了移动终端和移动应用的进一步发展，因此，如何扩展移动终端的资源，成为需要迫切解决的问题[1]。

为了解决移动终端资源受限的问题，移动云计算技术应运而生，通过计算迁移，用户可以将应用迁移至远程云端或微云来进行处理，以此弥补移动终端的资源缺陷，提高应用的服务质量[2-3]。其中，与远程云端相比，微云具有与终端距离更近、传输延迟更小的优势。对于实时性要求很高而计算要求相对不高的应用而言，它们就非常适合迁移至微云处理。这类应用往往可再细分为若干相互存在时序和数据依赖关系的任务。针对这一类复杂应用，在迁移过程中，如何根据各任务之间的依赖关系，有效地结合不同微云的优势，为移动应用中的计算任务确定合理有效的迁移方案，降低移动设备上能量消耗和响应时间，是一个值得挑战的问题。

针对移动云环境下具有依赖关系的多任务计算迁移问题，本文在考虑任务类型细分的基础上对不同微云的计算能力进行了细化表达，并在此基础上给出了迁移方案的效用函数计算方法，进而基于时序和数据依赖约束提出了一个改进的遗传算法，以尽可能减少任务间的数据传输，提高任务的并行度，从而得到响应时间和终端能量消耗总体较优的迁移方案。

1 相关工作

目前，针对移动云计算中计算迁移问题的研究有很多，文献[4]中将移动应用分为通信密集型和计算密集型，通信密集型应用适合于终端处理，计算密集型应用适合于远程云端处理，而介于两者之间的应用则需要根据局域网中的带宽条件来确定处理位置。文献[5]在博弈论的基础上提出了一种算法，该算法对于移动终端和远程云端的最优能耗问题，可获得纳什均衡解。文献[6]同样是在博弈论的基础上提出了一种分布式的计算迁移方法，该方法可以根据技术任务的规模来有效地进行任务迁移。文献[7]提出了一种自动贪婪迁移算法，可以更好地解决任务迁移过程中的能效问题。文献[8]提出了一种禁忌搜索算法，可以为应用任务的迁移获得更好的解决方案。文献[9-10]根据逆推动态规划的解法提出了一种迁移算法，该算法对于一组串行任务，可在满足响应时间的前提下，将移动终端的能耗最小化。文献[11]提出了一组并行任务的联合迁移算法，可以更快地获得终端能耗的最优解。文献[12]提出了一个面向云数据中心的主动服务迁移框架，该框架采用轻量级程序来部署运行时分布式平台，采用粗粒度级和简单的开发部署过程，实现移动云环境下的计算迁移。文献[13]考虑了由远程云端、微云和移动终端组成的三层移动云计算架构，根据局域网的条件提出了一种迁移算法，该算法可以在满足响应时间的同时降低移动终端的能量消耗。文献[14]将计算迁移模式分为三种：远程云端服务模式、连接式点对点(Ad Hoc)微云服务模式和机会式Ad Hoc微云服务模式，然后对提出的三种计算迁移模式在Ad Hoc微云上进行了详细的分析研究。文献[15]使用了移动云环境下的三层架构，定义了一个模型来研究计算迁移对用户感知性能的影响，把这个问题表述为一个广义纳什平衡问题，针对此问题提出了一种分布式均衡计算算法。

若从计算任务的处理位置来讲，这些研究可大致分为两类：第1类只考虑移动终端和远程云端两个处理位置[4-12]，第2类则考虑移动终端、微云和远程云端三个处理位置[13-15]。远程云端存储资源丰富，处理计算任务的速度也非常快，其任务处理时间相对移动终端而言几乎可以忽略不计。然而，远程云端往往距离用户较远，传输延迟较大，很多具有较高实时性要求的计算任务，并不适合迁移到远程云端进行处理。与之相反，微云尽管存储资源有限，处理计算任务的速度也相对远端而言有所欠缺，但是它们距离用户往往较近，传输延迟能得以大幅减少。

对很多实时性要求很高而计算要求相对不高的复杂应用而言，比如某些在线网络游戏、图片处理等应用，就更适合迁移到微云平台而非远程云端上去处理。然而，目前仅考虑本地和微云的迁移研究较少，对不同微云的描述也不够细致，难以为不同类型任务计算迁移提供丰富的候选参数。

此外，当前研究大多为多个独立任务的迁移研究，而实际的复杂应用可以划分为多个相互之间存在依赖关系的任务，任务之间不仅仅只有时序依赖，还存在有数据依赖。一个任务可能会接收另外任务的处理结果作为输入数据进行进一步处理。此时，需基于数据依赖将各任务迁移至符合其特性的微云执行，而大多现有文献中的计算迁移策略很难适用于这种场景。

2 系统模型及问题描述

在本文中，计算任务的处理位置只考虑终端本地和微云端，并且计算任务之间存在着时序和数据双重依赖关系。在这种场景下，如何迁移处理计算任务，以期得到较优的响应时间和终端能耗，即较低的效用值，是我们将要解决的主要问题。

2.1 计算任务模型

计算任务代表着在移动应用中，能实现某种特定目的的一个模块或一段程序。一个移动应用在一个时间段内，可能会产生一组计算任务，并且任务与任务之间存在着时序或数据依赖。用一个带权有向无环图G(V,ξ)来表示产生的一组计算任务，其中：V={v1,v2,v3,…,vn}表示这一组计算任务的集合，n表示这一组计算任务的数量。ξ={h(vi,vj)|vi,vj∈V}表示计算任务之间的依赖关系集合，当h(vi,vj)=0时，表示任务vi和任务vj之间没有依赖关系；当h(vi,vj)=1时，表示任务vi和任务vj之间只有时序依赖；当h(vi,vj)=2时，表示任务vi和任务vj之间存在时序和数据双重依赖。

在本文中，用一个四元组vi=(di,wi,ri,tyi)来表示计算任务，其中:di(单位为MB)表示vi任务本身的数据量，wi(单位为MB)表示处理该任务时所需要的计算量，ri(单位为MB)表示任务vi的处理结果的数据量，tyi表示计算任务的类型。计算任务可以根据其实现目的分为不同的类型，例如视频、图片、游戏等。在本文中，假设有四种不同的任务类型，用TY={A、B、C、D}来表示，tyi∈TY。由于指令集不同等原因，我们认为本地或微云对于不同类型的计算任务，其处理能力也是不同的。

2.2 计算资源模型

根据上述场景描述，本文假设移动云计算环境下的计算资源主要由移动终端的本地资源和微云资源两部分组成，它们两者之间可以通过局域网进行通信。由于普通云端往往距离较远，因此会造成延迟过大，所以暂不考虑。

微云资源可通过fkty表示，其中k表示微云的编号，k=1,2,…,m。fkty(单位为GHz)表示微云的不同计算能力，ty∈TY。此外，移动终端和微云之间一般通过局域网进行通信，该局域网带宽可统一通过Bc(单位为MB/ms)表示。

2.3 问题描述

在移动云计算环境下，由移动终端产生的计算任务，可以有在本地处理和迁移到微云端处理两种选择。本文用一个一维向量S=(s1,s2,…,sn)来表示迁移方案，其中si∈{0,1,…,k,…,m}，m表示微云的个数。当si=0的时候，表示任务vi在本地进行处理，此时，其响应时间为：

(1)

移动终端的能量消耗为：

e(i,0)=t(i,0)×Plocal

(2)

当si=1,2，…,k,…,m时，表示任务vi将要被迁移到微云中进行处理，此时其响应时间为：

ri/Bc+2×LLAN+Lwait

(3)

移动终端的能量消耗为：

Psend+(ri/Bc)×Prec

(4)

针对一组具有时序和数据依赖的任务，本文的迁移方案主要综合了响应时间和移动终端能耗这两方面的考虑，以期能够在节约能耗的同时获得较好的应用性能。

在本文中，采用效用函数来表示最终的优化结果，其公式如下：

(5)

α+β=1 0≤α≤1，0≤β≤1

(6)

因为最终目标是响应时间最小并且终端能耗最低，所以效用值U越小即代表迁移方案越接近最优，而此时所对应的迁移方案S即为最终迁移方案。

3 基于任务依赖的计算迁移方法

根据以上描述，结合遗传算法，本文提出了一个基于任务依赖的多任务迁移方法，以期获得响应时间和终端能耗总体较优的迁移方案。遗传算法是一种参照生物进化规律而设计的随机搜索方法，被广泛用于解决此类求全局最优解的问题[16]。遗传算法模拟生物的遗传规律，从初始个体出发，通过选择、交叉和变异操作来产生新的个体，如此不断进化下去，直到满足停止条件。

首先我们需要基于应用中的任务数量设置与种群大小、染色体(chromosome)长度等相对应的参数值,然后根据参数值生成初代种群，种群中的每个染色体对应于迁移方案，染色体中的每个基因对应于任务所在的处理位置。之后可根据式(5)得出种群中每个个体的适应性值，即效用函数U。然后，根据个体适应性值进行选择操作，适应性较优的个体根据计算任务之间的双重依赖关系进行交叉、变异操作，操作之后产生的新个体遗传到下一代种群。如此不停地迭代，直到满足停止条件，产生结果。

3.1 种群初始化

种群初始化操作就是初始化计算任务的处理位置，对于一个任务vi的处理位置，随机产生si={0,1，…,m}的随机整数。在进行初始化时，暂不考虑任务依赖对迁移的影响。用相同的方法遍历所有的计算任务，可以获得作为染色体的初始位置集合S0，并且染色体的长度即基因数量由所有计算任务的数量确定。由于种群由多个染色体组成，因此在本文中，种群由矩阵pop表示。

3.2 适应性值的计算

在遗传算法中，每个染色体代表一个解，满足最优适应性值的个体即为最优解。为了在选择过程中衡量每一个个体的优异程度，需要设计一个能直接反映个体性能的适应度函数，在本文中，效用函数U即为适应度函数，由该函数计算得到的效用值即为适应性值。

在计算个体的效用值之前，要将每个计算任务的具体描述以及任务之间的依赖关系输入进来。为了得到个体的效用值，首先我们要遍历该个体的每一个基因值，根据其基因值所代表的任务处理位置，使用式(1)或式(3)可得出每个计算任务的响应时间。其中，若多个并行的任务迁移到同一个微云进行处理，则会出现等待现象，此时需要将处理时间较少的任务优先处理，以降低等待时间。然后根据式(2)或式(4)可得出处理每个计算任务的终端能耗。

求这一组任务全部处理完时的响应时间总和与终端能耗总和，此时需要结合两个计算任务之间的依赖关系以及是否可以联合迁移，将两个任务之间进行数据传输部分的响应时间和终端能耗去掉。最后根据式(5)得出该个体的效用值。种群中的其他个体效用值可用同样的方式计算得出。

3.3 选择操作

选择操作是选择效用值较优的部分染色体，并将其进行交叉、变异操作产生适应性更佳的下一代染色体。本文采用轮盘赌法来进行选择操作。首先，用下式计算第j个个体被选择的概率，Uj表示第j个个体的效用值：

(7)

然后，计算个体k的累积概率以构造轮盘：

(8)

最后进行轮盘选择，在[0,1]区间内产生一个随机数ms，若ms满足如下条件：qk-1

算法1选择操作算法

输入：父代种群及每个个体的适应值

输出：进行选择操作之后的子代种群

BEGIN

1. 根据式(7)计算第j个个体被选择的概率spj；

2. 根据式(8)计算个体k的累积概率qk，并将其放入矩阵中，以构造轮盘；

3. fork=1到popsize

4. 在[0,1]区间产生一个随机数ms；

5. ifms<=qk且ms>qk-1

6. 选择个体k进入子代种群；

7. end

8. end

END

3.4 交叉操作

例如，选择两个即将进行交叉操作的父代个体Sp和Sq，并选取交叉点：

Sp=(s1,s2,s3,s4,s5,s6,|s7,s8,s9,s10)

算法2交叉操作算法

输入：进行选择操作之后的种群

输出：进行交叉操作之后的子代种群

BEGIN

1. fori=1到popsize-1，每次循环i=i+2

2. 在[0,1]区间产生一个随机数mr；

3. ifmr<交叉概率pc

4.cpoint=find1()；

5. ifcpoint==false

6. 跳出该次循环；

7. else

8. 将cpoint之后的基因进行交叉；

9. end

10. end

11.find1()：

12. 定义寻找次数flag，并初始化为0；

13. do(在[0,1]区间产生随机数mr1；

14.cpoint1=mr1*基因个数；

15. 将cpoint1进行四舍五入得到cpoint；

16.flag=flag+1；)

17. while((h(vi,vcpoint)==2 &&si==scpoint)

18. &&flag<=10)

19. ifflag==11

20. return false；

21. else

22. returncpoint；

END

3.5 变异操作

采用上述变异操作所获得的新个体具有较好的适应性，也可以有效提高算法的收敛速度。

算法3变异操作算法

输入：进行交叉操作之后的种群

输出：进行变异操作之后的子代种群

BEGIN

1. fori=1到popsize

2. 在[0,1]区间产生一个随机数mt；

3. ifmr<变异概率pm

4.mpoint=find2()；

5. ifmpoint==false

6. 跳出该次循环；

7. else

8. 进行基因变异：

9.smpoint=si或smpoint=sj；

10. end

11. end

12.find2()：

13. 定义寻找次数flag，并初始化为0；

14. do(在[0,1]区间产生随机数mt1；

15.mpoint1=mt1*基因个数；

16. 将mpoint1进行四舍五入得到mpoint；

17.flag=flag+1；)

18. while((h(vi,vmpoint)==2 &&si==smpoint)

19. ‖(h(vmpoint,vj)==2 &&smpoint==sj)

20. &&flag<=10)

21. ifflag==11

22. return false；

23. else

24. returnmpoint；

END

3.6 得出结果

对于迭代的停止条件，一般有两种方式：第一种是设置一个期望结果的界限，当结果达到这个界限时，迭代停止；第二种就是设置迭代次数限制，当迭代次数达到限制次数时，迭代停止。

在本文中我们使用第二种迭代停止方式，我们设置一个最大迭代次数，当迭代次数达到设定的值之后就会停止，然后将适应性U最优的个体输出，得到迁移方案S即为最终的迁移方案。

4 仿真实验和分析

在这一节中，将会对本文提出的假设及其实现算法进行仿真实验验证。为了验证方法的有效性，我们求取了另外三种迁移方案与本方法所求迁移方案进行对比，分别是将计算任务全部放在终端进行处理的无迁移方案、将计算任务在微云和终端随机分配处理的迁移方案和将计算任务在微云平均分配处理的迁移方案。

将前文提到的效用值U作为性能指标，最后将实验结果进行分析总结。

4.1 实验设置

实验在配置为3.4 GHz Intel(R) Core(TM) i3-4130 CPU和8 GB RAM的机器上运行，操作系统为Windows 10，采用MATLAB 2016版软件进行编程仿真。本文主要考虑在商场等固定公众场所下的微云场景，人们在休闲等待时往往会有实时游戏等娱乐需求，其周围的微云数量可设置为4。在实验进行之前，首先要设置实验的参数，如移动设备的性能、微云的性能以及在实验进行中需要用到的参数等，各具体参数参照本文的部分参考文献，并归纳分析，设置如表1-表3所示。

表1 移动设备性能参数

表2 微云性能参数 GHz

表3 其他参数

4.2 实验过程

在设置好实验参数之后，我们随机生成一组计算任务，然后随机生成各个计算任务之间的依赖关系，用一个二维矩阵表示：0表示两个计算任务之间没有依赖关系，1表示两个计算任务之间只有时序依赖，2表示两个计算任务之间存在时序和数据双重依赖关系。

生成一组计算任务之后，就可以根据前文提出的算法将该组计算任务进行迁移处理，然后得到实验结果，即效用值U和迁移方案S。

当计算任务的数量是20时，随机生成的一组计算任务和任务之间的依赖关系分别如表4和表5所示。

表4 计算任务的属性

表5 任务之间的依赖关系h(vi,vj)

4.3 实验结果及分析

当α=1、β=0时，本文迁移方案的效用值U随迭代次数的变化情况如图1所示。最后得到的最小效用值为0.338 5，而平均分配方案和随机分配方案的效用值分别为0.412 3和0.442 3。最终的迁移方案S={3,3,4,2,2,3,1,3,3,3,3,3,3,3,3,2,3,4,1,0}。

图1 效用值随迭代次数的变化

当α=0、β=1时，本文迁移方案的效用值U随迭代次数的变化情况如图2所示。最后得到的最小效用值为0.507 8，而平均分配方案和随机分配方案的效用值分别为0.724 6和0.673 8。最终的迁移方案S={0,0,2,2,2,3,0,0,4,3,2,0,0,0,2,2,1,0,2,2}。

图2 效用值随迭代次数的变化

当α=0.5、β=0.5时，本文迁移方案的效用值U随迭代次数的变化情况如图3所示。最后得到的最小效用值为0.495 4，而平均分配方案和随机分配方案的效用值分别为0.568 5和0.554 6。最终的迁移方案S={3,0,4,0,3,2,3,1,3,3,4,4,3,4,3,3,4,1,4,4}。

图3 效用值随迭代次数的变化

由图1-图3可以看出，随着迭代次数的增多，效用值U是可以逐渐降低并最后得到一个最小值的，这说明本文的迁移方法是有效的。

为了验证实验效果，在本文中，计算任务的数量分别设置为10、20、30、40和50。通过记录多组的效用值U，最后生成比较图。由于在计算效用值U时，选取了计算任务全部在终端进行处理的无迁移方案作为分母，因此将计算任务全部放在终端进行处理的无迁移方案的效用值等于1，并未在比较图中画出。

在图4中，α=1、β=0，此时的效用值U仅表示响应时间。

图4 效用值随计算任务数量的变化

在图5中，α=0、β=1，此时效用值U仅表示终端的能量消耗。

图5 效用值随计算任务数量的变化

在图6中，α=0.5、β=0.5，此时响应时间和终端能量消耗对于效用值U的影响是相同的。

图6 效用值随计算任务数量的变化

综合图4-图6可以看出，本文的迁移方法均可以得到相对最小的效用值，这说明对于具有数据、时序依赖关系的一组任务而言，本文所提出的迁移方法确实可以得到更优化的解，迁移方案S即为最终迁移方案。

5 结 语

本文针对移动云环境下计算任务迁移的响应时间和终端设备能耗综合优化问题进行了研究。针对延迟比较敏感且计算要求相对不高的多个相互依赖的任务，提出了一种基于遗传算法思想的迁移方法。该方法根据计算任务的不同类型和不同微云的分类处理能力描述来计算迁移方案的效用值并完成选择操作，基于各个任务之间的依赖关系来完成交叉和变异操作，从而通过多次迭代最终生成综合效用值较优的任务迁移方案。仿真实验结果表明，本文方法能有效减少移动终端的响应时间和能耗。

本文的研究仍然存在不足和值得进一步研究的问题，例如，如果移动用户处于移动状态，而且所应用到的无线网络也是会发生变化的。将用户的移动性和网络的时变性加入到迁移模型中，更加贴合现实生活，再在此基础上研究迁移方法，是未来的工作之一。