The Cost of Global Broadcast Using Abstract MAC Layers

Abstract

We analyze greedy algorithms for broadcasting messages throughout a multi-hop wireless network, using a slot-based model that includes message collisions without collision detection. Our algorithms are split formally into two pieces: a high-level piece for broadcast and a low-level piece for contention management. We accomplish the split using abstract versions of the MAC layer to encapsulate the contention management. We use two different abstract MAC layers: a basic non-probabilistic one, which our contention management algorithm implements with high probability, and a probabilistic one, which our contention management algorithm implements precisely. Using this approach, we obtain the following complexity bounds: Single-message broadcast, using the basic abstract MAC layer, takes time O(D log(n/epsilon) log(Delta)) to deliver the message everywhere with probability 1 - epsilon, where D is the network diameter, n is the number of nodes, and Delta is the maximum node degree. Single-message broadcast, using the probabilistic abstract MAC layer, takes time only O((D + log(n/epsilon)) log(Delta)). For multi-message broadcast, the bounds are O((D + k' Delta) log(n/epsilon) log(Delta)) using the basic layer and O((D + k' Delta log(n/epsilon)) log(Delta)) using the probabilistic layer,for the time to deliver a single message everywhere in the presence of at most k' concurrent messages.