An adaptive local-search algorithm for the channel-assignment problem (CAP)

The channel-assignment problem (CAP) for cellular radio networks is an NP-complete problem. Previous techniques for solving this problem have used graph-coloring algorithms, neural networks, simulated annealing, and pattern-based optimization procedures. We describe an efficient two-phase adaptive l...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on vehicular technology 1996-08, Vol.45 (3), p.459-466
Main Authors: Wei Wang, Rushforth, C.K.
Format: Article
Language:English
Subjects:
Applied sciences
Bandwidth
Cellular networks
Equipments and installations
Exact sciences and technology
Frequency
Land mobile radio cellular systems
Mobile radiocommunication systems
Neural networks
NP-complete problem
Radiocommunications
Simulated annealing
Symmetric matrices
Telecommunications
Telecommunications and information theory
Telephony
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The channel-assignment problem (CAP) for cellular radio networks is an NP-complete problem. Previous techniques for solving this problem have used graph-coloring algorithms, neural networks, simulated annealing, and pattern-based optimization procedures. We describe an efficient two-phase adaptive local-search algorithm for the channel-assignment problem. This algorithm has been applied to several existing benchmark problems with encouraging results. In many cases it outperforms the existing algorithms in the quality of the solution obtained. When used in conjunction with structured preprocessing, the algorithm can be applied to large networks. It is thus a practical tool for the planning of cellular radio networks.
ISSN:0018-9545
1939-9359
DOI:10.1109/25.533761