Date Added: Jul 2012
In this paper, the authors study the problem of scheduling wireless links in a model where successive interference cancellation is combined with the physical interference model and uniform power assignment. 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.