You are not logged in You are not logged in to this journal. Log In

Journal of Water Resources Planning and Management / Volume 134 / Issue 6 / TECHNICAL PAPERS

LOG IN or SELECT A PURCHASE OPTION:

Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks

J. Water Resour. Plann. Manage. 134, 516 (2008); http://dx.doi.org/10.1061/(ASCE)0733-9496(2008)134:6(516) (11 pages)

Andreas Krause1, Jure Leskovec2, Carlos Guestrin3, Jeanne VanBriesen, M.ASCE4, and Christos Faloutsos5

1Graduate Research Assistant, Computer Science Dept. Carnegie Mellon Univ., Pittsburgh, PA 15213. E-mail: krausea@cs.cmu.edu
2Graduate Research Assistant, Machine Learning Dept., Carnegie Mellon Univ., Pittsburgh, PA, 15213. E-mail: jure@cs.cmu.edu
3Assistant Professor, Machine Learning Dept. and Computer Science Dept., Carnegie Mellon Univ., Pittsburgh, PA, 15213. E-mail: guestrin@cs.cmu.edu
4Professor, Dept. of Civil & Environmental Engineering and Dept. of Biomedical Engineering, Carnegie Mellon Univ., Pittsburgh, PA 15213. E-mail: jeanne@cmu.edu
5Professor, Computer Science Dept., Carnegie Mellon Univ., Pittsburgh, PA 15213. E-mail: christos@cs.cmu.edu

View MapView Map

(Submitted 20 February 2007; accepted 22 February 2008)

The problem of deploying sensors in a large water distribution network is considered, in order to detect the malicious introduction of contaminants. It is shown that a large class of realistic objective functions—such as reduction of detection time and the population protected from consuming contaminated water—exhibits an important diminishing returns effect called submodularity. The submodularity of these objectives is exploited in order to design efficient placement algorithms with provable performance guarantees. The algorithms presented in this paper do not rely on mixed integer programming, and scale well to networks of arbitrary size. The problem instances considered in the approach presented in this paper are orders of magnitude (a factor of 72) larger than the largest problems solved in the literature. It is shown how the method presented here can be extended to multicriteria optimization, selecting placements robust to sensor failures and optimizing minimax criteria. Extensive empirical evidence on the effectiveness of the method presented in this paper on two benchmark distribution networks, and an actual drinking water distribution system of greater than 21,000 nodes, is presented.

© 2008 ASCE

Acknowledgments

The writers would like to thank Stratos Papadomanolakis, Shannon Isovitsch, Jianhua Xu, Mitch Small, Paul Fischbeck, Jared Cohen, and the anonymous referees for valuable discussions and feedback. This work was partially supported by NSF Grant Numbers CNS-0509383, CNS-0625518, BES-0329549, IIS-0534205 and by the Pennsylvania Infrastructure Technology Alliance (PITA), with additional funding from Intel and NTT. The third writer was partly supported by an Alfred P. Sloan Fellowship and an IBM Faculty Fellowship. The first and second writer were partly supported by a Microsoft Research Graduate Fellowship. Most of the experiments were conducted on a HP server sponsored by Hewlett-Packard.

Article Outline

  1. Introduction
    1. Related Work
  2. Sensor Placement Objectives
    1. Example
    2. Properties of the Penalty Reduction
  3. Multicriteria Optimization
  4. Algorithms for Optimization
    1. Greedy Algorithm
    2. Location-Specific Placement Costs
    3. Online Bounds
    4. Mixed Integer Programming
    5. Improving Solutions through Search
    6. Note on Minimizing the Expected Penalty
  5. Extensions
    1. Adversarial Objective Functions
    2. Robustness of Sensor Placements
  6. System Implementation
    1. Fast Computation of the Score Function
    2. Fast Implementation of the Greedy Algorithm
  7. Results
    1. Networks Analyzed
    2. Impact Analysis
    3. Single Objective Optimization
      1. Comparison with Random Placements and Heuristics
      2. Online and Offline Bounds
      3. Mixed Integer Programming and Local Search
    4. Multicriteria Optimization and Results from BWSN
    5. Adversarial Objectives
    6. Real 21,000 Node Network
  8. Conclusions

KEYWORDS

RELATED DATABASES

To view database links for this article, you need to log in.

ARTICLE DATA

Digital Object Identifier
http://dx.doi.org/10.1061/(ASCE)0733-9496(2008)134:6(516)

PUBLICATION DATA

ISSN

0733-9496 (print)  
1943-5452 (online)

Publisher

ASCE

For access to fully linked references, you need to log in.

For access to citing articles, you need to log in.


Figures (5) Tables (1)

Access to article objects (figures, tables, multimedia) requires a subscription; log in to view available files.
(Access to supplementary files, where available, is free for this journal.)

Access to article objects (figures, tables, multimedia) requires a subscription; log in to view available files.
(Access to supplementary files, where available, is free for this journal.)


Close

Your Recent History Recent History Help

Recently Viewed

  1. Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks
  2. Practical Solution Concepts for Planning and Designing Roadways
  3. Single-Stage Integer Programming Model for Long-Term Transit Fleet Resource Allocation
  4. Estimating Highway Capacity Considering Two-Regime Models
  5. Analytical Procedures for Estimating Capacity of Freeway Weaving, Merge, and Diverge Sections
close