Strong barrier coverage detection and mending algorithm for directional sensor networks

In this paper, we investigate strong barrier coverage using directional sensors with arbitrarily tunable orientations to provide good coverage. Firstly, we introduce the concept of virtual node to divide the original continuous solution space into finite set of discrete spaces. We then construct a directional barrier graph to model this barrier coverage question such that we can quickly answer whether there are directional sensors' orientations that can provide strong barrier coverage over a given belt region. If such orientations exist, we develop a solution to find strong barrier path(s) that will minimize the number of active directional sensors. Otherwise, we design an efficient algorithm based on directional barrier graph to find barrier gaps and mend these gaps with the minimum number of extra directional sensors. Finally, we evaluate the performance of our solution through extensive simulations.