基于5G边缘计算的智能电网高性价比任务调度

张少军，金 燊，于 佳

(1.国网冀北电力有限公司信息通信分公司，北京100053；2.南瑞集团有限公司，江苏 南京 210003)

0 引言

智能电网中的电力数据信息量是巨大的、高度异构的，如何有效地分析和处理这些数据是智能电网面临的挑战之一[1]。5G带来的大带宽、广连接、低时延促进了边缘计算技术的进一步发展，通过在智能电网中引入5G边缘计算可以很好地解决上述问题[2]。文献[3]将边缘计算引入智能电网，提出了智能电网中实时监控服务的边缘计算框架，并进一步建立了最小化框架连接时延的边缘调度策略问题。文献[4]提出了一种基于云-雾的智能电网资源管理模型，并且使用一些负载平衡策略来处理智能电网消费需求；文献[5]在智能电网中提出了一种使用雾节点来进行数据处理的通信系统；文献[6]提出了一个任务调度和资源管理策略，以最大限度地减少雾计算系统中的任务完成时间；文献[7]提出了一种动态计算卸载策略，以最小化带有能量收集设备的贪婪移动边缘计算系统的执行成本。在这些工作中，边缘计算中的任务调度和资源管理问题得到了很好的研究。然而，在智能电网环境中，针对在边缘服务器上执行任务的成本缺乏研究。因此，本文研究了智能电网场景下边缘计算系统任务调度的成本，在完成任务需求的同时，最大限度地降低成本[8]。

1 系统模型

1.1 基于边缘计算系统的智能电网通信网络

智能电网通过集成先进技术，为传统电网增加信息流，打造自动高效的能源传输网络[9]。为了实现多路电力数据的实时采集和网络的控制，智能电网部署了大量的物联网设备，如传感器、摄像机等[10]。它们可以收集不同类型的数据，是智能电网中信息流的来源。然而，由于资源和功能的限制，物联网设备无法对数据进行实时分析和处理，这需要智能电网通信网络中强大的存储和计算资源[11]。基于边缘计算系统的智能电网通信网络系统模型如图1所示。

图1 系统模型Fig.1 System model

边缘计算将服务器部署在靠近数据源的地方，以便在附近提供服务[12]。通常，边缘计算系统由控制器和多个异构边缘服务器组成[13]。控制器具有所有可用资源的全局概述，并与每个部署的服务器通信[14]。每个服务器都可以运行几台虚拟机来对智能电网网络中物联网设备卸载的数据进行分析和处理。

对于从物联网设备卸载的每个任务，控制器将根据其资源需求选择可用的服务器进行处理[15]。本文研究了任务调度，以尽量减少维护边缘服务正常运行的成本。

1.2 任务建模和优化目标

为了解决智能电网中的边缘计算系统任务调度问题，本文首先对物联网设备和可用边缘服务器上卸载的输入任务进行建模[16];然后，列出了任务调度问题的资源约束，并提出了一个统一的优化框架。

1.2.1 任务模型和服务器模型

在边缘计算系统中，考虑一组延迟敏感任务T={t1,t2,…,tn}，其中n是输入任务的总数。每个任务由ti={di,wi,δi,si}表示，其中di表示任务ti的传输数据大小,它包括由服务器计算的输入数据和返回的输出数据,wi表示ti的计算工作量，δi表示任务ti的截止时间要求，si表示ti的存储要求。

在边缘计算系统中有m个异构边缘服务器E={e1,e2,…,em}，每个服务器由ej={Bj,Vj,Rj,Sj}表示，其中Bj表示执行任务调度策略时服务器ej与控制器之间的可用通信带宽。在每个服务器上部署一组VM，每个VM只能同时处理一个计算任务。设Vj是部署在服务器ej上VM 的数量，Sj表示服务器ej的可用存储资源。用Rj表示服务器ej上VM的计算速率，每个VM的计算速率相等。当系统进行任务调度时，可以动态调整每个VM所占用的带宽[17]。

此外，将bij表示任务ti计划到服务器ej进行处理时的带宽需求，Cj表示服务器ej处于开启状态时的每秒成本。定义二进制变量xij来表示任务ti是否被调度到服务器ej，当任务ti被调度到服务器ej时，xij=1，否则xij=0。

由于边缘计算系统计算能力足够强，可以处理所有电网任务请求，而任务ti只能由一个服务器处理。

(1)

在任务调度过程中，服务器存储空间溢出将丢失任务数据，而每个服务器的存储能力受限。因此，服务器ej上所有任务的存储需求要小于它的可用存储资源：

(2)

由于部署在服务器上的VM有限，因此调度到服务器ej的任务数要小于它部署的VM数：

(3)

1.2.2 性能分析

由于智能电网的卸载任务时延受限，任务总时延包括：任务ti从控制器到服务器ej的输入数据传输时间、任务计算时间以及输出数据返回传输时间。

(4)

对于每一个任务ti调度到服务器ej处理时，这三部分时间用以下公式来计算：

(5)

(6)

(7)

(8)

代入式(4)，

(9)

如果任务ti被调度到服务器ej，通过求解式(9)可以得到：

(10)

为了减少边缘计算系统成本，考虑所有任务在它们截止时间前准确完成，那么在控制器和服务器间的任务ti所需的带宽为：

(11)

调度到服务器ej上的任务总带宽要小于它的可用通信带宽：

(12)

1.2.3 成本最小化优化问题

在边缘计算系统中，由于控制器与每个边缘服务器通信，对于处于开启状态的服务器，维持该服务器的正常运行需要一定的成本[18]。例如，控制器需要消耗资源来管理正在运行的服务器，而运行状态的服务器将消耗大量的能量。让Cj表示边缘计算系统在服务器ej处于开启状态下的开销。本文将边缘计算系统的成本定义为服务器开启状态下的总成本。

下面用一个二进制变量yj来表示服务器ej的状态：

在本文基于边缘计算系统的智能电网通信网络中，控制器负责向不同的服务器调度任务。分配到任务的服务器即处于开启状态，需要计算成本。本文任务调度策略的优化目标是最小化边缘计算系统的成本[8]。 综上所述，边缘计算系统的成本最小化优化问题可以表述如下：

(13)

s.t.

(14)

(15)

(16)

(17)

2 算法设计

由于本文提出的成本优化问题是NP-hard的，因此不可能在多项式时间中得到最优解[19]。本文提出一种基于贪心策略的启发式任务调度算法来解决上述成本最优问题。算法包括两个阶段，在第一阶段得到初步的任务调度策略，在第二阶段优化之前的策略并得到最终策略。本文所提具体算法分析如下：

任务调度到不同的服务器成本也不一样，本文所设计的算法目的是最小化边缘计算系统的成本，选择单位成本uj最小的服务器，不失一般性，不同服务器的单位成本也不同。

(18)

式中，zj表示服务器ej的大小：

(19)

(20)

其中，

(21)

式中，pt*j表示调度到服务器ej的所有任务需要的资源。由于最后选择的服务器将有大量可用资源，所以将单位成本最小的服务器任务调度到最终选定的服务器。本算法可以提高成本最高的服务器利用率，并且可以减少成本较小的服务器造成的不必要成本。

综上所述，本文基于贪心策略的启发式任务调度算法如算法1所示。

算法的输入是需要进行调度的任务集和可供选择的边缘服务器集。在第一行，首先初始化优化问题中的二进制决策变量xij和yj。

在第一阶段，当单位成本等于根据式(18)和式(19)算出的值时，按照uj以及Cj从小到大的顺序对边缘服务器进行排序。从算法的第5～16步，根据服务器的资源需求和可用资源选择服务器来处理计划外的任务。在第6步，选择可用服务器集E中有着最小单位成本的服务器ej。如果所选服务器的可用资源能够满足计划外任务集T中某些任务的资源需求则选择要放入服务器ej的最大任务(第7～14步)。否则，服务器ej从可用服务器集E中删除(第15行)。最大的任务ti可以根据式(21)和式(22)在第8步上得到，然后将任务ti从计划外的任务集删除，并且将tij，yj设为1(第10～12步),然后将服务器ej添加到使用服务器集U中。

在第二阶段，首先获得U中成本最小的最后选择的服务器eg1和eg2。如果服务器eg1中的可用资源能满足服务器eg2中任务ti的资源需求i，重新将任务ti输入服务器eg1并更新任务调度变量(第19～27步)。当服务器eg2中的任务都被删除时，它将从U中删除并更新状态，然后从U获得成本最小的新服务器(第22～25步)。

下面分析基于贪心策略的启发式任务调度算法的时间复杂度。算法的第一阶段包括两部分：选择服务器和向服务器调度任务。第一部分选择服务器的时间复杂度至少为O(mlog(m))，第二部分有n个任务需要调度。考虑被选服务器满足所有未调度任务资源需求的最差情况，算法需要n时间计算点积和选择最大任务。在此情况下，第二部分至少花n2时间。因此算法第一阶段的最差时间复杂度为O(mlog(m))+n2。第二阶段在最差情况下将需要n-1时间。因此本文基于贪心策略的启发式任务调度算法最差时间复杂度为O(mlog(m))+n2。

3 仿真分析

本节对求解成本优化问题的算法进行性能评估，比较输入任务数量、传输数据大小和延迟要求对所提算法成本的影响，经过与能量感知资源调度策略(EARS)[20]和随机调度策略(RANDOM)仿真结果对比，表明本文所提算法的有效性与性能改进良好。本文算法在不同输入任务数量下的性能比较如图2所示。

图2 不同输入任务数量下算法的性能Fig.2 Performance of the algorithm under different input tasks

输入任务的传输数据大小设置为50 MB，将输入任务的数量由20更改为200，增量为20。将本文所提算法的性能与RANDOM算法和EARS算法进行了比较，当输入任务数量增加时，边缘计算系统的成本也随之增加，原因是更多的服务器参与了任务卸载。如图2所示，本文算法平均可以降低RANDOM算法50%的成本，原因是增加了每个使用服务器的资源利用率。在这种情况下，开启状态下的服务器数量将减少。与EARS算法相比，随着任务数量的增加，本算法与EARS算法之间的差距变小，最终趋于一致。输入任务的不同传输数据大小对本文所提基于贪心策略的启发式任务调度算法、EARS算法以及RANDOM算法性能的影响如图3所示。

图3 不同输入任务传输数据量下算法的性能Fig.3 Performance of the algorithm for different input tasks

设置输入任务数为150，传输任务数据量以5 MB的增量从15 MB增加到50 MB。结果表明，在本文所提算法下，传输任务数据量的增加，边缘计算系统的成本也随之增加。

但是在图3中，任务传输数据量小于25 MB时，成本保持不变，其原因在于每个服务器上部署多个VM，此时任务传输数据量很小，服务器上的资源利用率(包括带宽和存储容量)不高。随着任务传输数据量继续增加，服务器资源利用率达到上限，需要增加服务器，成本也就增加了[8]。

此外，图3中RANDOM算法成本维持稳定，原因是RANDOM算法对任务处理时采用随机调度的方式，并未充分利用服务器的资源。当传输数据量增大时，服务器资源利用率提高了，但总成本保持不变。本文所提算法可以平均降低RANDOM算法30%的成本，降低EARS算法50%的成本。算法在不同的输入任务延迟要求下的性能评估如图4所示。

图4 不同减少率下算法的性能Fig.4 Performance of the algorithm at different reduction rates

定义一个包括7个任务的任务集，其中任务的传输数据大小从20～50 MB不等，增量为5 MB。使用 15个任务集作为输入任务，每个任务的延迟要求设置为γ/α，其中γ是初始延迟，α是减少率，将α从1改为2，增量为0.1，并绘制了3种算法得到的边缘计算系统的成本。随着减少率α的增加，所提算法和EARS算法获得的成本将增加，RANDOM策略的成本基本没有变化，这是因为较小的延迟意味着需要更大的传输带宽，这导致需要更多的服务器来处理输入任务。结果表明，本文基于贪心策略的启发式任务调度算法平均可以降低RANDOM算法45%的成本，降低EARS算法40%的成本。

4 结论

本文探讨了基于5G边缘计算的智能电网任务调度的成本优化问题，首先提出了一个带边缘计算系统的智能电网通信网络模型，接着在同时满足所有输入任务QoS要求下提出一个优化问题以最小化边缘计算系统的成本，然后提出了一种基于贪心策略的启发式任务调度算法用于求解成本优化问题。仿真结果表明，与RANDOM算法和EARS算法相比，所提算法在降低系统成本方面有所改进。