Fast computation of schedules for dynamic traffic in wireless mesh networks

A large number of algorithms focus on using scheduling to maximize the stability region. However, this goal does not necessarily result in good performance in terms of supporting a large number of users where users' average time to transfer a file meets a target. This paper develops several computationally efficient schemes for computing schedules for time-varying offered load. Two important findings are that when the traffic is time-varying, the computational complexity can be substantially reduced by using the previous schedule as an initial starting point of the optimization (i.e., warm start). Furthermore, very few iterations (e.g., one iteration) are needed to get a suitable schedule, that is, there is no need to wait for the optimization to converge. A second finding is that there is no need to repeatedly solve the maximum weighted independent set (MWIS) problem. Instead, the MWIS problem is only solved during initialization. Because of the computational efficiency, the schemes presented can be used to frequently update schedules, allowing schedules to quickly adapt to changes in the offered load. Consequently, as compared to other scheduling schemes, the schemes developed support a larger number of users for a given average service time.