Abstract
dc:descriptionThe 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science - MSc
- Level thesis:degree_level
- master's
- Discipline thesis:degree_discipline
- Computer Science
- Grantor dc:publisher
- University of British Columbia
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Tseng, Kuan-Chieh Robert
Rights
dc:rights- Statement dc:rights
-
- Attribution-NonCommercial-NoDerivatives 4.0 International
- Language dc:language
- eng
Identifiers
dc:identifier.*- Handle dc:identifier
- http://hdl.handle.net/2429/33713