An investigation of the possible scenarios for the optimal locating of quality sensors in the water distribution networks with uncertain contamination

Water distribution networks are vulnerable to the intentional or accidental contamination due to the wide range of accessible points. The water contamination possibility from any point of the water distribution network and its diffusion is a serious concern (Yousefi et al. 2018, 2019). Contamination that enters the network can seriously threaten the health of individuals in the community. One of the most effective means of ensuring the provision of drinking water with the desirable quality for the consumer is the water quality monitoring within the water distribution network. Accordingly, the optimal sensor placement in order to reduce the effect of contamination entry to the network is of utmost importance. The research background on the placement of quality sensors in the water distribution network goes back to the 1990s.

Lee & Deininger (1992) employed the mixed integer linear programming (MILP) based on the steady-state flow under one or more demand patterns in order to optimally locate the quality sensors with the aim of maximizing the water demand coverage by them. Kumar et al. (1997) developed the method used in the study of Lee & Deininger (1992). In order to calculate the water quality at each node, they simulated the residual chlorine concentration and estimated the total water demand coverage values based on it. In this approach, the time between contamination injection and its diagnosis is ignored.

Despite the above-noted problems, many scholars have based their investigations on Lee & Deininger (1992) and continued the monitoring studies of the water distribution network on the basis of this study. The study of Berry et al. (2005) was one of the first investigations conducted on the water distribution network monitoring in which some nodes were more likely to be attacked than others. In this study, the MILP method was developed for the location of the sensors with the aim of minimizing at-risk populations. Only four 6-h consumption patterns were used in this study. Shastri & Diwekar (2006) did not agree with the deterministic method used by Berry et al. (2005) for quantifying the uncertainties. For this purpose, they presented a nonlinear probabilistic optimization program in order to solve the sensor placement problem. In most of these studies, an estimation of the effect of an attack on a specific node of the network has been considered in the sensor placement optimization problem. This estimation was obtained via analyzing the flow direction and velocity, pipe lengths and the water demand amount of the nodes. The disadvantage of this formulation is that the dilution of the contaminant, concentration and method of attack are not modeled.

Recent research dealing with the optimal quality sensors placement have directly used the pollutant transmission simulation in order to minimize the risk of contamination entry. Berry et al. (2006) improved their previous approach in 2005 by considering the contamination concentration at different times. They generalized the optimization problem from a single-objective one (minimizing people affected by contamination) to a more comprehensive formula taking an impact factor for each node into consideration. In their paper, the mixed integer programming method was also considered as a p-median problem. This method is a mixed approach introduced by Resende & Werneck (2004) and is called RW. A large number of contamination events needs to be simulated while implementing optimizations which use the pollutant transmission simulations. For this reason, the implementation of simulations for evaluating any new alignment of the sensors will make the application of optimization techniques such as evolutionary algorithms very costly. To overcome this problem, conducting off-line simulation prior to performing the optimization has attracted the attention of many researchers (Propato 2006; Krause et al. 2008). Hence, the simulation time is separated from that needed to run the optimization program. Comboul & Ghanem (2013) developed the uncertainty analysis for the optimal sensor locating with the aim of maximizing the likelihood of detecting contamination intrusion in the network. Rathi & Gupta (2015) considered the two objectives of maximizing the water demand coverage and likelihood of the contamination diagnosis for the optimal sensors placement. The authors normalized these two goals and weighted in a linear single-objective function. Hu et al. (2017) developed a Spark-based genetic algorithm (GA) for the sensor placement in a large water distribution network. In their investigation, the sensor locating criterion in the network was to minimize the detection time by the sensors. Using the complex network theory, Nazempour et al. (2018) considered the two objectives of minimizing the contamination coverage time and maximizing the water demand coverage of the nodes for the optimal location of the sensors. Nasirzade et al. (2018) developed a probabilistic model considering the possibility of simultaneous contamination entry from multiple nodes and implemented the NSGA-II in order to minimize the risks and costs. Winter et al. (2018) integrated various objectives, including the likelihood of contamination diagnosis and detection by the sensor, average time during which the sensor detects the contamination and the estimated effect of the attack in a relationship, and developed a single-objective model based on the greedy algorithm for optimizing the sensors placement in the water distribution network. Recently, Khorshidi et al. (2018) utilized the game theory and considered the two objectives of minimizing the sensor cost and the contamination detection time for the optimal sensors placement.

The continuing studies on the optimal locating of water quality sensors indicate the developing place of this issue in the international arena. As a conclusion, given the limited cost, problem complexity and uncertainties existing in the type, time, mass, contamination entry location and water demand, the location of a limited number of quality monitoring sensors should be optimally investigated with the aim of minimizing the damage due to the network pollution.

The present paper aims to optimize the quality sensors placement for the most critical possible scenario based on the robust optimization models.

Also, in this study, a novel formulation is presented to solve the sensor locating problem using the new concept of minimizing the probable damage caused by the affected population (AP). For the first time in this paper, the importance of nodes within the objective function is defined. In addition to the uncertainty in the contamination entry site, this approach takes into account the time of entry. To optimize the sensors placement, using a simulation–optimization approach which directly uses the pollutant transmission simulation, a bi-objective GA-based optimization model (NSGA-II) has been developed in order to minimize the ‘maximum possible damage’ caused by infected populations along with the number of sensors. In this model, the decision variables are the number of nodes in which the quality sensors are placed. To calculate the damage, the amount of contaminated water consumed (before being detected by the first sensor) is taken into account. The ‘maximum possible damage’ refers to the maximum amount of damage that can be caused through the contamination entry from any node at any time step. To calculate the ‘maximum possible damage’ value, the damage matrices are used being calculated prior to the optimization. In other words, the optimal location of the quality sensors in the present model is selected so as to minimize the maximum damage due to the contamination entry (with uncertainties in the location and time of entry).

Also, for the first time in the optimization process, in addition to the population covered, the definition of the importance of nodes is used. In the formula presented for the damage estimating, the nodes are considered to be weighted in order to account for the differences between their importance levels. Six scenarios were defined in this study. The uncertainties in the pollutant mass injected into the nodes, the location of the contamination entry and corresponding time were among the parameters considered in these six scenarios.

The proposed algorithm has been implemented on a sample network for a city in Iran as shown in Figure 1. This network has no contamination detecting sensor and consists of 81 nodes, 121 pipes and a reservoir. Figure 1 indicates the nodes which have the potential of injecting contamination. The city's population is about 324,000. The hourly multipliers of the base demand are depicted in Figure 2.

To consider the importance of the nodes in terms of their applications, each node's coverage and population density were considered as five weight categories. Each node's weight is influenced by the importance that the corresponding application will create in increasing the damage caused by the AP if infected. Applications were categorized as residential areas, hospitals, hotels, restaurants, religious sites, universities and passenger terminals. Higher weights are dedicated to the nodes covering multiple uses simultaneously. According to Table 1, the classification of the nodes' spatial importance is performed. A significance coefficient of between 0.05 and 0.005 was assigned to the damage calculation formulation. The higher the significance coefficient, the greater the likelihood of selecting a scenario in which the critical population is covered by the sensor.

In this research, six scenarios were considered. In all scenarios, the contamination (arsenic) is injected gradually for 1 h. The contamination entry is observed every hour of the day. In the first scenario, it is assumed that the contamination can be entered from all nodes and the pollutant rate in this scenario is 100 mg/s. Similar to the first scenario, the contamination entry from all the nodes is completely accidental in the second and third scenarios. The contamination entry occurs through all the nodes every 24 h, but the pollutant rates in these scenarios are 150 and 200 mg/s, respectively. In these three scenarios, the possibility of contamination entry from all the nodes is identical. In the fourth to sixth scenarios, nodes which are prone to contamination were identified. Therefore, the probability of the contamination entry is 0 and 1. In this section, it is assumed that the ground level components are easily accessible for the attack and are considered as the possible target of contamination. Thus, only a group of nodes are known as vulnerable ones, and the probability of contamination entry through them is 1. In these scenarios, it is assumed that only a subset of nodes is a potential target of attack. The vulnerable nodes were selected on the basis of the ease of access, security features, pressure relief valves, firefighting valves of the storage tanks and pumping stations. One of the factors of the easy access to the nodes is the urban texture consideration. City centers are the initially developed sections that are very ancient with poor protection and high accessibility. Therefore, it can be referred to as a vulnerable node.

The details associated with each scenario are presented in Table 2.

Here, A is the reaction rate coefficient, and nr stands for the reaction order constant. The value of A will be positive for the formation reaction and negative for the deterioration one.

The qualitative analysis of the network involves the simultaneous solution of the above equations together with those associated with the mixing process in the reservoirs.

The EPANET 2.0 has been implemented for preparing the hydraulic model of the network. This program includes a dynamic-link library called EPANET Programmers Toolkit that allows users to customize the EPANET computing engine with respect to their demands. The output of this program with the extension (.inp) is introduced as the input to the MATLAB environment. This software uses the gradient method to solve the network hydraulic equations and the Lagrangian transfer algorithm for solving the qualitative ones (Rossman 2000).

The simulation of the water distribution network was statically performed before 2004. In this way, the system response was only simulated to a particular and given state of flow (Watson et al. 2005). In this case, a specific moment was only considered as the maximum or minimum hourly flow, and qualitative analysis was ignored. Whereas, in this study, the pollutant transmission simulation is directly used for the quality analysis via the dynamic analysis of the flow. The pollutant materials mix with the water mass in the WDS. Assuming that the pollutant does not react with water, its dynamics is expressed by several parameters such as the water flow direction, intensity of the water flow and dilution of the pollutant concentration along the distance between the contamination entry site into the system and the location of the water consumption. Simulating the pollutant transmission in optimization requires analyzing a large number of contamination events. Accordingly, implementing the simulation to evaluate each new layout, will make the optimization methods very costly.

To solve this issue, the simulation is performed according to the scenarios being defined before conducting the optimization. Hence, the time simulation is separated from that required to run the optimization program.

As in the study of Shafiee & Zechman (2013), it is assumed that the health of an adult weighing an average of 70 kg is endangered with 3.5 mg of arsenic. Therefore, in this study, the population consuming 3.5 mg of arsenic or more is called the affected population. Nasirzade et al. (2018) and Khorshidi et al. (2018) considered the bulk flow reaction (0.05 day⁻¹) in the quality simulation. They did not consider the wall reaction coefficient for the quality simulation as arsenic does not react with the pipe's wall materials. Janke et al. (2017) defined a concept known as the sensor detection limit. According to this definition, the detection limit of the sensor is the concentration threshold above which the sensor is capable of detecting values (binary function).

The present problem approach is the optimal location of the quality sensors for the most critical possible scenario based on the robust optimization models. In this research, the assumptions are given as below:

1. The pollutant (arsenic) is stable, in other words, it does not react with the available substances in the water, and then the separation reactions take place in response to the contaminated water without any delay.

2. Each contamination event occurs at one point in the network.

3. When the sensor detects the contamination, an alert occurs and the network is closed.

4. Each node can be a possible location for the quality sensor placement.

5. For ease of the sensor locating problem analysis, the sensors are assumed to be flawless and detect the pollutant concentration to the allowable limit, without any negative or positive errors.

6. The contamination infusion starts at each hour of the day.

Here, is the damage at jth node and tth time step due to the contamination entry from the kth node at hth time step, and defines the contamination binary concentration at jth node and tth time step due to the same contamination entry data. Also, stands for the observational concentration at jth node and tth time step due to the contamination entry from the kth node at hth time step. Furthermore, ⁠, ⁠, ⁠, n_j and n_t define the consumption pattern coefficients, population vector, importance vector of each node, total number of demand nodes and simulation steps in the network, respectively.

According to the damage function coefficients, it is obvious that the obtained damage represents the virtual population affected by the contamination inflow.

is a binary parameter which causes damage to be calculated only before the flow is interrupted. It is clear that these values depend on the arrangement of the sensors and concentration values.

The location of the sensors should now be determined in such a way as to minimize the ⁠. In other words, the location of the sensors should be such that the worst possible damage (assuming the uncertainty in the location and time of the contamination entry) is minimized.

In the above problem, the bi-objective GA is used. This algorithm changes the location of the sensors enough to minimize the maximum possible damage to the network. The general outline of the method presented in this investigation is depicted in Figure 3.

In this section, it is assumed that the contamination can enter the water supply network from all nodes. The pollutant mass is different for these scenarios and varies between 100, 150 and 200 mg/s. The Pareto optimal is shown in Figure 4.

Generally, as the number of available sensors increases, one can reduce the damage due to the contaminated water consumption with the optimal placement. The damage reduction meets higher slope when the number of sensors is lower. However, it decreases with lower slope when the number of sensors exceeds a specific limit (10 sensors).

This means that for more than 6 sensors, increasing the pollutant dose does not have a noticeable impact on Pareto fronts. In Figure 5, this issue is addressed separately. Figure 5 plots the damage variations due to the arsenic entry with the increasing mass for various numbers of sensors (1–6 sensors). Upon placing one sensor within the network, the contamination mass increase from 100 to 150 and from 150 to 200 mg/s, increases the damage by 35 and 33%, respectively. However, this value significantly decreases with an increment in the number of sensors, so that the increasing contamination mass leads to an increase of 25 and 19% in the damage by locating 3 sensors, respectively. Furthermore, the least damage increase occurs upon placing 5 sensors in the network.

The primary aim of a WDS multi-objective model is to reach a solution that is optimal for the single-objective functions. Therefore, one of the solutions set on the Pareto must be selected to report it as the end result of the multi-objective design. To achieve this variety, various methods of conflict resolution exist in this regard. This study applies Young's method (Young 1993), in which one point is selected by maximizing a mathematical equation based on the Pareto's gradient of different points (Young 1993). By using this method, points (Figure 4) are chosen and differentiated by a square, diamond and circle for three scenarios in Figure 4. The optimal layout of selected points in this study is shown in Figure 6 for each scenario. As would be observed, the proposed sensor locations are well distributed throughout the city in order to minimize the maximum possible damage. Investigating the location of sensors in different scenarios shows that this placement is very diverse and not necessarily the same in all scenarios.

The suggested approach in this paper places sensors in nodes that can protect areas of greater importance from contamination. The key idea of this paper is to consider the importance coefficient of nodes in detecting a critical scenario. Thus, the sensors are located in places in this situation which minimize the critical scenario damage. Bahadur et al. (2003) also pointed out the importance and necessity of the role of users' sensitivity on the issue of pollution tracking but did not consider a specific framework for this task. In this paper based on He et al. (2018), the effect of the importance of all nodes in calculating the damage was considered. He et al. (2018) considered the importance of nodes as an independent probabilistic objective function. Unlike the method of He et al. (2018), which considered nodes as two categories and defined the same value for very important nodes, in this paper, nodes are divided into five categories in terms of importance and the significance coefficient was defined within the main objective function.

According to Figure 6, the findings reveal that besides the population covered by each node, the location of the sensors is influenced by the significance coefficient of the nodes. This finding is consistent with the He et al. (2018) findings.

Another important result discussed in the studied network is the examination of the most critical location and time step of the contamination entry into the network which cause the greatest possible damage. The entry of pollution is an independent scenario for measuring the damage at every time step. The reason for that is the hourly consumption pattern of each node's population. Therefore, it is expected that the most critical scenario for calculating damages is related to peak consumption hours.

In Figure 7, for each of scenarios 1–3, the most critical time and location of contamination entry are plotted corresponding to different number of sensors (1–10 sensors).

The results of most scenarios indicate that if the contamination enters the network at time steps within the interval 16–19, it will cause the highest damage. As expected, these results are consistent with the trend of the hourly consumption pattern.

The critical input node varies for different sensor placement conditions, but the range of the most critical nodes can be considered as illustrated in Figure 7. It seems that nodes 1, 3, 18, 22, 46, 57 and 60 are the ones causing the highest damage on the contamination entry.

In this section, it is assumed that contamination can possibly enter from only specific nodes having the potential for pollutant entry in terms of the urban context and access to the water network facilities. In other words, nodes in this area can be exposed to intentional contamination with a very high probability. The pollutant mass in these scenarios is 100, 150 and 200 mg/s, respectively. The optimal Pareto is shown in Figure 8.

One can minimize the damage caused by the contaminated water consumption through increasing the number of sensors and their optimal locations. According to Figure 8, it can be seen that the slope of the diagram is higher when only one sensor is placed in the network compared with the cases with more sensors. The slope of the graph changes with a gentle slope as the number of sensors exceeds 3.

Similar to Figure 5, the damage variation due to the arsenic entry with increasing mass is plotted in Figure 9 for various numbers of the quality sensors. It can be concluded that an increment in the contamination entry mass will not cause a noticeable change in the damage if the proper number of sensors with an optimal distribution are placed. In other words, by locating a sensor in the network, the contamination mass increase from 100 to 150 and from 150 to 200 mg/s, increases the damage by 62 and 10%, respectively. As the number of sensors increases, this value decreases markedly such that by locating 5 sensors, the increasing contamination mass only causes an increase of 0.03% in the damage and no change is observable in the network damage increase in the case of placing 6 sensors.

The optimal placement of the proposed algorithm for best solution based on Young's method (Young 1993) is shown in Figure 10 for each scenario.

As can be seen, the proposed locations for the sensors are well distributed throughout the city in order to reduce the maximum possible damage. The investigation of the location of the sensors in the different scenarios indicates that their location is approximately the same in all three.

In Figure 11, the most critical time and location of contamination entry associated with each of scenarios 4–6 are plotted for different numbers of sensors (1–10 sensors). The critical input node varies for different sensor placement conditions, but the range of the most critical nodes can be considered as illustrated in Figure 11. According to the figure, it seems that nodes 1, 3, 18, 22, 27, 46 and 60 are the ones exposing more people to damage upon the contamination entry.

Details of the optimal sensors placement are listed in Tables 3 and 4 for various numbers of the sensors. In these tables, in addition to the critical contamination entry times and optimal sensors location, the damage changes are presented for the increasing number of sensors from 1 to 6 relative to the absence of any sensors. Limiting the possibility of contamination from some nodes seems to have a significant impact on Pareto outcomes and the location of sensors. The reason for this is the difference in the selection of the critical scenario in the optimization process of the two mentioned strategies. It should be noted that, in a situation where pollution enters only from certain nodes, the cost and complexity of optimization are much less than a situation where pollution enters from all nodes.

The obtained results indicate that the location of the sensors differs from one scenario to another. However, it can be seen that some nodes, such as nodes 3, 43, 45 and 49, have been replicated in different scenarios, assuming the contamination entry from all nodes or from those with higher potential and play an important role in the network contamination spreading. These nodes appear to be appropriate places to put the sensors.

As can be seen from Table 3, by considering all three scenarios, the damage can be reduced by 50–67% by increasing only one sensor at the optimal location. These values are shown for other scenarios and more sensors. According to the results presented in Table 4, it can be seen that the damage is reduced by 93–95% by adding 6 sensors compared with the case of sensor absence in the entry network.

Due to the complex nature of water distribution networks and the great importance of drinking water quality in the health of society, in recent years, several studies have been conducted to maintain and guarantee water quality, especially in the event of terrorist attacks. In this regard, many optimization techniques have been developed to identify the optimal targeting of sensors. The predominant assumption in these techniques was that the probability of contamination of all nodes was the same. While some nodes may be important or sensitive users, even with low water consumption, the security of high-quality water should be guaranteed. In other words, water contamination of these users has social effects and more severe consequences than normal users.

In this paper, a method was proposed for optimizing the placement of quality sensors in the water distribution networks using two objectives of minimizing the number of sensors and maximum possible damage considering the minimum detection time. In this regard, six scenarios were defined in which uncertainties related to the location and time step of the contamination entry into the network were considered. The damage matrices were utilized in order to calculate the maximum possible damage. The significance coefficient of each node was taken into account while formulating the present problem.

The importance of nodes according to their location and use is a very important factor in safety of water quality which can be very effective in the identification of optimal solutions. The results revealed that by identifying nodes from which the probability of contamination is very high, it is possible to reduce computational costs and increase the probability of achieving an optimal sensing strategy. The observed results also indicate the necessity of this point. In other words, when there are less than six sensors, the damage and the dose of pollution that enters the network are directly related. The main model for sensors locating is a GA-based bi-objective optimizer that is used to minimize the maximum possible damage with the least number of sensors. This model is usable for any desired network. A real network was selected in Iran as the case study and its results were evaluated in six scenarios. The present achievements illustrated that adding only one sensor can reduce the damage by at least 50%. In this regard, the present proposal could well determine the optimal placement of a certain number of sensors. In this study, a range of appropriate sensor locations was proposed.

In closing, the results of this paper propose a complementary method for considering the importance of nodes in the process of sensor optimization and placement by using a data-based method. Further study of other uncertainties arising in the issue of placement of quality sensors, such as those corresponding to the type of pollutant and duration of the contamination infusion is suggested for future research.

Data cannot be made publicly available; readers should contact the corresponding author for details.