Optimal scheduling for multi-radio multi-channel multi-hop cognitive cellular networks

Due to the emerging various data services, current cellular networks have been experiencing a surge of data traffic and are already overloaded; thus, they are not able to meet the ever exploding traffic demand. In this study, we first introduce a multi-radio multi-channel multi-hop cognitive cellular network (M³ C² N) architecture to enhance network throughput. Under the proposed architecture, we then investigate the minimum length scheduling problem by exploring joint frequency allocation, link scheduling, and routing. In particular, we first formulate a maximal independent set based joint scheduling and routing optimization problem called original optimization problem (OOP). It is a mixed integer non-linear programming (MINLP) and generally NP-hard problem. Then, employing a column generation based approach, we develop an ε-bounded approximation algorithm which can obtain an ε-bounded approximate result of OOP. Noticeably, in fact we do not need to find the maximal independent sets in the proposed algorithm, which are usually assumed to be given in previous works although finding all of them is NP-complete. We also revisit the minimum length scheduling problem by considering uncertain channel availability. Simulation results show that we can efficiently find the ε-bounded approximate results and the optimal result as well, i.e., when ε = 0% in the algorithm.