Inductive coloring: implementing basic communication primitives with Rayleigh-fading interference

Abstract

We study distributed algorithms for achieving efficient communications in the Rayleigh-fading Model. This model extends the popular deterministic SINR model using stochastic propagation to address fading effects observed in reality. Stochastic propagation greatly increases the difficulty of dealing with interference and collisions, especially in a local context without much global knowledge. We present a new technique called Inductive Coloring that can be used to schedule fast transmissions with Rayleigh-fading interference. The computation of inductive coloring takes only O(log2n) time with the proposed distributed algorithm, where n is the number of nodes in the network. We illustrate the power of inductive coloring by giving algorithms for implementing two basic communication primitives. The first primitive is Local Broadcast (LB), which can work in a MAC layer and has been widely studied in different interference models. The proposed algorithm for LB matches the fastest one under the simpler SINR model. The second primitive is Single-Reception (SR), which is to make each node receive at least one message from its neighbors. The proposed algorithm can implement SR in O(log2 n) rounds. To illustrate the versatility of the SR primitive, we use the primitive to derive efficient algorithms for information broadcast and function computations. We conduct simulations to verify all the proposed algorithms, and the results show that the algorithms also perform well in realistic environments.