Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks
Publication: Journal of Water Resources Planning and Management
Volume 134, Issue 6
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.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
The writers would like to thank Stratos Papadomanolakis, Shannon Isovitsch, Jianhua Xu, Mitch Small, Paul Fischbeck, Jared Cohen, and the anonymous referees for valuable discussions and feedback. This work was partially supported by NSF Grant Numbers NSFCNS-0509383, NSFCNS-0625518, NSFBES-0329549, NSFIIS-0534205 and by the Pennsylvania Infrastructure Technology Alliance (PITA), with additional funding from Intel and NTT. The third writer was partly supported by an Alfred P. Sloan Fellowship and an IBM Faculty Fellowship. The first and second writer were partly supported by a Microsoft Research Graduate Fellowship. Most of the experiments were conducted on a HP server sponsored by Hewlett-Packard.
References
Berry, J., Hart, W., Phillips, C. A., and Watson, J. P. (2006a). “A facility location approach to sensor placement optimization.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Berry, J., Hart, W. E., Phillips, C. E., Uber, J. G., and Watson, J. (2006b). “Sensor placement in municipal water networks with temporal integer programming models.” J. Water Resour. Plann. Manage., 132(4), 218–224.
Berry, J. W., 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.
Boyd, S., and Vandenberghe, L. (2004). Convex optimization, Cambridge University Press, Cambridge, U.K.
Dorini, G., et al. (2006). “An efficient algorithm for sensor placement in water distribution systems.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Garey, M. R., and Johnson, D. S. (2003). Computers and intractability: A guide to the theory of NP-completeness, Freeman, San Francisco
Guan, J., Aral, M. M., Maslia, M. L., and Grayman, W. M. (2006). “Optimization model and algorithms for design of water sensor placement in water distribution systems.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Gueli, R. (2006). “Predator-prey model for discrete sensor placement.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Huang, J. J., McBean, E. A., and James, W. (2006). “Multiobjective optimization for monitoring sensor placement in water distribution systems.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), 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.
Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). “Optimization by simulated annealing.” Science, 220(4598), 671–680.
Krause, A., and Guestrin, C. (2005) “A note on the budgeted maximization of submodular functions.” Technical Rep. No. CMU-CALD-05-103.
Krause, A., McMahan, B., Guestrin, C., and Gupta, A. (2007). “Selecting observations against adversarial objectives.” Advances in Neural Information Processing Systems, Vancouver, Neural Information Processing Systems Foundation, La Jolla, Calif.
Kumar, A., Kansal, M. L., and Arora, G. (1997). “Identification of monitoring stations in water distribution system.” J. Environ. Eng., 123(8), 746–752.
Lerner, U., and Parr, R. (2001). “Inference in hybrid networks: Theoretical limits and practical algorithms.” 17th Conf. on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, Calif.
Leskovec, J. et al. (2007). “Cost-effective outbreak detection in networks.” 13th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Association for Computing Machinery (ACM), New York.
Nemhauser, G., and Wolsey, L. (1981). Studies on graphs and discrete programming, North-Holland, Amsterdam, 279–301.
Nemhauser, G., Wolsey, L., and Fisher, M. (1978). “An analysis of the approximations for maximizing submodular set functions.” Math. Program., 14(1), 265–294.
Ostfeld, A., et al. (2008). “The battle of the water sensor networks: 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.
Ostfeld, A., and Salomons, E. (2006). “Sensor network design proposal for the battle of the water sensor networks (bwsn).” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Preis, A., and Ostfeld, A. (2006). “Multiobjective sensor design for water distribution systems security.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Propato, M., and Piller, O. (2006). “Battle of the water sensor networks.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Rossman, L. A. (1999). “The epanet programmer’s toolkit for analysis of water distribution systems.” Annual Water Resources Planning and Management Conf., Tempe, Ariz., Section 4E, ASCE, New York, 1–10.
Sviridenko, M. (2004). “A note on maximizing a submodular set function subject to knapsack constraint.” Oper. Res. Lett., 32(1), 41–43.
Uber, J., Janke, R., Murray, R., and Meyer, P. (2004). “Greedy heuristic methods for locating water quality sensors in distribution systems.” Proc., World Water & Environmental Resources Congress, EWRI-ASCE, Reston, Va.
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 Environmental Resources Conf., ASCE, Reston Va.
Wu, Z. Y., and Walski, T. (2006). “Multi objective optimization of sensor placement in water distribution systems.” 8th Annual Symp. on Water Distribution Systems Analysis, Cincinnati, Ohio, Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 134 • Issue 6 • November 2008
Pages: 516 - 526
Copyright
© 2008 ASCE.
History
Received: Feb 20, 2007
Accepted: Feb 22, 2008
Published online: Nov 1, 2008
Published in print: Nov 2008
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.