摘 要

移动边缘计算（MEC）技术已经成为信息领域不可或缺的关键技术，它大大推动了应用程序在移动设备上的推广。MEC可以显著提高任务卸载的效率，MEC中任务的卸载已经成为近年来研究的热点问题。本文充分研究了MEC和任务调度的研究现状，提出了一种动态迭代关键路径（IDCP）调度算法，IDCP算法借鉴了贪婪算法的思想，根据关键路径的相关原理设计了一种调度任务集，对任务图（DAG）进行迭代调度；并根据动态调度的特点，在每次节点调度后动态更新所有任务节点的状态，最终实现动态地缩短关键路径的长度。在性能评估部分，本文将DAG执行算法后的关键路径长度与初始的关键路径长度之比定义为伸缩比，作为本次实验的评估指标。本文分析了IDCP算法在不同任务复杂度和迭代次数下的性能，并通过与其他调度算法对比验证了本文所提出算法的优越性。

关键字：MEC，任务调度，DAG，IDCP

Abstract

Mobile Edge Computing (MEC) technology has become an indispensable key technology in the field of information, which greatly promotes the promotion of applications on mobile devices. MEC can significantly improve the efficiency of task unloading. Task unloading in MEC has become a hot issue in recent years. In this paper, the research status of MEC and task scheduling is fully studied, and a dynamic iterative critical path (IDCP) scheduling algorithm is proposed. The IDCP algorithm draws on the idea of greedy algorithm, designs a scheduling task set based on the principle of critical path, and schedules the task graph (DAG) iteratively. According to the characteristics of dynamic scheduling, it updates all tasks dynamically after each node scheduling. The state of task node can shorten the length of critical path dynamically. In the part of performance evaluation, the ratio of the critical path length of DAG to the initial critical path length is defined as the scaling ratio, which is used as the evaluation index of this experiment. This paper analyses the performance of IDCP algorithm under different task complexity and iteration times, and verifies the superiority of the proposed algorithm by comparing with other scheduling algorithms.

Key Words: MEC, task scheduling, DAG, IDCP

目 录

第1章 绪论 1

1.1 研究背景及意义 1

1.2 研究现状 2

1.2.1 MEC研究现状 2

1.2.2任务调度研究现状 6

1.3 研究内容及组织结构 6

第2章 算法原理 8

2.1 DAG 8

2.1.1 DAG的定义 8

2.1.2 DAG的数学属性 9

2.1.3 DAG的遍历 9

2.2 节点的调度 10

2.2.1 静态调度 10

2.2.2 动态调度 10

第3章 算法设计 12

3.1 节点选择 13

3.2 建立调度工作集 14

3.3 贪婪算法 15

3.4 IDCP算法 16

第4章 性能评估 17

4.1 迭代次数 17

4.2 节点数量 18

4.3 算法对比 19

4.3.1 对比算法介绍 19

4.3.2 实验结果及分析 20

第5章 总结与展望 21

5.1 总结 21

5.2 展望 21

参考文献 23

致 谢 25

第1章 绪论

1.1 研究背景及意义

小型移动设备在技术和设计上的突飞猛进，给我们提供了一个广阔且有力的平台去实现许多新的移动应用[1][2]。例如交互性游戏，虚拟现实以及自然语言处理等，它们都是典型的计算密集型应用程序，需要消耗大量的计算资源和能量[3]-[5]。然而我们日常生活中的小型移动设备仅有有限的计算能力和电池容量，这种在资源消耗型应用和资源受限型移动设备之间的冲突给新型应用程序在移动设备上的推广带来了前所未有的挑战。

一种叫做移动云计算(MCC)的新型技术给解决上述挑战提供了可能。通过将移动设备上的任务迁移到基于基础架构的云服务器，移动边缘计算可以在优化应用程序表现的同时减少移动设备的能量消耗。然而，基于基础架构的云服务器一般位于网络的中心，即远离于移动设备。在移动设备和云服务器之间的长距离传输可能会导致延迟波动并导致额外的传输能量消耗[6]。因此，计算卸载的效率会严重降低。

图1.1 MEC系统简图

移动边缘计算(MEC)被认为是提高卸载效率的一种可观的方法，系统简图如图1.1所示。在移动边缘计算的框架中，云计算能力是由靠近这些移动设备的无线接入网络提供的[7]，换言之，在移动边缘计算的帮助下，移动设备并不需要将任务卸载到网络中心的服务器上，而是将它们的任务卸载到网络边缘的MEC服务器上。这种MEC的模式在计算卸载过程中具有低时延、高带宽、高计算敏捷性以及对无线电网络信息和位置感知的实时洞察的特征。所有这些都可以转化为价值，并为移动运营商、移动应用和资源提供商创造机会，使他们能够更好地通过此获得高收益，并在多种业务模式中相互促进和激励。

用户可以选择将任务全部或者部分卸载到边缘服务器。文章[8][9]主要研究了将任务全部卸载到云端，从而最小化完成时间或者能耗。在另一方面，由于移动边缘服务器和中心服务器相比计算能力有限、内存资源也较小，如果选择将任务全部卸载到云端可能会导致边缘服务器拥塞。于是与全部卸载相比，部分卸载更具有灵活性，往往能给用户带来更好的体验，因此本文研究的重点为部分卸载。由于研究问题的方便性，目前大多数的研究工作[10]-[13]都是基于单用户的部分任务卸载，在单用户的研究模型中，边缘服务器被理想化为具有充足的计算资源来执行计算任务。

目前移动边缘计算中任务卸载问题比较复杂，也是学术界的热点问题，正是基于此，本文尝试研究移动边缘计算中的任务卸载问题。

1.2 研究现状

1.2.1 MEC研究现状

第一个通过在网络边缘放置服务器缩小服务器与用户的通信距离的系统cloudlet是由M. Satyanarayanan，Victor Bahl等人提出的[14]，一个cloudlet就是一个位于网络边缘的移动增强型的小规模云数据中心，其部署架构就像是如今的Wi-Fi接入点，解决方案为用虚拟机技术对cloudlet的基础架构进行瞬态定制，使用前定制和使用后清理可确保每次使用后cloudlet基础架构恢复到原始软件状态，无需人工干预，其最终目标就是缩小通信距离。Debessay Fesehaye，Yunlong Gao等人研究了cloudlet对交互式移动云应用程序的影响，并提出了云网络和服务架构的设计，并推荐使用自适应方案利用微云进行内容缓存和计算卸载[15]。

另一种移动边缘计算方式为基于ad hoc模式的ad-hoc cloud，即点对点模式的云计算网络。该网络通过组合大量邻近的终端设备，临时云计算的志愿云基础架构将允许云服务在现有的这些异构设备上运行。通过共享这些终端设备的处理器及内存等资源，提高组织的资源利用率，从而支持处理计算密集型任务，这可以节省大量成本，该模型类似于志愿计算[16]-[18]。但在实际的应用中，ad-hoc cloud存在诸多限制，例如很难在没有统一管理器的情况下进行资源管理，实现多异构处理器的协作以及各处理器在处理共享数据时的安全问题等。

Cisco公司于2012年提出雾计算模型，雾计算位于智能终端设备和传统云或数据中心之间，把云计算的范式拓展到网络的边缘[19]。这种模式通过提供无处不在、可扩展、分层、联合和分布式计算、存储和网络连接，支持垂直隔离、延迟敏感的应用程序。因此，雾计算被认为是物联网（IoT）和大数据应用的关键推动者之一。雾计算具有与云计算相似的特征，又区别于云计算，雾计算面临着新的安全和隐私问题。[20]中研究了雾计算中的安全和隐私问题，包括信任及授权、信任模型、流氓雾节点、网络安全以及安全数据存储等问题。在[21]中，Rodrigo Romana等人详细分析了云计算中各种范式的区别和联系，并指出MEC在起步阶段所面临的安全威胁和挑战。

图1.2 MEC框架设计图

MEC是一种由欧洲电信标准化协会（ETSI）在2016年才标准化的新技术，最早于2013年被提出，并已和网络功能虚拟化（NFV）技术以及软件定义网络（DSN）技术一起被欧洲5G PPP（5G Infrastructure Public Private Partnership）组织认定为5G网络的关键技术。ETSI给出的MEC的框架如图1.2所示，MEC使移动边缘应用程序可以实施成为一个软件实体运行在虚拟化基础设施上，MEC系统由MEC系统管理层，MEC主层和外部相关层组成。MEC框架显示了涉及的一般实体，可分为系统级、主机级和网络级实体。MEC在移动网络边缘、无线接入网络（RAN）内以及移动用户附近提供IT服务环境和云计算功能，其目的是减少延迟，确保高效的网络操作和服务交付，并提供改进的用户体验。MEC代表了实现5G演进的关键技术和架构概念，因为它有助于推动移动宽带网络向可编程世界的转变，并有助于满足5G在预期的整体性、延迟、可扩展性和自动化方面的要求[22]。

前文已经讨论了几种主要云计算范式的研究现状，接下来本文将继续讨论一下这几种云计算范式的异同。当分析不同范式的特点时，一个显而易见的结论是它们产生于不同的背景却有着基本相同的目标：将类似云计算的功能带到网络的边缘。如图1.3所示，它们都支持某种类型的多组虚拟化基础设施（例如雾节点，MEC服务器，cloudlet），并可以通过多种网络（例如光纤，无线网，高速移动宽带）轻松获取。这些基础设施可以根据需要调整对其用户位置和需求的能力供应，访问附近的计算资源（例如邻居虚拟池，分布式移动设备）。此外，所有范式都考虑到监测不同资源使用时的需要，尽管负责这种监测的实体和这些实体的分布根据范式各异[21]。每种范式都充分使用多种策略来支持用户移动性：从位于网络层次结构中更高级别的移动性管理实体到支持虚拟机（VM）迁移的机制。所有范式都可以作为云的扩展，补充其服务，从而创建分层的多层体系结构。另一方面，这些范式的要素也能以分散的方式表现；边缘数据中心可以自主提供服务和决策，并且可以相互协作，而不必完全依赖中央基础设施。此外，所有范例都追求创建联合的基础设施，其中多个边缘基础设施可以共存和交换。

图1.3 主要云计算范式的概述

即使所有这些范式都有相同的目标，但也会在如何实现这一目标方面存在一些潜在的差异。例如，MEC将边缘计算平台的部署限制为移动网络基础设施，如5G。而雾节点可以部署在其他位置，例如用户管理的服务器、接入点、路由器、网关等。至于MCC，它具有更加分散的范围，在某些情况下，设备本身可以参与在服务提供过程中。边缘数据中心的部署和管理方面的这种差异会影响谁可以成为服务提供商，例如在MEC中，只有电信运营商才能成为MEC提供商，因为他们拥有部署边缘数据中心的移动网络基础设施。相比之下，在雾计算和MCC中，任何用户（从公司到精通技术的最终用户）都可以部署自己的雾节点和MCC节点。另一个明显区别是策划应用程序的部署。由于MEC服务器由电信运营商控制并托管在其基础设施中，因此第三方服务提供商可以与运营商密切合作并开发MEC特定服务，然后可以对这些服务进行广泛测试，并可能以定制方式集成。雾计算也是如此，因为某些雾节点可以部署在ISP基础设施（例如路由器和网关）中。最后有一些范式提供了一些其他范例不考虑的特定服务，例如MCC提供对与虚拟化无关的分布式执行机制的支持，可以允许在受约束设备上执行MapReduce并行算法。

1.2.2任务调度研究现状

近年来，任务图调度问题受到了学界的广泛关注，其中以有向无环图的研究最为普遍和深入。Yu-Kwong Kwok和Ishfaq Ahmad[23]在1996年提出一个有效的将任务图分派到多处理器的方法——动态关键路径调度算法（DCP），此算法定义了动态关键路径，并定义了动态关键路径上节点的最早开始时间和最晚开始时间，通过调度动态缩短关键路径的长度。[24]中，作者提出了一种考虑应用缓冲区排队状态和空闲处理器的一维搜索算法，以最小化延迟。在[25]中，作者提出了一个应用在基于雾计算的车联网实时交通管理系统中的调度算法，首先建立了一个分布式的城市范围的交通管理系统，其中靠近路边单元的车辆可以作为雾节点，然后根据排队论建立停泊车雾节点模型，移动的基于车辆的雾节点可以被建模为M/M/1队列，并开发了一种近似方法，将其分解为两个子问题，并在不同的雾节点之间调度交通流。上述文章只考虑了单用户的全任务卸载。在[26]中，Wael Labidi等人设计了一种联合优化每个用户的调度和计算卸载策略，综合考虑到能耗和时延。尽管如此，但上述的文章只考虑了将全部任务都放在本地执行或者全部任务卸载到云端执行，并没有考虑到服务器和本地的并行调度。

在[27]中，作者考虑了一个车载网络整体的调度，包括服务器和本地的并行调度，并在[23]的基础上提出了非固定开始时间算法（UST），增强了任务的可调度性，除此之外这篇文章的贡献还在于为解决调度冲突提出了偏移值调整重调度算法（ROM）和回溯优先级算法（BPP）。在[28]中，作者针对多用户分区问题（MCPP），设计了一个离线启发式算法，根据云上资源的状况，最小化所有用户的任务平均完成时间。显然这是一个离线的预调度算法，其无法远测即将到来的动态环境，无法应用到动态场景。在线调度策略可以在一定程度上缓解静态调度由于预调度带来的问题。在[29]中，作者提出了一种称为自适应调度算法（ASA）的在线动态弹性调度算法，在多轮中将任务分配给空闲处理器以防止任何不利的决定，避免某些关键任务的低效分配以使处理器变慢。在[30]中，Choudhury等人设计了一种用于多处理器的任务图的混合调度方法，该算法基于当前时间的调度动态执行列表调度。然而上述研究并没有考虑任务属性和处理器的动态性。

1.3 研究内容及组织结构

本文研究的是移动边缘计算中的计算卸载问题，并设计了一个动态迭代调度算法（IDCP），其中涉及到有向无环图以及调度的相关知识。本算法借鉴了贪婪算法的思想，并设计了调度工作集动态调度工作集上的节点，最后实现动态地缩小调度长度。最后通过实验评估了该算法的性能表现。

根据研究内容，本文行文的具体安排如下：

第一章：绪论；本章介绍了移动边缘计算的发展背景以及本课题的研究意义，分析了MEC以及任务调度的研究现状，以及对不同的云计算范式进行了对比。

第二章：算法原理；本章介绍了算法设计的相关原理，包括有向无环图的相关原理以及调度的相关原理。

第三章：算法设计；本章主要讲述了算法设计的过程，包括节点的选择、工作集的设计以及贪婪算法的设计等，最后给出了IDCP算法，并分析了其特点。

第四章：性能评估；本章介绍了算法的性能评估过程，在IntelliJ IDEA平台，运用JAVA语言编写的代码对IDCP算法进行了性能分析。实验验证主要分为迭代次数、DAG节点数量以及与其他算法的对比三部分。

第五章：总结与展望；本章对本文所研究的内容进行了总结并指出了本文的不足和尚待改进的地方，对相关领域的发展做出了展望。

第2章 算法原理

本章介绍了IDCP算法设计的背景知识，在2.1节介绍了有向无环图（DAG）的相关知识，包括DAG的定义、数学属性及图的遍历；在2.2节介绍了调度的相关知识，包括静态调度和动态调度。

2.1 DAG

2.1.1 DAG的定义

在图论中，DAG是一个没有环的有向图，通常包含有限的节点和边，每条边从一个节点出发到另一个节点结束，因此在DAG中不存在从一个节点出发经过一系列边和节点再回到该节点的路径。同样地，DAG是一个有向图，它具有拓扑顺序，一个节点序列，使得每一条边在序列中都是由前到后定向的。有向图的拓扑排序是将其节点排序为一个序列，这样对于每个边，边的起始节点在序列中出现的时间早于边的结束节点。具有拓扑顺序的图不能有任何循环，因为到循环最早节点的边必须以错误的方式定向。因此，具有拓扑排序的每个图都是非循环的。相反，每个有向无环图至少有一个拓扑序。因此，这个属性可以用作有向非循环图的另一个定义：它们正是具有拓扑顺序的图。如图2.1所示，为一个无权有向无环图。

图2.1 无权有向无环图

2.1.2 DAG的数学属性

有向无环图具有一些特定的数学属性。可达性在DAG中可形式化为节点的偏序。在这个偏序中，当DAG中存在一条从节点u到节点v的有向路径时，节点u和v排序为。然而，不同的DAG可以产生相同的可达性关系和相同的偏序，例如有两条边和的DAG与有三条边，和的DAG具有相同的可达性关系，它们具有相同的偏序，节点的排序都为。DAG的传递闭包性是可以表示相同的可达性并且拥有最多边的图。DAG的传递减少性是表示与G相同的可达性关系并且具有最小边的图。它是DAG的子图，由丢弃边形成，对于它，DAG还包含连接相同两个节点的较长路径。与传递闭包一样，传递约简也是为DAG唯一定义的。相反，对于非循环的有向图，可以有多个子图具有相同的可达性关系。DAG的这些独特的数学属性可应用在调度、数据处理等方面。

一个并行的任务可以通过一个DAG表示，例如，其中V节点的集合，E是边的几何。在并行任务图中，一个节点表示一个任务即一系列必须在同一个处理器处理的指令集合。和每个节点相关的是计算成本，也称为节点权值，物理意义为节点任务的执行时间。在并行任务图中，边代表交流的信息和节点之间的优先级限制，和每条边相关的数字代表从一个节点到另一个节点交流数据需要的时间，这个数字叫做边的交流成本，用表示。这里，下标ij表示有向边从源节点指向目标节点。这里源节点和目标节点分别称为父母节点和孩子节点。在一个任务图中，一个没有任何父母节点的节点为入口节点，一个没有任何孩子节点的节点为出口节点。节点任务要在收集到父母节点所有信息的情况下才能开始执行，这是DAG的优先级限制。

2.1.3 DAG的遍历

DAG的遍历定义为是从图中的任一节点出发，对图中的所有节点访问一次且只访问一次。DAG的遍历是DAG的一种基本操作，DAG的许多其它操作都是建立在遍历操作的基础之上的。DAG的遍历算法目前主要分为深度优先搜索（Depth-first Search，DFS）和广度优先搜素（Broad-first Search，BFS）两种。