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

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