Effective coverage in sensor networks: Binary integer programming formulations and heuristics

Coverage is a fundamental task in sensor networks. We present two binary integer programming models for the effective sensor placement on a grid-structured sensor field when there are more than one type of available sensors with varying sensing quality and price. The first model assumes perfect sensor detection. The second one is more realistic and gives an optimal placement strategy for probabilistic sensing. Both models suffer from the intractability of the binary integer programming formulations. We therefore suggest greedy and Lagrangean heuristics, which are both accurate and efficient. Computational results are also provided.