Linear programming-based model for joint routing and sleep scheduling in data-centric wireless sensor networks

“Sleep scheduling” is a widely adopted technique in wireless sensor networks (WSNs) for reducing unnecessary idle energy consumption; however, when MAC-layer sleep scheduling is carried out oblivious to network-layer routing, it may increase delay and even adversely affect the overall energy consumption in the network. To capture the interplay between scheduling and routing in a principled fashion, one can resort to the well-established paradigm of cross-layer formulation. Accordingly, in this paper, we draw on linear programming (LP) to propose a bi-objective model of delay and energy cost minimization in a TDMA-based WSN by formulating the problems of sleep scheduling and routing conjointly. Compared to prior art, our formulation not only is bi-objective, but also is more realistic given that it explicitly accounts for link capacities and different types of signal interference that may affect a wireless transmission; we further present extensions of the formulation for the situations when sensor nodes have the capability of data aggregation. The optimal solution provided by this paper can serve as a theoretical benchmark to evaluate any heuristic targeting the same problem.