Alternative Approaches for Solving the Sensor Placement Prob- lem in Large Networks

摘要

Positioning sensors in a water supply network is a NP-hard task. We propose three algorithms - one based on integer linear programming (ILP) and the other two based on the Greedy paradigm. We apply these algorithms to real case networks and compare the results of these algorithms with the results of an algorithm based on NSGA II, a genetic algorithm. We come to the conclusion that our algorithms outperform NSGA II in every single case. The algorithm based on linear integer programming may be applied as a competitor to the algorithm implemented in TEVA -SPOT (Berry, 2009), while the first Greedy algorithm may replace the ILP algorithm in large networks due to its faster running time. The second Greedy algorithm approaches the question on finding those nodes which are the most sensitive to variations in pressure and are thereby ideal places to monitor the hydraulic state of a water distribution network.