电力物联网边缘计算终端部署与业务分配优化方法

2022-04-25陈元榉蔡泽祥孙宇嫣岑伯维胡凯强武志刚

南方电网技术 2022年3期

陈元榉，蔡泽祥，孙宇嫣，岑伯维，胡凯强，武志刚

(华南理工大学电力学院，广州510640)

0 引言

在电力物联网中[1]，智能设备数量巨大，待处理信息量呈爆炸式增长，有效降低边缘数据的处理延时成为目前亟需解决的问题之一[2]。目前，边缘计算技术在电力物联网中的应用存在“边-边交互”及“边-端交互”等方式[3 - 5]，且边缘计算终端(edge computing terminals，ECT)具有一定的业务处理独立性。ECT的所处位置、管控区域及其承担的业务直接影响系统数据传输特性与处理特性等[6 - 8]，故在多台ECT协同处理系统数据架构下，合理部署ECT对提高系统数据处理实时性、计算资源利用率具有重要意义。

目前，对于复杂网络中节点的划分，文献[9]提出一种利用节点连接关系确定子图的划分方法，该方法并未充分考虑节点位置差异对部署方案的影响。对于智能终端部署，文献[10]提出一种适用于电缆监测的边缘计算终端部署节点的规划方法。文献[11]提出一种云边协同模式下的电力终端控制方法，该方法结合密度和距离两个因素，采用聚类的思想部署电力终端，该方法未充分考虑终端间相互交互对终端部署的影响。文献[12]提出一种基于需求分析的云计算资源部署方法。针对任务分配，文献[13]根据用户体验质量建立雾计算场景下的模糊模型，以最大化用户体验质量为目标实现任务的分配。文献[14]介绍一种任务卸载决策算法，考虑设备有限的供电能力与任务最大允许延时较小的情况，可有效均衡设备能耗与计算任务处理时间，但未充分考虑业务间的关联关系对终端部署的影响。

多“边”协同的业务处理方式是提高边缘区域业务处理自动化的主要手段之一，ECT部署与业务分配是直接影响业务处理特性的主要原因，ECT部署时考虑其承担的业务类型的影响对提高业务处理性能具有重要意义。而上述研究均将ECT部署与业务分配当成独立的研究内容，并未充分考虑两者的相互影响对提高业务处理实时性的作用。本文提出一种电力物联网的ECT部署与业务分配方法，首先提出一种考虑业务关联的多ECT处理架构，根据业务的关联关系及业务在ECT间的分配情况，系统内ECT间的交互呈现多元结果。其次，根据系统节点分布提出ECT管控节点的划分方法，为ECT部署奠定基础。再次，建立考虑业务关联的ECT部署与业务分配的双层模型，外层模型根据内层模型的ECT部署方案求解最优的业务分配结果，内层模型根据外层的业务分配情况确定最优的ECT部署方案，通过分析内、外层模型间的相互影响以实现系统业务处理实时性的最优。最后，利用求解器CPLEX求解该双层模型的最优解，并利用算例验证了本文所提模型与方法的有效性与先进性。

1 系统模型

1.1 边缘计算终端信息处理架构

如图1所示，系统的通信拓扑结构包含数据分析设备、采集设备与指令执行终端，前者指ECT，后两者指数据节点(data points，DP)上实现数据采集与指令操作功能的物理设备。在信息处理过程中，DP的数据信息上送至ECT，ECT根据系统分配的业务实现对接收的数据的处理，并将处理结果信息与其他ECT进行通信共享，而ECT将处理指令下达至执行终端并由其完成，执行终端将处理完的结果返回ECT[15 - 16]。在上述过程中，节点间通信链路的构建取决于业务间的处理关系及信息流的传输[17 - 18]。

图1 电力物联网通信拓扑结构Fig.1 Communication topology in power Internet of Things

1.2 业务处理模型

本文考虑ECT处理的业务信息如表1所示，包括基础业务与应用服务两类，基础业务指ECT对管控范围内每个DP均需完成的处理任务，应用服务指在完成基础业务后的一些高级应用服务。本文考虑系统的应用服务的数据处理任务由一台ECT完成，故分别将每个应用服务部署于一台ECT上。基础业务与应用服务间的处理关系如图2所示，设表1中的业务处理逻辑分为并行处理与串行处理[19]，对于每台ECT需执行的基础业务均可并行处理，并将处理结果按业务处理逻辑输入至下一业务APP；对于APP3与APP4，在接收到APP2的处理结果时，可并行处理；基础业务APP实现对数据采集与预处理，APP1将采集的数据传输至APP2；将应用服务分为监测类应用服务APP与分析类服务APP，APP3与APP4在接收到APP2的处理结果时，可并行处理APP2的处理数据；APP5、APP6与其他业务为串行处理关系，APP3与APP4的处理结果输入至APP5，待APP5处理完成后，将APP3与APP4、APP5的处理结果输入至APP6，完成整个业务处理时序逻辑，做出相应的指令。

表1 系统业务的相关参数Tab.1 Related parameters of service application

图2 系统业务及其关联关系Fig.2 System services and their relationship

2 ECT部署与业务分配双层模型

数据处理延时主要来自数据传输、处理的过程，一方面ECT承担的应用服务不同将影响ECT间的数据传输特性及其本身的数据处理延时，另一方面ECT管控区域及其所处位置影响ECT承担的应用服务类型，即在系统数据处理过程中，ECT的部署位置与应用服务的分配存在耦合关系[20]。因此提出利用双层模型实现对ECT的部署以及应用服务的优化分配。其中外层模型以总处理延时最小为目标求解系统应用服务在各ECT间的分配；内层模型以传输延时最小为目标求解ECT在节点簇内的部署。

2.1 外层模型

对于内层模型中每种ECT部署方案，外层模型可计算得到一种实时性最优的应用服务分配方案，外层模型在遍历所有方案后确定总延时最小的应用服务分配方案及其对应的ECT部署情况。

1)目标函数

以优化系统数据处理延时为目标，如式(1)所示。

minDsum=Dt+Dc

(1)

式中：Dsum为处理总延时；Dt为总计算延时；Dc为总通信延时；i为数据源节点编号；a为APP编号；下标e、e′均为ECT编号，用以区分不同的ECT；tae为计算延时，表示ECTe处理APPa时产生的计算延时；die为数据源节点i与ECTe间的通信延时，dee′为ECTe与ECTe′间的通信延时。

2)计算模型

DP业务数据处理响应时间包括ECT中业务应用模型对数据的处理时间tae，该延时主要与ECT分配给该任务的处理频率及数据处理的负荷有关。在ECT内，任务处理时占用CPU资源，所需的处理时间以经过的CPU时钟周期(CPU cycle)的多少进行表征，当以单位处理频率f0处理APPa时，APPa所需的时钟周期为wa，即APPa在ECT内产生的负荷为wa。ECT根据其承担的处理业务不同，对其CPU资源进行分配，当处理任务获得的CPU资源愈多，其所需的处理时间愈少，本文以同一时刻下处理APPa的处理频率fae表征APPa获得的CPU资源。因此，可利用式(2)表征计算延时tae。在电力物联网中DP数据动态变化，导致不同业务应用APP的负荷动态变化，而在一段时间内，ECT分配给APPa的计算资源基本不变[21]。为了更好实现ECT部署与业务分配优化，提出利用单位计算延时t0对tae进行简化，t0为单位处理频率f0处理单位负荷w0时产生的计算延时，所以当fae给定时，计算延时tae为t0的倍数，其动态变化关系与wa相同。

(2)

(3)

式中：wa为ECTe处理应用服务APPa产生的负荷；fae为ECTe处理业务应用APPa时的处理频率；ζae为0- 1变量，当ECTe完成业务a的处理任务时ζae=1，反之ζae=0。表1中业务负荷wa与处理的数据量有关；Fe为ECTe所能提供的最大处理频率。

3)通信模型

数据在通信网络的传输造成传输延时与传输的数据量大小成正相关、与传输速率成负相关，所以刻画DPi与ECTe间的传输延时die如式(4)所示。本文考虑uie由多个基本数据单元u0组成，在一定数据传输速率R0下，u0在传输单位距离l0时产生的延时为d0。一般而言，节点间采用的通信方式不变，即传输速率不变，传输延时可简化为单位传输延时d0的倍数，且传输延时的变化情况与传输数据量的变化情况相同。de′e为分布式部署时ECT间的通信延时，其计算方法同die，仅将式(4)中下标i替换为另一台ECT的下标e′。

(4)

(5)

(6)

2.2 内层模型

1)目标函数

本文将ECTe管控的DP称为一个节点簇Se(节点簇与ECT采用相同的编号e)，系统各节点簇Se的并集为Ssum。在系统通信架构中，ECT与节点簇内DP及系统其他ECT间的相对位置关系直接影响节点簇的数据传输延时，据此本文提出内层模型以实现ECT于节点簇中的部署，使系统业务处理延时最小。根据外层模型中通信延时的刻画，建立内层模型的目标函数如式(7)所示。

minDc

(7)

2)节点簇划分

在内层模型中，实现节点簇内ECT的部署的前提是对DP进行划分，划分依据主要考虑ECT管控的DP数量及其位置。当DP数据处理产生的计算负荷相同时，ECT管控DP数量相同可使各计算设备间负载较均衡。故设ECTe管控的节点数为he，根据系统ECT数量K与DP数量n确定ECT管控的平均节点数量he，如式(8)所示。

(8)

式中：PInt表示整数部分；PMod表示小数部分。当PMod≠0时，系统存在[K×(1-PMod)]台ECT管控的DP数量为PInt，(K×PMod)台ECT管控的节点数为(PInt+1)。

确定节点簇内的节点数量后，本文考虑节点簇划分依据是使节点簇节点距离之和最小，如式(9)所示。式(10)所示为一个NP-hard问题[22]，故本文提出利用系统节点的分布位置关系对该NP-hard问题进行近似求解，即根据系统已知条件对上述问题进行约束，包括：1)存在与其他所有节点的相对距离之和最小的节点Vi，距离Vi较远的一些位于拓扑结构边界处的节点，仅能与其最近的若干个节点组成节点簇；2)任意选取he个节点构成节点簇，对节点簇内节点的相对距离之和的最小值进行排序得到A，选取距离之和最小的前m个节点簇，在满足式(9)的约束下，本文所求Ssum必存在于A中。此外，m的选取影响系统节点簇划分的精确性与计算速率。

(9)

(10)

式中：Lsum为各节点簇ECT与DP距离之和的最小值；Lemin为ECTe所在节点簇的ECT与DP距离之和的最小值；lie为DPi与ECTe间的距离；φ为空集；SK为第K个节点簇中所有DP构成的集合；∪、 ∩分别为集合的并、交运算。

3 模型处理与求解

3.1 其他约束条件

1)约束条件线性化

CPLEX求解器是求解线性优化问题、混合整型规划问题的常用工具，可灵活快速求解规划问题的最优解[23]，是目前求解优化问题的主要手段之一[24]，因此，本文提出利用CPLEX求解上述优化问题。在上述双层模型中，连续变量与离散变量间的乘积造成系统模型的强非线性，为利用CPLEX求解该模型，需对上述模型中非线性部分进行线性化变化[25]。利用麦考密克凸包络法实现对式(2)的taefae进行线性化，如式(11)所示。

(11)

利用方形约束实现对式(9)中lie的非线性表征进行转换[26]，如式(12)所示。

(12)

在利用CPLEX进行求解过程之前，需对系统相关参数进行设置及定义传输延时、计算延时变量及相关的中间变量。中间变量用于表示对延时变量的约束，或表示多变量的乘积。表示多变量乘积的变量需用式(11)—(13)所示的多组不等式约束进行等价替换。其次，将上述ζie与ζae设为求解变量，即为CPLEX的决策变量。

(13)

式中：下标U、L分别表示该变量的最大值、最小值，如fae,U、fae,L分别为fae的最大值、最小值。

2)延时约束条件

不同业务对数据处理实时性需求不同，利用式(14)所示的约束条件进行约束，即

(14)

式中：dea为ECTe处理APPa时产生的延时；de为ECTe处理各种APP产生的延时；da为APPa的延时容忍度。

3.2 模型求解

1)节点簇划分

针对上述NP-hard问题的约束，提出系统节点簇划分流程如图3所示，虚线框中为节点簇内的节点相对距离之和Le min的求解流程，得到节点簇Ssum。

图3 节点簇划分流程图Fig.3 Flow chart of node cluster partition

2)双层模型嵌套求解

系统业务处理成本分析过程中，需要同时考虑ECT管控的节点及其部署节点的选取，以及ECT协同处理的业务类型。在实现节点簇划分的基础上，上述双层模型等价为求解ζie与ζae，双层模型求解算法如图4所示。

图4 双层优化算法Fig.4 Bi-layer optimization algorithm

4 算例分析

4.1 参数设置

为了验证本文所提模型与方法的可行性与有效性，根据电力物联网实际运行情况，在如图1所示的某地区30节点系统中，以节点V9为参考节点，利用节点的相对位置关系，形成各节点的位置信息，令该地区ECT的数量为K=6，设每台ECT的最大处理能力为Fe=3.2 GHz；令d0=t0=20 ms；且ECT处理业务相关参数如表2所示，ECT业务处理信息流如图2所示[27 - 28]。

表2 业务应用的相关参数Tab.2 Related parameters of service application

4.2 节点簇划分

对于n节点系统而言，任意he个节点的组合存在[n!/(K×he!)]种方案，即在图1所示的30节点系统中约存在3.684×1029种ECT管控方案。本文考虑对NP-hard问题的约束条件为：1)V26与V6、V21与V3、V4与V24等绑定在同一节点簇内；2)将距离V9较远的若干个边界节点与它们最近的(he-1)个节点构成一个Ssum，并将各节点簇的节点距离之和进行排序，得到A。选取Lsum最小的组合作为系统节点簇划分依据。随后利用仿真软件确定满足式(12)所示模型的节点分簇方案，如表3所示。

表3 节点簇划分及终端部署与应用服务分配结果Tab.3 The results of node cluster partition, ECT deployment and services allocation

4.3 延时分析及终端部署与应用服务分配

针对节点传输的数据量差异，研究不同场景下业务计算时的传输延时大小，以DP数据相同时为场景1，当DP的数据波动情况不同时记为场景2～4，其中场景2中的数据相较场景1的变化率为1.67%；场景3中的数据相较场景1的变化率为27.08%；场景4中的数据相较场景1的变化率为9.58%。并将场景1中的业务数据处理延时从大到小排序，得到如图5所示的曲线，横坐标表示内层模型求解的应用服务分配方案，按场景1的业务分配方案排序方式获取其他场景的延时曲线，如图5所示。可知当DP数据动态变化时，系统完成数据处理产生的延时随应用服务的分配方案不同的变化趋势基本一致，且当DP数据一致时系统的延时曲线最低，即场景1的延时变化曲线低于场景2～4的延时变化曲线。

图5 不同场景中的总延时Fig.5 Total latency in different scenarios

以图5所示的延时最小的应用服务分配方案作为系统应用服务分配方案，如表3所示，并据此计算完成系统各业务的计算所需的延时大小，各ECT承担业务处理时产生的总延时，其结果如图6所示。图6(a)为不同场景中各业务总处理延时的变化情况，其中横坐标为业务的种类，纵坐标为延时大小，不同颜色的柱状图表示不同的场景。图6(b)为不同场景中ECT承担业务处理时产生的总延时，其中横坐标表示不同场景，纵坐标表示延时大小，不同颜色的柱状图表示不同的ECT。

一般而言，业务的负荷较大时，处理延时较大。如图6(a)中，业务5与业务6的处理延时明显高于其他业务，从而导致承担这些业务的ECT的处理延时高于其他ECT，如图6(b)中ECT5与ECT6的总延时明显高于其他ECT。但是当业务负荷相对较小，而处理的数据量较大时，总处理延时也将达到较高水平，如图6(a)中业务2的处理延时与业务5的基本一致，而业务2与业务5的负荷相差较大，即相同业务处理数据量的累积将影响业务负荷。

图6 各业务与各ECT的处理总延时Fig.6 Total latency of each service and each ECT

分别以业务与ECT为研究对象，由图6(a)计算不同场景下各业务的总处理延时，由图6(b)计算不同场景下各ECT处理其承担的业务的从延时，可以得到两者的结果相同，即可以确定图6中在不同场景下各业务总延时大小总是与各ECT处理总延时保持一致。由表2的业务参数及表3的业务分配情况，当ECT承担较多类型或数量的处理业务时，ECT的负荷较大，如ECT5与ECT6。为保证ECT5与ECT6在分别处理负荷较大的APP6与APP5时，能够满足延时要求，APP6与APP5将占用ECT的主要的CPU资源，从而导致ECT5与ECT6承担的其他业务的处理延时增加，如APP1与APP2，从而导致业务的总延时增加或ECT的处理总延时增加，如图6(a)中业务2的处理总延时高于业务3与业务4，图(b)中ECT3与ECT4的处理总延时远小于ECT5与ECT6的总处理延时。

为比较本文所提模型与方法的优势，在场景一中比较本文所提方法与其他方法如top-k[29]、K-means[30]与Random下的ECT部署与业务分配的结果，如表4所示，其中O(·)表示所用算法的复杂度的数量级运算。从表4的结果可知，Random方法下延时明显高于其他3种方法；而利用top-k与K-means方法计算出的ECT部署与业务分配结果，系统业务处理所能达到的最小延时高于本文所用方法；且基于图1所示的系统拓扑结构，本文方法的复杂度为常数阶，而top-k与K-means方法的复杂度分别为线性对数阶、线性阶。此外，top-k与K-Means方法下ECT负荷的平衡程度较本文所用方法差。