Complexity of minimum uplink scheduling in backbone-assisted successive interference cancellation-based wireless networks

Abstract Relative to the networks with multiple independent sinks, in backbone-assisted networks, multiple sinks are connected together with high-speed wirelines. So, by exchanging decoded signals of User Equipments (UEs) among sinks through the backbones, more interferences to undecoded signals could be cancelled further. Thus, potential optimization rooms for reducing access delays are provided. In this paper, we study the problem of minimum uplink scheduling for Backbone-Assisted Successive Interference Cancellation-based Wireless Networks (BASICWNs), so as to reduce the mean access delays of UEs. We formulate the problem, and prove that it is NP-Complete by presenting a reduction from the partition problem. We further propose a polynomial-time heuristic algorithm based on the greedy strategy that as many UEs as possible are simultaneously scheduled in one slot. Experimental results show, relative to that with multiple independent sinks, the uplink frame length of BASICWNs is reduced by 48% with the heuristic algorithm proposed, and the performance is virtually very close to the optimum.