智能电网中基于混合贪心算法的通信网络备用电源渐进恢复调度研究

《IEICE Transactions on Communications》：Backup power scheduling for communication networks during progressive recovery in smart grids

本文针对智能电网中通信网络与电网相互依赖引发的级联故障风险，研究了在渐进恢复过程中如何优化备用电源单元的启动时机。作者提出了一种基于备用电源利用效率启发式的混合贪心算法，能够在恢复进度信息有限的情况下获得次优解；同时提出了一种轻量级方法，可在多项式时间内求解近似解。仿真实验表明，所提方法能有效抑制级联故障扩散，显著提升智能电网在恢复期间的性能水平。

　　

随着能源系统的智能化转型，智能电网作为关键基础设施正面临着前所未有的挑战。智能电网由通信网络和电网紧密耦合而成，这种相互依赖关系在提升系统效率的同时，也埋下了潜在风险。一旦电网发生物理故障，可能引发连锁反应，导致故障在通信网络和电网之间相互传导，最终演变为大规模的级联故障，威胁整个智能电网的安全稳定运行。

在自然灾害等极端情况下，电网可能遭受大范围物理损坏，多个受损电力节点需要通过多个恢复子周期逐步修复。在此期间，为通信节点配备的备用电源单元成为阻止级联故障扩大的关键防线。然而，备用电源单元的容量有限，可能无法支撑整个恢复期间的运行。这就引出了一个关键问题：如何在恢复过程中优化每个备用电源单元的启动时机，以最小化级联故障的负面影响？

传统研究主要关注级联故障发生后的即时影响缓解，而对整个恢复期间的性能维持重视不足。特别是，现有工作尚未系统研究在渐进恢复过程中备用电源的调度策略。这就构成了本研究要解决的核心问题：在电力节点被逐步修复的多个恢复子周期内，如何安排各备用电源单元的运行时间，以最小化整个恢复期间不可用电力节点的累积数量？

针对这一挑战，Nagao OGINO和Atsushi ITO在《IEICE Transactions on Communications》上发表的研究中，提出了一套完整的备用电源调度解决方案。他们首先使用混合整数线性规划(MILP)模型精确描述了备用电源调度问题，该模型的解指明了每个备用电源单元需要运行的最优恢复子周期。

为了在信息有限的情况下获得实用解，研究人员创新性地提出了混合贪心(HG)方法。该方法基于备用电源单元利用效率的启发式规则，只需掌握有限的后继恢复子周期信息即可推导次优解。更值得关注的是，团队还开发了一种轻量级方法，能够为每个恢复子周期单独推导备用电源调度方案。结合这种轻量级方法的贪心算法可在多项式时间内求解问题的近似解，大大提升了算法实用性。

研究人员为开展这项研究采用了几个关键技术方法：首先建立了智能电网的相互依赖网络模型，明确规定了通信节点和电力节点的正常工作条件；然后构建了混合整数线性规划(MILP)模型来形式化描述备用电源调度问题；接着提出了基于启发式的混合贪心算法，利用有限恢复进度信息获得次优解；最后设计了轻量级调度方法，通过构建多播树来近似求解每个恢复子周期的调度问题，确保算法在多项式时间内完成。

3. 智能电网中的备用电源调度

3.1 智能电网模型

智能电网包含通信网络和电网的配对。通信网络包含控制服务器节点，由多个通信节点组成。电网容纳发电机节点，包含多个电力节点。控制服务器节点通过服务器通信节点与通信网络连接，负责管理电网配置、收集感知数据并发布控制指令。发电机节点通过发电机电力节点与电网连接，作为该区域的电力来源。

通信网络与电网之间的相互依赖关系通过方向性跨网络链路表示。起始点为通信节点、终点为电力节点的链路表示通信网络中的接入线路；起始点为电力节点、终点为通信节点的链路表示配电网络中的总线系统。这种相互依赖关系使得电网中的物理故障可能引发大规模的级联故障。

图1展示了考虑的智能电网模型示例。当电力节点n^p₁和n^p₃遭受初始物理损坏时，由于与发电机节点断开连接（条件4），电力节点n^p₅和n^p₆变得不可用。然后，四个通信节点n^c₁、n^c₂、n^c₃和n^c₅因失去电力供应而变得不可用（条件1）。通信节点n^c₄也因与控制服务器节点断开而不可用（条件2）。最终，电力节点n^p₂和n^p₄因无法控制而不可用（条件3）。初始仅两个电力节点损坏，最终导致六个电力节点不可用。

3.2 备用电源调度的必要性

自然灾害可能导致电网遭受大范围物理损坏，多个受损电力节点需要逐步修复。恢复期被划分为多个恢复子周期，每个受损电力节点在不同的恢复子周期内被修复。通信节点依靠备用电源单元在工作电力节点无法供电时保持可用，从而阻止级联故障的扩大。

然而，备用电源单元的容量可能不足以支撑整个恢复期间的操作。备用电源单元只能在有限数量的恢复子周期内运行。因此，每个备用电源单元投入运行的时机影响着受保护的电力节点总数。优化每个备用电源单元的启动时机对于最小化渐进恢复期间不可用电力节点的数量至关重要。

图2展示了电力节点n^p₁和n^p₃发生物理故障时的渐进恢复示例。恢复期分为两个恢复子周期：电力节点n^p₁在恢复子周期0修复，n^p₃在恢复子周期1修复。每个备用电源单元只能在一个恢复子周期内运行。如图2(a)所示，如果通信节点n^c₂和n^c₃的备用电源单元在恢复子周期0运行，可以保护两个电力节点n^p₂和n^p₄。而如图2(b)所示，如果相同的备用电源单元在恢复子周期1运行，可以保护三个电力节点n^p₂、n^p₄和n^p₆。无备用电源单元时，恢复子周期0和1期间不可用电力节点的累积数量为11(=6+5)。当两个备用电源单元分别在恢复子周期0和1运行时，该数值变为9(=4+5)和8(=6+2)。因此，两个备用电源单元应在恢复子周期1投入运行。

4. 备用电源调度的贪心方法

4.1 前向和后向贪心方法

前向贪心(FG)和后向贪心(BG)方法作为基线备用电源调度方法。FG方法从故障发生后的第一个恢复子周期开始，迭代求解小规模MILP模型。通信网络运营商需要在每个恢复子周期开始时获取未修复电力节点信息，求解小规模MILP模型以确定后续恢复子周期需要运行的备用电源单元。

BG方法从最后一个恢复子周期开始，逆向重复求解小规模MILP模型。后向贪心方法需要在恢复期开始时掌握整个恢复期间修复电力节点的完整顺序信息，从而事先推导所有恢复子周期的备用电源调度方案。

4.2 混合贪心方法

混合贪心(HG)方法也在每个恢复子周期开始时优化备用电源调度，但它还利用了有限数量后继恢复子周期的信息。HG方法基于备用电源单元利用效率的启发式规则。

图3说明了控制服务器节点在通信网络中的布置方向与发电机节点在电网中的布置方向不同的两种场景。图3(a)中，远离控制服务器节点的方向与远离发电机节点的方向一致；而图3(b)中，这两个方向相反。在第一种场景下，当渐进恢复沿远离发电机节点的方向进行时，不同的备用电源单元可以在每个恢复子周期抑制级联故障。在第二种场景下，当渐进恢复沿接近发电机节点的方向进行时，需要更多的备用电源单元来抑制级联故障。

研究表明，备用电源单元的需求数量随着渐进恢复的推进保持不变或减少，这意味着备用电源单元的利用效率不会随着恢复的进行而降低。因此，在为配备备用电源单元的通信节点恢复供电之前投入运行是最有利的。HG方法仅使每个备用电源单元在配备该单元的通信节点恢复供电前的C_bp个恢复子周期内可用。

5. 备用电源调度的轻量级方法

5.1 每个恢复子周期的轻量级备用电源调度

为了简化每个恢复子周期的备用电源调度问题，研究仅考虑在起源处抑制级联故障的扩展。因此，选择满足以下准则的通信节点作为候选节点，其备用电源单元需要运行：准则1）每个候选通信节点仅依赖不可保护电力节点的电力供应；准则2）每个候选通信节点控制至少一个可保护电力节点。

候选通信节点需要与控制服务器节点连接，即使其备用电源单元可以投入运行。为了实现这一目标，研究考虑在通信网络中配置连接服务器通信节点和所有候选通信节点的最小Steiner树。由于最小Steiner树问题也是NP难问题，研究利用多项式时间内构建多播树的贪心算法来近似最小Steiner树。

图4说明了轻量级备用电源调度方法的误差因素。在最后一个恢复子周期，仅电力节点n^p₃未修复，通信节点n^c₂的备用电源单元已耗尽不可用。此时，仅通信节点n^c₃是候选节点，它仅依赖不可保护电力节点n^p₃并控制可保护电力节点n^p₄。即使通信节点n^c₃的备用电源单元在最后一个恢复子周期运行，电力节点n^p₄仍不可用，因为它因电力节点n^p₂的级联故障而与发电机节点断开。这是第一个误差因素，不可用电力节点的数量可能不会减少，而运行的备用电源单元数量却增加。此外，如果通信节点n^c₄的备用电源单元额外运行，电力节点n^p₆可以受到保护。轻量级备用电源调度仅考虑在原始通信节点处抑制级联故障，这是第二个误差因素，可能错过保护级联故障下游电力节点的机会。

5.2 轻量级前向和后向贪心方法

轻量级前向贪心(LFG)方法不求解小规模MILP模型，而是从第一个恢复子周期开始迭代执行轻量级备用电源调度方法。轻量级后向贪心(LBG)方法从最后一个恢复子周期开始逆向执行轻量级备用电源调度方法。

5.3 轻量级混合贪心方法

轻量级混合贪心(LHG)方法也使用轻量级方法推导每个恢复子周期的备用电源调度。在LHG方法中，除非配备备用电源单元的通信节点所依赖的至少一个电力节点在后续C_bp个恢复子周期内变得可保护，否则该备用电源单元不可用。

6. 仿真实验

6.1 仿真设置

仿真实验采用连通空间随机拓扑来评估通信网络和电网。配置了五个包含32个节点和48条链路的通信网络，以及五个包含64个节点和96条链路的电网。每个通信节点从最近的电力节点获取电力，每个电力节点由最近的通信节点控制。每个备用电源单元在整个恢复期间只能激活一次，即连续运行。

图6展示了四个仿真场景，分别对应控制服务器节点、发电机节点和物理故障区域布置不同的情况。指定数量的电力节点(|F₀|)因自然灾害遭受物理损坏。恢复子周期数(T)等于受损电力节点数。受损电力节点按距发电机电力节点的跳数升序顺序依次修复，即渐进恢复沿远离发电机节点的方向进行。

6.2 贪心方法的仿真结果

仿真结果表明，全局优化方法（通过求解原始MILP模型）在备用电源单元容量充足时，不可用电力节点的累积数量与不可保护节点的累积数量重合。FG方法仅需未修复电力节点信息，但与全局优化方法相比，略微增加了不可用电力节点的累积数量。BG方法需要整个恢复期间修复顺序的完整信息，其不可用电力节点的累积数量与全局优化方法几乎相同。HG方法仅需有限数量后继恢复子周期的信息，却能实现与BG方法几乎相同的性能水平。

图7显示，当备用电源单元容量充足时，后期恢复子周期的备用电源单元利用率高于前期。这表明当备用电源单元容量有限时，应在后期恢复子周期投入运行。这也是BG方法能比FG方法更显著减少不可用电力节点累积数量的原因。

图8表明，控制服务器节点远离方向与渐进恢复方向差异越大，前期和后期恢复子周期的利用率差异越大。这导致FG方法中不可用电力节点的累积数量按场景1、2、3、4的顺序显著增加。

6.3 轻量级贪心方法的仿真结果

轻量级贪心方法能够很好地近似相应的贪心方法。特别是LHG方法，仅需有限数量未来恢复子周期的信息，就能实现与LBG方法几乎相同的性能水平。当受损电力节点数量增加时，轻量级贪心方法仍能很好地近似相应的贪心方法。HG和LHG方法能够实现与BG和LBG方法几乎相同的性能水平。

7. 结论与研究意义

本研究系统阐述了智能电网渐进恢复过程中的备用电源调度问题，提出了一种基于备用电源利用效率启发式的混合贪心方法，能够从有限的修复顺序信息中推导次优解。针对贪心方法仍涉及NP难问题的情况，研究还提出了轻量级方法，可高效求解每个恢复子周期的备用电源调度方案。结合轻量级方法的轻量级贪心方法能够在多项式时间内推导问题的近似解，显著提升了算法的实用性。

仿真实验验证了所提方法的有效性。混合贪心方法在仅需有限后继恢复子周期信息的情况下，性能与需要完整信息的后向贪心方法几乎相同。轻量级混合贪心方法也能很好地近似轻量级后向贪心方法。这些方法在不同场景和不同受损节点数量下均表现出良好的适应性。

这项研究的重要意义在于首次系统研究了智能电网在渐进恢复过程中的备用电源调度问题，为提升智能电网的韧性提供了实用化解决方案。所提出的方法能够有效抑制级联故障的扩散，在备用电源容量有限的情况下最大化维持智能电网的性能水平，对于构建 resilient 的智能电网基础设施具有重要参考价值。

然而，研究仍存在进一步探索的空间。轻量级贪心方法的近似率分析需要深入研究。当电网中链路和节点容量受限时，恢复期间可能需要负荷削减，这种情况下的备用电源调度问题也有待探讨。这些方向为未来研究提供了有价值的切入点。