Resilience of wireless sensor networks
Kuan-Chieh Robert Tseng · cIRcle (University of British Columbia) · 2011
The coverage of a wireless sensor network is a measure of the quality of service. One type of coverage is k-barrier coverage. Given a starting region S and an ending region T , we say that a sensor network has k-barrier coverage with respect to S and T if any S−T path in the surveillance domain must intersect the coverage regions of at least k sensors. In this thesis, we focus on determining the resilience of a wireless sensor network. The resilience is defined to be the minimum number of sensors that need to be removed in order to ensure the existence of a S−T path that does not cross any sensor coverage region. A sensor network with resilience k constitutes a k-barrier coverage. We demonstrate that determining resilience of a wireless sensor network with 2D surveillance domain is NP-hard for the case when the sensor coverage regions are unit line segments. Furthermore, it is possible to extend the reduction to show that the problem remains NP-hard for other types of sensor coverage regions. In general, if the shape of the coverage region is non-symmetric, then determining resilience is NP-hard. We also investigate the problem of determining resilience of a wireless sensor network with 3D surveillance domain. In this case, we show that if the coverage regions of the sensors are unit spheres, then the problem is NP-hard.