Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-04T18:44:37.519Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  04 April 2009

Sacha Varone  and
Nicolas Zufferey
Sacha Varone
Affiliation:
Haute École de Gestion (HEG), Bâtiment F, Route de Drize 7, 1227 Carouge, Switzerland; [email protected]
Nicolas Zufferey
Affiliation:
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 protected]
Get access

Abstract

Wireless LAN using IEEE 802.11 networks are now widely deployed athome by residential users or in hot spots by telecommunicationoperators. A hot spot is a place where a set of access points (APs)are located nearby each other and can serve many users. Sinceperturbations can degrade the quality of the signal, a carefulchannel assignment to each AP has to be done. Channel assignment ofAPs at hot spots, and more generally setup configuration andmanagement, is still often done manually. In this paper, we considera modeling that enables optimization of channel assignment withrespect to the dynamic behavior of end-users. We prove our problem'sformulation to correspond to the Minimum Interference FrequencyAssignment Problem, and hence the problem to be NP-hard. We proposeand compare three different tabu search methods to solve theproblem of channel assignment in 802.11 WLAN networks. The firstone, called TabuObj, tackles the problem using directly theobjective function associated with the model. The second one, calledTabuApproxObj, uses a simplified and approximate objectivefunction in order to visit more solutions during the same amount oftime, i.e. to be quicker than TabuObj. The third one, calledTabuLevel, is even more quicker and is based on the followingphilosophy: under time constraints, it could be judicious to explorevery quickly lots of solutions, rather than spending muchcomputation time for the evaluation of each solution, and hence onlyconsidering a few solutions. Those three methods are then comparedbased on time constraints and on the quality of their solutions.

Keywords

WLANchannel assignmentcoloringtabu search.
Type
Research Article
Information
RAIRO - Operations Research , Volume 42 , Issue 4: ALIO/EURO V Conference on Combinatorial Optimization , October 2008 , pp. 501 - 514
Copyright
© EDP Sciences, ROADEF, SMAI, 2008

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., and Sassano, A., Models and solution techniques for frequency assignment problems. A Quaterly Journal of Operations Research 1 (2003) 261–317.
Battiti, R. and Tecchiolli, G., The reactive tabu search. ORSA J. Comput. 6 (1994) 126–140. CrossRef
Bloechliger, I. and Zufferey, N., A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35 (2008) 960–975.
Eisenblätter, A., Grötschel, M., and Koster, A.M.C.A., Frequency assignment and ramifications of coloring. Discussiones Mathematicae Graph Theory 22 (2002) 51–88.
Galinier, P. and Hao, J.-K., Hybrid Evolutionary Algorithms for Graph Coloring. J. Comb. Optim. 3 (1999) 379–397. CrossRef
Glover, F., Tabu search – part I. ORSA J. Comput. 1 (1989) 190–205. CrossRef
Glover, F., Tabu search – part II. ORSA J. Comput. 2 (1990) 4–32. CrossRef
F. Glover and M. Laguna, Tabu Search. Kluwer Academic Publishers, Boston (1997).
W.K. Hale, Frequency assignment: Theory and applications, in Proceedings of the IEEE 68 (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. Heuristics 4(1) (1998) 47–62.
Hertz, A. and de Werra, D., Using tabu search techniques for graph coloring. Computing 39 (1987) 345–351. CrossRef
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 Processing 5 (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.
Montemanni, R., Moon, J.N.J., and Smith, D.H, An improved tabu search algorithm for the fixed-spectrum frequency-assignment problem. IEEE Trans. Vehicular Technology 52 (2003) 891–901. CrossRef
P802.11, IEEE Standard for Wireless LAN-Medium Access Control and Physical Layer Specification, 1999. http://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).