点击次数：

论文类型：期刊论文

发表时间：2012-01-15

发表刊物：INFORMATION PROCESSING LETTERS

收录刊物：SCIE、EI

卷号：112

期号：1-2

页面范围：21-25

ISSN号：0020-0190

关键字：On-line algorithms; Call control problem; Cellular networks

摘要：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. (C) 2011 Elsevier B.V. All rights reserved.