Robust Sensor Placement for Detecting Adversarial Contaminations in Water Distribution Systems

Drinking water distribution systems (WDS) are complex and dynamic systems. The intentional introduction of a contaminant could theoretically be detected by a network of sensors placed at nodes in the system. Optimizing the placement of these hypothetical sensors for metropolitan area size WDS is an important research challenge. Recently, the Battle of the Water Sensor Networks led to the development of several promising techniques for deploying sensors in large, complex networks. However, this challenge focused on designing sensor networks that detect random, accidental contaminations well. In order to guard WDSs against malicious attacks, sensor network detection performance has to be optimized with respect to the worst possible contamination. We recently developed a new algorithm, Saturate, that can efficiently solve large robust sensor placement problems. The obtained solutions are provably close to optimal. Our algorithm can handle imprecise sensors that can fail. Our method can also be used to obtain placements that simultaneously perform well both for malicious (i.e., worst-case) contaminations, as well as accidental (i.e., average-case) contaminations. We report results from applying our method to a large hypothetical distribution system with more than 12,000 nodes.