Distributed Approximation Algorithms for Spectrum Allocation in Wireless ad Hoc Networks

Spectrum allocation is a difficult and hot issue in wireless ad hoc networks. An efficient method of spectrum allocation is a key factor to improve quality of service and performance of wireless networks. In this paper, we consider the spectrum allocation problem which asks how to allocate the least number of spectrum blocks in a field to ensure the service on any random k locations simultaneously. Our solution to the spectrum allocation problem is the minimum k-Roman dominating set. We propose two distributed algorithms for the issue of spectrum allocation in wireless ad hoc networks. One is a distributed 6k-approximation algorithm for the spectrum allocation of satisfying any random k (k ≥ 2) locations in the class of unit ball graphs. The other one is a better distributed algorithm for finding a (1 + ε)-approximation for the spectrum allocation problem of serving any random two locations, in the class of growth-bounded graphs. We also describe the simulation results and analyze them.