移动云计算中任务的协同调度与卸载算法研究

发布时间：2020-07-29 22:15

【摘要】：为了满足人们生活中的各种需求,丰富复杂的应用程序相继被软件工程师开发出来。由于用户的大部分任务是复杂繁重的,而移动设备的计算能力和资源通常是有限的,这就使得用户对任务的实时高效的要求很难得到满足。目前,移动云计算技术是解决这类问题的主流方法。然而,并不是应用程序的所有子任务都适合卸载到云服务器上。同时,将子任务从移动端上传到云端,或从云端下载到移动端,移动设备都需要消耗相应的能量和时延。为使移动设备的能耗尽可能少和满足用户对任务的实时性要求,这就需要我们设计一种任务卸载和调度相结合的方法。关于移动云计算中任务的协同调度与卸载的问题,即移动云计算中的每一次任务卸载过程都需要调用任务调度的过程,不是单纯的任务卸载问题。对于此类问题,在当前学术界的研究中主要使用IBM的CPLEX优化器来进行解决,但是这种方法需要耗费很大的内存和计算资源,而且程序的运行时间很长,不适合应用在实际问题中。同时,由于IBM的CPLEX优化器解决的移动云计算中协同任务卸载和调度的问题并没有考虑到任务的异构性,而实际问题中任务通常是异构的,因此CPLEX优化器并不适合应用在实际问题中。关于移动云计算中协同任务的调度与卸载的问题,在现有的研究基础上,本文给出了一个更加适合实际物理问题的数学模型。该数学模型与目前这类问题的模型不太相同,主要是考虑到了应用程序中子任务的异构性。针对该模型,本文提出了一种启发式算法,来解决移动云计算中任务的协同卸载与调度的问题。该启发式算主要由任务卸载的过程和任务调度的过程组成。其中,启发式算法在每一次任务卸载的过程中都需要调用任务调度的过程,以便用来判断这次任务卸载的过程是否可行的。任务卸载过程采用了贪心的策略,目的是确保每次卸载一个子任务的时候,移动设备所需要的能耗减少量比上一次都尽可能大。任务调度过程利用了任务的优先权来进行实时调度,目的是确保应用程序的完成时间不超过它的截止时间。通过实验证明,本文提出的启发式算法能在较短的时间内得出问题的近似最优解。在模拟实验中,我们将启发式算法与现有的传统方法进行了对比。本文还提出了一种适合本研究的模拟退火算法,该算法对启发式算法的解进行了优化。经过实验观察及对比,我们发现模拟退火算法的解与启发式算法的解是十分接近的,进一步说明了我们的启发式算法是高效、可行的。
【学位授予单位】：广东工业大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP30
【图文】：

基本结构,移动设备,研究背景

第一章绪论研究背景及意义1 研究背景随着计算机技术的发展，各种各样的移动设备的性能获得了显著地提升，手机、平板、笔记本电脑等。社会经济的发展促使人们的生活更加多样化学习中的需求也越来越多，许多相应的软件相继被开发出来。这就使得移运行这类软件时需要更多的内存资源，计算资源和电量。虽然处理器和内经得到了很大的发展，移动终端的性能也有很大提升，但仍无法满足计算务的需求。同时，在移动设备上，数据密集型程序的执行受限于移动设备量，导致移动设备有限的资源将无法满足移动用户对相关资源的迫切需求

流程图,模拟退火算法,流程图

广东工业大学硕士学位论文Step5: 如果ΔC<0 则接受 V 作为新的当前解，即更新当前解；否则算法将会以概率 exp(-ΔC/T)接受 V 作为新的当前解。然而，如果当新解被判定为不可被接受的时候，则只需要在原当前解的基础上继续下一轮试验，即在。Step6: 如果满足终止条件，比如要求的目标函数的值或者温度下降到终止温度T0，则输出当前解作为最优解，结束程序。算法的终止条件是指，如果遇到连续很多个新的解决方案都不被算法接受时，那么就终止算法的运行过程。Step7: T 以衰减因子Δt 逐渐减少，且 T 趋向 T0，然后转 Step2。

拓扑图,依赖任务

边代表着两个子任务之间的数据交互或者信息交互。其中任务图，因为子任务之间的数据传输时单向不可逆的。任务图中只有一务节点，这个节点代表了应用程序的起始任务。同样，任务图中节点的任务节点，这个节点代表了应用程序的终止任务。合任务调度和卸载 (Joint Scheduling & Computation Offloading, Jard 问题[42]，一般都比较复杂。因此，现存研究的联合任务调度和情况下任务图的结构是串行依赖图,如图 3-1 所示，大大降低了研实际应用任务之间的依赖关系，在大部分情况下是非线性串行的应用程序所形成的任务拓扑图是十分复杂的，一个孩子节点或许或者一个父亲节点拥有多个孩子节点。但是，本文研究的任务图中不存在到自身的路径。很显然，这种假设是符合实际应用场景的子任务之间数据流是不会回溯的。

【相似文献】