Interference pair-based distributed spectrum allocation in wireless mesh networks with frequency-agile radios

Spectrum allocation algorithms are able to improve the performance of wireless mesh networks by exploiting the frequency agility of modern radios, and several such algorithms have been proposed. However, their interference constraints are at a coarse-grained level, which results in a low spectrum efficiency. To achieve higher spectrum resource utilization, we use interference pairs as a finer granularity to model the interference constraints in wireless mesh networks, and derive a sufficient and necessary condition for interference-free spectrum allocation. Based on a set of rigorous models, we formulate spectrum allocation as an optimization problem and divide it into two subproblems, for which we propose a two-phase interference pair-based distributed spectrum allocation (IPDSA) algorithm. In IPDSA, a negotiation-based frequency hierarchy mechanism heuristically determines the relation between the center frequencies of links in each interference pair; and then a dual decomposition-based spectrum allocation algorithm converges to the optimal allocation of center frequencies and spectral widths of all links. Extensive simulation results show that IPDSA is able to significantly improve spectrum utilization and thus increase network utility and aggregate throughput, thanks to a high accuracy in modeling interference constraints.