7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks

Research Article

Generic Coverage Verification without Location Information Using Dimension Reduction

  • @INPROCEEDINGS{10.1109/WIOPT.2009.5291620,
        author={Gaurav Kasbekar and Yigal Bejerano and Saswati Sarkar},
        title={Generic Coverage Verification without Location Information Using Dimension Reduction},
        proceedings={7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks},
        publisher={IEEE},
        proceedings_a={WIOPT},
        year={2009},
        month={10},
        keywords={wireless networks; sensor networks; coverage; distributed algorithms; dimension reduction},
        doi={10.1109/WIOPT.2009.5291620}
    }
    
  • Gaurav Kasbekar
    Yigal Bejerano
    Saswati Sarkar
    Year: 2009
    Generic Coverage Verification without Location Information Using Dimension Reduction
    WIOPT
    IEEE
    DOI: 10.1109/WIOPT.2009.5291620
Gaurav Kasbekar1,*, Yigal Bejerano2,*, Saswati Sarkar1,*
  • 1: Department of Electrical and Systems Engineering at University of Pennsylvania, Philadelphia, PA, U.S.A.
  • 2: Bell-Labs, Alcatel- Lucent, Murray Hill, N.J., U.S.A
*Contact email: kgaurav@seas.upenn.edu, bej@research.bell-labs.com, swati@seas.upenn.edu

Abstract

Wireless Sensor Networks (WSNs) have recently emerged as a key sensing technology with diverse civilian and military applications. In these networks, a large number of small sensors or nodes perform distributed sensing of a target field. Each node is capable of sensing events of interest within its sensing range and communicating with neighboring nodes. The target field is said to be k-covered if every point in it is within the sensing range of at least k sensors, where k is any positive integer. We present a comprehensive framework for verifying k-coverage of a d-dimensional target field for arbitrary positive integers k, d. Our framework uses a divide and conquer approach based on the technique of dimension reduction, in which the k-coverage verification problem in d-dimensions is reduced to a number of coverage verification problems in (d-1) dimensions, which are then recursively solved. Our framework leads to a distributed polynomial-time coverage verification algorithm that does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in WSNs. Each node can execute the algorithm using only the distances between adjacent nodes within its transmission range and their sensing radii. We analytically prove that the scheme detects a coverage hole if and only if the target field has a coverage hole.