On routing and channel selection in cognitive radio mesh networks

Secondary users in a cognitive radio mesh network may select from a set of available channels, provided that they do not disrupt communications among primary users. This ability can improve the overall network performance but introduces the question of how to best use the channels. This paper first considers the problem of selecting the channels to use given a routing path such that the end-to-end throughput along the path is maximized. We show that a dynamic programming-based approach can optimally solve the problem and, if the path satisfies a natural condition, in time, be linear in the length (hop count) of the path. In addition, the algorithm can easily be implemented in a distributed fashion. We also examine the harder joint problem of finding the best routing path and channel selection that maximizes the end-to-end throughput. We prove that obtaining a (2/3 + ε) approximation to the joint problem is NP-hard. We then present a heuristic algorithm for the joint problem and a second heuristic channel-aware routing-only algorithm. Numerical results are provided to demonstrate the effectiveness of the methods on several experimental scenarios.