Sensor placement for fault location identification in water networks: A minimum test cover approach

TitleSensor placement for fault location identification in water networks: A minimum test cover approach
Publication TypeJournal Article
Year of Publication2016
AuthorsPerelman, L. Sela, W. Abbas, X. Koutsoukos, and S. Amin
JournalAutomatica
Volume72
Pagination166 - 176
ISSN0005-1098
Keywordswater networks
Abstract

Abstract This paper focuses on the optimal sensor placement problem for the identification of pipe failure locations in large-scale urban water systems. The problem involves selecting the minimum number of sensors such that every pipe failure can be uniquely localized. This problem can be viewed as a minimum test cover (MTC) problem, which is NP-hard. We consider two approaches to obtain approximate solutions to this problem. In the first approach, we transform the \{MTC\} problem to a minimum set cover (MSC) problem and use the greedy algorithm that exploits the submodularity property of the \{MSC\} problem to compute the solution to the \{MTC\} problem. In the second approach, we develop a new augmented greedy algorithm for solving the \{MTC\} problem. This approach does not require the transformation of the \{MTC\} to MSC. Our augmented greedy algorithm provides in a significant computational improvement while guaranteeing the same approximation ratio as the first approach. We propose several metrics to evaluate the performance of the sensor placement designs. Finally, we present detailed computational experiments for a number of real water distribution networks.

URLhttp://www.sciencedirect.com/science/article/pii/S000510981630231X
DOI10.1016/j.automatica.2016.06.005