Jhumka, Arshad (2010) Crash-tolerant collision-free data aggregation scheduling for wireless sensor networks. In: 29th IEEE International Symposium on Reliable Distributed Systems, New Delhi, India, 31 Oct - 03 Nov 2010 . Published in: Symposium on Reliable Distributed Systems. Proceedings pp. 44-53.

Full text not available from this repository.

Abstract

Data aggregation scheduling, or convergecast, is a fundamental pattern of communication in wireless sensor networks (WSNs), where sensor nodes aggregate and relay data to a sink node. For WSN applications that require fast response time, it is imperative that the data reaches the sink as fast as possible. For such timeliness guarantees, TDMA-based scheduling can be used to assign time slots to nodes in which they can transmit messages. However, any slot assignment approach needs to be cognisant of the fact that crash failures can occur (e. g., due to battery exhaustion, defective hardware). In this paper, we study the design of such data aggregation scheduling (convergecast) protocols. We make the following contributions: (i) we identify a necessary condition to solve the convergecast problem, (ii) we introduce two versions of the convergecast problem, namely (a) a strong version, and (b) a weak version, (iii) we show that the strong convergecast problem cannot be solved, (iv) we show that deterministic weak convergecast cannot be solved in presence of crash failures, (v) we show that there is no 1-local algorithm that solves stabilising weak convergecast in presence of crash failures, (vi) we provide a modular d-local algorithm that solves stabilising weak convergecast in presence of crash failures where d is the network radius, and (vii) we show how specific instantiations of parameters can lead to an d-local algorithm that achieves more efficient stabilization. Our contributions are novel: (i) the first contribution (necessary condition) provides the theoretical basis which explains the structure of existing convergecast algorithms, and (ii) the study of convergecast in presence of crash failures has not previously been studied.

Item Type:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science
Journal or Publication Title:	Symposium on Reliable Distributed Systems. Proceedings
Publisher:	IEEE
ISSN:	1060-9857
Book Title:	2010 29th IEEE Symposium on Reliable Distributed Systems
Date:	2010
Page Range:	pp. 44-53
Identification Number:	10.1109/SRDS.2010.14
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	29th IEEE International Symposium on Reliable Distributed Systems
Type of Event:	Other
Location of Event:	New Delhi, India
Date(s) of Event:	31 Oct - 03 Nov 2010
URI:	http://wrap.warwick.ac.uk/id/eprint/41503

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item