Optimus: SINR-Driven Spectrum Distribution via Constraint Transformation

How to distribute radio spectrum across network nodes is a critical problem in spectrum auctions and management. In this paper, we consider the problem of distributing spectrum using SINR-driven physical interference models. We propose Optimus, a new line of approximation algorithms that perform within a constant distance of min {2^α + 1, 10} from the optimum in terms of spectrum usage efficiency, where α ≥ 2 is the pathloss exponent. Different from conventional greedy solutions, Optimus applies a global optimization mechanism that transforms the spatial interference constraints into a set of linear constraints, reducing the original optimization into a linear/convex/separableprogramming problem. While linearization techniques have been applied in prior works, Optimus makes a new and important contribution by deriving a highly efficient constraint transformation applicable to general network configurations. Experiments using real network measurements and sophisticated propagation models show that Optimus outperforms existing solutions by 20-50% in spectrum utilization and is within 20% gap from the optimum. Optimus supports a wide variety of objective functions, and is applicable to many spectrum-driven applications such as spectrum auctions and spectrum admission control.