点击次数：

论文类型：期刊论文

发表时间：2010-06-28

发表刊物：THEORETICAL COMPUTER SCIENCE

收录刊物：SCIE、EI、Scopus

卷号：411

期号：31-33

页面范围：2871-2877

ISSN号：0304-3975

关键字：Call control; Cellular network; Competitive ratio

摘要：We study an on-line call control problem in cellular networks that are based on the Frequency Division Multiplexing (FDM) technology. In such networks, interference may occur when the same frequency is assigned to two different calls emanating from the same cell or its neighboring cells. The number of frequencies supporting the networks is limited. The goal is to maximize the number of calls served without causing any interference. We focus on the case that the number of frequencies is sufficiently large and the calls stay forever. We give a deterministic on-line algorithm with asymptotic competitive ratio of 2.5 and show a general lower bound of 2. For the special case of linear cellular networks, we achieve a best possible deterministic on-line algorithm with asymptotic competitive ratio of 3/2. (C) 2010 Elsevier B.V. All rights reserved.