R´epublique Alg´erienne D´emocratique et Populaire Minist`ere de L’Enseignement Sup´erieur et de la Recherche Scientifique Universit´e M’hamed Bougara Boumerdes Facult´e des Sciences D´epartement de Math´ematiques Projet de fin d´´etude En vue de L´Obtention Du Diploˆme De Master En Recherche Op´erationnelle Option :Recherche Op´erationnelle Mod´elisation et Aide `a la D´ecision Par :REBAH Asma MEGHOUCHE Selma (cid:97)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:98)(cid:99) M´ethodologie de la gestion d´un spectre et (cid:100) (cid:101) (cid:100) l´impl´ementation des points d´acc`es (AP) dans(cid:101) (cid:100) (cid:101) (cid:100) un r´eseau -Alg´erie T´el´ecom Boumerdes (cid:101) (cid:100) (cid:101) (cid:102)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:103)(cid:104) Soutenue a` l´UMBB,le 20/06/2016,devant le jury compos´e de : Mme FASS M.A.A Encadreur l’UMBB - Boumerdes. Mr MAHLOU Encadreur DOT - Boumerdes Mme LARBI M.A.A Pr´esidente l’UMBB - Boumerdes. Mme HARFOUCHE M.A.A Examinatrice l’UMBB - Boumerdes. Ann´ee Universitaire 2015−2016 Remerciment Nous tenons avant tout `a remercier DIEU tout puissant de nous avoir donn´e la force et la volont´e pour achever ce modeste travail. Nous tenons aussi `a exprimer notre gratitude `a madame FASS notre promotrice pour tout les conseils, les suivis avis´es ainsi pour son prestigieux aide, sa disponibilit´e et avis ´eclair´es. Nos plus vifs remerciements vont ´egalement `a notre encadreur Monsieur MAHLOU.R pour avoir accepter de co-encadrer ce th`eme de recherche , et pour son aide et ses nombreux conseils scientifiques . Nos gratitudes vont aussi aux membres du jury : Nousadressonsdemˆemenoschaleureuxremerciements`atoutlestaff d´Alg´erie T´el´ecom sans oubli´e Monsieur kARA Ali , qui n´ont pas h´esit´e `a nous aider pour la r´ealisation de ce m´emoire. Sans oublier, ´evidemment les enseignants du d´epartement Math´ematique de la Fa- cult´e des Sciences de Boumerdes pour tous les cours dispens´es tout au long de notre parcours universitaire. Enfin, notre reconnaissance va `a tout ceux qui ont contribu´es de pr´es ou de loin `a l´´elaboration de ce travail ainsi qu´`a ceux qui nous ont encourag´e sans relˆache au cours des p´eriodes difficiles de ce projet. i D´edicaces Je d´edie ce modeste travail`a mes tr`es chers parents qui n´ont pas cess´e de m´encourager durant toutes mes ´etudes que dieu me les garde . Je le d´edie ´egalement `a mes chers fr`eres et mes chers sœurs ainsi qu’`a toute la famille MEGHOUCHE , du plus vieux jusqu’au plus jeune. Je d´edie ce modeste travail `a ma tr`es ch`ere amie et binoˆme Asma et sa famille. Je le d´edie ´egalement `a toutes mes amies ici et ailleurs . Je tiens aussi `a le d´edier `a tous ceux qui nous ont apport´e leurs soutien pour ´elaborer ce travail notamment Mr.kara ali mourad . Enfin, je le d´edie chaleureusement `a tout ceux qui me connaissent que j’aime et qui m’aiment. Selma ii D´edicaces Jed´ediecemodestetravail`amestr`eschers parents quin´ontpascess´edem´encourager durant toutes mes ´etudes que dieu me les garde . Je le d´edie ´egalement `a mes chers fr`eres et mes chers sœurs ainsi qu’`a toute la famille REBAH , du plus vieux jusqu’au plus jeune. Je d´edie ce modeste travail `a ma tr`es ch`ere amie et binoˆme Selma et sa famille. Je le d´edie ´egalement `a tous mes amis(e) avec lesquels j’ai partag´e mes moments de joie et de bon heur,surtout ma ch´erie Amina. Je tiens aussi `a le d´edier `a tous ceux qui nous ont apport´e leurs soutien pour ´elaborer ce travail. Enfin, je le d´edie chaleureusement `a tout ceux qui me connaissent que j’aime et qui m’aiment. Asma iii Table des mati`eres Introduction g´en´erale 2 1 Pr´esentation de l´organisme d´accueil :Alg´erie T´el´ecom 5 1.1 Pr´esentation d´Alg´erie T´el´ecom . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Pr´esentation de la Direction Op´erationnelle de T´el´ecommunication DOT Boumerdes 8 1.2.1 L´historique de la DOT de Boumerdes . . . . . . . . . . . . . . . . . . . . 8 1.2.2 Missions de direction de Boumerdes . . . . . . . . . . . . . . . . . . . . . . 8 1.2.3 Organisation de la DOT de Boumerdes . . . . . . . . . . . . . . . . . . . . 9 1.2.4 Diff´erents services de la DOT de Boumerdes . . . . . . . . . . . . . . . . . 9 1.3 Pr´esentation du champ d´´etude (service d´eploiement) . . . . . . . . . . . . . . . . 11 1.3.1 Responsabilit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2 D´efinitions,G´en´eralit´e sur le Wimax 13 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 G´en´eralit´es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3 R´eseau sans fil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.1 D´efinition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3.2 Equipement d´un r´eseau sans fil . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3.3 M´ethodes de transmission dans les r´eseaux sans fil . . . . . . . . . . . . . . 16 2.3.4 Cat´egories des r´eseaux sans fil . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 Technologie Wimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.1 D´efinition et pr´esentation du Wimax . . . . . . . . . . . . . . . . . . . . . 18 2.4.2 Wimax : Evolution des standards . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.3 Principaux ´equipements Wimax . . . . . . . . . . . . . . . . . . . . . . . . 22 2.4.4 Mode op´eratoire du Wimax . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.4.5 Apport du Wimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.4.6 Domaines et applications des r´eseaux Wimax . . . . . . . . . . . . . . . . . 25 2.4.7 Avantages du Wimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4.8 Inconv´enients du Wimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5 Technologie autour du Wimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.1 Quelques d´efinitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.5.2 Ressources fr´equentielles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.5.3 Spectre de fr´equence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.6 Gestion d´un spectre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.6.1 Objectifs de la gestion du spectre . . . . . . . . . . . . . . . . . . . . . . . 30 2.6.2 N´ecessite de la gestion du spectre de fr´equence . . . . . . . . . . . . . . . 31 2.6.3 Approche traditionnelle (actuelle) . . . . . . . . . . . . . . . . . . . . . . . 31 2.7 Impl´ementation des points d´acc`es (AP) dans un r´eseau . . . . . . . . . . . . . . . 32 iv 2.7.1 Installation des points d´acc´es . . . . . . . . . . . . . . . . . . . . . . . . 33 2.7.2 Configuration du r´eseau . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3 Probl´ematique et Mod´elisation 35 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.2 R´eseaux hertziens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 Concept cellulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.4 Interf´erences du Wimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 3.5 Handover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.6 Pr´esentation du probl`eme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.7 Mod´elisation par graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.7.1 Description des donn´ees du graphe . . . . . . . . . . . . . . . . . . . . . . . 41 3.8 Mod´elisation par la programmation lin´eaire. . . . . . . . . . . . . . . . . . . . . . . 41 3.8.1 Description des donn´ees du probl`eme . . . . . . . . . . . . . . . . . . . . . 41 3.8.2 Description de mod`ele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.9 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4 M´ethodes de R´esolution 45 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.2 Probl`eme d´optimisation combinatoire . . . . . . . . . . . . . . . . . . . . . . . . 46 4.3 Complexit´e d’un probl`eme combinatoire . . . . . . . . . . . . . . . . . . . . . . . . 46 4.4 Choix des m´ethodes de r´esolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.5 M´ethodes exactes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 4.6 M´ethodes approch´ees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.7 M´ethode Tabou . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 4.7.1 Algorithme de la recherche Tabou . . . . . . . . . . . . . . . . . . . . . . 52 4.8 Adaptation de la m´ethode Tabou au probl`eme d’allocation de fr´equences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.9 Exemple d´application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 5 Impl´ementation de logiciel 63 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Exemple d´application . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 5.3 L´ex´ecution : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Conclusion g´en´erale 68 Annexe 70 bibliograhie 79 v Table des figures 2.1 Adapteur sans fil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2 Point d´acc`es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 R´eseaux sans fils . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Exemples de mat´eriels Wimax fixe. . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.5 Exemple d’un mod`ele Wimax mobile. . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.6 LOS et NLOS. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.7 Onde hertzienne. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Deux sch´emas de configuration d’un site :(a) site muni d’une seule antenne omnidi- rectionnelle, (b) site muni de trois antennes sectorielles. . . . . . . . . . . . . . . . 36 3.2 Concept cellulaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 3.3 Concept cellulaire : (a) couverture th´eorique, (b) couverture r´eelle. . . . . . . . . . 37 3.4 D´eroulement d’un handover inter-cellulaire. . . . . . . . . . . . . . . . . . . . . . . 39 4.1 Classement des m´ethodes de r´esolution.. . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 Classification des m´ethodes de r´esolution de probl`emes d’optimisation. . . . . . . . 49 4.3 R´eseau cellulaire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 vi 1 Liste des tableaux 2.1 La famille IEEE 802.16. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Comparaison entre le Wimax fixe et mobile. . . . . . . . . . . . . . . . . . . . . . . 22 2.3 Bandes des fr´equences utilis´ees pour le Wimax . . . . . . . . . . . . . . . . . . . . 28 2.4 Le spectre de fr´equence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 UMBB 2 Introduction g´en´erale Les ´evolutions se poursuivent de toute part, tant dans le monde des r´eseaux sp´ecialis´es (capteurs, ´etiquettes intelligentes..etc) que des r´eseaux t´el´ecoms. Ceux-ci voient d´esormais des solutions concurrentes apparaˆıtre provenant de divers horizons : monde t´el´ecoms classiques, monde des r´eseaux sans fil avec le Wimax (Worldwide Interoperability for Microwave Access) voire le monde de la diffusion t´el´evision terrestre et satellite. Depuis les ann´ees 80, le probl`eme d’allocation de fr´equences fait l’objet de diff´erentes ´etudes men´ees par des chercheurs. Le spectre de fr´equences qui est attribu´e aux op´erateurs de t´el´ecommunication est divis´e en canaux fr´equentiels. L’allocation de fr´equences regroupe les m´ecanismes et proc´edures mis en œuvre afin de g´erer l’attribution des canaux de fr´equences aux demandes de communication. La gestion des fr´equences permet de d´eterminer la qualit´e du r´eseau. La qualit´e du r´eseau sans fil avec le Wimax repose essentiellement sur la gestion des ressources radio. Le r´eseau sans fil avec le Wimax utilise des fr´equences pour ´etablir les communications. Le nombre de fr´equences allou´ees `a chaque op´erateur ´etant limit´e, les fr´equences doivent ˆetre r´eutilis´ees. A cause de la r´eutilisation des fr´equences et dans le but de satis- faire la demande qui ne cesse de croitre, diff´erentes contraintes doivent ˆetre respect´ees :nombre de fr´equences par ´emetteur, compatibilit´e ´electromagn´etique...etc. L’allocation de fr´equences est un probl`eme d’optimisation combinatoire. C’est un probl`eme qui s’av`ere difficile `a r´esoudre de mani`ere exacte. En effet, la r´esolution d’un probl`eme dans lequel on consid`ere des instances de taille comparable `a celles rencontr´ees dans la pratique conduit souvent `a se heurter `a des probl`emes de temps de calcul trop importants pour des m´ethodes calculant UMBB 3 la solution optimale. Au d´ebut des ann´ees 90 ,de nouvelles heuristiques ont ´et´e d´evelopp´es .Les m´ethodes permettant d´avoir les solution approches de bonne qualit´e en temps raisonnable. Les m´etaheuristiques tel que (recuit simul´e, algorithmes g´en´etiques et la recherche Tabou ) se sont r´ev´el´es particuli`erement efficaces et on ´et´ee applique avec r´ev´el´ees particuli`erement efficaces et ont ´et´e appliqu´ees avec succ`es `a de nombreux probl`emes difficiles. Par cons´equent le ”d´eveloppement d’un outil interne de v´erification et de planification de fr´equences”,ayant comme objectif l’optimisation des violations fr´equentielles des sites on utilisant un nombre de fr´equences minimal est tr`es utile `a l’entreprise. C’est dans ce contexte que s’inscrit l’objectif de notre projet de fin d’´etudes intitul´e M´ethodologie de gestion d´un spectre et impl´ementation des points d´acc`es (AP) dans un r´eseau , propos´e dans le cadre d’une collaboration entre faculte des Sciencess M’hamed Bougara d’une part et l’op´erateur Alg´erie T´el´ecom d’autre part. Notre m´emoire de fin d’´etude est structur´e de la mani`ere suivante : Le premier chapitre est une pr´esentation de l’organisme d’accueil Alg´erie T´el´ecom et la direction op´erationnelle de T´el´ecommunication de Boumerdes en particulier, `a travers son fonctionnement g´en´eral et ses missions. Le deuxi`eme chapitre est consacr´e aux d´efinitions et g´en´eralit´es concernant le domaine de t´el´ecommunication et ´electronique, la pr´esentation de la nou- velle technologie Wimax en terminant par une m´ethodologie de la gestion du spectre et l´impl´ementation des points d´acc´ees. Le troisi`eme chapitre comprend la probl´ematique et les objectifs assign´es `a notre travail basant sur quelque d´efinitions du concept cellulaire et r´eseau hertzien.On terminant par une mod´elisation plus affine de notre probl´ematique assign´e . Avant d´entam´e la r´esolution de notre probl`eme, un quatri`eme chapitre est consacr´e pour Les m´ethodes de r´esolution de probl`eme d´allocation de UMBB