Sensor placement for fault location identification in water networks: a minimum test cover approach
Lina Sela, Waseem Abbas, Xenofon Koutsoukos, Saurabh Amin

Citation
Lina Sela, Waseem Abbas, Xenofon Koutsoukos, Saurabh Amin. "Sensor placement for fault location identification in water networks: a minimum test cover approach". Automatica, 72, October 2016.

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.

Electronic downloads

Internal. This publication has been marked by the author for FORCES-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Lina Sela, Waseem Abbas, Xenofon Koutsoukos, Saurabh Amin.
  <a
  href="http://www.cps-forces.org/pubs/131.html"
  >Sensor placement for fault location identification in
  water networks: a minimum test cover approach</a>,
  <i>Automatica</i>, 72, October 2016.

• Plain text

  Lina Sela, Waseem Abbas, Xenofon Koutsoukos, Saurabh Amin.
  "Sensor placement for fault location identification in
  water networks: a minimum test cover approach".
  <i>Automatica</i>, 72, October 2016.

• BibTeX

  @article{SelaAbbasKoutsoukosAmin16_SensorPlacementForFaultLocationIdentificationInWater,
      author = {Lina Sela and Waseem Abbas and Xenofon Koutsoukos
                and Saurabh Amin},
      title = {Sensor placement for fault location identification
                in water networks: a minimum test cover approach},
      journal = {Automatica},
      volume = {72},
      month = {October},
      year = {2016},
      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.},
      URL = {http://cps-forces.org/pubs/131.html}
  }
  

Posted by Saurabh Amin on 15 Apr 2016.
Groups: forces
For additional information, see the Publications FAQ or contact webmaster at cps-forces org.