Efficient On-Line Frequency Allocation and Call Control in Cellular Networks |
| |
Authors: | Caragiannis Kaklamanis and Papaioannou |
| |
Affiliation: | (1) Computer Technology Institute and Department of Computer Engineering and Informatics, University of Patras, 26500 Rio, Greece caragian@cti.gr, kakl@cti.gr, papaioan@cti.gr , GR |
| |
Abstract: | In this paper we consider communication issues arising in cellular (mobile) networks that utilize frequency division multiplexing
(FDM) technology. In such networks, many users within the same geographical region can communicate simultaneously with other
users of the network using distinct frequencies. The spectrum of available frequencies is limited; thus, efficient solutions
to the frequency-allocation and the call-control problems are essential. In the frequency-allocation problem, given users
that wish to communicate, the objective is to minimize the required spectrum of frequencies so that communication can be established
without signal interference. The objective of the call-control problem is, given a spectrum of available frequencies and users
that wish to communicate, to maximize the number of users served. We consider cellular, planar, and arbitrary network topologies.
In particular, we study the on-line version of both problems using competitive analysis. For frequency allocation in cellular
networks, we improve the best known competitive ratio upper bound of 3 achieved by the folklore Fixed Allocation algorithm, by presenting an almost tight competitive analysis for the greedy algorithm;
we prove that its competitive ratio is between 2.429 and 2.5 . For the call-control problem, we present the first randomized algorithm that beats the deterministic lower bound of 3 achieving a competitive ratio between 2.469 and 2.651 for cellular networks. Our analysis has interesting extensions to arbitrary networks. Also, using Yao's Minimax Principle,
we prove two lower bounds of 1.857 and 2.086 on the competitive ratio of randomized call-control algorithms for cellular and arbitrary planar networks, respectively. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|