Scheduling dynamic wireless networks with limited operations

摘要

Scheduling in wireless networks is critical to maximize the network throughput by avoiding interference among wireless links, and is usually formulated as solving the NP-hard Maximum Weighted Independent Set (MWIS) problem over a network confiict graph. Existing scheduling algorithms are designed to provide approximations to global optimality via distributed operations in wireless networks, but will frequently reschedule the entire network in cases of network dynamics regardless of the actual network area being affected by these dynamics. Such repetitive rescheduling results in a large amount of computation and communication overhead, most of which may be, however, unnecessarily incurred over the wireless links that remain unchanged. To reduce such overhead and improve the scheduling cost-effectiveness, in this paper we develop distributed algorithms that adaptively constrain network scheduling within the limited scope where network dynamics occur. The scheduling results from such limited operations are then combined with the previous scheduling results over the remaining portions of the network, hence still providing guaranteed network throughput. The performance of our proposed algorithms has been validated by formal analysis, and been verified by both numerical studies and real-world experiments.