No Access

DYNAMIC MAINTENANCE OF SUPPORT COVERAGE IN SENSOR NETWORKS

DINESH DASH

Department of Computer Science & Engineering, Indian Institute of Technology Kharagpur, India

Search for more papers by this author

AROBINDA GUPTA

Department of Computer Science & Engineering, Indian Institute of Technology Kharagpur, India

Search for more papers by this author

, and

ARIJIT BISHNU

Advanced Computing & Microelectronics Unit, Indian Statistical Institute, Kolkata, India

Search for more papers by this author

https://doi.org/10.1142/S0129626410000120Cited by:1 (Source: Crossref)

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.

Keywords:

References

M. T. Thai, F. Wang and D. Du, 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
S. Megerianet al., IEEE Trans. on Mobile Computing 4(1), (2005), DOI: 10.1109/TMC.2005.15. Google Scholar
C. Huang and Y. Tseng, Mobile Network and Applications 10(4), (2005), DOI: 10.1109/TMC.2005.15. Google Scholar
G. Xinget al., 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 et al. , 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
G. Wanget al., IEEE Trans. on Mobile Computing 6(5), (2007). Google Scholar
S. Chellappan et al. , 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
X. Li, N. Santoro and I. Stojmenovic, IEEE Trans. on Computers 58(9), (2009). Google Scholar
S. Chellappanet al., IEEE Trans. on Mobile Computing 6(10), (2007), DOI: 10.1109/TMC.2007.1032. Google Scholar
C. Shen et al. , 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