Accurate and Optimal Sensor Placement for Source Identification of Water Distribution Networks
Publication: Journal of Water Resources Planning and Management
Volume 143, Issue 8
Abstract
The problem of sensor placement for early-warning detection systems is a topical issue for industry and utilities who want to equip their networks with such technology. Solving the problem entails finding the best sensor locations that optimize a criterion such as detection rate or time to detection. Few methods exist concerning sensor placement that optimize the result of a source identification method. This paper fills the gap by coupling an adjoint source identification method and a Monte Carlo sensor placement algorithm. The first one is treated through the use of a backtracking algorithm. It uses binary responses at sensors to calculate the ranked list of potential contamination location nodes and contamination times. A criterion is then defined based on the source identification accuracy and specificity. Finally, two optimizing methods that maximize this criterion are proposed: a greedy algorithm and a local search algorithm, which are both coupled with a Monte Carlo method to give the locations of sensors that are the best suited for allocating the source of a contamination. These methods are tested on a 2,500-node network to evaluate their efficiency.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The authors wish to acknowledge the following institutes for allowing use of their computation cluster to carry out the simulations performed in this project: Mésocentre de Calcul Intensif Aquitain (MCIA), Avakas supercomputer. The research part of the project is supported by the German Federal Ministry of Education and Research (BMBF; Project 13N12180) and by the French Agence Nationale de la Recherche (ANR; Project ANR-11-SECU-006).
References
Berry, J., Hart, W. E., Phillips, C. A., Uber, J. G., and Watson, J. P. (2006). “Sensor placement in municipal water networks with temporal integer programming models.” J. Water Resour. Plann. Manage., 218–224.
Dawsey, W., Minsker, B., and VanBlaricum, V. (2006). “Bayesian belief networks to integrate monitoring evidence of water distribution system contamination.” J. Water Resour. Plann. Manage., 234–241.
De Sanctis, A., Shang, F., and Uber, J. (2010). “Real-time identification of possible contamination sources using network backtracking methods.” Water Resour. Plann. Manage., 444–453.
Galinier, P., and Hertz, A. (2005). “A survey of local search methods for graph coloring.” Comput. Oper. Res., 33(9), 2547–2562.
Guan, J., Aral, M., Maslia, M., and Grayman, W. (2006). “Identification of contaminant sources in water distribution systems using simulation optimization method: Case study.” J. Water Resour. Plann. Manage., 252–262.
Krause, A., et al. (2006). “Optimizing sensor placements in water distribution systems using submodular function maximization.” Proc., 8th Annual Water Distribution System Analysis Symp., Univ. of Cincinnati, Cincinnati, 17.
Laird, C. D., Biegler, L. T., and Van Bloemen Waanders, B. G. (2006). “Mixed-integer approach for obtaining unique solutions in source inversion of water networks.” J. Water Resour. Plann. Manage., 242–251.
Lee, B. H., and Deininger, R. A. (1992). “Optimal locations of monitoring stations in water distribution system.” J. Environ. Eng., 4–16.
Liu, L., Sankarasubramanian, A., and Ranjithan, S. R. (2011). “Logistic regression analysis to estimate contaminant sources in water distribution systems.” J. Hydroinf., 13(3), 545–557.
Liu, S., and Auckenthaler, P. (2014). “Optimal sensor placement for event detection and source identification in water distribution networks.” J. Water Supply Res. Technol. AQUA, 63(1), 51-57.
Neupauer, M. R., Records, K. M., and Ashwood, H. M. (2010). “Backward probabilistic modeling to identify contaminant sources in water distribution systems.” J. Water Resour. Plann. Manage., 587–591.
Ostfeld, A., et al. (2008). “The Battle of the Water Sensor Networks (BWSN): A design challenge for engineers and algorithms.” J. Water Resour. Plann. Manage., 556–568.
Perelman, L., and Ostfeld, A. (2010). “Bayesian networks for estimating contaminant source and propagation in a water distribution system using cluster structure.” Proc., 12th Annual Water Distribution Systems Analysis Symp., ASCE, Reston, VA, 426–435.
Piller, O., Deuerlein, J., Gilbert, D., and Weber, J. M. (2015). “Installing fixed sensors for double calibration and early-warning detection purposes.” Procedia Eng., 119, 564–572.
Preis, A., and Ostfeld, A. (2006a). “Multiobjective sensor design for water distribution systems security.” Water Distribution Systems Analysis Symp. 2006, ASCE, Reston, VA, 17.
Preis, A., and Ostfeld, A. (2006b). “Optimal sensors layout for contamination source identification in water distribution systems.” Water Distribution Systems Analysis Symp. 2006, ASCE, Reston, VA, 12.
Propato, M., and Piller, O. (2006). “Battle of the water sensor networks.” 8th Annual Water Distribution System Analysis Symp., ASCE, Reston, VA, 8.
Propato, M., Sarrazy, F., and Tryby, M. (2010). “Linear algebra and minimum relative entropy to investigate contamination events in drinking water systems.” J. Water Resour. Plann. Manage., 483–492.
Propato, M., Tryby, M. E., and Piller, O. (2007). “Linear algebra analysis for contaminant source identification in water distribution systems.” World Environmental and Water Resources Congress 2007, Tampa, FL, 10.
Rathi, S., and Gupta, R. (2014). “Sensor placement methods for contamination detection in water distribution networks: A review.” Procedia Engineering, 89, 181–188.
Seth, A., Klise, K., Siirola, J., Haxton, T., and Laird, C. (2016). “Testing contamination source identification methods for water distribution networks.” J. Water Resour. Plann. Manage., 04016001.
SMaRT-. (2017). “Risk analysis, identification and evaluation of impacts.” ⟨http://www.smart-onlinewdn.eu/⟩ (Mar. 28, 2017).
Tryby, M. E., Propato, M., and Ranjithan, S. R. (2010). “Monitoring design for source identification in water distribution systems.” J. Water Resour. Plann. Manage., 637–646.
Information & Authors
Information
Published In
Copyright
©2017 American Society of Civil Engineers.
History
Received: Feb 22, 2016
Accepted: Jan 18, 2017
Published online: May 3, 2017
Published in print: Aug 1, 2017
Discussion open until: Oct 3, 2017
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.