Weighted beeping networks improve local broadcast with signal strength
Weighted Beeping Networks
Distributed, Parallel, and Cluster Computing
Summary
Traditional beeping networks assume that a beep either happens or doesn't, but in real wireless systems signals can be stronger or weaker. This paper extends that simple model by assigning weights to connections, so a beep is heard only if the combined signal strength reaches a threshold. The authors design an algorithm that efficiently broadcasts messages in this weighted setting, proving it is almost as fast as possible. They also show how older algorithms can work in this new model with some extra effort.
What this means in practice
- •For wireless network designers: Create communication protocols that consider variable signal strengths for more realistic wireless deployments.
- •For sensor network engineers: Improve local message broadcasting in sensor networks where nodes have different transmission powers and varying interference.
Authors
Dariusz R. Kowalski, Miguel A. Mosteiro
Abstract
Beeping Networks (BN) have become an established model of wireless communication and computation. They assume, however, that the communication interference caused by beeping nodes is binary (OR channel), while both artificial and nature-driven networks are based on varied signal strength and receiving thresholds. This work naturally extends the classic beeping networks to weighted beeping networks (WBN), by modeling signal strengths by weights on graph edges and receiving a beep if the accumulative signal strengths of transmitting neighbors are above receiving threshold. Under this generalized model, we study the fundamental Local Broadcast (LB) problem. Since edges with low weights may not even accumulate to a received beep, we only require that messages are delivered along sufficiently heavy edges, with weights above some given threshold $σ$. We design an LB algorithm that completes its task in $O(I_σ\log n \cdot (\mathcal{M}+\log n))$ beeping rounds, whp, where $n$ is the number of nodes, $I_σ$ is the maximum local interference on heavy edges, and $\mathcal{M}$ is the maximum length of messages sent locally. This result is nearly optimal, as, with probability $1$, $Ω(I_σ)$ beeping rounds are necessary to solve LB. Finally, we show that any algorithm designed for the classic beeping networks and terminating in polynomial number of beeping rounds, can be emulated on any WBN with a logarithmic overhead, that is, it returns the same output as working on the classic beeping network isomorphic to the sub-graph of heavy edges.