Frequency Assignment for Cellular Mobile
Systems Using Constraint Satisfaction Techniques
Makoto Yokoo, Katsutoshi Hirayama,
EEE Annual Vehicular Technology Conference
(VTC2000-Spring), 2000.
This paper presents a new algorithm for solving frequency assignment
problems in cellular mobile systems using constraint satisfaction
techniques.
The characteristics of this algorithm are as follows:
1) instead of representing each call in a cell (a unit area in providing
communication services) as a variable,
we represent a cell (which has multiple calls) as a variable that has a very large
domain, and determine a variable value step by step,
2) a powerful cell-ordering heuristic is introduced,
3) a branch-and-bound search that incorporates forward-checking is
performed,
and 4) the limited discrepancy search is introduced to improve the chance of
finding a solution in a limited amount of search.
Experimental evaluations using standard
benchmark problems show
that this algorithm can find optimal or semi-optimal solutions for
these problems, and most of the obtained solutions are better than or
equivalent to those of existing methods using simulated annealing,
tabu search, or neural networks.
These results show that
state-of-the-art constraint satisfaction/optimization techniques are capable of
solving realistic application problems
when equipped with an appropriate problem
representation and heuristics.