Elsevier

Water Research

Volume 47, Issue 16, 15 October 2013, Pages 6097-6108
Water Research

Controllability analysis as a pre-selection method for sensor placement in water distribution systems

https://doi.org/10.1016/j.watres.2013.07.026Get rights and content

Highlights

  • Automated sensor layout for online monitoring of water distribution systems is computationally restricted.

  • We apply Controllability analysis as preprocessing method for sensor placement.

  • Significant benefit for subsequent optimization is demonstrated.

  • Case studies reveal that the method is theoretical sound and of practical value.

Abstract

Detection of contamination events in water distribution systems is a crucial task for maintaining water security. Online monitoring is considered as the most cost-effective technology to protect against the impacts of contaminant intrusions. Optimization methods for sensor placement enable automated sensor layout design based on hydraulic and water quality simulation. However, this approach results in an excessive computational burden. In this paper we outline the application of controllability analysis as preprocessing method for sensor placement. Based on case studies we demonstrate that the method decreases the number of decision variables for subsequent optimization dramatically to app. 30 to 40 percent.

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:dxtdt=Axt+Butwhere 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)

  • A. Aisopou et al.

    In-pipe water quality monitoring in water supply systems under steady and unsteady state flow conditions: a quantitative assessment

    Water Research

    (2012)
  • American Water Works Association (AWWA)

    Contamination Warning Systems for Water: an Approach for Providing Actionable Information to Decision-makers

    (2005)
  • J. Arad et al.

    A dynamic thresholds scheme for contaminant event detection in water distribution systems

    Water Research

    (2013)
  • M.M. Aral et al.

    A multi-objective optimization algorithm for sensor placement in water distribution systems

  • R. Bahadur et al.

    PipelineNet: a model for monitoring introduced contaminant sin a distribution system

  • J. Berry et al.

    Water quality sensor placement in water networks with budget constraints

  • J. Berry et al.

    Sensor placement in municipal water networks with temporal integer programming models

    Journal of Water Resources Planning and Management

    (2006)
  • J. Berry et al.

    Scalable water network sensor placement via aggregation

  • J.W. Berry et al.

    User's Manual: TEVA-SPOT Toolkit 2.0

    (2008)
  • M. Blanke et al.

    Structural analysis

  • S.L. Campbell et al.

    Duality, observability, and controllability for linear time-varying descriptor systems

    Circuits, Systems and Signal Processing

    (1991)
  • J.R. Chastain

    Methodology for locating monitoring stations to detect contamination in potable water distribution systems

    Journal of Infrastructure System

    (2006)
  • J.W. Deuerlein

    Decomposition model of a general water supply network graph

    Journal of Hydraulic Engineering

    (2008)
  • J.W. Deuerlein et al.

    Graph decomposition in risk analysis and sensor placement for water distribution network security

  • G. Dorini et al.

    An efficient algorithm for sensor placement in water distribution systems

  • S.R. Ghimire et al.

    A heuristic method for waterquality sensor location in a municipal water distribution system: mass-released based approach

  • M.B. Giles et al.

    An introduction to the adjoint approach to design

    Flow, Turbulence and Combustion

    (2000)
  • J. Guan et al.

    Optimization model and algorithms for design of water sensor placement in water distribution systems

  • W.E. Hart

    The TEVA-SPOT toolkit for drinking water contaminant warning system design

  • W.E. Hart et al.

    Limited-memory techniques for sensor placement in water distribution networks. learning and intelligent optimization

  • W.E. Hart et al.

    Review of sensor placement strategies for contamination warning systems in drinking water distribution systems

    Journal of Water Resources Planning and Management

    (2010)
  • J. Huang et al.

    Multi-objective optimization for monitoring sensor placement in water distribution systems

  • R. Janke et al.

    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

    (2006)
  • R.E. Kalman

    On the general theory of control systems

    IRE Transactions on Automatic Control

    (1959)
  • 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 Research
      Citation 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.

    • Assessing the global resilience of water quality sensor placement strategies within water distribution systems

      2020, Water Research
      Citation 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 Research
      Citation 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).

    View all citing articles on Scopus
    View full text