World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

DYNAMIC MAINTENANCE OF SUPPORT COVERAGE IN SENSOR NETWORKS

    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

    • 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