  In recent years there is a growing effort to provide learning algorithms for
spectrum collaboration. In this paper we present a medium access control
protocol which allows spectrum collaboration with minimal regret and high
spectral efficiency in highly loaded networks. We present a fully-distributed
algorithm for spectrum collaboration in congested ad-hoc networks. The
algorithm jointly solves both the channel allocation and access scheduling
problems. We prove that the algorithm has an optimal logarithmic regret. Based
on the algorithm we provide a medium access control protocol which allows
distributed implementation of the algorithm in ad-hoc networks. The protocol
utilizes single-channel opportunistic carrier sensing to carry out a
low-complexity distributed auction in time and frequency. We also discuss
practical implementation issues such as bounded frame size and speed of
convergence. Computer simulations comparing the algorithm to state-of-the-art
distributed medium access control protocols show the significant advantage of
the proposed scheme.
