Sleeping schedule-aware minimum latency broadcast in wireless ad hoc networks

Broadcast is a fundamental operation of wireless ad hoc networks (WANET) and has been widely studied in the last decade. However, very few existing broadcasting strategies has considered the scenarios with sleeping schedule, which is a prevalent power-saving method in wireless networks. In this paper we study the sleeping schedule-aware minimum latency broadcast (MLB-SA) problem in WANETs and prove its NP-hardness. By constructing a Shortest Path Tree (SPT) defined with the latency function on the network, we derive a lower bound on the broadcast latency theoretically. Following the top-down layered approach and using the D2-coloring solution, we proposed two progressively improved algorithms: the Simple LAyered Coloring algorithm (SLAC) and the Enhanced LAyered Coloring algorithm (ELAC) for the MLB-SA problem. The SLAC has an approximation ratio of O(Δ2 + 1) where Δ is maximum degree of the network, while the ELAC has constant approximation ratio of 24|T|+1 where |T| is the number of time-slots in a scheduling period. The two algorithms have O(n2) and O(n3) time complexities respectively. The performance of the proposed algorithms are evaluated by simulations.