File Download
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Conference Paper: Deterministic online call control in cellular networks and triangle-free cellular networks
  • Basic View
  • Metadata View
  • XML View
TitleDeterministic online call control in cellular networks and triangle-free cellular networks
 
AuthorsChan, JWT4
Chin, FYL2
Han, X1
Lam, KC2 3
Ting, HF2
Zhang, Y2
 
KeywordsAsymptotic performance
Competitive algorithms
Online call control
Frequency division multiplexing
Wireless telecommunication systems
 
Issue Date2010
 
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
CitationThe 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 222–233 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-14553-7_22
 
AbstractWireless Communication Networks based on Frequency Division Multiplexing (FDM in short) plays an important role in the field of communications, in which each request can be satisfied by assigning a frequency. To avoid interference, each assigned frequency must be different to the neighboring assigned frequencies. Since frequency is a scarce resource, the main problem in wireless networks is how to utilize the frequency as fully as possible. In this paper, we consider the call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests, in handling each request, we must immediately choose an available frequency to accept (or reject) it. The objective of call control problem is to maximize the number of accepted requests. We study the asymptotic performance, i.e., the number of requests in the sequence and the number of available frequencies are very large positive integers. In this paper, we give a 7/3-competitive algorithm for call control problem in cellular network, improving the previous 2.5-competitive result. Moreover, we investigate the triangle-free cellular network, propose a 9/4-competitive algorithm and prove that the lower bound of competitive ratio is at least 5/3. © 2010 Springer-Verlag Berlin Heidelberg.
 
DescriptionLNCS v. 6213 is the conference proceedings of FAW 2010
 
ISSN0302-9743
2013 SCImago Journal Rankings: 0.310
 
DOIhttp://dx.doi.org/10.1007/978-3-642-14553-7_22
 
ReferencesReferences in Scopus
 
DC FieldValue
dc.contributor.authorChan, JWT
 
dc.contributor.authorChin, FYL
 
dc.contributor.authorHan, X
 
dc.contributor.authorLam, KC
 
dc.contributor.authorTing, HF
 
dc.contributor.authorZhang, Y
 
dc.date.accessioned2010-12-23T08:39:23Z
 
dc.date.available2010-12-23T08:39:23Z
 
dc.date.issued2010
 
dc.description.abstractWireless Communication Networks based on Frequency Division Multiplexing (FDM in short) plays an important role in the field of communications, in which each request can be satisfied by assigning a frequency. To avoid interference, each assigned frequency must be different to the neighboring assigned frequencies. Since frequency is a scarce resource, the main problem in wireless networks is how to utilize the frequency as fully as possible. In this paper, we consider the call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests, in handling each request, we must immediately choose an available frequency to accept (or reject) it. The objective of call control problem is to maximize the number of accepted requests. We study the asymptotic performance, i.e., the number of requests in the sequence and the number of available frequencies are very large positive integers. In this paper, we give a 7/3-competitive algorithm for call control problem in cellular network, improving the previous 2.5-competitive result. Moreover, we investigate the triangle-free cellular network, propose a 9/4-competitive algorithm and prove that the lower bound of competitive ratio is at least 5/3. © 2010 Springer-Verlag Berlin Heidelberg.
 
dc.description.natureLink_to_subscribed_fulltext
 
dc.descriptionLNCS v. 6213 is the conference proceedings of FAW 2010
 
dc.description.otherThe 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 222–233
 
dc.identifier.citationThe 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 222–233 [How to Cite?]
DOI: http://dx.doi.org/10.1007/978-3-642-14553-7_22
 
dc.identifier.doihttp://dx.doi.org/10.1007/978-3-642-14553-7_22
 
dc.identifier.epage233
 
dc.identifier.hkuros178327
 
dc.identifier.issn0302-9743
2013 SCImago Journal Rankings: 0.310
 
dc.identifier.scopuseid_2-s2.0-77955872768
 
dc.identifier.spage222
 
dc.identifier.urihttp://hdl.handle.net/10722/129572
 
dc.identifier.volume6213 LNCS
 
dc.languageeng
 
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
 
dc.publisher.placeGermany
 
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
 
dc.relation.referencesReferences in Scopus
 
dc.rightsThe original publication is available at www.springerlink.com
 
dc.subjectAsymptotic performance
 
dc.subjectCompetitive algorithms
 
dc.subjectOnline call control
 
dc.subjectFrequency division multiplexing
 
dc.subjectWireless telecommunication systems
 
dc.titleDeterministic online call control in cellular networks and triangle-free cellular networks
 
dc.typeConference_Paper
 
<?xml encoding="utf-8" version="1.0"?>
<item><contributor.author>Chan, JWT</contributor.author>
<contributor.author>Chin, FYL</contributor.author>
<contributor.author>Han, X</contributor.author>
<contributor.author>Lam, KC</contributor.author>
<contributor.author>Ting, HF</contributor.author>
<contributor.author>Zhang, Y</contributor.author>
<date.accessioned>2010-12-23T08:39:23Z</date.accessioned>
<date.available>2010-12-23T08:39:23Z</date.available>
<date.issued>2010</date.issued>
<identifier.citation>The 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 222&#8211;233</identifier.citation>
<identifier.issn>0302-9743</identifier.issn>
<identifier.uri>http://hdl.handle.net/10722/129572</identifier.uri>
<description>LNCS v. 6213 is the conference proceedings of FAW 2010</description>
<description.abstract>Wireless Communication Networks based on Frequency Division Multiplexing (FDM in short) plays an important role in the field of communications, in which each request can be satisfied by assigning a frequency. To avoid interference, each assigned frequency must be different to the neighboring assigned frequencies. Since frequency is a scarce resource, the main problem in wireless networks is how to utilize the frequency as fully as possible. In this paper, we consider the call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests, in handling each request, we must immediately choose an available frequency to accept (or reject) it. The objective of call control problem is to maximize the number of accepted requests. We study the asymptotic performance, i.e., the number of requests in the sequence and the number of available frequencies are very large positive integers. In this paper, we give a 7/3-competitive algorithm for call control problem in cellular network, improving the previous 2.5-competitive result. Moreover, we investigate the triangle-free cellular network, propose a 9/4-competitive algorithm and prove that the lower bound of competitive ratio is at least 5/3. &#169; 2010 Springer-Verlag Berlin Heidelberg.</description.abstract>
<language>eng</language>
<publisher>Springer Verlag. The Journal&apos;s web site is located at http://springerlink.com/content/105633/</publisher>
<relation.ispartof>Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)</relation.ispartof>
<rights>The original publication is available at www.springerlink.com</rights>
<subject>Asymptotic performance</subject>
<subject>Competitive algorithms</subject>
<subject>Online call control</subject>
<subject>Frequency division multiplexing</subject>
<subject>Wireless telecommunication systems</subject>
<title>Deterministic online call control in cellular networks and triangle-free cellular networks</title>
<type>Conference_Paper</type>
<description.nature>Link_to_subscribed_fulltext</description.nature>
<identifier.doi>10.1007/978-3-642-14553-7_22</identifier.doi>
<identifier.scopus>eid_2-s2.0-77955872768</identifier.scopus>
<identifier.hkuros>178327</identifier.hkuros>
<relation.references>http://www.scopus.com/mlt/select.url?eid=2-s2.0-77955872768&amp;selection=ref&amp;src=s&amp;origin=recordpage</relation.references>
<identifier.volume>6213 LNCS</identifier.volume>
<identifier.spage>222</identifier.spage>
<identifier.epage>233</identifier.epage>
<publisher.place>Germany</publisher.place>
<description.other>The 4th International Frontiers of Algorithmics Workshop (FAW 2010), Wuhan, China, 11-13 August 2010. In Lecture Notes in Computer Science, 2010, v. 6213, p. 222&#8211;233</description.other>
</item>
Author Affiliations
  1. Dalian University of Technology
  2. The University of Hong Kong
  3. Zhejiang University
  4. Hong Kong Baptist University