Convergence of a quasistatic frequency allocation algorithm

Abstract

The paper proves the convergence of a quasistatic frequency allocation algorithm for a cellular network. The algorithm is distributed and asynchronous and is executed by the base stations at random epochs when they sense a conflict with other transmitters. We prove that the algorithm eventually finds an acceptable allocation of frequencies whenever one exists. We also derive bounds on the average number of steps required by the algorithm. We study methods for speeding up the convergence, and derive analytical expressious for the case where the base stations are located on a line. We present the results of computer simulations, which show a very fast convergence.