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

DOI10.1007/S11134-015-9438-XzbMATH Open1325.60122DBLPjournals/questa/MeyfroytBBD15arXiv1509.08665OpenAlexW2169536423WikidataQ59428054 ScholiaQ59428054MaRDI QIDQ747717FDOQ747717

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)

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.

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

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

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)

Cites Work

• General state space Markov chains and MCMC algorithms
• An Introduction to the Theory of Point Processes
• Title not available (Why is that?)
• Failure rate modeling for reliability and risk
• The broadcast storm problem in a mobile ad hoc network
• The limits of sequences of iterated overshoot distribution functions

Cited In (4)

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

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)