Optimal Spectrum Scheduling in Cognitive Wireless Mesh Networks

In a cognitive wireless mesh network (CogMesh), each cognitive radio (CR) enabled mesh node can sense and opportunistically access the under-utilized spectrums in the primary system. Since the unoccupied spectrum is location- dependent and time-dependent, the available spectrums in each mesh node are different. With this spectrum heterogeneity, each node shall have the knowledge of spectrum, scheduling, and routing path of other nodes such that it can communicate with them with minimal cost and no collision. The problem may occur in a number of the situations, e.g. the routing table re-building and the unicast real-time applications. In this paper, we focus on the 2-hop spectrum scheduling, which will enable any pair of 2-hop neighborhood nodes know the spectrum, collision-free scheduling, and minimal-cost routing path. Two optimal strategies are proposed to address the spectrum scheduling: optimal deterministic spectrum scheduling (ODS) and optimal randomized spectrum scheduling (ORS). In the deterministic situation, with the scheme ODS, the 2-hop spectrum scheduling can be solved in polynomial time. In the randomized situation, with the scheme ORS, the 2-hop spectrum scheduling can be solved in polynomial time with high probability at least (1 - 1/n) where n denotes the network size. The simulation experiment is carried out to show the achievable performance of the proposed algorithms.