Efficient Sensor Placement for Leak Localization Considering Uncertainties

In well maintained water distribution systems (WDS), only 3 - 7 % of water is lost. Though in developing countries this number can go up to 50 % and more (Colombo et al. 2009). Most of the lost water originates from leaks.

Therefore, water loss reduction through locating and repairing leaks in WDS is becoming increasingly important.

In terms of leak localization water utilities follow two different approaches, the active and passive leakage control (Puust et al. 2010). In case of the passive approach, the utility waits until customers report leaks because they experience supply problems or leakages find their way to the surface and thus become visible. However, not all leaks become visible leading to high unreported leaks and hence to high total water losses.

The better strategy to reduce water losses is active leakage control (Farley and Trow 2003). One central task of an active leakage control strategy is searching for leaks on a regular basis. Different methods are applied for finding the position of leaks, like e.g. step testing or by temporary placing acoustic loggers. These methods are referred to as leak localization, which has the purpose of limiting the possible location of a leak to several hundred meters. Leak localization has to be followed by pinpointing to get the exact position of the leak e.g. with ground microphones, leak-noise correlators or gas leak detection.

Model-based leak localization methods have been introduced over the past few decades using measurement data from hydraulic sensors along with hydraulic models. In general, two different techniques are available. First, steady state analysis based techniques, second, transient based techniques (Colombo et al. 2009).

This paper is based on steady state leak localization, which was first proposed by Pudar and Liggett (1992). They formulated an inverse problem where the discrepancy between real-world measurements and data obtained from hydraulic simulations was minimized. Since then, leak localization by solving inverse model-based approaches has been extensively investigated (e.g. Wu et al. 2010; Pérez et al. 2011).

In fact, the success of model-based leak localization depends to a great extent on the choice of the measurement positions within a WDS (Kang and Lansey 2010). For that reason optimal sensor placement (OSP) has the potential for significantly improving the localization of leaks.

While much research work has been put into dealing with OSP for contaminant detection and WDS model calibration (see for example Savic et al. 2009), only few studies have focused on the same problem for leak localization.

The first discussion and analysis of OSP for leak localization emerged in 2008 with the work of Farley et al. (2008, 2010, 2013), followed in 2009 by Pérez et al. (2009). Both OSP approaches are based on the leak sensitivity matrix. The approach of Pérez et al. (2009) binarizes this matrix which leads to a loss of information (Quevedo et al. 2011).

To overcome this information loss, Casillas et al. (2013) formulated the OSP as an integer optimization problem based on projections from a non-binarized leak sensitivity matrix solved with a semi-exhaustive search and a genetic algorithm (GA).

Subsequently, Pérez et al. (2014) defined a greedy-search algorithm, which minimizes the maximum distance of leak scenarios to the gravity center of the nodes with projections over 99 % of the maximum value of the projections. This resulted in more robust sensor placements.

Recently, Cugueró-Escofet et al. (2015) extended the approach of Casillas et al. (2013) with a relaxed isolation index taking practical applications like the acceptable isolation distance into account.

Alternatively, Sarrate et al. (2012) invented a strategy maximizing a ”leak isolability index” based on structural analysis of a WDS solved by a depth-first search algorithm. Since this strategy is only capable of medium-sized networks, it is combined in Sarrate et al. (2013) with clustering techniques to reduce the size and complexity of the OSP problem. However, due to its simple description, structural analysis cannot ensure that the diagnosis performance obtained from such models hold for real-world systems. Therefore, in Sarrate et al. (2014) the approach is combined with projections calculated again from sensitivity matrices.

Nejjari et al. (2015) invented an algorithm based on pressure sensitivity matrix analysis using an exhaustive search strategy with average worst leak expansion distances as sensor placement performance measure.

Currently, Casillas et al. (2015) placed sensors in an optimal way by minimizing the overlapping signatures in the leak signature space.

A completely different approach was introduced by Christodoulou et al. (2013), who invented an entropy-based OSP algorithm by maximizing the total entropy in the network.

In hydraulic modeling as well as in measuring hydraulic parameters one has to face several sources of uncertainty (Hutton et al. 2014). We therefore assume that these effects should be taken into account in OSP algorithms. Blesa et al. (2014) studied the robustness of the methodology introduced by Sarrate et al. (2014) against sensitivity matrix uncertainties. The main result was that the sensor positions are not sensitive to the size of the leaks, but to the working point of the WDS. Furthermore, Blesa et al. (2015) used multi-objective optimization to place sensors. The objectives were to determine the mean and the worst locatability index.

Both papers investigate the consequences of uncertainties on the OSP algorithms, but neither of them incorporates these uncertainties in the OSP itself. To the best of our knowledge, Steffelbauer et al. (2014) was the first study incorporating uncertainties in the OSP problem. Unfortunately, the problem was only solved for four sensors.

The aim of this paper is to extend the work described in Steffelbauer et al. (2014) providing a methodology that uses cost-benefit functions for predicting the sensor placements quality for leak localization depending on the number of sensors as well as the strength of general and not only demand uncertainties. Therefore, it provides WU with a methodology that helps them to decide how many sensors should be placed in their system for leak localization.

First, the effect of demand uncertainties on possible pressure measurement points is investigated according to Section 2.3. MCS with 10000 mcsteps are performed with random demands drawn from a normal distribution using the nodal demand at minimum night flow as mean μ _q and a standard deviation σ _d of 10 % . The resulting \(\sigma _{p_{i}}\) of the nodal pressures are depicted in Fig. 2a.

The sensitivity matrix S is calculated as described in Section 2.2. Leakage scenarios were generated with an emitter coefficient of c _e = 0.5 in EPANET for every node in the system. Only one leak size c _e = 0.5 was chosen to build the sensitivity matrices, since Blesa et al. (2015) has found that the sensor positions are not sensitive to leak sizes. The overall sensitivity at every possible measurement position \(\overline {s_{j}}\) in the system is calculated by Eq. 4 and plotted in Fig. 2b.

In the upper region of the case study area exist points that are sensitive to demand uncertainties Fig. 2a. Therefore, this points should be punished by an OSP algorithm. For solving the OSP problem it is needed to compute the residuals R. In this paper R are calculated with the same emitter coefficient c _e = 0.5 as S.

\(\sigma _{p_{i}}\), S and R are then used for solving the enhanced OSP problem described in Section 2.4. The OSP problem is solved for a different N ranging from 2 to 10 and different ω (with ω = (0.0, 0.125, 0.25, 0.5, 1.0)).

The range of N was chosen, because for N = 1 the ideal sensor position is trivially at the point with the highest overall sensitivity and N > 10 was viewed as uneconomical for the size of the investigated WDS.

ω was chosen between ω = 0.0, which corresponds to the case with no uncertainties, and ω = 1.0, which takes the uncertainties into account with full strength. Simulations with ω = 1.0 have shown that the sensors cluster too much in regions with low demand uncertainties and are not spread anymore over the whole system (e.g. see Fig. 3h). Therefore, ω was halved so long \((\omega =1.0\xrightarrow {1/2}0.5\xrightarrow {1/2}0.25\xrightarrow {1/2}0.125)\) until sensors appeared again in the upper part of the system with high demand uncertainties.

For each combination of N and ω the GA described in Section 2.5 is applied 10 times solving the enhanced OSP. Due to the stochastic behavior of the GA, the resulting sensor placement quality parameters \(\overline {\epsilon }(\mathbf {q})\) may vary for different optimization runs with same N and ω parameters. Table 1 thus illustrates the statistics of \(\overline {\epsilon }(\mathbf {q})\) found during 10 optimization runs and contains the mean, the minimum and the standard deviation of \(\overline {\epsilon }(\mathbf {q})\) of all runs.

In Fig. 3 the optimal sensor positions for selected values of N and ω are presented¹. The first four plots (Fig. 3a to d) show the OSP results for N = 2 to N = 5 with ω = 0.0, whereas the last four plots Fig. 3e and h show results for five sensors under incorporation of uncertainties with varying ω (between 0.125 and 1.0).

Without uncertainties the algorithm tends to place sensors in regions with high demand uncertainties (upper part in Fig. 2). This can be seen in Fig. 3a to d. The higher ω, the more the sensors move to regions with low demand uncertainties (see Fig. 3d to h). Therefore, the extension of the OSP algorithm by incorporating uncertainties shows the desired behavior by punishing measurement points with high uncertainties. Nevertheless, this decreases the spreading of the sensors over the whole system since sensors tend to cluster in areas with low uncertainties.

Additionally, in Fig. 3a to d it can be seen that the optimal set for N − 1 sensor positions \({\mathcal {P}(N-1)}\) is not a subset of the optimal placement \(\mathcal {P}(N)\) of N sensors (\(\mathcal {P}(N-1) \nsubseteq \mathcal {P}(N)\)). The algorithm leads to different sensor positions for different N. The same results are also found by Kapelan et al. (2005) for sensor placement for model calibration.

Finding the mathematical law behind the cost-benefit function describing the OSP is a main objective of this paper since it provides WU with a methodology to answer how many sensors should be placed in a WDS for leak localization. To predict the behavior of \(\overline {\epsilon }(\mathbf {q})\) on N for different ω, the resulting mean values were chosen, fitted with different functions and subsequently tested with GoF statistics to figure out which mathematical law the cost-benefit functions follow.

Different functions were taken into account describing the decreasing behavior one can see in Fig. 4 of the results of the GA.

Table 2 shows the result of the fits. In the first column, the different functions which were fitted to the \(\overline {\epsilon }(\mathbf {q})\) values as a function of N are shown. N _p is the number of parameters, ν the number of degrees of freedom. χ ² is the value resulting from χ ² statistics calculated by Eq. 12, \({\chi _{r}^{2}}\) is the value from the reduced χ ²-statistic (13), the value for Akaike’s information criterion aic is calculated using Eq. 14 and the value for Bayesian information criterion bic by Eq. 15. All values are the resulting means over the simulations with different ω. For example, χ ² in Table 2 is calculated through According to Table 2, function f ₆(N), an extended power law equation, leads to the best χ ² and \({\chi _{r}^{2}}\) whereas the simple power law equation f ₇(N) leads to the best aic and bic values. Table 3 shows the best-fit values of the parameters of functions f ₆(N) and f ₇(N) together with the estimated standard error for these values. The best-fit values for equation f ₆(N) show high standard errors, especially for parameters a and b, whereas the best-fit values of f ₇(N) show much lower error bounds. Therefore f ₇(N) is chosen as a cost-benefit function for the values in Fig. 4.

The power-law behavior of f ₇(N) has practical consequences for water utilities. This is shown through an example for ω = 0.0. Placing 3 sensors instead of 2 improves the quality of the sensor placement by Values are taken from Table 1. To get again the same improvement for 3 sensors, the water utility has to place double as many sensors as before going from 3 to 5 sensors For getting the same improvement for 5 sensors, 4 additional sensors, again double as many as before, have to be placed Therefore, for a linear improvement of the quality the number of sensors has to be doubled.

Furthermore, the power-law behavior stays true under incorporation of uncertainties, hence the former example is in general true. The only difference to simulations without uncertainties (ω = 0.0) is that the quality parameter of a sensor placement with a specific N becomes worse if ω is increased. This makes sense, since leaks are harder to find in real-world networks with high uncertainties compared to theoretical perfect known systems. For example, to achieve the same quality parameter as in simulations with no uncertainties (ω = 0.0) for N = 2 sensors, N = 4 sensors are needed for ω = 0.5 and N = 6 are needed if the uncertainty is fully taken into account (ω = 1.0). This can also be seen in Fig. 4.

Incorporating uncertainties in the OSP problem for leak localization is of great importance. Since points which are sensitive to demand variations can also be points which are sensitive to leaks (upper part of Fig. 2). Hence, leaks can be hidden by demand fluctuations for sensors placed at these points. Consequently, it may be harder to locate leaks with sensors at these points.

Nevertheless, nodes from this region are always chosen by the sensor placement algorithm if the uncertainty effects are not taken into account (see Fig. 3a to d for example). The enhanced algorithm in Section 2.4 supposes a way out of this dilemma. Increasing the ω value leads to placements avoiding these regions of high uncertainty.

Additionally, it is apparent from Fig. 3d to h that the higher ω is the more sensors are placed in regions with low uncertainties. Unfortunately, this leads to a clustering of sensors. However, a good sensor placement should also lead to positions that are spread over the whole WDS, since sensors are more sensitive to changes in their close proximity. Therefore, the OSP was solved not only for ω = 1.0, taking the full uncertainty into account, but also for smaller ω values. Nevertheless, the paper lacks in providing a methodology for choosing this value.

Another important finding is that the optimal set for N−1 sensor positions \({\mathcal {P}(N-1)}\) is not a subset of the optimal placement \(\mathcal {P}(N)\) of N sensors. Therefore, OSP algorithms that solve the problem by placing one sensor and find the next sensor position through incorporation of the previous one (greedy sensor placement algorithms) may not find global optimal solutions of the problem.

It has to be mentioned that for a high number of sensors the results in Table 1 must be treated with caution, since the search space becomes very large. Placing 10 sensors on 392 measurement locations (network nodes of the case study) results in ≈ 2 ⋅ 10¹⁹ possible combinations. Since the GA evaluates approximately 8000 times the fitness functions in one optimization run, this is just a small part of the total solution space.

Another interesting finding is that fitting the functions from Table 2 to the simulated sensor placement cost-benefit values lead to two equations, which both have a power law behavior (f ₆(N) and f ₇(N)). f ₆(N) has lower χ ² and \({\chi _{r}^{2}}\) values while f ₇(N) results in better Akaike and Bayes information criteria values. A closer look at the confidence intervals of the fitness coefficients leads to favor equation f ₇(N) . This curve is therefore chosen as the cost-benefit curve of the OSP for all ω parameters (see Fig. 4). It is surprising that higher ω parameters do not change the form of the cost-benefit curve, they merely lead to higher values of the cost-benefit function. One surprising finding is that the form of the function is robust against uncertainties.

The limitations of this study are that it can only be applied to WDS where a hydraulic model already exists since it is necessary to compute the sensitivity matrix. Additionally, the OSP algorithm is only as good as the model. For example, an unknown closed valve can have strong influence on the hydraulics and therefore the OSP result might not be optimal in reality.

Furthermore, for bigger systems the computation time increases for both, calculating the MOU as well as solving the OSP problem, making the method not directly applicable for big real world systems with thousands of nodes. Additionally, the OSP algorithm can only take single leaks into account, not multiple leaks.

This paper set out to determine the effect of MOUs (e.g. the effect of uncertain demands on pressures) on OSP for leak localization in a real-world network. The research has shown that pressure measurement points, which are sensitive to leaks may also be points which are sensitive to uncertain demand and hence less ideal to place sensors on. Incorporating MOU in the OSP algorithm leads to placements avoiding regions of high uncertainty.

The simulations confirmed that the optimal sensor positions for N − 1 sensors is not a subset of the optimal locations of N sensors. As a consequence, greedy sensor placement algorithms may fail in finding optimal measurement locations. Therefore, choosing GA to solve the OSP problem in this paper was the right decision.

Furthermore, this paper showed that the effect of the number of sensors on the sensor placement quality has a power law behavior. This even stays true under incorporation of uncertainties.

Although, the work in this paper focuses on the effect of demand uncertainties on the placement of pressure sensors, it should be mentioned that this method is more general in scope. The method is also applicable for other sensors (e.g. flow or quality sensors) and has capability for different sources of uncertainties as well (e.g. roughness, elevation, bulk reactions, ...).

A limitation of this study is the high computation complexity since the search space of the OSP problem can become very large even for small WDS. Clustering algorithms as in Sarrate et al. (2014) can show a way out in future work to reduce the complexity of the problem.