Planning the deployment of fault-tolerant wireless sensor networks
Loading...
Files
Full Text E-thesis
Date
2013-01
Authors
Sitanayah, Lanny
Journal Title
Journal ISSN
Volume Title
Publisher
University College Cork
Published Version
Abstract
Since Wireless Sensor Networks (WSNs) are subject to failures, fault-tolerance becomes an
important requirement for many WSN applications. Fault-tolerance can be enabled in
different areas of WSN design and operation, including the Medium Access Control (MAC)
layer and the initial topology design. To be robust to failures, a MAC protocol must be able
to adapt to traffic fluctuations and topology dynamics. We design ER-MAC that can switch
from energy-efficient operation in normal monitoring to reliable and fast delivery for
emergency monitoring, and vice versa. It also can prioritise high priority packets and
guarantee fair packet deliveries from all sensor nodes.
Topology design supports fault-tolerance by ensuring that there are alternative acceptable
routes to data sinks when failures occur. We provide solutions for four topology planning
problems: Additional Relay Placement (ARP), Additional Backup Placement (ABP),
Multiple Sink Placement (MSP), and Multiple Sink and Relay Placement (MSRP). Our
solutions use a local search technique based on Greedy Randomized Adaptive Search
Procedures (GRASP). GRASP-ARP deploys relays for (k,l)-sink-connectivity, where each
sensor node must have k vertex-disjoint paths of length ≤ l. To count how many disjoint
paths a node has, we propose Counting-Paths. GRASP-ABP deploys fewer relays than
GRASP-ARP by focusing only on the most important nodes – those whose failure has the
worst effect. To identify such nodes, we define Length-constrained Connectivity and
Rerouting Centrality (l-CRC). Greedy-MSP and GRASP-MSP place minimal cost sinks to
ensure that each sensor node in the network is double-covered, i.e. has two length-bounded
paths to two sinks. Greedy-MSRP and GRASP-MSRP deploy sinks and relays with minimal
cost to make the network double-covered and non-critical, i.e. all sensor nodes must have
length-bounded alternative paths to sinks when an arbitrary sensor node fails. We then
evaluate the fault-tolerance of each topology in data gathering simulations using ER-MAC.
Description
Keywords
MAC protocol , Network deployment planning , Node-disjoint paths , Centrality
Citation
Sitanayah, L. 2013. Planning the deployment of fault-tolerant wireless sensor networks. PhD Thesis, University College Cork.