基于能源互联网的边缘计算能耗感知调度

摘要

当5G网络和云平台协同服务于人们的生活时，边缘计算已得到广泛研究。边缘设备电池提供的能量有限，阻碍了其应用。本文聚焦于结合能量采集技术(EH)与能源互联网(EI)的边缘计算中的任务调度。边缘节点通过EH收集绿色能源，节点之间通过EI交换能量。能源互联网从边缘节点获取绿色能源。相较于绿色能源，我们将来自电网（非通过能量采集技术从边缘节点获取的能量）称为棕色能源。如何减少褐色能源消耗是本文最重要的问题之一。以往的研究未考察节点间的能量衰减，也未研究虚拟机(VMs)的迁移路径。本文分析了虚拟机调度，并对边缘计算中虚拟机迁移能耗、任务卸载以及绿色能量传输的能耗进行了建模。本文提出了一个启发式假设：系统中仅存在一个虚拟机，然后针对具有多个虚拟机的系统提出了三种启发式方法。仿真结果表明，所提出的基于最小能量传输衰减比的虚拟机迁移方法(METAR)在减少褐色能源消耗和总能耗方面有效，并提高了绿色能源的利用率。与能量效率问题解决方案(EE‐PRO)和最大化任务能耗调度(MTS)相比，METAR在褐色能源消耗上平均降低了28.23%和49.50%。同时，METAR在执行时间上平均减少了5.67%和11.52%。

索引术语

边缘计算，绿色计算，启发式方法算法，仿真。

一、引言

随着智能手机、无线技术[1],移动设备、在线应用[2],尤其是5G网络的出现[3],，边缘计算正变得越来越重要和普及[4]，因为它在工作、社会[5]和经济[6]等几乎所有方面都提升了人们的生活质量。边缘计算还促进了物联网[7],[8],虚拟化[9],医疗系统[10],车载网络[11],及其他行业的研究。然而，能量限制和有限的计算能力阻碍了边缘设备[6]的应用。

为了应对边缘计算的挑战，任务通过电缆和网状网络从本地节点卸载到附近的边缘节点[5]（或远程云），以提高处理能力和电池工作时间[12]。

图1展示了一个三层边缘计算框架。通过使用路由器、网关、基站和其他类型的接入点，该系统通过将本地边缘节点的部分任务卸载到具有更多能量和更高处理能力的其他边缘节点，从而提升移动边缘节点的计算能力并延长其工作时间[13]。大多数研究集中在任务应卸载到何处。然而，虚拟机迁移对边缘节点性能的影响尚不明确，因为边缘节点之间以及节点内虚拟机之间的不同路径具有不同的指标，例如带宽和能量传输衰减率（ETAR）[12]。这些指标会影响任务处理时间以及虚拟机迁移和任务处理的能耗。在本文中，我们将来自能源互联网（EI）的能量称为棕色能源。

如图1所示，绿色边缘计算框架包含三层。在第一层中，用户通过移动设备、平板、智能手机或其他设备提交任务。第二层不仅支持通信（或

在边缘节点之间不仅提高了处理能力，还通过EI技术实现它们之间的能量传输[14],[15]。第三层的边缘节点通过能量收集设备获取能量，并将工作负载卸载到外部（其他节点或远程云）更强大的系统（即云中），以延长电池寿命。EI技术使得边缘节点之间可以通过有线或无线方式进行能量传输[14],[15]。以太网供电（PoE）交换机可以同时传输数据和能量。路径的选择会影响传输过程中的绿色能源损耗，因为不同路径的能量传输衰减率（ETAR）不同。虚拟机的位置也会影响能耗。一方面，不同的虚拟机迁移路径消耗的能量不同；另一方面，任务通过不同路径传输所需的能量也不同。本论文是首次将EI技术、EH技术与边缘计算相结合的研究。

我们在论文中综合考虑了虚拟机迁移、能量传输和任务调度。任务和绿色能源通过两条规则进行调度：（1）将节点（在该节点上调度任务和绿色能源）添加到具有最小能量传输衰减比（METAR）的虚拟机；（2）将节点（在该节点上调度任务和绿色能源）添加到具有最小能耗损耗（ACL）的虚拟机。基于规则（1）和（2）的调度方法分别为METAR和ACL。我们也可以交替使用规则（1）和（2），称为ALT方法。

主要贡献如下：

• 我们将能源互联网与边缘计算相结合，以在能耗方面增强边缘计算；
• 我们对采用EI技术并包含多个虚拟机的边缘计算进行建模，并采用基于全局搜索的方法来调度任务；
• 提出了三种基于三条规则的启发式方法，以最小化褐色能源消耗。
• 对所提出的方法和其他方法的性能进行了比较。

本文的其余部分组织如下。第二节介绍了边缘计算的相关工作以及边缘计算中使用的EI技术。第三节提出了本文在绿色边缘计算中所采用的模型。第四节提供了一种全局搜索方法来调度资源和能量。第五节中，首先假设系统中只有一个虚拟机，并提出一种启发式算法来卸载任务和进行能量调度；然后，我们提出了三种当系统具有多个虚拟机时的调度启发式方法。在第六节中，通过仿真验证了所提出方法在能耗及其他方面的性能。

II. 相关工作

第二节(II(A))概述了边缘计算中的能量感知调度。第二节(II(B))介绍了边缘计算中使用的能源互联网（EI）和能量采集技术（EH technology）。第二节(II(C))给出了一个示例，以说明论文的动机。

A. 能量感知边缘计算

在边缘计算中，许多因素影响任务调度的能耗。主要有四个因素，即本地资源、远程资源、任务和网络[16]。

本地资源为本地执行的任务提供处理能力。具有高能源利用率（能量功率/计算速度）的资源通常可以降低将任务传输到其他节点或远程云的概率，从而减少能耗。

资源根据各处的能耗情况决定任务的执行位置。本地节点与远程资源之间的路径会影响输入和输出数据传输的能耗。当任务在邻近节点或远程云上执行时，其能耗还受到数据大小（输入和输出文件）和带宽的影响。例如，如果输入和输出文件较小的任务在远程资源上执行，计算能耗可能会降低（如果远程资源具有更高的能量效率）[17]。相反，若这些任务的输入和输出文件较大且执行时间较短，当在其他节点上执行时，则会增加能耗并延长执行时间。

为了节省边缘节点的能量，许多方法已被应用于边缘计算环境。任务卸载可能耗费更多时间，而在某些情况下（例如输出文件较大时）本地执行可能需要更多能量。这些方法通常试图在时间和能量之间进行权衡。张 Y. 等[18]提出了一种能量感知卸载方案，该方案在有限能量和对延迟敏感的条件下联合优化通信与计算资源分配。他们提出了一种迭代搜索算法，用于优化本地计算频率调度、信道分配、功率分配以及计算任务卸载。

崔L. 等[19]尝试在能耗与延迟之间为各类物联网应用的用户需求做出权衡。他们将多目标优化问题形式化（最小化平均能耗和平均延迟时间），并采用 NSGA‐II方法求解。这些调度方法及其他重要指标旨在最大化能量效率。孙H. 等[20]定义了计算效率，即计算的数据位数量除以相应的能耗。其调度目标是在考虑权重因子的情况下，最大化用户间计算效率之和。他们使用迭代与梯度下降法解决了该问题。王Q. 等[21]

提出了一种分布式算法，包含四个部分：时钟频率配置、传输功率分配、信道速率调度和任务卸载策略选择。他们采用任务卸载选择策略来确定任务应在何处执行，然后对本地执行的时钟频率、传输功率分配以及移动边缘计算中的队列延迟进行优化。这些方法[18]–[24]总是将能量感知调度问题建模为多目标调度问题，并利用一些方法来解决该问题。两个最重要的目标是最小化执行时间以及最小化能耗。

除了前述方法外，一些研究人员还使用其他方法解决了该问题。杨S.等[25]展示了如何在网络中部署云粒，并在不违反每个任务延迟要求的前提下，将每个请求的任务分配给云粒和公有云，以实现总能耗最小化。

数据传输在边缘计算中消耗了大量能量。刘L. 等[26]等利用局域网从用户收集数据，并通过数据压缩减少数据传输能耗。此外，发送和接收数据时的能耗有所不同。郑J.等[23]在通信与计算资源分配中同时考虑了下行链路和上行链路，并为超密集异构网络提出了一种高效的联合上下行链路任务卸载算法。赵X.等[27]采用基于预测模型的多层长短期记忆（LSTM）来预测边缘设备的流量。基于预测结果，提出了一种基于交叉熵的移动数据卸载策略，通过确定哪些用户应卸载至Wi‐Fi系统，以最大化系统吞吐量。穆罕默德Z. 等[28]提出了基于博弈论的资源管理技术，在满足用户服务质量的前提下，最小化基础设施能耗和成本。阿里B.等提出了[29]一种志愿者支持的雾计算（VSFC），旨在探索这两种分布式计算领域之间的相互作用，以降低云计算固有的通信延迟、能耗和网络使用。

B. 能量收集、能源互联网技术结合边缘计算

能量收集（EH）技术已广泛应用于边缘计算[16]。EH捕获环境中的可再生能源，包括太阳辐射、风能和人体运动能量[18]。EH具有可控性高、稳定性好等优点，有利于边缘设备[30]。毛Y.[16]研究了配备EH设备的绿色MEC系统，并提出了基于Lyapunov优化的动态计算卸载算法来解决该问题。该卸载方法考虑了执行延迟和任务失败，并在决策任务卸载时综合考虑移动端执行的CPU周期频率以及计算卸载的发射功率。旨在研究支持EH的MEC中能耗与执行延迟之间的权衡

系统，张G 等[31]研究了缓冲队列和电池电量的稳定性作为约束条件，并将任务卸载建模为移动设备能耗与执行延迟的平均加权和最小化问题。这些方法均利用能量采集技术获取绿色能源，并确保某些指标，如时间限制和能耗。在图2中，我们将来自GH1 ∼GH5的能量称为绿色能源，其他能源为棕色能源。

能量采集技术仅从外部获取绿色能源，而未考虑如何在不同设备之间进行能量传输。能源互联网（EI）能够在电网中的节点之间灵活且可定制地传输能量。在边缘计算中，部分节点可以获得绿色能源（如太阳能）。EI可在边缘设备之间传输能量，特别是向那些能量充足或系统负载较低的节点传输能量。EI为任务分配和能量调度带来了新的挑战。当某些节点拥有较多能量时，可以将其传输给其他节点；相反，某些节点则需要从其他节点获取能量。当任务被卸载到不同节点时，其消耗的能量也各不相同，这些因素为新环境下的调度带来了挑战。大多数研究集中在如何将任务从边缘设备卸载到远程云。而在新环境中，我们还需要考虑能量传输的路径选择问题。我们的目标是最大化绿色能源的利用率并减少褐色能源消耗。不同的传输路径具有不同的能量衰减比和能量损耗，路径选择直接影响能耗。为了最大化绿色能源利用率并降低褐色能源消耗，顾L.et al.[13]通过联合考虑虚拟机迁移、任务分配和绿色能源调度，研究了能量成本最小化问题，并提出了一种启发式算法来解决任务卸载与能量传输的问题。然而，他们假设系统中仅存在一个虚拟机。而在大多数实际系统中，通常存在多个虚拟机。我们尝试结合EI技术来解决任务卸载问题。本文重点研究在考虑虚拟机迁移和绿色能量传输的情况下，如何进行任务调度以最小化褐色能源消耗。

C. 示例动机

见图2。在边缘计算环境中，有五个节点（n1 ∼n5）和两个虚拟机（VM1 ∼VM 2）。每个节点都配备有一个绿色能量收集装置（GH1 ∼GH 5），可从太阳能中收集绿色能源。VM1和VM 2分别位于节点n1和n4上。部分节点之间具有直接链路连接，而其他节点则没有。例如，n2和n3彼此之间没有任何链路，但它们可以通过n1进行通信。链路上的“A”和“C”分别表示能量传输衰减率以及两节点之间的跳数。

在图2中，节点n2和n5,之间的多条路径包括：{n2,n5}、{n2, n1, n5}、{n2, n1, n3, n5}、{n2, n1, n4, n5}以及{n2, n1, n3, n4, n5}。路径{n2,n1,n5}具有能量传输最小的衰减比（1‐0.95∗0.95）。路径的选择对于虚拟机迁移、任务卸载和能量传输至关重要。不同的路径可能导致边缘节点的能量损失不同。较差的路径会增加虚拟机迁移和任务卸载的能耗。例如，任务T1从n3,提交以执行，我们可以从其他节点（n1, n4）迁移一个虚拟机，或将该任务卸载到拥有虚拟机的节点（n1, n4）。如果边缘节点收集的绿色能源不足以处理所有任务，则需要从系统外部获取能源，即棕色能源。棕色能源通常通过电网获得，并通过电缆传输。如何减少棕色能源的使用是本论文最重要的关注点之一。

III. 系统模型

本节中，我们给出了论文中使用的模型。表1列出了论文中使用的参数。图2提供了论文中使用的边缘计算环境的示例。

A. 网络模型

我们采用一个无向图G=(I, E)来表示边缘计算网络，其中包含节点集合I和网络边集合E。该系统包含N个节点和VMN个虚拟机。集合ei,j(i, j ∈I)表示节点ni与nj之间是否存在链路。如果ei,j等于1，则表示它们之间存在链路；否则，两者之间无链路。di,j表示节点ni与nj之间的距离。对于该网络，我们始终使用节点间的跳数作为各节点之间的距离。当i= j时，我们特别将距离设为0。vi是一个二进制变量，用于指示节点ni是否拥有虚拟机。eai,j表示从节点ni到nj的能量传输衰减率。

我们将系统建模为多个时隙，每个时隙具有相同的能量传输衰减值。

边缘计算环境中的能耗受以下参数影响：能量传输衰减比、绿色能源供应、任务处理能耗、任务卸载能耗以及虚拟机迁移。

表1。本文使用的符号。

B. 两个不同节点之间的能量传输衰减比

如果某个节点中的绿色能源不足以支持该节点中虚拟机的处理任务，则可以从不承载虚拟机的相对较近的节点调度绿色能源。假设绿色能源从节点ni传输到nj，我们选择经过节点集合NSi={nli,j |1 ≤ l ≤L}的路径，其中L表示节点ni与节点nj之间的总节点数。节点ni与节点nj之间能量传输的最小衰减比如下（mti,j）：

$$ mti,j = \prod(1 - mineax,y) $$ (1)

其中x= nli,j,y= nli,j + 1, 1 ≤ l ≤ L。大多数情况下，节点ni与nj之间存在多条路径，假设有K条路径。对于第k条路径，相应的能量传输最小衰减比为metki,j，则

$$ metari,j = min(metki,j |1 ≤ k ≤ K) $$ (2)

例如，在图2中，有多条路径从节点n2遍历到节点n5,,包括：{n2 ,n5}，{n2, n1, n5}，{n2, n1, n3, n5}

{n2, n1, n4, n5} 和 {n2, n1, n3, n4, n5}。路径 {n2,n1, n5} 具有能量传输的最小衰减比（1‐0.95∗0.95）。

mineax,y是从节点x到节点y的能量传输的最小衰减比。我们将eax,y视为节点x与节点y之间的距离，其值可通过迪杰斯特拉[32]弗洛伊德方法提出的方法获得。

C. 绿色能源损耗

当系统决定在不同节点之间传输绿色能源时，总是优先选择能量传输衰减率最小的路径。在第s个时隙将能量从节点ni传输到节点nj时的总绿色能源损耗为:

$$ gel(i,j)= ngi,s ∗(1 −metari,j) $$ (3)

其中，ngi,s表示在第s个时隙期间节点n上新增到达的绿色能源。

D. 任务处理能耗

处理任务的能耗包括两部分：虚拟机上处理任务的能量以及将任务（数据和代码）从提交节点移动到虚拟机的能耗。对于任务t，假设它从节点i提交并被移动到节点 j，总能耗egt(t,i,j)：

$$ egt(t,i,j)= egtp(t,j)+ \frac{egtd(t)}{1 −metari,j} $$ (4)

其中，egtp(t,j) 是在节点 j（节点上的一个虚拟机）上处理任务的能耗，而 egtd(t) 是任务t的数据在没有能量传输衰减情况下的传输能耗。

E. 虚拟机迁移能耗

对于虚拟机 v，我们假设它从节点i提交并迁移到节点j。总能耗egv(v,i,j)为:

$$ egv(v,i,j)= \frac{egvd(v)}{1 −metari,j} $$ (5)

其中egvd(v)是虚拟机从节点i迁移到节点j时，在无能量传输衰减情况下的能耗。

F. 褐色能源消耗

对于节点 j （其上有一个虚拟机），总能耗tecj的计算方式如下:

$$ tecj =∑t egt(t,i,j)+ egv(v,i,j) $$ (6)

ngi,s是第ni个节点在第s个时隙期间新到达的绿色能源。

节点j提供的能量为:

$$ pe j =∑i gel(i,j)+ngi,s $$ (7)

节点j的褐色能源消耗是:

$$ bec j = \begin{cases}
tec j −pe j & \text{if } pe j < tec j \
0 & \text{if } pe j ≥ tec j
\end{cases} $$ (8)

G. 调度任务与虚拟机迁移的综合分析

在本小节中，我们将任何节点提供的能量称为正向能量，包括上一时隙获得的绿色能源（lgi,s）和新到达的绿色能源（ngi,s）。我们将用于虚拟机迁移的能量称为负向能量（evi）。因此，Ei,s表示节点i在时隙s期间的能量，其表达式如下:

$$ Ei,s= lgi,s+ ngi,s $$ (9)

如果节点 i 上的能量传输到节点 j，则能量损失Distesi,j为

$$ Distesi,j= Ei,s ∗ metari,j $$ (10)

如果节点 i 上存在一个虚拟机，该虚拟机将迁移到节点 j，此时能耗为egvd(i)，而能量传输衰减率为零。能耗Distvsi,j是

$$ Distvsi,j= \frac{egvd(i)}{1 −metari,j} $$ (11)

由于能量传输衰减率最小的路径在能量传输和虚拟机迁移过程中始终具有最小的能量损耗，因此能量传输和虚拟机迁移可能会选择同一路由以降低能耗。如果节点 i 上不存在虚拟机，则 Distvsi,j= 0.

如果节点i上的处理任务被提交到节点j（节点j上的虚拟机），则任务处理能耗Disttsi,j为

$$ Disttsi,j= eegt(s,i,j) $$ (12)

其中，变量Distsi,j表示从节点i到节点j的能量消耗，如下所示:

$$ Distsi,j = Distesi,j + Distvsi,j + Disttsi,j $$ (13)

IV. 系统分析

在本节中，首先，我们提出了不考虑系统复杂度的调度方法。我们将该方法称为不考虑算法复杂度的卸载方法（OFFWC）。由于虚拟机迁移总是需要一定时间（1∼5分钟），我们假设在一个时隙内仅有一次虚拟机迁移的机会。该调度方法包括两个主要步骤：（1）寻找所有可能的虚拟机迁移和能量传输路径；以及（2）寻找所有可能的任务卸载方案。我们选择褐色能源消耗最小的方案。

A. 寻找所有可能的路径

系统中有VMN个虚拟机和N个边缘节点。挑战在于从VMN个不同的节点中获取分布在N个不同边缘节点上的虚拟机。迁移虚拟机的可能解决方案数量为:

$$ CVMN N = N^{VMN} $$ (14)

集合vmp[VMIM][N]用于表示虚拟机迁移后虚拟机的位置。vmp中的一行表示一种虚拟机迁移策略。在虚拟机迁移过程中，

我们总是选择能量传输衰减比最小的路径来降低能耗。根据第三节中的方法，虚拟机迁移的总能耗在集合 egmi[VMIM],中得以保留，相关的绿色能源消耗和褐色能源消耗分别为egmig[VMIM]和egmib[VMIM],。此处((1 ≤temp ≤VMIM))

$$ egmi[temp]= egmig[temp]+ egmib[temp] $$ (15)

在一个时隙内，时间太短而无法迁移虚拟机两次，因此我们在调度中只考虑一次迁移。

B. 寻找所有可能的任务卸载方案

对于时隙s，调度中有Ts个任务和VMN个虚拟机。问题是如何将Ts个任务分配到 2∗VMN个虚拟机上。我们通过能量传输衰减率的路径来分配任务，以降低能耗。

可能的分配方法数TAM为:

$$ TAM=(2 ∗ VMN)^{Ts} $$ (16)

每一行代表一种分配方法，总能耗为egt[TAM]。相关的绿色能源消耗和棕色能源消耗分别为egtg[TAM]和egtb[TAM]。此处((1 ≤temp ≤TAM))

$$ egt[temp]= egtg[temp]+ egtb[temp] $$ (17)

从第IV(A)节和第IV(B)节中，我们获得了所有可能的资源分配方案。我们有三个目标：（1）最小化总能耗，（2）最小化褐色能源消耗，以及（3）最大化总绿色能源。

$$ tar1=∑ {VMIN}^1 egmi[temp]+∑ {TAN}^1 egt[temp] $$ (18)

$$ tar2=∑ {VMIN}^1 egmib[temp]+∑ {TAN}^1 egtb[temp] $$ (19)

$$ tar3=∑ {VMIN}^1 egmig[temp]+∑ {TAN}^1 egtg[temp] $$ (20)

三个目标的权重分别为： α1、 α2和 α3。因此，目标tar是:

$$ Tar= α1 ∗ tar1+ α2 ∗ tar2 − α3 ∗ tar3 $$ (21)

我们选择Tar最小的方法。该方法的复杂度为:

$$ y O(VMIM ∗ TAM)= O(N^{VMN} ∗ VMN^{Ts}) $$ (22)

该方法的复杂度太高。因此，我们在接下来的部分中提出了三种启发式方法来降低该方法的复杂度。

V. 边缘计算中能量高效任务分配的启发式方法

在本节中，我们首先介绍当系统中只有一个虚拟机时的调度方法。然后，我们提出当存在多个虚拟机时的三种启发式调度方法。最后，我们在第V(C)节中给出了所提出的三种启发式方法的复杂度。

算法1 H‐One(v, I) // v是位于虚拟机的节点

1: mintar=+∞,tarn=空;
mintar是Tar的最小化目标值（公式21）， tarn是虚拟机迁移节点；
2: 对于 每个节点 (n) 在 I −v// 选择节点 n作为虚拟机移民目标
3: 对于 每个节点 (m) 在 I −v −n
4:如果Distmt→v< Distmt→n
5:将节点m添加到集合 A；
6: Else
7:将节点m添加到集合 B；
8: EndIF
9:结束循环
10: Tar1= Schedule(A,v);
11: Tar2= Schedule(B,n);
12:如果 mintar>(Tar1+Tar2)
13: mintar=(Tar1+Tar2);
14: tarn= n;
15:结束如果
16:结束循环

A. 边缘计算中仅有一个虚拟机的启发式方法

假设系统中只有一个虚拟机，并且位于节点 v 上。与调度相关的两个主要问题是：（1）选择哪个节点作为虚拟机的迁移目标节点？（2）应如何将任务和能量调度到虚拟机的初始节点和迁移目标节点？这正是算法1的目标。在算法1中，我们尝试通过计算公式（21）的目标函数值来确定哪个节点应作为虚拟机的迁移目标节点。我们假设每个目标具有相同的权重，α1= α2= α3。我们通过选择在公式（21）中目标函数值最小的节点作为迁移目标节点。

首先，我们假设节点（n）被选为虚拟机的迁移目标节点（算法1第2行，下文相同）。根据两节点之间的能耗（公式22），将节点划分为两个集合：A和B。与节点v之间能耗较小的节点归入集合A，其余节点归入集合B。第10行给出了集合A中的任务在节点v上执行时的调度目标值。第11行给出了集合B中的任务在节点n上执行时的调度目标值。我们选择目标函数最小的节点（第 10∼15行）。

算法2 Schedule(X, v) // v是位于虚拟机的节点 并且X是其任务应在节点上执行的集合 节点 v；返回Tar的目标值

1：将X中的节点按Dists升序排列 x,v(x ∈ X)
2: 将任务卸载到X中的节点 v；
3：将节点X中的绿色能源传输到节点v
请4：求从系统中获取棕色能源。
5：根据公式（Tar计算目标值16）。

传输（公式2）（第3行）。如果从集合A获取的能量不足以处理集合A中的所有任务，则获取棕色能源（第4 行）。算法2返回目标函数的值（第5行）。

算法2获取当集合X中的节点上的任务在虚拟机v上执行时Tar的目标值。我们首先将集合X中的节点按照Distxs, v(x ∈ X)的升序进行排序（算法2第1行；下文相同），然后将集合X中节点的任务卸载到节点v（第2行）。同时，我们将集合X中节点的能量传输到节点v（第3行）。最后，我们获取棕色能源（第4行）以及目标值Tar的值（第5行）。

基于能源互联网的边缘计算能耗感知调度

B. 边缘计算中多个虚拟机的启发式方法

算法1假设系统中只有一个虚拟机。然而，系统中存在多个虚拟机。在本小节中，我们尝试解决系统中多个虚拟机的调度问题。集合V表示虚拟机所在的位置节点:

$$ V={v_{temp}|\ temp \in[1, VMN} $$ (23)

在第V(A)节中，我们给出了系统中只有一个虚拟机时的调度方法。当存在多个虚拟机时，如果我们将系统划分为多个集合，且每个集合包含一个虚拟机，则可以重复使用‘‘H‐One(v)’’来调度任务和传输能量。因此，我们的调度目标转化为如何将节点划分为多个集合。

首先，我们将每个带有虚拟机的节点作为集合的初始节点，然后根据两条规则将来自这些初始节点的剩余节点添加到相应的集合中：（1）将节点添加到具有最小能量传输衰减率（METAR）（公式2）的集合中；（2）将节点添加到具有能耗损失（ECL）（公式23）的集合中。算法3和算法4分别给出了基于规则（1）和规则（2）的启发式方法。

算法3 METAR(虚拟机数量S[temp]) // 虚拟机数量为数量 虚拟机

1: 对于每个节点vtemp在V中
2:将vtemp添加到集合S[temp]中
3: 结束
4:无虚拟机的节点集合= I − V;
5: 当无虚拟机的节点集合不为空
6: 对于 每个集合S[temp]在 S中
7: vt= vtemp; //vt是当前虚拟机所在节点
8: minmet=+∞;
9:对于 每个 节点ln在 无虚拟机的节点集合中
10:如果minmet> metarln ，vt
11: minmet= metarln,vt, seln= ln;
12:结束如果
13:结束循环
14:将节点seln添加到S[temp]
15:结束循环
16:当结束
17: 对于 每个集合S[temp]在 S中
18: H‐One(vtemp, S[temp]);
19: 结束

METAR。我们分别检查每个集合，每次每个集合都会获得一个新节点（第 6∼15行）。我们获取所有集合，并通过 Algorithm1对每个集合进行Schedule（第 17∼19行）。

算法4初始化VMN个集合（每个集合包含一个虚拟机），并通过将节点添加到具有能耗损失的集合中来向每个集合添加节点。在算法4中，第1∼3行初始创建VMN个集合，每个集合以一个虚拟机初始化，这与算法3类似。第4行获取不属于任何集合的节点。minmet表示能量传输的最小衰减比， seln是选定节点。对于每一个S[temp]属于S，如果某个节点（尚未被分配到任何集合）具有最小的ECL（第 10∼12行），则我们将该节点加入到S[temp]中（第14行）。我们单独检查每个集合，每次每个集合获得一个新节点（第 6∼15行）。我们得到所有集合，并使用算法1对每个集合进行Schedule（第 17∼19行）。

除了算法3和4之外，我们还可以通过使用两条规则交替划分集合。我们首先使用规则1（第 7∼17行）将一个节点添加到每个集合中，然后使用规则2（第 9∼29行）进行同样操作。我们重复这些步骤，直到所有节点都被分配到集合中。算法5给出了交替使用两条规则时的详细过程。

算法5 ALT (VMNS[temp]) // VMN为虚拟机数量

1: 对于 每个节点vtemp在 V中
2:将vtemp添加到集合S[temp]中；
3: End
4:无虚拟机的节点集合= I − V;
5: 当无虚拟机的节点集合不为空
6:如果检查== 0
7:对于 每个集合 S[temp]在S中
8: vt= vtemp; //vt是当前虚拟机所在的节点
9: minmet=+∞;
10:对于每个位于无虚拟机的节点集合中的节点 ln
11:如果minmet> metarln，vt
12: minmet=METAR ln,vt, seln= LN;
13: EndIf
14: EndFor
15:添加节点seln到 S[temp]
16: EndFor
17:检查= 0；
18: Else
19:对于 每个集合S[temp]在 S中
20: vt= vtemp; //vt是当前虚拟机所在节点
21: minmet=+∞;
22对于 每个 节点ln在 无虚拟机的节点集合中
23:如果minmet> Distt ln→vt
24: minmet= Distt ln→vt, seln= ln;
25: EndIf
26:结束循环
27:将节点seln添加到S[temp]
28:结束循环
29:检查= 1;
30:结束如果
31: 对于 每个集合 S[temp]在S中
32: H‐One(vtemp, S[temp]);
33: End
34:当结束

步长为2。虚拟机迁移的能量消耗是[3, 30]中的随机值。活动虚拟机的功率为50瓦，空闲虚拟机的功率为30瓦。在下一节中，所使用的仿真参数见表2，除非另有说明。

在实验中，我们考虑一个如图3所示的网络。系统中有11个节点。我们评估了虚拟机迁移能耗（ECV MI）、能量损失（EL：用于任务卸载和绿色能源传输）、总能耗（TEC）以及褐色能源（BE）在不同情况下的性能：（1）不同的任务到达率；（2）不同的绿色能源生成速率；（3）不同的能量衰减比（范围）；以及（4）不同数量的虚拟机。最重要的指标是BE（褐色能源消耗）。BE是评估这些方法性能的标准。其他指标解释了BE需求差异的原因。我们将把所提出的方法与

表2. 仿真中使用的参数。

图4. ECVMI在不同AARs下的表现。

RAD 和 NOMOV。RAD 随机选择一个节点作为虚拟机迁移目标。NOMOV 在调度中不进行虚拟机迁移。

B. 实验

1) 到达率的影响

在本节中，我们评估了不同AAR下的各种方法。我们试图确定AAR对不同调度方法各项指标的影响。图 4∼7分别展示了不同方法在ECVMI、EL、TEC,和BE方面的性能。其中，AAR以2为步长从8变化到20。

通常，所有方法在AAR增加时，在EL、TEC,和褐能方面均呈现上升趋势，而在ECVMI方面呈现下降趋势。RAD的值始终最大，其次是NOMOV、ACL、ALT和METAR。当系统具有更高的到达率时，可能会将更多任务卸载到虚拟机，从而增加EL（图5），最终导致TEC（图6）和碳排放（图7）增加。NOMOV和RAD在EL、TEC,和BG中始终具有最大值。RAD在ECVMI中的值也最大。在METAR、ACL和ALT中，METAR表现最佳，因为它始终具有最小的

碳排放的值（图7）。我们还发现，所有方法（除了ACL）随着ARR的增加均略有下降，因为额外任务更容易确定任务卸载路径和迁移虚拟机以选择较低的ETAR。ACL始终优先选择ETAR最小的路径，因此在不同的AAR下没有显著差异。与ACL、ALT、NOMOV和RAD的碳排放相比，METAR平均分别减少了0.16（e+05）、0.46（e+05）、1.38（e+05）和1.67（e+05），即分别约减少10.94%、26.30%、51.56%和56.41%。

2) 绿色能源发电速率的影响

图 8∼11展示了不同方法在ECVMI、EL、TEC,和BE方面，随不同GEGR变化的性能表现。GEGR从[0, 3]变化到[0, 7]。

对于EL、TEC,和BG，调度方法从最优到最差的顺序为METAR、ACL和ALT。BE是最重要的指标。与 NOMOV相比，RAD、METAR、ACL、ALT的BE分别平均减少了6.91 (e+04)、6.26(e+04)、5.14(e+04)和1.89 (e+04)。随着GEAR的增加，所有方法获取的绿色能源增多，从而降低了TEC和BE，并提升了EL。

3) 能量传输衰减率的影响

图 12∼15用于研究不同方法在各种能量传输衰减率下以多种指标衡量的性能。能量传输衰减率分别在[0, 0.1],[0, 0.15],[0, 0.2],[0, 0.25],[0, 0.3],[0, 0.35]和[0, 0.4],范围内变化。

通常，所有方法都通过提高ETAR来改善这四个指标，因为较高的ETAR会导致绿色能源传输和虚拟机迁移过程中的能量损耗增加，从而改善负载均衡，并最终提升其余三个指标。ECVMI、负载均衡,和TEC的下降顺序为

METAR、ACL、ALT、NOMOV 和 RAD。与 ACL、ALT、 RAD 以及 NOMOV 的BE相比，METAR 平均分别减少了 0.51(e+04)、2.51(e+04)、3.34(e+04)、9.90(e+04)。

4) 虚拟机数量的影响

图 16∼19用于评估在虚拟机数量分别为2、3和4时，四种方法在ECVMI、EL、TEC和碳排放方面的性能。与NOMOV、ECL和ALT的碳排放相比，METAR降低了0.98

(e+05)、0.02 (e+05) 和 0.31 (e+05)，平均而言。METAR 表现最佳，因为它不仅减少了迁移虚拟机的能耗，还试图降低任务卸载和绿色能源传输的能耗。

C. 所提出的方法与其他方法的比较

从第六节(C)中，我们发现METAR在AARs和GEARs不同取值下的所有指标中始终表现最佳。

ETARs以及虚拟机数量。在所有这些指标中，棕色能源是最重要的值。因此，我们将METAR的值与BE领域最先进的方法进行比较。MTS [13]是一种近似最优的启发式方法，考虑了虚拟机迁移、任务调度和能量调度。但MTS假设系统中只有一个虚拟机，我们将其扩展到多个虚拟机。我们还将EE‐PRO[36]与我们的方法进行比较。假设一个虚拟机的处理能力为[0.8, 1.2]标准机器（标准机器：8核，8G内存，1T硬盘）。任务在标准机器上的执行时间约为[1, 100]时间单位（秒）。

图 20∼23展示了在不同参数（AARs、GEARs、ETARs以及虚拟机数量）下METAR、MTS和EE‐PRO的褐色能源消耗情况。总体而言，无论参数如何变化，METAR在所有环境下的表现均最优，其次为MTS和EE‐PRO。与MTS和EE‐PRO相比，METAR的褐色能源消耗平均降低了28.23%和49.50%。

从8到20，步长为2（其他参数的三个方法也呈现相同趋势）。在三种调度方法中，METAR的AET和AWT值始终最小，其次是EE‐PRO和MTS。与MTS和EE‐PRO的 AET相比，METAR平均降低了5.67%和11.52%；与 MTS和EE‐PRO的AWT相比，METAR平均降低了9.92% 和11.31%。

D. 讨论

从上述仿真结果可以看出，AAR、GEGR 和虚拟机数量影响了这些方法的性能。所有方法在 EL、TEC 和棕色能源方面均随着 AAR 的增加而呈上升趋势，而 METAR 在各种 AAR 情况下始终表现最佳。所有方法在 ECVMI 上表现出稳定的性能，并随着 GEGR 的提高，在 EL、TEC, 和 BE 上略有上升。其原因是这五种方法需要进行绿色能量传输并损失更多能量（图9），从而增加了 TEC 和 BE。我们还发现，NOMOV 的表现优于 RAD，因为随机任务卸载和虚拟机迁移会浪费更多的绿色能源，并需要更多的虚拟机迁移能量。其他方法则智能地选择绿色能量传输

为了在调度中保持指标稳定。从GEGR的角度来看，METAR在四个指标上表现最佳。所有方法的EL、TEC,和BE均随虚拟机数量增加而上升，而ECVMI则下降，因为更多的虚拟机会提高每种方法选择具有较低 ETAR的能量传输路径（绿色能源）和虚拟机迁移路径的可能性，从而降低EL。

我们还将METAR与MTS和EE‐PRO进行了比较。我们还发现，在所有测试条件下，METAR消耗的棕色能源最少。METAR表现更优的原因在于其同时关注提高绿色能源利用率，并选择能量传输衰减率较小的路径。我们选择ETAR值最小的路径用于绿色能源传输、虚拟机迁移和任务卸载。在确定虚拟机迁移目标、能量传输路径和任务卸载路径后，可以通过启发式算法（算法1 和算法2）在较小范围内搜索可能的方案，从而获得相对较好的调度结果。

VII. 结论与未来工作

在本文中，我们讨论了在具有EI技术的移动环境中遇到的问题。我们提出了三种任务调度和虚拟机迁移的方法：METAR、ACL和ALT。通过考虑四个参数和四个指标，利用仿真对这些方法进行评估。这四个参数是（1）不同的任务到达率；（2）不同的绿色能源生成率；（3）不同的能量传输衰减比（范围）；以及（4）不同数量的虚拟机。我们在四个指标上进行了比较：ECVMI、EL、TEC和BE。仿真结果表明，METAR在减少棕色能源使用方面优于其他方法。因此，在传输能量和迁移虚拟机时，优先选择ETAR最小的路径，能够降低总能耗，并使其他指标（如平均等待时间、平均执行时间）保持良好性能。此外，我们将METAR与MTS和 EE‐PRO进行比较，仿真结果表明，METAR在BE、 AWT和AET方面表现出良好的性能。

如果我们能够利用一些气象模型[37]来预测绿色能源，这可能会有助于边缘设备的调度。整合技术[38]也可用于在我们的环境中降低能耗，这将成为本论文的一项新研究。边缘计算已广泛应用于气象站、环境监测设备和医疗保健设备等多个领域。我们也希望在特定领域对这些方法进行评估并开展进一步的研究。