基于多智能体混合调度的电网自愈系统

王娟娟 王宏安

1(中国科学院软件研究所 北京 100190)

2(中国科学院大学 北京 100049)

(wjuanj89@126.com)

随着智能电网、信息技术和新能源技术的飞速发展，风电、光伏等可再生能源的迅速建设以及电动汽车等储能设备的快速出现，传统电网的“源-网-荷”三个固化环节正在向“源-网-荷-储”互动协调的智慧能源新型运营模型进行转变[1].能源互联网的提出，强有力地推动了新能源革命的发展.能源互联网以智能电网为基础，将不同种类的电力网络(如火电、核电、风电等)、能源网络(如天然气管网、热力管网等)、信息网络(如互联网、物联网等)、交通网络等多种类型网络进行融合，实现了多种能源形态协同转化、集中式与分布式能源协调运行的超大规模复杂网络[2].因此，能源互联网具有3个特点：

1) 弹性发电、优质供应.能源互联网需要尽可能以可再生能源替代传统能源，并以需求为向导，通过智能化管理实现按需供电、阶梯电价.

2) 多能融合、双向流动.能源互联网能够对不同形式的能源进行高效协同，将太阳能、核能、化学能与常规能源进行转换和存储，减少弃风、弃水、弃光等弃网问题，实现能源的最佳使用.

3) 高度自治、实时动态.以微网为代表的分布式发配电系统将成为电力网络的关键节点，减少了输配电能量损耗，提升冗余电力备份.同时，以电动汽车为代表的大量移动、小型储能设备的接入，使电网具有较强的供需双侧随机性变化.

可以看出，能源互联网的正常运行涉及到电力、物流、计算机网络等多种知识领域，需要极高的自动化、智能化的管理和调度系统.同时，能源互联网是多种网络的融合，必然存在“遗传”的安全漏洞.一旦遭受攻击，后果不堪设想.文献[3]已经在传统电力网络中阐述了自愈系统相关概念和主体结构.自愈系统在电网正常运行时以预防为目标，及时发现、诊断和消除故障；在电网发生故障时，进行自动修复.但该文并未提出自愈系统的具体软件设计架构和关键技术实现方式.随着电网技术的不断进步，智能电网中的自愈系统需要进一步考虑分布式发电设备、电动汽车等对电网造成影响.类似地，能源互联网新增的多种能源转换、多种网络融合及客户体验提升等需求，给其自愈系统带来了更多的挑战性，具体表现在3个方面：

1) 智能化程度要求更高.能源互联网日常运营涉及多种知识领域，其安全操作已逐步不能满足于手工操作、程序化操作.自愈系统必须内置覆盖多领域的专家系统，能够根据当前状态自动进行安全操作.

2) 安全性要求更高.能源互联网本质上是安全攸关系统[4]，不论是日常操作还是应急故障处理，都必然进行大量甚至海量的安全操作.这些安全操作将在不同的节点、不同设备上执行，并且其次序和执行时间有着严格的规定.一旦指令在错误的设备上执行、在错误的时刻执行、执行时间超长、执行次序错误都可能带来严重的故障，造成巨大的损失.

3) 实时性要求更高.能源互联网需要在广域地域内，对多种行业领域、海量个体设备进行状态监控，并通过高速网络进行信息采集和指令下发.同时，能源互联网需要对各种设备进行“开关”、“增减”、“并串”等物理操作，每一个操作都有相应的时间长度.因此，在自愈系统对突发情况进行紧急处置的时候，其自动执行修复操作序列必须根据当前的故障状态、信息网络状态、设备状态等多种状态才能形成真正有效的方案.如某个设备与自愈系统控制中心的通信链路网络拥塞，指令无法及时下发和执行，则整个修复操作序列是无效方案.

因此，在能源互联网中的自愈系统，必须能够在全局时空范围内，对网络节点、网络设备状态进行实时的状态采集，并根据物理设备的特性、地域的特性、信息网络的特性，通过智能化的专家系统综合考虑、进行决策.本文针对能源互联网和给电网自愈系统的安全需求和截止期限，给出了一套初步的解决方案.主要贡献有3点:

1) 我们提出了一种带有截止期实时约束的电网自愈系统基于多智能体进行处理的机制和可供参考的软件实现架构.在系统中加入了带有截止期约束的故障链和安全操作树，以在一个完整调度周期内求解出有效的修复解决方案，并且以总修复时间最短、持续的故障链长度最短为目标，以遍布电网中的多智能体为控制手段，对能源互联网故障进行紧急处置.

2) 针对具有实时截止期约束条件下的安全操作序列求解问题，提出了一种基于多智能体的混合关键性调度任务模型.当故障发生并将信息传递到自愈系统控制中心时，故障链节点将被激活.在其对应的安全操作树(即解决故障的操作方法集合)中，根据物理设备、网络状况、地域分布等多种特性，求解有效的安全操作序列.此后，系统会下发有效安全操作序列到关键节点中驻留的智能体代理，让这些代理去执行这些安全操作.如果在其截止期实时约束之内能够完成执行，后续可能产生的故障将被避免.

3) 本文给出了电网自愈多智能体进行混合调度的方法，给出了优化目标和约束条件，用混合整数线性规划(MILP)模型求解；并通过仿真结果验证了智能电网自愈多智能体混合关键性调度方法有效地增加了故障结点安全操作处理的成功率(平均17.74%)，并减少了故障链式的后续触发率(平均7.72%).

1 相关概念

1.1 能源互联网的基本概念

能源和环保是人类生存和发展的两大主题，也是相互影响和相互制约的矛盾.随着“雾霾”、“酸雨”等环境污染问题的不断加剧，以石油和煤炭为核心的化石能源时代必须进行改变，形成了以互联网技术为核心、以新能源和化石能源为互补的“能源互联网时代[5]”.能源互联网将以可再生能源为主要能量供应方式，通过互联网技术实现能量流与信息流实时流动，多种能源供应、传输网络及能源技术、信息技术高度耦合的新型能源利用体系[6].

可以看出，与传统电网、智能电网有所不同，能源互联网将汇聚“火电”、“水电”、“核电”、“风电”、“光伏”多种能量的相互转化，并以互联网技术为基础、以电力系统为中心，将电力系统与天然气网络、供热网络以及工业、交通、建筑系统等紧密耦合，横向实现电、气、热、可再生能源等“多源互补”，纵向实现“源-网-荷-储”各环节高度协调.可以预计，能源互联网将对电力、运输、信息[7]等诸多方面产生深远的影响.

能源互联网覆盖的地域如此之广、能源类型如此之多、网络规模如此之复杂，如何通过自动化、智能化的系统，在全网范围内构建能够快速自我修复的电网自愈系统，就变得更加重要.

1.2 能源互联网中的智能化自愈系统

自愈系统能够在日常运行过程中，实现自我控制、预防和故障恢复的功能.电网自愈系统是对电网的各个关键节点、核心设备中的运行状态进行实时的监视和测量，能够快速准确地评估当前的健康状态，选取恰当的控制策略并进行有效执行.当电网经受扰动或故障时，自愈系统将自动进行故障检测、隔离、恢复供电来进行自我修复.文献[8]提出了电网自愈控制系统分模块的设计方案及自愈时间、自愈率等评价指标.但是，该文仅仅是“记录”电网从发出警报信号到自愈完成的时间长度，并未在系统中引入与自愈修复动作相关的时间约束和次序约束.

能源互联网电网的自愈系统是在日常运行过程中能够维持能源互联网横向能源转换和纵向“源-网-荷-储”配电的正常运行，同时尽量提升可再生能源和清洁能源的能效，实现低成本运行.当发生故障时，将根据故障发生的原因找到备选的解决方案，并根据当前设备的物理状态求解出有效的安全操作序列，并进行执行.自愈系统将通过部署在全网范围的智能硬件设备和软件代理，对全网进行实时不间断监测和数据上传，并对数据进行分析，不断预测和判断当前能源互联网的运行状态，调用和能源互联网相关的一切可用资源，及时发现和排除故障.

1.3 多智能体的基本概念

由于能源互联网本身的复杂性和多知识领域相互交织，因此，仅仅采用人工的方式进行调度和修复时无法满足电网自愈的要求；同时，能源互联网还具有分布式[9]、自管理的特性，在电网发生故障时，有可能在局部上具有能够完成电网自愈的资源和能力.

多智能体系统由多个可以既彼此独立又可以相互协作的智能体组成.其中，智能体具有自治性、交互性、协作性、主动性等特点.在多智能体系统中，智能体可以根据自己的目标，结合已有的知识，规划出需要采取的行为，并通过与其他智能体的通信协商来完成某项特定的任务[10].多智能体技术可以通过智能体间协作解决单个智能体无法独立完成的复杂任务，提高了系统解决问题的能力.目前多智能体技术已经广泛应用于工业制造、交通控制、智能机器人、面向智能体软件开发等领域[11].

随着技术的发展，针对不同领域的多智能体系统越来越多，因此，用多智能体系统构建电网自愈系统在技术上是可行的，而且在智能电网中基于多智能体构建电网自愈系统已有相应的设计和实现.文献[12]考虑微网接入对配电网的影响，提出了“2-3-10”的自愈控制网络架构结构，并进行了自愈控制的仿真，能够使配电网保持在经济运行状态，并提供良好质量的电能.该文虽然给出了基于智能体的电网自愈系统软件实现架构，并引入了实时预测模块，在当前时刻对下一个时间周期的电网负荷进行预测，但是，并未考虑到在电网故障已经出现时且对修复时间有强制性要求时，如何进行快速修复.文献[13]提出了基于多智能体的智能配电网分层保护思路，并且融入了免疫算法，完成电网的自愈控制.该文的配电系统是一个网络结构，通过转为关联矩阵并进行矩阵运算，实现故障的隔离.但是，该文是通过将物理节点抽象为节点模型并进行故障识别运算的，考虑到了空间受限的问题，但未引入受限于操作时间、操作序列固定的修复动作的计算和编排.

但是，在能源互联网中这种安全攸关的领域中，电网自愈系统对操作时间的要求十分严格.一个小小的时延可能会造成重大的灾难.目前，虽然已经有不少成熟的多智能体平台被不断设计与开发，如JADE，Mobile-C，JACK等，但是这些平台并没有提供对实时的支持，无法保障电网内任务的实时约束.能源互联网的日常维护需要进行大量甚至海量的安全操作，这些安全操作将在不同地域、不同设备上执行，并且其次序和执行时间有着严格的规定.

目前，只有少数研究针对多智能体平台提出了实时性方面的改进，如设计实时多智能体平台的体系结构以优化平台内任务的响应时间、为平台中任务引入截止期属性使任务尽可能在截止期内完成等.然而这些工作都无法对任务的响应时间进行预测，也就无法保证任务的截止期约束，从而限制了多智能体平台在实时领域的应用.更进一步地，基于多智能体平台，如何实现在操作时间受限、操作序列受限的硬实时环境下进行规则调度，保证在事故截止期到达前完成全部安全操作序列，防止事故的进一步恶化是一个新的问题，并逐步成为当前实时调度领域的研究热点.

随着智能电网系统或能源互联网的日趋复杂，电网安全操作越来越涉及多知识领域的交织，本文提出电网自愈多智能体混合实时调度方法，对电网自愈过程中的安全运行和故障处理提出减少后继故障的实时性需求，要求在此过程中同时满足保证不同关键性的故障链截止期和安全操作树截止期.

2 多智能混合实时电网自愈系统的框架设计

2.1 能源互联网中对多智能体电网自愈系统的需求

图1展示了能源互联网主要运行模式，能源互联网在“源-网-荷-储”之间有着紧密的合作和衔接；同时，自愈系统在全网范围内通过物联网[14]技术，对“源-网-荷-储”系统进行实时监控，并通过遍布全网关键节点的智能体进行信息采集和设备操控.

Fig. 1 The concept of energy Internet图1 能源互联网的概念图

能源互联网的自愈系统日常运行的内容包括：

1) 多种能源的转换控制.自愈系统将通过发电厂与清洁能源进行不同时间段、不同地域的协调互补；同时，不同能源还能够通过能量转换设备进行双向转换，提升能源利用率.

2) 协调电厂并网.遍布在广泛地域的光伏、风能或类似可再生能源发电厂的发电效率和时长并不稳定，需通过与主干电网互补协作，才能在保证稳定供电的基础上，降低一次性能源消耗，提升用电效能.

3) 动态存储调度.在传统电网中，用电负荷侧被认为是固定的、具有周期性或可预测的.但是随着电动汽车、蓄电池等储能的需求，用电侧也是可以进行配置的.因此，自愈网络需要主动地对用电负荷和储能设备进行控制，引导用户主动使用可再生能源，提升用电效能.

4) 故障处理.自愈网络在发现能源互联网发生故障时，能够快速定位故障位置，诊断故障原因，执行修复方案.

Fig. 2 The architecture of self-heal system图2 自愈系统总体架构图

因此，构建能源互联网对电网自愈系统的需求满足3方面的要求：

1) 高速高效地实时监控.能够在能源互联网中涉及到的相关领域都具有足够、及时的信息收集、传递、执行的能力.如供热系统、天然气系统、电网系统、微网系统中，都需要有传感节点采集和传递信息，并且有智能软件代理接收和执行操作指令.

2) 智能化任务计算系统.能源互联网应具有高速通信网络及云端信息处理系统，能够完成大量复杂的并行任务处理，用于对全网范围内的信息进行实时处理，并计算出相应的电力维护和异常处理任务序列以完成任务.

3) 符合实际情况的硬实时操作序列推理.在日常维护(特别是故障紧急处理)过程中，自愈系统需要对各种关键设备进行诸如“开关”、“增减”、“并串”等物理操作.其中，每项操作都有相应的时间长度，并且，多项操作之间存在先后次序.因此，自愈系统必须正确计算出在当前状态下，满足一定时长、一定次序的安全操作序列，并下发给智能代理进行执行.

可以看出，能源互联网必须具有高速高效的通信网络、足够的计算能力、遍及全网的神经感知末梢硬件基础设施，通过合理的、可实现的软硬件系统，执行正确的任务序列.

本文将重点在第3节中讨论在具备以上硬件的条件下，如何实现避免后继故障的硬实时任务序列的生成和执行.

2.2 基于多智能体的电网自愈系统的整体框架

多智能体电网自愈系统由大量可计算的、驻留在关键节点的智能代理组成，系统内的智能体既彼此独立又可以相互作用.不同的智能体之间可以进行通信、交互.

图2展示了多智能体电网自愈系统的概貌，包括了横向、纵向和垂向：

1) 从横向上看，包括了不同领域内的智能体代理，如电网系统、电厂系统、微网系统、供热系统等，在每个领域内，都会有与本领域知识相关的软件系统进行管控.

2) 从纵向上看，包括了不同层次的代理，如中央级代理、区域级代理.

3) 从垂向上看，包括了不同地域的智能体代理，如不同省市、不同地区、不同小区的智能体代理.

图2给出的仅是一个参考架构，其本质上是一个自相似图形系统，在省内、市内、区县内甚至小区内都能以类似的软件架构为参考，实现分层、分级、分区域的“源-网-荷-储”互通协作.

本文的重点是提出和论证自愈系统中需要加入实时截止期约束，提出求解方法，这里并不针对每个知识领域内的智能体系统进行具体软件设计和实现.在此，仅对每种领域抽象出3类智能代理用于完成基本的功能，包括通信代理、信息采集代理和命令执行代理.

能源互联网的多智能体自愈系统日常工作可以抽象为若干任务的计算、分配、下发和执行，如图3所示.电网自愈系统包括决策和执行2个层面.决策层包括信息预处理系统、专家系统和实时截止期约束推理机.信息预处理系统用于完成信息的收集、去掉冗余信息和矛盾信息，对电网系统当前的运行状态进行定性判断.

Fig. 3 The process of self-heal system图3 自愈系统工作流程

电网自愈系统的主要工作流程包括：

1) 在能源互联网的“源-网-荷-储”中各个关键节点中部署的智能代理，通过相关传感器收集相应的信息，并上传到该分级决策系统.

2) 该级的决策系统将会先对收集的信息进行处理，去伪存真，而后判断当前电网运行状态是否正常.如果正常，将在安全操作树中计算需要执行的日常维护操作任务；如果发生故障，将在安全操作序列树中计算需要执行的日常维护操作任务.

3) 计算符合当前状态需要的任务序列，并将任务序列进行实时截止期约束下的计算.如当故障发生时，对应的故障链上的结点将被触发；推理机将根据故障结点在安全操作树求解安全操作序列，当安全操作序列的操作时间满足故障结点时间截止期时，则视为成功操作序列；若该操作序列不满足，则求解新的操作序列；若所有求解的操作序列均不能满足截止期，则视为该故障结点无法及时自动修复，后继的故障结点也将被触发.此时，将已触发故障结点和后继结点的截止期叠加，并以改截止期求解新的安全操作序列.

4) 向智能代理下发符合条件的任务序列进行执行，完成工作周期内的任务.

专家系统中包括了能源互联网涉及到的各种领域知识，我们将其抽象为3个集合：故障链集合、正常状态集合和安全操作树集合.

故障链集合是根据经验总结的可能发生或已经发生的故障状态，每一个故障状态都对应一个时间长度，在此定义为截止期，如果不能在截止期完成，将引发新的故障.不属于故障链的集合将属于正常状态.安全操作树包括了日常维护和故障处理的全部安全的任务处理序列，以有向图的方式进行存储.

任何一个故障链或正常状态链，都至少对应了一个安全操作树中的一个完整操作序列子树；当对应的智能代理完成全部操作序列后，该故障排除；如果不能在规定时间内完成，故障无法排除，并产生新的故障，故障链进入下一环节，需要完成更多的安全操作序列，如图4所示:

Fig. 4 The mapping between fault chain and security operation tree图4 故障链和安全操作树的映射

由于电网自愈系统是分级系统，在每一级中具有相应的决策系统，对该级别以下的所有区域、所有领域内的代理进行集中式协调，由该决策系统对电网自愈系统需要完成的日常维护或故障处理目标进行规划和分配.

本文将电网自愈系统的行为抽象成为电网自愈多智能体混合关键性实时调度下的实时推理系统，并通过多智能体进行任务的执行实现.

本文的先期工作在文献[15]中有所描述.该文对已有的多智能体平台AgiBuilder进行了改进，构建了原型系统，可以运算和执行硬实时调度任务.本文在此基础上，针对能源互联网，提出和设计了基于多智能体的电网自愈系统软件架构，以落实图2所示的横向(多种知识领域的融合)和纵向(多层级控制调度)电网自愈过程.

首先，在纵向上，电网自愈系统的多智能体包括设备级、小区级、中央级3种层次.在3种层次中，分别对应着不同知识领域的智能体进行相互协作和集中决策.

1) 设备级智能体，即能源互联网的核心设备中部署的智能体.具体包括产线智能体、管网智能体、转储智能体，作用有3点：

① 产线智能体.部署在电厂、微网、化工厂等能源生产场所，完成数据采集、发送和指令接收.当发生故障时,可通过专用装置隔离和消除故障，减少损失.

② 管网智能体.在多种管网中的核心装置中部署智能体，完成管线状态实时采集、管线的开关等功能.

③ 转储智能体.在储能设备和能源转化设备中部署智能体，用于完成储能、能源转化过程的监控.

在设备级智能体这一层次中，在各自领域设备中部署的智能体的设计与设备类型有关，软件内部结构各有不同，核心目标是完成对该类设备的监控.

2) 小区级智能体，即可以汇聚该区域内设备级代理回传的信息并进行处理.当小区级智能代理在收集本区域的信息后发现某个设备发生故障时，将立即进入修复过程；如果依靠本小区无法解决问题时，将会向中央级智能代理发送资源协调请求.

在小区级智能体这一层次中，各知识领域的智能体软件结构是类似的，主要的区别在于内部的操作逻辑不同；每一领域的智能体拥有该领域的知识库以及故障事件到安全操作的映射法则.

3) 中央级智能体，即在一个广泛区域内掌控较充分资源的智能体.在收到小区级智能体资源协调需求后，中央级智能体将根据相应预案进行快速资源调度，计算相关安全操作序列，并将符合时间约束条件的指令序列经由小区级智能体下发到设备级智能体进行执行.

在中央级智能体这一层次中，其软件结构与小区级智能体是类似的.两者的区别在于中央级智能体拥有了该区域内全部的知识领域智能体，并拥有更高等级、更深层次、更大力度的安全操作能力及相应的映射法则.

通过这三级智能体，并结合原有的原系统，可以实现适用于电网自愈系统的基础软件架构.但是，以上的软件体系仅仅是基础设施层的设计和实现，并未解决电网自愈系统的操作序列固定、操作时间受限的调度问题.本文第3节和第4节分别对该调度问题进行建模和求解.

3 电网自愈多智能体混合实时调度任务建模

为了实现电网自愈多智能体混合实时调度，我们基于正常状态集合、故障链集合、安全操作树和智能体建立起调度任务模型，如图5所示.

Υ={Υ(l),1≤l≤n},
Υ(l)={τi|ri,Di,Gi,{τi,j|Cij,1≤j≤ni},1≤i≤k}.
Ψ={Ψ(r),1≤h≤m},
Ψ(r)={τi,k∈G(τi),…,τj,h∈G(τj),…,τp,q∈G(τp)}.

该模型有8点内容需要说明：

1)Υ是由n个故障链Υ(l)组成的；

2) 每一条Υ(l)上有k个结点，每个结点代表了一个安全操作子图，把这个操作子图的处理过程看成一个调度任务τi,若Υ(l)上第1个结点对应的调度任务在其截止期内完成执行，则该故障链不向后传播，否则触发该故障链上的下一个结点对应的调度任务；

Fig. 5 Task model for scheduling图5 调度任务模型

3) 就绪时间ri:τi进入系统的时间，即故障触发进入安全操作树的时间；

4) 相对截止期Di:τi所允许的最大响应时间；

5) 偏序图Gi(graph):该有向图定义了组成任务τi的ni个子任务之间的偏序关系，Gi代表了安全操作树，决定了任务τi的执行流；

6) 执行时间Cij:通过最坏执行时间分析技术所预定义的子任务τij所需要执行的时间；

7) 多智能体有m类智能体给任务提供处理器资源，调度的目标是让这些智能体能成功调度Υ中的所有子任务即Ψ=Υ，同时故障链上向后触发的故障数最少；

8) 分属不同Υ(l)的子任务根据操作类型的不同，被指定给对应类别的智能体上去执行，则智能体上能执行的子任务集合记为Ψ(r).

偏序图Gi中，如果存在有向边从子任务τi,u指向子任务τi,v，则τi,v被称为τi,u的子结点直接后继，τi,u被称为τi,v的父结点直接前驱.子任务τi,j的直接前驱集合记为preddirect(τi,j)和τi,j的直接后继集合记为succdirect(τi,j).如果存在有向边路径从子任务τi,u可达子任务τi,v，则τi,v被称为τi,u的后继，τi,u则被称为τi,v的前驱.子任务τi,j的所有前驱集合记为pred(τi,j)和τi,j的所有后继集合记为succ(τi,j).没有前驱的子任务称为源结点，没有后继的子任务称为终结点.

表1中列出了每个任务∀τi(i≥1)及其对应的子任务τi,k，k∈{1,2,…,j}在调度中可以用到的参数.

Table 1 Parameters of Tasks and Sub-Tasks表1 任务及子任务的调度参数

1) 开始时间si和si,k:τi和τi,k开始执行的时间；

2) 执行时间Ci,k:通过最坏执行时间(worst-cast execution time, WCET)分析技术所预定义的τi,k所需要执行的时间；

3) 时刻t的剩余执行时间Ci(t)和Ci,k(t):Ci和Ci,k减去到时刻t为止已执行过的累积时间；

4) 完成时间fi和fi,k:τi和τi,k执行结束的时间，即Ci(t)=0和Ci,k(t)=0的时刻，fi=min{t|Ci(t)=0}，fi,k=min{t|Ci,k(t)=0}；

5) 就绪时间ri,k是其Gi上所有直接前驱结点都完成的时刻，即ri,k=max(fi,j)，τi,j=preddirect(τi,k)；

6) 响应时间Ri:τi从就绪到执行完成的时间长度，Ri=fi-ri，Ri≤Di；

7) 绝对截止期di:di=ri+Di，fi≤di；

succ(τi,k),Pi,k,l∈Pi,k；

因为EDF在调度上的最优性[16-17]，在每个智能体上使用EDF对任务进行调度.那么，Ψ(r)被EDF成功调度的充分必要条件是∀τi,k,τj,h∈Ψ(r),ri,k≤dj,h,dj,h-ri,k≥∑Cp,q(∀τp,q∈Ψ(r),ri,k≤rp,q,dp,q≤dj,h).

4 电网自愈多智能体混合实时调度方法

电网自愈多智能体混合实时调度整体过程如下：

Step1. 对安全关键的任务子集合Υcri进行调度：通过给Υcri在多智能体上分布式地给每个任务偏序图上的子任务找到一种可调度的局部截止期分配方案来确保多智能体的处理器资源可成功地调度所有的安全关键任务,并同时给剩余的其他任务留出尽可能多的空闲处理器资源；

Step2. 对其他任务Υnon-cri进行调度，重复执行Step2.1～Step2.3直至所有任务都执行完毕或没有空闲的处理器资源：

Step2.1. 任务的默认当前等级为Level1;

Step2.2. 根据其链的结构，根据当前等级的执行时间需求和截止期内来分析能否在多智能体上找到足够长的空闲处理器长度来完成执行；

Step2.3. 如果任务可被成功调度，则将该任务按当前等级准入并执行；否则，该任务进入下一个等级，转到Step2.2进行执行.

其中，Step1需通过对各子任务划分局部截止期保证其能够被成功调度.

通过给子任务τi,k分配局部截止期di,k，使所有子任务在各自的智能体上分别完成其执行需求，同时任意子任务的截止期di,k都不超过其所属任务τi的截止期di，从而Υcri中所有任务τi都能被成功调度.为此，前驱子任务不能过度使用智能体上的松弛时间而要给后继子任务留出足够的时间来完成执行.合适的局部截止期分配不仅要考虑调度任务在执行路径上的执行工作总量，还要考虑与其他任务共享的智能体上处理器资源的竞争关系.

每个智能体上的局部截止期分配方法的优化目标是最大化子任务的最小松弛时间[18-19]，为后续其他子任务留出尽可能多的松弛时间来帮助满足其所属任务总截止期的约束.同时，也要保证不同任务在该智能体上的所有子任务是可调度的.

把上述目标和约束用数学形式化表述如下：

约束条件：

② ∀τi,k,τj,h∈Ψ(r),ri,k≤dj,h,dj,h-ri,k≥∑Cp,q(∀τp,q∈Ψ(r),ri,k≤rp,q,dp,q≤dj,h).

在完成Step1后，每个多智能体将根据子任务的局部截止期，对其Ψ(r)上的子任务进行调度，其核心算法如下：

挑选Ψ(r)中局部截止期最小的τi,k去执行，di,k=min{dj,h|τj,h∈Ψ(r)}.

当Ψ(r)的子任务τi,k完成执行时，

1) 将τi,k的完成信息通知给τi,j,其中，∀τi,j∈succdirect(τi,k)∩τi,j∈Ψ(l)；

2) 把τi,k从Ψ(r)中丢弃Ψ(r)=Ψ(r)-{τi,k}；

3) 挑选Ψ(r)中局部截止期最小的子任务τp,q去执行，dp,q=min{dj,h|τj,h∈Ψ(r)}.

Ψ(l)获得τi,k的完成信息后，

1) 让τi,j就绪，τi,j∈succdirect(τi,k)∩τi,j∈Ψ(l)；

3) 如果划分局部截止期失败，采取以下步骤：

① 可借鉴文献[21]的任务丢弃处理策略，用传播的方式通知其对应智能体上的后继succ(τi,j)并将τi丢弃；

② 若是Υnon-cri中的任务，再将τi转入下一个等级分配到多智能体上.

重复上述操作直至所有任务执行完毕.

5 实验与结果

本节通过实验基于本文提出的电网自愈多智能体混合任务模型，随机生成任务测试集，对EDF简单调度和第4节调度方法下的任务成功率进行对比.

5.1 度量标准

1) 调度成功率STSR.STSR=N(STS)N(TS)×100%，其中，N(STS)是能被成功调度的任务集个数,N(TS)是随机产生的任务集总个数.用于Υcri任务调度效果对比.

2) 故障出现率DTR.DTR=N(DT)N(T)×100%，其中，N(DT)是被调度丢弃的任务次数(丢弃的次数越多，故障个数也就越多),N(T)是随机产生的任务总个数.DTR用于Υnon-cri任务的调度效果对比.

5.2 数据集

系统中有8个智能体提供处理器资源，随机生成100个故障链，每条链上结点个数是取值于[3,9]中的随机值，每个结点对应的任务具有泊松分布的到达时间ri,泊松分布的参数范围是[10,150]之间(该值为就绪时间间隔的期望值),模拟生成不同的负载情况.随机任务的相对截止期Di服从均匀分布U[100,500].

随机任务在随机链生成的基础上添加1～5条路径形成安全操作树，书上结点的执行时间Ci,j服从参数为100Di的指数分布的随机变量.若生成的任务执行时间超过Di，则该任务不被采纳.在不同的任务集负载①(50,150,…,500)各随机生成100个任务集.

5.3 实验和结果

本节将观察随机任务测试集负载不同的情况下,用EDF简单调度的策略和第4节调度方法下的调度成功率和故障出现率的变化，如图6所示.

调度成功率的变化曲线如图6(a)所示，这里比较的是在每个任务集负载下生成的100个任务集通过简单EDF调度方法和本文提出的调度方法能成功调度的任务集个数.能被某个方法调度成功的任务集也称为可行的任务集，那么，图6(a)表明了本文提出的调度方法可比简单EDF调度方法能找到的可行任务集个数要平均多出17.74%.本文提出的调度方法随着任务集负载的增加调度成功率的降低比较平稳，是因为本文的调度方法始终都不断逼近第4节中提出的优化目标；而简单EDF调度则随着任务集负载的增加、调度成功率的降低，根据随机任务集参数的不同而时缓时急.

故障出现率的变化曲线如图6(b)所示，故障个数增多伴随着丢弃任务的次数增加，一个任务之所以会被丢弃，要么是因为在简单EDF调度下该任务的截止期限无法得到满足，要么在本文提出的调度方法下找不到给该任务的子任务划分局部截止期的方案.从图6(b)可以看出，本文提出的调度方法在随机任务集不同负载的情况下，故障出现率都保持在一个较低的水平，尤其是高负载的情况下，故障出现率仍然令人满意；而简单EDF在较高负载下的故障出现率急剧增长.本文提出的调度方法比简单EDF调度方法所丢弃的任务数，即出现故障几率，要平均减少7.72%.

Fig. 6 Performance comparison on Simple EDF and Our Approach图6 简单EDF调度和第4节调度方法的结果比较

① 任务负载为密度之和比智能体个数：U(T)=sum(CiDi)m

6 总 结

本文提出了一种带有截止期实时约束的电网自愈系统基于多智能体进行处理的机制和可供参考的软件实现架构.针对具有实时截止期约束条件下的安全操作序列求解问题，提出了一种基于多智能体的混合关键性调度任务模型；并给出了电网自愈多智能体进行混合关键性调度的求解方法，给出了优化目标和约束条件，用混合整数线性规划(MILP)模型求解.通过仿真结果验证了智能电网自愈多智能体混合关键性调度模型及其求解算法有效地增加了故障结点安全操作处理的成功率，并减少了故障链式的后续触发率.在下一步工作中，我们将把故障链扩展为故障树，在此基础上建立基于故障树的调度任务模型并分析其调度方法.