Message and time efficient multi-broadcast schemes

Liron Levin, Dariusz R. Kowalski, Michael SegalarXiv 2013 · DOI

Abstract

We consider message and time efficient broadcasting and multi-broadcasting in wireless ad-hoc networks, where a subset of nodes, each with a unique rumor, wish to broadcast their rumors to all destinations while minimizing the total number of transmissions and total time until all rumors arrive to their destination. Under centralized settings, we introduce a novel approximation algorithm that provides almost optimal results with respect to the number of transmissions and total time, separately. Later on, we show how to efficiently implement this algorithm under distributed settings, where the nodes have only local information about their surroundings. In addition, we show multiple approximation techniques based on the network collision detection capabilities and explain how to calibrate the algorithms' parameters to produce optimal results for time and messages.

Introduction

In wireless ad-hoc networks, communication is often constrained by limited battery life and shared, interference-prone channels. A fundamental challenge in these environments is the multi-broadcast problem: a scenario where a specific subset of source nodes each possesses a unique piece of data (a "rumor") that must be delivered to every other node in the network.

Optimizing these networks requires balancing two often-conflicting goals: message efficiency (minimizing total transmissions to conserve energy) and time efficiency (minimizing latency). This paper proposes a "bi-criteria" approximation approach that performs well on both metrics simultaneously. Central to this approach is a partial aggregation model, where up to c rumors can be compressed into a single message batch, reflecting practical data compression and header-stripping techniques.

The Network Backbone: Connected Dominating Sets

The authors' primary strategy involves constructing a network backbone using Connected Dominating Sets (CDS). A CDS is a subset of nodes such that every node in the graph is either in the set or a neighbor of a node in the set. The size of a Minimum CDS (MCDS) is directly proportional to message efficiency, as it represents the smallest group of nodes capable of reaching the entire network.

Relationship between source nodes and the MCDS backbone.

In the proposed centralized algorithm, the network finds a CDS and designates a "root" node. The process follows two phases:

  1. Convergecast: All source nodes send their rumors toward the root.
  2. Broadcast: The root aggregates the rumors into batches of size c and broadcasts them back to the entire network via the backbone.

Addressing Latency: Minimum Diameter CDS

While a small CDS ensures message efficiency, it does not guarantee speed. A standard MCDS might have a very large diameter (the longest path between any two nodes), leading to significant delays during the broadcast phase. This is often referred to as a "stringy" backbone.

Comparison of input graph diameter vs. MCDS diameter.

To solve this, the authors introduce a clustering technique using Depth-First Search (DFS) to create a Minimum Diameter CDS. This ensures the backbone's diameter is at most four times the diameter of the original graph ($4 \cdot d_G$), significantly reducing the time required for rumors to propagate across the network.

Distributed Implementation and Results

Transitioning from centralized to distributed settings—where nodes only know their immediate neighbors—introduces complexity. The authors provide routines tailored to the hardware's capabilities, specifically whether the nodes can detect signal collisions. Without collision detection, nodes must rely on acknowledgment-based protocols, which increases the message and time overhead.

Key Performance Metrics

  • Message Efficiency: For general graphs, the centralized algorithm achieves an approximation ratio of $(2H(\Delta) + 5)(1 + 1/c)$, where $\Delta$ is the maximum degree and $H$ is the harmonic number. In Unit Disc Graphs (UDG), the ratio is a constant 15.6.
  • Time Efficiency: By bounding the backbone diameter, rumors propagate in time proportional to the optimal possible delay ($s_{opt}$).

Conclusion and Future Work

This research demonstrates that a well-chosen CDS serves as a near-perfect proxy for an optimal transmission schedule in multi-broadcast scenarios. By incorporating diameter constraints, the authors bridge the gap between energy conservation and low latency.

Future work remains in testing these schemes under more complex interference models, such as SINR (Signal-to-Interference-plus-Noise Ratio), and adapting the algorithms for dynamic topologies where nodes are mobile or links are unstable. Closing the performance gap between centralized knowledge and purely local distributed information remains a primary open challenge in the field.

Summary updated

BibTeX
@misc{levin2013message,
  author = {Liron Levin and Dariusz R. Kowalski and Michael Segal},
  title = {{Message and time efficient multi-broadcast schemes}},
  year = {2013},
  doi = {10.4204/eptcs.132.3},
}
Figure