Target-oriented conflict graph-based approach for the coverage problem in directional sensor networks

Abstract

Maximizing target coverage with a minimum number of sensors is an elementary problem in the area of wireless sensor networks with many applications in monitoring, tracking, se- curity, and surveillance systems. The recent increase in the use of directional sensors adds a new dimension to the problem. As the problem is understood to be NP-hard, most of the previous works attempt greedy heuristics for achieving a near-optimal solution. Unlike previous research works, we take a graph theoretic target-oriented approach to the problem and provide a novel solution based on a polynomial-time graph algorithm. The usage of graph models minimizes the run time complexity while simultaneously improving the solu- tion’s optimality. In over-provisioned Visual Sensor Networks where there exists sufficient number of sensors to cover all the targets, the suggested approach exhibits promising resul