Energy-latency trade-offs in real-time wireless sensor networks

Wireless Sensor Networks (WSN) can be modeled as Discrete Event Systems (DES). In this dissertation, we study the optimal control of a class of resource allocation problems characterized by energy-latency trade-offs in WSN using the framework of DES. Our work is based on the observation that energy of wireless nodes can be greatly saved by introducing some delay of task completion time. Specifically, we consider a family of problems motivated by WSN such as Dynamic Transmission Control and Dynamic Voltage Scaling, where the objective is to minimize energy consumption while satisfying real-time operating constraints.; We study both off-line and on-line control problems. In the off-line case, we show that a static policy is the unique optimal control of a problem subject to task deadline constraints, as long as the cost function is strictly convex, differentiable, and monotonically decreasing in the service time per operation. We propose a novel Receding Horizon (RH) on-line control method to bypass the complexity that would result from a stochastic analysis of the problem. The RH scheme possesses a number of attractive properties, including (i) the fact that it still guarantees all real-time constraints (if the original off-line optimization problem is feasible) and (ii) the fact that the error introduced relative to the optimal control can actually be zero over segments of the sample path of the system. Simulation results verify these properties and show that the RH controller performs well even if the RH window size is not large. In addition, sample path analysis techniques are used to develop a Generalized Critical Task Decomposition Algorithm (GCTDA) for solving the Downlink Transmission Scheduling (DTS) problem. Our algorithm utilizes a two-fold decomposition approach, which is more efficient than the existing ones in the literature for solving similar problems. Moreover, we show that (i) the optimal transmission scheduling problem in a path that contains relay nodes can be transformed to a much simpler DTS problem and (ii) the optimal control of a transmission scheduling problem in multi-access channels possesses a special structure.