BLMST: a scalable, power-efficient broadcast algorithm for wireless networks

The power-efficient broadcast for multi-hop wireless networks is discussed in this paper. We first investigate the trade-off between (i) using larger transmission power to reach more nodes in one hop and (ii) using smaller power and relaying broadcast messages through multiple hops. Analysis indicates that multi-hop broadcast is more power-efficient if α ≥ 2.2, where the power consumption model is P(r, α) = c₀ · r^α + c₁. Based on the analysis, we propose broadcast on local minimum spanning tree (BLMST). An underlying topology is first derived using local minimum spanning tree (LMST), a localized topology control algorithm. Broadcast messages are then simply relayed through the derived topology in a constrained flooding fashion. BLMST is fully localized, scalable, and power-efficient. Simulation results show that the performance of BLMST is comparable to that of existing centralized algorithms.