移动云计算任务分配策略研究综述

张 璐，张艳飘

(河北经贸大学 信息技术学院，河北 石家庄 050061)

移动云计算任务分配策略研究综述

张 璐，张艳飘

(河北经贸大学 信息技术学院，河北 石家庄 050061)

移动云计算是移动互联网与云计算技术相结合产生的一种新技术，移动云计算技术的出现为移动用户提供了愈加丰富的应用以及更好的体验。本文针对移动云计算技术应用与发展面临的任务分配问题,分析了移动云计算的三种应用模式，比较了任务分配时常用的三种启发式算法的优点和不足，并对其进行了分析和总结，对任务分配问题提出了未来的展望。

移动云计算；应用模式；任务分配算法

前言

随着移动互联网和云计算技术的快速发展，为了满足用户对移动终端日益增加的种种需求，移动云计算技术应运而生。移动云计算技术构建了“云计算—互联网—移动端”的应用环境，克服了移动终端自身内存、电容量等性能的限制，提高了移动终端进行计算和存储资源的能力，给用户带来了更加丰富多彩的功能体验。在移动云计算技术中，用户的每一个需求即为移动云计算环境下的一个任务，用户需求实现的过程也就是移动云计算完成任务的过程。目前，如何合理地给各个计算节点分配任务，提高任务完成的效率是移动云计算研究的热点问题，还有待进一步解决调优。本文针对移动云计算面临的任务分配问题展开研究，分析梳理当前移动云计算任务分配问题的技术状况，并对其将来发展方向进行展望。

1 研究背景

移动云计算环境下进行任务分配的过程就是基于移动云计算平台动态可扩展地实现大规模任务分配调度的过程。移动云计算环境下进行任务分配的主要目标是减少用户等待时间，提高移动云计算平台的服务质量和资源利用效率，实现负载均衡[1]。移动云计算是以云计算为基础的进一步发展和扩充，因此云计算中的任务分配和调度策略可以为移动云计算的任务分配提供参考。移动云计算任务分配策略和云计算任务分配问题的不同之处在于，除了云平台中面临的问题外，移动云计算进行任务分配时还需要把移动终端的性能对系统性能的影响作为参考因素。

目前，国内外研究者对云平台任务分配问题展开了深入探索，取得了一定成果，可以供移动云计算学习和借鉴，而移动云计算任务分配问题的探索刚刚起步。文献[2]采用以神经网络算法为基础的程序资源消耗预测模型来估算云平台各项任务的资源使用情况，并根据预测结果设计采用混合遗传算法优化调度方案，降低能耗，节约成本。文献[3]建立了一种基于云计算环境的区分服务的演化博弈调度模型，实现了在动态的云平台环境下对任务资源进行合理分配，提高了任务的服务质量。文献[4]针对复杂任务，提出了改进的MapReduce模型，很大程度上提高了MapReduce模型的并行性，并设计了基于ACO的云计算任务调度算发法来解决用户多类型、多粒度的任务需求，增强了交互性。文献[5]针对移动用户将应用迁移至云端处理会引起大量的数据传输导致高能耗的问题，提出了一种任务联合执行策略，有效地减少了搜索最优解的运算时间，并在简单遗传算法的基础上，利用一次迁移最优特性来设计交叉操作和变异操作，进一步提高了算法性能。文献[6]为解决云环境下用户服务质量的优化问题，建立了新的工作流调度云系统模型和相应的数学模型，并在生物共生演算法的基础上改进并提出了一种拥有多维服务质量约束的工作流调度算法。文献[7]建立了一种称为策略迭代调度的新方法，全面优化了独立任务调度方案，最大程度地降低了优先级任务的总体执行时间，实现了云平台中任务的动态调度。文献[8]在网络状态良好的条件下，分别采用Dijkstra算法和贪心算法来计算任务执行最优时间和为任务寻找最合适的执行节点，实现任务执行耗时最短。文献[9]介绍了调度问题包括的4个步骤，并提出了一种新的算法，该算法以最小延迟调度方案为出发点，利用动态电压和频率缩放技术，通过在本地内核和云之间迁移任务，降低能量耗损。文献[10]基于蚁群优化算法研究了在混合MCC体系结构中多任务调度的MCC辅助执行问题，同时考虑到了任务的利润，任务期限，任务依赖性，节点的异质性和负载平衡等条件。

云计算平台中任务的分配与调度问题是专家学者研究的热点问题之一，但是随着计算机技术的不断进步，传统的分配方法不能很好地满足日益增长的应用需求。近来，启发式智能算法在任务分配中的应用为优化该类问题提供了新的解决思路和方法。

2 移动云计算应用模式

移动云计算的应用模式是任务分配工作展开的基础架构，应用模式的不同影响着任务分配策略的选择。目前，移动云计算的应用模式主要包括三种[11-12]：移动设备接入云端模式、云端增效模式和微云模式。本节将对这三种模式展开详细分析和阐述。

2.1 移动设备接入云模式

移动设备接入云端的模式下移动设备通过网络连接技术实现与云端的智能连接，并将所有的数据处理任务放到云端完成，因此该模式由SaaS 和IaaS共同服务。目前将移动设备接入云端的模式主要有以下应用：谷歌提供的地图和邮箱应用、苹果公司提供的存储同步应用等。文献[13]设计实现的基于R-OSGi技术的框架Alfredo是移动设备接入云模式的一种实现，该模式的任务调度问题与云平台中的任务调度问题处理方法相似。移动设备接入云端模式的应用环境如图1所示。

2.2 云端增效模式

云端增效模式通过移动互联网将移动设备应用运行时产生的一部分或全部数据存储和计算需求传送到云端完成，减少了资源有限问题对移动设备的影响，该应用模式是当前较常使用的一种移动云计算应用模式，一般被看作PaaS或IaaS服务。云端增效模式主要包含两种：固定模式和弹性模式，其中固定模式又包括瘦客户模式和胖客户模式。应用的小部分功能在移动设备中运行，大部分功能在云端完成，则是瘦客户模式，与之相反则是胖客户模式。计算任务能够在移动设备和云端之间较为灵活地进行动态分配，则是弹性模式。

文献[14]提出了一种基于云端增效模式的实现方案克隆云项目，该项目将移动设备的一部分应用通过虚拟机迁移技术传送到云平台的克隆云上完成。文献[11]采用了移动云计算的云端增效模式，在借鉴双处理器任务分配问题的基础上，提出了基于最大流理论的弹性任务分配算法，该算法能够将任务分配转换为网络流的求最小割问题，减少了应用执行时间，降低了网络费用。云端增效模式的应用环境类似于图1所示。

2.3 微云模式

微云模式与通常所说的移动云计算存在一定不同之处，微云模式中移动设备自身构建成一个自适应网络，其中部分移动设备执行计算节点(SLAVER)的功能，构成计算资源池即云平台端，给网络中的其他节点(MASTER)提供服务。如图2所示，同一个网络内包含多个移动设备，其中任何一个移动设备都既能当做云平台的计算节点来使用，又能看作云平台的客户端和调度中心。微云模式当前还处在实验研究过程中，不能广泛使用。

图1 移动设备接入云模式图 图2 微云模式示意图

文献[15]提出的Hyrax项目是微云模式的实现，该项目以云计算技术为基础，将移动设备作为计算节点，建立了一个移动的云资源池，一定程度上克服了移动设备自身的资源不足问题。文献[11]借鉴网格计算中的任务调度问题，将蚁群算法应用于微云模式的任务分配调度中，大程度降低了计算任务的运行时间。文献[12]设计了移动MapReduce框架，并综合考虑移动设备的计算性能等影响因素，以降低任务完成时间和系统设备总能耗为优化目标，在遗传算法的基础上提供了三种移动云计算任务分配算法。

本文通过对三种应用模式展开研究和比较，得出结论如表1所示。

表1 三种移动云计算应用模式的比较

3 三种智能化的任务分配算法分析

移动云计算中的任务分配问题是一个典型的NP完全问题，传统的移动云计算任务分配算法有Min-min算法、Max-min算法等，Hadoop中自带的任务分配算法有先进先出算法、公平调度算法等，但是这些算法都不能很好地满足用户的需要。近些年来，国内外专家和学者们陆续将启发式算法及其改进运用到任务调度问题中来，大大提高了任务分配的效率，本节将介绍3种启发性智能算法及其改进[16]。

3.1 遗传算法

遗传算法[17]是由Holland教授在自然选择和遗传学理论基础上提出的模仿生物界演化进程来寻找最优答案的一种方法。遗传算法由3个基本成分组成：种群、适应度函数和遗传操作，其中遗传操作中选择算子方法如公式1所示，N为种群大小，xi为个体，f(xi)为个体的适应度，P(xi)为个体的选择概率。

(1)

文献[18]基于Min-Min算法、Max-Min算法和遗传算法的基本原理，提供了一种优化的遗传算法，将Min-Min算法、Max-Min算法和遗传算法三种算法相结合，应用于云计算的任务分配过程中，提高了资源的使用效率。文献[19]基于遗传算法改进并设计了一种新的多目标动态调度算法，该算法面向动态多变的云计算平台，充分考虑任务长度和资源计算能力对任务执行的影响，将任务合理地分配给计算节点，缩短了任务的执行过程，减少了能量损耗。文献[20]为了解决遗传算法在求解过程中收敛速度太慢的问题，对传统的串行编码以及二进制编码方式进行了改进，使用了一种新型的任务-资源的编码方式，对染色体的表述更为直接，解决了染色体过长的问题。

3.2 蚁群算法

蚁群算法是根据生物界蚁群寻找食物的行为而提出的一种仿生算法，意大利学者M.Dorigo等先后提出了模拟蚂蚁觅食行为的AS(ant system)算法和ACS(ant colony system)算法，并将两种算法定义为 ACO(ant colony optimization)算法[21]。

蚁群的状态转移概率如式(2)所示，其中，k代表某只蚂蚁，i和j表示不同的位置节点，τij表示由i到j的信息素强度，α和β为常数，代表信息素和能见度的加权值。

(2)

τij计算公式如公式(3)所示，其中m代表蚂蚁个数，ρ表示信息素蒸发率，n为迭代次数。

(3)

(4)

文献[22]在改良蚁群算法的基础上提出了一种云计算任务调度算法，优化了蚁群算法的概率计算公式、信息素更新公式和常数β，提高了搜索速度，大幅度降低了云计算任务执行时间，解决了资源分配不平衡的难题。文献[23]采用了一种以时间成本负载加强型为基础的蚁群算法，基于各种最新的蚁群算法，创新地改进了信息素和启发信息，提高了云环境下资源分配的效率。文献[24]面向蚁群算法存在的固有缺陷，优化并设计了一种以优化的蚁群算法为基础的云计算任务分配算法，改善了蚁群算法不易获取到全局最优解的状况，减少了任务执行时间。

3.3 模拟退火算法

模拟退火算法是一种基于概率的算法，该算法是根据固体退火原理设计提出的，主要模仿物理学的固体退火降温过程来解决既定目标的组合优化问题，通过对问题解空间的查找来获得最合适的解。模拟退火算法的实现主要以Metropolis原则为根本计算准则：假设某系统在状态为xold时受到一定干扰而使其变成一种新的状态xnew，则系统的能量也发生相应变化，从E(xold)变为E(xnew)，其中系统的状态由xold变成xnew的接受概率p如公式5所示。

(5)

文献[25]将改进的离散形式的粒子群算法与模拟退火机制和混沌机制相结合来完成调度任务，降低了最小化工作流中任务完成所需的总的综合执行成本。文献[26]提供了一种以模拟退火算法为基础的队列级别调度策略，该策略将队列使用资源的效率当做退火概率，将作业期望完成时间、资源量限制等当做设计的参数，并结合高效率、低初始条件约束的模拟退火算法，提高了计算能力调度器的调度分配效果。文献[27]在云平台的MapReduce编程架构基础上，设计了一种结合蚁群算法和模拟退火算法的混合调度算法(ACOSA)，该算法分别把任务与资源的匹配因子和负载均衡度作为算法参数，降低了任务分配调度的时间。

以上三种算法及其改进都各有其优点和劣势，对其进行分析和比较结果如表2所示。

表2 三种智能算法对比分析

4 总结和展望

近年来，移动云计算技术快速发展并取得了大量研究成果，但在任务分配方面的研究还比较薄弱，尤其是移动云计算任务分配策略有待从以下几个方面开展深入研究：

(1)提高和完善硬件技术：现有的移动云计算应用模式还不成熟，如微云模式还处在试验阶段，大部分移动设备仍受硬件性能限制，有待进一步提高和完善硬件功能和性能。

(2)设计更高效的任务分配算法：本文提到的任务分配算法都受到参数的制约，参数不易控制，运行时间长，如模拟退火算法初始温度的设置问题，今后应继续研究算法在时间和参数控制方面的改进，设计更高效的任务分配算法，减少调度成本缩短分配时间。

(3)综合提升移动云计算系统效能：移动端设备和云计算平台自身都存在一定的局限性，如移动设备的电池容量、存储量、云计算的安全等问题，如何从系统整体出发更高效地解决移动云计算的任务分配问题有待继续深入研究与实践。

[1] 何富江.云环境下任务分配策略的研究[D].江西理工大学，2015.

[2] 吴世山.面向节能的云计算任务调度策略研究[D].哈尔滨工业大学，2013.

[3] 张希翔.云计算环境下任务调度算法的研究[D].广西大学，2012.

[4] 史恒亮.云计算任务调度研究[D].南京理工大学，2012.

[5] 柳兴，李建彬，杨震,等.移动云计算中的一种任务联合执行策略[J].计算机学报，2017，40(2):364-377.

[6] 刘振鹏，刘晓丹，张锡忠,等.云环境下一种多维QoS约束的工作流调度算法[J].郑州大学学报(理学版)，2017，49(2):91-96.

[7] Hu B，Xie N，Zhao T，et al.Dynamic Task Scheduling Via Policy Iteration Scheduling Approach for Cloud Computing[J].Ksii Transactions on Internet & Information Systems，2017，11.

[8] Shi C，Lakafosis V，Ammar M H，et al.Serendipity: enabling remote computing among intermittently connected mobile devices[C]// ACM MOBIHOC.2012:145-154.

[9] Lin X，Wang Y，Xie Q，et al.Task Scheduling with Dynamic Voltage and Frequency Scaling for Energy Minimization in the Mobile Cloud Computing Environment[J].IEEE Transactions on Services Computing，2015，8(2):175-186.

[10] Wang T，Wei X，Tang C，et al.Efficient multi-tasks scheduling algorithm in mobile cloud computing with time constraints[J].Peer-to-Peer Networking and Applications，2017:1-15.

[11] 姚慧峰.移动云计算环境下任务分配问题的研究[D].南京邮电大学，2014.

[12] 王祝琳.移动云计算中任务分配策略研究[D].吉林大学，2016.

[13] Giurgiu I，Riva O，Juric D，et al.Calling the Cloud: Enabling Mobile Phones as Interfaces to Cloud Applications[J].Lecture Notes in Computer Science，2009，5896:83-102.

[14] Chun B G，Ihm S，Maniatis P，et al.CloneCloud: elastic execution between mobile device and cloud[C]// Conference on Computer Systems.ACM，2011:301-314.

[15] Marinelli E E.Hyrax: Cloud Computing on Mobile Devices using MapReduce[C].Hyrax Cloud Computing on Mobile Devices Using Mapreduce，2009.

[16] 苏淑霞.面向云计算的任务调度算法研究[J].安徽大学学报(自科版)，2014，38(5):24-30.

[17] Bratton D，Kennedy J.Defining a Standard for Particle Swarm Optimization[C]//Swarm Intelligence Symposium，2007.Sis.IEEE，2007:120-127.

[18] 杨福涛，孟宪勇.改进遗传算法在云计算任务调度中的应用[J].软件导刊，2015，14(10):5-8.

[19] 钟潇柔，翟健宏.基于动态遗传算法的云计算任务节能调度策略研究[J].智能计算机与应用，2015，5(3):37-39.

[20] 宣豪骏.基于遗传算法的云计算任务调度策略的研究与实现[D].昆明理工大学，2016.

[21] Dorigo M，Caro G D.Ant colony optimization:a new meta-heuristic[C]// Evolutionary Computation，1999.CEC 99.Proceedings of the 1999 Congress on.IEEE，2002:1477 Vol.2.

[22] 张海玉.基于改进蚁群算法的云计算任务调度研究[J].微电子学与计算机，2016，33(9):110-113.

[23] 聂清彬，蔡婷，王宁.改进的蚁群算法在云计算资源调度中的应用[J].计算机工程与设计，2016，37(8):2016-2020.

[24] 谢伟增.改进蚁群算法的云计算任务调度方法[J].计算机系统应用,2017,(06):198-201.

[25] 赵轩，蔚承建，王开,等.离散PSO结合模拟退火算法解决云调度问题[J].微电子学与计算机，2013，30(5):137-140.

[26] 李悦.基于改进模拟退火算法的Hadoop云平台下新型调度器的研究和开发[D].太原理工大学，2014.

[27] 张浩荣，陈平华，熊建斌.基于蚁群模拟退火算法的云环境任务调度[J].广东工业大学学报，2014,(3):77-82.

Researchonresourceallocationstrategyinmobilecloudcomputing

ZHANGLu，ZHANGYan-piao

(Information&TechnologyCollege，HebeiUniversityofEconomics&Business，ShijiazhuangHebei050061，China)

Mobile cloud computing is a new technology which is combined with mobile Internet and cloud computing，the appearance of mobile cloud computing provides a richer application and a better experience for mobile users.In this paper，three application modes of mobile cloud computing and three kinds of heuristic algorithms commonly used are introduced，which was based on the application of mobile cloud computing and the task assignment problem.This paper also puts forward the prospect of the future by analysis and summary.

Mobile cloud computing; Application mode; Task allocation algorithm

2017-08-14

张 璐(1995-),女，河北定州人，硕士研究生，研究方向：移动云计算与大数据.

1001-9383(2017)03-0018-07

TP393

A