Point and area sweep coverage in wireless sensor networks
Barun Gorain, Partha Sarathi Mandal · Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks · 2013
Sweep coverage term is recently introduced for coverage in wireless sensor networks. The criteria for sweep coverage is different from the traditional coverage problem where a continuous monitoring with sensor nodes is required. But in sweep coverage, periodic monitoring is sufficient with a small number of mobile sensor nodes. Finding minimum number of mobile sensor nodes with a constant velocity to guarantee sweep coverage is NP-hard and it cannot be approximated within a factor of 2 [11]. In this paper we have proposed a 2-approximation algorithm for solving the sweep coverage for a given set of points of interest (PoI). The best known approximation factor is 3 for this problem [11]. When all PoI are static sensor nodes, we have proposed a distributed approximation algorithm with approximation ratio 2, where the sensor nodes compute the number of mobile 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 2√2-approximation algorithm is proposed in order to solve the problem for a square region. A generalized version of the area sweep coverage problem for an arbitrary bounded region is also investigated in this paper.