Distributed Online Frequency Assignment in Cellular Networks

Jeannette Janssen, Danny Krizanc, Lata Narayanan, Sunil Shende

Research output: Contribution to journalArticle

47 Citations (Scopus)

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 multi-coloring 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 competilive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.

Original languageEnglish (US)
Pages (from-to)119-151
Number of pages33
JournalJournal of Algorithms
Volume36
Issue number2
DOIs
StatePublished - Jan 1 2000

Fingerprint

Frequency Assignment
Competitive Ratio
Online Algorithms
Cellular Networks
Vertex Model
Triangular Lattice
Weighted Graph
Assignment Problem
Vertex of a graph
Distributed Algorithms
Colouring
Subgraph
Coloring
Lower bound
Series
Framework
Class

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Cite this

Janssen, Jeannette ; Krizanc, Danny ; Narayanan, Lata ; Shende, Sunil. / Distributed Online Frequency Assignment in Cellular Networks. In: Journal of Algorithms. 2000 ; Vol. 36, No. 2. pp. 119-151.
@article{fc5e2758918840958b9d3597ed15d5d4,
title = "Distributed Online Frequency Assignment in Cellular Networks",
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 multi-coloring 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 competilive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.",
author = "Jeannette Janssen and Danny Krizanc and Lata Narayanan and Sunil Shende",
year = "2000",
month = "1",
day = "1",
doi = "10.1006/jagm.1999.1068",
language = "English (US)",
volume = "36",
pages = "119--151",
journal = "Journal of Algorithms",
issn = "0196-6774",
publisher = "Academic Press Inc.",
number = "2",

}

Distributed Online Frequency Assignment in Cellular Networks. / Janssen, Jeannette; Krizanc, Danny; Narayanan, Lata; Shende, Sunil.

In: Journal of Algorithms, Vol. 36, No. 2, 01.01.2000, p. 119-151.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Distributed Online Frequency Assignment in Cellular Networks

AU - Janssen, Jeannette

AU - Krizanc, Danny

AU - Narayanan, Lata

AU - Shende, Sunil

PY - 2000/1/1

Y1 - 2000/1/1

N2 - A cellular network is generally modeled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multi-coloring 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 competilive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.

AB - A cellular network is generally modeled as a subgraph of the triangular lattice. The distributed online frequency assignment problem can be abstracted as a multi-coloring 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 competilive ratios. In contrast, we show lower bounds on the competitive ratios of some natural classes of online algorithms.

UR - http://www.scopus.com/inward/record.url?scp=0346738663&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346738663&partnerID=8YFLogxK

U2 - 10.1006/jagm.1999.1068

DO - 10.1006/jagm.1999.1068

M3 - Article

VL - 36

SP - 119

EP - 151

JO - Journal of Algorithms

JF - Journal of Algorithms

SN - 0196-6774

IS - 2

ER -