.png){kind=icon}
.png){kind=icon}
Return
Approximation algorithms for sweep coverage in wireless sensor networks
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2014.02.009.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 (Pots). 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 Pols 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 2 root 2-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). (C) 2014 Elsevier Inc. All rights reserved.
Keywords:
Sweep coverage
Approximation algorithm
Mobile sensor
MST
Euler tour
TSP
Wireless networks
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K