Incremental Sensor Placement Optimization on Water Network

Abstract. With the development and expansion of cities, the public water distribution systems in cities would be enlarged as a consequence. Therefore, as far as the monitoring of water distribution systems is con-cerned, strategic placement of additional sensors throughout distribution network would exert great impact on the performance of real-time early warning systems (EWSs). On the other hand, constraints of the modifi-cation cost on the original placement strategy should also be taken into consideration. In this paper, we reduce the incremental sensor deploy-ment optimization problem to set cover problem and algorithms with provable performance guarantees because of the submodularity property of the objective function based on greedy heuristic are designed and optimized by local search approaches such as simulated annealing. The detailed experimental results using two benchmark distribution networks demonstrate the effectiveness and efficiency of our algorithms.