Algorithms for the Wireless Scheduling Problem With Frequency Band Partition in Wi-Fi

In this work, we extend the classical Shortest Link Scheduling problem from the wireless network literature with features from Wi-Fi protocols. In this variant, one must decide the joint task of wireless link scheduling and frequency band partition considering the SINR interference model. Besides, each scheduled transmission must have a minimum throughput indicated in the input. We contribute to the literature with a constructive heuristic and a mathematical formulation based on integer programming. Moreover, we build benchmark instances following the methodology found in related work, and each instance can have up to 512 links. The computational experiments show that our formulation found optimal solutions for instances with up to 128 links within 7200 seconds. The experiments also show that the heuristic can find feasible solutions for the hardest instances within less than one second.