MÉMOIRE DE STAGE DE FIN D’ÉTUDES MASTER EN INFORMATIQUE SPÉCIALITÉ RÉSEAUX ET SYSTÈMES COMMUNICANTS Auto configuration d’un réseau maillé sans fil de secours Encadrants : • Mme Isabelle Guérin Lassous • M. Anthony Busson Stagiaire : • HA Pham The Anh - Promotion 16 Ce stage a été réalisé au laboratoire d’informatique de l’école normale supérieure de Lyon Juin-Novembre, 2013 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table des matières 1 Introduction .1 Environnement de stage .4 Plan du rapport. 8 2 État de l'art .1 Détection de signal/porteuse (CCA) .4 La zone d'interférence en NS3 .2 Formulation du modèle de conflit .1 Présentation des métriques .1 Réduction de la capacité du chemin (PCR) .2 Chemin d'interférence maximal (MPI) .3 Algorithme glouton existant .4 Algorithme glouton évolutif .1 Résumé des contributions et présentation des résultats important .1 Formulations estimées la capacité .2 Les scénarios de test. 51 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Remerciements Je tiens particulièrement à remercier Mme Isabelle Guérin Lassous et M.
Anthony Busson, mes responsables de stage, pour l’encadrement, l’aide, les conseils précieux pendant 6 mois de mon stage. J’adresse mes sincères remerciements à tous les professeurs de l’Institut de la Francophonie pour l’Informatique (IFI) pour m’avoir enseigné et me donnée les cours intéressants pendant mes études au niveau master. Je profite de cette occasion pour dire remercier à M. NGUYEN Huu Nghi qui m’a apporté de l’aide.
Je remercie chaleureusement mes camarades de la promotion XVI pour leurs amitiés sans faille et leurs souhaites bonnes chances pour la soutenance. Enfin, je voudrais remercier ma famille, mes parents et mes amis qui sont toujours près de moi et m’ont apporté de courage dans les moments difficiles. 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Résumé Le but de ce stage est de proposer et de développer une solution distribuée d’assignation de canaux pour des nœuds Wi-Fi formant un réseau maillé. Nous supposons que des nœuds Wi-Fi forment un réseau ad hoc destiné à acheminer des données.
Nous supposons également que ces nœuds ont plusieurs chemins possibles pour communiquer. De plus, chaque nœud est équipé de plusieurs cartes sans fil. Si ces cartes sans fil utilisent la même fréquence/canal, des interférences importantes peuvent apparaître et le partage de ce canal peut amener une capacité de bout en bout très faible. L’idée est donc d’assigner des fréquences/canaux différents aux cartes d’un même nœud.
Dans ce contexte, nous avons proposé un algorithme distribué efficace pour chaque nœud permettant d’assigner à chacune de ses cartes radios un des canaux disponibles. Il offre un maximum de capacité et de fiabilité tout en assurant la connexité du réseau. Notre algorithme a été implémenté sur le simulateur de réseau NS-3 et comparer avec des algorithmes existants. Les résultats montrent que notre approche améliore la capacité tout en réduisant la complexité.
Mots- clés : Multi-radio, multi-canal, multi-saut, assignation de canal, route, réseau ad hoc. 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Abstract The purpose of this internship was to propose and develop a distributed channel assignment algorithm for nodes in a wireless mesh network. We assume that wireless nodes are equipped with several Wi-Fi network interfaces configured in ad hoc mode. Also, we assume that the routing protocol computes several paths to the different destinations.
If these wireless cards use the same Wi-Fi channel, it may increase interference in the network and decreases significantly the end-to-end throughput. In this context, the idea is to associate different channels to the wireless cards of a same node. We propose an efficient algorithm for each node to assign a channel to its wireless cards in order to maximize the network capacity. This algorithm has been implemented on the Network Simulator NS-3, and compared with existing algorithms.
Results show that our approach improved the network capacity while reducing the algorithm complexity. Keywords: Multi-radio, multi-channel, multi-hop, channel assignment, routing and ad hoc networks. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Liste de figures Figure 1 : Le débit bidirectionnel idéal entre deux nœuds en NS3. 10 Figure 2 : Le débit directionnel idéal entre deux nœuds en NS3 .11 Figure 3 : La relation entre la collision et la distance.
21 Figure 4 : Réduction de la capacité du chemin. 23 Figure 5 : Chemin d'interférence maximal. 23 Figure 6 : Nouvelle métrique. 24 Figure 7: Chemins disjoints (extraite de [6]).
25 Figure 8 : Topologie grille. 30 Figure 9 : Topologie aléatoire. 31 Figure 10 : Topologie de grille sans route disjointe. 32 Figure 11 : Topologie aléatoire sans route disjointe.
33 Figure 12 : Topologie de grille avec la route disjointe. 34 Figure 13 : Topologie aléatoire avec la route disjointe. 35 Figure 14 : La performance entre la route disjointe et sans disjointe. 36 Figure 15 : La possibilité sans suppression.
37 Figure 16 : Capacité homogène. 40 Figure 17 : Capacité hétérogène - Nœud Destination - 1MBit/s. 40 Figure 18 : Capacité hétérogène - Nœud Destination - 2MBit/s. 50 Figure 19 : Capacité hétérogène - Nœud Destination - 5.
50 Figure 20 : Capacité hétérogène - Nœud Destination - 11MBit/s. 51 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.1 Environnement de stage Dans le cadre de mon stage de Master 2 entre l’institut de la francophonie pour l’informatique et l’université Claude Bernard Lyon 1, ce stage a été réalisé dans le laboratoire d’informatique de l’école normale supérieure de Lyon dans le cadre du projet ANR « RESCUE» et sous la direction de Mme Isabelle Guérin Lassous et Mr. Le but du projet RESCUE est de proposer des solutions pour le déploiement de réseau de substitution permettant de palier à un défaut de fonctionnement du réseau natif (réseau filaire d’un opérateur par exemple).2 Problématique De nos jours, les équipements ayant une capacité de communication sans fil sont légions (téléphone portable, smartphone, PDA, baladeur, ordinateur, etc. Ils sont capables de créer un réseau sans fil ad hoc où ils communiquent directement entre eux sans le besoin de s’associer avec un point d’infrastructure.
Ces réseaux ont plusieurs avantages. Ils peuvent se déployer rapidement, n’importe où, peuvent être temporaire, et sont peu onéreux. Dans le cadre du projet RESCUE, c’est ce type de solutions qui a été choisit pour se substituer à la partie du réseau en défaut. Les réseaux visés pouvant être des réseaux d’opérateurs, le réseau ad hoc de substitution doit fournir une capacité importante.
Mais dans les réseaux sans fil traditionnels, les nœuds sont généralement équipés d’une seule carte radio, et ces cartes configurées sur le même canal Wi-Fi. Le canal est donc fortement partagé. La capacité du canal se réduit significativement avec la taille du réseau [5].3 Motivation En pratique, un lien sans fil devra partager son canal avec tous les liens en « conflits » [2]. La notion de conflits sera discutée un peu plus loin dans ce document.
Elle est relative à un lien, et peut être définit comme l’ensemble des autres liens avec lesquels une transmission simultanée n’est pas possible. Si le nombre de ces conflits diminue, la capacité du réseau sera améliorée. Un moyen simple d’augmenter cette capacité est d’équiper les nœuds de plusieurs cartes sans fils et de leur assigner des fréquences/canaux différentes. Les liens précédemment en conflits ne le seront plus car ces fréquences/canaux peuvent être utilisés de manière simultanée et sans interférer.
Le problème consiste alors à assigner les fréquences de manière à minimiser le nombre de 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com conflits dans le réseau. Il existe déjà des algorithmes centralisés, par exemple : CLICA (Connected Low Interference Channel Assignment) [3], Tabu [1], Glouton [1], qui propose des solutions à ce problème d’optimisation. Toutefois, ces derniers assignent tous les liens dans le réseau quand même ces liens ne sont pas des liens « actifs », c'est-à-dire ne participe pas à la transmission des données. Cela provoque des gaspillages de radio et de fréquence, et génère un grand nombre de conflits.
De plus, il cherche à minimiser le nombre total de conflits dans le réseau. Il est clair que cette quantité est liée à la capacité du réseau, mais ce lien ne peut pas être exprimé sous forme analytique. Ce stage présente deux contributions : la proposition d’une fonction de bénéfice qui soit proche de la capacité réel du réseau et donc du problème que l’on cherche à optimiser, et la proposition d’une heuristique/algorithme permettant d’approcher son optimal.4 Plan du rapport Le présent document est organisé comme suit : Le chapitre deux a pour but d'aborder les inconvénients existant dans les réseaux sans fil ad hoc. Plus précisément, nous présentons une étude de l’impact des « conflits » sur le débit moyen des liens.
Nous avons testé un certain nombre de scénarios au travers de simulations afin d’étudier ce phénomène de manière réaliste. Grâce à ces scénarios, nous avons déterminé les cas réduisant le débit. Cela nous a permis de proposer un modèle simple permettant de trouver les liens qui se trouvent en conflit avec un lien donné. Le chapitre trois présente des métriques qui nous permettent d’évaluer le nombre de conflit sur un chemin (routes au sens IP).
Ces métriques sont directement liées à la diminution du débit sur ces chemins par rapport au débit nominale des liens. Nous présentons également une nouvelle métrique qui évalue le débit de bout en bout. Cette dernière métrique constituera la base de la fonction que l’on optimisera pour assigner les fréquences. Enfin, notre algorithme d’assignation est présenté de manière détaillée sous forme algorithmique.
Le chapitre quatre décrit les résultats de l’algorithme proposé. Il montre aussi les comparaisons entre l'algorithme glouton issu de la littérature, notre algorithme et le cas où les nœuds ont une seule interface et utilisent tous la même fréquence. Les simulations ont été faites avec le simulateur NS-3. Plus précisément, nous avons utilisé deux programmes.
Un premier programme en langage C fixe la topologie, calcul les routes, assigne les fréquences suivant les différents algorithmes. Ils génèrent alors un ensemble de fichiers NS-3. Ces fichiers sont ensuite transmis automatiquement à NS3, qui simulent les scénarios de manière réaliste, et qui calcul la capacité en réception (nombre de Mbit/s reçu à la destination). Le chapitre cinq consiste en un bref résumé des résultats, des évolutions possibles, des problèmes survenus et des perspectives.
8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 2 État de l'art 2.1 Vérifications Pour cette partie, nous avons vérifié les conclusions décrites dans [4] en proposant des scénarios dans le réseau ad hoc. Le but est d’étudier les topologies et scenarios pour lesquelles des conflits apparaissent. L’idée est la suivante. Dans un premier temps, on estime le débit d’un seul lien Wi-Fi lorsqu’il n’y a aucun conflit, autrement dit lorsqu’il n’y a que deux nœuds.
Puis, nous comparons ce cas à des scenarios plus complexes où il y a plusieurs liens utilisant le même canal et transmettant en même temps. Les liens sont considérés en conflits s’il y a une perte de débit. Ces simulations nous ont permis de déterminer les cas où les liens sont en conflits et de proposer un modèle simple permettant d’estimer le nombre de conflits à partir des informations topologiques. Nous avons considéré une chaîne de nœud dans les simulations.
Ces simulations utilisent l'outil NS3.1 Détection de signal/porteuse (CCA) CCA (Clear Channel Assessment) est défini dans les normes IEEE 802. Les opérations ont lieu de la couche MAC où un protocole d’accès au médium radio a été basé sur une écoute active du canal radio afin de déterminer son état étant libre ou non. Si un signal est reçu avec une puissance supérieure à un seuil appelé « seuil de détection de porteuse », le médium sera considéré comme occupé et la station voulant envoyer une trame doit attendre. Cela provoque le partage de la bande passante.