Back to search

University of British Columbia

Resilience of wireless sensor networks

Abstract

dc:description

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.

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

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Tseng, Kuan-Chieh Robert. Resilience of wireless sensor networks. master's thesis, University of British Columbia, 2011. http://hdl.handle.net/2429/33713