Towards reliable broadcast in practical sensor networks

Lewis Tseng, Boston College

Abstract

Broadcast is one of the fundamental primitives to enable sensor networks. In this paper, we address some practical concerns regarding reliable broadcast. Particularly, we consider the following issues: • Hybrid fault model: We prove the tight necessary and sufficient condition for using Certified Propagation Algorithm (CPA) to achieve reliable broadcast in directed networks under hybrid fault model. The hybrid fault model considers both node and link failures. • Geometric Random Graph: Geometric random graph is considered to be a suitable network model for sensor network deployment. We show that our condition has close relations with connectivity in geometric random graphs in the one-dimensional space. We prove that with a suitable choice of parameters, we can use CPA to achieve reliable broadcast in such graphs. • Eventually reliable broadcast: We also study the reliable broadcast problem with relaxed properties. Especially, we explore the trade-off between latency of broadcast and validity (or correctness). For validity, we provide a lower bound on the probability of receiving a correct value in any graphs. For latency, we show that in the geometric random graphs in the one-dimensional space, the proposed algorithm achieves low latency (through simulations).