Structural Cost-Optimal Design of Sensor Networks for Distributed Estimation

Mohammadreza Doostmohammadian, Hamid R. Rabiee, Usman A. Khan

TL;DR

This paper provides a computationally efficient framework for designing sensor networks that minimize both sensing and communication costs while ensuring "distributed observability." The authors prove that for a common class of systems (structurally full-rank), the once-thought NP-hard problem of optimal sensor placement can actually be solved in polynomial time ($O(m^3)$), and they offer a practical 2-approximation for the more difficult task of designing directional communication links.

What Problem Does This Paper Address?

In large-scale infrastructure—like power grids or environmental monitoring stations—you need to estimate the state of a complex system using a network of sensors. This presents two major challenges:

  1. Sensing Cost: Which sensors should you buy and where should you put them to ensure you can "see" the whole system?
  2. Networking Cost: How should these sensors talk to each other so that every single node in the network eventually gains enough information to estimate the entire system state?

Previous research suggested that finding the absolute cheapest set of sensors to ensure observability is an NP-hard problem (meaning it's computationally "impossible" for very large systems). This paper challenges that notion for a specific, widely applicable class of systems called "structurally full-rank" systems.

Methods

The authors use Structural Systems Theory, which represents the system's internal dynamics and sensor measurements as a directed graph (digraph). This allows them to ignore specific numerical values (which might change over time) and focus on the "wiring" of the system.

They break the master optimization problem into two distinct subproblems:

  • Problem P1 (Sensing): They map the sensor selection problem to the Linear Sum Assignment Problem (LSAP). By identifying "Parent Strongly Connected Components" (SCCs) in the system graph, they show that the optimal sensor placement is essentially a matching problem between sensors and these components.
  • Problem P2 (Networking): They aim to create a "Strongly Connected" network (where a path exists between any two sensors).
  • For undirected (bidirectional) links, they use the standard Minimum Spanning Tree (MST) approach.
  • For directed (one-way) links, the problem is NP-hard. They apply Edmond’s algorithm to find a "2-approximation"—a solution guaranteed to be no more than twice the cost of the absolute best possible network.

Datasets

Not discussed in the paper. This is a theoretical and algorithmic paper; it focuses on mathematical proofs and computational complexity analysis rather than empirical testing on specific datasets.

Key Insights and Ideas

  • The "Full-Rank" Shortcut: The authors identify that if a system is "structurally cyclic" (full-rank), the complexity of the sensing problem collapses. In these systems, the number of sensors needed is exactly equal to the number of "parent" components in the system's graph.
  • Decoupling is Key: The paper demonstrates that you can optimize the sensors first and the network second without losing the "distributed observability" guarantee. This modularity makes the math much more manageable.
  • Polynomial vs. NP-Hard: The most significant "aha" moment is the proof that sensing cost optimization for this class of systems is $O(m^3)$ (using the Hungarian Method), contradicting earlier claims that the problem is always NP-hard.
  • Directionality Matters: The paper highlights a massive jump in difficulty when moving from bidirectional communication (easy/MST) to directional communication (hard/MSSS).

Key Results

  • Sensing Optimization: Solved exactly in $O(m^3)$ time, where $m$ is the number of sensors. This is a "polynomial order" solution, meaning it scales well for large systems.
  • Undirected Networking: Solved exactly in $O(m^2)$ time using Prim’s or Kruskal’s algorithms.
  • Directed Networking: Provided a 2-approximation algorithm with $O(m^2)$ complexity. This means even for massive networks where the perfect solution is unreachable, we can quickly find a solution that is at most 100% more expensive than the theoretical minimum.

Limitations and Future Work

  • System Class Restriction: The polynomial-time solution for sensing only applies to "structurally full-rank" systems. While common, this doesn't cover every possible dynamical system.
  • Single Measurement Assumption: The model assumes each sensor is assigned to only one measurement. While the authors claim this is "without loss of generality," real-world multi-modal sensors might require a more complex formulation.
  • Gap in Directed Networking: The solution for directed networks is an approximation, not an exact optimum. Future work could explore tighter bounds or specific graph topologies where an exact solution is easier to find.

Summary updated

Abstract

In this letter, we discuss cost optimization of sensor networks monitoring structurally full-rank systems under distributed observability constraint. Using structured systems theory, the problem is relaxed into two subproblems: first, sensing cost optimization; and second, networking cost optimization. Both problems are reformulated as combinatorial optimization problems. The sensing cost optimization is shown to have a polynomial-order solution. The networking cost optimization is shown to be NP-hard in general, but has a polynomial-order solution under specific conditions. A 2-approximation polynomial-order relaxation is provided for general networking cost optimization, which is applicable in large-scale system monitoring.
BibTeX
@article{doostmohammadian2018structural,
  author = {Mohammadreza Doostmohammadian and Hamid R. Rabiee and Usman A. Khan},
  title = {{Structural Cost-Optimal Design of Sensor Networks for Distributed Estimation}},
  journal = {IEEE Signal Processing Letters},
  year = {2018},
  url = {https://openreview.net/forum?id=tWNV281q37LH},
}

Loading related content...

Figure