Controllability analysis as a pre-selection method for sensor placement in water distribution systems
Graphical abstract
Introduction
Placement of sensors in water distribution systems (WDSs) fulfills various objectives regarding modeling and operational control of such networks, such as data collection for parameter calibration, standard water quality monitoring [see e.g. Aisopou et al. (2012)], detection of contaminant intrusion (see e.g. Arad et al., 2013), etc. This manuscript focuses on the last aspect and discusses some aspects regarding sensor placement in WDSs for contaminant detection.
Contamination warning systems (CWSs) are expected to be a cost-efficient technology to mitigate risks (ASCE2004; American Water Works Association AWWA, 2005, Janke et al., 2006, U.S. EPA, 2005). Thus far, as it is too costly to place sensors at all locations in a network, a key issue in the design of CWS is the strategic placement of sensors within the distribution system (Storey et al., 2011). The placement strategy aims to minimize the potential public health impact from any contamination intrusion with a limited number of sensors (Hart and Murray, 2010). Note that usually at maximum a few tens of sensors are placed in a system. Thus far, three main approaches of sensor placement are described in the literature: empirical methods (Berry et al., 2005, Trachtman, 2006), empirically-based methods (Bahadur et al., 2003, Ghimire and Barkdoll, 2006, Xu et al., 2008), and optimization methods. Here, the empirically based methods refer to the ranking of potential sensor locations (Hart and Murray, 2010) based on expert information (e.g. data from geographical information system). Among these methods, optimization methods are the most advocated ones today, given their capability to enable automated sensor placement based on hydraulic and water quality simulation. Thus, a sensor network that minimizes contamination risks could be automatically planned using computationally search methods.
Ostfeld et al. (2008) compared 15 different approaches for sensor placement in the battle of the water sensor networks (BWSN). The current available optimizers are mainly based on integer programming (e.g. Lee and Deininger, 1992), mixed-integer programming (e.g. Propato, 2006), heuristic-based algorithms (e.g. Dorini et al., 2006), graph theory algorithms (e.g. Kessler et al., 1998), and genetic algorithm schemes (e.g. Ostfeld and Salomons 2004).
Although these methods can find near optimal sensor layouts (Hart and Murray, 2010), there are still obstacles and knowledge gaps, as pointed out by Hart and Murray (2010) based on results from real-world large utility networks. One of the most noteworthy obstacles is the computational efficiency. On the one hand, distribution networks are complex systems resulting in significant computational effort for water quality simulation (see also Arad et al., 2013). On the other hand, the optimization methods (especially GAs) entail a high computational cost in order to achieve a sound level of good solutions. Consequently, trade-offs between accuracy of the result and efficiency of the computation are commonly unavoidable. For instance, detailed models of the distribution network may be replaced by simplified ones (Perelman and Ostfeld, 2011). Further, with the exception of the TEVA-SPOT toolkit (Berry et al., 2008, Hart, 2008), existing sensor placement optimization methods assume that only a fixed number of sensors will be used in a CWS. To allow for a more efficient optimization - albeit less accurate result – the optimization strategies are frequently reformulated to reduce the solution sets [e.g. by decreasing the number of decision variables (Berry et al., 2007and Hart et al., 2008) and/or the number of considered scenarios (Preis and Ostfeld, 2007)].
Independent from the efforts to re-formulate the optimization methods, the prior use of preprocessing strategies is another generally applicable technique for reducing the computational load (Hart and Murray, 2010). For example, contamination simulations can be excluded from the optimization process by performing offline simulations as a preprocessing step (Berry et al., 2006, Chastain, 2006, Krause et al., 2008, Propato, 2006). As the most efficient way to speedup the process is the reduction of the number of candidate nodes, Guan et al. (2006) and Aral et al. (2008) introduced the sub-domain approach into the genetic algorithm. Specifically, a roulette wheel method was applied to choose the sub-domain based on nodal water demands for all scenarios. Huang et al. (2008) used a prior preparation of the database to provide initial solutions for optimization. The database stores data for intrusion events at each node and the classified consequences of these intrusions. By exploiting the submodularity property of objective functions, the approach proposed by Krause et al. (2008) can achieve at least a fraction of (1 − 1/e) of the optimal solution, and therefore can handle real-world networks of size up to 21,000 nodes. Another pre-processing approach to reduce the computational effort in deriving the optimal sensor placement strategy is to develop methods that deepen insights into the structure and mechanism of distribution systems and subsequently allow for a pre-selection of optional sensor locations. Only a few studies have been done in this context. Deuerlein (2008) developed a generalized decomposition model that simplifies a network into a graph consisting of two main components, called forests and cores, respectively. The model is applied to the risk analysis and sensor placement for WDS security (Deuerlein et al., 2010). Perelman and Ostfeld (2011) developed topological clustering tools for WDS analysis. As clusters result from the flow directions in pipes, the placement of sensor can be proposed.
This study explores sensor placement for contaminant detection in WDS on the basis of insights gained from control theory-oriented complex system analysis. Specifically, this paper introduces a novel method for improving sensor placement based on controllability analysis as outlined by Liu et al. (2011). The key idea is to reduce the parameter set for sensor placement optimization by minimizing the number of possible locations. According to control theory, a dynamical system is controllable if driving a suitable set of nodes by different signals can offer full control over the network. The selected nodes are termed as “driver nodes”. Here, the term full control refers to driving the system from any initial state to any desired final state within finite time (Kalman, 1963, Luenberger, 1979, Slotine and Li, 1991). Thus, every node in the system should receive the corresponding signal from the driver node within finite time. Typically, controllability analysis is related to actuator placement. Nevertheless, the method for actuation can be extended to sensing through an inversion of the inputs and outputs [also refer to observability (Kalman, 1959, Campbell et al., 1991; Trease and Kota, 2006; Liu et al., 2013)]. The new system, driven from such an inversion, is termed as the dual or adjoint system (e.g. ATv = g) of the original one (e.g. Au = f). The equivalence of the two forms is easily proved as vTf = vTAu=(ATv)Tu = gTu (Giles and Pierce, 2000). If in the dual system, ∀ni ∈ N (niis a node, and N = {n1,…, nm}) a path from a certain driver node dj to ni always exist, the status of any node ni can also be delivered to the corresponding driver node(s) dj in the original system.
In the context of WDS analysis, the driver nodes in the dual system of the original WDS are likely to be proper places for sensor placement given the reason described above. Specifically, as in this case matrix A could be an adjacency matrix (Aij = −Aji = aij if node i and j are connected, where aij is the weight of the directed link, i → j; or Aij = Aji = 0 otherwise). The dual system is subsequently a water distribution network with reversed flow direction in every link (AT). The dual system is subsequently a water distribution network with reversed flow direction in every link (AT). Consequently, the input signals at driver nodes could be regarded as time-dependent indicator for contamination events (e.g. the contaminant's concentration). Therefore, the signal (contamination intrusion) will definitely be detected at driver nodes. As the network is fully controlled by driver nodes, it might be possible to identify the contamination source(s) in finite time by tracing back along the directed paths from the driver nodes (where intrusion events are detected) to all linked upstream nodes. Thus, given the simplifying assumptions of the approach as e.g. that any pollutant does not vanish due to reactions (e.g. degradation) during transport in the network (discussed in detail later), any contamination event in the network is detected when all driver nodes of a WDS are monitored. Besides, the method can handle WDSs with arbitrary sizes. This is another advantage of the approach.
Liu et al. (2011) developed an analytical tool to identify the minimum number of driver nodes in arbitrary complex directed networks. Analyzing WDS's by this tool could therefore determine the minimum number of sensors required to ensure detection of any contamination event. Consequently, these driver nodes are identified as the decision variables for further optimization. Moreover, such controllability analysis is extremely efficient as the computational cost is O(N1/2L) at most, where N and L denotes the number of nodes and links respectively. Consequently, the driver nodes for large-scale all-pipe networks can be determined even for different scenarios. In this paper we present controllability analysis as a reliable preprocessing method for sensor placement optimization.
Section snippets
Network controllability
The controllability of complex water distribution systems is explored using the canonical linear, time-invariant state-space equation:where the vector x(t) = (x1(t), …, xN(t))T represents the state of a system of N nodes at time t. The N × N matrix A describes the system's wiring diagram and the interaction strength between the components, for instance the flow rate in pipes in water distribution systems. B is the N × M matrix (M ≤ N) that identifies the driver nodes controlled by
Practical application
For verification of the method, several real-world case studies are investigated in the following. A first case study focuses on the battle of the water sensors network 1 (BWSN1) (Ostfeld et al., 2008) since the results of the method are easily compared with other researchers' solutions. Second, the feasibility of the method toward large-scale networks is tested.
Conclusions
This study applies controllability analysis to sensor layout planning of water distribution systems – with the sensor system aiming at contaminant detection. The method provides a pre-selection of sensor locations for this purpose and thus reduces the problem space of subsequent optimization of the sensor layout. Given the inherent simplifications of the method (most important the assumption of a conservative pollutant), controllability analysis allows to identify the minimum number of driver
Acknowledgements
We are sincerely appreciated to Su Xu and Peng Xu for providing data of the real-world water system, denoted as “Anonymous network”. We also thank Hanchen Xiong and Zhengji Wang for programming help.
References (48)
- et al.
In-pipe water quality monitoring in water supply systems under steady and unsteady state flow conditions: a quantitative assessment
Water Research
(2012) Contamination Warning Systems for Water: an Approach for Providing Actionable Information to Decision-makers
(2005)- et al.
A dynamic thresholds scheme for contaminant event detection in water distribution systems
Water Research
(2013) - et al.
A multi-objective optimization algorithm for sensor placement in water distribution systems
- et al.
PipelineNet: a model for monitoring introduced contaminant sin a distribution system
- et al.
Water quality sensor placement in water networks with budget constraints
- et al.
Sensor placement in municipal water networks with temporal integer programming models
Journal of Water Resources Planning and Management
(2006) - et al.
Scalable water network sensor placement via aggregation
- et al.
User's Manual: TEVA-SPOT Toolkit 2.0
(2008) - et al.
Structural analysis
Duality, observability, and controllability for linear time-varying descriptor systems
Circuits, Systems and Signal Processing
Methodology for locating monitoring stations to detect contamination in potable water distribution systems
Journal of Infrastructure System
Decomposition model of a general water supply network graph
Journal of Hydraulic Engineering
Graph decomposition in risk analysis and sensor placement for water distribution network security
An efficient algorithm for sensor placement in water distribution systems
A heuristic method for waterquality sensor location in a municipal water distribution system: mass-released based approach
An introduction to the adjoint approach to design
Flow, Turbulence and Combustion
Optimization model and algorithms for design of water sensor placement in water distribution systems
The TEVA-SPOT toolkit for drinking water contaminant warning system design
Limited-memory techniques for sensor placement in water distribution networks. learning and intelligent optimization
Review of sensor placement strategies for contamination warning systems in drinking water distribution systems
Journal of Water Resources Planning and Management
Multi-objective optimization for monitoring sensor placement in water distribution systems
Comparison of physical sampling and real-time monitoring strategies for designing a contamination warning system in a drinking water distribution system
Journal of Water Resources Planning and Management
On the general theory of control systems
IRE Transactions on Automatic Control
Cited by (33)
Efficient k-means clustering and greedy selection-based reduction of nodal search space for optimization of sensor placement in the water distribution networks
2022, Water ResearchCitation Excerpt :The above methods oversimplified the SPP by overseeing the effects of temporal demands, reverse flows and contaminant transport velocity, as their applicability was tested only on a small number of contamination events. Diao et al. implemented controllability analysis on BWSN Network1 to condense the decision variable search space by (Diao and Rauch, 2013) choosing nodes that facilitated maximum network observability in a given time frame. But, this prioritized the observability at the expense of swiftness in detections when a set of nodes are considered together for sensor placement.
Multi-criteria method for the realistic placement of water quality sensors on pipes of water distribution systems
2022, Environmental Modelling and SoftwareAssessing the global resilience of water quality sensor placement strategies within water distribution systems
2020, Water ResearchCitation Excerpt :This is because the EA search mechanisms are stochastically based and hence they need to call continuously the water quality simulation model (that is often computationally expensive) to enable the calculations of objective functions (Hart and Murray, 2010). To overcome this issue, continuous efforts have been made to improve the optimization efficiency with the aid of several techniques, including graph theory (Perelman and Ostfeld, 2011), preconditioning methods (Huang et al., 2008; Diao and Rauch, 2013), surrogate models (Bi et al., 2015), data-archive methods (He et al., 2018) and sampling methods (Tinelli et al., 2017). Given the selected objective function and the optimization algorithm as mentioned above, optimal WQSPSs that have the best overall performance in detecting water quality issues can be identified for the WDS.
Optimal and objective placement of sensors in water distribution systems using information theory
2018, Water ResearchCitation Excerpt :Another approach is to use more computationally efficient optimization algorithms that search for a near optimal solution, at the expense of lower accuracy, objectivity and robustness (Berry et al. 2008, 2012; Janke et al., 2017). While most of the literature have focused on developing different optimization techniques to solve for subjectively selected decision variables, Diao and Rauch (2013) argued a more precise and objective method to pre-determine the potential locations of sensors in WDS should be adopted. In an effort to tackle this issue, they proposed an approach inspired by the concept of control theory for complex system analysis (Liu et al., 2011).
Robust sensor placement for pipeline monitoring: Mixed integer and greedy optimization
2018, Advanced Engineering Informatics