Convergence of a quasistatic frequency allocation algorithm

Issue title: Wireless Networks

Article type: Research Article

Authors: Preneel, Bart^; | Walrand, Jean

Affiliations: Department of EECS, University of California, Berkeley, CA 94720, USA, E-mail: {preneel,wlr}@eecs.berkeley.edu

Note: [] Research supported in part by DIVA COMMUNICATIONS. The first author is a postdoctoral researcher, sponsored by the N.F.W.O. (National Science Foundation of Belgium).

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.

Keywords: Cellular radio, frequency allocation, frequency division multiple access, graph coloring

DOI: 10.3233/JHS-1996-5102

Journal: Journal of High Speed Networks, vol. 5, no. 1, pp. 3-22, 1996