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...

Full description

Saved in:
Bibliographic Details
Published in:Computer networks (Amsterdam, Netherlands : 1999) Netherlands : 1999), 2019-12, Vol.165, p.106939, Article 106939
Main Authors: Costa, José Maurício, Paniago, Pedro P., de Andrade, Joaquim, Noronha, Thiago F., Vieira, Marcos A.M.
Format: Article
Language:English
Subjects:
Algorithms
Bandwidths
Combinatorial optimization
Frequency spectrum
Integer programming
Linear programming
Link scheduling
Links
Mixed integer
Optimization
Production scheduling
Schedules
Scheduling
Wireless networks
Wireless scheduling problem
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1389-1286
1872-7069
DOI:10.1016/j.comnet.2019.106939