Qualité de service et routage dans les réseaux maillés sans fil, Quality of Service and Routing in Wireless Mesh Networks

Usman Ashraf

Description

Sous la direction de Guy Juanole, Abdellatif Slim
Thèse soutenue le 08 avril 2010: INSA de Toulouse
Ce travail de thèse présente trois contributions qui portent sur le routage et la fourniture de qualité de service dans les réseaux maillés sans fil basés sur IEEE 802.11. La première contribution définit une métrique de routage qui permet de sélectionner les chemins empruntant des liens avec de bonnes performances exprimées en termes d’interférences physiques (qui causent des pertes), d’interférences logiques (qui causent des délais) et de capacité. L’évaluation de cette métrique par rapport aux principales métriques de la littérature scientifique montre une amélioration des performances du réseau. La deuxième contribution concerne l’amélioration du mécanisme de maintenance de route le plus souvent utilisé par les protocoles de routage réactifs. Ce mécanisme considère qu'une route est coupée si l'un de ses liens observe plusieurs échecs successifs de retransmission. Nos études montrent que ces échecs sont assez souvent dûs à de problèmes transitoires sur les liens (bruit, interférence etc.). Nous avons donc proposé des algorithmes de maintenance de route qui appréhendent mieux les problèmes ponctuels ou soutenus sur les liens ce qui permet de prendre une décision cohérente et réfléchie quant à la coupure d’un lien (et donc d'une route). Les études de performances montrent une amélioration conséquente des performances globales du réseau. La dernière contribution propose un cadre pour la fourniture de la Qualité de Service (garantie de bande passante) dans les réseaux maillés multi-interfaces, multi-canaux. Ce cadre intègre un protocole de routage réactif couplé à un mécanisme de contrôle d'admission et de partage de charge. Ces derniers exploitent la diversité des liens entre nœuds voisins afin d’améliorer le taux d’admission des flux avec garantie de bande passante
-Réseaux maillés sans fil
-Qualité de service
-Métrique de routage
-Routage
This thesis presents three contributions in the area of routing and Quality of Service for IEEE 802.11-based Wireless Mesh Networks. The first contribution defines a routing metric for the selection of route by taking into consideration the performance of wireless links in terms of physical interference (which causes packet losses), logical interference (which causes delay) and the capacity of the links. The performance evaluation of the proposed metric compared to the popular existing metrics shows an improvement in the performance of the network. The second contribution improves the route maintenance mechanism most often used by reactive routing protocols. The existing mechanism considers a route as broken if any of the links in the route experiences multiple successive transmission failures. Our study shows that the transmission failures are often caused by transient problems on the wireless link (noise, interference etc). We propose a novel mechanism of route maintenance which distinguishes between links with temporary or transient transmission problems compared to those with sustained problems in order to make a coherent decision about link breakage (and consequently route breakage). The performance evaluation shows a substantial improvement in the performance of the network. The final contribution proposes a framework for providing Quality of Service (bandwidth guarantee) in multi-radio multi-channel wireless mesh networks. The framework integrates a reactive routing protocol coupled with an admission control mechanism and load balancing. The framework exploits link diversity between neighboring nodes to improve the flow admission ratio with bandwidth guarantees
-Wireless mesh networks
-Quality of service
-Routing metric
Source: http://www.theses.fr/2010ISAT0005/document

Sujets

• Qualité de service
• Routage

Informations

• Publié par: Thesee
• Nombre de lectures: 44
• Langue: English
• Poids de l'ouvrage: 3 Mo

Extrait

Page 1 of 1
THÈSE
En vue de l’obtention du
DOCTORAT DE L’UNIVERSITÉ DE TOULOUSE
Délivré par l’ Institut National des Sciences Appliquées
Discipline : Systèmes Informatiques
Présentée et soutenue par
Usman Ashraf
Le8 avril2010
Qualité de Service et Routage dans
les Réseaux Maillés Sans Fil
JURY
http://ciuen2008.org/images/uploads/logo_exposant_UNR-MIDI-PYR.png 12/04/2010
Président : Michel Diaz LAAS-CNRS
Rapporteurs : Andrzej DUDA INP-Ensimag
David SIMPLOT-RYL Université de Lille1
Examinateurs : Edmundo MONTEIRO University of Coimbra
Slim ABDELLATIF Université de Toulouse (INSA)
Guy JUANOLE Université de T (Paul Sabatier)
École Doctorale : École Doctorale Systèmes
Unité de Recherche : Laboratoire d’Analyse et d’Architecture des Systèmes LAAS-CNRS
Directeurs de Thèse : Slim Abdellatif, Guy JuanoleDedicated to my parents, Muhammad Ashraf (late) and Razia Ashraf.....Acknowledgements
I would like to express my deepest thanks and gratefulness to Allah Almighty who provi-
ded me the opportunity to pursue research in the exciting domain of wireless mesh networks
in this strange and beautiful country. It is only with His help and His guidance that I have
accomplished this milestone.
I would like to thank Andrzej Duda and Simplot-Ryl for kindly accepting to review my
thesis and for being part of the jury and I would also like to express my gratitude to Michel
Diaz and Edmundo Monteiro for being part of my jury. I value the insightful and compre-
hensive feedback of the reviewers as well as the jury members on my dissertation.
I am grateful to my advisors Slim Abdellatif and Guy Juanole who helped me during the
long and difficult phases of the doctorate. Their guidance and feedback, and their emphasis
on high standards of research significantly improved the quality of this dissertation.
I would also like to express gratitude to my colleagues Mohamed El Masri, Ihsan Tou and
Ahmed Akl for their support. Mohamed El Masri has been a constant source of help during
my thesis and I appreciate his help in almost every aspect of my stay here in LAAS-CNRS.
For the wireless mesh testbed, a lot of work was required. I would like to acknowledge
the long hours of help put in by Ghassen Abassi during the experimental phase of my thesis,
in particular during the deployment of the testbed.
Last but not the least, I would like to express my gratitude to my family. They have been
a constant and tireless source of support for me and their support and prayers played a key
role in enabling me to achieve this significant milestone in my life.
Toulouse,13 avril2010.
vO Lord, thy sea is so large and my boat is so small....
viiAbstract
Wireless mesh networks are a promising technology for providing last-mile broadband wire-
less Internet to a large number of users spread across large geographical regions. Due to their
peculiar limitations and the increasing demand of users for high performance (high through-
put, low delays etc), mesh networks have attracted the attention of researchers world-wide.
Towards this goal, this dissertation contributes in several areas of Routing and Quality-of-
Service provisioning in IEEE 802.11-based wireless mesh networks. Chapter 1 introduces
wireless mesh networks and their architectural and functional components. The difference
between mesh networks and traditional wireless multi-hop networks is emphasized. A com-
prehensive background study of routing and QoS solutions for multi-hop wireless networks
is presented with an emphasis on mesh-specific solutions.
Chapter2 presents our first contribution : route selection in wireless mesh networks. A pri-
mary research problem in mesh networks is to find the "best" available route between a pair
of mesh routers. Recent research shows that selecting the shortest path is a poor decision as
it does not take into account other factors pertaining to link quality. We propose an efficient
routing metric - Expected Link Performance metric (ELP) which considers a number of factors
including link loss ratio, link interference, and link capacity to find the ”best” route between
a pair of mesh routers. Performance evaluation of ELP is carried out against contemporary
routing metrics. A part of metric is also evaluated on a mesh testbed. An extension of the me-
tric is proposed for the special case of mesh traffic directed at gateways. A gateway discovery
protocol is also proposed which integrates the extended metric and performance evaluation
is carried out against traditional gateway and gateway-route selection schemes.
Chapter 3 presents our second contribution : route maintenance in mesh networks. After
route selection, the next research problem that we consider is the maintenance of that route.
The route maintenance mechanism of on-demand routing protocols in 802.11-based mesh
networks is inaccurate and results in frequent route breakages which cause route instability
and performance degradation. The chapter discusses the problem of route stability for on-
demand protocols in detail. The Efficient Route Maintenance (ERM) scheme is proposed which
improves route maintenance for on-demand routing protocols in wireless mesh networks by
using cross-layering to get information from lower layers. The ERM scheme is then exten-
ded for multi-radio multi-channel mesh scenarios. ERM is evaluated against classical route
maintenance mechanism of the on-demand routing protocols.
Chapter 4 presents the final contribution of the thesis : QoS framework for bandwidth gua-
rantees in multi-radio multi-channel mesh networks. Providing QoS guarantees is particularly
important for users who use the mesh network to access the Internet. The framework pro-
vides flow-specific reservation-based bandwidth guarantees in mesh networks. Link diversity
(the availability of multiple redundant links between neighbors) is exploited for proposing a
novel QoS provisioning solution which can provide better load-balancing in the network and
provide a higher flow admittance ratio.
ixTableofcontents
Tableofcontents x
Listoffigures xv
Introduction 1
1 On Wireless Mesh Networks 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Basicsof Wireless Mesh Networks . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Components of a Wireless Mesh Network . . . . . . . . . . . . . . . . 7
1.2.2 Classification of Wireless Mesh Networks . . . . . . . . . . . . . . . . 8
1.2.3 Communication Technologies for Wireless Mesh Networks . . . . . . 10
1.2.4 The Power of Wireless Mesh Networks . . . . . . . . . . . . . . . . . 11
1.2.5 Differences from Traditional Wireless Multi-Hop Networks . . . . . . 13
1.3 QoSin Wireless Multi-Hop Networks . . . . . . . . . . . . . . . . . . 14
1.3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.2 Why QoS is difficult in Wireless Multi-Hop Networks . . . . . . . . . 14
1.3.3 QoS From a Layered Perspective . . . . . . . . . . . . . . . . . . . . . 16
1.3.4 QoS Frameworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3.5 QoS Solutions for Wireless Mesh Networks . . . . . . . . . . . . . . . 19
1.4 Routingin Wireless Multi-Hop Networks . . . . . . . . . . . . . . . 21
1.4.1 Overview of Routing Approaches in Wireless Multi-Hop Networks . . 21
1.4.2 Design Considerations for Routing Protocols in Mesh Networks . . . . 25
1.4.3 Mesh-Specific Routing Protocols . . . . . . . . . . . . . . . . . . . . . 26
1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Route Selectionin Wireless Mesh Networks 29
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2 Design Considerationsfor Routing Metricsin Mesh Networks . . 32
2.2.1 Route Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.2.2 Elements for Specifying Routing Metrics . . . . . . . . . . . . . . . . 33
2.2.3 Efficient Algorithm to Calculate Minimum cost Path . . . . . . . . . . 36
2.2.4 Loop-Free Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.3 Reviewof Routing Metricsfor Wireless Mesh Networks . . . . . . 37
2.3.1 ETX - Expected Transmission Count . . . . . . . . . . . . . . . . . . . 38
x