Integer linear programming formulations for the variable data rate and variable channel bandwidth scheduling problem in wireless networks

摘要

The IEEE 802.11ac standard enables a higher transmission speed than the previous IEEE standards because it allows the network frequency spectrum to be divided into communication channels of different bandwidths, varying from 20MHz to 160MHz. In this paper, we introduce the Variable Rate and Variable Bandwidth Scheduling Problem (VRBSP), which is a generalization of the classical Variable Rate Scheduling Problem (VRSP) on wireless networks. The best algorithm in the literature of VRSP, Datarate PPTAS, can only be efficiently run on networks with up to 64 links and does not guarantee optimality. In this paper, we propose two Mixed Integer Linear Programming (MILP) formulations that are used within a MILP solver to seek optimal schedules for VRBSP. This approach can also be used to solve VRSP. The computational experiments were carried out on classical network instances from the literature with up to 2048 links. They show that the MILP-based exact algorithms were able to find optimal VRBSP schedules for networks with up to 256 links and optimal VRSP schedules for networks with up to 1024 links within 3600 seconds of running time. (C) 2019 Elsevier B.V. All rights reserved.