Open AccessA Variable Neighborhood Search Algorithm for Assigning Cells to Switches in Wireless Networks
Author(s) -
Matthieu André,
Gilles Pesant,
Samuel Pierre
Publication year - 2005
Publication title -
journal of computer sciences/journal of computer science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.161
H-Index - 28
eISSN - 1552-6607
pISSN - 1549-3636
DOI - 10.3844/jcssp.2005.175.181
Subject(s) - computer science , variable (mathematics) , variable neighborhood search , wireless , algorithm , computer network , wireless network , telecommunications , metaheuristic , mathematical analysis , mathematics
The problem of assigning cells to switches in wireless networks consists of minimizing the
total operating cost, that is, the cost of linking cells to switches and the cost of handover from one cell
to another, by taking into account factors such as network topology, switch capacity and traffic load in
the entire network. Such a problem is well known in the literature as NP-hard, such that exact
enumerative approaches are not suitable for solving real-size instances of this problem. Thus,
heuristics are recommended and have been used for finding good solutions in reasonable execution
times. Tabu Search (TS) is one of the best heuristics used to solve this problem. This research proposes
a hybrid heuristic approach for further improving the quality of solutions obtained from TS. This
approach applies TS in combination with variable neighborhood search, a recent metaheuristic that is
based on the principle of systematic change of neighborhood during the local search.. A key element in
the success of this approach is the use of several neighborhood structures that complement each other
well and that remain within the feasible region of the search space