Select Lab Publications


Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks (2008)

By: Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos

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

Download Information
Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos (2008). "Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks." Journal of Water Resources Planning and Management, 134(6), 516-526. (Draft; full version available here). Winner of the Best Research Paper Award. pdf            
BibTeX citation

@article{krause-jwrpm08,
AUTHOR = {Andreas Krause and Jure Leskovec and Carlos Guestrin and Jeanne VanBriesen and Christos Faloutsos},
TITLE = {Efficient Sensor Placement Optimization for Securing Large Water Distribution Networks},
JOURNAL = {Journal of Water Resources Planning and Management},
YEAR = {2008},
volume = {134},
number = {6},
pages = {516-526},
month = {November},
wwwaward = {Winner of the Best Research Paper Award},
note = {(Draft; full version available here)},
source = {http://cedb.asce.org/cgi/WWWdisplay.cgi?0810312},
wwwfilebase = {jwrpm2008-krause-leskovec-guestrin-vanbriesen-faloutsos},
wwwtopic = {Sensing}
}



full list