Sensor placement for fault location identification in water networks: A minimum test cover approach
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...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Elsevier
2018
|
| Online Access: | http://hdl.handle.net/1721.1/118402 https://orcid.org/0000-0001-9517-4369 https://orcid.org/0000-0003-1554-015X |
| _version_ | 1811087189722791936 |
|---|---|
| author | Abbas, Waseem Koutsoukos, Xenofon Sela, Polina Amin, Saurabh |
| author2 | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering |
| author_facet | Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Abbas, Waseem Koutsoukos, Xenofon Sela, Polina Amin, Saurabh |
| author_sort | Abbas, Waseem |
| collection | MIT |
| description | 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. Keywords: Fault identification; Minimum test cover; Water networks |
| first_indexed | 2024-09-23T13:41:25Z |
| format | Article |
| id | mit-1721.1/118402 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:41:25Z |
| publishDate | 2018 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | mit-1721.1/1184022022-09-28T15:33:28Z Sensor placement for fault location identification in water networks: A minimum test cover approach Abbas, Waseem Koutsoukos, Xenofon Sela, Polina Amin, Saurabh Massachusetts Institute of Technology. Department of Civil and Environmental Engineering Sela, Polina Amin, Saurabh 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. Keywords: Fault identification; Minimum test cover; Water networks 2018-10-09T19:00:26Z 2018-10-09T19:00:26Z 2016-07 2016-03 Article http://purl.org/eprint/type/JournalArticle 0005-1098 http://hdl.handle.net/1721.1/118402 Sela Perelman et al. “Sensor Placement for Fault Location Identification in Water Networks: A Minimum Test Cover Approach.” Automatica 72 (October 2016): 166–176 © 2016 Elsevier Ltd https://orcid.org/0000-0001-9517-4369 https://orcid.org/0000-0003-1554-015X en_US http://dx.doi.org/10.1016/j.automatica.2016.06.005 Automatica Creative Commons Attribution-NonCommercial-NoDerivs License http://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf Elsevier Prof. Amin |
| spellingShingle | Abbas, Waseem Koutsoukos, Xenofon Sela, Polina Amin, Saurabh Sensor placement for fault location identification in water networks: A minimum test cover approach |
| title | Sensor placement for fault location identification in water networks: A minimum test cover approach |
| title_full | Sensor placement for fault location identification in water networks: A minimum test cover approach |
| title_fullStr | Sensor placement for fault location identification in water networks: A minimum test cover approach |
| title_full_unstemmed | Sensor placement for fault location identification in water networks: A minimum test cover approach |
| title_short | Sensor placement for fault location identification in water networks: A minimum test cover approach |
| title_sort | sensor placement for fault location identification in water networks a minimum test cover approach |
| url | http://hdl.handle.net/1721.1/118402 https://orcid.org/0000-0001-9517-4369 https://orcid.org/0000-0003-1554-015X |
| work_keys_str_mv | AT abbaswaseem sensorplacementforfaultlocationidentificationinwaternetworksaminimumtestcoverapproach AT koutsoukosxenofon sensorplacementforfaultlocationidentificationinwaternetworksaminimumtestcoverapproach AT selapolina sensorplacementforfaultlocationidentificationinwaternetworksaminimumtestcoverapproach AT aminsaurabh sensorplacementforfaultlocationidentificationinwaternetworksaminimumtestcoverapproach |