Robust Placement of Water Quality Sensors in Water Distribution Networks

Water Distribution Networks (WDNs) are used to supply drinking water to billions of people around the world. An upcoming threat to these networks are accidental and deliberate contaminations which can lead to poisoned water, many fatalities and large economic consequences. In order to protect against these intrusions or attacks, an efficient sensor network with a limited number of sensors should be placed in a WDN. It is assumed that attacks can only happen at certain vulnerable nodes in the network. In this thesis, we focus on improving the robustness of these sensor placements by introducing multiple greedy-based algorithms in which the imperfection of sensors, dynamic demand and multiple objectives can be taken into account. For this, the sensor placement formulation is converted into one or multiple weighted bipartite graph with changing weights. The algorithms were tested using several benchmark instances. It was shown that our algorithms are able to find sensor placements in large networks in reasonable time and that its solutions are provably close to optimal. Furthermore, relaxing the previously used assumption that sensors work perfectly results in different sensor placements than were found before. To show that this assumption is incorrect, experiments have been performed on the real-life WaDi testbed. It was concluded that sensor readings can be unreliable and unstable such that sensor imperfection should be taken into account when deciding on the sensor placement.