SLOTS: Effective Algorithm for Sensor Placement in Water Distribution Systems
Publication: Journal of Water Resources Planning and Management
Volume 136, Issue 6
Abstract
This paper deals with methods aimed at the effective and efficient detection of accidental and/or intentional contaminant intrusion(s) in water distribution systems. The objective of this paper is to present a methodology entitled sensors local optimal transformation system (SLOTS) to address both single-objective and multiobjective sensor layout problems. SLOTS is tested on two benchmark water distribution networks used for the Battle of the Water Sensors Networks challenge (BWSN), held as part of the Water Distribution Systems Analysis Symposium, in Cincinnati in 2006. The objectives considered are detection likelihood and the expected population affected prior to detection. The results obtained demonstrate that SLOTS sensor placements are often near optimal. For both single-objective and multiobjective cases, SLOTS is shown to be capable of identifying placements which are consistently better performing than one of the best BWSN methodologies, the greedy algorithm.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This work was supported partially by the U.K. Engineering and Physical Sciences Research Council (Grant No. UNSPECIFIEDEP/C532651/1 entitled “Incorporating Risk and Uncertainty Analysis into the PUrE Framework”). This support is gratefully acknowledged. The writers also thank Alix Slater for her valuable help.
References
Berger-Wolf, T. Y., Hart, W. E., and Saia, J. (2005). “Discrete sensor placement problems in distribution networks.” Journal of Mathematical and Computer Modelling, 42(13), 1385–1396.
Berry, J., Boman, E., Phillips, C. A., and Riesen, L. (2008). “Low-memory Lagrangian relaxation methods for sensor placement in municipal water networks.” Proc., World Water Environmental Resources Congress, American Society of Civil Engineers, Reston, Va.
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.
Berry, J. W., Hart, W. E., Phillips, C. A., and Watson, J. (2006). “A facility location approach to sensor placement optimization.” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Dorini, G., Jonkergouw, P., Kapelan, Z., di Pierro, F., Khu, S. T., and Savic, D. (2006). “An efficient algorithm for sensor placement in water distribution systems.” Proc., 8th Water Distribution Systems Analysis Symp., 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.” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Gueli, R. (2006). “Predator-prey model for discrete sensor placement.” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Huang, J. J., McBean, E. A., and James, W. (2006). “Multi-objective optimization for monitoring sensor placement in water distribution systems.” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Johannes, J. (1999). “Theory of vector maximization: Various concepts of efficient solutions.” Multicriteria decision making: Advances in MCDM models, algorithms, theory, and applications, T. Gal, T. J. Stewart, and T. Hanne, eds., Kluwer, Dordrecht, 2-1–2-32.
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., et al. (2006). “Optimizing sensor placements in water distribution systems using submodular function maximization.” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Krause, A., Guestrin, C., VanBriesen, J., and Faloutsos, C. (2008). “Efficient sensor placement optimization for securing large water distribution networks.” J. Water Resour. Plann. Manage., 134(6), 516–526.
Lee, B. H., and Deininger, R. A. (1992). “Optimal locations of monitoring stations in water distribution system.” J. Environ. Eng., 118(1), 4–16.
Nemhauser, G., Wolsey, L., and Fisher, M. (1978). “An analysis of the approximations for maximizing submodular set functions.” Math. Program., 14, 265–294.
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.
Ostfeld, A., and Salomons, E. (2006). “Sensor network design proposal for the battle of the water sensor networks (BWSN).” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Ostfeld, A., Uber, J., and Salomons, E. (2005). “Battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms.” ⟨http://www.eng.uc.edu/wdsa2006/BWSN_Rules_Final.pdf⟩ (Aug. 23, 2010).
Preis, A., and Ostfeld, A. (2006). “Multiobjective sensor design for water distribution systems security.” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Preparata, F. P., and Shamos, M. I. (1993). Computational geometry, Springer, New York.
Propato, M., and Piller, O. (2006). “Battle of the water sensor networks.” Proc., 8th Water Distribution Systems Analysis Symp., Environmental and Water Resources Institute of ASCE (EWRI of ASCE), New York.
Rossman, R. A. (1999). “The Epanet programmer’s toolkit for analysis of water distribution systems.” Annual Water Resources Planning and Management Conf., Section 4E, ASCE, New York, 1–10
Rubinstein, R. Y. (1999). “The simulated entropy method for combinatorial and continuous optimization.” Methodol. Comput. Appl. Probab., 1, 127–190.
Shastri, Y., and Diwekar, U. (2006). “Sensor placement in water networks: A stochastic programming approach.” J. Water Resour. Plann. Manage., 132(3), 192–203.
Uber, J., Janke, R., Murray, R., and Meyer, P. (2004). “Greedy heuristic methods for locating water quality sensors in distribution systems.” Conf. Proc., ASCE, New York, Vol. 138, 481.
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 (CD-ROM edition), ASCE, New York.
Wu, Z. Y., and Walski, T. (2006). “Multi objective optimization of sensor placement in water distribution systems.” Proc., 8th Water Distribution Systems Analysis Symp., 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 136 • Issue 6 • November 2010
Pages: 620 - 628
Copyright
© 2010 ASCE.
History
Received: Oct 6, 2008
Accepted: Feb 24, 2010
Published online: Feb 26, 2010
Published in print: Nov 2010
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.