Topological Placement of Quality Sensors in Water-Distribution Networks without the Recourse to Hydraulic Modeling
Publication: Journal of Water Resources Planning and Management
Volume 146, Issue 6
Abstract
The detection of contaminant intrusion into a water-distribution network (WDN) is a difficult issue due to uncertainty related to the type of injected contaminant, source location, and intrusion time. The placement of water quality sensors has received increasing interest in the last years, and it still represents an open problem and a great challenge for researchers and utilities. Efficient numerical techniques are needed to support any contamination warning system (CWS) design. These require a well-calibrated hydraulic model of the WDN and a great deal of information, both of which are often unavailable to water utilities. In addition, as the size of the WDN increases, the choice of effective sensor placement becomes a computationally intractable problem. This paper introduces a methodology to support water utilities in the design of an effective CWS without any use of hydraulic information, but just exploiting the knowledge of the topology of the WDN. To ensure a complete coverage of the network, the method relies on a priori clustering of the WDN and on the installation of quality sensors at the most central nodes of each cluster, selected according to different topological centrality metrics. The procedure is tested on a benchmark network and on a real WDN serving a town close to Naples, Italy. The solutions obtained with topological criteria are effective in terms of detection time, detection likelihood, redundancy, and population exposed through ingestion.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Data, models, and codes generated or used for this study are available from the corresponding author by request.
References
Adedoja, O. S., Y. Hamam, B. Khalaf, and R. Sadiku. 2019. “A state-of-the-art review of an optimal sensor placement for contaminant warning system in a water distribution network.” Urban Water J. 15 (10): 985–1000. https://doi.org/10.1080/1573062X.2019.1597378.
ASCE. 2004. Interim voluntary guidelines for designing an on-line contaminant monitoring system. Reston, VA: ASCE.
AWWA (American Water Works Association). 2005. Contamination warning systems for water: An approach for providing actionable information to decision-makers. Denver: AWWA.
Bazargan-Lari, M. R. 2014. “An evidential reasoning approach to optimal monitoring of drinking water distribution systems for detecting deliberate contamination events.” J. Cleaner Prod. 78 (Sep): 1–14. https://doi.org/10.1016/j.jclepro.2014.04.061.
Berry, J., R. D. Carr, W. E. Hart, V. J. Leung, C. A. Phillips, and J. P. Watson. 2009. “Designing contamination warning systems for municipal water networks using imperfect sensors.” J. Water Resour. Plann. Manage. 135 (4): 253–263. https://doi.org/10.1061/(ASCE)0733-9496(2009)135:4(253).
Berry, J. W., W. E. Hart, C. A. Phillips, J. G. Uber, and T. M. Walski. 2005a. “Water quality sensor placement in water networks with budget constraints.” In Proc., World Water and Environmental Resources Congress. Reston, VA: ASCE.
Berry, J. W., W. E. Hart, C. A. Phillips, and J. P. Watson. 2005b. “Scalability of integer programming computations for sensor placement in water networks.” In Proc., World Water and Environmental Resources Congress. Reston, VA: ASCE.
Berry, J. W., W. E. Hart, C. A. Phillips, and J. P. Watson. 2006. “A facility location approach to sensor placement optimization.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Bonacich, P. 1972. “Technique for analyzing overlapping memberships.” Sociol. Methodol. 4 (Jan): 176–185. https://doi.org/10.2307/270732.
Chang, N. B., N. P. Pongsanone, and A. Ernest. 2013. “A rule-based decision support system for sensor deployment in small drinking water networks.” J. Cleaner Prod. 60 (Dec): 152–162. https://doi.org/10.1016/j.jclepro.2012.10.036.
Cheifetz, N., A. C. Sandraza, C. Feliers, D. Gilbert, O. Piller, and A. Lang. 2015. “An incremental sensor placement optimization in a large real-world water system.” Procedia Eng. 119 (Jan): 947–952. https://doi.org/10.1016/j.proeng.2015.08.977.
Chianese, S., A. Di Nardo, M. Di Natale, C. Giudicianni, D. Musmarra, and G. F. Santonastaso. 2017. “DMA optimal layout for protection of water distribution networks from malicious attack.” In Proc., 12th Int. Conf. on Critical Information Infrastructures Security. New York: Springer.
Ciaponi, C., E. Creaco, A. Di Nardo, M. Di Natale, C. Giudicianni, D. Musmarra, and G. F. Santonastaso. 2019. “Reducing impacts of contamination in water distribution networks: A combined strategy based on network partitioning and installation of water quality sensors.” Water 11 (6): 1315. https://doi.org/10.3390/w11061315.
Davis, M. J., and R. Janke. 2009. “Development of a probabilistic timing model for the ingestion of tap water.” J. Water Resour. Plann. Manage. 135 (5): 397–405. https://doi.org/10.1061/(ASCE)0733-9496(2009)135:5(397).
Deb, K., S. Agrawal, A. Pratapm, and T. Meyarivan. 2002. “A fast and elitist multi-objective genetic algorithm: NSGA-II.” IEEE Trans. Evol. Comput. 6 (2): 182–197. https://doi.org/10.1109/4235.996017.
Dijkstra, E. W. 1959. “A note on two problems in connexion with graphs.” Numerische Mathematik 1 (1): 269–271. https://doi.org/10.1007/BF01386390.
Di Nardo, A., C. Giudicianni, R. Greco, M. Herrera, and G. F. Santonastaso. 2018. “Applications of graph spectral techniques to water distribution network management.” Water 10 (1): 45. https://doi.org/10.3390/w10010045.
Dorini, G., P. Jonkergouw, Z. Kapelan, F. Di Pierro, S. T. Khu, and D. Savic. 2008. “An efficient algorithm for sensor placement in water distribution systems.” In Proc., 8th Annual Water Distribution Systems Analysis Symp., 1–13, Reston, VA: Environmental and Water Resources Institute of ASCE.
Eliades, D., and M. Polycarpou. 2006. “Iterative deepening of Pareto solutions in water sensor networks.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Fortunato, S. 2010. “Community detection in graphs.” Phys. Rep. 486 (3–5): 75–174. https://doi.org/10.1016/j.physrep.2009.11.002.
Freeman, L. C. 1977. “A set of measures of centrality based on betweenness.” Sociometry 40 (1): 35–41. https://doi.org/10.2307/3033543.
Ghimire, S. R., and B. D. Barkdoll. 2006a. “Heuristic method for the battle of the water network sensors: Demand-based approach.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Ghimire, S. R., and B. D. Barkdoll. 2006b. “A heuristic method for water quality sensor location in a municipal water distribution system: Mass related based approach.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Girvan, M., and M. E. Newman. 2002. “Community structure in social and biological networks.” Proc. Natl. Acad. Sci. 99 (12): 7821–7826. https://doi.org/10.1073/pnas.122653799.
Giudicianni, C., A. Di Nardo, M. Di Natale, R. Greco, G. F. Santonastaso, and A. Scala. 2018. “Topological taxonomy of water distribution networks” Water 10 (4): 444. https://doi.org/10.3390/w10040444.
Grayman, W. M., R. Murray, and D. A. Savic. 2009. “Effects of redesign of water systems for security and water quality factors.” In Proc., World Environmental and Water Resources Congress 2009: Great Rivers, 1–11. Reston, VA: ASCE.
Guan, J., M. M. Aral, M. L. Maslia, and W. M. Grayman. 2006. “Optimization model and algorithms for design of water sensor placement in water distribution systems.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Gueli, R. 2006. “Predator–prey model for discrete sensor placement.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Günter, S., and H. Bunke. 2003. “Validation indices for graph clustering.” Pattern Recognit. Lett. 24 (8): 1107–1113. https://doi.org/10.1016/S0167-8655(02)00257-X.
Hart, W. E., and R. Murray. 2010. “Review of sensor placement strategies for contamination warning systems in drinking water distribution systems.” J. Water Resour. Plann. Manage. 136 (6): 611–619. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000081.
Herrera, M., R. Wright, C. Giudicianni, A. Di Nardo, and J. Izquierdo. 2018. “Complex network multiresolution for optimal sensor placement in big urban infrastructures.” In Artificial intelligence research and development: Current challenges, new trends and applications, 308. Amsterdam, Netherlands: IOS Press.
Huang, J., E. A. McBean, and W. James. 2006. “Multiobjective optimization for monitoring sensor placement in water distribution systems.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Janke, R., R. Murray, T. M. Haxton, T. Taxon, R. Bahadur, W. Samuels, and J. Uber. 2012. Threat ensemble vulnerability assessment-sensor placement optimization tool (TEVA-SPOT) graphical user interface user’s manual. Washington, DC: USEPA.
Janke, R., R. Murray, J. Uber, and T. Taxon. 2006. “Comparison of physical sampling and real-time monitoring strategies for designing a contamination warning system in a drinking water distribution system.” J. Water Resour. Plann. Manage. 132 (4): 310–313. https://doi.org/10.1061/(ASCE)0733-9496(2006)132:4(310).
Katz, L. 1953. “A new status index derived from sociometric analysis.” Psychometrika 18 (1): 39–43. https://doi.org/10.1007/BF02289026.
Kessler, A., A. Ostfeld, and G. Sinai. 1998. “Detecting accidental contaminations in municipal water networks.” J. Water Resour. Plann. Manage. 124 (4): 192–198. https://doi.org/10.1061/(ASCE)0733-9496(1998)124:4(192).
Khorshidi, M. S., M. R. Nikoo, E. Ebrahimi, and M. Sadegh. 2019. “A robust decision support leader-follower framework for design of contamination warning system in water distribution network.” J. Cleaner Prod. 214 (Mar): 666–673. https://doi.org/10.1016/j.jclepro.2019.01.010.
Krause, A., J. Leskovec, C. Guestrin, J. VanBriesen, and C. Faloutsos. 2008. “Efficient sensor placement optimization for securing large water distribution networks.” J. Water Resour. Plann. Manage. 134 (6): 516–526. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:6(516).
Krause, A., J. Leskovec, S. Isovitsch, J. Xu, C. Guestrin, J. VanBriesen, and P. Fischbeck. 2006. “Optimizing sensor placements in water distribution systems using submodular function maximization.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Kroll, D. J. 2006. Securing our water supply: Protecting a vulnerable resource. Tulsa, OK: PennWell Books.
Kumar, A., M. L. Kansal, and G. Arora. 1997. “Identification of monitoring stations in water distribution system.” J. Environ. Eng. 123 (8): 746–752. https://doi.org/10.1061/(ASCE)0733-9372(1997)123:8(746).
Lee, B. H., and R. A. Deininger. 1992. “Optimal locations of monitoring stations in water distribution system.” J. Environ. Eng. 118 (1): 4–16. https://doi.org/10.1061/(ASCE)0733-9372(1992)118:1(4).
McKenna, S. A., D. B. Hart, and L. Yarrington. 2006. “Impact of sensor detection limits on protecting water distribution systems from contamination events.” J. Water Resour. Plann. Manage. 132 (4): 305–309. https://doi.org/10.1061/(ASCE)0733-9496(2006)132:4(305).
Meng, F., G. Fu, R. Farmani, C. Sweetapple, and D. Butler. 2018. “Topological attributes of network resilience: A study in water distribution systems.” Water Res. 143 (Oct): 376–386. https://doi.org/10.1016/j.watres.2018.06.048.
Murray, R., T. Baranowski, W. E. Hart, and R. Janke. 2008. Risk reduction and sensor network design. Washington, DC: USEPA.
Nazempour, R., M. A. S. Monfared, and E. Zio. 2018. “A complex network theory approach for optimizing contamination warning sensor location in water distribution networks.” Int. J. Disaster Risk Reduct. 30 (Sep): 225–234. https://doi.org/10.1016/j.ijdrr.2018.04.029.
Newman, M. E. 2005. “A measure of betweenness centrality based on random walks.” Soc. Networks 27 (1): 39–54. https://doi.org/10.1016/j.socnet.2004.11.009.
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. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:6(556).
Ostfeld, A., and E. Salomons. 2004. “Optimal layout of early warning detection stations for water distribution systems security.” J. Water Resour. Plann. Manage. 130 (5): 377–385. https://doi.org/10.1061/(ASCE)0733-9496(2004)130:5(377).
Ostfeld, A., and E. Salomons. 2005. “Securing water distribution systems using online contamination monitoring.” J. Water Resour. Plann. Manage. 131 (5): 402–405. https://doi.org/10.1061/(ASCE)0733-9496(2005)131:5(402).
Ostfeld, A., and E. Salomons. 2006. “Sensor network design proposal for the battle of the water sensor networks (BWSN).” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Panguluri, S., G. Meiners, J. Hall, and J. G. Szabo. 2009. Distribution system water quality monitoring: Sensor technology evaluation methodology and results. Washington, DC: USEPA.
Preis, A., and A. Ostfeld. 2006. “Multiobjective sensor design for water distribution systems security.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Preis, A., and A. Ostfeld. 2008. “Multiobjective contaminant sensor network design for water distribution systems.” J. Water Resour. Plann. Manage. 134 (366): 366–377. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:4(366).
Propato, M., and O. Piller. 2006. “Battle of the water sensor networks.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Rathi, S., R. Gupta, and L. Ormsbee. 2015. “A review of sensor placement objective metrics for contamination detection in water distribution networks.” Water Sci. Technol. Water Supply 15 (5): 898–917. https://doi.org/10.2166/ws.2015.077.
Rossman, L. A. 2000. EPANET2 users manual. Cincinnati: USEPA.
Schal, S., A. Lothes, L. S. Bryson, and L. Ormsbee. 2013. “Water quality sensor placement guidance using TEVA-SPOT.” In Proc., World Environmental and Water Resources Congress 2013: Showcasing the Future, 1022–1032. Reston, VA: Environmental and Water Resources Institute of ASCE.
Tinelli, S., E. Creaco, and C. Ciaponi. 2017. “Sampling significant contamination events for optimal sensor placement in water distribution systems.” J. Water Resour. Plann. Manage. 143 (9): 04017058. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000814.
Tinelli, S., E. Creaco, and C. Ciaponi. 2018. “Impact of objective function selection on optimal placement of sensors in water distribution networks.” Ital. J. Eng. Geol. Environ. 173–178. https://doi.org/10.4408/IJEGE.2018-01.S-16.
Trachtman, G. B. 2006. “A ‘strawman’ common sense approach for water quality sensor site selection.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Uber, J., R. Janke, R. Murray, and P. Meyer. 2004. “Greedy heuristic methods for locating water quality sensors in distribution systems.” In Critical transitions in water and environmental resources management, 1–9. Reston, VA: ASCE.
Ung, H., O. Piller, D. Gilbert, and I. Mortazavi. 2017. “Accurate and optimal sensor placement for source ıdentification of water distribution networks.” J. Water Resour. Plann. Manage. 143 (8): 04017032. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000777.
USEPA. 2008. User’s manual: TEVA-SPOT toolkit. EPA 600/R-08/041. Washington, DC: USEPA.
Wasserman, S., and K. Faust., eds. 1994. Vol. 8 of Social network analysis: Methods and applications. New York: Cambridge University Press.
Watson, J. P., H. J. Greenberg, and W. E. Hart. 2004. “A multiple-objective analysis of sensor placement optimization in water networks.” In Critical transitions in water and environmental resources management, 1–10. Reston, VA: ASCE.
WHO (World Health Organization). 2006. Guidelines for drinking-water quality—First addendum to third edition, Vol. I: Recommendations, 48–83. Geneva: WHO.
Woo, H. M., J. H. Yoon, and D. Y. Choi. 2001. “Optimal monitoring sites based on water quality and quantity in water distribution systems.” In Bridging the gap: Meeting the world’s water and environmental resources challenges, 1–9. Reston, VA: ASCE.
Wu, Z. Y., and T. Walski. 2006. “Multiobjective optimization of sensor placement in water distribution systems.” In Proc., 8th Annual Water Distribution System Analysis Symp. Reston, VA: Environmental and Water Resources Institute of ASCE.
Xin, K. L., T. Tao, S. Li, and H. Yan. 2017. “Contamination accidents in China’s drinking water distribution networks: Status and countermeasures.” Water Policy 19 (1): 13–27. https://doi.org/10.2166/wp.2016.157.
Xu, X., Y. Lu, S. Huang, Y. Xiao, and W. Wang. 2013. “Incremental sensor placement optimization on water network.” In Proc., Joint European Conf. on Machine Learning and Knowledge Discovery in Databases, 467–482. Berlin: Springer.
Zheng, F., J. Du, K. Diao, T. Zhang, T. Yu, and Y. Shao. 2018. “Investigating effectiveness of sensor placement strategies in contamination detection within water distribution systems.” J. Water Resour. Plann. Manage. 144 (4): 06018003. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000919.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 146 • Issue 6 • June 2020
Copyright
©2020 American Society of Civil Engineers.
History
Received: Mar 21, 2019
Accepted: Dec 6, 2019
Published online: Mar 20, 2020
Published in print: Jun 1, 2020
Discussion open until: Aug 20, 2020
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.