Chennai Mathematical Institute


Approximation Algorithms for Power-Aware Scheduling of Wireless Sensor Networks with Rate and Duty-Cycle Constraints
Rajgopal Kannan
Louisiana State University.


In this talk, I discuss Fully Polynomial Approximation schemes for a particular version of the minimum energy transmission scheduling problem for duty-cycle and rate constrained wireless sensor nodes transmitting over an interference channel. Since traditional optimization methods using Lagrange multipliers do not work well and are computationally expensive given the non-convex constraints, we develop fully polynomial approximation schemes (FPAS) for finding optimal schedules by considering restricted versions of the problem using multiple discrete power levels. For two fixed transmit power levels (0 and P), we develop a 2-factor approximation for finding the optimal fixed transmission power level per time slot, P_opt, that generates the optimal (minimum) energy schedule. This can then be used to develop a (2,1+epsilon)-FPAS that approximates the optimal power consumption and rate constraints to within factors of 2 and arbitrarily small epsilon>0, respectively. Finally, we develop an algorithm for computing the optimal number of discrete power levels per time slot (O(1/epsilon)), and use this to design a (1, 1+epsilon)-FPAS that consumes less energy than the optimal while violating each rate constraint by at most a 1+epsilon factor.