# Three tabu search methods for the MI-FAP applied to 802.11 networks

Sacha Varone; Nicolas Zufferey

RAIRO - Operations Research (2009)

- Volume: 42, Issue: 4, page 501-514
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topVarone, Sacha, and Zufferey, Nicolas. "Three tabu search methods for the MI-FAP applied to 802.11 networks." RAIRO - Operations Research 42.4 (2009): 501-514. <http://eudml.org/doc/105417>.

@article{Varone2009,

abstract = {
Wireless LAN using IEEE 802.11 networks are now widely deployed at
home by residential users or in hot spots by telecommunication
operators. A hot spot is a place where a set of access points (APs)
are located nearby each other and can serve many users. Since
perturbations can degrade the quality of the signal, a careful
channel assignment to each AP has to be done. Channel assignment of
APs at hot spots, and more generally setup configuration and
management, is still often done manually. In this paper, we consider
a modeling that enables optimization of channel assignment with
respect to the dynamic behavior of end-users. We prove our problem's
formulation to correspond to the Minimum Interference Frequency
Assignment Problem, and hence the problem to be NP-hard. We propose
and compare three different tabu search methods to solve the
problem of channel assignment in 802.11 WLAN networks. The first
one, called TabuObj, tackles the problem using directly the
objective function associated with the model. The second one, called
TabuApproxObj, uses a simplified and approximate objective
function in order to visit more solutions during the same amount of
time, i.e. to be quicker than TabuObj. The third one, called
TabuLevel, is even more quicker and is based on the following
philosophy: under time constraints, it could be judicious to explore
very quickly lots of solutions, rather than spending much
computation time for the evaluation of each solution, and hence only
considering a few solutions. Those three methods are then compared
based on time constraints and on the quality of their solutions.
},

author = {Varone, Sacha, Zufferey, Nicolas},

journal = {RAIRO - Operations Research},

keywords = {WLAN; channel assignment; coloring; tabu search.; tabu search},

language = {eng},

month = {4},

number = {4},

pages = {501-514},

publisher = {EDP Sciences},

title = {Three tabu search methods for the MI-FAP applied to 802.11 networks},

url = {http://eudml.org/doc/105417},

volume = {42},

year = {2009},

}

TY - JOUR

AU - Varone, Sacha

AU - Zufferey, Nicolas

TI - Three tabu search methods for the MI-FAP applied to 802.11 networks

JO - RAIRO - Operations Research

DA - 2009/4//

PB - EDP Sciences

VL - 42

IS - 4

SP - 501

EP - 514

AB -
Wireless LAN using IEEE 802.11 networks are now widely deployed at
home by residential users or in hot spots by telecommunication
operators. A hot spot is a place where a set of access points (APs)
are located nearby each other and can serve many users. Since
perturbations can degrade the quality of the signal, a careful
channel assignment to each AP has to be done. Channel assignment of
APs at hot spots, and more generally setup configuration and
management, is still often done manually. In this paper, we consider
a modeling that enables optimization of channel assignment with
respect to the dynamic behavior of end-users. We prove our problem's
formulation to correspond to the Minimum Interference Frequency
Assignment Problem, and hence the problem to be NP-hard. We propose
and compare three different tabu search methods to solve the
problem of channel assignment in 802.11 WLAN networks. The first
one, called TabuObj, tackles the problem using directly the
objective function associated with the model. The second one, called
TabuApproxObj, uses a simplified and approximate objective
function in order to visit more solutions during the same amount of
time, i.e. to be quicker than TabuObj. The third one, called
TabuLevel, is even more quicker and is based on the following
philosophy: under time constraints, it could be judicious to explore
very quickly lots of solutions, rather than spending much
computation time for the evaluation of each solution, and hence only
considering a few solutions. Those three methods are then compared
based on time constraints and on the quality of their solutions.

LA - eng

KW - WLAN; channel assignment; coloring; tabu search.; tabu search

UR - http://eudml.org/doc/105417

ER -

## References

top- K.I. Aardal, S.P.M. van Hoesel, A.M.C.A. Koster, C. Mannino, and A. Sassano, Models and solution techniques for frequency assignment problems. A Quaterly Journal of Operations Research1 (2003) 261–317. Zbl1042.90049
- R. Battiti and G. Tecchiolli, The reactive tabu search. ORSA J. Comput.6 (1994) 126–140. Zbl0807.90094
- I. Bloechliger and N. Zufferey, A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res.35 (2008) 960–975. Zbl1278.90327
- A. Eisenblätter, M. Grötschel, and A.M.C.A. Koster, Frequency assignment and ramifications of coloring. Discussiones Mathematicae Graph Theory22 (2002) 51–88. Zbl1055.05147
- P. Galinier and J.-K. Hao, Hybrid Evolutionary Algorithms for Graph Coloring. J. Comb. Optim.3 (1999) 379–397. Zbl0958.90071
- F. Glover, Tabu search – part I. ORSA J. Comput.1 (1989) 190–205. Zbl0753.90054
- F. Glover, Tabu search – part II. ORSA J. Comput.2 (1990) 4–32. Zbl0771.90084
- F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, Boston (1997).
- W.K. Hale, Frequency assignment: Theory and applications, in Proceedings of the IEEE68 (1980) 1497–1514.
- P. Hansen, The steepest ascent mildest descent heuristic for combinatorial programming, in Proc. of Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986).
- Jin-Kao Hao, Raphaël Dorne, and Philippe Galinier, Tabu search for frequency assignment in mobile radio networks. J. Heuristics4(1) (1998) 47–62. Zbl1071.90578
- A. Hertz and D. de Werra, Using tabu search techniques for graph coloring. Computing39 (1987) 345–351. Zbl0626.68051
- L. Hui and N.K. Shankaranarayanan, A distributed channel allocation technique for throughput improvement in a dense wlan environment, in Proc. of 2004 IEEE International Conference on Acoustics, Speech, and Signal Processing5 (2005) V–345–8.
- K.K. Leung and B.J. Kim, Frequency assignment for IEEE 802.11 wireless networks, in Proc. of 58th Vehicular Technology Conference (2003) 1422–1426.
- Y. Ming, N. Karmarkar, and A. Malvankar, A dynamic radio channel allocation scheme for wireless lans, in IEEE/Sarnoff Symposium on Advances in Wired and Wireless Communication (2005) 17–20.
- R. Montemanni, J.N.J. Moon, and D.H Smith, An improved tabu search algorithm for the fixed-spectrum frequency-assignment problem. IEEE Trans. Vehicular Technology52 (2003) 891–901.
- P802.11, IEEE Standard for Wireless LAN-Medium Access Control and Physical Layer Specification, 1999. . URIhttp://ieee802.org/11/
- D. Rossier, S. Varone, J.-F. Wagen, F. Gamba, V. Inguscio, and E. Marchon, System für die dynamische Zuweisung von Trägerfrequenzen zu Zugriffspunkten eines lokalen Funknetzes. Patent 03405356.1, May (2003).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.