Optimal meter placement for pipe burst detection in water distribution systems

a

emitter pressure exponent

C

emitter discharge coefficient

D

detection matrix

D_ij

an element of D having a value of 1 or 0, indicating whether the ith burst event would be or would not be detected, respectively, by the jth meter

i

index for burst events

j

index for meters

m

total number of nodes or pipes

N_d

number of burst events that were detected

N_tb

total number of burst events

p_t,i

pressure at node i at time t

q_t,i

burst flow at node i at time t

t_di

time (h) of detection of the ith detected burst event

t_bi

time (h) of occurrence of the ith detected burst event

X

configuration vector

X_j

an element of X indicating whether there is a meter at the jth location (i.e., node or pipe) or not

X_max

number of available meters

ADT

average detection time

CUSUM

cumulative sum

CL

control limit

DP

detection probability

EWMA

exponentially weighted moving average

MCUSUM

multivariate CUSUM

MEWMA

multivariate EWMA

ROC

receiver operating characteristic

RF

rate of false alarm

SCADA

supervisory control and data acquisition

SPC

statistical process control

WL

warning limit

WEC

Western Electric Company

Pipe burst refers to the rupture of a pipe due to pipe deterioration, excessive pressure, or ground shifts caused by temperature changes or earthquakes. Water loss through the rupture increases the total flow entering the system, overall pipe flow rates, and head losses through pipes, which in turn, lowers the pressure at the customers' taps. Morrison (2004) reported that the time for detection and location of a 1.1 lps burst was approximately 5 days. Degradation of system functionality (i.e., performance level) persists until the broken pipe is fully repaired. Therefore, early detection of pipe bursts helps improve system resilience by minimizing water losses and system impact. In addition, it saves the energy cost spent in lifting the additional quantity of water.

Over the last two decades, several methodologies have been developed to detect pipe bursts. Most approaches assume the availability of information on measured pipe flows and/or system pressures from supervisory control and data acquisition (SCADA) systems, and include artificial neural networks (Mounce et al. 2002, 2003, 2010; Mounce & Machell 2006), state estimation (Andersen & Powell 2000; Ye & Fenner 2011, 2013), Bayesian approach (Poulakis et al. 2003), and time series modeling (Quevedo et al. 2010). Constructing a district metered area (DMA)-structured network was considered the most common alternative for detecting unreported leakages and small bursts (Morrison 2004; Misiunas et al. 2005; Sturm & Thornton 2005; Alkasseh et al. 2013).

Statistical process control (SPC) methods are most widely applied in the detection of pipe bursts (Misiunas et al. 2006; Romano et al. 2010, 2014; Palau et al. 2012; Jung et al. 2015). SPC methods apply statistical theory to the system output parameters (i.e., the measurable quality parameters, also known as quality characteristics) to identify non-random patterns that may be caused by bursts.

Romano et al. (2010) applied the Western Electric Company (WEC) rules (Western Electric Company 1958) to the pressure data from a 13 m long pipeline deployed in a DMA to identify pipe bursts generated by opening hydrants. Normal pressure data were used to compute time-varying mean and standard deviation that are the bases of Shewhart control chart and the resulting warning and control limits (CLs). Violating any of the four rules in the WEC rules caused an alarm. In a follow-up paper, Romano et al. (2014) employed the WEC rules in a real-time event detection model that included preprocessing of pipe flow/pressure measurements, forecasting pipe flows/pressures, detecting pipe bursts/other events, and estimating the probability of the events. The WEC rules are fixed as identifiers, thus making its application straightforward.

Jung et al. (2015) compared the performance of six SPC methods for pipe burst detection with respect to their detection effectiveness and efficiency: three univariate methods (the WEC rules, the cumulative sum (CUSUM), and the exponentially weighted moving average (EWMA) methods) and three multivariate methods (Hotelling T-squared, multivariate CUSUM (MCUSUM), and multivariate EWMA (MEWMA) methods). Hypothetical pipe flow and pressure measurements were generated at predefined locations in a modified Austin network (Brion & Mays 1991). The EWMA had the best detection effectiveness and efficiency among the six SPC methods.

In addition to being affected by the detection method, pipe bursts' detectability is affected also by the network structure and the available information. During design, the network structure is largely determined by land use, topography, and water demand distribution; pipe burst detection is not a primary concern at this stage. The amount of information on pipe burst detection in a measurement is a function of the number and types of meters and their locations, as well as the network structure and burst location. As such, measurements at some locations can include more signals of an anomaly than measurements at other locations.

To improve pipe burst detectability, the number of meters within the system can be increased. However, the number of meters that can be installed is normally limited by the network's structure, and more importantly, by the available budget. Therefore, finding an optimal sensor network design under budget constraints is a challenging task. Sensor network design methodology must identify: (1) the optimal number of meters, (2) the optimal combination of meters (pressure and pipe flow meters), and (3) the locations of the meters, and incorporate an optimal methodology for pipe burst detection.

In the water distribution systems (WDS) domain, a few studies have proposed sensor placement methodologies for pipe burst detection. Farley et al. (2010) have developed a sensor placement methodology to determine the most sensitive locations of pressure meters to detect pipe bursts at different locations. The approach was based on the Jacobian sensitivity matrix of pressure change as a function of burst rate at a given location. The Jacobian matrix was converted to a binary matrix where ‘1’ indicates that the pressure change is less than an arbitrary chosen threshold value, and ‘0’ indicates otherwise. The number of burst events detected was maximized using the generated binary matrix. In a follow-up paper, they proposed a pipe burst localization method using the Jacobian matrix (Farley et al. 2013). Perez et al. (2009) proposed a sensor placement method that determines the location of the smallest number of pressure meters for burst detection and localization. An enumeration technique was used to determine the threshold value for the Jacobian-binary matrix conversion. Wu & Song (2012) developed a pressure meter location method that maximizes the number of unique leakage events detected for a given number of candidate locations. Analogous to Farley et al. (2013) the Jacobian matrix of the pressure change was converted to a binary matrix, using the sensor instrument's measurement error as the threshold value. Huang et al. (2012) developed a clustering-based pressure meter placement method for pipe burst detection, by which the optimal number of meters was determined. A few studies considered a different criterion (e.g., accuracy of state estimation) for determining sensor locations (Kang & Lansey 2010).

While most previous studies were based on the Jacobian matrix of pressure change as a function of burst rate, an arbitrary threshold value was applied to convert the Jacobian matrix to a binary matrix. However, a more efficient pipe burst detection methodology (e.g., SPC method) should be applied to the raw field measurements to develop the binary matrix. In addition, most of the previous sensor placement studies focused on pressure meters only, without considering the potential detection effectiveness of pipe flow meters. Further, they neglected the importance of false alarms in determining sensor locations.

In this study, we develop and solve an optimal WDS meter placement model to identify the optimal meter locations that maximize detection effectiveness for a given number of meters and type of meter. An SPC method is used to populate the detection matrix (i.e., binary matrix) in the model. The linear programming-based model is demonstrated on a modified Austin network (Brion & Mays 1991). First, the pipe burst detection characteristics are investigated based on a single meter's performance. Then, the optimal sensor networks for pressure and flow meters are independently determined and compared. Finally, the trade-off relationship between the number of available meters and pipe burst detection effectiveness (with respect to not only detection probability (DP), but also false alarm frequency) is investigated by plotting the latter against the former.

RF is the proportion of natural random events in which a false alarm is issued among the total number of natural events. Therefore, DP is related to the false negative (type II error) rate, while RF indicates false positive (type I error) rate. The receiver operating characteristic (ROC) curve (Egan 1975), a graphical plot that illustrates the performance of a binary classifier system, is created by plotting the true positive rate against the false positive rate at various threshold settings. Therefore, the ROC curve for a sensor network for pipe burst detection displays plots of DP and RF for different number of meters to explore the trade-off between the two metrics.

The problem's objective (Equation (3)) is to maximize DP that is computed from the intermediate binary problem variable α_i. If one or more meters would detect burst i, then α_i is set equal to 1 (Equations (4) and (5)). If all possible sets of meters are considered, the search space of the problem will be 2^m. Here, the number of meters is included as a constraint (Equation (6)): (1) to reduce the search space, (2) to consider a field situation where the possibility of placing meters in the system is limited, and (3) to exclude the need for system-specific meter cost data.

Cost can be the main decision driver in this problem; the other drivers are meter types' access to power or SCADA data lines, and the location relative to these lines. For example, installing flow meters in a WDS is more expensive than installing pressure meters, because they require excavation, installation of a valve and a meter, backfilling, and pavement work (Walski 2012). On the other hand, pressure meters can often be installed inexpensively on fire hydrants. The flow meter is also more expensive than a pressure meter. To minimize cost, the above problem could be modified by deleting Equation (6) and changing the objective to the cost of installed meters and introducing a budget constraint. Equation (3) would become a constraint with a lower bound on the acceptable DP. Similarly, the false alarm rate can also be bounded by adding a false alarm matrix similar to D, but corresponding to a set of non-burst conditions that some meter locations identify as bursts. An alternative approach is to minimize RF; this also requires a false detection matrix (D_f) analogous to D. The rows and columns of D_f correspond to natural random events and potential meter locations, respectively. As in the case of D, the elements of D_f(D_f,ij) are 1 or 0 indicating whether a false alarm would be or would not be raised, respectively, on the ith natural event by the jth=meter.

To assess a sensor network's effectiveness, control measurements are generated considering randomness in nodal demands only, while out-of-control measurements are produced considering both random pipe bursts and random demands. The latter is used to develop a detection matrix, and the former is used to form a false alarm matrix. For both conditions, the WEC rules described below are applied to detect the outliers. With the detection matrix D, the optimization problem (Equations (3)–(6)) can be formed and solved. The optimal locations to limit the frequency of false alarms are also determined. Therefore, the objective function is to minimize RF by replacing D_ij with D_f,ij in Equation (4).

The WEC rules (1958) are a set of decision rules based on the Shewhart control chart for detecting non-random patterns in measured data (Montgomery 2009). Romano et al. (2010) modified the original WEC rules for WDS pipe burst detection and for identifying a non-random pattern, if the measured quality characteristic satisfies any of the following rules.

• Rule 1. Any single measurement is beyond the CL.

• Rule 2. Two out of three consecutive measurements are beyond the WLs.

• Rule 3. Four out of five consecutive measurements are beyond the WLs.

• Rule 4. Eight consecutive measurements are beyond the WLs.

The term refers to the warning/CL that is plus or minus n standard deviations from the mean. The WEC rules are applied to one side of the centerline at a time. In other words, a measurement on one side, immediately followed by a measurement on the other side of the centerline outside the WLs will not be taken into account as a non-random pattern. The WEC rules consider, at most, the eight most recent past measurements, having a potential to consider series of previous measurements in decision. Most of the previous detection methods used in sensor placement methodologies took into account a single/current measurement (Farley et al. 2010; Wu & Song 2012).

The WEC rules are easy to implement with no parameters to be estimated. Jung et al. (2015) confirmed that the WEC rules outperformed multivariate SPC methods with respect to DP. A DP of over 76% was obtained by applying the WEC rules when measurements of five meters are provided in a loop-dominated system. The DP increased up to 93% when pressure measurements of five meters are used for applying the WEC rules. On the other hand, application of the WEC rules results in relatively high false alarm rates when multiple meters are used. Therefore, determining the location of meters that yields minimum false alarm is also important while applying the WEC rules.

The detection matrix (D) has binary elements in which the ith row lists all the pressure/pipe flow meters that detect the ith pipe burst as per the WEC rules; its jth column lists all the pipe bursts detected by the jth pressure/pipe flow meter. The following steps are followed to populate D (Figure 2).

• Step 1. Generate a large number of pipe bursts with random magnitudes and locations.

• Step 2. Generate 100 2-day traces of pressure/pipe flow measurements considering random demands and the pipe bursts generated in Step 1.

• Step 3. Assuming that the jth pressure/pipe flow meter is installed in the network, determine if the ith burst is detected by examining the post-burst pressure/pipe flow measurements as per the WEC rules.

• Step 4. Set the element at the jth column's ith row as 1 if the ith pipe burst is detected by the jth meter and 0 otherwise.

• Step 5. Repeat Step 4 for all pipe bursts (i = 1, …, N).

• Step 6. Repeat Steps 3–5 for all pressure/pipe flow meters (j = 1, … , m).

To identify the optimal meter locations that yield minimum false alarm rates, a false alarm matrix can be developed in a similar manner, but constructed for random demand conditions without pipe bursts. The false alarm matrix has binary elements in which the ith row lists all pressure/pipe flow meters that raise a false alarm from the measurements resulting from the ith series of natural variability.

The optimal meter placement model was applied to a modified Austin network (Brion & Mays 1991). The modified network is a branch-dominated transmission system with several looped subareas. It consists of 125 nodes, a fixed head reservoir, 90 pipes, and seven pumps. The pipe sizes range from 152 mm (6 in) to 1,829 mm (72 in). Three out of the seven pumping units were consistently operated.

The other data sets were (1) a control sample and (2) the out-of-control set used to construct the false alarm and detection matrices, respectively. The control sample considers only natural demand randomness. The out-of-control data set includes demand randomness and pipe bursts. In total, 100 burst events and 100 natural random events were considered. The random burst characteristics are the burst location, initiation time, and burst magnitude. The burst magnitude is defined by the emitter coefficient C that was assumed to be uniformly distributed over the range of 1 to 50. A leakage exponent a of 0.5 is used for all the bursts. The resulting burst magnitudes ranged from 0.1 to 3.3% of the total system mean demand (726 lps). The quality characteristics' control and out-of-control measurements from a location were provided at a time for evaluation as per the WEC rules to populate the false alarm and detection matrices, respectively.

Shewhart control charts with a centerline, three WLs, and a single CL were constructed from the historical data set generated (Figure 3) for each potential meter location (i.e., all nodes and pipes). The mean nodal pressures and pipe flow rates vary over time because of the diurnal demand pattern. While the variances of pipe flow rates are relatively constant through the day, the nodal pressures have high uncertainty during peak demand hours, resulting in wider CLs. Low variations in nodal pressure were observed at night and early morning because of the low demand and low variability during these periods. Control and out-of-control measurements were evaluated as per the WEC rules, using the Shewhart control chart for the desired meter location, to construct the false alarm and detection matrices, respectively. The results for a pressure meter installed at node 15 and representing 15 burst events are summarized in Table 1.

A number of assumptions and simplifications were made in this hypothetical case study: (1) the hydraulic model perfectly represents the real system; (2) the pipe roughness coefficients and other system parameters are known with certainty; (3) a burst that is not detected within 48 h after its occurrence is considered as a non-detected event; (4) a natural random event that does not cause a false alarm within 48 h is considered as a non-false alarming event; (5) only one burst occurs in a span of 48 h; (6) the measurement error of a meter is negligible; (7) measurements are available every 5 min without any missing measurement; (8) only one meter is installed per node/pipe; and (9) the pressure and pipe flow rates are normally distributed around their mean centerlines in the Shewhart control chart, as confirmed in the study by Jung et al. (2015). In order to compare alternative pressure/pipe flow meters' configurations, detectability measures (Equations (1) and (2)) are calculated.

The meter location problem (Equations (3)–(6)) was solved for the Austin system for pressure meters with X_max ranging from 1 to 125. For pipe flow meters, a maximum of 90 pressure meter locations was available. The RF for the best DP set was computed. In addition to optimizing the DP, meter locations that minimized false alarm were also determined. The three results were combined in the ROC curves. A hundred random pipe bursts events were considered for the optimization. The detection and false alarm matrices had dimensions of 100 by 125 binary matrices for pressure meters, and 100 by 90 for flow meters. The binary integer programming problem was solved by the general reduced gradient (Abadie 1970) nonlinear solver in Microsoft Excel 2007. The solver was implemented on a 3.4 GHZ Intel Core i7 Quad processor with 8 GB of memory, running Window 7. A CPU time of approximately 0.27 s was required to find an optimal solution of the problem with a predefined number of available meters.

The differences in the optimal meter layout are because of the hydraulic characteristics of pressure and pipe flows. The pressure meter location having the most information for pipe burst detection is at the end of the network, because the pressure will drop when any nodal demand in the system is increased because of higher upstream head losses. On the other hand, the best flow meter location is in the pipes near the source, because pipe flows are affected most by the changes in flow downstream of the meter location.

Both meter types show a rapid increase in DP when the sensor network has only a few meters. For example, the five optimally located pressure meter network (meter installation level of 4%) has a DP of 72%, while the best five flow meter network (meter installation level of 5.6%) has a DP of 87%. When 10% of the pipes are monitored with flow meters, the DP is nearly 100%, and the DP is virtually 100% with 37 flow meters (meter installation level of 30%) (Figure 18(b)). The highest DP for pressure meters is approximately 82%. Although the DP is higher for flow meters, the false alarm rate is also high. The RF for the optimal pressure meters is consistent and lies between 10 and 20%. On the other hand, increasing the number of flow meters increases the RF until an RF of approximately 96% is reached.

Burst detectability is related to the magnitude of the burst and proximity to a sensor. Given the ability to install meters at many locations, it is difficult to identify the best sensor locations using only engineering judgment. Hence, a general optimal meter placement model to maximize the detectability of pipe bursts has been formulated as a binary integer optimization problem, and solved for a real network with hypothetical demands. The model designs a sensor network that attempts to detect a set of randomly generated bursts.

A multi-step process is required to formulate the meter placement problem, including: (1) developing Shewhart control charts for each possible flow and pressure meter location using the network's hydraulic model and random nodal demands; (2) generating control and out-of-control events to test the sensor network's ability to detect anomalies; (3) applying the WEC rules to produce false alarm and detection matrices for the test events; and (4) solving the binary integer optimization problem. Two objective functions, to maximize the DP and minimize the RF, were posed while constraining the allowable number of meters. The ROC curves were evaluated for the resulting designs, and the sensitivities of DP and RF were investigated with respect to the level of available information.

Prior to solving the optimization problem, the results from the first three process steps were studied to better understand the burst detection monitoring. Pipe burst detection characteristics were investigated based on a single meter's performance. Most pressure meters had a DP of approximately 70%, which is much higher than the overall DP of the flow meters. On the other hand, the RF was less than 10% regardless of the type of meter. Many pressure meters can detect a large set of the same bursts, while each flow meter detects fewer events that are likely to be more localized. Finally, most pipe bursts were detected at night and early morning because of low demand variability during these periods.

The optimal sensor networks were distinctly different depending on whether pressure or flow meters were installed. While maximizing the DP, the pressure meters were located at distal locations relative to the water source, while the pipe flow meters were installed near the source. The meter locations that yield minimum false alarm were also identified. The results were opposite to those corresponding to the best DP locations. The optimum location for pressure meters is near the source, while the optimum location is near the end of the network for pipe flow meters. It appears that the downstream nodes are impacted more by bursts due to higher head losses that accumulate through the network during a burst. Conversely, the flow at the upstream pipes is more sensitive to the downstream anomalies. The ROC curves for the alternative pressure and pipe flow meters showed that using many pipe flow meters could detect all the pipe bursts when the maximum DP with the pressure meters was 82%. As flow meters are vulnerable to false alarms, using pressure meters is likely to be more valuable for pipe burst detection in the modified Austin network.

The proposed sensor placement model employed the WEC rules which are the easiest to implement, as there are no parameters to be estimated. However, other SPC methods with higher detection effectiveness, such as CUSUM and EWMA can replace the WEC rules for improving detectability, although the system-specific parameters should be estimated by paying high computational costs.

This study has several limitations that future research must address. First, as in most sensor network designs, the layout is based on a limited set of conditions. Here, we have defined a set of bursts; the final design may be biased by this set, and some study should be conducted to determine how large a set is needed to converge to a consistent design. Multiple simultaneous bursts can be generated and provided for burst detection. Second, this study determined the optimal locations for pressure and flow meters independently. The optimal combinations of pressure and flow meters and their locations can be determined with a small extension of the posed model. Along this line, meter costs and a budget constraint can be included in the optimization model, instead of only limiting the number of meters. Third, as confirmed from this study, a trade-off exists between DP and RF. Multi-objective optimal meter placement problems can be formulated to minimize total meter cost and RF and maximize DP. This study and the previous studies focused on burst occurrence detection. However, since all the pressure meters detect the same set of bursts, they provide little information on where the burst is located. To provide a truly effective monitoring system, it is necessary to simultaneously consider the possibility of detecting and locating bursts, while minimizing false alarms and detection time. Finally, the proposed approach can be applied to detect real-life bursts by including additional preprocessing steps such as raw measurement filtering.

This material is based in part upon the work supported by the National Science Foundation under Grant No. 0835930. The opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.