Approximation algorithms for sweep coverage in wireless sensor networks

• Proposed point sweep coverage algorithm with the best possible approximation factor 2.
• Proposed a distributed 2-approximation algorithm for the same problem.
• Introduced area sweep coverage problem and proved it is NP-Complete.
• 22-approximation algorithm is proposed for a square and then improved the factor for a rectangle.

Periodic monitoring is sufficient for sweep coverage   with a small number of mobile sensor nodes, whereas a continuous monitoring with static sensor nodes is required for the coverage problem in wireless sensor networks. Finding the minimum number of mobile sensor nodes with a uniform speed to guarantee sweep coverage is NP-hard and it cannot be approximated within a factor of 2 (Li et al., 2011). In this paper we have proposed a 2-approximation algorithm for solving the sweep coverage for a given set of points of interest (PoIs). The best known approximation factor is 3 for this problem (Li et al., 2011). Modification of the algorithm is also proposed for extending lifetime of the mobile sensors, sweep coverage in the presence of obstacles and failure of mobile sensors. When all PoIs are static sensor nodes, we have proposed a distributed approximation algorithm with approximation ratio 2, where the static sensor nodes compute the number of mobile sensor nodes and their positions. We have introduced sweep coverage for a given area of interest (AoI) and proved that the problem is NP-complete. A 22-approximation algorithm is designed in order to solve the problem for a square region. An improvement over the approximation factor is designed for any rectangular region. Based on our simulation study we have shown that less number mobile sensor nodes are required for our point sweep coverage algorithm compared to the algorithm proposed in Du et al. (2010).