Scheduling in Single-Hop Multiple Access Wireless Networks with Successive Interference Cancellation

We study the optimal scheduling problem for minimizing the length of the schedule required to satisfy the traffic demands of the links in single-hop multiple access wireless networks using Successive Interference Cancellation (SIC). We first formulate the optimal scheduling as a Linear Programming (LP) problem where each variable represents the time allocated to a subset of the links sorted according to their decoding order for SIC at the receiver. Since the LP formulation requires a high number of variables exponential in the decoding capability of the receiver, we propose a Column Generation Method (CGM) based heuristic algorithm. This algorithm is based on decomposing the original problem into Restricted Master Problem (RMP) and Pricing Problem (PP), and approximating the exponentially complex PP by a greedy heuristic algorithm. Compared to the CGM based heuristic algorithms previously proposed for minimum length scheduling problem in various types of networks, the formulation of the PP and the heuristic algorithm proposed for PP are different due to the requirement of including the decoding order of simultaneous transmissions in SIC based networks. We demonstrate via simulations that the proposed algorithm performs very close to the optimal LP formulation with runtime robust to the increasing number of the links and decoding capability of the receiver, and much smaller than that of the optimal algorithm.