Optimal Design of Sensor Placement in Water Distribution Networks

The recent terrorism concerns have caused emergency management personnel and public health officials to devote attention to the security of infrastructure systems in the United States and around the world (Congressional Research Service 2002). Since the water supply infrastructures are not built to withstand an intentional attack, they are vulnerable to external attacks (House Science Committee 2001). Since the occurrence of the recent terrorism events, various preventative measures have been enacted. However, because these measures depend on a lengthy response time, they are sorely inadequate and fail to provide an early warning or instantaneous notification that would be required for an intentional attack. Thus, to be protective of public health, water distribution system security requires faster detection methods and response of a computerized control network—an early warning detection system—to an intentional attack.

Reducing or minimizing the vulnerability of water distribution systems require the implementation of a detection system that can (1) assure that any degradation in water quality is quickly identified and (2) rapid assessments can be made identifying areas of the distribution system that have been impacted. For this purpose a well-designed water sensor network system is necessary to detect the contamination events in minimum time reducing the risk of prolonged exposure. The design of this water sensor network deals with several factors such as cost, reliability of the designed system, detection time, and the population exposed. A good design should provide an acceptable trade-off among these competing factors.

More recently a special session entitled “Battle of the Water Sensors Network” (BWSN 2006) was dedicated to this issue during the conference of WDSA (2006) held in Cincinnati. The special session included 14 papers addressing this problem and the researchers provided solutions to this problem using different methods and different points of view (BWSN 2006). In this paper we also provide a comparison of the results presented in this study with the outcome provided by the writers of the other studies, as referenced above.

Prior to the recent terrorism events, the scientific literature primarily focused on assessing water quality monitoring networks in terms of efficiency and cost to guarantee a reliable supply of potable water to the public. Ostfeld and Salomons (2004) provided a review of this literature, which will not be repeated here owing to brevity. Recently, the literature has been focused more on the optimal layout of early warning detection systems with respect to intentional biological or chemical attacks and assessment of the risk to population exposure (Bahadur et al. 2001; Bahadur et al. 2003; Ostfeld and Salomons 2004, 2006). For a comprehensive resource on security of water supply systems, the reader is also referred to Mays (2004). More recently, the optimal sensor network design problem was discussed in the BWSN session of the conference WDSA (2006), as referenced above. These studies provided 14 different approaches to the solution of the sensor placement problem. We provide a comparison of the results of these designs in this study using standardized analysis of the results with respect to the criteria identified for the BWSN exercise. However, the reader is referred to the conference proceeding (BWSN 2006) for further details of each design consideration discussed in these 14 applications.

The design of an effective water sensor network may be formulated as an optimization model. A variety of models and solution algorithms, including integer programming methods and combinatorial heuristics, have been developed and reported in the literature. A detailed review of mixed-integer programming models to determine the placement of contaminant sensors within a municipal water network can be found in Berry et al. (2005) and Propato (2006). As the objective function, these models use the concept of minimization of the expected population that is at risk for an attack and solve the problem using intelligent variations of branch and bound approaches. Ostfeld and Salomons (2004) proposed a two-stage approach to determine the optimal layout of an early warning detection stations in the water distribution system. In their methodology a randomized pollution matrix (RPN) was constructed based on random injection events and a genetic algorithm was used to obtain maximum column coverage of the RPN. Although both of these approaches are effective, they may not provide an effective and efficient solution for large-scale water distribution systems because of the heavy computational burden they may require.

In the optimal placement of sensors in a network, the objective function selected directly influences the sensor placement location in the system. In most models that are used in the literature a single objective is selected for this purpose. For example: (1) minimizing total contaminated volume consumed (Kessler et al. 1998); (2) minimizing the time of detection (Kumar et al. 1999); (3) maximizing detection coverage and probability (Ostfeld and Salomons 2004); or (4) minimizing population affected by contamination (Berry et al. 2005). Actually the optimal water sensor placement problem is a multiobjective decision problem. To the best of our knowledge, there are a few reported models in the literature that use a multiobjective solution approach for this application (Watson et al. 2004; Ostfeld and Salomons 2004; Propato 2006). Perhaps the reason lies in the fact that the optimization algorithm may tend to be extremely inefficient for an integer programming solution containing thousands of variables which would be the case for a large water distribution system in some cases and in other cases where multiple feasible solutions are provided, a selection of the final design is most commonly compromised since the final selection would still reflect the preferences or the point of view of the decision maker. One of the goals of the method proposed in this study is to overcome this dilemma through the formulation of a single synthetic objective function that would mimic the performance of a multiobjective approach. Thus, in this study a single-objective optimization model is developed that incorporates the four criteria adopted in the Battle of the Water Sensors Network (BWSN 2006), as described below. A progressive genetic algorithm (PGA) is used to solve the model to overcome the computational inefficiency issues in the study of the large-scale water distribution networks. The outcome, based on our comparisons with other solutions, is a robust methodology which may be useful in solving this problem effectively.

Two hypothetical networks were supplied for the BWSN application (BWSN 2006) and we will use these two water distribution systems to demonstrate the performance of the model proposed here. The characteristics of these two water distribution systems are given in Table 1.

To evaluate the proposed algorithm’s efficiency and reliability in detecting contamination events using these two networks, four quantitative design objectives were identified, as described in the BWSN exercise:

Expected Time of Detection ${{Z}}_{\mathbf{1}}$ . For a particular contamination scenario, the time of detection by a sensor is defined as the elapsed time from the start of the contamination event to the first presence of a nonzero contaminant concentration at a sensor. This detection time is denoted as $t_i$ where the subscript $i$ refers to the $i\text{th}$ sensor location. The time of detection for the sensor network for a particular random contamination event, $t_d$ , can be identified as the minimum detection time among all sensors present in the design, $t_d=\text{min}$ $t_i$ . In this case the objective function to be minimized is the expected value computed over the assumed probability distribution of random contamination eventswhere $E\left[\cdot \right]=\text{expected}$ value and will be approximated by Monte Carlo simulation for the purpose of comparing alternative designs. The assumed probability distribution of contamination events is discussed below in conjunction with other design assumptions.

Expected Population Affected prior to Detection ${\mathit{Z}}_{\mathbf{2}}$ . For a particular contamination scenario, the population affected is measured as a function of the ingested contaminant mass. The ingested contaminant mass in turn depends on the time of detection for the sensor network, as described above. The key assumption here is that no mass will be ingested after detection since it is assumed that an appropriate response, such as the shutdown of the system, will be initiated at that time. For a particular contamination scenario, the mass ingested—prior to detection—by any individual at network node $i$ can be calculated aswhere $\varphi =\text{mean}$ volumetric ingestion rate (L/day); $\Delta t=\text{time}$ step (days); $c_{ik}=\text{contaminant}$ concentration at junction $i$ at time step $k$ (mg/Liter); ${\rho }_{ik}=\text{dose}$ rate multiplier for junction $i$ at time step $k$ and calculated by ${\rho }_{ik}=q_{ik}/{\overline{q}}_i$ ; ${\overline{q}}_i=\text{average}$ water demand at junction $i$ ; and $N=\text{number}$ of time steps prior to detection.

A typical dose-response model is used to express the probability that any person ingesting mass $M_i$ will be affected (i.e., become infected or symptomatic)where $R_i=\text{probability}$ [0, 1] that a person who ingests contaminant mass $M_i$ will become infected or symptomatic; $\beta =\text{Probit}$ slope parameter (dimensionless); $W=\text{assumed}$ body weight (kg); $D_{50}=\text{dose}$ that would result in a 0.5 probability of becoming infected or symptomatic (mg/kg); and $\Phi =\text{standard}$ normal cumulative distribution function.

Based on this, the population affected for a particular contamination scenario is calculated bywhere $P_i=\text{population}$ assigned to node $i$ ; and $m=\text{total}$ number of junctions. For simplicity, the population can be estimated by the total water demand divided by total per capita water consumption rate. During the design stage, the contamination scenarios will be randomly generated and contamination can occur at any junction and at any time step according to a uniform probability distribution. The more scenarios one considers in this approach, the more reliable the designed water sensor network will be. Of course, the use of a large number of scenarios will increase the computation time and the computer memory requirements. According to this criterion, the measure $Z_2$ is based on the expected value of $P_a$ computed over the assumed probability distribution of contamination eventswhere $E\left[\cdot \right]$ again denotes the expected value and will be approximated by Monte Carlo simulation for purposes of comparing alternative sensor placement designs. The assumed probability distribution of contamination events is discussed below in conjunction with other design assumptions. In the scenarios tested, the contaminant intrusion occurs at a junction of the system with injection flow rate of 125 L/h at a contaminant concentration of 230,000 mg/L and the injection duration is 2 h. The hydraulic and water quality parameters used for these two networks are given in Table 2.

Expected Demand of Contaminated Water prior to Detection ${\mathit{Z}}_{\mathbf{3}}$ . $Z_3$ =expected volume of consumed contaminated water prior to detectionwhere $V_d$ denotes the total volumetric water demand that exceeds a predefined hazard concentration and $E\left[\cdot \right]=\text{expected}$ value, as defined above. As to the expected population affected, the key assumption is that no water is delivered after detection. The objective $Z_3$ (as $Z_2$ and $Z_1$ ) is to be minimized.

Reliability ${\mathit{Z}}_{\mathbf{4}}$ . Given a sensor network design (i.e., number of sensors and sensor locations) the reliability (the probability of detection) is defined aswhere $d_i=1$ if contamination scenario $i$ is detected and zero if otherwise and $N=\text{number}$ of the total contamination scenarios considered. Contrary to the objectives $Z_1$ , $Z_2$ , and $Z_3$ , the objective $Z_4$ is to be maximized.

It is important to note that for all four measures described above, the detection of a contaminant by a sensor is an important part of the computation of the value of the measure. In the optimization protocol proposed in this study, if a contamination scenario is not detected, that event is not ignored but instead the time of detection for that event is set to be the end of the simulation period (i.e., maximum simulation time). The effect of a scenario not being detected is also directly reflected in the reliability measure as well. A good solution should yield lower values of the former three measures and a higher reliability value. As discussed in detail below, the methodology and the procedure developed here strikes a balance between these four measures. It can be stated that in the procedure described here the “trade-off” coefficients of the objective function are defined in terms of the four measures defined above and thus they are optimized as well. This is the most important contribution of the algorithm proposed here.

The performance of the network designed is evaluated using the four criteria given above. These criteria are all compatible in the following sense. In order to reduce the number of exposed population and contaminated water volume, one would attempt to design the system to minimize the detection time and clearly a higher reliability is necessary for the system to be effective. However, it is important to recognize that emphasizing any one of these criteria over the others will result in a different sensor placement pattern for the water distribution network. One alternative to minimize the effect of this dilemma is to use a multiobjective optimization approach. However, the multiobjective approach, in one way or another, will be eventually associated with a trade-off methodology in the selection of the final design. Thus, we start with the premise that there is no single mathematical formulation that would yield all four criteria to reach their true optimal values, which would be otherwise obtained if these criteria were used as a stand alone criterion. Our goal is to identify an objective function that would strike a balance between these four objectives without artificial controls or one that would eventually reflect the preferences of the decision maker in selecting one design among many feasible optimal solutions that may be provided. For this purpose, in this study a single-objective formulation approach is selected. The goal is to blend the four criteria into one objective function as best as possible. To accomplish this, the following objective function is proposed:where $s=\text{index}$ of contamination scenarios or events; $X=\text{decision}$ vector; and $X={\left[x_1,x_2,\cdots ,x_{N_s}\right]}^T$ where $x_i$ =decision variable, $x_i=\left\{0,1\right\}$ . If $x_i=1$ , a sensor is placed at junction $i$ , otherwise there is no sensor placement at junction $i$ . $E_s[\cdot ]$ =expected value of total water demand that exceeds a predefined threshold hazard concentration, $C_{\text{min}}$ in the water distribution system; $t_s^{in}$ =index of injection time at which the contaminant is injected into the system for contamination event $s$ ; $V_{is}\left(t\right)$ =volume of contaminated water consumed at junction $i$ for contamination event $s$ at time step $t$ ; $i$ =index of junctions in the system; $N$ =total number of junctions in the system; $t$ =index of time steps; and $r\left(X\right)$ =reliability measure of event detection (%). If the $N_s$ contamination events are randomly generated with uniform distribution within a specified period, the equation given above can be written aswhere $N_s=\text{number}$ of contamination events. If we identify $t_s^d$ as the time of detection for sensor network for the contamination events $t_s^d$ can be calculated aswhere $j=\text{index}$ of sensors in solution $X$ and $t_{js}=\text{time}$ of detection at sensor $j$ for event $s$ . Then, $t_s^d$ will be an implicit function of $X$ . In the objective function above, Eq. (8a) or (8b), $V_{is}\left(t\right)$ is calculated bywhere $q_i\left(t\right)=\text{water}$ demand at junction $i$ at time step $t$ and $\Delta t=\text{time}$ step interval. The reliability measure $r\left(X\right)$ is determined by the solution vector $X$ . During the optimization process, $r\left(X\right)$ can be approximately estimated by the reliability, which is defined as $d_s=1$ if contamination scenario $s$ is detected and $d_s=0$ if otherwise.

This objective function synthetically reflects the four criteria described above in a unified form. As stated earlier, the population affected is a function of water volume consumed. The minimization of water volume contaminated can directly realize the purpose of reducing the population affected. In the model proposed above, the time of detection directly affects the objective function value through two factors. One is associated with the summation terms, the longer the time of detection is, the more terms there will be in the summation. This results in a larger objective function value which we would be minimizing. The other is associated with the term $\left(t-t_s^{in}+1\right)$ . This term is included as a penalty coefficient. The larger the value of $t$ , the larger the penalty coefficient will be. However, it is clear that this penalty function is not preassigned but minimized as well, as the solution progresses. Thus, the optimal solution is associated with detection time being small, which is the objective of our model. The term $\left[1-r\left(X\right)\right]$ is a coefficient associated with the reliability of the solution. Higher reliability values results in a smaller coefficient. This yields smaller objective function value and vice versa. Again, this coefficient is not a set constant but is also minimized as the optimization process progresses. We anticipate that the optimized results obtained using this objective function may yield a balanced inherent trade-off solution for the four criteria identified above. More important, as emphasized in this study, the bias that exists in the trade-off coefficients defined in the objective function is also optimized as the solution progresses. Thus, the trade-off is based on the balance that can be found among the four objectives of the problem.

In the water distribution system, each junction node may be selected as a candidate location for the installation of a sensor. Installation of more sensors will increase the reliability of the sensor network, albeit at a higher cost. The purpose of optimal design of water sensor network is to determine the number of sensors that are needed and where to place these sensors while satisfying the specified reliability of the system. Explicitly, the number of sensors needed is a function of the specified reliability. Therefore, the following constraint is also considered in the formulation:where $M\left(r_c\right)=\text{number}$ of sensors needed for the specified reliability; $m=\text{specified}$ number of sensors; and $r_c=\text{predefined}$ reliability.

Eq. (13) indicates that the probability of detected events under the condition of a specified number of sensors must be larger than or equal to a given reliability level of the system for the water distribution system security. If Eq. (13) is not included in the model, the optimization problem may be identified as the case where one seeks optimal sensor placement with a specified number of sensors. Otherwise, the optimization problem also identifies the optimal number of sensors necessary and their optimal placement given the reliability constraint. Both optimization problems will be addressed in the numerical applications discussed below.

The optimization model described above is {0,1} integer programming problem. Although the conventional {0,1} integer programming methods, such as branch and bound and enumeration and implicit enumeration, can be used to solve this problem, they may tend to be inefficient for large number of candidate junctions. In recent years, the application of heuristic algorithms is also explored in the solution of these problems. A genetic algorithm was used to design the early warning detection systems by Ostfeld and Salomons (2004). In their study a genetic algorithm framework in integration with the network solver EPANET (Rossman 2000) was proposed and the methodology was demonstrated through two example applications. However, we must emphasize that both example applications studied in their paper contain less than 20 candidate junctions. There is no doubt that the proposed approach is efficient in selecting the sensor locations from 20 candidate junctions. However, if the number of candidate junctions is in the order of thousands, this approach may be inefficient because the crossover operation used in the genetic algorithm may lose its functionality. For example, selecting five-sensor locations from 1,000 candidate junctions, the chromosome with 1,000 bits contains only five bits which has a value “one” and all other bits will be “zero.” With such a chromosome, most of the offspring children generated by the crossover operation may tend to be the same as their parents. In this case, the solution will improve very slowly increasing the computational cost. In this study, the PGA (Guan and Aral 1999; Aral et al. 2001; Guan and Aral 2005; Guan et al. 2006a,b) is used for the solution of the optimization model described above to determine the optimal number of sensors and sensor placements. The PGA works on the subdomain of junctions that is a subset of the complete set of junctions in the water distribution system. The solution of the problem in the subdomain is based on the conventional genetic algorithm procedures and the subdomain selection and subdomain evolution is based on earlier concepts developed by Guan and Aral (1999) and Aral et al. (2001) which will not be repeated here.

For a specified number of sensors, this procedure can also be used to identify the optimal locations of sensors. In this case, the algorithm may be linked to another loop to check if the solution satisfies a predefined reliability constraint [Eq. (13)]. The reliability is estimated by Eq. (11). If the reliability is less than the specified reliability, this would indicate that more sensors are required. If the reliability is larger than the specified reliability, this would imply that the number of sensors may be reduced to save on cost. This process of increasing or decreasing the number of sensors is systematically determined in the proposed algorithm according to the following criteria:where $\epsilon =\text{preselected}$ allowable error. The change in the number of sensors can be approximated bywhere $l=\text{index}$ of iterations; $\Delta M=\text{incremental}$ number of sensors to add or subtract. In the first iteration, $l=0$ , $\Delta M$ may be assigned a valueIn general, the reliability of the system is a monotonically increasing function of the number of sensors and linear interpolation can be used to determine $\Delta M$ . Therefore, in the subsequent iterations $\Delta M$ is determined using the equation belowwhere $\left[\cdot \right]$ yields a ceiling integer value. In Eq. (17), the sign of $\Delta M$ depends on the term $\left[r_c-r^{\left(l\right)}\right]$ if $r$ is monotonically increasing as a function of the number of sensors. If $r_c>r^{\left(l\right)}$ , the sign is positive, the system will increase the number of sensors required. If $r_c>r^{\left(l\right)}$ , the sign is negative, the algorithm will decrease the number of sensors required. However, as described above, the objective function synthetically trades-off the four criteria and may yield a case with $r^{\left(l\right)}⩽r^{\left(l-1\right)}$ under $M^{\left(l\right)}⩾M^{\left(l-1\right)}$ or $r^{\left(l\right)}⩾r^{\left(l-1\right)}$ under $M^{\left(l\right)}⩽M^{\left(l-1\right)}$ . For such cases, $\Delta M$ should be set to the value given by Eq. (16) because it is well known that increasing number of water sensors will increase the reliability of the system.

It must be pointed out that the PGA works on a subset of junctions rather than all junctions. This will improve the efficiency of the genetic algorithm in solving the {0,1} integer programming problem. However, this may result in a local optimal solution. This situation can be progressively overcome through the updating of the subdomain during the iterative solution. The final solution may converge to the global optimal solution as long as all junctions are included into the subdomain at least once.

In the proposed algorithm, the EPANET water distribution system modeling platform is an important component that is used to perform extended-period simulation of hydraulic and water quality behavior within a pressurized pipe network (Rossman 2000). Because these data will be repeatedly used in the evaluation of the objective function, the EPANET simulation is conducted before optimization and the data that are used in the subsequent optimization steps are recovered from the stored data in the computer memory. This approach reduces the computational burden.

The model and the methodology proposed above is used in the solution of the two water distribution networks provided in the BWSN application (BWSN 2006). The performance of the water sensor network designed is synthetically evaluated using the four criteria previously described.

Water Distribution System 1. Network 1 is a relatively simple water distribution system consisting of 169 pipes, 129 junctions, a reservoir, two elevated storage tanks, and two pumping stations (BWSN 2006). For the design of the water sensor network, 20 contamination scenarios for each junction are randomly generated within the first 24 h, resulting in a total of 2,580 scenarios. During the scenario generation stage, the writers did not consider the multiple injection point case since it is assumed that the critical scenario would be the one source case (Case A in BWSN exercise) in view of the objective function selected here. During optimization, the number of candidate junctions in the subdomain was selected as 50 and the number of subdomains as 20. The reliability of the system is specified to be 85%. The candidate junctions are selected using the roulette wheel method based on the detection time. Parameters used in the PGA are given in Table 3.

The case for a specified number of sensors is addressed first. The optimal results obtained for the number of sensors ranging from 5 to 20 are given in Table 4, where $Z_1$ , $Z_2$ , $Z_3$ , and $Z_4$ are the measures identified earlier. In Table 4, the network junction identification (junction ID) is identified with a letter “J” and a number which indicates the junction identifier.

The relation between the number of sensors used and the value of the four measures are shown in Fig. 1. Based on these results, it can be clearly seen that the expected contaminated water volume [Fig. 1(c)] and population affected [Fig. 1(b)] decrease as the number of sensors increase. The reliability [Fig. 1(d)] increases as the number of sensors increase, although there are small fluctuations in this outcome. The expected time of detection [Fig. 1(a)] has a decreasing pattern with larger fluctuations as the number of sensors increase. This fluctuation is expected considering the multiobjective nature of the problem, as discussed below, for the fluctuations on the reliability measure. For the scenario with 17 sensors (Table 4), there is a trend reversal for the reliability. The value of the measure, $Z_4$ , decreases from a value of 84.03% for 16 sensors to 83.88% for 17 sensors. Although this decrease is not significant, it is a consequence of the objective function used. This outcome should be evaluated in light of the decrease in contaminated water volume from 1,475.21 gal. for 16 sensors to 1,178.33 gal. for the 17-sensor case (Table 4). This outcome reflects the multiobjective nature of the objective function used. The four measures of the designed water sensor network $\left(Z_1\text{-}{Z}_4\right)$ yield a reasonable trade-off among the measures when the proposed objective function is used. If a single measure is chosen as the objective function, that measure is expected to improve as the optimization outcome. However, for such an analysis, the other three measures may become worse progressively, for example, if we select the maximization of the reliability as a single objective. In the five-sensor case, the optimal sensor placement would be at junctions J11, J45, J83, J100, and J117 and the reliability reaches a level of 81.74%. However, the remaining three measures $Z_1$ , $Z_2$ , and $Z_3$ become 927.64 min, 341.37 individuals (ind), and 13,117.22 gal., respectively (compare these results with the results shown in Table 4 for the five-sensor design). This comparison would indicate a worsening condition for these measures. This case can be tested because any objective function can be used in the algorithm the writers have developed and in this verification example we have only used an objective function that maximizes the reliability. We will not go into the details of the use of alternative objective functions since it is not the theme of the study presented here. Given the objective function identified in Eq. (8b), the value of the objective function monotonically decreases as the number of sensors increase however the values of individual measures may fluctuate and that is expected (Fig. 2).

In order to measure the effectiveness of the water sensor network designed, the software provided in BWSN is used to generate the intrusion scenarios. Twenty contamination scenarios for each junction within the first 24 h are randomly generated. The four measures $\left(Z_1\text{-}{Z}_4\right)$ are calculated and the outcome is given in Table 5. These results are also shown in Fig. 1 as the “verification” analysis. The reliability is almost identical for both optimization and verification scenarios. The other three measures have similar trends although there are differences between “design” stage results and the verification stage results. During optimization, the demands and concentrations are intensively used for the evaluation of the objective function. For this purpose, in the design stage, the hourly average data were stored and used in the optimization algorithm. In the verification phase, the data specific to each time step is used (i.e., 30 min for demands and 5 min for concentration). This is the main reason that the measures for the expected contaminated water volume $\left(Z_3\right)$ and population affected $\left(Z_2\right)$ in the verification simulations are smaller than those in the design simulations. This also indicates of the robustness of the proposed algorithm since a more crude data are used in the design phase as opposed to the verification phase.

For the five-sensor case, the objective function value is 13,656.12 and decreases to 3,916.70 for the 10-sensor case (Fig. 2). The rate of decrease tends to reduce as the number of sensors increase. The objective function value for the 20-sensor case becomes 723.96. Fig. 3 shows that the PGA is convergent since the objective function value for the best solution in each subdomain generation decreases monotonically. At the start, for the first several generations, the objective function value shows a significant improvement. Then the convergence rate tends to decrease. Although the results presented cannot be claimed to be the best solutions, they are indeed very good solutions based on the performance measure values obtained and the comparisons made with the other solutions submitted to the BWSN session, as discussed below.

When the number of sensors used in a design is treated as a variable, the reliability measure can be used to determine the number of sensors required for a preset reliability level. For a preset reliability level of $r_c=85\%$ and an allowable error of 0.5%, the iteration process described for constraint Eq. (13) works as the outcome shown in Table 6 when we begin with the five-sensor case. When the number of sensors is initially set as 5, $\Delta M$ is set as 1 using Eq. (16). Thus, the number of sensors in the next solution is set as 6. In the first iteration, $\Delta M$ increases to 9 using Eq. (17). This leads to an $M$ value of 15 for the second iteration. In the third iteration, the reliability is about the same as the one in the second iteration, thus $\Delta M$ takes on the value 1. The reliability in the fourth iteration is slightly less than the third iteration but this value is still less than the preselected reliability level to be achieved, thus $\Delta M$ is determined by Eq. (16) and is set as 1. In this process, as demonstrated for this case, five iterations are required to achieve the reliability level of $\sim 85\%$ . The final results indicate that at least 18 sensors are needed in the system to satisfy this preselected reliability level. Obviously, the computation demonstrated above is done algorithmically within the model.

Water Distribution System 2. For Network 2, the water distribution system is complicated as it is characterized by 12,523 junctions, 14,822 pipes, two reservoirs, two tanks, four pumps, and eight valves (Table 1). The simulation time is 2 days and system operations are characterized by five distinct demand patterns. In this case the time interval used for hydraulic and water quality simulations are selected as 60 and 5 min, respectively. The optimization calculation for this case requires a large amount of computer memory and computational time. For Network 2, we have used a total of 300 randomly generated scenarios for the junctions with largest demands during the design phase as opposed to 2,580 scenarios used in Network 1. This may, of course, limit the representative nature of the scenarios selected for the complete domain but the sensor design obtained from these limited scenario cases compete rather well with the other designs submitted to the BWSN problem and this is again an indication of the robustness of the method suggested here. The two cases with five and 20 sensors each will be explored for this application. In order to test the optimal solution, a total of 1,000 verification scenarios are randomly generated. The performance measures obtained through the application of the proposed algorithm for Network 2 are given in Table 7. For the case with five sensors, the optimal sensor placement is given in Table 10 and the corresponding objective function value is 553,200. For the case with 20 sensors, the optimal sensor placement is given in Table 11 and the corresponding objective function value is 73,026. Obviously, an increase in the number of sensors improves the performance of the water sensor network. The comparison of results for the design and verification cases indicates that the reliability is almost identical for both cases but there are some differences in the results for the other three measures, again, the verification results indicating better performance as was observed in Network 1. Based on the objective function used in this study, a significant change and improvement is observed in the value of $Z_4$ . This may imply that this parameter is a sensitive parameter in the design. For large-scale water distribution systems such as the one reported here as Network 2, the use of five or 20 water sensors are not enough to guarantee the reliability of the system at high percentages. It is expected that the performance of the network will improve significantly as the number of water sensors used further increases.

The solutions submitted to the BWSN (2006) included the application of various models and algorithms for the optimal sensor placement problem discussed above. At the conference, most writers identified the best sensor locations using their preferred algorithms. Some of these solutions focused on optimizing all four measures, others selected some or, in some cases, only one of the four measures as the criterion for optimization. It is possible to compare these solutions based on the four criteria identified in this paper which was the primary criteria to satisfy for the BWSN challenge. The comparison provided below should not be interpreted as an effort to identify which solution is the best or optimal because nobody knows what the true optimal solution is for this problem and no solution is perfect for all measures. Furthermore, as stated above, some of the solutions presented to the BWSN session studied restricted cases of the general problem investigated in this paper, thus evaluating them, considering all four measures, may not yield a fair comparison. However, the challenge was not to consider only a few of the measures but instead the challenge was to consider all four measures in the analysis in this exercise. On the other hand, evaluating these submissions using a methodology such as Pareto analysis will not be also appropriate since in Pareto method the domination analysis is done by giving importance to one measure against the others. This evaluation method would favorably evaluate the designs that are based on one or two measures as would be selected in the Pareto analysis evaluation.

Keeping these issues in mind, in order to evaluate the performance of the water sensor networks submitted to BWSN, we attempted to identify a unique criterion to test the performance of each design. The available data at hand was the sensor locations submitted to the BWSN session by different writers, that is, the five- and 20-sensor locations for Network 1 and Network 2 and we chose to study the Case-A scenario of the BWSN challenge. Using these sensor locations and using random attack scenarios, it is possible to calculate the value of the four measures for each of the cases submitted. In our evaluation, the number of random attack scenarios we selected is 6,000 for both networks. In our evaluation we have used the same random attack scenarios for all cases and performed our analysis for all results submitted. The results for the performance values for the four measures are given in Tables 8–11 for all cases submitted to the BWSN session.

During the BWSN session (BWSN 2006) it was mentioned that, as an evaluation criteria, the scenarios that were not detected by a solution were excluded from the calculation of the expected time of detection, the population affected, and the contaminated water volume calculations. This concept was not well received during the session. In our opinion, if one ignores the nondetect scenarios, this would lower the values of measures $Z_1$ , $Z_2$ , and $Z_3$ , artificially—the desired outcome. It also reduces the value of the measure $Z_4$ , which is not desired. This may lead to an overall evaluation criterion which would be very difficult to resolve. A design which has artificially low measures of the first three measures and also a relatively low reliability measure may be ranked as a good solution. This is not the correct way to interpret the performance (Aral et al. 2008). Again, in our opinion, to resolve this issue, one can choose to do the following. For the scenarios that are not detected, the time of detection can be set to be the end of the simulation period. The population and contaminated water volume can then be calculated from the initiation of injection time to the end of the simulation duration. This would penalize the nondetect scenarios equally in all competitive entries for all measures. This approach does not imply that at the end of simulation time the detection has occurred, thus for these cases, $Z_4$ measure is still recorded as a nondetected contamination event lowering the reliability values as it should. This idea stems from the fact that the first three measures need to reflect the nondetect cases appropriately as well, in some form, rather than artificially lowering their values by not including these scenarios in the calculation of $Z_1$ , $Z_2$ , and $Z_3$ . That is why the values of the four measures we are reporting here are different than the values reported during the BWSN session in Cincinnati in 2006. During the design phase analysis of this study, this criterion was used in the calculation of the four measures and the comparative analysis given below is also based on the same criteria.

The next phase of the comparative analysis is the normalization of the results given in Tables 8–11. For this purpose two approaches can be used to normalize the outcome to a range [0, 1]. The first option is to identify the maximum values for $Z_1$ , $Z_2$ , $Z_3$ , and $Z_4$ from solutions submitted ( $Z_{1\text{max}}$ , $Z_{2\text{max}}$ , $Z_{3\text{max}}$ , $Z_{4\text{max}}$ ) and calculate the normalized values $W_i$ using Eq. (18)or one can also identify the maximum and minimum values for $Z_1$ , $Z_2$ , $Z_3$ , and $Z_4$ from solutions submitted: ( $Z_{i\_\text{max}}$ , and $Z_{i\_\text{min}}$ ; for $i=1,2,3,4$ ) and calculate $W_i$ using Eq. (19)In Eqs. (18) - (19), the larger the values of $Z_1$ , $Z_2$ , and $Z_3$ are, the smaller $W_1$ , $W_2$ , and $W_3$ will be, and the larger the value of $Z_4$ is, the larger $W_4$ will be. This trend follows the interpretation of these four measures as they are used in the optimization criteria.

Estimation of the overall performance of each case for each solution submitted maybe calculated byorThe score obtained from Eq. (20) weighs the four measures equally, and the score obtained from Eq. (21) gives a larger weight to the reliability measure. This score is also included here since there was a discussion at the BWSN session (BWSN 2006) on the point of view of reliability being the more important measure. The overall performance of the results submitted to the BWSN session with the use of two different normalization methods and two different averaging methods are given in Tables 12–15. Combining two different normalization procedures with the two averaging processes yields four different scores in the estimation of the overall performance of the sensor placement solutions submitted. More important, these evaluation scores are linear and not biased based on a domination ranking process such as the Pareto front analysis, as was presented during the BWSN session in Cincinnati in 2006.

In this study, we have proposed an optimization model and a solution process for the design of water sensor networks which provide an effective procedure for the analysis of large-scale water distribution systems. Although we have used a single-objective function in this model, the proposed objective function reflects the requirements of the four criteria identified in the BWSN challenge and may achieve the purpose of a multiobjective function with a reduced computational effort. This objective function is not linked with the specific solution methodology suggested in this study, thus it can be embedded in other solution methods to achieve the same effect or even can be used in Pareto analysis. The proposed model also introduces the reliability constraint concept to determine the optimal number of sensors necessary to satisfy a prespecified reliability level of detection for the system. The proposed optimization model is based on a {0,1} integer programming approach for which the optimal solutions are difficult to achieve for problems with large number of variables. To overcome this difficulty, PGA is used to solve the optimization problem (Guan and Aral 1999; Park and Aral 2004; Aral et al. 2001). Based on a conventional genetic algorithm, the PGA works on a subdomain of junctions and the final optimal solution is obtained through progressive evolution of these subdomains. This approach improves the efficiency of the genetic algorithm solution and reduces the computational burden. During the optimization process, the EPANET algorithm is used as the simulator to calculate the water supply and concentration distribution in the network for different contaminant intrusion events. How one uses the EPANET software in the application also affects the efficiency of the solution of the optimization problem. In the application discussed here, there are two approaches that can be used during this stage. In the first approach, EPANET can be used before optimization to obtain all the data necessary for the evaluation of the objective function. These data can be stored in the computer memory and directly used by the optimization algorithm. In this manner, one can reduce the computation time. The disadvantage of this approach is that it requires a large amount of computer memory. This memory, however, seems to be readily available within the current computational platforms. In the second approach, EPANET simulations can be conducted during the optimization procedure. This approach requires the repeated application of the EPANET model for all scenarios for each solution during optimization, resulting in lengthy computational times but less computer memory storage requirement. In this study, the first approach is used. Whichever method is used, reducing the required computational time and computer memory is one of important issues for the optimal design of a water sensor networks for large water distribution systems. The subdomain concept is used effectively to solve this problem in this study.

The design of water sensor placement in a water distribution system may be formulated as a multiobjective optimization model that includes the four measures described above $\left(Z_1\text{-}{Z}_4\right)$ . In this case the model can then be solved by some trade-off method or by Pareto analysis. In either case, either the trade-off coefficients should be determined a priori or in the case of Pareto analysis, since it would yield a number of feasible optimal solutions, the selection of the final design would involve the trade-off preference of the decision maker. These are important and arguable issues one has to answer when a single solution is required for a multiobjective problem. In the model proposed here, the four design measures are incorporated into a single-objective function. The trade-off coefficients inherently imbedded in the objective function are defined in terms of the four measures. Thus, they are optimized during the solution process. The solutions obtained by the model indeed reflect the interactive effect of the four measures without emphasizing one over the other.

Evaluation of the performance of water sensor placement design using the four design measures is also another important issue. In this paper, a simple normalization process is chosen to directly compare the outcome of the solutions submitted to the BWSN session (BWSN 2006) for all four measures. This comparison is based on the premise that all four measures are equally important when Eq. (20) is used or nearly equally important when Eq. (21) is used. As can be seen from the comparative results presented in the tables above, there is a clear trend in the higher ranked solutions for each network for different number of sensor placement cases. The solutions presented by Berry et al. (2006) and Guan et al. (2006a,b) (the solution discussed in this paper) is consistently ranking as the higher ranked solutions. The solution submitted by Berry et al. (2006) is consistently ranking high (12 first place rankings, 2 s place rankings and 2 third place rankings out of sixteen scores). The solution by Guan et al. (2006a,b) always ranks second or first for all evaluation cases (14 second-place ranking and two first-place ranking out of 16 scores), with the solution submitted by Berry et al. (2006) ranking higher more frequently. For certain cases and this occurs for Network 1 the Berry et al. (2006) solution drops to third rank. The solution submitted by Propato and Piller (2006) and Dorini et al. (2006) is also showing good performance for some cases although Propato and Piller solution was not provided for the second network and was evaluated only for the first network. The solutions submitted by Huang et al. (2006), Krause et al. (2006), Eliades and Polycarpou (2006), and Ostfelt and Salomons (2006) mostly ranked third or fourth. This ranking was achieved only for some cases while for other cases their ranking is lower. The other solutions are mostly not close to the top rankings for all cases as they are evaluated here. As stated earlier, probably the reason behind this is that some of these solutions did not consider all four measures in the optimization model equally or ignored the nondetect cases and this affected the overall score of these solutions since these solutions miss near-optimal values for the remaining measures, as was discussed earlier. This emphasizes the importance of using a solution method that balances the optimization of all measures considered in the problem rather than one or a few of the measures, since all four measures are equally important in the design.

The two water distribution networks of the BWSN are used to demonstrate the performance of the model and the solution algorithm proposed. Based on the computational results, the following conclusions can be drawn:

The findings and conclusions in this article have not been formally disseminated by the Agency for Toxic Substances and Disease Registry and should not be construed to represent any agency determination or policy.