Designing Contamination Warning Systems for Municipal Water Networks Using Imperfect Sensors
Publication: Journal of Water Resources Planning and Management
Volume 135, Issue 4
Abstract
We consider the problem of designing a contaminant warning system for a municipal water distribution network that uses imperfect sensors, which can generate false-positive and false-negative detections. Although sensor placement optimization methods have been developed for contaminant warning systems, most sensor placement formulations assume perfect sensors, which does not accurately reflect the behavior of real sensor technology. We describe a general exact nonlinear formulation for imperfect sensors and a linear approximation. We consider six general solution strategies, some of which have multiple solution methods. We applied these methods to three test networks, including one with over 10,000 nodes. Our experiments indicate that it is worth deploying a sensor network even when sensors have low detection probability. They also indicate it is worth paying attention to sensor imperfections when placing sensors even when there is a response delay of up to 8 h. The best choice of solution strategy depends upon the user’s goals and the problem size. However, for large-scale problems with a moderate number of sensors, using a local search for the linear approximation formulation provides a reasonable-quality solution in a few minutes of computation. Our models assume that sensors can fail via false negatives. Additionally, we discuss ways to model false positives, ways to limit them, and how to trade them off against false negatives. All of our solution methods can handle false positives but our experiments do not explicitly consider them.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
Sandia is a multipurpose laboratory operated by Sandia Corporation, a Lockheed-Martin Company, for the United States Department of Energy under Contract No. DE-AC04-94AL85000. This work was funded through an Interagency Agreement with the United States Environmental Protection Agency.
References
Berman, O., Krass, D., and Menezes, M. B. (2007). “Facility reliability issues in network -median problems: Strategic centralization and co-location effects.”Oper. Res., 55(2), 332–350.
Berry, J., Carr, R., Hart, W., Leung, V., Phillips, C., and Watson, J. (2006a). “On the placement of imperfect sensors in municipal water networks.” Proc., 8th Symp. on Water Distribution Systems Analysis, ASCE, Reston, Va.
Berry, J., Carr, R. D., Hart, W. E., and Phillips, C. A. (2007). “Scalable water sensor placement via aggregation.” Proc., Water Distribution System Symp., ASCE, Reston, Va.
Berry, J., Fleischer, L., Hart, W. E., Phillips, C. A., and Watson, J.-P. (2005). “Sensor placement in municipal water networks.” J. Water Resour. Plann. Manage., 131(3), 237–243.
Berry, J., Hart, W. E., Phillips, C. A., and Uber, J. (2004). “A general integer-programming-based framework for sensor placement in municipal water networks.” Proc., World Water and Environment Resources Conf., ASCE, Reston, Va.
Berry, J., Hart, W. E., Phillips, C. E., Uber, J. G., and Watson, J.-P. (2006b). “Sensor placement in municipal water networks with temporal integer programming models.” J. Water Resour. Plann. Manage., 132(4), 218–224.
Collinson, P. (1998). “Of bombers, radiologists, and cardiologists: Time to ROC.” Heart, 80(3), 215–217.
Fourer, R., Gay, D. M., and Kernighan, B. W. (2002). AMPL: A modeling language for mathematical programming, 2nd Ed., Brooks/Cole, Pacific Grove, Calif.
Gill, P. E., Murray, W., and Saunders, M. A. (2006). “SNOPT: An SQP algorithm for large-scale constrained optimization.” SIAM Rev., 47(1), 99–131, ⟨http://www.sbsi-sol-optimize.com/asp/sol_products_snopt_desc.htm⟩.
Hart, W. E., Krasnogor, N., and Smith, J. E., eds. (2004). Memetic evolutionary algorithms, Springer, New York.
Kessler, A., Ostfeld, A., and Sinai, G. (1998). “Detecting accidental contaminations in municipal water networks.” J. Water Resour. Plann. Manage., 124(4), 192–198.
Klise, K., and McKenna, S. (2006). “Water quality change detection: Multivariate algorithms.” Proc., SPIE Conf. on Defense and Security Symp., Vol. 6203. SPIE, Bellingham, Wa.
Kumar, A., Kansal, M. L., and Arora, G. (1999). “Discussion of ‘Detecting accidental contaminations in municipal water networks.’” J. Water Resour. Plann. Manage., 125(4), 308–310.
Lee, B. H., and Deininger, R. A. (1992). “Optimal locations of monitoring stations in water distribution system.” J. Environ. Eng., 118(1), 4–16.
Lee, B. H., Deininger, R. A., and Clark, R. M. (1991). “Locating monitoring stations in water distribution systems.” J. Am. Water Works Assoc., 83(7), 60–66.
McKenna, S. A., Wilson, M. P., and Klise, K. A. (2008). “Detecting changes in water quality data.” J. Am. Water Works Assoc., 100(1), 74–85.
Metz, C. (1978). “Basic principles of ROC analysis.” Semin Nucl. Med., VII(4), 283–298.
Murray, R., Uber, J., and Janke, R. (2006). “Modeling acute health impacts resulting from ingestion of contaminated drinking water.” J. Water Resour. Plann. Manage., 132(4), 293–299.
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., 134(6), 556–568.
Ostfeld, A., and Salomons, E. (2004). “Optimal layout of early warning detection stations for water distribution systems security.” J. Water Resour. Plann. Manage., 130(5), 377–385.
Propato, M., Piller, O., and Uber, J. (2005). “A sensor location model to detect contaminations in water distribution networks.” Proc., World Water and Environmental Resources Congress, ASCE, Reston, Va.
Resende, M., and Werneck, R. (2004). “A hybrid heuristic for the -median problem.” J. Heuristics, 10(1), 59–88.
Rossman, L. A. (1999). “The EPANET programmer’s toolkit for analysis of water distribution systems.” Proc., 26th Water Resources Planning and Management Conf., ASCE, Reston, Va., ⟨http://www.epanet.gov/ORD/NRMRL/wswrd/epanet.html⟩.
Snyder, L. V. (2006). “Facility location under uncertainty: A review.” IIE Trans., 38, 537–554.
Synder, L. V., and Daskin, M. S. (2005). “Reliability models for facility location: The expected failure cost case.” Transp. Sci., 39(3), 400–416.
Watson, J.-P., Greenberg, H. J., and Hart, W. E. (2004). “A multiple-objective analysis of sensor placement optimization in water networks.” Proc., World Water and Environment Resources Conf., ASCE, Reston, Va.
Information & Authors
Information
Published In
Copyright
© 2009 ASCE.
History
Received: Jan 16, 2008
Accepted: Feb 27, 2009
Published online: Jun 15, 2009
Published in print: Jul 2009
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.