Scheduling Wireless Links with Successive Interference Cancellation

In this paper we study the problem of scheduling wireless links in a model where successive interference cancellation is combined with the traditional physical interference model. Successive interference cancellation is based on the observation that interfering signals should not be treated as random noise, but as well-structured signals. By exploiting this structured nature, the strongest signal can be decoded and subtracted from a collision, thus enabling the decoding of weaker simultaneous signals. The procedure can be repeated iteratively as long as the collided signals differ in strength significantly. It has been shown that the problem of scheduling wireless links with successive interference cancellation is NP-hard. In this work, we propose a polynomial-time scheduling algorithm that uses successive interference cancellation to compute short schedules for network topologies formed by nodes arbitrarily distributed in the Euclidean plane. We prove that the proposed algorithm is correct in the physical interference model and provide simulation results demonstrating the performance of the algorithm in different network topologies. We compare the results to solutions without successive interference cancellation and observe that throughput gains of up to 20% are obtained in certain scenarios.