Link scheduling in wireless networks with successive interference cancellation

Successive interference cancellation (SIC) is an effective way of multipacket reception (MPR) to combat interference at the physical layer. To understand the potential MPR advantages, we study link scheduling in an ad hoc network with SIC at the physical layer. The fact that the links detected sequentially by SIC are correlated at the receiver poses key technical challenges. A link can be interfered indirectly when the detecting and removing of the correlated signals fail. We characterize the link dependence and propose a simultaneity graph (SG) to capture the effect of SIC. Then interference number is defined to measure the interference of a link. We show that scheduling over SG is NP-hard and the maximum interference number bounds the performance of a maximal greedy scheme. An independent set based greedy scheme is explored to efficiently construct a maximal feasible schedule. Moreover, with careful selection of link ordering, we present a scheduling scheme that improves the bound. The performance is evaluated by both simulations and measurements in a testbed. The throughput gain is on average 40% and up to 120% over IEEE 802.11. The complexity of SG is comparable with that of conflict graph, especially when the network size is not large. (C) 2011 Elsevier B.V. All rights reserved.