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 , tackles the problem using directly the objective function associated with the model. The second one, called , 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 . The third one, called , 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.
Mots clés : WLAN, channel assignment, coloring, tabu search
@article{RO_2008__42_4_501_0,
author = {Varone, Sacha and Zufferey, Nicolas},
title = {Three tabu search methods for the {MI-FAP} applied to 802.11 networks},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {501--514},
publisher = {EDP-Sciences},
volume = {42},
number = {4},
year = {2008},
doi = {10.1051/ro:2008026},
mrnumber = {2469109},
zbl = {1205.68390},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ro:2008026/}
}
TY - JOUR AU - Varone, Sacha AU - Zufferey, Nicolas TI - Three tabu search methods for the MI-FAP applied to 802.11 networks JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2008 SP - 501 EP - 514 VL - 42 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ro:2008026/ DO - 10.1051/ro:2008026 LA - en ID - RO_2008__42_4_501_0 ER -
%0 Journal Article %A Varone, Sacha %A Zufferey, Nicolas %T Three tabu search methods for the MI-FAP applied to 802.11 networks %J RAIRO - Operations Research - Recherche Opérationnelle %D 2008 %P 501-514 %V 42 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ro:2008026/ %R 10.1051/ro:2008026 %G en %F RO_2008__42_4_501_0
Varone, Sacha; Zufferey, Nicolas. Three tabu search methods for the MI-FAP applied to 802.11 networks. RAIRO - Operations Research - Recherche Opérationnelle, Tome 42 (2008) no. 4, pp. 501-514. doi : 10.1051/ro:2008026. http://www.numdam.org/articles/10.1051/ro:2008026/
[1] , , , , and , Models and solution techniques for frequency assignment problems. A Quaterly Journal of Operations Research 1 (2003) 261-317. | MR | Zbl
[2] and , The reactive tabu search. ORSA J. Comput. 6 (1994) 126-140. | Zbl
[3] and , A graph coloring heuristic using partial solutions and a reactive tabu scheme. Comput. Oper. Res. 35 (2008) 960-975. | Zbl
[4] , , and , Frequency assignment and ramifications of coloring. Discussiones Mathematicae Graph Theory 22 (2002) 51-88. | MR | Zbl
[5] and , Hybrid Evolutionary Algorithms for Graph Coloring. J. Comb. Optim. 3 (1999) 379-397. | MR | Zbl
[6] , Tabu search - part I. ORSA J. Comput. 1 (1989) 190-205. | Zbl
[7] , Tabu search - part II. ORSA J. Comput. 2 (1990) 4-32. | Zbl
[8] and , Tabu Search. Kluwer Academic Publishers, Boston (1997). | MR | Zbl
[9] , Frequency assignment: Theory and applications, in Proceedings of the IEEE 68 (1980) 1497-1514.
[10] , The steepest ascent mildest descent heuristic for combinatorial programming, in Proc. of Congress on Numerical Methods in Combinatorial Optimization, Capri, Italy (1986).
[11] , , and , Tabu search for frequency assignment in mobile radio networks. J. Heuristics 4(1) (1998) 47-62. | Zbl
[12] and , Using tabu search techniques for graph coloring. Computing 39 (1987) 345-351. | MR | Zbl
[13] and , 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.
[14] and , Frequency assignment for IEEE 802.11 wireless networks, in Proc. of 58th Vehicular Technology Conference (2003) 1422-1426.
[15] , , and , A dynamic radio channel allocation scheme for wireless lans, in IEEE/Sarnoff Symposium on Advances in Wired and Wireless Communication (2005) 17-20.
[16] , , and , An improved tabu search algorithm for the fixed-spectrum frequency-assignment problem. IEEE Trans. Vehicular Technology 52 (2003) 891-901.
[17] P802.11, IEEE Standard for Wireless LAN-Medium Access Control and Physical Layer Specification, 1999. http://ieee802.org/11/.
[18] , , , , , and , System für die dynamische Zuweisung von Trägerfrequenzen zu Zugriffspunkten eines lokalen Funknetzes. Patent 03405356.1, May (2003).
Cité par Sources :
