Approximate Optimal Sensor Placements in Grid Sensor Fields

This paper proposes a simple heuristic to effectively and efficiently place sensors in grid sensor fields under the constraint of complete coverage. The heuristic guarantees a solution of min(1 + alpha, 3)-optimal when an additional constraint of prioritized placement is enforced, where alpha is the maximum ratio between the weights (priorities) of the grid points. When there is no prioritized placement, a solution of 2-optimal is guaranteed. We also show that these bounds are the best possible unless P = NP. Comparisons are performed against some well known sensor placement techniques, where the proposed heuristic outperforms in solution quality and execution time.