【精彩论文】面向电工智慧物联的服务缓存和计算卸载策略

面向电工智慧物联的服务缓存和计算卸载策略

孙毅¹, 常少南¹, 陈恺¹, 崔强², 沈维捷³

（1. 华北电力大学 电气与电子工程学院，北京 102206; 2. 国网物资有限公司，北京 100120; 3. 国网上海市电力公司，上海 200122）

摘要：海量数据接入对电工装备智慧物联发起挑战，亟须边缘计算协助数据实时处理。现有工作重点研究了任务卸载技术在工业互联网场景的应用，未充分关注服务缓存对任务卸载策略的影响。针对上述问题，提出了面向电工装备智慧物联场景的联合服务缓存与任务卸载策略。针对供应商与服务提供商的收益冲突问题，以供应商数据处理时延最小化为目标，研究与证明了计算服务提供商与供应商之间的主从博弈以及纳什均衡点的存在，提出结合粒子群的广义Benders分解算法实现问题求解。仿真结果表明，所提策略有效提高了任务处理效率，降低了供应商的计算成本，提高了服务提供商的服务收益。

引文信息

孙毅, 常少南, 陈恺, 等. 面向电工智慧物联的服务缓存和计算卸载策略[J]. 中国电力, 2022, 55(4): 23-32, 43.

SUN Yi, CHANG Shaonan, CHEN Kai, et al. Joint service caching and computing offloading strategies for electrical equipment intelligent iot platform[J]. Electric Power, 2022, 55(4): 23-32, 43.

引言

电工装备建造质量是决定能源互联网可靠安全运行的重要因素^[1]。为了推动电工装备高质量发展，国家电网有限公司全力打造电工装备现代化“5 E一中心”供应链运作体系。截至2020年年底，电工装备智慧物联平台(electrical equipment intelligent IoT platform，EIP)在上海开展试点且已接入53家供应商，覆盖23类电网物资^[2-3]。然而EIP供需信息实时共生共享的需求难以满足，亟须技术保障EIP所需业务数据高效传输与处理。随着工业互联网发展，要求各类传感器、工业机器人的数据能够就近完成计算，以提高智能工业设备运行效率^[4-5]、故边缘计算作为新兴计算方案，在工业互联网领域得到广泛关注^[6]。传统工业互联网的任务卸载研究关注异构设备之间执行任务卸载的协调性与统一性^[7-10]，并针对完成任务所需时延、能耗等目标进行优化。如文献[8]提出了一种时延依赖-优先级感知的任务卸载策略，用于将从IoT设备生成的任务卸载到恰当的边缘计算设备完成处理。文献[9]分析了人工智能（artificial intelligence, AI）计算任务复杂性带来的高能耗问题，并提出一种面向异构任务的绿色边缘计算任务调度框架以降低AI计算能耗。EIP作为工业互联网在能源领域的延伸与重要应用实践之一^[1]，工业边缘计算架构的引入可有效解决EIP无法实现实时监造与全息画像等时延敏感型业务的低时延计算困境。而现有研究中，工业互联网的边缘计算不但需关注协调性与统一性，还需关注网络中不同主体之间的利益交互。如EIP信息设备主要由电网系统直接部署与管理，并通过智慧物联网关完成供应商及电网内外网信息交互^[11-12]，上述行为涵盖电网、供应商与第三方服务商等多个主体，部分业务计算需依赖第三方提供相关服务，因此在执行任务卸载时还需考虑供应商服务成本的优化。文献[13]为节约计算成本，提出一种基于最小成本最大流图的任务卸载算法以提高边缘节点的计算效用比。文献[14-15]分别提出一种面向边缘计算的多服务提供商算力共享平台让用户可以选择性地获取最优计算服务。上述工作均默认边缘节点缓存有全部服务功能，实际情况下边缘节点的缓存空间有限，无法部署全部计算功能，需在边缘设备中缓存重要应用服务及数据库以满足对应计算任务在边缘侧快速处理的需求。近年来，联合服务缓存与任务卸载问题开始得到关注，对服务缓存容量有限情况下的任务卸载决策进行研究，以降低任务延迟和能耗。文献[16]首次研究任务卸载和服务缓存联合优化问题。文献[17]研究联合任务缓存和任务调度问题，构建基于合作博弈的车联网服务模型，降低了整体通信时延。文献[18]研究了单服务器下的联合服务缓存与任务卸载问题并提出了基于半定松弛的优化算法，降低了求解复杂度。文献[19]研究一种基于动态规划的服务功能代码库缓存和计算卸载策略优化算法，减少任务执行延迟和用户能耗的加权总和。文献[20]在考虑用户信息不确定性前提下基于贝叶斯博弈提出一种计算收益最大化的联合服务缓存与任务卸载决策算法。文献[21]提出通信、计算和服务缓存联合优化模型，利用异步分布式强化学习优化卸载决策和资源管理方案。上述工作仅研究了单服务器多用户场景下的联合服务缓存与任务卸载，未考虑多边缘计算节点多用户场景下的服务缓存问题；并且上述工作假设缓存服务全部由同一电信运营商提供，不会存在收益冲突。在现实场景中EIP涉及的服务功能与相关数据库种类丰富且功能复杂，需要多个服务提供商提供算法库或者软件程序。针对上述问题，本文提出了面向电工装备智慧物联场景的联合服务功能缓存与任务卸载策略，涉及的工作与创新点如下。（1）针对现有工作仅研究单服务器-多用户场景下的联合服务缓存与任务卸载模型，本文提出了一种面向EIP场景的多边缘节点-多供应商-服务提供商的联合服务缓存与任务卸载模型，令边缘物联代理协同为供应商提供最优计算服务功能部署策略以及低时延计算服务。（2）针对现有工作未考虑电工装备智慧物联场景下供应商与第三方服务商服务收益与计算性价比相冲突的问题，本文提出一种基于主从博弈的联合服务缓存与任务卸载策略解决冲突问题，并得到各方收益最优时的缓存决策与卸载决策。

（3）针对传统Benders分解方法求解主问题效率低下问题，进一步提出一种结合粒子群的广义benders分解算法加速问题求解速度。

1  面向电工装备智慧供应链的云边协同网络模型

考虑一个面向电网系统与电工装备供应商（以下简称供应商）信息交互的网络场景，如图1所示，由一个电力中心云平台与 k_max 个边缘物联代理(edge computing device, ECD)组成， K=[1,k_max] ，云中心编号为0。ECD之间的服务范围互不重叠，为范围内的 i_max 电工装备生产供应商 I_k=[1,i_kmax] 提供计算服务，每个供应商配置一个通信终端，记供应商通信终端集合记为  I = {I₁,⋅⋅⋅,I_k,⋅⋅⋅,I_kmax}  （以下简称为终端）。另外，ECD还可充当中继节点将计算任务转发到邻近一跳内的其他ECD或更上层云平台上完成计算。

图1  面向电工装备智慧供应链的云边协同网络模型

Fig.1  The cloud-edge collaborative network model for EIP

假设网络计算服务提供商（以下简称服务商）在该网络场景中为供应商提供 M 种对应的计算服务，考虑到电网公司需要供应商提供相关生产信息用于开展产能分析、质量检测等业务，因此设供应商终端的计算任务只能将任务上传到ECD上完成处理。在本文中，供应商终端任务均不可继续拆分为多个子数据块来处理。设各供应商 i 有一个计算任务需要处理，计算任务属性可以由所需服务功能类型、数据规模（单位bit）和计算任务所需CPU周期（单位MHz）3种属性描述，分别表示为 u_i 、 s_i 和 h_i 。1.1  服务功能缓存模型

ECD拥有有限缓存空间 C 用于缓存第三方服务商的服务功能程序代码或者数据库，记ECD的缓存空间集合 C={c₁,⋅⋅⋅,c_kmax} 。记表示供应商 i 的计算任务是否属于类型 m ，服务 m 所需缓存空间为 s′_m ，第 k 个ECD 关于服务 m 的缓存决策向量 b_km 表示为

式（2）表示终端 i 的任务只能归属到一种服务类型。当ECD缓存服务 m 时能够为需要该类型服务功能的计算任务提供服务，否则任务需卸载到缓存了服务 m 的ECD或云中心完成计算。最后，ECD的缓存决策需满足

当第 k 个ECD 缓存服务 m 后，终端能够上传该计算任务至第 k 个ECD 完成计算，并回传处理结果至终端。

1.2  任务卸载与数据传输模型

关于终端 i 的卸载决策向量集合记为x_i∈{0,1} ，当第 k 个ECD缓存有用户 i 所需服务 m 时，终端 i 可以将计算任务卸载到第 k 个ECD完成计算，在边缘网络中的卸载决策满足

另外，终端可以选择卸载任务到本地ECD、邻近ECD以及云中心，但计算任务仅能做出一次卸载决策，卸载决策 x_i 还应满足

终端可以选择卸载任务到本地ECD、邻近一跳距离的ECD以及电工装备智慧物联云平台。第1种情况下的终端 i 只能选择处于通信范围内的ECD进行任务卸载；在第2种情况下由于终端 i 不处于第 k 个ECD服务范围内，需要本地ECD转发计算任务至第 k 个ECD。为区分终端是否处于服务范围，设终端 i 与第 k 个ECD 的关系向量记为

结合式（4），卸载至ECD产生的传输时延为

式中：1[⋅] 表示指示函数，当里边函数满足条件时取值为1，反之为0；r_ik 为终端 i 与本地ECD之间的通信速率；R_L 为ECD之间的LAN通信速率。

另外，表示关于云中心的终端 i 卸载决策，当ECD不满足卸载条件时，将任务继续上传云完成计算。因此，终端 i 执行任务卸载实际产生的传输时延表示为

式中：R₀ 为电工装备智慧物联平台数据传输速率， r_i＜R₀＜R_L 。考虑到任务处理后的计算结果所含数据远小于原任务，本文忽略结果回传产生的通信时延。

1.3  电力业务数据计算模型

ECD可用计算资源有限，需要为计算任务合理分配计算能力完成处理。设第 k 个ECD的计算资源由CPU工作频率 f_k 表示， f_i=f_k⋅χ_ik 为分配给终端 i 的计算资源，其中计算资源分配系数 χ_ik∈[0,1] ，应满足

任务计算时间与ECD的CPU工作频率有关，设终端 i 的任务所需计算时间为

2  基于供应商-服务提供商的两阶段主从博弈模型

服务商和供应商的两阶段主从博弈模型如图2所示，服务商是领导者，占主导地位，其目标为最大化边缘计算设备的服务功能使用收益，供应商终端是追随者。本文所提博弈第1阶段令各服务商宣布计算服务价格和缓存决策，第2阶段令各供应商选择卸载决策，同时网络根据卸载决策进行计算资源分配，如图2所示。

图2  服务商和供应商终端的两阶段主从博弈模型Fig.2  The two-stage Stackelberg game model for service providers and suppliers

供应商终端的目标是做出最优的卸载决策，一方面，为了保证电工装备智慧供应链的正常运行，需要尽可能地降低任务计算时延；另一方面供应商需要借用服务商的服务资源，将带来计算服务成本。供应商的目标为最小化计算资源的服务成本和任务计算总时延 R(x,b) ，表示为

式中：w 为时延加权系数；δ_m 为服务商针对服务 m 收取的服务费用^[22]， δ_m=ε_m−a_mp_m² ， p_m 为服务 m 的价格调节参数，满足 p_m＞0,1≤m≤M ， ε_m 和 a_m 为价格调节系数，满足 δ_max⩾ε_m＞0 且 a_m＞0 。终端的成本由2部分组成：服务商计算资源总价格和任务计算总时延。

服务商部署到ECD的服务功能得到供应商使用时，将带来计算服务收益，这促使服务商尽可能在边缘网络部署更多类型的服务令供应商访问，服务商的目标为最大化边缘计算设备的服务功能使用收益。一方面服务商需要保证服务收益；另一方面，为了满足电工装备智慧物联供应链建设需求，在保证任务计算时延的同时其业务通信与计算时延需要尽可能在本地ECD完成处理，若服务商未恰当部署服务功能，造成较多的计算任务需要上传电工装备智慧物联云平台进行处理，将导致网络带宽以及业务服务质量造成恶化，进而给服务商带来负收益，任务卸载到云中心造成的亏损为 δ₀ ，为一个定值。

因此，以考虑服务收益最大化为目标的联合缓存与卸载决策问题可表示为

式中：约束（3）为服务功能缓存容量约束；约束（4）表示终端只能将任务卸载到缓存有对应服务类型的ECD上；约束（9）与约束（10）分别为ECD计算资源分配限制以及分配系数与卸载变量的关系。

根据逆向归纳法原理^[22-23]，本文提出的主从博弈模型的纳什均衡点存在且唯一。由于变量 {x,b} 为0−1变量，式（14）为MIP问题，求解难度为NP-HARD，求解时间复杂度随用户以及ECD的数目以及服务功能类型的增多而呈指数上升。因此，本文将提出一种联合服务缓存和计算卸载优化算法实现问题求解。

3  基于GBD的联合服务缓存和计算卸载优化算法

由于离散变量 {x,b} 的存在，直接采用CVX工具箱求解MIP问题复杂度较高，本文采用广义Benders分解方法(general Benders decomposition, GBD)求解MIP问题^[23]。基于GBD方法的分离定理，服务商目标函数优化问题式（14）可以分解成服务缓存主问题与价格优化子问题。设在第 t 次迭代中的任务卸载决策为 计算资源分配决策为 χ^t ，缓存决策为t_b 为当前循环迭代次数，得到固定缓存决策下的价格优化子问题为

根据约束（16）~（18）得到约束矩阵 Y(b,p) 为

由于其他决策向量固定，式（15）只包含连续变量且为凹函数，故价格优化子问题式（15）可以通过内点法获取最优的价格策略 p^∗ 以及约束条件的最优拉格朗日乘子定义为 t_b 次迭代中价格优化子问题的最优值，该值为服务商目标函数优化问题上界。

在GBD方法中，主问题用于求解固定价格决策下的最优缓存决策，因此服务缓存决策问题可表达为

式中：为GBD方法引入的因子集合。服务缓存主问题与价格优化子问题可以通过交替迭代完成式（14）的求解。为了求解主问题式（20），通过带入价格优化子问题的最优价格策略并基于分支界定法对卸载决策变量进行松弛与搜索^[17]，将其重新写成混合整数规划的形式，即

式中：z_b 为引入的辅助连续变量；F_b 表示价格优化子问题的可行解集合；G_b 为不可行解集合。ϕ_ν(b) 与 Θ_γ(b,p) 分别为用于获取第 t_b−1 次迭代中服务商目标函数优化问题可行解与不可行解集合的辅助函数^[23]。在第 t_b 次迭代中式(21)的最优解为优化问题下界每一次迭代必然增加关于服务商目标函数优化问题的可行或不可行解集，因此记当前循环所需最大迭代次数 t_b 为可行集与不可行集数量的和， t_b=F_b+G_b ；为避免算法迭代次数过多，引入忍耐系数 τ_b ， τ_b>0 ，当迭代过程中上界与下界满足时该算法终止迭代，视为获取近似最优解。将主问题和子问题不断求解并迭代，进而完成服务商目标函数优化问题求解，并记第 t 次迭代中得到的决策为原问题的上界 U^t 。

同样基于GBD方法的分离定理，供应商目标函数可以分解成一个卸载决策主问题和计算。引入一个十分小的正实数 σ 来扩展计算资源分配优化子问题变量 χ 的取值范围，避免出现 χ 取值为0导致求解错误，记扩展后的变量取值范围变成设在第 t 次迭代中的缓存决策为价格策略为 p^t，任务卸载决策为其中 t_x 为当前循环迭代次数，计算资源分配子问题表示式为

根据约束式（22）~（24）得到约束矩阵为

由于卸载决策向量固定，同理计算资源分配优化子问题式（22）可以通过内点法获取最优资源分配决策 χ^∗ 以及约束条件的最优拉格朗日乘子 定义为在第 t_x 次迭代中计算资源分配优化子问题的最优值，该值为供应商目标函数优化问题的上界。由于卸载决策主问题用于求解固定资源分配决策下的最优缓存卸载决策，可将主问题表示为

式中：为GBD方法引入的因子集合。故同样可以通过主问题与子问题交替迭代完成供应商目标优化问题求解。在第 t_x 迭代中，式（26）可以重新写成式（27）的混合整数规划形式，代入通过资源分配优化子问题得到的最优资源分配变量。

式中：z_x 为引入的辅助连续变量；F_x 为资源分配优化问题的可行解集合；G_x 为不可行解集合；ϕ_α(x) 与分别为用于获取第 t_x−1 次迭代的资源分配优化问题可行解与不可行解集合的辅助函数^[23]，后两个约束用于排除不可行的卸载决策。记在第 t_x 次迭代式(27)的解为优化问题的下界 同时引入忍耐系数 τ_x＞0 ，当迭代过程中满足时当前算法终止迭代，视为获取近似最优解。并记第 t 次迭代中得到的决策为原问题的下界 D^t ，引入忍耐系数 τ＞0 ，当满足 U^t−D^t⩽τ 时终止迭代。

而在实际情况下，采用分支定界法求解式（21）和式(27)将产生高计算复杂度。因此，本文进一步提出采用二进制粒子群优化算法(particle swarm optimization, PSO)解决主问题求解^[24]，进而加速迭代过程。结合粒子群的GBD算法具体实现流程如图3所示。

图3  基于粒子群的GBD算法流程

Fig.3  Flow chart of PSO-based GBD algorithm

4  仿真分析

文章基于MATLAB R2019 a，Intel(R) Core(TM) i7-10700 F CPU @2.90 GHz以及32 GB内存环境进行。另外，本文采用CVX工具箱^[25]内嵌的内点法^[26]完成GBD方法中的涉及IP问题求解。本文考虑了一个如图1所示的仿真网络场景，其中存在 K_max=6 个ECD，在各ECD的覆盖范围中用户数目服从为的泊松分布，每个ECD的覆盖范围互不重叠，各ECD通过光纤链路相连并构成如图1所示的LAN通信网架，每个终端在很短的时间内仅生成一个业务计算需求，其中业务数据服从 λ^s=0.5Mb 的指数分布。涉及的电工物联业务功能有 M=6 类，包括智能监造、智能量测、产能分析，区块链订单智能交易等功能，分别对应的电力APP服务功能数据规模服从 s′∈[0.5,2]Mbit 的均匀分布。在本文仿真中，为简化计算，假设所有ECD具有相同的缓存容量，记 C = 15Mbit ，忍耐系数 τ_b=τ_x=τ=0.01 ，要注意的是，本文算法在ECD具有不同缓存容量的仿真场景一样适用。最后，其他仿真参数如表1所示。

表1  仿真参数设定

Table 1  Simulation parameters

在下述仿真分析中，将所提算法与固定定价的缓存与卸载算法、定制价格与热门缓存与卸载算法^[20]、定制价格与时延最优卸载算法^[27]在收益优化、网络时延以及缓存命中率3种性能指标上进行对比。图4为采用粒子群算法求解GBD分解后的整数规划主问题的收敛性分析，可以看到，当算法达到600次迭代后算法收敛，粒子群找到了在固定资源分配决策下的任务卸载与缓存决策最优解。

图4  主问题求解收敛性分析

Fig.4  Convergence analysis of main problem solution

图5展示了缓存容量变化对算法性能的影响。随着缓存容量上升，供应商计算成本、服务商的服务收益均呈近线性上升，其中本文算法通过主从博弈模型，在服务商更新缓存策略后，供应商再根据服务商提供的信息更新任务卸载策略，令供应商与服务商收益竞争达到平衡点，因此博弈双方收益相对均衡，其中供应商具有最低的服务成本并保证了服务商收益能够维持在较高值，另外，相比于其他算法，由于考虑了供应商的计算时延需求，在保障低成本开销同时具有与时延最优算法相近的时延性能。

图5  数据规模对算法收益影响分析

Fig.5  Impact analysis of the data size on algorithm revenue

4种缓存与计算模型的供应商与服务商收益变化受云计算惩罚成本影响的情况如图6所示。固定定价的缓存与决策算法的定价模式由于不受到惩罚成本变化的影响，在任何情况下均固定定价，因此随着惩罚成本上升令服务商具有更精确的缓存决策时，供应商用户能够获取更多的服务并付出更低成本，但导致供应商在大部分情况下出现亏损；而随着惩罚成本增加，本文算法能够通过主从博弈模型，动态调整供应商与服务商的卸载与缓存决策，服务商为了获得更高的计算收益，需在改变缓存决策时需要充分考虑供应商决策的变化，因此双方在博弈中达到均衡时能够实现双方共赢，获取最优时延与服务收益。

图6  ECD供应商通信终端数目变化对算法性能影响

Fig.6  Influence of the ECD supplier communication terminal number change on algorithm performance

在博弈过程中，联合服务缓存与任务卸载模型的时延性能除了受到双方博弈动作影响，还与ECD可用计算资源相关。如图7所示，在可用计算资源较少的阶段，3种模型均具有高的计算时延，这是由于不论具有多少缓存空间，计算资源不足导致了部分任务只能上传云计算层完成计算；而随着计算资源增多，服务缓存功能部署充足时，供应商能够就近在边缘获取更多计算服务用于实现实时监造与安全识别等时延敏感型业务，进而相比于另外两种模型具有更优的时延性能，而热门度优先算法仅考虑了历史情况，无法根据实际用户偏好变化决定当前时段的用户缓存需求，而固定定价由于无法为服务商带来明显收益，而导致用户卸载决策不具有可调度性，进而影响了计算性能。

图7  ECD计算资源变化对算法性能影响

Fig.7  Impact of the ECD computing resource change on algorithm performance

图8展示了3种算法的服务功能缓存命中率性能。明显地，由于本文算法能考虑实时终端计算需求，具有较好的缓存命中率，而热门度优先缓存算法仅依靠历史记录决策，无法考虑现阶段供应商终端计算任务类型的变化，而随机缓存并未考虑任何因素，具有最差的性能。

图8  缓存命中率分析

Fig.8  Analysis of cache hit ratio

5  结论

本文针对面向电工装备智慧供应链的联合服务缓存与任务卸载策略优化问题提出了一种多边缘节点-多供应商-服务提供商的联合服务缓存与任务卸载模型，基于供应商-服务提供商两阶段主从博弈模型，求解得到服务缓存容量有限情况下最优的任务卸载决策，实现了服务提供商收益和供应商终端任务成本以及时延加权的优化。最后通过算例分析验证了所提模型的有效性。主要得出以下结论。（1）通过分析与推导证明了所提的基于供应商-服务提供商的两阶段主从博弈模型存在唯一均衡解，既能降低服务成本也能降低任务时延。（2）通过提出结合粒子群的广义benders分解算法，解决传统benders分解方法求解主问题效率低下的问题。（3）通过对比仿真网络场景下，其他条件一定时，缓存容量变化、云计算惩罚成本变化、ECD可用计算资源变化3种情况时的服务成本和用户不满意度，分析得到所提优化策略能实现服务商收益以及通信时延的优化。综上，本文提出的基于主从博弈的联合服务缓存与任务卸载优化策略有助于解决服务缓存容量有限情况下的任务卸载决策问题，具有较好的适应性和经济性。但是在本文研究中只选取服务成本和任务时延两个指标对任务卸载的结果进行评价，之后的研究中可以针对更多评价指标展开研究。

（责任编辑　张重实）

作者介绍

孙毅（1972—），男，教授，从事能源互联网及其信息通信技术等研究，E-mail：[e-mail];

★

常少南（1998—），男，通信作者，硕士研究生，从事任务卸载技术研究，E-mail：[e-mail];

★

陈恺（1997—），男，博士研究生，从事云边协同及任务卸载技术研究，E-mail：[e-mail];

★

崔强（1985—），男，博士研究生，从事物资供应链管理，E-mail：[e-mail];

★

沈维捷（1965—），男，高级工程师，从事物资供应链管理，E-mail：[e-mail].

 往期回顾 

编辑：杨彪

校对：蒋东方

审核：方彤

声明

根据国家版权局最新规定，纸媒、网站、微博、微信公众号转载、摘编《中国电力》编辑部的作品，转载时要包含本微信号名称、二维码等关键信息，在文首注明《中国电力》原创。个人请按本微信原文转发、分享。欢迎大家转载分享。