Volume 42, Number 4, October-December 2008ALIO/EURO V Conference on Combinatorial Optimization
|Page(s)||501 - 514|
|Published online||04 April 2009|
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; firstname.lastname@example.org
2 Université Laval, Département Opérations et Systèmes de Décisions, Faculté des Sciences de l'Administration, Québec (QC), G1K 7P4, Canada; email@example.com
Accepted: 9 January 2008
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.