Article: Absolute and asymptotic bounds for online frequency allocation in cellular networks

File Download Links for fulltext
(May Require Subscription)
Supplementary
  • Basic View
  • Metadata View
  • XML View
TitleAbsolute and asymptotic bounds for online frequency allocation in cellular networks
AuthorsChan, JWT1
Chin, FYL2
Ye, D3
Zhang, Y2
KeywordsCellular networks
Competitive analysis
Frequency allocation
Multicoloring
Online algorithms
Issue Date2010
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
CitationAlgorithmica (New York), 2010, v. 58 n. 2, p. 498-515 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-009-9279-2
AbstractGiven 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. © 2009 Springer Science+Business Media, LLC.
ISSN0178-4617
2011 Impact Factor: 0.604
2011 SCImago Journal Rankings: 0.042
DOIhttp://dx.doi.org/10.1007/s00453-009-9279-2
ISI Accession Number IDWOS:000279681700013
Funding AgencyGrant Number
Hong Kong RGCHKU 7113/07E
NSFC10601048
National Natural Science Fund60496321
Funding Information:

F.Y.L. Chin was supported in parts by Hong Kong RGC Research Grant HKU 7113/07E. D. Ye was supported in parts by grant NSFC (10601048). Y. Zhang was supported in parts by National Natural Science Fund (grant no. 60496321).

ReferencesReferences in Scopus
DC Field
Value
dc.contributor.authorChan, JWT
dc.contributor.authorChin, FYL
dc.contributor.authorYe, D
dc.contributor.authorZhang, Y
dc.date.accessioned2010-12-23T08:45:07Z
dc.date.available2010-12-23T08:45:07Z
dc.date.issued2010
dc.description.abstractGiven 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. © 2009 Springer Science+Business Media, LLC.
dc.description.natureLink_to_subscribed_fulltext
dc.identifier.citationAlgorithmica (New York), 2010, v. 58 n. 2, p. 498-515 [How to Cite?]
DOI: http://dx.doi.org/10.1007/s00453-009-9279-2
dc.identifier.citeulike3989277
dc.identifier.doihttp://dx.doi.org/10.1007/s00453-009-9279-2
dc.identifier.epage515
dc.identifier.hkuros178318
dc.identifier.isiWOS:000279681700013
Funding AgencyGrant Number
Hong Kong RGCHKU 7113/07E
NSFC10601048
National Natural Science Fund60496321
Funding Information:

F.Y.L. Chin was supported in parts by Hong Kong RGC Research Grant HKU 7113/07E. D. Ye was supported in parts by grant NSFC (10601048). Y. Zhang was supported in parts by National Natural Science Fund (grant no. 60496321).

dc.identifier.issn0178-4617
2011 Impact Factor: 0.604
2011 SCImago Journal Rankings: 0.042
dc.identifier.issue2
dc.identifier.openurl
dc.identifier.scopuseid_2-s2.0-77955663788
dc.identifier.spage498
dc.identifier.urihttp://hdl.handle.net/10722/129982
dc.identifier.volume58
dc.languageeng
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
dc.publisher.placeUnited States
dc.relation.ispartofAlgorithmica (New York)
dc.relation.referencesReferences in Scopus
dc.rightsThe original publication is available at www.springerlink.com
dc.subjectCellular networks
dc.subjectCompetitive analysis
dc.subjectFrequency allocation
dc.subjectMulticoloring
dc.subjectOnline algorithms
dc.titleAbsolute and asymptotic bounds for online frequency allocation in cellular networks
dc.typeArticle
Author Affiliations
  1. King's College London
  2. The University of Hong Kong
  3. Zhejiang University