Data-rate maximization in wireless communication networks

Despite great effort from the research community, wireless networks still operate below full capacity. To increase the network throughput it is important to study algorithms that select communication requests that can decode their signals despite mutual interference. In this paper, we study the joint problem of data rate assignment and link scheduling in the physical interference model. The objective of the problem is to maximize the total number of bits transmitted in one time slot. By constructing an intermediate network representation through a disk graph, we prove that a constant approximation solution can be computed in polynomial time. Finally, we propose a parallel implementation of a polynomial-time approximation scheme and show through simulations that the one-slot throughput of a wireless network can be significantly improved by using variable data rates.