Approximate Dynamic Programming for Link Reconfiguration to Reduce Malicious Input Controllability in Consensus Networks
作者: Nathaniel Mailhot, Mohammad Pirani, Davide Spinello
分类: eess.SY
发布日期: 2026-10-29
💡 一句话要点
提出近似动态规划以降低共识网络中的恶意输入可控性问题
🎯 匹配领域: 支柱八：物理动画 (Physics-based Animation)
关键词: 动态规划 恶意输入 共识网络 可控性 网络安全 鲁棒性 马尔可夫决策过程 学习算法
📋 核心要点
- 核心问题：现有方法在动态共识网络中难以有效降低恶意输入对系统的影响，尤其是在攻击者行为不确定的情况下。
- 方法要点：本文提出通过近似动态规划（ADP）学习攻击者转移和Gramian成本，以优化防御策略，增强网络的鲁棒性。
- 实验或效果：在20节点和100节点的仿真中，ADP的性能与精确动态规划相差不大，且在跟踪任务中显著降低了误差。
📝 摘要（中文）
通信链路影响恶意输入在共识网络中对传感器的影响程度。本文研究了防御者在观察到被攻击传感器后，如何通过选择一个额外链路来降低这种影响。被攻击的传感器随时间变化，脆弱性通过有限时域可控性Gramian的迹来衡量。论文定义了一种局部ε-贪婪攻击者响应规则，构建了一个折扣马尔可夫决策过程。通过精确动态规划（DP），利用完整的Gramian收益矩阵和攻击者转移模型提供最优策略。接着，提出了近似动态规划（ADP），通过从采样的攻击者转移和经验Gramian成本中学习。在条件无偏成本和标准采样及学习率条件下，学习的动作价值表收敛于精确DP解。在20节点和100节点图上的仿真中，经验ADP的回报成本分别与精确DP相差0.23%和1.76%。在二维入侵者跟踪示例中，两种策略相较于未缓解攻击，均将网络范围内的均方根跟踪误差降低了约25%。
🔬 方法详解
问题定义：本文旨在解决在动态共识网络中，恶意输入对系统可控性影响的问题。现有方法在面对攻击者行为变化时，难以实时调整防御策略，导致系统脆弱性增加。
核心思路：论文提出了一种近似动态规划（ADP）方法，通过学习攻击者的转移模式和经验Gramian成本，来优化防御者的决策。这样的设计使得防御者能够在不构建完整收益矩阵的情况下，依然获得接近最优的防御策略。
技术框架：整体架构包括两个主要模块：首先是通过采样获得攻击者的转移数据，其次是利用这些数据来估计Gramian成本，并更新防御者的策略。整个过程通过折扣马尔可夫决策过程进行建模。
关键创新：最重要的创新在于引入了近似动态规划的方法，使得防御者能够在动态环境中有效学习并适应攻击者的行为。这与传统的精确动态规划方法相比，显著降低了计算复杂度。
关键设计：在设计中，采用了局部ε-贪婪策略来平衡探索与利用，同时在学习过程中设置了标准的采样和学习率条件，以确保学习过程的稳定性和收敛性。具体的参数设置和损失函数设计也经过了细致的调优。
🖼️ 关键图片
📊 实验亮点
实验结果显示，近似动态规划（ADP）方法在20节点和100节点图上的回报成本分别与精确动态规划相差仅0.23%和1.76%。在二维入侵者跟踪任务中，两种策略均将网络范围内的均方根跟踪误差降低了约25%，显示出显著的性能提升。
🎯 应用场景
该研究具有广泛的应用潜力，尤其在网络安全、智能传感器网络和自动化控制系统中。通过优化防御策略，可以有效降低恶意攻击对系统的影响，提高系统的鲁棒性和可靠性，具有重要的实际价值和未来影响。
📄 摘要（原文）
Communication links influence how strongly a malicious input at one sensor affects a consensus network. We study how a defender can reduce this influence by selecting one additional link after observing the currently attacked sensor. The attacked sensor changes over time, and vulnerability is measured by the trace of a finite-horizon controllability Gramian. A prescribed local epsilon-greedy attacker response rule defines a discounted Markov decision process for the defender. Exact dynamic programming (DP) provides an optimal policy using the full Gramian payoff matrix and attacker transition model. We then introduce approximate dynamic programming (ADP) that learns from sampled attacker transitions and empirical Gramian costs estimated from measured impulse responses. Under conditionally unbiased costs and standard sampling and learning-rate conditions, the learned action-value table converges to the exact DP solution. The analysis uses Bellman contraction and bounds the effect of persistent Gramian estimation bias, establishing when measured responses recover optimal defender decisions without constructing the full payoff matrix. In simulations on 20- and 100-node graphs, empirical ADP rollout costs are within 0.23% and 1.76%, respectively, of exact DP. In a two-dimensional intruder tracking example, both policies reduce network-wide root-mean-square tracking error spread by approximately 25% relative to an unmitigated attack.