Linear-Time Scheduling for Time-Varying Wireless Networks via Randomization

We study the problem of designing efficient throughput-optimal joint routing and scheduling policy for time-varying network, which has seen recent emergence from the surge in wireless edge-device systems. The only known solutions to the optimal control of dynamic network require solving the NP-hard problem of Max-Weight scheduling, thereby hindering the practicality. Even for the simplified setting of time-invariant network, previous work only considered efficient scheduling without routing, where any direct extension would only be able to incorporate unicast routing, which is restricted in practice. In this paper, we propose the Randomized Universal Max-Weight (RUMW) policy, which supports the generalized routing paradigm and relies on incremental sampling and updating rule to find good scheduling decisions, thereby resulting a linear-time scheduling algorithm. We further show that the RUMW algorithm is throughput-optimal in the setting of time-varying network. Of independent interest, the algorithmic structure of RUMW is directly congruent with the emerging Software-Defined Network (SDN) architecture.