Absolute and asymptotic bounds for online frequency allocation in cellular networks

Joseph W T CHAN, Francis Y.L. Chin, Deshi Ye, Yong Zhang

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

Given a cellular (mobile telephone) network, whose geographical coverage area is divided into hexagonal cells, phone calls are serviced by assigning frequencies to them so that no two calls emanating from the same or neighboring cells are assigned the same frequency. Assuming an online arrival of calls, the goal is to minimize the span of frequencies used to serve all of the calls. By first considering χ-colorable networks, which is a generalization of the (3-colorable) cellular networks, we present a (χ+1)/2-competitive online algorithm. This algorithm, when applied to cellular networks, is effectively a positive solution to the open problem posed in (Caragiannis et al. in Theory Comput. Syst. 35(5):521-543, 2002) Does a 2-competitive online algorithm exist for frequency allocation in cellular networks? We further prove a matching lower bound, which shows that our 2-competitive algorithm is optimal. We discover that an interesting phenomenon occurs for the online frequency allocation problem when the number of calls considered becomes large: previously-derived optimal bounds on competitive ratios no longer hold true. For cellular networks, we show a new asymptotic lower and upper bounds of 1.5 and 1.9126, respectively, which breaks through the optimal bound of 2 shown above.

Original languageEnglish
Pages (from-to)498-515
Number of pages18
JournalAlgorithmica
Volume58
Issue number2
DOIs
Publication statusPublished - Oct 2010

Scopus Subject Areas

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

User-Defined Keywords

  • Cellular networks
  • Competitive analysis
  • Frequency allocation
  • Multicoloring
  • Online algorithms

Fingerprint

Dive into the research topics of 'Absolute and asymptotic bounds for online frequency allocation in cellular networks'. Together they form a unique fingerprint.

Cite this