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 to schedule, and ii. in what order in a time-slot to decode each transmission in order to maximize the system utility and/or satisfy a system constraint. 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 several different scheduling problems in this context. The objective of the problems is to either maximize the throughput of the system or to obtain some kind of fairness among the users. We formulate and study each problem from the perspective of computational complexity. For each problem, we either propose a polynomial time algorithm, if any exists, or show that the problem is NP-hard.

Successive Interference Cancellation (SIC) is a physical-layer technique that enables reception of multiple overlapping transmissions. While SIC has the potential to boost the network throughput, if the MAC protocol employed in the network is agnostic to such a capability at the physical-layer, the full potential of SIC can not be utilized in the network. There have been a number of studies to design new SIC-aware MAC protocols or adjust the existing protocols to exploit SIC. Despite that, the exact effect of MAC protocols on the throughput of SIC-enabled networks is unknown. In this paper, we propose a novel SIC-aware MAC protocol based on the disparity of user channels in a wireless network and analyze its performance. We consider a simple random access protocol with no SIC as the base configuration and compare it with three other configurations with different levels of SIC-awareness. We show that while a SIC-enabled physical layer without a SIC-aware MAC protocol can increase the throughput of the network by 1.5×, a specifically designed MAC protocol is far more efficient achieving up to 3.3× improvement in throughput. Our SIC-aware MAC protocol is fully distributed and hence subject to selfish behavior of users. Thus, we also consider the case where the users behave selfishly. We model our proposed protocol as a one-shot simultaneous move game and derive a mixed strategy Nash equilibrium. We also show that we can set the cost of packet transmission in such a way that we get the optimal system throughput at the Nash equilibrium.

This paper considers the problem of uplink scheduling in wireless networks supporting successive interference cancellation (SIC) at the physical layer. By allowing concurrent interfering transmissions, SIC enables multi-packet reception at the receiver resulting in increased network throughput. Specifically, we consider maximum throughput scheduling and proportional fair scheduling problems and study optimal and heuristic algorithms for these problems. We prove that the maximum throughput scheduling problem is NP-hard and develop a throughput efficient polynomial time greedy algorithm for the problem. While being throughput efficient, the maximum throughput scheduling can lead to highly unfair rates among the users. The proportional fair scheduling, on the other hand, is not throughput optimal but achieves proportional fairness among the users. For scheduling multiple users in a single time-slot, we show that there exists an algorithm that solves the proportional fair scheduling problem in polynomial time. For scheduling in multiple time-slots, we develop a greedy algorithm that computes a highly fair schedule in polynomial time. Numerical results are also provided to show the utility and efficiency of the proposed scheduling algorithms in various simulated networks.