Cognitive Radio (CR) capitalizes advances in signal processing and radio technology and is capable of reconfiguring RF and switching to desired frequency bands. It is a frequency-agile data communication device that is vastly more powerful than existing multi-channel multi-radio (MC-MR) technology. In this thesis, we investigate the important problem of multi-hop networking with CR nodes. In a CR network, each node has a set of frequency bands (not necessarily of equal size) that may not be the same as those at other nodes. The uneven size of frequency bands prompts the need of further division into sub-bands for optimal spectrum sharing. We characterize behaviors and constraints for such multi-hop CR network from multiple layers, including modeling of spectrum sharing and sub-band division, scheduling and interference constraints, and flow routing. We give a formal mathematical formulation with the objective of maximizing the network throughput for a set of user communication sessions. Since such problem formulation falls into mixed integer non-linear programming (MINLP), which is NP-hard in general, we develop a lower bound for the objective by relaxing the integer variables and linearization. Subsequently, we develop a nearoptimal algorithm to this MINLP problem. This algorithm is based on a novel sequential fixing (SF) procedure, where the integer variables are determined iteratively via a sequence of linear program (LP). In order to implement and evaluate these algorithms in a controlled laboratory setting, we design and implement an emulation testbed. The highlights of our experimental research include: ⢠Emulation of a multi-hop CR network with arbitrary topology; ⢠An implementation of the proposed SF algorithm at the application layer; ⢠A source routing implementation that can easily support comparative study between SF algorithm and other schemes; ⢠Experiments comparing the SF algorithm with another algorithm called Layered Greedy Algorithm (LGA); ⢠Experimental results show that the proposed SF significantly outperforms LGA. In summary, the experimental research in this thesis has demonstrated that SF algorithm is a viable algorithm for optimal spectrum sharing in multi-hop CR networks.
