American Society of Civil Engineers


Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks


by Andreas Krause, (Grad. Res. Asst., Computer Sci. Dept. Carnegie Mellon Univ., Pittsburgh, PA 15213. E-mail: krausea@cs.cmu.edu), Jure Leskovec, (Grad. Res. Asst., Machine Learning Dept., Carnegie Mellon Univ., Pittsburgh, PA 15213. E-mail: jure@cs.cmu.edu), Carlos Guestrin, (Asst. Prof., Machine Learning Dept. and Computer Sci. Dept., Carnegie Mellon Univ., Pittsburgh, PA, 15213. E-mail: guestrin@cs.cmu.edu), Jeanne VanBriesen, M.ASCE, (Prof., Dept. of Civ. & Envir. Engrg. and Dept. of Biomedical Engrg., Carnegie Mellon Univ., Pittsburgh, PA 15213. E-mail: jeanne@cmu.edu), and Christos Faloutsos, (Prof., Computer Sci. Dept., Carnegie Mellon Univ., Pittsburgh, PA 15213. E-mail: christos@cs.cmu.edu)

Journal of Water Resources Planning and Management, Vol. 134, No. 6, November/December 2008, pp. 516-526, (doi:  http://dx.doi.org/10.1061/(ASCE)0733-9496(2008)134:6(516))

     Access full text
     Purchase Subscription
     Permissions for Reuse  

Document type: Journal Paper
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.


ASCE Subject Headings:
Water distribution systems
Water pollution
Optimization
Algorithms