A Joint Routing and Time-Slot Assignment Algorithm for Multi-Hop Cognitive Radio Networks with Primary-User Protection

Cognitive radio has recently emerged as a promising technology to improve the utilization efficiency of the radio spectrum. In cognitive radio networks, secondary users (SUs) must avoid causing any harmful interference to primary users (PUs) and transparently utilize the licensed spectrum bands. In this paper, we study the PUprotection issue in multi-hop cognitive radio networks. In such networks, secondary users carefully select paths and time slots to reduce the interference to PUs. We formulate the routing and time-slot assignment problem into a mixed integer linear programming (MILP). To solve the MILP which is NP-Hard in general, we propose an algorithm named RSAA (Routing and Slot Assignment Algorithm). By relaxing the integral constraints of the MILP, RSAA first solves the max flow from the source to the destination. Based on the max flow, RSAA constructs a new network topology. On the new topology, RSAA uses branch and bound method to get the near optimal assignment of time slots and paths. The theoretical analyses show that the complexity of our proposed algorithm is O(N^4). Also, simulation results demonstrate that our proposed algorithm can obtain near-optimal throughputs for SUs.