The Library
Crash-tolerant collision-free data aggregation scheduling for wireless sensor networks
Tools
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. doi:10.1109/SRDS.2010.14 ISSN 1060-9857.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1109/SRDS.2010.14
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 T Technology > TK Electrical engineering. Electronics Nuclear engineering |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Wireless sensor networks, Computer scheduling, Fault-tolerant computing | ||||
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 | ||||
Official Date: | 2010 | ||||
Dates: |
|
||||
Page Range: | pp. 44-53 | ||||
DOI: | 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 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |