Static frequency assignment in cellular networks

L. Narayanan, Sunil Shende

Research output: Contribution to journalArticle

55 Scopus citations

Abstract

A cellular network is generally modeled as a subgraph of the triangular lattice. In the static frequency assignment problem, each vertex of the graph is a base station in the network, and has associated with it an integer weight that represents the number of calls that must be served at the vertex by assigning distinct frequencies per call. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. The static frequency assignment problem can be abstracted as a graph multicoloring problem. We describe an efficient algorithm to multicolor optimally any weighted even or odd length cycle representing a cellular network. This result is further extended to any outerplanar graph. For the problem of multicoloring an arbitrary connected subgraph of the triangular lattice, we demonstrate an approximation algorithm which guarantees that no more than 4/3 times the minimum number of required colors are used. Further, we show that this algorithm can be implemented in a distributed manner, where each station needs to have knowledge only of the weights at a small neighborhood.

Original languageEnglish (US)
Pages (from-to)396-409
Number of pages14
JournalAlgorithmica (New York)
Volume29
Issue number3
DOIs
StatePublished - Jan 1 2001

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Static frequency assignment in cellular networks'. Together they form a unique fingerprint.

Cite this