On the evaluation and classification of routing protocols for mobile ad hoc networks [Elektronische Ressource] / Daniel Lang

Informations

• Publié par: technische_universitat_munchen
• Publié le: 01 janvier 2006
• Nombre de lectures: 22
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Technische Universit¨at Munc¨ hen
Institut fur¨ Informatik
On the Evaluation and Classification
of Routing Protocols for
Mobile Ad Hoc Networks
Daniel LangIILehrstuhl fur¨ Netzwerkarchitekturen,
Telematik, Telekooperation
On the Evaluation and Classification
of Routing Protocols for
Mobile Ad Hoc Networks
Daniel Lang
Vollst¨andiger Abdruck der von der Fakult¨at fu¨r Informatik der Technischen
Universit¨at Munc¨ hen zur Erlangung des akademischen Grades eines
Doktors der Naturwissenschaften (Dr. rer. nat.)
genehmigten Dissertation.
Vorsitzender: Univ.-Prof. Dr. Helmut Krcmar
Prufer¨ der Dissertation:
1. Univ.-Prof. Dr. Eike Jessen, em.
2. Univ.-Prof. Dr. J¨org Ebersp¨acher
3. Univ.-Prof. Anja Feldmann, Ph.D.
DieDissertationwurdeam27.11.2003beiderTechnischenUniversit¨atMunc¨ hen
eingereicht und durch die Fakult¨at fur¨ Informatik am 07.07.2006 angenom-
men.II
Keywords
Mobile Ad Hoc Networks, Routing, Evaluation, Simulation, Scenarios
Abstract
A Mobile Ad Hoc Network (MANET) is a mobile, wireless network that does
not necessitate a pre-existing infrastructure. The routing infrastructure needs
to be established in a distributed, self-organized way. Many routing protocols for
MANETshavebeenproposed,andsomeevaluatingworkhasbeenconducted. The
large number of the proposed routing protocols and evaluations makes it difficult
to keep track of the development and to get an overview of the strengths and
weaknesses of routing protocols. This dissertation analyses evaluation techniques
from the past anddescribes commonproblems withsimulation based evaluation of
routing protocols for MANETs and how to resolve them. Simulation scenarios are
examined and evaluated, sample applications are suggested and relations to past
and present evaluations are drawn. A comprehensive number of MANET routing
protocols is examined and categorized and similarities (e.g. due to evolutionary
development) are deduced and presented. It is proposed that these can be used
to reduce the number of experiments. Finally a set of sample simulation results is
presented.Contents
1 Introduction 1
1.1 Commonly used terms . . . . . . . . . . . . . . . . . . . . . . 1
1.2 MANETs - A self-organizing networking concept . . . . . . . . 2
1.3 Problems with Mobile Ad Hoc Networks . . . . . . . . . . . . 3
1.4 Applications for MANETs . . . . . . . . . . . . . . . . . . . . 4
1.5 Evaluation and Scenarios . . . . . . . . . . . . . . . . . . . . . 4
1.6 Status of IETF development efforts . . . . . . . . . . . . . . . 5
1.7 Outline of this Dissertation . . . . . . . . . . . . . . . . . . . 5
2 Problems and Motivation 7
2.1 Evaluation in Past and Present Research . . . . . . . . . . . . 7
2.1.1 Performance Metrics . . . . . . . . . . . . . . . . . . . 8
2.1.2 Simulation Software . . . . . . . . . . . . . . . . . . . 10
3 Methodologies and Motivation for Comparison 13
3.1 Types of Comparisons and Motivation . . . . . . . . . . . . . 13
3.2 Relevance of Comparisons . . . . . . . . . . . . . . . . . . . . 14
3.3 Representation of Characteristics . . . . . . . . . . . . . . . . 15
3.3.1 Encoding Method for Characteristics . . . . . . . . . . 16
3.3.2 General Description of the Comparison Functions . . . 17
3.3.3 Comparison Result . . . . . . . . . . . . . . . . . . . . 18
3.4 Comparisons and Evaluations not done . . . . . . . . . . . . . 19
3.5 Implementation of Comparisons . . . . . . . . . . . . . . . . . 19
4 Scenarios Used in Previous Evaluations 21
4.1 Characteristics and Quality of a Scenario . . . . . . . . . . . . 21
4.2 Currently Used Scenarios . . . . . . . . . . . . . . . . . . . . . 24
4.2.1 Common Observations . . . . . . . . . . . . . . . . . . 24
4.2.2 Simple Scenarios . . . . . . . . . . . . . . . . . . . . . 25
4.2.3 Advanced Scenarios . . . . . . . . . . . . . . . . . . . . 28
4.2.4 Real Installations: CMU Testbed and AODV Testbed . 30
IIIIV CONTENTS
4.3 Other Models and Tools . . . . . . . . . . . . . . . . . . . . . 30
4.3.1 Modeling Turning and Acceleration: Smooth is Better
than Sharp . . . . . . . . . . . . . . . . . . . . . . . . 30
4.3.2 Scenario Generators and CADHOC . . . . . . . . . . . 31
4.4 Discussion: Why Have These Scenarios Been Used . . . . . . . 32
4.4.1 Why the 1500×300m area? . . . . . . . . . . . . . . . 33
4.4.2 Why random waypoint/random direction ? . . . . . . . 33
4.5 Criticism of Proposed Scenarios . . . . . . . . . . . . . . . . . 33
4.5.1 Node Behavior . . . . . . . . . . . . . . . . . . . . . . 33
4.5.2 Mobility Metric . . . . . . . . . . . . . . . . . . . . . . 34
4.5.3 Number of Nodes . . . . . . . . . . . . . . . . . . . . . 34
4.5.4 Modeling of Physical Properties . . . . . . . . . . . . . 35
4.5.5 Border Behavior . . . . . . . . . . . . . . . . . . . . . 35
4.6 Comparing Scenarios Against Benchmark Characteristics . . . 36
4.6.1 Benchmark Characteristics and Reference Values . . . 36
4.6.2 Benchmark Results . . . . . . . . . . . . . . . . . . . . 40
4.7 Comparison of the Simulation Scenarios . . . . . . . . . . . . 41
4.7.1 Characteristics used for Comparison . . . . . . . . . . 41
4.7.2cterizing and Comparing the Scenarios . . . . . . 50
4.7.3 Similarity Results . . . . . . . . . . . . . . . . . . . . . 66
5 Applications for MANETs 77
5.1 Overview. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Characteristics of Application Scenarios. . . . . . . . . . . . . 78
5.3 Matching Simulated Scenarios to Applications . . . . . . . . . 82
5.3.1 Comparison of Application and Simulation Scenarios . 83
5.3.2 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.4 Matching Results Overview . . . . . . . . . . . . . . . . . . . 89
5.5 Application Scenarios in Detail . . . . . . . . . . . . . . . . . 93
5.5.1 PANs and Bluetooth . . . . . . . . . . . . . . . . . . . 93
5.5.2 Conference Room . . . . . . . . . . . . . . . . . . . . . 94
5.5.3 Trade Fair Networks . . . . . . . . . . . . . . . . . . . 95
5.5.4 Event Coverage . . . . . . . . . . . . . . . . . . . . . . 97
5.5.5 Extended Cellular Phone Networks . . . . . . . . . . . 99
5.5.6 Office Building Networks . . . . . . . . . . . . . . . . . 100
5.5.7 Individual Spontaneous Networks . . . . . . . . . . . . 102
5.5.8 Car Based Networks . . . . . . . . . . . . . . . . . . . 103
5.5.9 Farm and Park Management . . . . . . . . . . . . . . . 105
5.5.10 Sensor Networks . . . . . . . . . . . . . . . . . . . . . 106
5.5.11 Disaster Area Recovery Support . . . . . . . . . . . . . 108
5.5.12 Military Applications . . . . . . . . . . . . . . . . . . . 110CONTENTS V
5.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6 Other Scenario Considerations 113
6.1 Other Views of Scenarios . . . . . . . . . . . . . . . . . . . . . 113
6.2 Empirical Movement Data for Scenarios . . . . . . . . . . . . 114
6.2.1 Tracks generated by a GPS receiver . . . . . . . . . . . 115
6.2.2 Data from Telecommunication Carriers . . . . . . . . . 116
6.3 Movement Properties . . . . . . . . . . . . . . . . . . . . . . . 116
6.3.1 Movement Strategies . . . . . . . . . . . . . . . . . . . 117
6.4 Correlated Movement and Group Mobility . . . . . . . . . . . 118
7 Classification and Comparison of MANET Routing Proto-
cols 121
7.1 Choice of Protocols examined . . . . . . . . . . . . . . . . . . 121
7.2 Classification of Ad Hoc Routing Protocols . . . . . . . . . . . 122
7.2.1 Single Channel vs. Multichannel Protocols . . . . . . . 124
7.2.2 Uniform vs. Non-Uniform Protocols . . . . . . . . . . . 125
7.2.3 Structure of Topology . . . . . . . . . . . . . . . . . . 125
7.2.4 Usage of External Services . . . . . . . . . . . . . . . . 127
7.2.5 Topology Updates. . . . . . . . . . . . . . . . . . . . . 129
7.2.6 Amount of Topology Information Maintained . . . . . 132
7.2.7 Use of Source Routing . . . . . . . . . . . . . . . . . . 132
7.2.8 Use of Broadcast Messages . . . . . . . . . . . . . . . . 132
7.2.9 Recovery Mechanisms . . . . . . . . . . . . . . . . . . 133
7.2.10 Route Selection Strategy . . . . . . . . . . . . . . . . . 133
7.3 Possible Dependencies Between Protocol Characteristics . . . 134
7.4 Comparison Functions for Routing Protocol Characteristics . . 135
7.4.1 Overview over Comparison Function . . . . . . . . . . 135
7.4.2 Description of Comparison Fns . . . . . . . . . . 135
7.4.3 Comparison Results. . . . . . . . . . . . . . . . . . . . 144
7.5 Performance Comparisons Previously Done . . . . . . . . . . . 152
7.5.1 ABR vs. DSR and DBF . . . . . . . . . . . . . . . . . 153
7.5.2 ADV vs. AODV, DSDV and DSR . . . . . . . . . . . . 153
7.5.3 AODV, DSDV, DSR and TORA . . . . . . . . . . . . 153
7.5.4 FSR, HSR and DSDV . . . . . . . . . . . . . . . . . . 153
7.5.5 GEDIR vs. DIR and MFR . . . . . . . . . . . . . . . . 154
7.5.6 GPSR vs. DSR . . . . . . . . . . . . . . . . . . . . . . 154
7.5.7 GSR vs. DBF and ILS . . . . . . . . . . . . . . . . . . 154
7.5.8 LANMAR vs. AODV, DSR and FSR . . . . . . . . . . 154
7.5.9 OLSR vs. AODV and DSR . . . . . . . . . . . . . . . 154
7.5.10 STAR vs. topology broadcast, ALP and DSR . . . . . 154VI CONTENTS
7.5.11 WAR vs. DSR . . . . . . . . . . . . . . . . . . . . . . 155
7.5.12 WRP vs. DBF, DUAL and ILS . . . . . . . . . . .