论文标题
网络系统中卡尔曼过滤的弹性传感器放置：复杂性和算法
Resilient Sensor Placement for Kalman Filtering in Networked Systems: Complexity and Algorithms
论文作者
论文摘要
给定受噪声影响的线性动力学系统，我们研究了受传感器放置预算约束的最佳放置传感器（在设计时）的问题，以最大程度地减少相应Kalman滤波器的稳态误差协方差的痕迹。虽然此问题通常是NP硬化，但我们考虑了与系统动力学矩阵关联的基础图，并专注于图表中的一个节点处的单个输入时的情况。我们提供最佳的策略（以多项式时间计算）将传感器放在网络上。接下来，我们考虑攻击（即删除）传感器攻击预算约束下放置的传感器的问题，以最大程度地提高所得卡尔曼滤波器的稳态错误协方差的跟踪。使用有关传感器放置问题的见解，我们提供了一种最佳的策略（以多项式时间计算）来攻击放置传感器。最后，我们考虑系统设计人员将传感器放置在传感器放置预算限制下的情况，然后对手攻击受传感器攻击预算约束的置换传感器。弹性传感器放置问题是找到一种传感器放置策略，以最大程度地减少与在攻击中幸存的传感器相对应的卡尔曼滤波器的稳态误差协方差的痕迹。我们表明，这个问题是NP固定的，并提供了伪多项式时间算法来解决该算法。
Given a linear dynamical system affected by noise, we study the problem of optimally placing sensors (at design-time) subject to a sensor placement budget constraint in order to minimize the trace of the steady-state error covariance of the corresponding Kalman filter. While this problem is NP-hard in general, we consider the underlying graph associated with the system dynamics matrix, and focus on the case when there is a single input at one of the nodes in the graph. We provide an optimal strategy (computed in polynomial-time) to place the sensors over the network. Next, we consider the problem of attacking (i.e., removing) the placed sensors under a sensor attack budget constraint in order to maximize the trace of the steady-state error covariance of the resulting Kalman filter. Using the insights obtained for the sensor placement problem, we provide an optimal strategy (computed in polynomial-time) to attack the placed sensors. Finally, we consider the scenario where a system designer places the sensors under a sensor placement budget constraint, and an adversary then attacks the placed sensors subject to a sensor attack budget constraint. The resilient sensor placement problem is to find a sensor placement strategy to minimize the trace of the steady-state error covariance of the Kalman filter corresponding to the sensors that survive the attack. We show that this problem is NP-hard, and provide a pseudo-polynomial-time algorithm to solve it.
