Issue RAIRO-Oper. Res. Volume 42, Number 4, October-December 2008 ALIO/EURO V Conference on Combinatorial Optimization Page(s) 501 - 514 DOI 10.1051/ro:2008026 Published online 04 April 2009

RAIRO-Oper. Res. 42 (2008) 501-514
DOI: 10.1051/ro:2008026

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

Sacha Varone¹ and Nicolas Zufferey<sup>2

1</sup>  Haute École de Gestion (HEG), Bâtiment F, Route de Drize 7, 1227 Carouge, Switzerland; sacha.varone@hesge.ch
²  Université Laval, Département Opérations et Systèmes de Décisions, Faculté des Sciences de l'Administration, Québec (QC), G1K 7P4, Canada; nicolas.zufferey@fsa.ulaval.ca

Received October 28, 2007. Accepted January 09, 2008. Published online 4 April 2009

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.

Mathematics Subject Classification. 65K10, 68T20, 90B80.

Key words: WLAN, channel assignment, coloring, tabu search.


© EDP Sciences, ROADEF, SMAI 2008

What is OpenURL?