移动云计算环境下任务调度的多目标优化方法

胡海洋 刘润华 胡 华

(杭州电子科技大学计算机学院 杭州 310018) (复杂系统建模与仿真教育部重点实验室(杭州电子科技大学) 杭州 310018)

移动云计算环境下任务调度的多目标优化方法

胡海洋 刘润华 胡 华

(杭州电子科技大学计算机学院 杭州 310018) (复杂系统建模与仿真教育部重点实验室(杭州电子科技大学) 杭州 310018)

(huhaiyang@hdu.edu.cn)

移动云计算技术可帮助移动用户在执行工作流任务时将一些任务迁移至云端服务器执行，从而节省移动设备的电池能耗，并提高计算能力.传统研究工作在进行移动云计算环境中的任务调度时缺乏对能耗和运行时间的联合优化.为了实现有效的任务调度，基于工作流图中任务执行的先后关系，分析了采用动态电压频率调节技术的移动设备处理器执行工作流任务的运行时间与能耗，并考虑了将任务通过无线信道迁移到云端服务器执行所需的时间，给出了能耗与执行时间联合优化的任务调度模型和目标方程.提出基于模拟退火算法的任务调度方法，分析了算法时间复杂度，进行了系统性的对比实验，评估了所提出方法的正确性和有效性.

移动云计算；工作流;任务调度；模拟退火；多目标优化

无线移动计算技术的普及为跨地域的企业内部工作流管理与移动办公提供了方便：借助于便携式移动计算设备，跨地域的各类工作人员可随时进行灵活的无线移动办公与协作支持，那些常需要出勤在外的企业管理与工作人员也能通过各类移动计算设备及时进入企业的工作流管理系统中审查日志、调配资源、交流协作和完成任务.

尽管智能手机和无线通信技术能力在日益进步，由于受电池容量、存储与计算能力等方面的约束，与传统服务器及桌面设备相比，移动计算设备的硬件能力仍显得非常有限[1].当执行数据密集型(data-intensive)或资源密集型(resource-intensive)的计算任务时，很难保证相应的服务质量.近年来移动云计算技术(mobile cloud computing)的出现[2-4]为克服上述困难提供了一个良好的解决方案：它提供了基于云端资源共享和增强移动计算两者相统一的平台[5-7]，可允许计算任务、数据存储和海量信息处理被卸载(offloaded)到云端服务器执行以提高服务的可靠性和可用性，并减少移动设备端能量与计算资源的消耗.目前许多移动应用已经采用移动云计算技术来提供增强的移动服务[8-9].

然而，现有面向移动云计算环境的任务调度方法主要针对如何优化任务完成的总时间[10-13]或者如何优化移动客户端的能量消耗[14-17]，很少有研究工作综合考虑这2方面的联合优化.本文针对这一多目标优化问题展开研究，给出调度模型与目标优化方程，并设计基于模拟退火方法的优化算法，来对工作流任务完成的总时间和移动客户端能量消耗这2方面进行综合优化.

1 相关工作

工作流任务调度问题已得到了广泛的研究，各种启发式算法被相继提出[10-17].这些工作可分为2类：1)优化应用程序的总完成时间[10-13]；2)优化整体的能源消耗[14-17].

在缩短工作流应用的总完成时间方面，文献[10]主要通过任务优先级对异构处理器环境中的应用程序实现高速的任务调度.文献[11]首先通过快速确定算法进行初始化，然后通过迭代方法不断地改进目前的解决方案.文献[12]采用增量贪心策略并开发了一个运行系统，它能自适应地为移动交互感知应用程序进行任务卸载和并行执行，从而减少应用程序的完成时间.文献[13]提出了一种方法，可在移动设备和云环境中的最大吞吐量之间，对数据流应用的任务分配问题进行优化.

在减少总体的能量消耗方面，文献[14]提出了在执行周期性任务的计算机系统中降低能耗并使能耗达到最少的问题，在该方法中，研究者们假设任务的周期是足够大的，任务之间的空隙时间是可以用来降低能耗的.文献[15]将工作流任务调度问题视为一个最大流最小割的问题来处理，通过优化在移动设备和云计算环境中执行的每个模块任务从而使能量消耗最小化.文献[16]在文献[10]的基础上进行了扩展，对异构处理器环境中的能源消费问题和任务完成时间都进行了阐述，但文献[16]中所给的任务调度算法不能保证调度结果一定都能满足用户所给的时间约束条件.文献[17]中提出了一种根据网络通信环境来进行简单直接的卸载策略以减少能源的消耗.

文献[18]在文献[16]基础上，考虑了如何满足时间约束条件下来进行任务调度，并通过动态电压频率调节(dynamic voltage and frequency scaling，DVFS)来减少任务之间的空隙时间从而降低能源消耗，但是该算法中使用到的动态电压频率调节技术是离散的，这对能耗减少的效果并不是特别明显，同时该算法对如何优化工作流任务的总完成时间也没有给出相应的算法，仅仅满足用户所给的时间约束条件.

综上所述，在任务分配时，大多数的任务分配算法仅考虑在最大截止时间条件下减少能耗，没有将完成时间也作为优化的一个目标.然而，为了减少能耗，会使得用户较多地去选择低功率的处理器或者通过技术手段动态降低处理器的运行功率，这样使得工作流任务的总完成时间相应增加.为了解决这样的多目标优化问题，本文提出一种基于模拟退火算法的时间和能耗联合优化的工作流任务调度算法，该算法通过连续动态电压调节技术能在满足完成时间约束条件情况下使工作流应用的完成时间和能量消耗都得到优化，从而减少移动设备的能量消耗并提高工作流应用的执行速度.

2 移动云计算任务调度模型

2.1 问题描述和基本框架

Fig. 1 Application of picture recognition图1 图片识别应用程序

由于移动云计算技术可以帮助移动用户将一些工作流计算任务迁移至云端服务器执行，从而节省移动设备的能耗，并提高计算效率.目前研究者已经开始探讨如何将移动云计算技术应用到日常工作环境中，例如物体手势识别、图像视频编辑、自然语言处理等领域[2,17-18].本文现通过一个具体实例来阐释相关问题.某大型企业为了提高管理效率、降低运营成本，建立了一个移动工作流管理系统，企业员工可利用移动终端设备进入系统中就可以随时随地地办公.在工作过程中，由于企业的一些数据处理工作较为复杂，此外一些复杂任务的计算量也较大，员工所携带的移动设备硬件能力与电池能耗已经不能满足移动办公的需要.为解决该问题，企业可搭建一个基于移动云计算环境的移动办公系统.下面我们通过一个能耗和任务执行时间都比较大的图片识别应用来进行说明，如图1所示.该应用包括图片数字化、色彩提取、形状提取、边缘提取、纹理提取、空间提取等一些处理步骤.对于图片采集和数字化工作可由移动设备自身完成；而对于色彩提取、形状提取、纹理提取等工作，由于计算量较大，则需要上传到公司的云端服务器去完成.对于这个工作流应用，我们可以用一个有向无环工作流图(如图2所示)G=(V,E)来表示，其中每个节点vi∈V表示一个任务，有向边e(vi,vj)∈E表示2任务之间的先后关系，即只有等vi完成之后vj才可以开始执行.

Fig. 2 Directed acyclic graph of the workflow图2 工作流的有向无环图

一个工作流由N个任务节点组成，一般情况下，N不会超过100，比如在计算机视觉应用程序中，N的范围就是10～30.在给定的工作流任务图中，没有任何前驱节点的任务节点为开始任务，没有任何后续节点的任务节点为结束任务.如图2所示，任务v1是开始任务，任务v10是结束任务；此外，其他一些工作流任务可以有前驱任务和后续任务(例如，对于任务v5来说，v1是它的前驱，v9是它的后续).基于文献[18]，我们给出图2中各个任务在移动设备处理器以及在云端服务器的处理时间如表1所示:

Table 1 Completed Time of Each Task

表1表示10个任务分别在3个处理器上的完成时间(表示为Tcore1,Tcore2,Tcore3)以及任务被迁移到云端服务器处理所需的发送时间ts(vi)、执行时间tc(vi)和接收时间tr(vi)，由于在云端可以高效地进行任务处理，任务在云端的处理时间统一为3 s，发送任务到云端和从云端接收运行结果的时间都统一为1 s.

为了便于理解，我们总结了本文的主要符号及其含义如表2所示:

Table 2 Definitions of Notations

2.2 任务执行时间

设移动设备含有M个异构处理器，每个处理器都可进行动态电压频率调节[18]，即在不同频率下对应有不同的电压.若用fmax(k)表示任务在第k个处理器上执行时的最大电压频率，则任务vi运行时的实际电压f(vi,k)可由电压变化率rat(vi)控制，即f(vi,k)=fmax(k)×rat(vi)，并且rat(vi)∈[ratmin(vi),1]，这里ratmin(vi)由式(1)确定：

(1)

其中,TL表示任务vi给定的截止时间，TM表示平均每个任务的理论最小完成时间：

(2)

其中，tc(vi)表示在云端服务器上运行任务vi所需的执行时间，包括将vi通过无线网络发送到云端服务器上所需时间、任务vi在云端服务器执行所需时间以及将执行处理后的任务结果通过无线网络返回到移动设备上所需时间这3部分；tmk(vi,k)为移动设备的第k个处理器上运行任务vi所需的执行时间，若采用DVFS调节，则任务vi在第k个处理器上的实际运行时间为tmk(vi,k)rat(vi).综合考虑这2方面情况，则任务vi的实际执行所需时间为

(3)

2.3 能源消耗

在任务调度优化过程中，一方面需要缩短工作流任务的总完成时间，另一方面也需要考虑工作流任务执行过程中移动设备的能源消耗.

设emk(vi,k)为无DVFS调节时任务vi在第k个处理器上执行的能耗；若vi执行时，处理器上的电压变化率为rat(vi)，则vi执行时的实际能源消耗为

(4)

则整个工作流G=(V,E)执行时移动设备所需的总能源消耗可以表示为

(5)

3 算法设计

本文提出一种基于模拟退火算法的任务调度策略SA-DVSA算法，来解决工作流任务调度的能耗与执行时间优化问题，算法分为3个步骤：初始化可行解、改变参数可行解和新变量取舍的判断.我们将会分析加入了连续动态电压调节技术后对结果的影响，并在实验部分对SA-DVSA算法与其他相关工作进行比较.

3.1 算法框架

基于物理中固体物质的退火过程与一般优化问题之间具有一定的相似性，模拟退火算法[19-20]已被证明是一种适合求解大规模组合优化问题的通用且有效的近似算法.对于组合优化问题来说,解空间的每一点都代表一个具有不同目标函数值的解，而优化过程就是在解空间寻找函数最小解的过程.若把函数看成能量函数，把控制参数视为温度，解空间作为状态空间，那么模拟退火算法寻找基态的过程就可被是为求解目标函数极小值的优化过程，算法流程图[19]如图3所示.

Fig. 3 Framework of the simulated annealing algorithm图3 模拟退火算法框架图

将任务的处理位置、执行顺序、处理器电压变化率作为变量，而工作流任务执行的总完成时间与移动设备的能源消耗这2方面的加权值作为适应度目标函数，则可将本文中的移动云计算环境中工作流任务调度优化问题转化成组合优化问题.对于这类组合优化问题，我们可以根据适应度函数，通过模拟退火算法迭代得到变量的最优值.下面给出变量的定义：1)LOC={loc(vi)}表示各工作流任务执行位置的集合，其中loc(vi)=k(1≤k≤M+1)表示任务vi被执行的位置：即若k

设任务vi的开始执行时刻为startT(vi),则由式(3)可得其实际完成时间为

(6)

vi的开始执行时刻startT(vi)由2方面因素决定：1)其前驱任务节点的最迟完成时刻； 2)其所在移动设备处理器或云端服务器上排序在前的那些任务的最迟完成时刻.这样，startT(vi)可递归地用AFT(vj)(vj≠vi)表示为

(7)

这样整个工作流的总完成时间可以表示为

(8)

则根据式(5)和式(8),执行时间与能耗的联合优化目标函数可表示为

(9)

3.2 初始化可行解

在本文的算法中，初始化解是随机生成的.INIT_VAR算法先随机产生工作流任务被处理的位置集LOC={loc(vi),loc(v2),…,loc(vN)}，然后根据式(1)和式(2)计算每个任务的最小电压变化率,再在此基础上随机产生任务的电压变化率集RATIO={rat(vi)}，接着初始化N个任务的顺序为ORDER={ord(vi)|ord(vi)=i,1≤i≤N},最后计算总能耗ETotal、运行时间TTotal以及目标函数值F.下面给出INIT_VAR算法的执行过程：

算法1. INIT_VAR算法.

输入：任务数N、移动设备的处理器数M、任务在云端服务器运行时间集TC={tc(vi)}、任务迁移到云端服务器运行时移动设备能耗集EC={ec(vi)}、任务在移动设备的运行时间集TMK={tmk(vi,k)};任务在移动设备运行的能耗集EMK={emk(vi,k)}、截止时间TL;

输出：任务处理初始位置集LOC、初始电压变化率集RATIO、初始任务执行顺序集ORDER.

随机生成处理位置集LOC{loc(vi)},其中loc(vi)=random(1,M+1);

FOR eachvi∈VDO

根据式(1)、式(2)计算ratmin(vi)；

IF(loc(vi)≠M+1)

rat(vi)random(ratmin(vi)，1);

ELSE

rat(vi)1.0;

ENDIF

将rat(vi)加入集合RATIO中;

ENDFOR

生成初始任务执行顺序集ORDER{ord(vi)},其中ord(vi)=i;

根据式(5)、式(8)和式(9)计算目标函数值F.

3.3 改变参数可行解算法

CHANGE_VAR算法将随机改变任务vi执行所在的位置及电压.在改变执行位置的过程中，随机选择某处理器或云端服务器位置k,得到k处的任务vi可被执行的次序区间R1.R1可通过如下过程计算得到：找出vi在k处的全部前驱任务中的最大执行次序值x1，找到vi在k处的全部后续任务中的最小执行次序值x2，则R1区间为(x1，x2).在区间R1上随机选择vi的某个执行次列位s1；然后遍历R1中所有其他执行次列上的当前任务，对每个任务vj，分析其在k处上的可执行的次序区间R2，分析R2与R1的交集Rcross，若Rcross≠∅，则表示vi与vj可互选，则将vj的执行次序位加入集合RA中，最终从可互换的执行序列集RA中随机选择一个序列位s2，交换s1和s2上的执行任务,从而得到新的可行解LOC′,RATIO′,ORDER′和目标函数值F′.下面给出CHANGE_VAR算法的执行过程：

算法2. CHANGE_VAR算法.

输入：任务处理位置集LOC、电压变化率集RATIO、任务执行顺序集ORDER;

输出：更新后的任务处理位置集LOC′、电压变化率RATIO′、新任务顺序ORDER′.

LOC′LOC;RATIO′RATIO;ORDER′ORDER;

从任务集V中随机选取任务vi;

随机选取任务新的处理位置k，loc(vi)k;

IF(k≠M+1)

rat(vi)random(ratmin(vi)，1);

ELSE

rat(vi)1.0;

ENDIF

计算vi处理位置k上的可执行次序区间R1；

在R1中随机选择可执行序列位s1,ord(vi)s1;

FOR eachs2∈R1DO

IF(s2≠s1)

获取s2上所对应的执行任务vj；

计算vj在处理位置k上的可执行次序区间R2；

令RcrossR1∩R2;

ENDIF

IF(Rcross≠∅)

RARA∪{s2};

ENDIF

ENDFOR

IF(RA≠∅)

从RA中随机选取序列位s2,获取s2上所对应的执行任务vj;

交换ORDER中vi与vj的执行序列;

ENDIF

3.4 变量值取舍算法

通过改变参数可行解算法得到了新可行解，新可行解是否被接受为当前最优解需要进一步计算确定.在ACC_NEW_VAR算法中，设新可行解所对应的目标函数值为F′，若F′rand()：若成立，则采用新的可行解F′，否则保留当前解F，这里tempk表示当前迭代第k次时的退火温度.下面给出ACC_NEW_VAR 算法的执行过程：

算法3. ACC_NEW_VAR算法.

输入：任务处理位置集LOC、电压变化率集RATIO、任务执行顺序集ORDER、更新后的任务处理位置集LOC′、电压比例RATIO′、新任务顺序ORDER′;

输出：True或False.

令LOC,RATIO,ORDER所对应的当前目标函数值为F;

根据LOC′,RATIO′,ORDER′计算新的目标函数值F′;

ΔFF′-F;

IF(ΔF>0)

IF(e(F-F′)tempk≤rand())

RETURN False;

ENDIF

ENDIF

RETURN True.

3.5 算法流程

SA-DVSA算法是基于迭代求解策略的一种随机寻优算法，它从一个较高的初始温度开始，在旧解基础上随机改变某个任务执行的位置和电压，并在满足任务执行关系的情况下，随机交换2个任务的顺序，伴随温度的不断下降重复抽样过程，直至得到问题的优化解，算法主要分以下4步： 1)计算得到每个任务在各个移动设备处理器上电压变化率的取值范围；2)初始化可行解，计算得到适应度函数值F，并作为当前最优值；3)根据当前变量值随机得到新的变量值，计算新变量值对应的适应度函数值F′，判断是否接受；4)在同一温度下求解并取舍新变量若干次，之后进行退温操作tempi+1=λ×tempi(λ为温度下降率)，直至温度小于给定值阈值β.基于模拟退火算法的工作流任务调度SA-DVSA算法执行过程如下：

算法4. SA-DVSA 算法.

输入：工作流图G=V,E、任务数N、移动设备的处理器数M、任务在云端运行时间集TC={tc(vi)}、任务在云端运行能耗集EC={ec(vi)}、任务在移动设备的运行时间集TMK={tmk(vi,k)};任务在移动设备运行的能耗集EMK={emk(vi,k)}、截止时间TL;

调用算法INIT_VAR(N,M,TC,EC,TMK,EMK,TL);

tempnum×N×M;*初始化温度,num为同一温度下求解并取舍新变量的次数*

F*+∞,LOC*∅,ORD*∅,RATIO*∅;

WHILEtemp>βdo

FORi=1 tonumDO

调用算法CHANGE_VAR(LOC,RATIO,ORDER)，获取新解LOC′,RATIO′,ORDER′;

IF(ACC_NEW_VAR(LOC,RATIO,ORDER,LOC′,RATIO′,ORDER′)= True)

LOC=LOC′,RATIO=RATIO′,ORDER=ORDER′;

根据式(5)计算得到总能耗ETotal;

根据式(8)计算得到任务总完成时间TTotal;

根据式(9)计算目标函数值F；

ENDIF

IF(F

F*F,LOC*LOC,RATIO*RATIO,ORDER*ORDER;

ENDIF

ENDFOR

temptemp×λ;

ENDWHILE

RETURNLOC*,RATIO*,ORDER*.

现在分析一下该算法的时间复杂度.SA-DVSA算法外循环的迭代次数为logλ(β(num×N×M))(其中λ代表温度下降率，β表示最终温度，N表示任务总数，M表示移动设备的处理器总数)，时间复杂度约为O(logλ(M×N))且M

4 实 验

本文实验主要是基于2.1节中的工作流图示例(如图2所示)和随机产生的工作流图来与文献[18]中已有的DVFS算法，及没有采用DVFS技术的MCC-SA算法进行对比实验来得出结论，进而分析和评价本文所提出的SA-DVSA算法的效率.实验采用的仿真工具为MATLAB R2014a，计算环境为：Intel®CoreTMi7-4790 CPU@3.60 GHz，内存8 GB，运行在64位Windows7系统中.

由于文献[18]中的动态电压调节技术用到的是固定参数值，这样不利于寻找一个最优的参数从而使得可行解空间利用率达到最大，所以我们设计SA-DVSA算法时从目标函数中迭代寻找较优参数，这样以满足能耗与时间的多目标优化问题.在适应度函数F=α×TTotal+(1-α)×ETotal中，α为权重因子，α取值范围为0～1，为了得到α的有效取值，在实验时，我们以内核数量为3、随机生成的10个任务关系图为实验对象，得出α在不同取值时所对应的能耗和完成时间，结果如图4所示.

Fig. 4 Values of weight α图4 权重因子α的实验图

从图4可以看出，当α=0时，即只考虑优化时间，不考虑能耗问题，这时任务的完成时间最短，能耗最大;当α=0.3时，能耗明显减少，并且之后基本趋于稳定，此时任务完成时间相对于α=0时有所增加，但增值不是很多，α在0.3～0.7这段值之间，能耗和时间都基本趋于稳定;当α=1时，此时能源消耗最少，但任务完成时间剧增.因此，α的有效取值范围在0.3～0.7之间，最优取值为0.35，在后面的实验中α的取值都为0.35.

使用SA-DVSA算法进行任务调度实验时，算法过程中的迭代次数性能图如图5所示.

从图5中可以看出，在最开始迭代的时候，时间和能耗的波动都比较大，但整体的趋势是降低的，当次数迭代到800左右时2个值都逐渐趋于平稳，当次数达到1 100时2个值都达到了最优解.

Fig. 5 Number of iterations图5 实验迭代次数图

下面基于2.1节中所给的工作流图来测试3种算法的调度结果，整个应用程序的总完成时间不能超过限制时间30 s(即TL≤32 s).移动设备有3个处理器，每个处理器在最大电压频率下能耗分别为P1=1J,P2=2J,P3=4J.DVFS算法、MCC-SA算法和SA-DVSA算法调度结果分别如图6～8所示.

Fig. 6 Scheduling under DVFS algorithm图6 DVFS算法调度分配结果

图6是用DVFS算法调度分配的结果，总完成时间TTotal=26 s，总能耗ETotal=23J.图7是采用没有加入连续动态电压技术的MCC-SA算法调度分配的结果，此时TTotal=26 s，ETotal=22J，该算法虽然在执行时间上与DVFS算法的结果一样，但是所需能耗有所减少.SA-DVSA算法调度结果如图8所示，TTotal=23.03 s，ETotal=19.47J，对比DVFS算法、MCC-SA算法，其在总完成时间和总能耗方面的效果都更好.

Fig. 7 Scheduling under MCC-SA algorithm图7 MCC-SA算法调度分配结果

Fig. 8 Scheduling under SA-DVSA algorithm图8 SA-DVSA算法调度分配结果

从图7可以看出，在MCC-SA算法中，任务8～9之间存在1 s的时间空闲，为了更好地利用这部分时间，在满足各个任务的开始和完成时间范围内，我们可以通过降低电压增加任务处理时间来降低能耗：例如在图8中，任务3在处理器1上用最大电压的完成时间是6 s，即在时间为11 s的时候任务3结束；任务3完成之后执行任务7，但是任务7的开始时间是15 s，11～15 s之间存在4 s时间段的空隙，这时降低处理器电压频率，使得任务3的完成时间延长为14.687 s，这样既可以降低处理器的能耗，也可以得到任务3完成时间不超过15 s的调度策略，显然这种任务调度策略是更加优化的.

综上所述，可以看出本文提出的SA-DVSA算法无论是在完成时间上还是在能源消耗上都比DVFS算法及MCC-SA算法都要更好.

为了进一步证明本文算法的有效性，下面将通过随机产生的具有50～100个不同任务节点的工作流图来进行对比实验(移动设备的处理器数M=3).3种算法各自任务完成时间和能源消耗情况如图9所示：

Fig. 9 Energy consumption and completed time with number of tasks changing where M=3图9 任务数与时间能耗关系图(M=3)

图9(a)显示当任务个数变化时3种算法下各自的移动设备能耗,图9(b)表示3种算法在任务个数不同时与任务完成时间的关系.从图9中可以观察到，SA-DVSA算法无论是在任务完成时间上还是能耗上都比DVFS算法和MCC-SA算法要好.随着任务节点个数的增加，任务完成时间和能耗都随之增加，但是节点个数增加到一定数量之后，SA-DVSA算法的性能明显优于DVFS算法和MCC-SA算法，所以，SA-DVSA算法在大规模的任务节点数中有更好的优势.

在图10的实验中，我们将移动设备的处理器数设为M=6，每个处理器在最大电压频率下能耗分别为P1=1J，P2=2J，P3=4J，P4=8J，P5=16J，P6=32J.从图10中可以得出和图9中相似的结论.此外，从图9和图10中可以观察到，当移动设备的处理器数M增加时，任务完成时间相应减少了，但是能耗却增加了，这是因为当移动设备有了更强计算能力的处理器，许多任务将被调度到上面执行，这样工作流任务执行所需的总能耗也将随之增多.

Fig. 10 Energy consumption and completed time with number of tasks changing where M=6图10 任务数与时间能耗关系图(M=6)

5 结 论

任务调度是工作流系统管理中的重要研究内容，在移动云计算环境中进行任务调度时，一个重要问题就是如何制定调度策略使任务完成时间和能耗达到最小.以往的研究中主要都集中在如何降低能耗的问题上，对能耗和时间的联合优化研究得很少.本文所提的SA-DVSA算法对这2个目标进行联合优化，并通过实验验证了该方法比文献中的DVFS算法在任务完成时间以及能耗问题都有了进步.在今后的工作中，本文将尝试设计其他启发式算法与模拟退火算法相结合来解决移动云计算的任务调度问题，并综合考虑能耗、时间、安全等多方面因素[21]，这些有待于进一步的努力.

[1]Chen Shuang, Wang Yanzhi, Pedram M. A semi-markovian decision process based control method for offloading tasks from mobile devices to the cloud[C]Proc of the 2013 Int Conf on Global Communications. Piscataway, NJ: IEEE, 2013: 2885-2890

[2]Deng Shuiguang, Huang Longtao, Taheri J, et al. Computation offloading for service workflow in mobile cloud computing[J]. IEEE Trans on Parallel and Distributed Systems, 2015, 26(2): 3317-3329

[3]Khan A, Ahirwar K. Mobile cloud computing as a future of mobile multimedia database[J]. International Journal of Computer Science and Communication, 2011, 2(1): 219-221

[4]Miettinen A P, Nurminen J K. Energy efficiency of mobile clients in cloud computing[C]Proc of the USENIX Int Conf on Hot Topics in Cloud Computing. Berkeley, CA: USENIX Association, 2010: 14-21

[5]Mavroeidakos T, Michalas A, Vergados D. Security architecture based on defense in depth for cloud computing environment[C]Proc of the 2016 IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2016: 334-339

[6]Sarbazi H, Zomaya A. Large Scale Network-Centric Distributed Systems[M]. Piscataway, NJ: IEEE, 2014

[7]Singh B, Dhawan S, Arora A, et al. A view of cloud computing[J]. Communications of the ACM, 2013, 53(4): 50-58

[8]Patra B, Roy S, Chowdhury C. A framework for energy efficient and flexible offloading scheme for handheld devices[C]Proc of the IEEE Int Conf on Advanced Networks and Telecommunications Systems. Piscataway, NJ: IEEE, 2015: 1-6

[9]Kumar K, Liu Jibang, Lu Yunhang, et al. A survey of computation offloading for mobile systems[J]. Mobile Networks and Applications, 2013, 18(1): 129-140

[10]Balamurugan M, Akila V. Effective processor selection on heterogeneous computing[C]Proc of the 2016 Int Conf on Science Technology Engineering and Management. Piscataway, NJ: IEEE, 2016: 13-16

[11]Feng Bailong, Gao Jing. Distributed parallel Needleman-Wunsch algorithm on heterogeneous cluster system[C]Proc of the 2015 Int Conf on Network and Information Systems for Computers. Piscataway, NJ: IEEE, 2015: 12-18

[12]Ra M, Sheth A, Mummert L, et al. Odessa: Enabling interactive perception applications on mobile devices[C]Proc of the 9th Int Conf on Mobile Systems, Applications, and Services. New York: ACM, 2011: 43-56

[13]Yang Lei, Cao Jiannong, Yuan Yin, et al. A framework for partitioning and execution of data stream applications in mobile cloud computing[C]Proc of the 5th Int Conf on Cloud Computing. Piscataway, NJ: IEEE, 2012: 794-802

[14]Terzopoulos G, Karatza H. Dynamic voltage scaling scheduling on power-aware clusters under power constraints[C]Proc of the 17th Int Conf on Distributed Simulation and Real Time Applications. New York: ACM, 2013: 72-78

[15]Saravanan S, Venkatachalam V. Advance MapReduce task scheduling algorithm using mobile cloud multimedia services architecture[C]Proc of the 6th Int Conf on Advanced Computing. Piscataway, NJ: IEEE, 2014: 21-25

[16]Deshmukh N, Deorankar A. Minimizing energy consumption in transmission efficient wireless sensor network[C]Proc of the Int Conf on Advances in Electrical, Electronics, Information, Communication and Bio-Informatics. Piscataway, NJ: IEEE, 2016: 475-479

[17]Kumar K, Lu Yunhang. Cloud computing for mobile users can offloading computation save energy[J]. Computer, 2010, 43(4): 51-56

[18]Lin Xue, Wang Yanzhi, Xie Qing, et al. Task scheduling with dynamic voltage and frequency scaling for energy minimization in the mobile cloud computing environment[J]. IEEE Trans on Services Computing, 2015, 8(2): 175-186

[19]Davis L. Genetic Algorithms and Simulated Annealing: An Overview[M]. San Francisco, CA: Morgan Kaufmann, 1987

[20]Fleming P, Pashkevich A, Fleming P, et al. Computer aided control system design using a multiobjective optimization approach[C]Proc of the Int Conf on Control. Piscataway, NJ: IEEE, 1985: 17-26

[21]Han Rui, Liu Yingbo, Wen Lijie, et al. A probabilistic approach to analyze and adjust time constraints in workflow management system[J]. Journal of Computer Research and Development, 2010, 47(1): 157-163 (in Chinese)(韩锐, 刘英博, 闻立杰, 等. 工作流管理系统中一种概率性分析和调整时间约束的方法[J]. 计算机研究与发展, 2010,47(1): 157-163)

Hu Haiyang, born in 1977. PhD and professor. His main research interests include workflow system and parallel computing.

Liu Runhua, born in 1990. Master. Her main research interests include workflow system and business process management.

Hu Hua, born in 1964. Professor and PhD supervisor. His main research interests include workflow system and database theory.

Multi-Objective Optimization for Task Scheduling in Mobile Cloud Computing

Hu Haiyang, Liu Runhua, and Hu Hua

(CollegeofComputerScience,HangzhouDianziUniversity,Hangzhou310018) (KeyLaboratoryofComplexSystemsModelingandSimulation(HangzhouDianziUniversity),MinistryofEducation,Hangzhou310018)

Mobile cloud computing provides effective help for mobile users to migrate their workflow tasks to cloud servers for executing due to the mobile device’s limited hardware capability and battery energy carried. When scheduling workflow tasks between mobile devices and cloud servers, it needs to consider both the energy consumed by the mobile device and the total amount of time needed for the workflow application. Traditional methods for scheduling workflow tasks in mobile cloud computing usually address only one of two issues: saving energy consumption or minimizing the time needed. They fail to provide methods for jointly optimizing the time and energy consumption at the same time. Based on the relations of workflow tasks, the time needed in the workflow application is computed due to the tasks scheduling between the cloud servers and the mobile devices that use the technique of dynamic voltage and frequency scaling. The energy consumption for executing tasks on the cloud server and mobile devices are modeled and computed. The scheduling scheme and objective function for jointly optimizing the time needed and energy consumption are proposed. Algorithms based on the simulated annealing are designed for the mobile devices. Their time complexities are analyzed. Extensive experiments are conducted for comparing the proposed methods with other research works, and the experimental results demonstrate the correctness and effectiveness of our approaches.

mobile cloud computing; workflow; task scheduling; simulated annealing; multi-objective optimization

2016-10-24；

2017-02-06

国家自然科学基金项目(61572162,61272188);南京大学计算机软件新技术国家重点实验室开放基金项目(KFKT2014B15);江苏省自然科学基金项目(BK20131277) This work was supported by the National Natural Science Foundation of China(61572162, 61272188), the Foundation of State Key Laboratory for Novel Software Technology of Nanjing University (KFKT2014B15), and the Natural Science Foundation of Jiangsu Province of China(BK20131277).

TP311