On the Complexity of Wireless Uplink Scheduling with Successive Interference Cancellation
Date
2011-07-14T15:39:52Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this paper, we study the problem of uplink scheduling in wireless networks with successive
interference cancellation (SIC). With SIC, concurrent transmissions, if properly scheduled, can be
successfully decoded at a receiver. The scheduler decides: (i) in which time-slot, and (ii) in what
order in a time-slot to decode each transmission in order to maximize the system utility. These two
scheduling decisions effectively determine the rates allocated to concurrent transmissions, which in turn
determine the throughput and fairness of the system. We consider two scheduling problems, namely
the Maximum Throughput Scheduling and Proportional Fair Scheduling. We prove the first problem is
NP-hard, while the second seemingly harder problem can be solved in polynomial time.
Description
Keywords
Wireless Uplink