Minimum-Latency Broadcast Schedule in Duty-Cycled Multihop Wireless Networks Subject to Physical Interference

Broadcast, one of the most essential operations in multihop wireless networks, is widely used for routing discovery, data collection, code updating and other network functions. The problem of computing a broadcasting schedule with minimum latency in multihop wireless networks is referred to as Minimum-Latency Broadcasting Schedule (MLBS). Under the assumption that all the nodes are always active, MLBS has been extensively studied. However, it is well-known that the networking nodes often switch between the active state and the sleep state to save energy. Unlike in conventional scenarios without sleep cycles, a node in duty-cycled scenarios with active/sleep cycles may require transmitting multiple times to send the broadcast message to all of its neighbors due to their different active time. The problem MLBS with Duty-Cycled scenarios (MLBSDC) has been well-studied in graph-based interference models such as the protocol interference model. To the best of our knowledge, no approximation algorithms have been proposed in the literature for the problem MLBSDC under the physical interference model with the duty-cycled scenarios taken into consideration. This is the first paper that develops efficient approximation algorithms for MLBSDC in multihop wireless networks with the duty-cycled scenarios under the physical interference model. Our algorithm, built upon a general technique which enables a unified graph-coloring treatment for communication scheduling, achieves approximation bound at most a constant time of the length of a scheduling period.