Point and area sweep coverage in wireless sensor networks

摘要

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.