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

¹ 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: 28 October 2007
Accepted: 9 January 2008

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.