Minimum-Latency Beaconing Schedule in duty-cycled multihop wireless networks

Beaconing is a primitive communication task in which every node locally broadcasts a packet to all of its neighbors within a fixed distance. The problem Minimum Latency Beaconing Schedule (MLBS) seeks a shortest schedule for beaconing subject to the interference constraint. MLBS has been well studied when all the nodes are always awake. However, it is well-known that the networking nodes often switch between the active state and the sleep state to save energy. A node in duty-cycled scenarios may require transmitting multiple times to inform all of its neighbors due to their different active times. Thus, all of the known algorithms for MLBS are not suitable for duty-cycled multihop wireless networks. In this paper, we study MLBS in Duty-Cycled multihop wireless networks (MLBSDC). We first present two constant-approximation algorithms for MLBSDC under the protocol interference model with the approximation bounds independent of the length of a scheduling period. Then, we develop an efficient algorithm for MLBSDC under the physical interference model. To the best of our knowledge, this is the first paper that develops efficient algorithms for MLBSDC under either of these two interference models.