基于遗传算法的边缘计算任务调度新方案

abstract

随着智能电网和全球能源互联技术的不断演进，大量智能终端接入电网，可作为边缘节点提供资源服务。传统云计算可用于在电网中提供存储服务和任务计算服务，但面临资源瓶颈、时延、网络带宽资源受限等挑战。边缘计算是云计算的有效补充，因为它可以为用户提供低延迟的本地计算服务。但是，由于单个边缘节点的资源有限，需要将资源密集型任务划分为多个子任务，然后通过资源协作分配给不同的边缘节点。使任务调度更有效是一个重要的问题。本文基于边缘计算的概念提出了一种两层资源管理方案。此外，基于遗传算法，提出了一种新的任务调度算法GA-EC(Genetic Algorithm for Edge Computing)，可以根据不同的调度目标动态调度任务。仿真结果表明，该算法对能耗和负载均衡有有益的效果，减少了时延。

1 Background 研究现状

随着智能电网和通信技术的快速发展,海量电力设备接入网络，电力服务用户日益增多。云能够存储大量数据并处理具有可扩展性、灵活性和安全性的计算密集型任务。云计算可以通过数据存储、容灾、智能用电、仿真分析等方式为电网提供支撑。云平台可以整合电网中不同系统的数据和资源并进行管理，实现智能电网中数据和资源的共享。为了保证电力云计算系统的有效性和稳定运行，必须实现合理的资源管理和任务调度。

云资源管理已经有很多研究。在节能研究中，[9]中的作者提出了一种方案，可以通过降低处理器速度来实现虚拟集群中的节能。 [10]中的作者提出了一种动态资源分配方法，可以根据实际需求调整资源节点的数量。为了降低将低分辨率视频转换为高分辨率的计算复杂度，同时最大限度地减少与移动客户端相关的计算和额外通信成本，中的作者研究了通过将计算任务卸载到移动云计算 (MCC) 来提高视频质量环境。

研究人员针对提高资源利用率提出了一种两层资源调度方案，可以根据启发式算法实现合理的任务调度,中的作者提出了一种节能的资源调度方法，可以提供实时的云服务，时延很小。此外，遗传算法被用于云计算的许多领域，包括资源管理。

云计算用于在电力网络中提供资源存储和任务计算服务。由于云计算的传输延迟长和边缘节点的计算资源有限，本文提出了一种两层资源管理模型和一种新颖的任务调度算法来满足电力网络的要求，如图1所示。 1、在智能电网中，边缘节点可以是智能终端、能源路由器、集中器等。

下文第二部分介绍了基于边缘计算的电源管理方案，第三部分详细介绍了任务调度算法。第四部分，我们模拟了新算法与其他三种对比算法的性能。第五部分是本文的总结。

2 Power Resource Management Scheme Based on Edge Computing 基于边缘计算的电源管理方案

随着云计算的快速演进，越来越多的智能终端接入网络。传统云计算中，所有计算任务都转移到云数据中心，无法始终满足用户的实时性要求。此外，在需要同时执行大量计算任务时，传统云计算不可避免地会出现带宽瓶颈。

在电力网络的边缘，有许多设备消耗大量资源[17]。如果这些设备中的资源可以用来提供计算服务，那么云计算的能量就可以得到扩展。对于本文的资源管理模型，云服务器中的部分计算任务可以卸载到边缘设备上，本地计算任务也可以在本地边缘设备上执行。

在新的资源管理模型中，计算节点有两层。第一层包括云服务器中的分析控制节点，第二层包括边缘设备中的计算节点。第一层节点用于执行计算密集型任务和管理第二层节点，第二层节点用于执行本地计算任务。因此，第二层节点中的资源应该由第一层节点统一调度。资源管理模型可应用于供电服务指挥系统、大数据平台、热点定位等多种应用场景。

在这种资源管理模型中，由于二层节点中边缘节点的资源是有限的，一些任务会被划分为子任务，由不同的边缘节点执行。因此，第二层的资源将在不同的任务之间共享和调度。

3 Introduction of Task Scheduling Algorithm in Detail 任务调度算法详细介绍

电力网络中的任务调度问题变得越来越复杂。调度算法对于提高节能性能、减少时间延迟和改善负载平衡至关重要。因此，在本文中，我们提出了一种新颖的任务调度智能优化算法。

对于本文提出的资源管理模型，边缘节点位于第二层，有限的资源会影响一些计算密集型任务的完成。因此，计算密集型任务将被划分为子任务，由不同的边缘节点执行。这使得在不同边缘节点之间分配任务成为一个关键问题。

许多学者研究了任务调度问题。例如，[18] 中提出了一种称为 DSF ACO 的任务调度算法，该算法可以在同一个调度队列中分配多个任务，以减少执行时间。该算法可以改善虚拟机资源的运行。 [19]提出的一种任务调度方法，采用质量函数的蚁群算法的信息素更新规则，通过加载标准差函数改进启发式信息模型，实现云中虚拟机的负载均衡。 [20] 中提出了一种称为 ECMM（代表 Energy-Considered Min-Min）的低功耗调度算法，但人们认为该算法可能会降低任务执行效率。 [21]中的作者提出了一种节能的资源分配算法，将高负载的应用程序迁移到新的多核服务器上，将低负载的应用程序迁移到现有的单核服务器上。

在第二层资源管理模型中，计算密集型任务将被划分为多个子任务，边缘节点通过相互协作来执行子任务。在本文中，我们提出了一种基于遗传算法的任务调度算法，以实现不同边缘节点之间的资源共享和任务分配。

3.1 Mathematical Model 数学模型

本节介绍任务调度算法的计算模型和流程图。对于本文，边缘节点数为n，任务数为m。边缘节点的集合是 R={R1,R2。 .里。 . .,Rn}，任务集为 T={T1,T2。 . .Tj . 。，Tm值}。任务调度的目的是根据调度目标函数为任务分配合适的边缘节点。

能耗计算模型

能耗计算模型

3.2 算法介绍

4 Simulations

在基于边缘计算概念的新资源管理模型中，我们提出了一种基于遗传算法的任务调度算法。在本节中，我们将模拟新算法的性能。不失一般性，所有数据均为10次实验的平均值。信道增益值 hUPi = l−τn , a n d τ = 4, ln ∈ [0, 50]。其他参数列在表中。 1、我们设置了一些对比方法来验证新算法的有效性。

5 Conclusion

Task Scheduling for Edge Computing with Agile VNFs On-Demand Service Model toward 5G and Beyond

Abstract

随着互联网的快速发展，满足服务请求、有效分配计算资源、提供服务按需应用的需求不断增加。边缘计算用于满足低延迟、网络连接和本地数据处理要求，并减轻云中的工作量。本文提出了一种基于网关的边缘计算服务模型，以减少数据传输的延迟和往返云的网络带宽。通过轻量级虚拟化技术Docker，调整边缘网关的任务调度，实现按需计算资源分配。边缘网关还可以处理本地网络中的服务请求。所提出的边缘计算服务模型不仅消除了传统云服务模型的计算负担，而且提高了边缘计算节点的运行效率。该模型还可用于 5G 及以后的云边缘计算环境中的各种创新应用。

1 Introduction

云计算、移动宽带网络、物联网（IoT）的快速发展，伴随着对网络资源分配、数据处理和服务管理的巨大需求，不可避免地改变了传统的网络基础设施。软件定义网络 (SDN) 和网络功能虚拟化 (NFV) 技术不仅将网络基础设施从复杂的物理实体转变为虚拟和可编程节点，而且还为信息和通信技术 (ICT) 的发展带来了重大变化 [1 , 2]。

NFV 代表了电信基础设施部署方式的核心结构变化 [3]。如图1所示，NFV旨在解决与网络设备资源分配相关的问题。具体来说，NFV 使用虚拟化技术将位于数据中心、网络节点和客户端设备 (CPE) 上的不同类型的设备（包括路由器、交换机、防火墙和入侵检测系统）集成到标准或通用硬件中设备。这样，NFV可以有效降低网络物理设备的采购成本和相关的网络维护成本。作为 NFV 的逻辑结果，虚拟网络功能 (VNF) 是以前由专有的专用硬件执行的虚拟化任务。 VNF 将单个网络功能从专用硬件设备转移到在商品硬件上运行的软件。同时，NFV 将网络功能从专有硬件设备中分离出来，通过使用软件来运行它们，并随后加速服务创新和配置，尤其是在服务提供商环境中。 NFV的出现有利于软件运营的网络，而不是物理设备运营的网络，增强了各个网络服务功能的灵活性和快速部署。 SDN是另一种用于解决传统网络刚性问题，满足多样化和动态网络服务需求的技术[4]。

SDN的主要目的是解决传统网络架构中网络分为控制平面和数据平面的局限性。软件通过集中控制的方式将网络管理权限授予控制平面上的软件控制器，从而重新安排网络架构。这样，这种从现有网络架构中抽离出来，转变为可编程网络的控制方式，有效地解决了传统网络设计的局限性。使用单个逻辑点控制整个网络，可以实现网络的集中控制和灵活运行。 SDN 和 NFV 是在数据传输和电信基础设施环境下，可以相互协同，引领网络设计的改造、部署和管理的网络技术。这些技术的融合也为互联网的未来发展指明了方向，尤其是在5G技术出现之后[5, 6]。

随着网络变得越来越灵活、软件定义和虚拟化，一些标准组织正在努力将 SDN/NFV 技术引入移动网络，以满足 5G/IoT 网络对数据处理和信息传输的低延迟要求，并间接驱动边缘计算技术的发展[7-9]。边缘计算是一种分布式计算架构，它将应用程序、数据和服务的计算能力从云数据中心服务器转移到靠近待处理用户网络边缘的 CPE [10-12]。网关是一种 CPE 和通用边缘计算设备，具有计算、分析和预处理在主机和其他物联网设备附近收集的数据的基本能力，以加速数据处理并减少传输延迟 [13, 14] .在基于网关的边缘网络架构中，数据在其源头附近进行计算和处理，从而使该架构适用于处理即时服务请求。

边缘计算的概念如图 2 所示。边缘网络位于物联网设备和云之间 [15]。边缘计算将现有的云计算范式扩展到网络边缘，以满足延迟关键和计算密集型物联网应用的需求。边缘计算节点的分布式架构满足了从云数据中心到CPE或微数据中心的多种应用、数据和服务的计算需求。根据不同的发展领域，边缘计算网络可以分为cloudlet、移动边缘计算（MEC）和雾计算[16-18]。 Cloudlet 是一种通信工具，它为用户周围的网络提供微服务，并虚拟化和缩小计算资源，以将计算资源部署在用户端附近。目前，Akamai 和 Microsoft 正在推广 cloudlets 的应用服务和技术。 MEC 由欧洲电信标准协会（ETSI）推出，在移动通信领域具有高度应用性，由通信公司运营和管理[19]。该技术主要旨在减轻网络设备日益增长的压力，帮助移动公司打造独特的移动服务模式。由 Cisco 推出，目前由 OpenFog Consortium Alliance 推动，雾计算是扩展云计算的概念，专注于本地网络的数据处理功能[20]。通过强调近场数据通信，雾计算可用于不同的网络设备，用于个人或企业管理，以及在特定领域提供相关的物联网服务。 OpenFog Consortium 旨在通过开发一种能够识别某些核心技术和能力的开放架构来推广 OpenFog 计算技术，例如分布式计算、网络和存储，为物联网边缘提供智能支持。顺应当前技术融合趋势，OpenFog还与ETSI工业规范组合作，为ICT的规范和互操作建立应用框架和开发技术，扩大边缘计算的应用范围。

5G技术的出现，增加了对传统集中式云计算架构的数据移动、数据存储、数据处理、数据分析等方面的要求，从而增加了提高核心网承载能力和网络承载能力所需的硬件设备数量。服务器。鉴于物联网产生的大量数据，现有的云服务模式无法满足用户大而分散的需求。该模型已用于数据计算、分析和处理。然而，对低延迟和即时性的需求逐渐增加，从而使该模型略显不足。边缘计算的引入有助于提前处理数据，减少数据流量和传输时间；该技术还允许将计算能力转移到 CPE 或终端节点，以增强边缘操作对环境的即时反馈 [21]。思科互联网业务解决方案集团 [22] 预测，到 2020 年物联网将拥有超过 500 亿个终端和设备，而国际数据公司估计未来超过 40% 的数据需要分析、处理和存储在网络边缘[23]。为了有效应对上述变化带来的挑战，必须重新定义网络边缘的服务模型，优化网络运行和服务处理效率，减少云端的工作量，满足网络的时延要求。 5G物联网。本文的其余部分安排如下。第二部分介绍了研究背景和相关工作。第 3 节描述了边缘计算服务模型的设计。第 4 节介绍了实验结果。第 5 节总结了本文。

网络运营商必须部署各种类型的网络设备和软件平台，以支持日益多样化的互联网需求。然而，目前的网络设计是基于硬件概念的，各种硬件设备往往不兼容或无法相互通信，网络维护管理复杂度高，成本高。最近提出了 NFV 作为网络运营商面临的困难的解决方案。通过NFV，网络和通信运营商可以降低相关成本，灵活高效地处理客户网络部署需求，减少硬件资源浪费，提高资源利用效率。当前的NFV相关标准主要由ETSI驱动。鉴于网络功能虚拟化带来的影响和好处，运营商——尤其是网络服务提供商和电信运营商——被认为是 NFV 标准开发中最积极的参与者。

如图 3 所示，管理程序和容器是 VNF [24] 的两个主要框架。 Hypervisor是最常见的虚拟化技术，它使用一组虚拟化硬件设备以虚拟的方式执行宿主操作系统，并抽象出宿主操作系统的物理硬件。虚拟机（VM）是部署在虚拟管理程序上的操作系统，而Linux容器（LXC）是操作系统级的虚拟化技术，主要将应用服务系统封装成一个软件容器，存储应用服务的代码软件、所需的操作系统核心和库。作为其最吸引人的特点，LXC 具有简化的软件结构。因此，容器的镜像文件只包含了一小部分比一般VM小的操作系统组件，它是一个完整的操作系统。鉴于其体积小、重量轻的特点，与 VM 相比，容器的部署或移动速度要快得多。因此，大多数行业从业者更喜欢容器而不是 VM。 Docker 是一个基于 LXC 技术 [25] 的开源项目，在 Linux 操作系统上运行。该技术创建了一个额外的软件抽象层，用于虚拟化服务应用程序以响应微服务的开发 [26]。 Docker 除了作为 Git Hub 社区的著名产品外，还受到了 Google 和 Red Hat 的青睐，是目前发展最快的 NFV 虚拟化技术。还进行了许多研究来检验 Docker 作为边缘计算平台的实现

虚拟化技术的发展推动了物联网架构的多项创新。边缘计算也作为一个新概念出现，满足了物联网对分布式数据处理和设备数量的要求。边缘网关等 CPE 设备使用虚拟化技术提供本地操作，特别适用于具有低延迟和即时性的 IoT 应用程序。边缘计算可以将原本由云数据中心处理的大规模服务完全拆解，将这些服务切割成小而易管理的部分，分布在边缘网络节点或微数据中心，以加速其分辨率，减少云中的工作负载。在这种情况下，用户的服务请求在边缘网络的网关上进行处理，而超出计算能力或边缘网络无法处理的请求被转发到边缘网络。减少发送回云端的数据量。这些数据最初在边缘节点进行处理，然后在将它们传输回云端之前进行预处理或过滤，以确保仅传输有用的数据。边缘计算不仅可以降低网络连接时延，满足5G/IoT改善时延的需求，还可以促进ICT行业技术的融合。使用轻量级虚拟技术还可以帮助网络运营商在边缘网关上安装应用程序和控制软件，提供本地化服务，并创建创新的服务模式。参考文献 [29] 提出了一种基于 SDN 的边缘计算架构，称为软件定义基础架构（SDI），它使用 OpenFlow 和 OpenStack 将服务资源虚拟化，用于在可以灵活调度网络资源的虚拟基础架构上构建智能应用程序。为了引入资源共享的概念，[30] 提出了一种云-边缘框架，其中每个边缘节点可以使用本地处理平台共享计算资源，以减少处理数据的云端的计算负担，并提高边缘网络的运行。为了满足移动网络的低延迟和快速数据处理要求，[12] 检查了移动边缘操作，确定了不同 MEC 的适用情况和参考场景，并提出了 MEC 卸载决策、计算资源分配和移动管理的边际。互联网的计算需求也可以作为检验边缘网络服务管理和应用创新的参考。

考虑到本地网关硬件的资源限制（如 CPU、内存和网络密集型服务请求），处理用户服务请求的任务调度机制对于提高边缘计算的服务能力具有重要作用。计算机系统中提供了几种任务调度算法[31]。还对云计算的几种任务调度算法进行了深入研究[32, 33]。参考文献[34]提出了一种称为HealthEdge的任务调度方法，它根据收集到的人体健康数据为不同的任务设置不同的处理优先级，并确定一个任务是必须在本地设备上运行还是在远程云上运行，以减少总处理量尽可能多的时间。参考文献[35]采用马尔可夫决策过程方法来解决MEC系统中的随机优化问题。在这种方法中，计算任务是根据任务缓冲区的排队状态、本地处理单元的执行状态和传输单元的状态来调度的。参考文献[36]提出了一种贪婪的最佳可用性（GBA）机制来识别理想化的任务调度策略，并通过根据任务完成时间调度任务来减少服务的排队时间。参考文献[37]分析了循环（RR）算法在云计算环境中的性能，揭示了RR调度通过使用时间片的方法在相同优先级的任务之间公平地分配计算资源。结果表明，与其他算法相比，RR算法表现出更好的响应时间和负载平衡。

3 Problem Definition

NFV 是目前最有价值的解决与网络服务的运营成本和效率相关的问题的解决方案。因此，许多ICT公司已经开始研究虚拟化技术。尽管对该技术寄予厚望，但满足服务请求、有效分配虚拟计算资源、提供服务按需应用等仍然对 NFV 的部署提出挑战，并在 5G/IoT 服务的未来发展中发挥关键作用。 NFV还允许基于共同的底层网络资源建立多个独立的、异构的虚拟网络，从而使服务提供商能够根据用户的需求提供定制化的服务。虚拟网络嵌入是根据基础设施提供商当前的资源情况，通过映射算法将虚拟网络映射到底层网络（底层网络）的过程。这个过程是一个 NPHard 问题，已经在 NFV 资源分配研究中进行了调查 [38, 39]。以往的研究[40, 41]也系统地讨论了虚拟网络映射问题，为研究提供了很好的参考。

本文旨在通过使用提出的边缘计算服务模式来优化任务调度和资源分配。与云计算相比，S c h e d u l i n g t a s k s i n e d g e c o m p u t i n g a r e m o r e c o m p l e x。边缘计算操作通常分布在客户端设备、边缘网关上，有时还分布在云网络的代理上。因此，决定在哪里安排计算任务仍然是边缘计算中的一个关键问题。鉴于目前基于网关的物联网架构是主流，本文讨论的任务调度机制主要集中在边缘网关。在可用计算资源有限的情况下，调度和资源分配是该网关要解决的主要问题。轻量级 NFV 技术在开发过程中发挥着不可或缺的作用。主机服务请求的任务调度和资源分配之间的关系如图 4 所示。由于每个服务请求到达的时间不同，所需的 VNF 服务和处理时间也不同。边缘网关可以根据服务请求之间的差异，调整任务调度和资源配置。作为服务按需模型的基本思想，只有一个 VNF 专用于单个服务请求。这个服务模型问题可以用排队论来分析，把request和react处理看成一个排队系统，把排队系统的输入看成服务请求，把服务计数器看成网关调度函数，输出为请求的 VNF 资源。尽管许多队列模型可用于运营管理 [42]，但本文主要关注任务调度方法，该方法允许某个边缘网关一个接一个地处理队列中的多个 VNF。由于容量有限，边缘网关只能调度有限数量的服务请求，而后续的服务请求需要转发到云端进行处理。考虑到这些，研究问题制定如下。假设服务请求是一个边缘网关内的泊松比，服务时间是指数分布。服务请求集可以表示为 푅 = {푅1, 푅2, 푅3, . . . , 푅푛}, w h e r e n 表示系统中的服务请求数。等式 (1) 和 (2) 用于确定系统中 n 个服务请求的概率。在这些等式中，N表示网关中可以调度的最大服务请求数，휆是单位时间内平均传入的用户请求数，휇是服务效率（服务计数器的能力），휌 = 휆/휇 为单位时间内可以满足请求的比率，P0表示初始条件，L表示计划时间内到达系统的服务请求总数，퐿푞表示服务器总数在系统中排队的请求。 L 和 퐿푞 可以分别使用 (3) 和 (4) 计算。等式（5）计算系统中服务的等待和服务时间，而（6）计算푊푞或用户请求的平均等待时间。

4 Design of the Edge Computing Service Model

如何构建弹性且高性价比的边缘计算服务模型，提高管理效率，满足用户服务需求，实现集中管理，开发灵活配置的服务模型，是当前5G SDN/NFV网络发展的研究趋势。本文提出了一种基于网关的边缘计算服务模型（图5），以提高边缘计算节点的运行效率，加速用户服务请求的处理，提高有限数量计算资源的利用效率。在该模型中，当不同的用户请求进入边缘网关时，该网关决定所请求的服务是否可以被处理。如果边缘网关本身缺乏计算能力或资源，则控制器将服务请求转发到云端，以减少数据处理延迟。

提出的边缘计算服务模型可以分为资源估计、调度器和轻量级VNF配置。图 6 展示了所提出的边缘计算服务模型中的操作流程图，这三个部分将在以下部分中进一步描述。
资源估计检查边缘网关是否有足够的计算资源来提供边缘计算服务。对于用户请求集R，资源分配必须遵守以下规则，边缘网关方式也使用这些规则

5 Experiment

进行了实验以评估所提出的任务调度算法并测试其在部署轻量级 VNF 中的性能。实验环境如图 7 所示。最初进行模拟，通过改变服务需求的数量来评估算法的任务调度性能。服务请求是
仿真评估了服务请求对不同调度机制的平均等待时间、平均响应时间和任务调度的影响。 FCFS基于进入边缘网关排队系统的服务请求，按照这些请求的先后顺序调度任务。优先级任务调度是一种不公平的调度算法，服务请求按照优先级进行排序，优先执行高优先级的任务。优先级相同的任务采用先进先出的调度机制进行排序。 GBA根据排队系统中服务请求的完成时间对任务进行排序。 RR算法是基于在进程调度中执行的常规RR调度。 RR调度通过使用时间片的方法（时间量子）将计算资源公平地分配给具有相同优先级的任务。

6 Conclusions

本文提出了基于网关的边缘计算服务模型和 GAF 任务调度机制，允许边缘网关在较短的平均时间内调度更多的任务。使用 VNF 配置技术提高边缘计算服务的运行效率，增加资源利用率，实现VNF的快速部署，满足服务按需请求。资源估计、任务调度和轻量级VNF配置设计相结合，提供了一个可以满足5G网络业务按需请求的一体化解决方案。仿真结果表明，所提出的 GAF 机制优于其他调度算法。同时，比较表明，在边缘网关中使用轻量级虚拟化技术比使用传统虚拟机更高效、更具竞争力。未来，我们计划研究边缘计算的多队列任务调度问题，边缘网关和云服务器之间可能的合作，以及利用SD-W AN技术实现云边缘网络的无缝运行。

Evaluation of Task Scheduling Algorithms in Heterogeneous Computing Environments
异构计算环境中 T ask 调度算法的评估

Abstract

这项工作建立了一套方法来评估异构计算上下文中任何任务调度策略的性能。我们正式陈述了混合边缘-云计算生态系统的调度模型，并对大型工作负载进行了基于仿真的实验。除了传统的云数据中心，我们还考虑由电池供电的智能手机和 Raspberry Pi 边缘设备组成的边缘数据中心。我们定义了计算资源的实际容量。一旦找到时间表，各种任务需求可以或不能通过资源容量来满足。我们建立了一个调度和评估框架，并测量了典型的调度指标，例如平均等待时间、平均周转时间、制造时间、轮询的吞吐量、最短作业优先、最小-最小和最大-最小调度方案。我们的分析和结果表明，与纯云媒体相比，最先进的独立任务调度算法在异构边缘云媒体中的数据中心的重大任务失败和非最佳资源利用方面存在性能下降。特别是对于大型任务集，由于电池电量不足或内存有限，每个调度方案都有超过 25% 的任务无法执行。

1 Introduction

执行工作负载的调度对于任何计算系统的性能都至关重要。特别是在异构计算环境中大规模处理异构大数据时，由于作业调度和资源分配的非最优以及物联网（IoT）移动性等因素，容易出现高延迟。考虑到目前智能边缘设备和物联网传感器数量空前，来自各种用例的大量异构数据不断产生 [1]。这直接转化为对延迟感知、节能计算技术的新兴需求[2]。在制定解决上述考虑的优化调度策略方面存在广泛的研究兴趣[3-5]。为了测试当前技术的性能，重要的是要有一个准确和正确评估的框架

通过对异构分布式系统任务调度领域的当前进展进行广泛的文献回顾 [6,7]，我们发现在现有调度算法（如 Min-Min 和 Max）的性能评估中迫切需要更加清晰和形式化-Min，在[8]中介绍。

我们在本文中解决的问题是对异构环境中的调度算法 Round-Robin (RR)、最短作业优先 (SJF)、Min-Min 和 Max-Min 的评估。这些算法已经在调度文献[9,10]中得到了广泛的研究，我们认为它们是评估和决定它们是否可以的合适选择异构计算的候选者。将来可以扩展这项工作以分析其他调度算法（例如，公平和容量调度、资源感知调度、遗传算法）。

我们明确定义了 CPU 和内存等云和边缘资源容量。为了实现真实的设置，我们进一步将执行工作负载的异构性定义为具有不同 CPU、内存和 I/O 要求的读取和写入任务的组合。考虑到边缘设备的某些资源容量可能不足以执行任务，我们获得的结果对前面提到的算法进行了新颖的分析。我们的分析阐明了何时可以安全地使用现有的调度算法，以及在分配任务以在低容量资源上执行时它们的性能受到多少影响。最后，我们确定需要开发考虑到上述计算约束的进一步调度算法。这是未来工作的主题。

Contributions

本文的研究贡献如下： https://github.com/roxana-stan/2HD-Scheduling-Algorithms-Evaluation-Framework

数学定义异构计算的调度模型，用于我们的性能评估；

构建一个框架（https://github.com/roxana-stan/2HD-Scheduling-AlgorithmsEvaluation-Framework，于 2021 年 8 月 15 日访问），用于评估边缘云异构环境中的调度算法。此外，作为框架的一部分，我们实施了一套全面的绩效评估指标；

通过我们的框架进行实验，根据一组指标评估最先进的调度算法的性能。我们选择了具有代表性需求和不同计算资源能力的异构任务；

根据传统调度算法的任务失败和非最优资源利用来评估性能下降。这是我们得出结论的关键，即需要开发未来的调度算法，以便在边缘云设置的背景下更好地优化低容量边缘资源的执行。

Structure

我们简要介绍了论文的概要。第 2 节概述了任务调度过程，突出了各种目标并详细说明了协作边缘-云系统中调度过程的步骤。在第 3 节中，我们从理论上定义了我们提出的异构计算环境调度模型。第 4 节解释了异构工作负载的概念并列出了可能的任务类型。在第 5 节中，我们基于一套完整的指标建立了一个评估方法，突出了实际实验的参数、假设和各种资源的配置。第 6 节介绍了不同调度算法的性能分析。我们讨论了实验结果，并在第 7 节中总结了这项研究工作的结论。

2 Task Scheduling

我们的论文评估了几种解决独立任务调度问题的技术，也称为任务袋 (BoT) 工作负载调度 [11]。给定一个由任务组成的应用程序，它们之间没有相互依赖，调度挑战包括为每个任务分配最适合其及时执行的计算资源。然而，所提出的评估方法也可以应用于工作流调度，以及具有优先约束的任务[12]。
一般来说，在计算机上优化调度任务的问题已被证明是 NP 完全的 [13]，因此有必要依赖启发式算法。

在分布式计算环境中，挑战在于是否将边缘资源或云资源分配给传入的任务。特别是，在本文中，我们考虑边缘数据中心将配备电池供电的边缘设备，例如智能手机和树莓派。
通过处理边缘数据中心内的任务，与传统云数据中心的过度消耗相比，我们可以从降低的能源利用率中受益。边缘数据中心的缺点是它们的处理能力低于云数据中心 [14]，因此，调度策略对于大小可变的任务至关重要。

Scheduling Objective
我们区分了调度策略旨在完成的几个功能：
实现高系统吞吐量；
最小化系统的响应时间；
最小化所有任务的总体完成时间。 （可选）完成工作量的最后期限（如果有）；
最大限度地降低边缘云计算服务的成本；
最大限度地减少数据中心的能源消耗；
有效利用系统资源。

Scheduling Steps

调度过程的架构如图 1 所示。在该框架中，边缘云数据中心代理负责工作负载调度，单个队列保存所有待提交执行的就绪任务。

image-20220330214351487

Scheduling Model for Heterogeneous Computing

在本节中，我们提出并正式陈述了混合计算环境中独立任务调度的模型。