On the Efficiency and Complexity of Distributed Spectrum Allocation

We study the efficiency and complexity of a distributed spectrum allocation algorithm using explicit user coordination. Users self-organize into coordination groups and adjust spectrum assignments in each local group to approximate an optimal assignment. Compared to the conventional topology-based optimizations, local coordination can significantly reduce the computation and communication overhead required to adapt to topology variations. We focus on analyzing the end-user performance in terms of spectrum efficiency and communication overhead. We derive a theoretical lower bound on the amount of spectrum each user can get from coordination, and a theoretical upper bound on the algorithm convergence time. We also perform experiments to verify our analytical results.