Exploring the Design Space of Greedy Link Scheduling Algorithms for Wireless Multihop Networks

Abstract

It is known that using a spatial TDMA (STDMA) access scheme can increase the capacity of a wireless network over CSMA/CD access scheme. Modern wireless devices are capable of transmitting at different data rates depending on the current network condition. However, little attention has been paid to how best is to use the multiple data rates capability. In this report, we focus on greedy link scheduling algorithms that work with variable rates, where devices can transmit at lower data rates to accommodate lower quality links. We propose criteria that can be used in the scheduling algorithms and investigate performances of different scheduling algorithms that employ these different criteria. We use the more realistic physical interference model, where packet reception rate depends on signal-to-interference-plus-noise ratio. Our investigation shows that by using the variable rate approach, we can increase the overall capacity of the network over traditional single-threshold-based algorithms.