摘 要

随着通信行业突飞猛进的发展，用户对通信质量的要求也逐渐增加。一种新的网络结构：移动边缘计算（Mobile Edge Computing MEC）被提了出来，这种网络结构旨在将云服务器放置在通信网络的边缘，有效地减小密集型任务从本地卸载到云服务器的距离，从而减少通信过程中所造成的延迟。而移动边缘计算对卸载的任务的调度关乎到用户应用的完成时间和所需能耗。

本文致力于研究基于移动边缘计算对于依赖性任务卸载的调度算法研究。本文研究分析了几种现有的调度算法：EZ算法、MCP算法以及MD算法，并通过算法原理的比较，得出了这几种算法的优缺点。本文结合了依赖性任务图的关键路径的概念，并采用了贪婪算法的概念，设计了根据任务图关键路径来调度任务节点的DCP算法，此算法还能够由用户提出优化要求来设置算法的优化调度次数，使得应用完成的时间达到用户预期。

本文使用JAVA以及Matlab模拟现有的几种算法和DCP算法，使不同的算法对相同的依赖性任务做出调度优化，并对优化结果做出比较。经过多次实验证明了DCP算法的优势。

关键词： 移动边缘计算；任务卸载；依赖性任务模型；任务调度；JAVA；Matlab。

Abstract

With the rapid development of telecommunication industry, users'requirements for communication quality are increasing. A new network structure, Mobile Edge Computing MEC (Mobile Edge Computing MEC), has been proposed. This network structure aims at placing cloud servers on the edge of communication networks, effectively reducing the distance from local unloading of intensive tasks to cloud servers, thereby reducing the delay caused by communication. The task scheduling of mobile edge computing for unloading is related to the completion time and energy consumption of user applications.

This paper is devoted to the research of scheduling algorithm for dependent task unloading based on mobile edge computing. This paper studies and analyses several existing scheduling algorithms: EZ algorithm, MCP algorithm and MD algorithm, and obtains the advantages and disadvantages of these algorithms by comparing their principles. This paper combines the concept of critical path of dependency task graph and adopts the concept of greedy algorithm, designs a DCP algorithm to schedule task nodes according to the critical path of task graph. This algorithm can also set the optimal scheduling times of the algorithm by the user's optimization requirements, so that the application completion time can meet the user's expectations.

In this paper, JAVA and Matlab are used to simulate several existing algorithms and DCP algorithms, so that different algorithms can optimize the scheduling of the same dependent tasks, and the optimization results are compared. The advantages of DCP algorithm have been proved by many experiments.

Key words: Moving edge calculation; Uninstall tasks; Dependency task model; Task scheduling; JAVA; Matlab.

目录

第1章 绪论 1

1.1目的意义 1

1.2国内外研究现状 3

1.3论文内容安排 4

第2章 设计相关原理 6

2.1依赖性任务模型的建立 6

2.2几种其他的调度算法 7

2.2.1 EZ算法 8

2.2.2 MCP算法 10

2.2.3 MD算法 11

第3章 算法设计与实现 14

3.1算法设计原理 14

3.1.1动态关键路径 14

3.1.2 DCP任务节点 15

3.1.3服务器选择 17

3.2 算法仿真与实验结果分析 17

3.2.1 DCP算法 17

3.2.2实验结果分析 20

第4章 总结与展望 26

4.1研究工作总结 26

4.2未来研究展望 27

参考文献 28

附录A 30

致谢 38

第1章 绪论

1.1目的意义

近年来，随着通信行业突飞猛进的发展，移动互联网的发展也十分迅速，加上通讯设备工厂化的生产和企业巨头的加大研发，促进了移动手持设备的进步。同时，人们日益剧增的信息交换的需求与对移动设备功能多样化的要求促使了智能移动设备（smart mobile devices SMD）的高速发展。

智能移动设备使用数量爆炸式增长，催生出了各种新的应用。机器学习、虚拟现实、人脸识别等计算密集型应用的出现，使的用户对移动终端计算能力要求更高。智能移动设备被视为支持计算密集型应用的主要未来计算设备，例如交互式游戏，图像/视频处理，电子商务和在线社交网络服务^[1][2]。

这些应用运行在智能移动设备上需要消耗大量的计算资源。由于智能移动设备受限的可用资源以及有限的电池容量，在智能移动设备上完成应用的质量以及设备电池续航都存在较大问题，因此难以长时间支持这些计算密集型程序，最终影响用户的使用体验。

已经有作者提到，复杂的应用的处理需要智能移动设备有更高的计算能力，内存和电池寿命^[3]。然而，由于物理尺寸限制，移动设备通常受资源限制。电池的有限能量供应一直是SMD最具挑战性的设计问题之一^[4][5][6][7]。

在移动设备上不能良好的解决计算密集型任务的问题，推动了移动云计算(mobile cloud computing MCC)概念的发展，MCC允许移动用户将计算密集型应用从移动设备本地卸载到云端进行计算。 通常，远程的云服务器由大量高性能服务器组成，具有较强的计算能力。用户可以将计算密集型程序卸载到远程服务器（centralized clouds CC）执行，远程服务器运行完后再把运行的结果回传给用户。

随着诸如3G，Wi-Fi和4G之类的无线通信技术的发展，移动云计算被设想为解决这种挑战的有前途的方法。移动云计算的目标是将资源丰富的远程云服务器的强大计算能力扩展到资源受限的智能移动设备，以增加移动设备的计算潜力。为了实现这一目标，移动云计算需要通过无线访问将资源密集型计算从智能移动设备迁移到云服务器，这一过程被称为卸载计算。

移动云计算中的移动应用程序需要划分为可以在移动设备上执行的一系列任务，称为本地计算/执行，还有一系列在云上执行，称为云计算/执行。

很明显，移动云计算可以容纳智能移动设备来执行复杂的应用程序，由于移动设备的资源不足，许多应用程序仅在移动设备上运行是不切实际的，例如感知应用程序^[4]。

移动云计算还有另一个优点，就是可以通过选择性地将应用程序的任务卸载到云上来改善移动设备的性能。此外，还有利于节省移动设备的能源并延长操作时间。

总的来说，使用远程的云服务器主要有以下几个优点：1）通过将移动设备端的计算密集型应用卸载到远程服务器运行，可以增加移动设备电池的续航时间；2）由于远程云服务器具有较强的处理器，可以较为快速地处理来自用户的计算密集型任务；3）远程服务器具有较大的存储空间，这为移动设备端解决不了的计算密集型程序提供存储能力。

但是使用远程服务器也不可避免的带来了一些问题，智能移动设备终端需要将本地的数据上传到云服务器，由于云服务器距离移动用户位置较远，因此处理应用的过程中，会造成较高的系统延迟，进而严重影响了用户实时应用程序的使用体验，经查阅资料，预计到2020年，全球智能移动设备总量将达到750亿部，而移动通信流量将超过24.3艾字节/月，并且随着用户们的移动设备将越来越智能化，智能设备中的应用将需要快速的计算能力和持久的数据处理所需的续航能量。如若智能终端将复杂计算卸载到远程的云服务器，可能会造成严重的网络拥堵，使通信带宽受限。

为了克服上述问题，一种新的网络结构移动边缘计算（Mobile Edge Computing MEC）被提了出来，这种网络结构旨在将云服务器放置在通信网络的边缘，拉近移动用户与云服务器之间的物理位置，有效地减小密集型任务从本地卸载到原服务器的距离，从而减少通信卸载过程所造成的延迟。

移动边缘计算拥有邻近移动用户接入的特点，它允许移动设备终端将计算复杂的应用卸载到云端，从而提高应用的服务质量（Quality of Service QoS）。此外，由于 MEC 系统能够在动态网络环境下快速地响应交互式应用请求，因此它也适用于车联网场景。

将云服务器放置在通信网络的边缘位置，移动用户可以通过无线网络等方式，将智能移动设备的计算密集型任务卸载到边缘服务器，减小了网络延迟。同时可以延长移动用户终端的使用时间，提升了用户的程序使用体验。移动边缘计算网络的提出是为了解决下一代移动通信（5G）面临的大量智能移动设备接入互联网造成的计算资源短缺的问题。移动边缘计算可以使得移动网络传输成本更低、效率更高、应用复杂度不受移动终端的限制。但是边缘服务器与远程云服务器相比较，计算能力受限，网络存储能力较于云中心服务器较小，因此当边缘服务器服务于用户时，需要考虑任务卸载决策（任务在本地执行或者上传到边缘服务器执行）以及任务之间的调度，从而在任务的协调下达到资源利用价值最大化。

用户可以选择将任务全部卸载到边缘服务器，也可以选择部分任务卸载到边缘服务器。由于边缘服务器与远程云服务器比较，计算能力受限，同时内存资源也较小，因此若用户将任务全部上传至边缘服务器可能会导致边缘服务器拥塞，同时也会影响用户的使用体验。与全任务卸载相比，部分任务卸载可以利用边缘服务器以及移动智能终端并行处理任务，提高工作效率，进一步降低了网络的延迟。

经查阅文献，许多作者在先前研究都考虑了独立任务的计算卸载，但是应用程序的计算任务通常依赖于彼此，并且各应用的数据输入有时需要满足严格的时序优先^{[8][9][10][11][12][13]}。因此，在本论文中，考虑的任务模型是相互依赖的任务，并在它们之间进行可能的数据通信。每个任务都可能具有必须在任务开始之前完成的前置任务。此外，如果需要在不同处理器上的任务之间传输数据，则可能会产生通信延迟以及通信成本。

通过在云端的边缘设备上执行应用的数据分析，可有效地应对数据爆炸问题，减轻网络的流量压力。边缘计算卸载能够缩短移动设备的响应时间，从而减少了从设备到远程与服务器的数据流量，以便在网络中更有效的分配资源。所以对于现实中依赖性任务的边缘卸载计算的研究是十分有必要的。

目前移动边缘计算中任务卸载问题比较复杂，如何有效的调度用户智能移动端的密集任务是一大挑战。正是基于这些挑战，本文尝试研究依赖性任务的卸载模型，研究如何正确地调度依赖性任务，提高资源的利用率，达到能量利用率最大化。因此本文的研究对于边缘计算的发展是有帮助的，并且具有广泛的现实意义。

1.2国内外研究现状

目前移动边缘计算的发展处于研发初期的阶段，主要研究通信网络架构的设计以及任务调度的策略。目前移动边缘计算服务器的架构以及任务调度策略正在被广泛的研究。

第一个提出在网络边缘放置的服务器，拉近与移动用户的距离的系统Cloudlet。Cloudlet的目标是通过在策略计算的位置放置合适大小资源的服务器为邻近的移动用户提供网络计算的资源。Cloudlet通过WiFi 热点或其他无线接入点覆盖一个区域，用户通过连接 WiFi 将计算任务上传至边缘云服务器进行计算，云服务器计算完后，将计算的结果回传给用户。Dinh等人调研了移动微云，主要介绍了移动微云中的应用程序。Fesehaye 等人介绍了微云之间的交互，利用微云进行内容缓存以及实现计算卸载。但是用户必须切换移动网络使用 WiFi 热点连接到微云，由于WiFi热点有限的覆盖范围，严重影响了用户的接入地点以及限制了用户的移动性^[14]。

另一种移动边缘计算方式 ad-hoc cloud，该网络通过组合大量的邻近的终端设备，通过共享这些终端设备的处理器以及内存等资源，从而支持处理计算密集型任务。实现这种系统有以下几个缺点：1）首先需要在网络边缘找到足够的终端设备；2）在没有统一的控制器的情况下进行资源管理，实现多个终端协作，完成计算密集型任务；3）用户需要贡献出自己的电池电量、CPU 处理器资源以及内存等资源，并且当用户贡献资源用于处理任务时，难以保证数据安全^[15]。此外，国内外研究人员将重点放在应用卸载上，以加快应用的执行。Chun 等人提出了 CloneCloud，通过使用一些执行节点对总任务进行二分，得到一系列子任务，以便最高效的进行执行。因此，CloneCloud可以为每个分区确定最有效的执行点。

早期研究关于依赖型任务的卸载工作通常只关注单个性能指标，通常是能量还是完工时间，在论文中，作者旨在确定减少能耗的任务调度决策^{[16] [17]}。但是他们两者都假设移动设备和云服务器上的任务不会同时运行，这对于他们的论文可以是正确的，因为并行执行无法实现能量增益。但是，利用移动设备和云服务器之间的工作并行性可以大大提高应用程序的完工时间。有研究就提出负载平衡启发式算法和遗传算法用于依赖任务，使完工时间减少^[8]。

现有的大多算法的目标是在具有应用完成截止日期的移动设备上最大限度地节省能源，他们的基于简化的假设，即移动设备和云上的任务不能同时运行，并且任务计算和数据通信不能同时发生^[18]。

有的论文中，作者针对确定和随机的应用期限提出了动态规划算法^[17]。有的论文中都假设了移动设备具有有限的容量并且可以同时执行任意数量的任务而不会影响每个任务的处理时间^{[10] [18]}。但是这种假设是不现实的，因为用户设备通常是资源有限的。在本论文的设计中中，计算系统由有限容量设备组成。允许本地设备和云之间的并行执行。此外，有的论文中仅考虑从移动设备到远程云的迁移^{[10] [18]}。相比之下，本论文对处理器网络的建模是通用的，可能包括各种移动处理器，边缘云服务器，云端云服务器。

1.3论文内容安排

本文的题目是边缘计算的依赖性任务卸载算法研究。从上文可知，对于用户应用的边缘卸载算法研究已经成为一个热门的研究方向。本文的基本目的就是基于依赖性任务中任务节点之间的依赖性，对依赖性任务做出调度，使得整个应用程序的完成时间达到用户的要求。在设计过程中，我们使用到了JAVA 来对本文提到的几种算法进行编程实现，并将结果输入到Matlab中绘制出折线图，更加直观的进行比较。本文的主要结构如下：

第1章为绪论，主要介绍了本研究的目的意义以及现阶段国内外对边缘计算任务调度的研究现状。

第2章详细的讲解了与本文设计的算法的基本原理，包括边缘计算中的依赖性任务的有向无环图模型，并介绍了现有的几种调度算法：EZ算法、MCP算法以及MD算法，通过分析这几种调度算法的原理，得出了各算法的优缺点。

第3章详细地讲解了DCP算法的通信模型以及算法的详细步骤，介绍了动态关键路径的概念，将任务节点加入到调度任务集中的方法，以及为需要调度节点选择服务器的方法。使用JAVA对提到的几种算法进行编程实现，并对相同的依赖性任务进行优化对比实验，将优化结果输入Matlab中绘制折线图，使得可以直观地观察并分析对比实验结果。

第4章中，对本文研究的工作进行了总结，并对未来研究工作的方向进行了展望。

第2章 设计相关原理

本节概述了本论文在边缘计算过程中的依赖性任务的模型、通信模型。

2.1依赖性任务模型的建立

本论文假设在位于需要计算的区域中有N个智能移动设备（SMD），由一组N = {1,2，...，N}表示，每个移动设备都具有需要完成的计算密集型移动应用。

在移动云计算中的移动应用程序可以被划分为M个相互依赖的任务的序列，由一组M = {1,2，...，M}表示。

智能移动设备可以以两种方式卸载到到边缘云服务器，即通过移动网络（电信网络）或通过Wi-Fi接入点，如图2.1所示。在移动网络的情况下，移动设备如蜂窝智能手机连接到移动网络通过基站（BS），使用3G或LTE通信。在Wi-Fi接入点的情况下，SMD通过Wi-Fi连接到接入点。

图2.1 智能移动设备接入云服务器