Steady-State Hydraulic Analysis Based on Cellular Automata Using a Parallel Paradigm
Publication: Journal of Water Resources Planning and Management
Volume 148, Issue 11
Abstract
Analysis of water distribution networks (WDNs) is considered to be indispensable for water supply design. Over the last decades, several methods have been developed to formulate and solve the steady-state hydraulic analysis of WDNs. For large WDNs, modeling the networks is complex and takes a great deal of time, and using the traditional methods becomes practically inefficient. This paper presents a parallel paradigm based on cellular automata to accelerate the hydraulic analysis of WDNs. The structure of the computing system is generated according to the structure of the WDN using the concept of cellular automata. Two methods are proposed for solving the hydraulic models. The performance of the proposed approach was compared with that of EPANET 2.0 software for networks with different complexity and topologies. The results indicate that, despite requiring more iterations to converge, the proposed parallel algorithm can accelerate the hydraulic analysis as much as 105 times using the proposed methods.
Practical Applications
WDNs analysis under steady-state conditions is used widely in applications such as network design and leak detection in WDNs. In these applications, it is necessary to solve hydraulic equations of the WDN under different scenarios to obtain the desired answer. As the size of the WDN increases, the time required to solve the equations increases accordingly. This paper presents a parallel paradigm to accelerate the hydraulic analysis of WDNs. The results indicate that the proposed parallel algorithm can accelerate the hydraulic analysis, thus reducing the network design time and determining the location of leaks in the WDN with greater speed and accuracy. Consequently, more money, time, and water can be saved. In addition, this acceleration may allow engineers to find new ways to solve their problems, or even to provide solutions to problems that in the past could not be solved with existing facilities.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
The input data, models, and code that support the findings of this study for the Fossolo network are available at https://github.com/afarghadan/WDNs_Model. Other networks can be run by changing the input file.
References
Abraham, E., and I. Stoianov. 2015. “Efficient preconditioned iterative methods for hydraulic simulation of large scale water distribution networks.” Procedia Eng. 119 (Aug): 623–632. https://doi.org/10.1016/j.proeng.2015.08.915.
Afshar, M. H. 2013. “A cellular automata approach for the hydro-power operation of multi-reservoir systems.” In Proc., Institution of Civil Engineers-Water Management, 465–478. New York: Thomas Telford.
Afshar, M. H., and R. Hajiabadi. 2019. “Multi-objective optimisation using cellular automata: Application to multi-purpose reservoir operation.” Civ. Eng. Environ. Syst. 36 (2–4): 115–132. https://doi.org/10.1080/10286608.2019.1604691.
Aleksandrov, V., and H. Samuel. 2010. The Schur complement method and solution of large-scale geophysical problems. Bayreuth, Germany: Bayerisches Geoinstitut (BGI). https://karel.troja.mff.cuni.cz/documents/2010-ML-Aleksandrov.pdf.
Burks, A. W. 1970. Essays on cellular automata. Urbana, IL: Univ. of Illinois Press.
Cross, H. 1936. Analysis of flow in networks of conduits or conductors. Urbana, IL: Univ. of Illinois at Urbana Champaign.
Crous, P. 2009. Application of stream processing to hydraulic network solvers. Johannesburg, South Africa: Univ. of Johannesburg.
Crous, P. A., J. E. van Zyl, and Y. Roodt. 2012. “The potential of graphical processing units to solve hydraulic network equations.” J. Hydroinf. 14 (3): 603–612. https://doi.org/10.2166/hydro.2011.023.
Diao, K., Z. Wang, G. Burger, C.-H. Chen, W. Rauch, and Y. Zhou. 2014. “Speedup of water distribution simulation by domain decomposition.” Environ. Modell. Software 52 (9): 253–263. https://doi.org/10.1016/j.envsoft.2013.09.025.
Elhay, S., O. Piller, J. Deuerlein, and A. R. Simpson. 2016. “A robust, rapidly convergent method that solves the water distribution equations for pressure-dependent models.” J. Water Resour. Plann. Manage. 142 (2): 04015047. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000578.
George, A., and J. W. Liu. 1981. computer solution of large sparse positive definite. Hoboken, NJ: Prentice Hall Professional Technical Reference.
Georgoudas, I. G., P. Kyriakos, G. C. Sirakoulis, and I. T. Andreadis. 2010. “An FPGA implemented cellular automaton crowd evacuation model inspired by the electrostatic-induced potential fields.” Microprocess. Microsyst. 34 (6): 285–300. https://doi.org/10.1016/j.micpro.2010.06.001.
Gilbert, J. R., and T. Peierls. 1988. “Sparse partial pivoting in time proportional to arithmetic operations.” SIAM J. Sci. Stat. Comput. 9 (5): 862–874. https://doi.org/10.1137/0909058.
Gorev, N. B., V. N. Gorev, I. F. Kodzhespirova, I. A. Shedlovsky, and P. Sivakumar. 2021. “Technique for the pressure-driven analysis of water distribution networks with flow- and pressure-regulating valves.” J. Water Resour. Plann. Manage. 147 (5): 06021005. https://doi.org/10.1061/(ASCE)WR.1943-5452.0001357.
Guidolin, M., Z. Kapelan, and D. Savic. 2013. “Using high performance techniques to accelerate demand-driven hydraulic solvers.” J. Hydroinf. 15 (1): 38–54. https://doi.org/10.2166/hydro.2012.198.
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 (Feb): 165–175. https://doi.org/10.1016/j.watres.2018.06.041.
Isaacs, L. T., and K. G. Mills. 1980. “Linear theory methods for pipe network analysis.” J. Hydraul. Div. 106: 1191–1201.
Ivetic, D., Ž. Vasilić, M. Stanić, and D. Prodanović. 2015. “Speeding up the water distribution network design optimization using the ΔQ method.” J. Hydroinf. 18 (Sep): 33–48. https://doi.org/10.2166/hydro.2015.118.
Kalogeropoulos, G., G. C. Sirakoulis, and I. Karafyllidis. 2013. “Cellular automata on FPGA for real-time urban traffic signals control.” J. Supercomput. 65 (2): 664–681. https://doi.org/10.1007/s11227-013-0952-5.
Kang, D., and K. Lansey. 2012. “Revisiting optimal water-distribution system design: Issues and a heuristic hierarchical approach.” J. Water Resour. Plann. Manage. 138 (Jun): 208–217. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000165.
Liu, H., D. A. Savić, Z. Kapelan, E. Creaco, and Y. Yuan. 2017. “Reliability surrogate measures for water distribution system design: Comparative analysis.” J. Water Resour. Plann. Manage. 143 (1): 04016072. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000728.
Martin, D. W., and G. Peters. 1963. “The application of Newton’s method to network analysis by digital computer.” J. Inst. Water Eng. 17 (2): 115–129.
Modanese, A. 2020. “Complexity-theoretic aspects of expanding cellular automata.” Nat. Comput. 21: 53–65. https://doi.org/10.1007/s11047-020-09814-2.
Moosavian, N. 2017. “Multilinear method for hydraulic analysis of pipe networks.” J. Irrig. Drain. Eng. 143 (8): 04017020. https://doi.org/10.1061/(ASCE)IR.1943-4774.0001193.
Moosavian, N., and M. R. Jaefarzadeh. 2014. “Hydraulic analysis of water distribution network using shuffled complex evolution.” J. Fluids 2014: 979706. https://doi.org/10.1155/2014/979706.
Ormsbee, L. E. 2008. “The history of water distribution network analysis: The computer age.” In Proc., Water Distribution Systems Analysis Symp. 2006, 1–6. Reston, VA: ASCE. https://doi.org/10.1061/9780784409411.
Peinado, J., and A. M. Vidal. 2004. “Three parallel algorithms for solving nonlinear systems and optimization problems.” In Proc., Int. Conf. on High Performance Computing for Computational Science, 657–670. Berlin: Springer.
Rosin, P., A. Adamatzky, and X. Sun. 2014. Cellular automata in image processing and geometry. Berlin: Springer.
Rossman, L. A. 2000. EPANET 2 users manual. Cincinnati, OH: National Risk Management Research Laboratory.
Salgado, R., E. Todini, and P. E. O’Connell. 1988. “Extending the gradient method to include pressure regulating valves in pipe networks.” In Proc., Int. Symp. on Computer Modelling of Water Distribution Systems, 12–13. Berlin: Springer.
Shamir, U., and C. D. D. Howard. 1977. “Engineering analysis of water-distribution systems.” Journal 69: 510–514.
Todini, E. 2008. “On the convergence properties of the different pipe network algorithms.” In Proc., Water Distribution Systems Analysis Symp. 2006, 1–16. Reston, VA: ASCE. https://doi.org/10.1061/9780784409411.
Todini, E., and S. Pilati. 1988. “A gradient algorithm for the analysis of pipe networks.” In Computer applications in water supply: Systems analysis and simulation. Somerset, UK: Research Studies Press.
Todini, E., and L. A. Rossman. 2013. “Unified framework for deriving simultaneous equation algorithms for water distribution networks.” J. Hydraul. Eng. 139 (5): 511–526. https://doi.org/10.1061/(ASCE)HY.1943-7900.0000703.
Toselli, A., and O. Widlund. 2006. Domain decomposition methods-algorithms and theory. Berlin: Springer.
University of Exeter. 2018. “Benchmarks.” Accessed September 3, 2022. https://engineering.exeter.ac.uk/research/cws/resources/benchmarks.
van Zyl, J. E., P. Kumar, and M. Gupta. 2008. “Two-point linearization method for the analysis of pipe networks.” J. Hydraul. Eng. 134 (8): 1176–1179. https://doi.org/10.1061/(ASCE)0733-9429(2008)134:8(1176).
Wang, Q., M. Guidolin, D. Savic, and Z. Kapelan. 2015. “Two-objective design of benchmark problems of a water distribution system via MOEAs: Towards the best-known approximation of the true Pareto front.” J. Water Resour. Plann. Manage. 141 (3): 04014060. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000460.
Yan, H., Q. Wang, J. Wang, K. Xin, T. Tao, and S. Li. 2019. “A simple but robust convergence trajectory controlled method for pressure driven analysis in water distribution system.” Sci. Total Environ. 659 (Apr): 983–994. https://doi.org/10.1016/j.scitotenv.2018.12.374.
Zecchin, A. C., P. Thum, A. R. Simpson, and C. Tischendorf. 2012. “Steady-state behavior of large water distribution systems: Algebraic multigrid method for the fast solution of the linear step.” J. Water Resour. Plann. Manage. 138 (Apr): 639–650. https://doi.org/10.1061/(ASCE)WR.1943-5452.0000226.
Zheng, F., A. C. Zecchin, J. P. Newman, H. R. Maier, and G. C. Dandy. 2017. “An adaptive convergence-trajectory controlled ant colony optimization algorithm with application to water distribution system design problems.” In IEEE transactions on evolutionary computation, 773–791. New York: IEEE.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 148 • Issue 11 • November 2022
Copyright
© 2022 American Society of Civil Engineers.
History
Received: Dec 1, 2021
Accepted: Jul 9, 2022
Published online: Sep 14, 2022
Published in print: Nov 1, 2022
Discussion open until: Feb 14, 2023
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.