A distributed broadcast algorithm for duty-cycled networks with physical interference model

Broadcast is a fundamental operation in multi-hop wireless networks. Given a source node with a message to broadcast, the objective is to propagate the message to all nodes in an interferencefree manner while incurring minimum latency. This problem, called Minimum-Latency Broadcast Scheduling (MLBS), has been studied extensively in wireless networks whereby nodes remain on all times and has been shown to be NP-hard. However, only a few studies have addressed this problem in the context of duty-cycled wireless networks, which unfortunately, remains NP-hard. In these networks, nodes do not wake up simultaneously, and hence, not all neighbors of a transmitting node will receive a broadcast message at the same time, meaning multiple transmissions may be necessary. Moreover, most of these studies addressed the MLBS problem over the idealistic protocol interference model. Henceforth, this paper considers MLBS for duty-cycled wireless networks under the physical interference model and presents an approximation algorithm called hexagon-based broadcast algorithm (HBA), which has a constant ratio in terms of broadcast latency and transmission times. We have evaluated HBA in different network configurations, and the results show that the latencies achieved by our algorithm are much lower than existing schemes. In particular, HBA manages to half the broadcast latency achieved by the state-of-the-art tree-based algorithm.