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

孙毅，常少南，陈恺，崔强，沈维捷

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

0 引言

电工装备建造质量是决定能源互联网可靠安全运行的重要因素[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所示，由一个电力中心云平台与个边缘物联代理 (edge computing device, ECD)组 成，云中心编号为0。ECD之间的服务范围互不重叠，为范围内的电工装备生产供应商提供计算服务，每个供应商配置一个通信终端，记供应商通信终端集合记为（以下简称为终端）。另外，ECD还可充当中继节点将计算任务转发到邻近一跳内的其他ECD或更上层云平台上完成计算。

图1 面向电工装备智慧供应链的云边协同网络模型Fig. 1 The cloud-edge collaborative network model for EIP

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

1.1 服务功能缓存模型

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

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

1.3 电力业务数据计算模型

ECD可用计算资源有限，需要为计算任务合理分配计算能力完成处理。设第个ECD的计算资源由CPU工作频率表示， fi=fk·χ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)，表示为

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

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

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

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

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

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

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

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

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

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

而在实际情况下，采用分支定界法求解式（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所示的仿真网络场景，其中存在 Kmax=6个ECD，在各ECD的覆盖范围中用户数目服从为 λIk=20的泊松分布，每个ECD的覆盖范围互不重叠，各ECD通过光纤链路相连并构成如图1所示的LAN通信网架，每个终端在很短的时间内仅生成一个业务计算需求，其中业务数据服从λs=0.5Mb的指数分布。涉及的电工物联业务功能有类，包括智能监造、智能量测、产能分析，区块链订单智能交易等功能，分别对应的电力APP服务功能数据规模服从 s′∈[0.5,2]Mbit的均匀分布。在本文仿真中，为简化计算，假设所有ECD具有相同的缓存容量，记 C =15 Mbit，忍耐系数 τ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种情况时的服务成本和用户不满意度，分析得到所提优化策略能实现服务商收益以及通信时延的优化。

综上，本文提出的基于主从博弈的联合服务缓存与任务卸载优化策略有助于解决服务缓存容量有限情况下的任务卸载决策问题，具有较好的适应性和经济性。但是在本文研究中只选取服务成本和任务时延两个指标对任务卸载的结果进行评价，之后的研究中可以针对更多评价指标展开研究。