  Recent trends suggest that cognitive radio based wireless networks will be
frequency agile and the nodes will be equipped with multiple radios capable of
tuning across large swaths of spectrum. The MAC scheduling problem in such
networks refers to making intelligent decisions on which communication links to
activate at which time instant and over which frequency band. The challenge in
designing a low-complexity distributed MAC, that achieves low delay, is posed
by two additional dimensions of cognitive radio networks: interference graphs
and data rates that are frequency-band dependent, and explosion in number of
feasible schedules due to large number of available frequency-bands. In this
paper, we propose MAXIMALGAIN MAC, a distributed MAC scheduler for frequency
agile multi-band networks that simultaneously achieves the following: (i)
optimal network-delay scaling with respect to the number of communicating
pairs, (ii) low computational complexity of O(log2(maximum degree of the
interference graphs)) which is independent of the number of frequency bands,
number of radios per node, and overall size of the network, and (iii)
robustness, i.e., it can be adapted to a scenario where nodes are not
synchronized and control packets could be lost. Our proposed MAC also achieves
a throughput provably within a constant fraction (under isotropic propagation)
of the maximum throughput. Due to a recent impossibility result, optimal
delay-scaling could only be achieved with some amount of throughput loss [30].
Extensive simulations using OMNeT++ network simulator shows that, compared to a
multi-band extension of a state-of-art CSMA algorithm (namely, Q-CSMA), our
asynchronous algorithm achieves a 2.5x? reduction in delay while achieving at
least 85% of the maximum achievable throughput. Our MAC algorithms are derived
from a novel local search based technique.
