Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks

Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne M. VanBriesen, Christos Faloutsos

Journal of Water Resources Planning and Management · 2008 · 421 citations · 27 references

Concepts

TL;DR

The paper seeks to deploy sensors in large water distribution networks to detect malicious contaminants by exploiting submodularity for efficient placement with provable guarantees. The authors design submodular‑based algorithms that extend to multicriteria optimization, robust to sensor failures, and minimax criteria. The algorithms scale to networks 72 times larger than previous work, avoid mixed‑integer programming, and empirical tests on two benchmarks and a 21,000‑node system demonstrate their effectiveness.

Abstract

The problem of deploying sensors in a large water distribution network is considered, in order to detect the malicious introduction of contaminants. It is shown that a large class of realistic objective functions—such as reduction of detection time and the population protected from consuming contaminated water—exhibits an important diminishing returns effect called submodularity. The submodularity of these objectives is exploited in order to design efficient placement algorithms with provable performance guarantees. The algorithms presented in this paper do not rely on mixed integer programming, and scale well to networks of arbitrary size. The problem instances considered in the approach presented in this paper are orders of magnitude (a factor of 72) larger than the largest problems solved in the literature. It is shown how the method presented here can be extended to multicriteria optimization, selecting placements robust to sensor failures and optimizing minimax criteria. Extensive empirical evidence on the effectiveness of the method presented in this paper on two benchmark distribution networks, and an actual drinking water distribution system of greater than 21,000 nodes, is presented.

References

27