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

• We formalise the problem of data aggregation scheduling and prove some impossibility results.
• We develop an efficient modular algorithm that solves stabilising data aggregation scheduling in the presence of crash failures.
• We show, through simulation and an actual deployment, the viability of our approach.

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.