Wireless scheduling with multiple data rates: From physical interference to disk graphs

Scheduling of wireless transmissions is a core component of performance optimization of wireless ad-hoc networks. Current radio technologies offer multi-rate transmission capability, which allows to increase the network's throughput. Nevertheless, most approximability results of scheduling algorithms have focused on single-rate radios. In this paper, we propose two formulations for the problem of scheduling wireless requests with multiple data-rates, considering the physical interference model with uniform power assignment. The objective of both problems is to select a subset of communication requests to transmit simultaneously, such that the sum of their data rates is maximized and no collisions occur. In the first formulation, data-rates are given as part of the input. In the second formulation, the data-rate assignment is part of the solution. We show that, under certain constraints on the input, these problems can be approximated by a disk graph model. This means that, despite the global nature of the physical interference model, conflicts between simultaneous requests can be restricted to the local neighborhood of the transmitting nodes. We show how to build the corresponding disk graph instances and prove that a weighted maximum independent set in this graph-based model provides a constant-factor approximation in the physical interference model. Moreover, we implement a polynomial-time approximation scheme, as well as a parallel implementation of the algorithm, to obtain solutions that are within an arbitrarily small factor of being optimal in the disk graph model.