Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks

Arshad Jhumka, Matthew Bradbury, Sain Saginbekov

Research output: Contribution to journalArticle

10 Citations (Scopus)

Abstract

This paper investigates the design of fault-tolerant TDMA-based data aggregation scheduling (DAS) protocols for wireless sensor networks (WSNs). DAS is a fundamental pattern of communication in wireless sensor networks where sensor nodes aggregate and relay data to a sink node. However, any such DAS protocol needs to be cognisant of the fact that crash failures can occur. We make the following contributions: (i) we identify a necessary condition to solve the DAS problem, (ii) we introduce a strong and weak version of the DAS problem, (iii) we show several impossibility results due to the crash failures, (iv) we develop a modular local algorithm that solves stabilising weak DAS and (v) we show, through simulations and an actual deployment on a small testbed, how specific instantiations of parameters can lead to the algorithm achieving very efficient stabilisation.

Original languageEnglish
Pages (from-to)1789-1801
Number of pages13
JournalJournal of Parallel and Distributed Computing
Volume74
Issue number1
DOIs
Publication statusPublished - 2014
Externally publishedYes

Fingerprint

Data Aggregation
Fault-tolerant
Wireless Sensor Networks
Wireless sensor networks
Agglomeration
Collision
Scheduling
Crash
Scheduling Problem
Network protocols
Local Algorithms
Time division multiple access
Vertex of a graph
Testbeds
Sensor nodes
Testbed
Relay
Stabilization
Necessary Conditions
Sensor

Keywords

  • Collision freedom
  • Correctness
  • Crashes
  • Data aggregation scheduling
  • Fault tolerance
  • Impossibility
  • Wireless sensor networks

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Hardware and Architecture
  • Software
  • Theoretical Computer Science

Cite this

Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks. / Jhumka, Arshad; Bradbury, Matthew; Saginbekov, Sain.

In: Journal of Parallel and Distributed Computing, Vol. 74, No. 1, 2014, p. 1789-1801.

Research output: Contribution to journalArticle

@article{7ea44668207649b9bd107f7b29717ab8,
title = "Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks",
abstract = "This paper investigates the design of fault-tolerant TDMA-based data aggregation scheduling (DAS) protocols for wireless sensor networks (WSNs). DAS is a fundamental pattern of communication in wireless sensor networks where sensor nodes aggregate and relay data to a sink node. However, any such DAS protocol needs to be cognisant of the fact that crash failures can occur. We make the following contributions: (i) we identify a necessary condition to solve the DAS problem, (ii) we introduce a strong and weak version of the DAS problem, (iii) we show several impossibility results due to the crash failures, (iv) we develop a modular local algorithm that solves stabilising weak DAS and (v) we show, through simulations and an actual deployment on a small testbed, how specific instantiations of parameters can lead to the algorithm achieving very efficient stabilisation.",
keywords = "Collision freedom, Correctness, Crashes, Data aggregation scheduling, Fault tolerance, Impossibility, Wireless sensor networks",
author = "Arshad Jhumka and Matthew Bradbury and Sain Saginbekov",
year = "2014",
doi = "10.1016/j.jpdc.2013.09.011",
language = "English",
volume = "74",
pages = "1789--1801",
journal = "Journal of Parallel and Distributed Computing",
issn = "0743-7315",
publisher = "Academic Press Inc.",
number = "1",

}

TY - JOUR

T1 - Efficient fault-tolerant collision-free data aggregation scheduling for wireless sensor networks

AU - Jhumka, Arshad

AU - Bradbury, Matthew

AU - Saginbekov, Sain

PY - 2014

Y1 - 2014

N2 - This paper investigates the design of fault-tolerant TDMA-based data aggregation scheduling (DAS) protocols for wireless sensor networks (WSNs). DAS is a fundamental pattern of communication in wireless sensor networks where sensor nodes aggregate and relay data to a sink node. However, any such DAS protocol needs to be cognisant of the fact that crash failures can occur. We make the following contributions: (i) we identify a necessary condition to solve the DAS problem, (ii) we introduce a strong and weak version of the DAS problem, (iii) we show several impossibility results due to the crash failures, (iv) we develop a modular local algorithm that solves stabilising weak DAS and (v) we show, through simulations and an actual deployment on a small testbed, how specific instantiations of parameters can lead to the algorithm achieving very efficient stabilisation.

AB - This paper investigates the design of fault-tolerant TDMA-based data aggregation scheduling (DAS) protocols for wireless sensor networks (WSNs). DAS is a fundamental pattern of communication in wireless sensor networks where sensor nodes aggregate and relay data to a sink node. However, any such DAS protocol needs to be cognisant of the fact that crash failures can occur. We make the following contributions: (i) we identify a necessary condition to solve the DAS problem, (ii) we introduce a strong and weak version of the DAS problem, (iii) we show several impossibility results due to the crash failures, (iv) we develop a modular local algorithm that solves stabilising weak DAS and (v) we show, through simulations and an actual deployment on a small testbed, how specific instantiations of parameters can lead to the algorithm achieving very efficient stabilisation.

KW - Collision freedom

KW - Correctness

KW - Crashes

KW - Data aggregation scheduling

KW - Fault tolerance

KW - Impossibility

KW - Wireless sensor networks

UR - http://www.scopus.com/inward/record.url?scp=84887028975&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887028975&partnerID=8YFLogxK

U2 - 10.1016/j.jpdc.2013.09.011

DO - 10.1016/j.jpdc.2013.09.011

M3 - Article

VL - 74

SP - 1789

EP - 1801

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

SN - 0743-7315

IS - 1

ER -