File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Deterministic online call control in cellular networks and triangle-free cellular networks

TitleDeterministic online call control in cellular networks and triangle-free cellular networks
Authors
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/
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–233 How to Cite?
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
Persistent Identifierhttp://hdl.handle.net/10722/129572
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, JWTen_HK
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorHan, Xen_HK
dc.contributor.authorLam, KCen_HK
dc.contributor.authorTing, HFen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-12-23T08:39:23Z-
dc.date.available2010-12-23T08:39:23Z-
dc.date.issued2010en_HK
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–233en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/129572-
dc.descriptionLNCS v. 6213 is the conference proceedings of FAW 2010-
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.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
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 networksen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HF:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.identifier.authorityTing, HF=rp00177en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-14553-7_22en_HK
dc.identifier.scopuseid_2-s2.0-77955872768en_HK
dc.identifier.hkuros178327en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77955872768&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6213 LNCSen_HK
dc.identifier.spage222en_HK
dc.identifier.epage233en_HK
dc.publisher.placeGermanyen_HK
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.scopusauthoridChan, JWT=16021445200en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridHan, X=34872071800en_HK
dc.identifier.scopusauthoridLam, KC=36439880500en_HK
dc.identifier.scopusauthoridTing, HF=7005654198en_HK
dc.identifier.scopusauthoridZhang, Y=7601329213en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats