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

Joseph W T CHAN, Francis Y.L. Chin, Xin Han, Ka Cheong Lam, Hing Fung Ting, Yong Zhang

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


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.

Original languageEnglish
Title of host publicationFrontiers in Algorithmics - 4th International Workshop, FAW 2010, Proceedings
Number of pages12
Publication statusPublished - 2010
Event4th International Frontiers of Algorithmics Workshop, FAW 2010 - Wuhan, China
Duration: 11 Aug 201013 Aug 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6213 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference4th International Frontiers of Algorithmics Workshop, FAW 2010

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Deterministic online call control in cellular networks and triangle-free cellular networks'. Together they form a unique fingerprint.

Cite this