Reducing Impacts of Contamination in Water Distribution Networks: A Combined Strategy Based on Network Partitioning and Installation of Water Quality Sensors

Abstract

This paper proposes a combined management strategy for monitoring water distribution networks (WDNs). This strategy is based on the application of water network partitioning (WNP) for the creation of district metered areas (DMAs) and on the installation of sensors for water quality monitoring. The proposed methodology was tested on a real WDN, showing that boundary pipes, at which flowmeters are installed to monitor flow, are good candidate locations for sensor installation, when considered along with few other nodes detected through topological criteria on the partitioned WDN. The option of considering only these potential locations, instead of all WDN nodes, inside a multi-objective optimization process, helps in reducing the search space of possible solutions and, ultimately, the computational burden. The solutions obtained with the optimization are effective in reducing affected population and detection time in contamination scenarios, and in increasing detection likelihood and redundancy of the monitoring system. Last but most importantly, these solutions offer benefits in terms of management and costs. In fact, installing a sensor alongside the flowmeter present between two adjacent DMAs yields managerial advantages associated with the closeness of the two devices. Furthermore, economic benefits due to the possibility of sharing some electronical components for data acquisition, saving, and transmission are derived.

1. Introduction

Installing an efficient monitoring and control sensor system gives the possibility to carry out main tasks on Water Distribution Network (WDN) management and protection. Securing these critical infrastructures is a crucial task for ensuring society’s welfare and prosperity. In fact, WDNs are strongly vulnerable to malicious and intentional actions [1] since they are made up of thousands of exposed elements. From a practical and economic point of view, securing all the apparatuses is not feasible. Thus, the design of an effective and cost-effective quality monitoring system represents a crucial management strategy for ensuring the delivery of good quality water to users. Optimal sensor placement becomes a necessary step for satisfactory water quality monitoring systems, also allowing identification of the source contamination [2]. These systems should provide a fast and accurate detection, distinguishing between normal variations and contamination events; furthermore, they should be economical, easy to integrate into network, and reliable [3]. This problem has been extensively studied for the past 20 years and several approaches have been proposed to identify optimal locations of sensors (Byoung et al. (1992) [4] defined the concept of maximum coverage to locate sensors formulating the problem as integer programming problem; using the same objective as the maximum coverage, Kumar et al. (1997) [5] employed a mixed-integer programming method; Watson et al.(2004) [6] used a mixed-integer linear programming model, showing that the problem of sensor placement must simultaneously consider multiple design objectives; Berry et al. (2005) [7] pointed out the difficulty of solving sensor placement by means of integer programming optimization; Ostfeld and Salomons (2004) [8] studied the problem in unsteady conditions using a genetic algorithm framework integrated with EPANET; Uber et al. (2004) [9] used a greedy heuristic solution methodology providing a heuristic (non-optimal) solution procedure scalable to large networks, taking into account uncertainty in threat scenario). The problem received lots of attention especially after the events of 11 September 2001. However, although many research works have been carried out in this field, the challenge of the optimal sensor placement is still open in many aspects, such as identification of optimal sensor locations and evaluation of performance and applicability to real-world scenarios. Models and algorithms for solving this arduous problem include deterministic and stochastic optimization techniques, optimizing one (Kessler et al. (1998) [10] defined the total volume of contaminated water consumed ahead of detection; Ostfeld and Salomons (2005) [11] enhanced previous study by taking into account the randomness of flow rate of the intruded pollutant, stochastic demands, and reaction time of the sensors; Berry et al. (2009) [12] incorporated into a mixed-integer programming formulation the probability of sensor failure) or more objectives (McKenna et al. (2007) [13] demonstrated the importance of considering sensor failure rates showing the trade-off between the sensor detection limit and the number of sensors; Dorini et al. (2008) [14] considered four objectives in the model and used a noisy cross-entropy sensor locator algorithm to find the optimal solution; Huang et al.(2008) [15] considered three objectives in their formulation solved by using a competent genetic algorithm while the contamination events were simulated by a development of Monte Carlo method; Propato and Piller (2006) [16] used a mixed-integer linear program methodology including notions of statistical and uncertainty analysis in the design process; Wu and Walski (2008) [17] combined four objectives into a single objective), such as detection likelihood, expected contaminated water volume, affected population, detection time, and the contaminated population. The interested reader can refer to Hart and Murray (2010) [18,19] for a review of this topic. The optimal sensor placement problem was also dealt with at the Battle of the Water Sensor Networks (BWSN) [20]. The main difficulty is that, given WDN complexity, efficient numerical techniques are needed to support optimal monitoring system design and the huge number of all potential contamination events in a WDN makes the problem computationally intractable (as each of these events is characterized by a different injection location, duration, mass rate, and starting time). Indeed, the optimal sensor placement in a network represents a combinatorial optimization problem that has been proven to be NP-hard [21]. For example, Krause et al. (2008) [22] showed that, using 30 parallel processors, it took 8 days to simulate random contamination events that could occur at 5 min intervals over a 24 h period from any of the 12,527 nodes in a medium-sized distribution network. In recent years, new concepts in sensor network design have been studied; Sankary and Ostfeld (2016) [23] investigated the possibility of adopting a mobile wireless sensor network to wirelessly transmit data to fixed transceivers in real time; Rathi et al. 2016 [24] proposed a novel strategy for the selection of contamination events with associated risk to be used in design of sensor network; Zheng et al. 2018 [25] investigated the characteristics of the sensor placement strategy effectiveness using several metrics, and providing guidance for selecting the most appropriate strategy for the preparedness for contamination events.

On the other hand, the “divide and conquer” concept has recently been gaining attention in the field of WDNs, showing to be one of the most efficient management strategies. The option of dividing large-scale networks into smaller and manageable subsystems, called district metered areas (DMAs), offers undisputable advantages for the monitoring and control of consumption, pressure, leakage, and water resource quality. In the scientific literature, numerous works were dedicated to the design of DMAs. Most of them are based on the application of decomposition algorithms [26,27] based on graph [28,29,30,31,32] and spectral theories [33,34], multi-agent method [35], social network theory [36], modularity index [37,38,39]. Though being significant contributions to the field, the works mentioned above are mostly focused on DMA design. Therefore, they fail to analyze the positive effects brought by the creation of DMAs to WDN management, for reducing the impacts of potential contamination events.

The global aim of this paper is to provide a general management framework for WDN monitoring, while exploring the benefits of water network partitioning (WNP) for:

• reduction in inauspicious consequences of contamination (both accidental and intentional) in terms of limitation of contaminated areas (direct action);
• optimal placement of quality sensors (indirect action).

While the analysis of the former aspect is presented hereinafter as a follow-up of the work of Ciaponi et al. (2018) [40], the analysis of the latter aspect is entirely novel. In this context, the possibility of installing some or all sensors at boundary pipes will be considered, resulting in a two-fold advantage: numerical, due to the reduction in the research space of possible candidate solutions for sensor installation, and managerial, due to easiness of access and to cost savings for the possibility of sharing some electronical components for data acquisition, saving, and transmission.

In the following sections, first the methodology is presented, followed by the applications to a real case study, testing different scenarios and comparing different sensor locations with four water quality-based parameters, in order to validate the results.

2. Materials and Methods

The methodology used in this work is the combination of two main procedures, used for WNP and sensor placement, respectively. These procedures, both derived from the scientific literature, are described in the following Section 2.1 and Section 2.2, respectively. Section 2.3 deals with the postprocessing of the sensor placement solutions obtained in Section 2.2.

2.1. Procedure 1—WNP

According to Perelmann et al. (2015) [41], WNP is carried out in two main phases: (a) clustering, in which the optimal shape and size of the clusters are defined by minimizing the number of edge cuts (boundary pipes) and by simultaneously balancing the number of nodes of each cluster, and (b) dividing, in which clusters are separated from each other by closing isolation valves at some boundary pipes and installing flow meters at the remaining boundary pipes.

In this work, the clustering layout is obtained exploiting the properties of the normalized Laplacian matrix L = D − A, in which D is the diagonal matrix containing the node degree k_i of each node, and A is the adjacency matrix. In this matrix, the elements a_ij = a_ji = 1 if nodes n_i and n_j are connected by a pipe; otherwise, a_ij = a_ji = 0. Shi and Malik (2000) [42] demonstrated that through the first C smallest eigenvector of the normalized Laplacian matrix, the relaxed version of the min-cut problem can be solved. In fact, it corresponds to the minimization of the Rayleigh quotient. If C is the number of clusters in which the network must be divided, the first C smallest eigenvectors of the Laplacian matrix are considered and used to create a new matrix U_nxC. A k-means algorithm is applied to the rows of U_nxC for grouping the nodes of the network in C clusters. The main trick is to change the representation of the nodes in the eigenspace of the first C eigenvectors, which enhances the cluster-properties of the nodes in such a way that they can be trivially detected in the new representation. The spectral clustering algorithm proved to show a superior performance to other clustering procedures, in that the provided clustering layout features both a well-balanced cluster size and a minimum number of edge cuts [43]. The main spectral clustering steps in the case of a WDN are described by Di Nardo et al. (2018b) [44]. The graph of the WDN can be considered un-weighted (every connection between the nodes has the same importance, a_ij = a_ji = 1) or weighted (the value a_ij = a_ji can be related to pipe features, such as diameter d and length l). In the applications of this work, a_ij and a_ji were set at 1. The optimal number of clusters C (from a topological point of view) in which to subdivide the network is chosen as a function of the number n of nodes, according to the relationship C_opt = n^0.28 [45]. The clustering phase provides the optimal cluster layout and, as a result, the edge-cut set, consisting of a group of N_ec boundary pipes between clusters. In correspondence to each boundary pipe, the flow transfer between the adjacent clusters must always be known, if it is larger than zero, in order to make the dividing effective. Therefore, the choice must be made whether either a gate valve must be closed, or a flow meter must be installed in the generic boundary pipe. Following this choice, the sum of closed gate valves (as numerous as N_gv) and installed flow meters (as numerous as N_fm) must be equal to N_ec. Closing gate valves has the effect of reducing the service pressure and, therefore, leakage in the WDN. However, if service pressure falls below the desired threshold value h_des, this negatively impacts on WDN reliability. In this work, the trade-off between leakage and WDN reliability was explored through the bi-objective optimization, performed through the NSGAII genetic algorithm [46]. In this optimization, several decisional variables equal to N_ec was considered, to encode, inside individual genes, gate valve closure (gene value equal to 1) or flow meter installation (gene value equal to 0) at boundary pipes. The first objective function f₁ to minimize was the daily leakage volume V_l (m³):

f₁ = V_l

(1)

where V_l is calculated as the sum of the temporal integral of the nodal leakage outflows, evaluated as a function of nodal pressure heads through the Tucciarelli et al. (1999) [47] formula.

The second objective function f₂ relates to the global resilience failure index GRF index proposed by Creaco et al. (2016) [48] to represent the instantaneous power surplus/deficit conditions of the WDN. In fact, GRF is dimensionless and is the sum of the resilience (I_r) and failure (I_f) indices evaluated at the generic instant of WDN operation:

$$GRF=I_r+I_f=\frac{max\left({\mathit{q}}_{\mathit{u}\mathit{s}\mathit{e}\mathit{r}}^{\mathit{T}}\mathit{H}-{\mathit{d}}^{\mathit{T}}{\mathit{H}}_{\mathit{d}\mathit{e}\mathit{s}},0\right)}{{\mathit{Q}}_{\mathbf{0}}^{\mathit{T}}{\mathit{H}}_{\mathbf{0}}-{\mathit{d}}^{\mathit{T}}{\mathit{H}}_{\mathit{d}\mathit{e}\mathit{s}}}+\frac{min\left({\mathit{q}}_{\mathit{u}\mathit{s}\mathit{e}\mathit{r}}^{\mathit{T}}\mathit{H}-{\mathit{d}}^{\mathit{T}}{\mathit{H}}_{\mathit{d}\mathit{e}\mathit{s}},0\right)}{{\mathit{d}}^{\mathit{T}}{\mathit{H}}_{\mathit{d}\mathit{e}\mathit{s}}}$$

(2)

where d and q_user are the vectors of nodal demands d (m³/s) and water discharges q_user (m³/s) delivered to users, respectively, at WDN demanding nodes. In this work, q_user was evaluated as a function of d and pressure head h (m) at each node though the pressure-driven formula of Tanyimboh and Templeman (2010) [49], with calibration proposed by Ciaponi et al. (2014) [50]. H and H₀ are the vectors of nodal heads (m) at demanding nodes and sources, respectively. H_des is the vector of desired nodal heads, which are the sum of nodal elevations and desired pressure heads h_des (m). Finally, Q₀ is the vector of the water discharges leaving the sources. The GRF index has the advantage of being within range [−1, 1]. Higher values of GRF indicate higher power delivered to WDN users and, therefore, higher service pressure. With reference to WDN daily operation, the second objective function f₂ to maximize was calculated with the following relationship, as suggested by Creaco et al. (2016) [48]:

f₂ = median(GRF)

(3)

The choice of the median value of GRF is because Creaco et al. (2016) [48] proved it to give a suitable and concise representation of a sequence of operation scenarios in the extended period simulation of the WDN. Both f₁ and f₂ can be calculated by applying a pressure-driven WDN solver (e.g., that of Creaco et al. 2016 [48]). They are mutually contrasting objectives: in fact, as the number of closed gates grows, f₁, which has to be minimized, decreases. At the same time, f₂, which has to be maximized, decreases as well due to the decreasing service pressure. This creates a trade-off between the two objectives, which takes the form of a Pareto front of optimal solutions, that is a group of solutions from which to select the final solution for the partitioning. To this end, additional criteria, such as the partitioning cost or demand satisfaction, can be adopted. In fact, the Pareto front of optimal solutions can be re-evaluated in terms of other functions, such as number N_fm of flow meters and demand satisfaction rate I_ds. In fact, N_fm is a surrogate for the partitioning cost [34], whereas I_ds represents the effectiveness of the service to WDN users. The latter index can be calculated as:

$$I_{ds}=\frac{w_d}{w_{tot}}$$

(4)

where w_d (m³) and w_tot (m³) are the delivered water volume and the WDN demand, respectively. Variable w_d can be calculated starting from the temporal integral of the water discharge q_user delivered to the users at each node.

2.2. Procedure 2—Optimal Sensor Placement

Let a set S of potential contamination events considered in the analysis, each of which featuring a certain location, starting time, duration, and total mass, be defined. In this context, sensor placement was formulated as a bi-objective optimization problem [51], in which the first objective function is f₃ = N_sens (number of installed sensors), as a surrogate for the installation cost for WDN monitoring, while the second objective function is:

$$f_4=pop=\frac{{{\displaystyle \sum }}_{r=1}^{S}po{p}_r}{S}$$

(5)

The objective function f₄ is related to the contaminated population pop_r before the first detection of the generic r-th contamination event. This corresponds to the sum of the inhabitants served by the contaminated nodes and can be evaluated using the EPANET quality solver [52], using an unreactive contaminant. The EPANET quality solver can be applied to the flow field obtained following procedure 1. If the r-th event is not detected, pop_r includes all the nodes crossed by the contamination till the whole contaminant mass leaves the WDN. Though numerous objective functions can be used for the optimal installation of sensors, the population exposed to contamination was chosen as the objective function to minimize along with the number of sensors. This choice was made because, compared to other potential objective functions (such as detection likelihood and sensor redundancy), the population exposed to contamination represents more directly the impact of contamination, which is the most meaningful from the viewpoint of risk assessment and mitigation. The time interval Δt_react for the activation of emergency operations is set to 0 hr hereinafter for simplifying purposes. This means that contamination is assumed to stop instantaneously after its detection. However, Δt_react can be set to other values without loss of validity of the whole methodology. The function f₄ is therefore the average value pop of pop_r. In the bi-objective optimization, functions f₃ and f₄ are minimized simultaneously through the NSGAII genetic algorithm [46]. In fact, the minimization of the former reduces the sensor cost while the minimization of the latter impacts positively on the system security. In the population individuals of NSGAII, the number of genes is equal to the number of network nodes where sensors can be installed. Each gene can take on the two possible values 0 and 1, which stand for absence and presence of the sensor in the node associated with the gene, respectively.

In this paper, four options for sensor locations on the partitioned network were tested:

• Option 1, sensors can be installed at all nodes (typical greedy approach);
• Option 2, sensors can be installed only at the hydraulically upstream nodes of the boundary pipes;
• Option 3, sensors can be installed at the most central nodes of each district, identified through topological considerations;
• Option 4, sensors can be installed at the hydraulically upstream nodes of the boundary pipes and at the most central nodes of each district.

In the last two cases, the idea is to take advantage from the study of WDN topology in order to define which nodes are potential candidates for sensor installation, according to their connectivity centrality. In this paper, the most central nodes were defined using the betweenness centrality [53], defined starting from the shortest paths in a graph. The shortest path σ(s, t) between two nodes s and t is the connecting path with the lowest number of links (or the minimum sum of the weights associated with its links in the case of weighted graph). The betweenness centrality of a node i is defined as the sum of the ratios of the number of shortest paths between nodes s and t passing through i to the total number of shortest paths between nodes s and t. It is a measure of the influence of a node i over the flow of information between other nodes. In this paper, for each cluster, the nodes with the highest value of betweenness centrality were selected as possible sensor locations alone (Option 3) or in combination with boundary nodes (Option 4). Options 2, 3, and 4 aim to investigate the possibility of limiting the search for optimal sensor locations to the hydraulically upstream nodes of the flow meter-fitted boundary pipes and to the most central nodes of each district. This choice leads to significant computational simplifications, due to the reduction in the search space. This offers the possibility of better facing the problem of optimal sensor placement also for big-size WDNs (for which the number of all potential scenarios makes the problem computationally intractable). Furthermore, the strategy of locating all or some sensors in the same stations as boundary flowmeters offers easiness and cheapness of inspection and maintenance.

2.3. Procedure 3—Comparison of Sensor Placement Solutions

Sensor placement solutions were evaluated using the following four contamination impact indicators. The first is function f₄ in Equation (5), followed by functions f₅, f₆ and f₇ reported in the following Equations (6)–(8), respectively.

The function f₅ is the detection likelihood (i.e., the probability of detection):

$$f_5=P_s=\frac{1}{S}{{\displaystyle \sum }}_{r=1}^S{d}_r$$

(6)

where d_r = 1 if contamination scenario r is detected, and zero otherwise; and S denotes the total number of the contamination scenarios considered.

The function f₆ is the detection time. For each detected contamination scenario, the sensor detection time corresponds to the elapsed time from the start of the contamination event, to the first identified presence of a nonzero contaminant concentration. If t_j is the time of the first detection (referred to the j-th sensor location), the detection time (t_d) for the solution for each contamination event, is the minimum among all present sensors t_d = min(t_j); the characteristic detection time of the solution is defined as the mean of all t_d for the contamination scenarios detected by at least one sensor:

$$f_6=mean\left(t_d\right)$$

(7)

Finally, the function f₇ is the sensor redundancy. In a generic scenario, the variable Red corresponds to the number of sensors (including the first) that detect the contamination within 30 minutes from the first detection; the redundancy Red of the solution is defined as the mean of all the values of redundancy Red for all the considered contamination scenarios:

$$f_7=Red=mean\left(Red\right)$$

(8)

which contributes to the safety of the monitoring systems, especially in the case of sensor failures or false positive/negative detection, conferring a higher reliability.

As for the choice of the objective functions, it must be remarked that theoretically more than two of them could be inserted in the same optimization framework. However, to prevent this framework from becoming overly complex, we preferred to keep only two objective functions (number of sensors and exposed population) in the optimization framework, while other assessment criteria (e.g., detection likelihood, detection time, and sensor redundancy) will be considered in the postprocessing of the optimal solutions.

3. Case Study

The methodology described above was tested on the WDN of Parete [54], which is a small town located in a densely populated area to the south of Caserta (Italy), with population of 11,150 inhabitants. This WDN has 182 demanding nodes (with ground elevations ranging from 53 m a.s.l. to 79 m a.s.l.), 282 pipes and 2 sources with fixed head of 110 m a.s.l. A uniform desired pressure head h_des = 19 m was assumed for the demanding nodes, coming from the sum of the maximum building height in the town, which is 9 m in Parete, and 10 m, as prescribed by the Italian guidelines. Reference was made to the day of maximum consumption in the year when the total nodal demand ranges from 7.6 L/s at nighttime to 77.2 L/s in the morning and midday peaks, with an average value of 36.3 L/s. The leakage volume of the networks in the day of maximum consumption adds up to 930 m³ (about 23% of the total outflow from the sources). The number of users connected to each WDN node was derived based on its average nodal demand.

4. Results and Discussions

In this section, the results of the procedures described in Section 2.1, Section 2.2 and Section 2.3 are reported. The first step is the definition of an optimal water network partitioning. In this regard, the clustering phase was applied to produce 5 DMAs. The choice of 5 DMAs was made because the formula C_opt = n^0.28 proposed by Giudicianni et al. (2018) [45] to calculate the optimal number of clusters yields C_opt = 4.3 for this WDN. The number of nodes for each DMA are DMA₁ = 20, DMA₂ = 35, DMA₃ = 39, DMA₄ = 41 and DMA₅ = 49, with N_ec = 21. For the dividing, the optimization through NSGAII yielded the Pareto front reported in Figure 1a, showing, as expected, growing values of median(GRF) with V_l growing. In fact, both variables are growing functions of the service pressure in the WDN. Figure 1b,c report the number N_fm of flow meters and the demand satisfaction rate I_ds, respectively, re-evaluated from the Pareto front and plotted against V_l. Globally, Figure 1b highlights that the higher values of N_fm tend to be associated with the high values of V_l. This is because V_l tends to grow when fewer gate valves are closed (and then more numerous flow meters are installed) at the boundary pipes. Finally, Figure 1c shows that I_ds tend to grow with V_l increasing, since both variables are increasing functions of the service pressure.

From the graphs in Figure 1, the solution with the lowest value of N_fm (= 8), highest number of closed valves N_gv (= 13), which ensures I_ds = 100%, was finally chosen. An important remark to be made is that among the several advantages of the WNP, the adopted partitioning solution enables also reducing leakage, from 930 m³ (for the un-partitioned layout) to 895 m³ (partitioned solution with 13 gate valves closed and 8 flow meters installed). This corresponds to a 3.7% leakage reduction without negatively affecting I_ds and GRF. In fact, for this solution median(GRF) is equal to 0.32, very close to the value of 0.36 for the un-partitioned network. The layout of the partitioned layout is reported in Figure 2. The optimal sensor placement is then carried out. The following assumptions were made for the construction of the set S of contamination events considered in the optimization:

• all the 182 demanding nodes were considered to be potential locations for contaminant injection;
• 24 possible contamination times in the day (hour 0, 1, 2, …, 22, 23);
• single value of the mass injection rate equal to 350 g/min;
• single value of the injection duration equal to 60 min.

The values reported above for mass injection and duration were sampled from those proposed by Preis and Ostfeld (2008) [55], using the procedure of Tinelli et al. (2017) [51], with the objective to obtain a representative smaller set of significant contamination events. Due to the previous assumptions, the total number S of contamination events was 182 × 24 × 1 × 1 = 4368.

The water quality simulations were run for 2 days of WDN operation to make sure that even contaminants injected close to the sources at the last instant of the first day had enough time to leave the network. In the optimization for sensor placement, the partitioned WDN layout was indicated as Var1 to differentiate it from the original layout (Var0). Therefore, according to the three optimization options described in Section 2.2, optimizations were organized as follows:

• Var1Op1: Optimal sensor placement on the partitioned WDN allowing sensor installation on all nodes (182 potential locations);
• Var1Opt2: Optimal sensor placement on the partitioned WDN allowing sensor installation only on the nodes hydraulically upstream from the flowmeter fitted boundary pipes (8 potential locations);
• Var1Opt3: Optimal sensor placement on the partitioned WDN allowing sensor installation only on the most central nodes of each district (15 potential locations, i.e., three locations for each district, which feature a much higher betweenness centrality value than the other nodes);
• Var1Opt4: Optimal sensor placement on the partitioned WDN allowing sensor installation on the nodes hydraulically upstream from the flowmeter fitted boundary pipes and on the most central nodes of each district (23 scenarios).

Compared to Var1Opt1, Var1Opt2, Var1Opt3 and Var1Opt4 reduce the group of potential sensor locations respectively by 96%, 92% and 87%, resulting in a research space reduction which helps in diminishing the computational burden. The three optimizations were compared with the benchmark Var0Opt1, where all the 182 potential sensor locations are explored in the original layout.

Table 1. Framework of optimizations for sensor placement in the Parete WDN.

Option	Variant 0 (Un-Partitioned)	Variant 1 (Partitioned)
1 (all nodes)	Var0Opt1	Var1Opt1
2 (only boundary nodes)	-	Var1Opt2
3 (only central nodes)	-	Var1Opt3
4 (boundary nodes + central nodes)	-	Var1Opt4

shows the optimization framework, made up of 5 runs. In all of them, NSGAII was applied with a population of 200 individuals and a total number of 200 generations.

For the optimizations that consider all nodes as potential sensor locations (Var0Opt1, Var1Opt1), the slow convergence of NSGAII was initially remarked towards interesting solutions for water utilities, which are solutions with a reasonably low number of sensors in comparison with the total number of demanding nodes. This problem was solved by implementing inside NSGAII a heuristic algorithm to correct solutions with numerous sensors, that is N_sens > 20. In this heuristic algorithm, for each NSGAII solution violating N_sens = 20, a random integer number within the range (1, 20) is generated, representing the target number of sensors for that solution. Then, starting from the initial value of N_sens, the least effective sensors in terms of pop are removed one by one to reach the target. Though increasing the computation time for each NSGAII generation by about 30 times, this algorithm proved to solve the issue of slow convergence. This heuristic algorithm was not applied to the optimizations Var1Opt2, Var1Opt3 and Var1Opt4. This made the NSGAII optimizations in the two latter applications much lighter from the computational viewpoint.

Figure 3a reports the Pareto fronts obtained in optimization Var0Opt1, on the un-partitioned layout, and in optimizations Var1Opt1, Var1Opt2, Var1Opt3 and Var1Opt4, on the partitioned layout. As expected, these fronts in Figure 3a show decreasing values of pop as N_sens increases up to 20. However, for high values of N_sens, the additional benefit of a further sensor installed in the network tends to decrease, as already pointed out by Tinelli et al. (2017) [56]. In the present work, N_sens = 6 appears to be the threshold of benefit for the installation of an additional sensor, slightly to right of the knee of the Pareto fronts (which lies around N_sens = 3).

Another point to highlight is that for the partitioned network, the contaminated population corresponding to the case of zero installed sensors (pop = 2458) is lower than the corresponding contaminated population for the un-partitioned WDN (pop = 2806) as shown in

Table 2. Simulation results in terms of exposed population from the four optimizations for sensor placement in the Parete WDN, considering N_sens up to 6.

Nsens	Var0Opt1	Var1Opt1	Var1Opt2	Var1Opt3	Var1Opt4
0	2806	2458	2458	2458	2458
1	1438	1274	1274	1274	1274
2	982	919	953	974	953
3	789	648	741	679	653
4	667	559	638	598	569
5	589	500	572	561	515
6	514	462	564	548	472

.

This points out the first advantage of the partitioning: by reducing the average number of possible paths in the network (due to the closure of some pipes), it produces a reduction in the contaminated population by around 12.4%. This is due to the reduction in the spreading of contamination (direct action). Furthermore, the WNP also enhances the results of optimal sensor placement (indirect action). As is shown in Table 2 for N_sens ≤ 6, pop for the un-partitioned WDN (Var0Opt1) is always higher than pop for the Var1Opt1 for all the number N_sens of sensors installed in the network. The minimum value of pop = 462 is for Var1Opt1. Var1Opt2 (sensors allowed only upstream from boundary pipes), Var1Opt3 (sensors allowed only on topologically central nodes in DMAs) and Var1Opt4 (sensors allowed upstream from boundary pipes and on topologically central nodes in DMAs) give similar results to Var1Opt1 up to N_sens = 2. For N_sens > 2, Var1Opt2 and Var1Op3 degenerate while the good performance of Var1Opt4 persists. This is evidence that constraining sensor installation only upstream from boundary pipes or on topologically central nodes may lead to remarkably sub-optimal solutions. However, the combination of locations upstream from the boundary pipes and of topologically central nodes offers a good set of potential locations in the problem of optimal sensor placements. Figure 3b–d report the results of the reprocessing of the optimal solutions in terms of detection likelihood, detection time, and redundancy as a function of N_sens. Along with Figure 3a, they give indications on the effectiveness of the solutions obtained in the NSGAII runs. Globally, the Var1 solutions obtained on the partitioned graph, especially Var1Opt1, Var1Op2, and Var1Opt4, tend to perform better in terms of pop, detection time, and sensor redundancy. Conversely, they feature slightly worse values in terms of detection likelihood. This may be because the optimization was carried out considering pop as objective function, which is slightly contrasted with detection likelihood [56]. In fact, the former variable mainly contributes to the system’s early warning capacity whereas the latter contributes to the system safety. As for Figure 3, it must be remarked that the curves in Figure 3a are Pareto fronts while those in the other Figure 3b–d are obtained by reprocessing the optimal solutions in terms of other assessment criteria. Since these curves are not Pareto fronts, they are not strictly monotonous. Figure 4 shows the sensor placement solutions obtained for N_sens = 6 with three optimizations (Var0Opt1, Var1Opt1, and Var1Opt4). In this context, it must be noted that the Var1Opt4 solution has three of the six sensors placed close to flowmeters (the other three sensors are in the most central nodes according to the betweenness centrality). This solution yields managerial and economic benefits, due to the closeness of some sensors to installed flow meters and due to the possibility of sharing some electronical components for data acquisition, sharing, and transmission. Summing up, the Var1Opt4 solution represents a quasi-optimal solution in the explored trade-off between pop and N_sens, while offering significant potentials for improved management. Another advantage compared to the Var0Opt1 and Var1Opt1 solutions with N_sens = 6 is that it was obtained at a much lower computation cost (about 1/30), due to the research space reduction mentioned above for Options 2–4. Overall, the advantages in terms of computational lightness during the optimization as well as the possibility of inspecting and maintaining sensors in proximity to flow meters make solutions obtained in Opt4 preferable from the water utilities’ viewpoint. The results highlighted that nodes close to flow meters used for the monitoring of DMAs, which must always be easily accessible sites, represent good sensor locations for WDN monitoring from contaminations, when they are inserted into an optimization framework that also includes topologically central nodes inside DMAs. As for the optimal positions of the sensors in Var1Opt1 (partitioned network and all nodes as potential candidates) and Var1Opt4 (partitioned network and sensor installations restricted to entry points and central nodes in DMAs), it must be remarked that many locations are similar in the two cases (see Figure 4). This corroborates the fact that entry points and central nodes in DMAs are good candidate locations in the present case study.

5. Conclusions

In this work, a methodology that combines WNP and optimal sensor installation was proposed, to investigate the benefits of the “divide and conquer” technique for the monitoring of WDNs from contamination events (direct action), and for the effectiveness of optimal sensor placement (indirect action). The applications concerned a real Italian WDN, which was first partitioned into 5 DMAs. Optimal sensor solutions were searched for on the original un-partitioned WDN and on the partitioned layout, in the trade-off between number of installed sensors and affected population for an assigned set of contamination events. Further optimizations were carried out by restricting sensor installation to some pre-selected nodes (nodes hydraulically upstream from the flow meter-fitted boundary pipes and central nodes). The results showed that, for a given number of installed sensors, the monitoring stations installed in the partitioned layouts offer better monitoring performance. On the other hand, the option of considering locations in proximity to flow meters and at most central nodes as the only potential locations in the context of optimal sensor placement has the following advantages:

• almost identical performance in terms of WDN monitoring, compared to the option of considering all nodes as potential locations;
• money savings thanks to the possibility of sharing some electronical components for data acquisition, sharing, and transmission;
• easiness of access to the sensors for maintenance;
• reduction in the search space and, therefore, in the computational complexity in the optimizations for optimal sensor placement;
• easier identification of the area from which the contamination starts with the subsequent possibility of isolating the district, assuring a higher resilience of the system to the spreading of the contamination.

With regards to the last issue, it must be noted that the calculations of the present work were carried out on a simple though real WDN. Therefore, the benefits are expected to be much larger in the case of big-size WDNs, for which the problem of optimal sensor placement may become computationally infeasible. Indeed, the topics analyzed in this paper fully match the future research directions identified by Ostfeld et al. (2008) [20] during the Battle of the Water Sensor Networks. In fact, specific reference was made to the problems of aggregation, i.e., the possibility of using a reduced but still significant sample of nodes for investigations into water quality, multi-criteria analysis of sensor performance, choice of optimal number of sensors and multiple use of boundary pipes (for both monitoring flow between DMAs and detecting potential contaminations).

Though topologically central nodes have been considered in this analysis along with DMA entry points, another attractive option is made up of critical sink nodes with lowest head inside DMAs, in which water quality parameters are already monitored. Future works will be dedicated to exploring the solution of critical sink nodes. Future work will be dedicated to investigating how results change when other objective functions from those used in the present work are considered. The methodology presented in this paper will be refined in the future considering also other benchmark networks. Adopting different clustering algorithms and centrality metrics could affect the results; to better investigate the influence on the solutions, new algorithms will be applied. Another aspect that deserves to be further investigated concerns the assumptions made for the definition of the representative set of contamination scenarios. Other prospects could concern the issues of restoration after the generic contamination and of constructing mega-monitoring stations on which to locate all the management devices (chlorine stations, pressure valves, etc.). This will be done with reference to specific real contaminants, while abandoning the simplifying assumption of unreactive and conservative contaminant adopted so far.