TY - JOUR

T1 - Online call control in cellular networks revisited

AU - Zhang, Yong

AU - Chin, Francis Y.L.

AU - Ting, Hing Fung

AU - CHAN, Joseph W T

AU - Han, Xin

AU - Lam, Ka Cheong

N1 - Funding Information:
ence, Hebei University, China. E-mail addresses: yzhang@cs.hku.hk (Y. Zhang), chin@cs.hku.hk (F.Y.L. Chin), hfting@cs.hku.hk (H.-F. Ting), cswtchan@gmail.com (J.W.-T. Chan), hanxin.mail@gmail.com (X. Han), pandaman@163.com (K.-C. Lam). 1 Research supported by NSFC (11171086). 2 Research supported by HK RGC grant HKU-7117/09E. 3 Research supported by HK RGC grant HKU-7171/08E. 4 Research supported by NSFC (11101065).

PY - 2012/1/15

Y1 - 2012/1/15

N2 - Wireless communication networks based on frequency division multiplexing (FDM in short) play 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 from the neighboring assigned frequencies. Since frequencies are scarce resources, the main problem in wireless networks is how to fully utilize the given bandwidth of frequencies. In this paper, we consider the online call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests arriving over time, each request must be either satisfied immediately after its arrival by assigning an available frequency, or rejected. The objective of the call control problem is to maximize the number of accepted requests. We study the asymptotic performance of this problem, i.e., the number of requests in the sequence and the bandwidth of frequencies are very large. In this paper, we give a 7/3-competitive algorithm, say CACO, for the call control problem in cellular networks, improving the previous 2.5-competitive result, and show that CACO is best possible among a class of HYBRID algorithms.

AB - Wireless communication networks based on frequency division multiplexing (FDM in short) play 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 from the neighboring assigned frequencies. Since frequencies are scarce resources, the main problem in wireless networks is how to fully utilize the given bandwidth of frequencies. In this paper, we consider the online call control problem. Given a fixed bandwidth of frequencies and a sequence of communication requests arriving over time, each request must be either satisfied immediately after its arrival by assigning an available frequency, or rejected. The objective of the call control problem is to maximize the number of accepted requests. We study the asymptotic performance of this problem, i.e., the number of requests in the sequence and the bandwidth of frequencies are very large. In this paper, we give a 7/3-competitive algorithm, say CACO, for the call control problem in cellular networks, improving the previous 2.5-competitive result, and show that CACO is best possible among a class of HYBRID algorithms.

KW - Call control problem

KW - Cellular networks

KW - On-line algorithms

UR - http://www.scopus.com/inward/record.url?scp=80054052545&partnerID=8YFLogxK

U2 - 10.1016/j.ipl.2011.10.005

DO - 10.1016/j.ipl.2011.10.005

M3 - Article

AN - SCOPUS:80054052545

VL - 112

SP - 21

EP - 25

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 1-2

ER -