Open Collections

Resilience of wireless sensor networks

University of British Columbia

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.

Text

2011-04-18

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/33713

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/