Minimum schedule lengths with rate control in wireless networks

In this paper, we study the problem of joint scheduling and rate control in wireless networks, when each transmitter has a finite amount of data traffic to deliver to its corresponding receiver. Our objective is to minimize the time required to deliver the total data traffic. The scheduling decisions take into account the constraints of the physical layer through the well-known physical interference model. First, we consider a time-slotted system. We provide an optimal solution through a graph-theoretic model, where the minimum-length scheduling problem is formulated as finding a shortest path on a single source directed acyclic graph. Next, due to the complexity of the discrete time problem, we simplify it in two dimensions: (i) we map it to a continuous time problem, and (ii) we restrict the set of feasible scheduling and rate control decisions that can be employed. We finally obtain an optimal scheduling and rate control policy of this simplified problem.