EDP Sciences Journals List
Home Document
Subscriber Authentication Point
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 Varone1 and Nicolas Zufferey2

1  Haute École de Gestion (HEG), Bâtiment F, Route de Drize 7, 1227 Carouge, Switzerland; sacha.varone@hesge.ch
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; 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?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.
  • If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
  • You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
  • You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.