DYNAMIC MAINTENANCE OF SUPPORT COVERAGE IN SENSOR NETWORKS
Abstract
Ensuring different types of coverage is an important problem in many wireless sensor applications. In this paper, we address the problem of maintaining support coverage in the presence of sensor failures. Given a placement of n sensors in an area A, and any two points i and f in A, the support value of any path between i and f is the maximum distance of any point on the path from its closest sensor. The path with the minimum support value is called the maximal support path. The support value of a path may increase if a sensor fails. Given a maximal support path with a support value ψ, we first present two centralized approximation algorithms that, on failure of a single sensor, compute a new path with a support value close to ψ by moving exactly one nearby sensor. The first algorithm assumes that the sensors are allowed to move in any direction, and the second one assumes that the sensors are constrained to move in any of the four directions east, west, north, and south. Both the support value for the new path computed and the movement necessary are shown to be within a constant-factor of the initial support value. We then show that even in case of multiple sensor failures, a new path with a bounded support value can be computed. Detailed simulation results are provided to show that the algorithms result in significant improvement in many cases in practice, and the improvements obtained are significantly better than the worst case bounds given by the analysis. We also discuss distributed implementations of the algorithms.
References
- International Journal of Sensor Network 3(3), (2008). Google Scholar
-
S. Kumar , T. H. Lai and A. Arora , Barrier Coverage with Wireless Sensors , ACM MOBICOM ( 2005 ) . Google Scholar - IEEE Trans. on Mobile Computing 4(1), (2005), DOI: 10.1109/TMC.2005.15. Google Scholar
- Mobile Network and Applications 10(4), (2005), DOI: 10.1109/TMC.2005.15. Google Scholar
- ACM Trans. on Sensor Networks 1(1), (2005). Google Scholar
- IEEE Trans. on Computers 52(6), (2003). Google Scholar
-
M. Zhang , X. Du and K. Nygard , Improving Coverage Performance in Sensor Networks by Using Mobile Sensors , IEEE MILCOM . Google Scholar -
G. Wang , Sensor Relocation in Mobile Sensor Networks , IEEE INFOCOM . Google Scholar -
A. Sekhar , B. S. Manoj and C. Siva Ram Murthy , Dynamic Coverage Maintenance Algorithms for Sensor Networks with Limited Mobility , IEEE PERCOM ( 2005 ) . Google Scholar - IEEE Trans. on Mobile Computing 6(5), (2007). Google Scholar
-
S. Chellappan , Sensor Networks Deployment Using Flipbased Sensors , IEEE MASS . Google Scholar - I. Stojmenovic, P. E. Villaneuva Peña; A Scalable Quorum Based Location Update Scheme for Routing in Ad Hoc Wireless Networks; SITE, University of Ottawa,Technical Report TR-99-09, September, 1999 . Google Scholar
- IEEE Trans. on Computers 58(9), (2009). Google Scholar
- IEEE Trans. on Mobile Computing 6(10), (2007), DOI: 10.1109/TMC.2007.1032. Google Scholar
-
C. Shen , Barrier Coverage with Mobile Sensors , IEEE ISPAN . Google Scholar -
D. P. Mehta , M. A. Lopez and L. Lin , Optimal Coverage Paths in Ad-hoc Sensor Networks , IEEE ICC . Google Scholar


