Revisiting the Water Quality Sensor Placement Problem: Optimizing Network Observability and State Estimation Metrics
Publication: Journal of Water Resources Planning and Management
Volume 147, Issue 7
Abstract
Real-time water quality (WQ) sensors in water distribution networks (WDN) have the potential to enable network-wide observability of water quality indicators, contamination event detection, and closed-loop feedback control of WQ dynamics. To that end, prior research has investigated a wide range of methods that guide the geographic placement of WQ sensors. These methods assign a metric for fixed sensor placement (SP) followed by metric-optimization to obtain optimal SP. These metrics include minimizing intrusion detection time, thereby minimizing the expected population and amount of contaminated water affected by an intrusion event. In contrast to the literature, the objective of this paper is to provide a computational method that considers the overlooked metric of state estimation and network-wide observability of the WQ dynamics. This metric finds the optimal WQ sensor placement that minimizes the state estimation error via the Kalman filter for noisy WQ dynamics—a metric that quantifies WDN observability. To that end, the state-space dynamics of WQ states for an entire WDN are given and the observability-driven sensor placement algorithm is presented. The algorithm takes into account the time-varying nature of WQ dynamics due to changes in the hydraulic profile—a collection of hydraulic states including heads (pressures) at nodes and flow rates in links that are caused by a demand profile over a certain period of time. Thorough case studies are given, highlighting key findings, observations, and recommendations for WDN operators. Github codes are included for reproducibility.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code used during the study were provided by a third party. Specifically, we provide a Github link that includes all the models, the data, and the results from the case study (Wang 2021).
Acknowledgments
This material is based upon work supported by the National Science Foundation under Grant Nos. 1728629, 1728605, 2015671, and 2015603.
References
Afshar, A., and M. A. Mariño. 2012. “Multi-objective coverage-based aco model for quality monitoring in large water networks.” Water Resour. Manage. 26 (8): 2159–2176. https://doi.org/10.1007/s11269-012-0008-2.
Al-Zahrani, M. A., and K. Moied. 2003. “Optimizing water quality monitoring stations using genetic algorithms.” Arabian J. Sci. Eng. 28 (1): 57–75.
Aral, M. M., J. Guan, and M. L. Maslia. 2010. “Optimal design of sensor placement in water distribution networks.” J. Water Resour. Plann. Manage. 136 (1): 5–18. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000001.
Basha, H., and L. Malaeb. 2007. “Eulerian–Lagrangian method for constituent transport in water distribution networks.” J. Hydraul. Eng. 133 (10): 1155–1166. https://doi.org/10.1061/(ASCE)0733-9429(2007)133:10(1155).
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.
Cormen, T. H., C. E. Leiserson, R. L. Rivest, and C. Stein. 2009. Introduction to algorithms. Cambridge, MA: MIT Press.
Cortesi, F. L., T. H. Summers, and J. Lygeros. 2014. “Submodularity of energy related controllability metrics.” In Proc., 53rd IEEE Conf. on Decision and Control, 2883–2888. Piscataway, NJ: IEEE. https://doi.org/10.1109/CDC.2014.7039832.
Di Nardo, A., C. Giudicianni, R. Greco, M. Herrera, G. F. Santonastaso, and A. Scala. 2018. “Sensor placement in water distribution networks based on spectral algorithms.” In Vol. 3 of Proc., 13th Int. Conf. on Hydroinformatics, edited by G. L. Loggia, G. Freni, V. Puleo, and M. D. Marchis, 593–600. Manchester, UK: EPiC Series in Engineering, EasyChair.
Eliades, D. G., M. Kyriakou, and M. M. Polycarpou. 2014. “Sensor placement in water distribution systems using the S-PLACE toolkit.” Procedia Eng. 70 (2010): 602–611. https://doi.org/10.1016/j.proeng.2014.02.066.
Eliades, D. G., M. Kyriakou, S. Vrachimis, and M. M. Polycarpou. 2017. “EPANET-MATLAB Toolkit: An open-source software for interfacing EPANET with MATLAB.” In Proc., Critical Information Infrastructures Security. Amsterdam, Netherlands: Zenodo. https://doi.org/10.5281/ZENODO.831492.
Fabrie, P., G. Gancel, I. Mortazavi, and O. Piller. 2010. “Quality modeling of water distribution systems using sensitivity equations.” J. Hydraul. Eng. 136 (1): 34–44. https://doi.org/10.1061/(ASCE)HY.1943-7900.0000138.
Ghimire, S. R., and B. D. Barkdoll. 2006. “Heuristic method for the battle of the water network sensors: Demand based approach.” In Proc., 8th Annual Water Distribution Systems Analysis Symp. Reston, VA: ASCE. https://doi.org/10.1061/40941(247)102.
Giudicianni, C., M. Herrera, A. Di Nardo, R. Greco, E. Creaco, and A. Scala. 2020. “Topological placement of quality sensors in water-distribution networks without the recourse to hydraulic modeling.” J. Water Resour. Plann. Manage. 146 (6): 04020030. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001210.
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.
He, G., T. Zhang, F. Zheng, and Q. Zhang. 2018. “An efficient multi-objective optimization method for water quality sensor placement within water distribution systems considering contamination probability variations.” Water Res. 143: 165–175. https://doi.org/10.1016/j.watres.2018.06.041.
Hespanha, J. P. 2018. Linear systems theory. Princeton, NJ: Princeton University Press.
Hooshmand, F., F. Amerehi, and S. A. MirHassani. 2020. “Logic-based benders decomposition algorithm for contamination detection problem in water networks.” Comput. Oper. Res. 115: 104840. https://doi.org/10.1016/j.cor.2019.104840.
Hu, C., L. Dai, X. Yan, W. Gong, X. Liu, and L. Wang. 2020. “Modified NSGA-III for sensor placement in water distribution system.” Inf. Sci. 509 (Jan): 488–500. https://doi.org/10.1016/j.ins.2018.06.055.
Hu, C., M. Li, D. Zeng, and S. Guo. 2018. “A survey on sensor placement for contamination detection in water distribution systems.” Wireless Networks 24 (2): 647–661. https://doi.org/10.1007/s11276-016-1358-0.
Jawaid, S. T., and S. L. Smith. 2015. “Submodularity and greedy algorithms in sensor scheduling for linear dynamical systems.” Automatica 61 (Nov): 282–288.
Kansal, M., T. Dorji, S. K. Chandniha, and A. Tyagi. 2012. “Identification of optimal monitoring locations to detect accidental contaminations.” In Proc., World Environmental and Water Resources Congress 2012: Crossing Boundaries, 758–776. Reston, VA: ASCE. https://doi.org/10.1061/9780784412312.079.
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).
Kumar, A., M. 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).
Lax, P. D., and B. Wendroff. 1964. “Difference schemes for hyperbolic equations with high order of accuracy.” Commun. Pure Appl. Math. 17 (3): 381–398. https://doi.org/10.1002/cpa.3160170311.
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).
Lovász, L. 1983. “Submodular functions and convexity.” In Mathematical programming the state of the art, 235–257. New York: Springer.
Morais, A. 2012. “Fast and robust solution methods for the water quality equations.” M.S. thesis, Dept. of Mathematics, Delft Univ. of Technology.
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).
Preis, A., and A. Ostfeld. 2008. “Multiobjective contaminant sensor network design for water distribution systems.” J. Water Resour. Plann. Manage. 134 (4): 366–377. https://doi.org/10.1061/(ASCE)0733-9496(2008)134:4(366).
Rajakumar, A. G., M. S. Mohan Kumar, B. Amrutur, and Z. Kapelan. 2019. “Real-time water quality modeling with ensemble Kalman filter for state and parameter estimation in water distribution networks.” J. Water Resour. Plann. Manage. 145 (11): 04019049. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001118.
Rathi, S., and R. Gupta. 2014a. “Locations of sampling stations for water quality monitoring in water distribution networks.” J. Environ. Sci. Eng. 56 (2): 169–178.
Rathi, S., and R. Gupta. 2014b. “Sensor placement methods for contamination detection in water distribution networks: A review.” Procedia Eng. 89: 181–188. https://doi.org/10.1016/j.proeng.2014.11.175.
Rossman, L. A., et al. 2000. EPANET 2: Users manual. Cincinnati: USEPA, Office of Research and Development.
Rossman, L. A., and P. F. Boulos. 1996. “Numerical methods for modeling water quality in distribution systems: A comparison.” J. Water Resour. Plann. Manage. 122 (2): 137–146. https://doi.org/10.1061/(ASCE)0733-9496(1996)122:2(137).
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: ASCE. https://doi.org/10.1061/9780784412947.099.
Shang, F., J. G. Uber, and M. M. Polycarpou. 2002. “Particle backtracking algorithm for water distribution system analysis.” J. Environ. Eng. 128 (5): 441–450. https://doi.org/10.1061/(ASCE)0733-9372(2002)128:5(441).
Shang, F., J. G. Uber, L. A. Rossman, and R. Janke. 2008. Epanet multi-species extension user’s manual. Washington, DC: USEPA.
Shastri, Y., and U. Diwekar. 2006. “Sensor placement in water networks: A stochastic programming approach.” J. Water Resour. Plann. Manage. 132 (3): 192–203. https://doi.org/10.1061/(ASCE)0733-9496(2006)132:3(192).
Summers, T. H., F. L. Cortesi, and J. Lygeros. 2016. “On submodularity and controllability in complex dynamical networks.” IEEE Trans. Control Network Syst. 3 (1): 91–101. https://doi.org/10.1109/TCNS.2015.2453711.
Summers, T. H., and J. Lygeros. 2014. “Optimal sensor and actuator placement in complex dynamical networks.” IFAC Proc. Volumes 47 (3): 3784–3789. https://doi.org/10.3182/20140824-6-ZA-1003.00226.
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-15.
Trefethen, L. N., and D. Bau III. 1997. Vol. 50 of Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics.
Tzoumas, V., A. Jadbabaie, and G. J. Pappas. 2016. “Sensor placement for optimal Kalman filtering: Fundamental limits, submodularity, and algorithms.” In Proc., American Control Conf., 191–196. Piscataway, NJ: IEEE. https://doi.org/10.1109/ACC.2016.7524914.
Wang, S. 2021. “Shenwang9202/water-quality-modeling-and-sensor-placement.” Accessed March 12, 2021. https://github.com/ShenWang9202/Water-Quality-Modeling-and-Sensor-Placement.
Wang, S., A. F. Taha, and A. A. Abokifa. 2020. “How effective is model predictive control in real-time water quality regulation? State-space modeling and scalable control.” Water Resour. Res. 56: e2020WR027771. https://doi.org/10.1029/2020WR027771.
Winter, C., V. R. Palleti, D. Worm, and R. Kooij. 2019. “Optimal placement of imperfect water quality sensors in water distribution networks.” Comput. Chem. Eng. 121 (Feb): 200–211. https://doi.org/10.1016/j.compchemeng.2018.10.021.
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. https://doi.org/10.1061/40569(2001)397.
Yang, Y. J., J. A. Goodrich, R. M. Clark, and S. Y. Li. 2008. “Modeling and testing of reactive contaminant transport in drinking water pipes: Chlorine response and implications for online contaminant detection.” Water Res. 42 (6–7): 1397–1412. https://doi.org/10.1016/j.watres.2007.10.009.
Zhang, H., R. Ayoub, and S. Sundaram. 2017. “Sensor selection for Kalman filtering of linear dynamical systems: Complexity, limitations and greedy algorithms.” Automatica 78: 202–210. https://doi.org/10.1016/j.automatica.2016.12.025.
Zhang, Q., F. Zheng, Z. Kapelan, D. Savic, G. He, and Y. Ma. 2020. “Assessing the global resilience of water quality sensor placement strategies within water distribution systems.” Water Res. 172: 115527. https://doi.org/10.1016/j.watres.2020.115527.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 147 • Issue 7 • July 2021
Copyright
© 2021 American Society of Civil Engineers.
History
Received: Jul 8, 2020
Accepted: Dec 7, 2020
Published online: May 12, 2021
Published in print: Jul 1, 2021
Discussion open until: Oct 12, 2021
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.