Jhumka, Arshad (2010) Crash-tolerant collision-free data agreegation scheduling for wireless sensor networks. In: 29th IEEE International Symposium on Reliable Distriduted Systems(SRDS10), New Delhi, India, October 31st, 2010

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 trong 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
Date:	October 2010
Status:	Peer Reviewed
Publication Status:	Published
Conference Paper Type:	Paper
Title of Event:	29th IEEE International Symposium on Reliable Distriduted Systems(SRDS10)
Type of Event:	Workshop
Location of Event:	New Delhi, India
Date(s) of Event:	October 31st, 2010
Related URLs:	Other Repository
URI:	http://wrap.warwick.ac.uk/id/eprint/47441

Request changes to a record

Actions (login required)

View Item