An Efficient Approach to Fault Identification in Urban Water Networks Using Multi-Level Sensing

ABSTRACT

The objective of this work is to develop an efficient and practical sensor placement method for the failure detection and localization in water networks. We formulate the problem as the minimum test cover problem (MTC) with the objective of selecting the minimum number of sensors required to uniquely identify and localize pipe failure events. First, we summarize a single-level sensing model and discuss an efficient fast greedy approach for solving the MTC problem. Simulation results on benchmark test networks demonstrate the efficacy of the fast greedy algorithm. Second, we develop a multi-level sensing model that captures additional physical features of the disturbance event, such as the time lapsed between the occurrence of disturbance and its detection by the sensor. Our sensor placement approach using MTC extends to the multi-level sensing model and an improved identification performance is obtained via reduced number of sensors (in comparison to single-level sensing model). In particular, we investigate the bi-level sensing model to illustrate the efficacy of employing multi-level sensors for the identification of failure events. Finally, we suggest extensions of our approach for the deployment of heterogeneous sensors in water networks by exploring the trade-off between cost and performance (measured in terms of the identification score of pipe/link failures).

References

1. Bentley, Water Hammer and Transient Analysis Software. http://www.bentley.com/en-US/Products/HAMMER/. Accessed: 2015-04--14.
2. J. Berry, W. Hart, C. Phillips, J. Uber, and J. Watson. Sensor placement in municipal water networks with temporal integer programming models. Journal of Water Resources Planning and Management, 132(4):218--224, 2006.
3. K. M. De Bontridder, B. V. Halldórsson, M. M. Halldórsson, C. A. Hurkens, J. K. Lenstra, R. Ravi, and L. Stougie. Approximation algorithms for the test cover problem. Mathematical Programming, 98(1--3):477--491, 2003.
4. A. Deshpande, S. E. Sarma, K. Youcef-Toumi, and S. Mekid. Optimal coverage of an infrastructure network using sensors with distance-decaying sensing quality. Automatica, 49(11):3351--3358, 2013.
5. D. Eliades and M. Polycarpou. A fault diagnosis and security framework for water systems. IEEE Transactions on Control Systems Technology, 18(6):1254--1265, Nov 2010.
6. B. V. Halldórsson, M. M. Halldórsson, and R. Ravi. On the approximability of the minimum test collection problem. In Proceedings of the 9th Annual European Symposium on Algorithms, ESA '01, pages 158--169, London, UK, UK, 2001. Springer-Verlag.
7. W. Hart, J. Berry, E. Boman, R. Murray, C. Phillips, L. Riesen, and J. Watson. The TEVA-SPOT Toolkit for Drinking Water Contaminant Warning System Design, chapter 511, pages 1--12.
8. W. Hart and R. Murray. Review of sensor placement strategies for contamination warning systems in drinking water distribution systems. Journal of Water Resources Planning and Management, 136(6), 2010.
9. M. D. Jolly, A. D. Lothes, S. Bryson, and L. Ormsbee. Research database of water distribution system models. Journal of Water Resources Planning and Management, 140(4):410--416, 2014.
10. T. Kim and S. J. Wright. PMU placement for line outage identification via multiclass logistic regression. arXiv:1409.3832v1 {math.OC}.
11. A. Krause, J. Leskovec, C. Guestrin, J. Vanbriesen, and C. Faloutsos. Efficient sensor placement optimization for securing large water distribution networks. Journal of Water Resources Planning and Management, 2008.
12. A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9:235--284, 2008.
13. M. Minoux. Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques, pages 234--243. Springer, 1978.
14. B. M. E. Moret and H. D. Shapiro. On minimizing a set of tests. SIAM Journal on Scientific and Statistical Computing, 6(4):983--1003, 1985.
15. A. Ostfeld, J. G. Uber, E. Salomons, J. W. Berry, W. E. Hart, Phillips, et al. The battle of the water sensor networks: A design challenge for engineers and algorithms. Journal of Water Resources Planning and Management, 134(6):556--568, 2008.
16. R. Puust, Z. Kapelan, D. A. Savic, and T. Koppel. A review of methods for leakage management in pipe networks. Urban Water Journal, 7(1):25--45, 2010.
17. L. Sela Perelman, W. Abbas, X. Koutsoukos, and S. Amin. Sensor placement for fault location identification in water networks: a minimum test cover approach. 2015. http://arxiv.org/abs/1507.07134 {cs.SY}.
18. E. Wylie, V. Streeter, and L. Suo. Fluid transients in systems. Prentice Hall, 1993.
19. T. T. Zan, H. B. Lim, K.-J. Wong, A. J. Whittle, and B.-S. Lee. Event detection and localization in urban water distribution network. IEEE Sensors Journal, 14(12):4134--4142, 2014.
20. J. Zhang, F.-Y. Wang, K. Wang, W.-H. Lin, X. Xu, and C. Chen. Data-driven intelligent transportation systems: A survey. IEEE Transactions on Intelligent Transportation Systems, 12(4):1624--1639, Dec 2011.

Index Terms

• Information systems

  • Information systems applications