Generic Detectability and Isolability of Topology Failures in Networked Linear Systems

Yuan Zhang, Yuanqing Xia, Jinhui Zhang, Jun Shang

Abstract

This paper studies the possibility of detecting and isolating topology failures (including link failures and node failures) of a networked system from subsystem measurements, in which subsystems are of fixed high-order linear dynamics, and the exact interaction weights among them are unknown. We prove that in such class of networked systems with the same network topologies, the detectability and isolability of a given topology failure (set) are generic properties, indicating that it is the network topology that dominates the property of being detectable or isolable for a failure (set). We first give algebraic conditions for detectability and isolability of arbitrary parameter perturbations for a lumped plant, and then derive graph-theoretical necessary and sufficient conditions for generic detectability and isolability of topology failures for the networked systems. On the basis of these results, we consider the problems of deploying the smallest set of sensors for generic detectability and isolability. We reduce the associated sensor placement problems to the hitting set problems, which can be effectively solved by greedy algorithms with guaranteed approximation performances.

Introduction

Modern critical infrastructure—from power grids to communication networks—can be modeled as networked linear systems. A major threat to these systems is "topology failure," where links are severed or nodes stop functioning due to accidents or attacks. Traditional Fault Detection and Isolation (FDI) methods usually require precise knowledge of all system parameters, such as the exact "weights" of every connection. However, in large-scale real-world systems, these exact values are often unknown or fluctuate. This paper investigates whether failure detectability and isolability can be determined based solely on the network's graph structure.

Methodology

The authors employ a mix of linear systems theory, abstract algebra, and graph theory to address this challenge:

  1. Algebraic Conditions: Necessary and sufficient algebraic conditions are derived for distinguishability between a nominal system and a failed one using transfer functions.
  2. Genericity Analysis: The authors prove that detectability and isolability are "generic" properties. In mathematics, a property is generic if it holds for "almost all" possible parameters. This allows the focus to shift from specific numerical values to the underlying network topology.
  3. Graph-Theoretic Mapping: Complex algebraic requirements are translated into geometric conditions. Specifically, a "transfer index" ($r_{max}$) is defined for subsystems, showing that detectability depends on the distance between the failure and the nearest sensor.
  4. Optimization: To solve the problem of optimal sensor placement, the challenge is reduced to a Hitting Set Problem, which is then solved using greedy algorithms with guaranteed approximation performance.

Key Theoretical Insights

The most significant finding is the proof that topology dominates system behavior in this context. If a network structure allows for failure detection for one set of weights, it almost certainly allows it for any other set of weights, provided the connections exist.

A critical result is the Distance Constraint: a failure is detectable only if the distance $d_{min}$ from the failure to a sensor is less than or equal to $r_{max} - 1$. Here, $r_{max}$ represents how "deeply" the internal dynamics of a subsystem allow a signal to propagate before being lost.

Illustration of the distance constraint in a chain network.

Furthermore, for single-link failures, the conditions required to detect a failure are equivalent to those required to isolate exactly which link failed.

Case Studies and Validation

The theoretical findings were validated using two primary models:

  • 5-node Synthetic System: This model illustrates how specific links can be "hidden" from certain sensor configurations.
  • IEEE 9-bus Power System: A standard benchmark in power engineering used to demonstrate the practical application of the sensor placement strategy.
A 5-node synthetic networked system used for validation.

In the IEEE 9-bus system, the authors showed that while a single sensor could theoretically detect a bus failure, adding more sensors significantly reduced the observation time required to distinguish the failure from background noise.

Conclusion and Future Work

This research establishes that the ability to monitor network topology failures is primarily a structural property. While the current framework assumes identical subsystems, future work will address heterogeneous components and "soft" failures (parameter drifts). Additionally, the authors aim to incorporate quantitative metrics, such as "time-to-detect," into the sensor placement optimization and explore data-driven approaches that minimize the need for system identification.

Summary updated

Abstract

This paper studies the possibility of detecting and isolating topology failures (including link failures and node failures) of a networked system from subsystem measurements, in which subsystems are of fixed high-order linear dynamics, and the exact interaction weights among them are unknown. We prove that in such class of networked systems with the same network topologies, the detectability and isolability of a given topology failure (set) are generic properties, indicating that it is the network topology that dominates the property of being detectable or isolable for a failure (set). We first give algebraic conditions for detectability and isolability of arbitrary parameter perturbations for a lumped plant, and then derive graph-theoretical necessary and sufficient conditions for generic detectability and isolability of topology failures for the networked systems. On the basis of these results, we consider the problems of deploying the smallest set of sensors for generic detectability and isolability. We reduce the associated sensor placement problems to the hitting set problems, which can be effectively solved by greedy algorithms with guaranteed approximation performances.
BibTeX
@article{zhang2020generic,
  author = {Yuan Zhang and Yuanqing Xia and Jinhui Zhang and Jun Shang},
  title = {{Generic Detectability and Isolability of Topology Failures in Networked Linear Systems}},
  journal = {IEEE Transactions on Control of Network Systems},
  year = {2020},
  doi = {10.1109/tcns.2020.3029151},
}
Figure