Green wave sleep scheduling: Optimizing latency and throughput in duty cycling wireless networks

Duty cycling or periodic sleep scheduling of RF transceivers of nodes in a wireless ad hoc or sensor network can significantly reduce energy consumption. This paper sheds light on the fundamental limits of the end-to-end data delivery latency and the per-flow throughput in a wireless network with multiple interfering flows, in the presence of "coordinated" duty cycling. We propose green wave sleep scheduling (GWSS) inspired by synchronized traffic lights for scheduling sleep-wake slots and routing data in a duty cycling wireless network, whose performance can approach the aforementioned limits. Particularly, we derive a general latency lower bound and show that GWSS is latency optimal on various structured topologies, such as the line, grid and the tree, at low traffic load. For an arbitrary network, finding a solution to the delay-efficient sleep scheduling problem is NP-hard. But for the 2D grid topology, we show that a non-interfering construction of GWSS is optimal in the sense of scaling laws of latency and capacity. Finally, using results from percolation theory, we extend GWSS to random wireless networks, where nodes are placed in a square area according to the Poisson point process. Aided by strong numerical evidence for a new conjecture on percolation on a semi-directed lattice that we propose, we demonstrate the latency optimality of GWSS on a random extended network, i.e., for an area-n random network with unit-density-Poisson distributed nodes, and a node-active (duty-cycling) rate p, GWSS can achieve a per-flow throughput scaling of T(n,p) = Ω(p/√n) bits/sec and latency D(n,p) scaling of O(√n) + O(1/p) hops/packet/flow.