Distributed Online Frequency Assignment in Cellular Networks |
| |
Authors: | Jeannette Janssen Danny Krizanc Lata Narayanan Sunil Shende |
| |
Affiliation: | a Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 3J5, Canada;b School of Computer Science, Carleton University, Ottawa, ON, Canada;c Department of Computer Science, Concordia University, Montreal, Quebec, Canada, H3G 1M8;d Department of Computer Science, Rutgers University, Camden, New Jersey, 08102 |
| |
Abstract: | A cellular network is generally modeled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multicoloring problem on a weighted graph, where the weight vector associated with the vertices models the number of calls to be served at the vertices and is assumed to change over time. In this paper, we develop 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 at each vertex information about increasingly larger neighborhoods of the vertex, and that achieve better competitive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|