Identifying Sets of Key Nodes for Placing Sensors in Dynamic Water Distribution Networks
This article has a reply.
VIEW THE REPLYThis article has a reply.
VIEW THE REPLYPublication: Journal of Water Resources Planning and Management
Volume 134, Issue 4
Abstract
The design of a sensor-placement scheme capable of detecting all possible contamination events for a water distribution system before consumers are put at risk is essentially impossible given current technologies and budgets. It is, however, possible to design sensor-placement schemes that optimize related objectives (e.g., minimize expected volume of contaminated water consumed prior to detection), but this requires the availability of hydraulic and water quality models for the distribution network and significant computational power, which are the main obstacles to the identification of optimal sensor locations. This paper describes a different approach that reduces the problem’s complexity by expressing a water distribution system as different graphs based on the information readily available from most, if not all, water utilities. The approach provides critical policy and decision support for utilities when hydraulic and water quality models are not available and/or when simulation-based techniques are computationally infeasible.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This work was funded by the National Science Foundation under Grant No. NSFBES-0329549. The writers wish to thank Kathleen Carley and her group at Carnegie Mellon University for all their help in doing the network analysis, Andreas Krause for providing the WaterSim software package for evaluating sensor placement performance, and the BWSN organizers for providing the network.
References
Banavar, J. R., Colaiori, F., Flammini, A., Maritan, A., and Rinaldo, A. (2000). “Topology of the fittest transportation network.” Phys. Rev. Lett., 84(20), 4745–4748.
Berry, J. W., Fleischer, L., Hart, W. E., Phillips, C. A., and Watson, J. (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., Uber, J. G., and Watson, J. (2006). “Sensor placement in municipal water networks with temporal integer programming models.” J. Water Resour. Plann. Manage., 132(4), 218–224.
Blumsack, S. A. (2006). “Network topologies and transmission investment under electric-industry restructuring.” Ph.D. thesis, Dept. of Engineering and Public Policy, Carnegie Mellon Univ., Pittsburgh.
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., and Hwang, D. U. (2006). “Complex networks: Structure and dynamics.” Phys. Rep., 424(4-5), 175–308.
Borgatti, S. P. (2006). “Identifying sets of key players in a social network.” Comput. Math. Org. Theory, 12(1), 21–34.
Carley, K., and De Reno, M. (2006). “ORA: Organization risk analyzer, ORA user’s guide.” ⟨http://www.casos.cs.cmu.edu/publications/papers.php⟩ (Nov. 12, 2006).
Cormen, T. H., Leiserson, C. E., and Rivest, R. L. (1997). Introduction to algorithms, 1st Ed., McGraw-Hill, New York.
Crucitti, P., Latora, V., and Porta, S. (2006a). “Centrality in networks of urban streets.” Chaos, 16(1), 015113.
Crucitti, P., Latora, V., and Porta, S. (2006b). “Centrality measures in spatial networks of urban streets.” Phys. Rev. E, 73(3), 036125.
Drezner, Z., and Hamacher, H. (2002). Facility location: Applications and theory, Springer, Berlin.
Faloutsos, M., Faloutsos, P., and Faloutsos, C. (1999). “On power-law relationships of the internet topology.” Comput. Commun. Rev., 29(4), 251–262.
Freeman, L. C. (1977). “A set of measures of centrality based on betweenness.” Sociometry, 40(1), 35–41.
Gould, R. V. (1987). “Measures of betweenness in nonsymmetric networks.” Soc. Networks, 9, 277–282.
Grayman, W. M., Ostfeld, A., and Salomons, E. (2006). “Locating monitors in water distribution systems: Red team-blue team exercise.” J. Water Resour. Plann. Manage., 132(4), 300–304.
Gueli, R. (2006). “Predator-prey model for discrete sensor placement.” Proc., Conf. on Water Distribution Systems Analysis, the 8th Annual Int. Water Distribution Systems Analysis Symp.
Kessler, A., Ostfeld, A., Sinai, G. (1998). “Detecting accidental contaminations in municipal water networks.” J. Water Resour. Plann. Manage., 124(4), 192–198.
Krause, A., et al. (2006). “Optimizing sensor placements in water distribution systems using submodular function maximization.” Proc., Conf. on Water Distribution Systems Analysis, the 8th Annual Int. Water Distribution Systems Analysis Symp.
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. L., Wolsey, L., and Fisher, M. (1978). “An Analysis of the approximations for maximizing submodular set functions.” Math. Program., 14, 268–294.
Newman, M. E. J. (2004). “Fast algorithm for detecting community structure in networks.” Phys. Rev. E, 69(6), 066133.
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., Uber, J., Salomons, E. (2006). “Battle of the water sensor networks (BWSNs): A design challenge for engineers and algorithms.” Proc., Conf. on Water Distribution Systems Analysis, the 8th Annual Int. Water Distribution System Analysis Symp.
Propato, M. (2006). “Contamination warning in water networks: General mixed-integer linear models for sensor location design.” J. Water Resour. Plann. Manage., 132(4), 225–233.
Shastri, Y., and Diwekar, U. (2006). “Sensor placement in water networks: A stochastic programming approach.” J. Water Resour. Plann. Manage., 132(3), 192–203.
Su, Y., Mays, L. W., Duan, N., and Lansey, K. E. (1987). “Reliability-based optimization model for water distribution systems.” J. Hydraul. Eng., 113(12), 1539–1556.
Todini, E., and Pilati, S. (1987). “A gradient method for the analysis of pipe networks.” Proc., Int. Conf. on Computer Application for Water Supply and Distribution.
Wagner, J. M., Shamir, U., and Marks, D. H. (1988a). “Water distribution reliability: Analytical methods.” J. Water Resour. Plann. Manage., 114(3), 253–275.
Wagner, J. M., Shamir, U., and Marks, D. H. (1988b). “Water distribution reliability: Simulation methods.” J. Water Resour. Plann. Manage., 114(3), 276–294.
Wasserman, S., and Faust, K. (1994). Social network analysis: Methods and applications, 1st Ed., Cambridge University Press, New York.
Watson, J., Greenberg, H. J., and Hart, W. E. (2004). “A multiple-objective analysis of sensor placement optimization in water networks.” Proc., 2004 World Water and Environmental Resources Congress: Critical Transitions in Water and Environmental Resources Management, 4609–4618.
Information & Authors
Information
Published In
Journal of Water Resources Planning and Management
Volume 134 • Issue 4 • July 2008
Pages: 378 - 385
Copyright
© 2008 ASCE.
History
Received: Dec 21, 2006
Accepted: Oct 18, 2007
Published online: Jul 1, 2008
Published in print: Jul 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.