Crash-tolerant collision-free data agreegation scheduling for wireless sensor networks
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, 2010Full text not available from this repository.
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|
|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|
Actions (login required)