Mixed Integer-Linear Programming for Link Scheduling in Interference-Limited Networks

We consider the problem of link scheduling in wireless networks with interference. The problem of computing a link schedule to minimize the power consumption with the constraint that each link supports a given average data rate is formulated as an optimization problem. A simple analytical solution is obtained for time division multiple access (TDMA) scheduling to minimize a linear combination of the average power consumption on the links; this schedule gives the minimum total power consumption for regular topologies. We then propose a method to compute energy efficient link schedules. It consists of the following two steps. (1) computation of a schedule (using a mixed integer-linear programming formulation) that minimizes the maximum sum of the cross-link gains from interfering links to an active link, subject to the constraint that each link is active for a time proportional to the optimal slot length computed for TDMA schedules. (2) power control to find the minimum transmission power vector that supports the desired average data rates on the links for the computed schedule. We also briefly consider the reverse problem of computing a link schedule that maximizes the minimum link rate, for given fixed link transmission powers.