Structural cost-optimal design of sensor networks for distributed estimation

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

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: (i) sensing cost optimization and (ii) 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.

Introduction

Monitoring large-scale infrastructure—such as power grids, water distribution networks, or environmental monitoring stations—requires the estimation of complex system states using a distributed network of sensors. Designing these networks involves balancing two primary economic and technical challenges: minimizing the sensing cost (the expense of purchasing and placing sensors) and minimizing the networking cost (the expense of establishing communication links between those sensors).

To be effective, the resulting network must satisfy "distributed observability," meaning every node in the network must eventually acquire enough information to estimate the entire system state. While previous literature suggested that finding the absolute minimum cost for sensor placement is an NP-hard problem, this research demonstrates that for a widely applicable class of systems—structurally full-rank systems—the problem can be solved with significantly lower computational complexity.

Methodology: Structural Systems Theory

The framework utilizes Structural Systems Theory, which abstracts the internal dynamics and sensor measurements of a system into a directed graph (digraph). By focusing on the "wiring" or topology of the system rather than specific numerical values (which may fluctuate), the design remains robust against parameter variations.

To solve the global optimization problem, the authors decouple it into two distinct subproblems:

1. Sensing Cost Optimization (Problem P1)

The goal is to select the cheapest set of sensors that ensures the system is observable. The authors map this to the Linear Sum Assignment Problem (LSAP). By identifying "Parent Strongly Connected Components" (SCCs) within the system's graph, they demonstrate that optimal sensor placement is essentially a matching problem between available sensors and these specific components. For structurally full-rank systems, the number of sensors required is exactly equal to the number of parent components.

2. Networking Cost Optimization (Problem P2)

Once sensors are placed, they must be connected to form a "Strongly Connected" network, ensuring a path exists between any two sensors for information sharing. The complexity of this task depends on the nature of the communication links:

  • Undirected Links: If communication is bidirectional, the problem is solved using the Minimum Spanning Tree (MST) approach.
  • Directed Links: If communication is one-way, the problem becomes NP-hard (Minimum Strongly Connected Subgraph). To address this, the authors apply Edmond’s algorithm to provide a 2-approximation, ensuring the solution is no more than twice the cost of the theoretical optimum.

Key Results and Computational Complexity

The most significant contribution of this work is the proof that sensing cost optimization for structurally full-rank systems is not NP-hard, but rather has a polynomial order solution.

Task Complexity Algorithm/Method
Sensing Optimization $O(m^3)$ Hungarian Method (LSAP)
Undirected Networking $O(m^2)$ Prim’s or Kruskal’s (MST)
Directed Networking $O(m^2)$ 2-approximation (Edmond's)

Note: $m$ represents the number of sensors.

These results indicate that the framework is highly scalable, making it feasible to design optimal monitoring networks for massive systems where previous methods would have failed due to computational limits.

Discussion and Limitations

While this framework provides a significant leap in efficiency, it is currently optimized for structurally full-rank (structurally cyclic) systems. While these are common in engineering, they do not encompass all possible dynamical systems. Additionally, the model assumes a single measurement per sensor, meaning each sensor is dedicated to one specific measurement point. Future research may expand these findings to multi-modal sensors and explore tighter bounds for directed networking approximations in specific graph topologies.

Conclusion

By decoupling the sensing and networking challenges and leveraging the properties of structurally full-rank systems, this paper provides a practical roadmap for designing cost-effective, distributed estimation networks. The shift from NP-hard complexity to polynomial-time solutions ($O(m^3)$) allows for the rigorous design of sensor networks in large-scale infrastructure that were previously considered computationally intractable.

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: (i) sensing cost optimization and (ii) 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},
}
Figure