Optimal Scheduling for Emptying a Wireless Network: Solution Characterization, Applications, Including Deadline Constraints

Link scheduling, i.e., which links should transmit together and for how long, has been and remains a cornerstone optimization problem in wireless networking. In minimum-time scheduling, the task is to minimize the amount of time before emptying the data demand residing at the source nodes. We derive a complete structural characterization of the solution that unifies and significantly extends the known results. First, we approach link scheduling with a general system model without restrictions on the shape of the achievable rate region. Then, we give and prove a solution characterization of optimality that is conceptually simple yet powerful. We demonstrate several applications of this characterization for analysis of optimality and problem tractability. Next, we consider a significant extension by including deadline constraints, under which optimal scheduling becomes much more complex. Yet, we show how our formulation yields a solution description for that problem as well.
Funding Agencies|Swedish Research CouncilSwedish Research Council; National Science FoundationNational Science Foundation (NSF) [CCF-0728966, CCF-1420651]; ONROffice of Naval Research [N000141410107]; European UnionEuropean Union (EU)