On the scalability and message count of trickle-based broadcasting schemes

DOI10.1007/S11134-015-9438-XzbMATHDBLPOpenAlexWikidataMaRDI QIDQ747717FDO

Authors Thomas M. M. Meyfroyt, Onno Boxma, Dee Denteneer, Sem Borst

Publication date 19 October 2015

Published in Queueing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.08665

zbMATH Keywords

Markov chainswireless networksbroadcasting schemesmessage counttrickle algorithm

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Communication theory (94A05) Discrete-time Markov processes on general state spaces (60J05) Communication networks in operations research (90B18) Network design and communication in computer systems (68M10)

Abstract: As the use of wireless sensor networks increases, the need for efficient and reliable broadcasting algorithms grows. Ideally, a broadcasting algorithm should have the ability to quickly disseminate data, while keeping the number of transmissions low. In this paper, we analyze the popular Trickle algorithm, which has been proposed as a suitable communication protocol for code maintenance and propagation in wireless sensor networks. We show that the broadcasting process of a network using Trickle can be modeled by a Markov chain and that this chain falls under a class of Markov chains, closely related to residual lifetime distributions. It is then shown that this class of Markov chains admits a stationary distribution of a special form. These results are used to analyze the Trickle algorithm and its message count. Our results prove conjectures made in the literature concerning the effect of a listen-only period. Besides providing a mathematical analysis of the algorithm, we propose a generalized version of Trickle, with an additional parameter defining the length of a listen-only period.

Recommendations

• scientific article; zbMATH DE number 2202243
• An Efficient Counter-Based Broadcast Scheme for Mobile Ad Hoc Networks
• Semantic analysis of gossip protocols for wireless sensor networks
• Algorithms for Wireless Sensor Networks: Design, Analysis and Experimental Evaluation
• Time-efficient broadcast in radio networks

Cites work

• scientific article; zbMATH DE number 2186878 (Why is no real title available?)
• An Introduction to the Theory of Point Processes
• Failure rate modeling for reliability and risk
• General state space Markov chains and MCMC algorithms
• The broadcast storm problem in a mobile ad hoc network
• The limits of sequences of iterated overshoot distribution functions

Cited in

(4)

• Minimizing message size in stochastic communication patterns: fast self-stabilizing protocols with 3 bits
• Ability to Count Messages Is Worth Θ(Δ) Rounds in Distributed Computing
• Generalized random sequential adsorption on Erdős-Rényi random graphs
• Degree-dependent threshold-based random sequential adsorption on random trees

This page was built for publication: On the scalability and message count of trickle-based broadcasting schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q747717)