(374b) Optimal Sensor Placement for Water Distribution Network Security

1 Introduction  

Polluted water has serious implications on all living creatures. In wake of the tragic events of September 11, the scope of risk and security has widened and water utilities are feeling a growing need to detect and minimize the risk of malicious water contamination in distributed water networks. Placement of adequate number of sensors at appropriate places in a water distribution network at design stage for timely detection of contaminants is one option which can be optimized using various costs and risks based objectives. The approach in [1] of minimizing the contamination begotten risk to the human population using sensors appears promising. However, without proper consideration of uncertainty, the analysis can not be robust. For the problem of sensor placement, uncertainty can manifest itself through changing population density/water demands at various junctions or through varying probability of contamination at a node. This work extends the formulation in [1] through extensive consideration of the uncertainties, transforming the problem into a two stage stochastic nonlinear programming problem with recourse. This proposed problem is solved using a new algorithm, L-shaped BONUS, proposed by the authors to solve stochastic nonlinear programming problems.  

2 Methodology  

The proposed stochastic programming formulation is an extension of the deterministic formulation in [1]. The work first proves that uncertainty consideration is important for this problem as it increases the contamination propagation possibilities through multiple flow patterns. This results in the formulation of a two stage stochastic programming problem which is given as:

Here i and j represent the set of nodes in the network, α_ip is the probability of attack at node v_i and d_jp is the population density at node v_j during flow pattern p, conditional on exactly one attack on a node during some flow pattern. C_ipj are the contamination indicators between nodes i and j during pattern p. Cipj = 1 if node v_j is contaminated by an attack at node v_i and 0 otherwise. s_ij are the sensor indicators on branch (i,j) of the network, β_ij is the costs of sensors, and Smax is the maximum number of permitted sensors. S is the cost associated with each person affected by the contamination (e.g. treatment cost). The objective function is the sum of the cumulative population at risk as a result of all the possible contamination attack scenarios under the given conditions and the total cost of sensors.

The risk is defined under a fixed number of flow patterns represented by the binary parameter fijp. fijp = 1 if there is positive flow along (directed) edge e=(v_i,v_j) during flow pattern p and is 0 otherwise. The formulation models uncertainty as varying population density d_jp and attack probability at a node α_ip which, as previously mentioned, increases the number of possible flow patterns. In the proposed formulation, this is accounted for by carefully including all the possible flow patterns in the constraints. The uncertain parameters are discretized through Nsamp samples and EPANET simulation for each sample gives the complete set of possible flow patterns P.

In the first stage problem, s_ij are the (binary) decision variables and E[R(C; s; u)] is the linear approximation to the recourse function, which is exactly calculated only in the second stage. Cipj are the second stage (binary) decision variables. For the second stage problem, the uncertain α_ip and d_jp variables with a known probability distribution (uniform or normal) are sampled; fijp values are obtained from EPANET simulator while the other parameters are known constants. Although the constraints are linear, the problem is nonlinear due to the nonlinear nature of EPANET simulations giving fkjp.

The problem is solved by using the sampling based L-shaped BONUS algorithm which has been recently proposed by the authors to solve the stochastic nonlinear programming problems more efficiently [2]. This algorithm is an integration of the standard sampling based L-shaped method and BONUS (Better Optimization of Nonlinear Uncertain Systems) algorithm [3]. It preserved the decomposition structure of the standard L-shaped method and incorporates reweighting scheme from BONUS to bypass repeated model simulations that are a computational bottleneck in L-shaped method. The algorithm uses Hammersley Sequence Sampling (HSS) technique [4] which is shown to have k dimensional uniformity property.  

3 Results and Conclusions  

The problem of sensor placement is solved for an example network with population density varying by ±25% with normal distribution around a mean. Nodal demands are linearly correlated with the uncertain population density and therefore are uncertain with the same distribution. The attack probability at various nodes is fixed and equal during any pattern. EPANET is used to perform all the hydraulic simulations. Two different types of sensor, high cost and low cost, are analyzed to understand solution tradeoffs. Three different solution formulations are compared: deterministic formulation (Method A) considering the mean demands and no uncertainty; formulation proposed in [1] (Method B) considering uncertain demands affecting only the objective function; and the proposed stochastic formulation (Method C).

The values of cost and percentage population at risk indicate significant differences, as high as 20%, in the solutions obtained by various methods. It is observed that the deterministic solution (A) underestimates the objective function value and the percentage population at risk (by about 10%). Method B and C show no such fixed trend and the relative values change, depending on the type of sensors (high cost or low cost) and the maximum number of allowed sensors. The optimal locations of the sensors also change for various solution methods. The solution indicates a tradeoff between the cost and population at risk in the solutions, so that high cost sensors leave greater population at risk to minimize overall objective. When computational times of the stochastic problem (method C) are compared for the standard L-shaped method and the proposed L-shaped BONUS method, reduction by a factor of 5 is observed for the sample size of 100. It is also observed that the computational time increases exponentially with the sample size for the L-shaped method while it increases linearly for the proposed algorithm. It can therefore be concluded that the proposed problem formulation gives a more realistic insight into the network problem and the proposed algorithm improves the computational efficiency.  

References  

[1] J. Berry, L. Fleischer, W. Hart, C. Phillips, and J. Watson. Sensor placement in municipal water networks. To appear in special issue of Journal of Water Res. Planning and Management, 2005.

[2] Y. Shastri and U. Diwekar. An efficient algorithm for large scale stochastic nonlinear programming problems. Submitted for review to Computers and Chemical Engineering, 2004.

[3] K.H. Sahin and U.M. Diwekar. Better Optimization of Nonlinear Uncertain Systems (BONUS): A new algorithm for stochastic programming using reweighting through kernel denisty estimation. Annals of Operations Research, 132:47?68, 2004.

[4] J.R. Kalagnanam and U. Diwekar. An efficient sampling technique for off-line quality control. Technometrics, 39(3):308?319, 1997.