Date : 2012
Editeur / Publisher : Villetaneuse : Université Paris 13 , 2012
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Analyse de réseau (planification)
Systèmes de communication sans fil
Résumé / Abstract : Wireless mesh networks (WMNs) have emerged as a key technology for next generationwireless networks, showing rapid progress and inspiring numerous applications. In this thesis we emphasize on the planning and resource allocation in WMN. The work can be divided in three parts. In the first part, we investigate the problem of designing the access tier network. We aim at minimizing the installation cost, and maximizing the nominal throughput to offer to each user while minimizing the interference. We propose to deal with this multi-objective problem using two approaches. In the first approach we divide the access tier network planning issue into two problems: (1) the mesh router placement problem and (2) the frequency assignment problem. To deal with the mesh router positioning problem, we propose two strategies namely the Markov Cluster-Integer Linear Programming (MCLILP) and the Disk Covering algorithms. However, to resolve the frequency assignment problem, we propose to reduce the interference using the three algorithms: Predefined frequency Vector Approach (PFVA), Least-Interfering Channel Search (LICS) and the TPsbased Least Interfering Channel Search (TPs-LICS). We propose a second approach dealing jointly with both problems of mesh router positioning and channel assignment, namely the Three-Phase Heuristic Algorithm forWLAN planning (TPHA). This novel fast and scalable heuristic based on the potential field approach. In the second part, we deal with the backhaul topology design problem. This latter involves the following two issues: the backhaul topology formation problem and the capacity assignment problem. To overcome the complexity of this global problem, we propose the Backhaul Topology Formation Algorithm (BTFA) to solve the problem of topology formation while maximizing the capacity. However, we use an iterative-based Weighted Max-Min Fair Capacity Allocation algorithm to deal with a fair capacity assignment. In the third part, we deal with the dimensioning problem (or resource allocation) in mesh networks. We consider two different access technologies at the access tier: connectionless communication mode and connection-oriented communication mode. We propose a dimensioning methodology for each assumed technology in order to satisfy the objectives of maximizing the capacity at the backhaul tier and sharing it in a weighted max-min fair manner among all mesh routers. We evaluate the performance of our propositions and show their effectiveness by comparing them to the exact solution.
Résumé / Abstract : Les réseaux maillés sans fils (Wireless Mesh Networks) sont apparus comme une technologie phare pour le développement des réseaux sans fils de nouvelle génération, subissant un développement rapide et inspirant un certain nombre d’applications. Dans cette thèses, on se focalise sur la planification et l’allocation de ressources dans WMN. Ce travail est divisé en trois volets. Dans le premier volet, nous traitons le problème de planification du réseau dorsal. Nous nous intéressons à la minimisation du coût d’installation, et la maximisation du débit nominal à offrir à chaque utilisateur, tout en minimisant l’interférence. Nous proposons de traiter ce problème multiobjectif en utilisant deux approches. Dans la première approche, nous définissons le problème de planification du réseau d’accès comme étant : (1) problème du positionnement de routeurs mesh et (2) problème d’affectation de canaux. Afin de résoudre le problème du positionnement des routeurs mesh, nous avons proposé deux stratégies : à savoir l’algorithme de Markov Cluster-Integer Linear Programming (MCLILP) et l’algorithme de disques couvrants. Par ailleurs, nous avons résolu le problème d’affectation de canaux par la proposition de trois algorithmes : Predefined frequency Vector Approach (PFVA), Least-Interfering Channel Search (LICS) and the TPsbased Least Interfering Channel Search (TPs-LICS). Ensuite, nous avons proposé une deuxième approche appelée Three-Phase Heuristic Algorithm for WLAN planning (TPHA). Notre deuxième approche permet d’optimiser conjointement les deux problèmes de positionnement de routeurs mesh et d’affectation de canaux. Cette nouvelle heuristique, rapide et évolutive, inspirée du domaine de la robotique, se base sur l’approche du champ de potentiel. Dans le deuxième volet, nous nous focalisons sur le problème de planification du réseau dorsal. Ce dernier, est défini comme étant : la formation de la topologie du réseau dorsal et l’affectation de sa capacité. Etant donné que la planification du réseau dorsal est un problème complexe, nous avons proposé une heuristique en deux phases. La première phase consiste en la formation de topologie en choisissant les liens qui maximisent la capacité totale du réseau dorsal. Tandis que la deuxième phase, permet le partage de la capacité du réseau dorsal entre les différents routeurs mesh selon l’équité Max-Min. Dans le troisième volet, nous nous intéressons au problème du dimensionnement (allocation de ressources) du réseau mesh à deux niveaux. Nous supposons deux technologies d’accès différentes : mode de communication non connecté et le mode connecté. Nous proposons une méthodologie de dimensionnement pour chaque mode de communication afin de satisfaire les deux objectifs de maximisation de la capacité et de la partager entre tous les routeurs mesh selon la stratégie d’équit´e Max-Min pondérée. Finalement, les algorithmes et modèles propos´es ont été évalués en comparant leurs résultats à la solution exacte.