Level-based approach for minimum-transmission broadcast in duty-cycled wireless sensor networks

Broadcast is a fundamental activity in wireless sensor networks (WSNs) and many problems related to broadcast have been formulated and investigated in the literature. Among them, the minimum-transmission broadcast (MTB) problem, which aims to reduce broadcast redundancy, has been well studied in conventional wireless ad hoc networks, where network nodes are assumed to be active all the time. In this paper, we study the MTB problem in duty-cycled WSNs where sensor nodes operate under active/dormant cycle and propose a novel scheme to solve it efficiently. The proposed Level-Based Approximation Scheme first identifies the forwarding nodes and their corresponding receivers for all time slots; then constructs a broadcast backbone by connecting these forwarding nodes to the broadcast source. The backbone construction is accomplished by a two-stage traversal on all the forwarding nodes, which successfully exploits transmissions of each forwarding node to its receivers. We have also conducted extensive simulations to evaluate the performance of our proposed scheme. Simulation results indicate that our scheme significantly outperforms existing ones.