Robust sensor placement for leak location: analysis and design

Water loss due to leaks in pipelines is one of the main challenges in efficient water distribution networks (WDNs). Leaks in WDNs can sometimes happen due to damage and defects in pipes, lack of maintenance, or increase in pressure. Leaks can cause significant economic losses and must be detected and located as soon as possible to minimize their effects. Some techniques and methods used to detect and locate leaks are based on the sensors installed in the network. Ideally, a sensor network should be configured to facilitate leak detection and location and maximize diagnosis performance under a given sensor cost limit.

In WDNs, only a limited number of sensors can be installed due to budget constraints. Since improper selections may seriously hamper diagnosis performance, the development of sensor placement strategy has become an important research issue in recent years. In particular, leaks in WDNs are an issue of great concern for water utilities. Continuous improvements in water loss management are being applied and new technologies being developed to achieve higher levels of efficiency (Puust et al. 2010).

Since Walski's (1983) study, many works that deal with the problem of optimal pressure sensor placement for hydraulic model calibration have been published. In particular, in Kapelan et al. (2005), a methodology based on single-objective and multi-objective genetic algorithms was presented. In the case of leak location purposes in WDNs, optimal locations of pressure sensor methodologies based on hydraulic simulations have been proposed (Farley et al. 2010). Some of the recent works that deal with the problem of leak location are based on the fault sensitivity matrix (Pérez et al. 2011; Casillas et al. 2012), which contains the information about how leaks affect the different node pressures. On the other hand, optimal pressure sensor placement algorithms that use the sensitivity matrix have been developed to determine which pressure sensors have to be installed among hundreds of possible locations in a WDN to carry out an optimal leak location as in Casillas et al. (2013) and Sarrate et al. (2014b). The fault sensitivity matrix can be obtained by convenient manipulation of model equations as long as fault (leak) effects are included in them (Blesa et al. 2012). Alternatively, it can be obtained by sensitivity analysis through simulation (Pérez et al. 2011). The elements of this matrix depend on the operating point defined by the heads in reservoirs, the inflow, demand distribution, which is not constant, and the leak magnitudes, which are unknown.

In this paper, the robustness of the sensor placement methodology introduced in Sarrate et al. (2014b), where only inner pressure sensors in the district metered area (DMA) were considered, is evaluated. As this methodology was conceived for a nominal case, from now on it will be referred to as the nominal sensor placement methodology. The study is based on the generation of different leak scenarios, taking into account different leak magnitudes on the one hand and several operating points on the other hand. A robustness percentage index, which is based on the leak locatability index, is defined to assess the robustness of the nominal sensor placement methodology.

The robustness study concludes that there is a significant dependency of the nominal sensor placement methodology on the network operating point. This motivates the need for developing a new sensor placement methodology that can cope with uncertain operating conditions. As a result, a robust sensor placement methodology is proposed, which is formulated into a multi-objective optimization strategy. This multi-objective problem provides a set of Pareto optimal solutions, from which a decision-maker chooses the preferred one.

The robustness study and the robust sensor placement methodology are illustrated by means of a simple network with 12 nodes and a DMA in the Barcelona WDN with 883 nodes. In this latter case, a clustering technique is combined with the sensor placement methodology to reduce the size and the complexity of the problem.

Model-based fault diagnosis techniques are applied to detect and locate leaks in WDNs. In model-based fault diagnosis (Blanke et al. 2006) a set of residuals are designed based on a process model. Fault detection and isolation is achieved through the evaluation of residual expressions under available measurements. A threshold-based test is usually implemented in order to cope with noise and model uncertainty effects. At the absence of faults, all residuals remain below their given thresholds. Otherwise, when a fault is present, the model is no longer consistent with the observations (known process variables). Thus, some residuals will exceed their corresponding thresholds, signaling the occurrence of a fault. In model-based fault isolation, the magnitude of the residuals that are inconsistent are compared against the different expected residual fault sensitivities, looking for the most probable fault that leads to model inconsistencies (residuals).

Thus, in general, the FSM defined in (1) is not constant but depends on the leak magnitude (f) and the operating point ⁠, i.e., ⁠.

A leak can be detected as long as there exists at least a residual sensitive to it.

The quality of a leak diagnosis system can be determined through the evaluation of leak detectability and locatability properties (Sarrate et al. 2014b).

Following the leak location criteria defined in Equation (7), the leak locatability index aggregates the normalized projection degree between the residual fault sensitivity vectors for all combinations of two leaks. Since a minimal normalized projection is desired, the greater the index is, the better it is.

Usually, the sensor placement problem is presented as an optimization problem where the cheaper sensor configuration fulfilling some given diagnosis specifications is sought (Bagajewicz et al. 2004; Sarrate et al. 2012). Nevertheless, a baseline budget is usually assigned to instrumentation by water distribution companies which constrains the maximum cost of the sought sensor configuration and consequently the achievable diagnosis specifications. Thus, in the water distribution domain, companies rather seek the best diagnosis performance that can be achieved by installing the cheapest number of sensors that satisfy the budget constraint. Henceforth, the sensor placement methodology introduced in Sarrate et al. (2014b) is evoked.

Let S be the candidate pressure sensor set and the maximum number of pressure sensors that can be installed in the network according to the budget constraint. Although fewer pressure sensors could be installed in the network, in this work it is assumed that sensors should be installed. Then, the problem can be roughly stated as the choice of a configuration of pressure sensors in S such that the diagnosis performance is maximized. This diagnosis performance depends on the set of sensors installed in the network and will be stated in terms of the detectable leak set and the leak locatability index, i.e., and I(S).

To solve the sensor placement problem, a network model is also required. The leak sensitivity matrix corresponding to the complete set of candidate sensors is assumed to be previously computed in a given operating point and for a given leak magnitude f, as described in the section ‘Leak detection and location in WDNs’. Hence, the nominal sensor placement for leak diagnosis can be formally stated as follows:

• GIVEN a candidate sensor set S, a nominal leak sensitivity matrix ⁠, a leak set F, and the number of pressure sensors to be installed.

• FIND the -pressure sensor configuration such that:

  1. all leaks in F are detectable, ⁠, and

  2. the leak locatability index I(S) is maximized, i.e.,

     

This optimization problem cannot be solved by efficient branch and bound search strategies. Thus, a suboptimal search algorithm based on clustering techniques will be applied. However, in order to alleviate the suboptimality drawback of clustering techniques a two-step hybrid methodology that combines them with an exhaustive search is proposed:

• Step 1 Clustering techniques are applied to reduce the initial set of candidate sensors S to ⁠, such that the next step is tractable. Step 1 will be described in the next section.

• Step 2 An exhaustive search is applied to the reduced candidate sensor set ⁠. This search implies that the diagnosis performance must be evaluated times. The most time demanding test concerns the evaluation of the leak locatability index for every pair of leaks which involves computing times the normalized projection of the leak sensitivity vectors. Thus, in all, an exhaustive search is of factorial complexity with the number of candidate sensors ⁠, but an optimal solution for the given reduced candidate sensor set is guaranteed.

In Sarrate et al. (2014a), a reduction in the number of candidate sensors has been proposed by grouping the n initial sensors candidate into groups (clusters) applying the evidential c-means (ECM) algorithm (Masson & Denoeux 2008).

Given a set of objects ⁠, clustering consists in partitioning the observations into groups in such a way that objects in the same group (or cluster) are more similar (in some sense) to each other than those in other clusters.

Given the vectors ⁠, ⁠, and that contain the plausibility values of the elements of the cluster set ⁠, the row numbers of the sensitivity matrix defined in Equation (1) relate to the elements of this cluster (sensor numbers) and the Euclidean norm of these rows of the sensitivity matrix. Algorithm 1 provides the vector with N representative elements (sensors) of the cluster ⁠: ⁠. The bigger N is the more representative the elements of the set are. In this algorithm, in addition to the plausibility values, the Euclidean norm of the sensor sensitivity matrix is taken into account in order to obtain sensor candidates that maximize the leak detectability defined in Equation (8).

The robustness analysis will concern the leak magnitude uncertainty and the operating point variation. Both analyses will be done separately.

On the one hand, the study concerning leak magnitude uncertainty will involve, for a given nominal operating point ⁠, evaluating the effect of possible uncertain values of the leak magnitude within a given interval on the nominal sensor placement methodology. This analysis considers a finite number sf of scenarios that lead to sf different FSMs ⁠, where and ⁠.

On the other hand, the study concerning the operating point variation will involve, for a given nominal leak magnitude ⁠, evaluating the effect of the operating point variation (total inflow, demand distribution, etc.) on the nominal sensor placement methodology. This analysis considers a finite number of representative operating point scenarios in the network that lead to different FSMs ⁠.

Concerning the operating point robustness study, scenarios are generated with EPANET by specifying several values for the network total inflow.

Five scenarios are defined concerning leak magnitude uncertainty (⁠⁠, f = {0.5, 0.7, 0.9, 0.93, 0.95}) corresponding to leaks of {3.5 lps, 4.9 lps, 6.3 lps, 6.51 lps, 6.65 lps}, respectively, and five others related to operating point variation (⁠ lps, lps). Note that the operating point is defined here by the network inflow and leaks are characterized through the emitter coefficient, i.e., f=EC.

Assume that a sensor placement problem with is to be solved. Concerning the fault detectability constraint, mm/lps is considered in Equation (8).

Notice that the normalized vector for all the considered leaks is almost the same. Thus, a nonsignificant variation in the locatability index (9) is expected for the different leak scenarios. Figure 2(b) shows the evolution of the same components of for different operating points ⁠, considering the same leak magnitude in all the leak scenarios. In this case, the variation that the normalized vector exhibits is remarkable. Thus, some variation in the locatability index (9) is expected for the different operating point scenarios.

In this case the network size is small and the clustering procedure is not needed to solve the sensor placement problem. Thus, just step 2 of the methodology outlined in the section ‘Nominal sensor placement methodology’ has been directly applied. Table 1 provides the resulting leak locatability matrices. At the top row, the optimal sensor locations for each scenario are provided.

The robustness percentage index for leak magnitude uncertainty is 3.94%, which means that the nominal sensor placement results are very robust against this kind of uncertainty. However, the robustness percentage index for operating point variation is 14.43%, which proves some dependency of the nominal sensor placement results on this kind of variation.

The same scenarios defined for case study 1 are considered for case study 2.

Pressure sensors at RM nodes set up the candidate sensor set. Assume that a sensor placement problem with has to be solved. Concerning the fault detectability constraint, mm/lps is also considered in Equation (8).

Note that there is an appreciable variation between the clustering obtained considering the nominal FSM and the one obtained considering the extended FSM.

The exhaustive search of the section ‘Nominal sensor placement methodology’ is next applied to the reduced candidate sensor set provided by the clustering algorithm based on the extended FSM. Table 2 provides the resulting leak locatability matrices.

Results are similar to case study 1 concerning robustness analysis. Note that the same optimal sensor configuration results regardless of the leak magnitude uncertainty, which implies that the corresponding robustness percentage index is 0%. Thus, the nominal sensor placement results are again very robust against this kind of uncertainty. However, the robustness percentage index for the operating point variation is 34.31%, which also proves some significant dependency of the nominal sensor placement results on this kind of variation.

Given the significant dependence of the leak detection and location procedure performance on the water network operating point, the goal of this section is to propose a sensor placement methodology that provides a set of pressure sensors that guarantee a robust performance. Thus, the nominal sensor placement methodology stated in the section ‘Nominal sensor placement methodology’ should be reformulated in order to cope with a new robustness specification. The robust sensor placement problem is cast into a multi-objective optimization strategy as follows:

• GIVEN a candidate sensor set S, a set of leak sensitivity matrices for representative operating point scenarios, a leak set F, and the number of pressure sensors to be installed.

• FIND the -pressure sensor configuration such that:

  1. all leaks in F are detectable, ⁠,

  2. the mean leak locatability index is maximized, i.e., ⁠, and

  3. the worst leak locatability index is maximized, i.e., ⁠.

Although two robustness specifications have been stated, other specifications could be included in the sensor placement problem. Since, in a multi-objective optimization set-up, both robustness specifications cannot usually be met at the same time, a Pareto optimality will be sought (Caramia & Dell'Olmo 2008). Given a set of objective functions, a solution is said to be Pareto optimal if no other feasible solution that improves an objective function without degrading at least one of the other objectives exists. There is usually a set of Pareto optimal solutions which is often called the Pareto front. The first goal of the robust sensor placement procedure will be to find the Pareto front. From this Pareto set, a decision-maker should examine the optimal solutions and through higher-level reasoning, choose the most suitable solution.

Different techniques exist to generate the Pareto front, such as those based on a linear scalarization (Das & Dennis 1997) or evolutionary algorithms (Deb et al. 2002). In this work, as in the case of the nominal sensor placement methodology, a two-step hybrid methodology that combines clustering techniques with an exhaustive search procedure is proposed. This methodology allows the computation of an approximation of the entire Pareto front for complex problems.

• Step 1 Clustering techniques are applied to reduce the initial set of candidate sensors S to ⁠, such that next step is tractable. The method described in the section ‘Candidate sensor set reduction’ is applied. However, now, in order to cope with the robustness requirement, the extended FSM defined in Equation (16) is considered.

• Step 2 An exhaustive procedure is applied to the reduced candidate sensor set ⁠. This procedure implies times the computation of the detectable leak set, as well as the mean and worst locatability indices. The most time demanding computation concerns the evaluation of both indices, which involves computing times the normalized projection of the leak sensitivity vectors. Thus, in all, this exhaustive search is of factorial complexity with the number of candidate sensors ⁠.

As in the case of evolutionary algorithms, the Pareto optimality of the solutions cannot be guaranteed, but none of the generated solutions dominates the others. For demonstration purposes, one solution, that is relatively good for both objectives, will be chosen from the Pareto front.

The robustness analysis of the sensor placement problem based on leak sensitivity matrix analysis in WDNs has been addressed in this paper.

A robustness percentage index has been introduced to evaluate the variation of the leak locatability index achieved by nominal sensor placement strategies for different leak magnitudes and DMA operating points.

A robustness analysis has been applied to an academic network and to a DMA in the Barcelona WDN. Results show that there is not an important variation of the leak locatability index when different leak scenarios are considered, but the variation can be significant when different operating point scenarios are considered. Therefore, this variation should be considered in optimal sensor placement strategies.

An important contribution of the paper is the development of a robust sensor placement methodology that takes into account the dependency of the leak location procedure on the network operating point. The robust sensor placement problem is formulated as a multi-objective optimization for which Pareto optimal solutions are generated. An exhaustive search is proposed to provide the Pareto front. In order to reduce the size and complexity of the optimization problem, a clustering technique based on an extended sensitivity matrix is applied beforehand to reduce the number of candidate sensors.

The exhaustive search provides the optimal Pareto front for the reduced candidate sensor set, but it is highly inefficient. Future research will focus on genetic algorithms or simulated annealing which will increase efficiency at the expense of global optimality.

The robust sensor placement methodology has focused on decoupled network operating uncertainties. However, the methodology could be easily extended to account for simultaneous uncertainties, provided that a complete set of fault sensitivity matrices could be generated. Of course, this would involve an increase in time complexity.

Future research should improve the formulation of the sensor placement problem presented in this paper. Currently, a solution with exactly pressure sensors has been sought. However, the leak locatability index does not exhibit monotonicity on the cardinality of the sensor configuration. This means that sensor configurations with fewer pressure sensors could eventually improve the leak location performance of the network. Thus, developing algorithms that seek for a maximization of the leak location performance while minimizing the sensor expense would be desirable. Additionally, in the formulation of the multi-objective optimization, other convenient robustness criteria for the decision-maker could be investigated.

This work has been funded by the Spanish Ministry of Economy and Competitiveness through the CICYT projects ECOCIS (ref. DPI2013-48243-C2-1-R) and HARCRICS (ref. DPI2014-58104-R), and by the European Commission through contract EFFINET (ref. FP7-ICT2011-8-318556).