Distributed Online Frequency Assignment in Cellular Networks

Dr. Daniel Krizanc
School of Computer Science
Carleton University
Ottawa, Canada

Tuesday, February 23, 1999
11 a.m.
Fuller Labs 311

A cellular network is generally modelled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multicoloring problem on a weighted version of such a graph where the weight associated with a vertex represents the number of calls to be served at the vertex, which is assumed to change over time. In this talk, we describe a framework for studying distributed online frequency assignment in cellular networks. We present the first distributed online algorithms for this problem with proven bounds on their competitive ratios. We show a series of algorithms that use information about increasingly larger neighborhoods of the vertices, thereby achieving better competitive ratios. In contrast, we show lower bounds on the competitive ratio of some natural classes of online algorithms. Some of our algorithms are optimal for the classes of algorithms studied.

This is joint work with J. Janssen, L. Narayanan and S. Shende.

Host

Micha Hofri

Colloquium Coordinator

Carolina Ruiz

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT