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

Title | Deterministic online call control in cellular networks and triangle-free cellular networks |
---|---|

Authors | Chan, JWT4 Chin, FYL2 Han, X1 Lam, KC2 3 Ting, HF2 Zhang, Y2 |

Keywords | Asymptotic performance Competitive algorithms Online call control Frequency division multiplexing Wireless telecommunication systems |

Issue Date | 2010 |

Publisher | Springer 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?] DOI: http://dx.doi.org/10.1007/978-3-642-14553-7_22 |

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. © 2010 Springer-Verlag Berlin Heidelberg. |

Description | LNCS v. 6213 is the conference proceedings of FAW 2010 |

ISSN | 0302-9743 2013 SCImago Journal Rankings: 0.310 |

DOI | http://dx.doi.org/10.1007/978-3-642-14553-7_22 |

References | References in Scopus |

DC Field | Value |
---|---|

dc.contributor.author | Chan, JWT |

dc.contributor.author | Chin, FYL |

dc.contributor.author | Han, X |

dc.contributor.author | Lam, KC |

dc.contributor.author | Ting, HF |

dc.contributor.author | Zhang, Y |

dc.date.accessioned | 2010-12-23T08:39:23Z |

dc.date.available | 2010-12-23T08:39:23Z |

dc.date.issued | 2010 |

dc.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. © 2010 Springer-Verlag Berlin Heidelberg. |

dc.description.nature | link_to_subscribed_fulltext |

dc.description | LNCS v. 6213 is the conference proceedings of FAW 2010 |

dc.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–233 |

dc.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–233 [How to Cite?] DOI: http://dx.doi.org/10.1007/978-3-642-14553-7_22 |

dc.identifier.doi | http://dx.doi.org/10.1007/978-3-642-14553-7_22 |

dc.identifier.epage | 233 |

dc.identifier.hkuros | 178327 |

dc.identifier.issn | 0302-9743 2013 SCImago Journal Rankings: 0.310 |

dc.identifier.scopus | eid_2-s2.0-77955872768 |

dc.identifier.spage | 222 |

dc.identifier.uri | http://hdl.handle.net/10722/129572 |

dc.identifier.volume | 6213 LNCS |

dc.language | eng |

dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ |

dc.publisher.place | Germany |

dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

dc.relation.references | References in Scopus |

dc.rights | The original publication is available at www.springerlink.com |

dc.subject | Asymptotic performance |

dc.subject | Competitive algorithms |

dc.subject | Online call control |

dc.subject | Frequency division multiplexing |

dc.subject | Wireless telecommunication systems |

dc.title | Deterministic online call control in cellular networks and triangle-free cellular networks |

dc.type | Conference_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–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. © 2010 Springer-Verlag Berlin Heidelberg.</description.abstract> <language>eng</language> <publisher>Springer Verlag. The Journal'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&selection=ref&src=s&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–233</description.other> </item>

Author Affiliations

- Dalian University of Technology
- The University of Hong Kong
- Zhejiang University
- Hong Kong Baptist University