Elsevier

Computers & Chemical Engineering

Volume 43, 10 August 2012, Pages 191-199
Computers & Chemical Engineering

Optimal sensor deployment in a large-scale complex drinking water network: Comparisons between a rule-based decision support system and optimization models

https://doi.org/10.1016/j.compchemeng.2012.03.012Get rights and content

Abstract

Many models or algorithms have been suggested for sensor placement in the drinking water distribution networks, such as genetic algorithms, multiobjective optimization models, and heuristic methods. Because these models or algorithms have high computational demands, however, the requirement of expensive technical computing software is unavoidable. This study presents a rule-based decision support system (RBDSS) to analyze and generate a set of sensor placement locations and compares the performance against 10 optimization models based on four indexes. Our findings show that the RBDSS demands relatively lower computational time and still exhibits outstanding performance in terms of all our indexes when dealing with a large-scale complex drinking water network.

Highlights

► Rule-based decision support system. ► Sensor placement. ► Water distribution network.

Introduction

In the past, the water distribution systems were normally considered the most vulnerable component of drinking water networks because not only are they large, spatially distributed infrastructures, but they also lack monitoring and security (Clark and Deininger, 2001, NRC, 2002). Hence, following the terrorist attack on September 11, 2001, a vulnerability assessment of drinking water distribution networks has been the research focus of the United States Environmental Protection Agency (US EPA, 2010a). Since then, many rigorous research efforts have been directed toward water security issues to search for optimal sensor deployment locations to protect populations from consuming contaminated water. To optimize sensor deployment options, the development of robust models or algorithms to achieve efficient and effective water monitoring performance in an early warning system (EWS) is deemed necessary to protect the population from exposure to contaminated drinking water systems (US EPA, 2009).

Methodologies for layout design of water quality monitoring stations throughout the drinking water distribution systems to detect the migration of contaminants of concern have been widely proposed (Al-Zahrani and Moied, 2001, Berry et al., 2003, Berry et al., 2005, Berry et al., 2004, Berry et al., 2006, Haught et al., 2003, Kessler et al., 1998, Ostfeld and Salomons, 2004, Preis et al., 2007, Propato, 2006, Propato et al., 2003, Woo et al., 2001). Ideally, a large number of sensors would increase the monitoring coverage of a network, but it would also increase cost associated with planning, design, and operation accordingly. In August 2006, “The Battle of the Water Sensor Network (BWSN): A Design Challenge for Engineers and Algorithms” workshop was held as part of the Eight Annual Water Distribution Systems Analysis (WDSA) Symposium in Cincinnati, Ohio. Two actual water distribution networks, Network 1 (Fig. 1) and Network 2 (Fig. 2) representing a small and large water distribution systems, respectively, were used for sensor deployment with respect to four objectives: expected time of detection (Z1), expected population affected prior to detection (Z2), expected consumption of contaminant water prior to detection (Z3), and detection likelihood (Z4). The objectives were employed simultaneously to evaluate the performance of sensor deployment locations of 14 different suggested models and algorithms. All 14 models and algorithms successfully proposed a distinctive set of sensor locations for Network 1 consisting of 126 nodes, 1 source, 2 tanks, 168 pipes, 2 pumps, and 8 valves.

In contrast to Network 1, Network 2, which consists of 12,523 nodes, 2 sources, 2 tanks, 14,822 pipes, 4 pumps, and 5 valves, presented difficulties to some algorithms due to significantly larger water distribution and higher complexity. Hence, only 10 models and algorithms were proposed for Network 2. The primary difficulty in analyzing a large-scale network is the limitation of available computing resources (e.g., available memory); computer memory and computational time requirements remain the main obstacles (Aral, Guan, & Marslia, 2010). Although many studies have demonstrated the ability to solve a large-scale network, their approaches can be easily utilized by the potential end-users in drinking water industry (Hart and Murray, 2010). For instance, mixed-integer linear programing (MILP) models cannot be applied to Network 2 in their practices because they have higher uncertainty due to a longer run-times and cannot process larger water distribution networks due to the limitation of “NP complete” issues that imply an extremely heavy computational loading would appear as the size of larger water distribution networks goes bigger (Propato and Piller, 2006). In addition, the application of Network 2 was not well addressed by using a multiobjective evaluation with a predator–prey model; the model must be adapted to a new scenario to overcome potential obstacles regarding specialization, disengagement, or cycling during coevolution (Gueli, 2006). The rule-based decision support system has been developed and applied in small water distribution networks, such as Network 1 in BWSN, to generate a set of candidacy nodes for sensor placement based on flow rate distribution, the density of node location, and contamination concentration distribution of a specific simulated event. Given the difficulties encountered by other proposed algorithms and models when focusing on large-scale complex systems such as Network 2, the objective of this study is to demonstrate the robustness, effectiveness, and efficacy of a rule-based decision support system (RBDSS) algorithm in dealing with a large-scale complex water distribution system for sensor deployment. To achieve this goal, RBDSS was applied to analyze Network 2 using a finite number of 20 sensors (Case N2A20), in BWSN, to generate a set of sensor deployment locations. The outcomes were then compared against the performance of sensor deployment locations via the BWSN-software utilities in relation to the other 10 models and algorithms based on the four objectives, Z1–Z4.

Section snippets

The principle of rule-based decision support system and algorithms

RBDSS is designed to help users choose the appropriate decision based on established rules, but this computer-base information system gives users flexibility by allowing decision makers to select input to meet their requirements and to fully explore the relationships between criteria, alternatives, methods available, and outcomes of the selection process (Deng and Wibowo, 2008). RBDSS is widely applied to support business and organizational decision-making, and it has clearly organized

Case study of Network 2 in BWSN

The methodology was divided into data collection, simulation analysis, weight assignment, rule base screening and node prioritization, design of sensor deployment locations, and evaluation of sensor locations with comparisons (Fig. 4). In this process, 1 represents the case when node i is selected, and 0 represents the case when the same node is excluded in a simulation scenario. The string with a combination sequence of 0 and 1 represents one snapshot in a simulation run screening a large

Results and discussion

Because Network 2 is too large to easily display all sensor locations, it was divided into 10 sections (Fig. 5). With the inclusion of the accessibility rule, the top 10 rankings of sensor deployment locations are 636, 1798, 1924, 3070, 3524, 3684, 4185, 4594, 5631, and 10,502. With the inclusion of the complexity rule, the top 10 rankings of the locations are 176, 1135, 3229, 4406, 4919, 5097, 6483, 7908, 8025, and 8900. Specifically, there are 4, 2, 1, 1, 3, 2, 6, and 1 sensor(s) assigned to

Conclusions

Sensor placement issues in drinking water distribution systems have been the focus in many water quality monitoring studies due to the vulnerability of these networks to malicious terrorist attack or epidemiological incidences that can potentially risk consumers’ health. At a practical level, general guidelines for sensor placement must be set to draw a final design. Four indexes, including the expected time of detection (Z1), the expected population affected prior to detection (Z2), the

Acknowledgments

The contributions and supports from previous work, Salomons (2006), are gratefully acknowledged. The authors acknowledge the constructive comments from all anonymous reviewers.

References (38)

  • N.B. Chang et al.

    Comparisons between a rule-based expert system and optimization models for sensor deployment in a small drinking water network

    Expert System with Application

    (2011)
  • M. Al-Zahrani et al.

    Locating optimum water quality monitoring stations in water distribution system

  • M.M. Aral et al.

    Optimal design of sensor placement in water distribution networks

    Journal of Water Resources Planning and Management

    (2010)
  • J.W. Berry et al.

    Sensor placement in municipal water networks

  • J.W. Berry et al.

    Sensor placement in municipal water networks

    Journal of Water Resources Planning and Management Division, ASCE

    (2005)
  • J. Berry et al.

    A general integer-programming based framework for sensor placement in municipal water networks

  • J.W. Berry et al.

    Sensor placement in municipal water networks with temporal integer programming models

    Journal of Water Resources Planning and Management Division, ASCE

    (2006)
  • N.B. Chang et al.

    A rule-based decision support system for sensor deployment in small drinking water networks

    Journal of Cleaner Production

    (2012)
  • R.M. Clark et al.

    Minimizing the vulnerability of water supplies to natural and terrorist treats

  • H. Deng et al.

    A rule-based decision support system for evaluating and selecting IS projects

  • J. Deuerlein et al.

    Reliability analysis of water distribution system using graph decomposition

  • G. Dorini et al.

    An efficient algorithm for sensor placement in water distribution systems

  • D. Eliades et al.

    Iterative deepening of Pareto solutions in water sensor networks

  • S.R. Ghimire et al.

    Heuristic method for the battle of the water network sensors: Demand-based approach

  • S.R. Ghimire et al.

    A heuristic method for water quality sensor location in a municipal water distribution system: Mass related based approach

  • J. Guan et al.

    Optimization model and algorithms for design of water sensor placement in water distribution systems

  • R. Gueli

    Predator–prey model for discrete sensor placement

  • W.E. Hart et al.

    Review of sensor placement strategies for contamination warning system in drinking water distribution systems

    Journal of Water Resources Planning and Management

    (2010)
  • R.C. Haught et al.

    Evaluation of water monitoring instrumentation at EPA's water awareness technology evaluation research security center

  • Cited by (40)

    • A general-purpose method for Pareto optimal placement of flow rate and concentration sensors in networked systems – With application to wastewater treatment plants

      2020, Computers and Chemical Engineering
      Citation Excerpt :

      In the process, the search is limited to the set of sensor layouts that make a predefined set of variables of interest observable. The relative improvement of precision is one way among many to evaluate practical observability (e.g., Waldraff et al., 1998; Chmielewski et al., 2002; Chang et al., 2012; Serpas et al., 2013; Mukherjee et al., 2017; Rico-Ramirez et al., 2007; Joshi and Boyd, 2008; Soldevila et al., 2018; de Winter et al., 2019; Nahar et al., 2019). The approach of Le et al. (2018) is based on the analysis of systems of linear equations, meaning that measuring a concentration in a single stream implies measurement of the flow rate in the same stream.

    • Quantitative decision making for a groundwater monitoring and subsurface contamination early warning network

      2019, Science of the Total Environment
      Citation Excerpt :

      Masoumi and Kerachian (2010) and Lee et al. (2014) used discrete entropy theory to quantify the efficiency of sample locations and frequencies. Chang et al. (2012) discussed an optimal monitoring network design by utilizing existing data to estimate the uncertainties for the potential locations which could be used as a criterion to determine the number of monitoring wells and estimate the efficiency of the future system. An overview of the decision-making process of the Colorado Water Watch is shown in Fig. 1.

    • Quality-of-sensing aware budget constrained contaminant detection sensor deployment in water distribution system

      2018, Journal of Network and Computer Applications
      Citation Excerpt :

      Erol-Kantarci and Mouftah (2011) consider local energy generation capability, prioritized appliances, and for real-time pricing. Chang et al., (2012a, 2012b) study on how to maximize the total population being protected by sensor detection with the consideration budget requirements. However, most existing work only considers a single type of sensors to be deployed in the WDS.

    • Actuator network design to mitigate contamination effects in Water Distribution Networks

      2018, Computers and Chemical Engineering
      Citation Excerpt :

      These actuators can be used to enforce a shutdown of the network by isolating the source nodes from the demand nodes following a sensor response so as to prevent further spread of the contaminant. Graph theoretic approaches have already been demonstrated to be useful in the instrumentation of networks, be it process or water (Nguyen and Bagajewicz, 2008; Bhushan and Rengaswamy, 2000; Chang et al., 2012). Here the actuator placement problem is mapped to a graph partitioning problem such that all source nodes are in one set (partition), and all demand nodes are in another set.

    View all citing articles on Scopus
    View full text