Upper and Lower Bounds for Deterministic Broadcast in Powerline Communication Networks

Yvonne-Anne Pignolet (1) , Stefan Schmid (2) , Gilles Trédan (3)

1 ABB Corporate Research [Västerås]
2 AAU - Aalborg University [Denmark]
3 LAAS-TSF - Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique

Powerline communication networks assume an interesting position in the communication network space: Similarly to wireless networks, powerline networks are based on a shared broadcast medium; unlike wireless networks , however, the signal propagation is constrained to the power lines of the electrical infrastructure, which is essentially a graph. This article presents an algorithmic model to study the design of communication services over powerline communication networks. As a case study, we focus on the fundamental broadcast problem, and present and analyze a distributed algorithm COLORCAST which terminates in at most n communication rounds, where n denotes the network size, even in a model where link qualities are unpredictable and time-varying. For comparison, the achieved broadcast time is lower than what can be achieved by any unknown-topology algorithm (lower bounds Ω(n log n/ log(n/D)) and Ω(n log D) are proved in [22] resp. [10] where D is the network diameter). Moreover, existing known-topology broadcast algorithms often fail to deliver the broadcast message entirely in this model. This article also presents a general broadcast lower bound for the powerline model.

Domaines: Réseaux et télécommunications [cs.NI]; Algorithme et structure de données [cs.DS]; Systèmes embarqués

Yvonne-Anne Pignolet, Stefan Schmid, Gilles Trédan. Upper and Lower Bounds for Deterministic Broadcast in Powerline Communication Networks. Distributed Computing, 2016, 29 (4), pp.239-250. ⟨10.1007/s00446-016-0263-1⟩. ⟨hal-02079806⟩