357 Pages
English

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

Gain access to the library to view online
Learn more

Subjects

Informations

Published by
Published 01 January 2006
Reads 22
Language English
Document size 2 MB

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 . . . . . . . . . . . . . 155
8 Description of Individual MANET Routing Protocols 157
8.1 ABR - Associativity Based Routing . . . . . . . . . . . . . . . 157
8.2 ADV - Adaptive Distance Vector Routing . . . . . . . . . . . 158
8.3 AODV - Ad Hoc On Demand Distance Vector Routing Protocol160
8.3.1 MAODV . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.4 CBRP - Cluster Based Routing Protocol . . . . . . . . . . . . 162
8.5 CGSR - Clusterhead Gateway Switch Routing . . . . . . . . . 163
8.6 CEDAR - Core-Extraction Distributed Ad Hoc Routing . . . . 164
8.7 DDR - Distributed Dynamic Routing Algorithm . . . . . . . . 166
8.8 DREAM - Distance Routing Effect Algorithm for Mobility . . 166
8.9 DSDV - Destination Sequenced Distance Vector Routing Pro-
tocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
8.10 DSR - Dynamic Source Routing . . . . . . . . . . . . . . . . . 169
8.11 DST - Distributed Spanning Tree Protocol . . . . . . . . . . . 170
8.12 FORP - Flow Oriented Routing Protocol . . . . . . . . . . . . 171
8.13 FSLS - Fuzzy Sighted Link State Algorithms . . . . . . . . . . 172
8.14 FSR - Fisheye State Routing . . . . . . . . . . . . . . . . . . . 174
8.15 GEDIR - Geographic Distance Routing . . . . . . . . . . . . . 175
8.16 GPSR - Greedy Perimeter Stateless Routing . . . . . . . . . . 175
8.17 GSR - Global State Routing . . . . . . . . . . . . . . . . . . . 177
8.18 HSR - Hierarchical State Routing . . . . . . . . . . . . . . . . 178
8.19 LANMAR - Landmark Routing Protocol . . . . . . . . . . . . 179
8.20 LAR - Location Aided Routing . . . . . . . . . . . . . . . . . 181
8.21 LMR - Lightweight Mobile Routing . . . . . . . . . . . . . . . 182
8.22 LRR - Link Reversal Routing . . . . . . . . . . . . . . . . . . 184
8.23 OLSR - Optimized Link State Routing . . . . . . . . . . . . . 185
8.24 SSA - Signal Stability-Based Adaptive Routing . . . . . . . . 185
8.25 STAR - Source Tree Adaptive Routing . . . . . . . . . . . . . 187
8.26 TBRPF - Topology Broadcast Based on Reverse Path For-
warding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
8.27 TLR/TRR/AGPF - Terminode Routing . . . . . . . . . . . . 190
8.28 TORA - Temporally Ordered Routing Algorithm . . . . . . . 192
8.29 WAR - Witness Aided Routing . . . . . . . . . . . . . . . . . 193
8.30 WRP - Wireless Routing Protocol . . . . . . . . . . . . . . . . 196
8.31 ZRP - Zone Routing Protocol . . . . . . . . . . . . . . . . . . 196CONTENTS VII
9 Realistic Scenarios for Evaluation 199
9.1 Requirements of Scenarios . . . . . . . . . . . . . . . . . . . . 199
9.1.1 The Node-Interactive Mobility Model . . . . . . . . . . 200
9.2 Partial Implementation of the Node-Interactive Model . . . . . 202
9.2.1 Requirements . . . . . . . . . . . . . . . . . . . . . . . 202
9.2.2 Outline of the Implementation . . . . . . . . . . . . . . 204
9.2.3 Limitations of thetation . . . . . . . . . . . 206
9.2.4 Achievements of the Implementation . . . . . . . . . . 206
10 Simulation Framework 207
10.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
10.1.1 On the Amount of Simulations to be Performed . . . . 207
10.2 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . 211
10.2.1 Requirements on the Implementation . . . . . . . . . . 211
10.2.2 Outline of the Implementation . . . . . . . . . . . . . . 212
10.2.3 Limitations of thetation . . . . . . . . . . . 212
10.2.4 Achievements of the Implementation . . . . . . . . . . 213
11 Simulations 215
11.1 Aims of these Simulations . . . . . . . . . . . . . . . . . . . . 215
11.2 Performance Metrics and Sample Statistics . . . . . . . . . . . 216
11.2.1 Routing Overhead . . . . . . . . . . . . . . . . . . . . 216
11.2.2 Route Setup Ratio . . . . . . . . . . . . . . . . . . . . 218
11.2.3 MAC Broadcast Ratio . . . . . . . . . . . . . . . . . . 219
11.2.4 IP Delivery Ratio . . . . . . . . . . . . . . . . . . . . . 220
11.2.5 Broken Links/Robustness . . . . . . . . . . . . . . . . 221
11.2.6 TCP Retransmitted Packets . . . . . . . . . . . . . . . 221
11.2.7 Application Data Throughput . . . . . . . . . . . . . . 222
11.2.8 TCP Delay . . . . . . . . . . . . . . . . . . . . . . . . 222
11.3 Simulation Tools Used . . . . . . . . . . . . . . . . . . . . . . 223
11.3.1 Requirements . . . . . . . . . . . . . . . . . . . . . . . 223
11.3.2 Examination of Existing Simulation Software. . . . . . 225
11.4 Scenario Generators Used . . . . . . . . . . . . . . . . . . . . 230
11.4.1 NoMoGen . . . . . . . . . . . . . . . . . . . . . . . . . 230
11.4.2 scengen . . . . . . . . . . . . . . . . . . . . . . . . . . 231
11.4.3 Traffic Scenario Generation . . . . . . . . . . . . . . . 232
11.5 Simulation Scenarios Used . . . . . . . . . . . . . . . . . . . . 232
11.5.1 Town Center with Cars and Pedestrians . . . . . . . . 233
11.5.2 Roads on the Countryside . . . . . . . . . . . . . . . . 235
11.5.3 A Disaster Area . . . . . . . . . . . . . . . . . . . . . . 236
11.5.4 A Nature Park . . . . . . . . . . . . . . . . . . . . . . 237VIII CONTENTS
11.6 Routing Protocols Used for this Simulation . . . . . . . . . . . 238
11.6.1 Representativeness of the Selected Routing Protocols . 238
11.6.2 Routing Transport Used in GloMoSim Implementation 239
11.7 Outline of Experiments . . . . . . . . . . . . . . . . . . . . . . 240
11.7.1 Problems with the Simulation Software . . . . . . . . . 240
11.7.2 Actual Number of Simulation Runs . . . . . . . . . . . 241
11.8 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
11.8.1 Do Similar Scenarios Yield Similar Results? . . . . . . 243
11.8.2 Differences Between Realistic and Simple Scenarios . . 247
11.8.3 Do Similar Routing Protocols Yield Similar Results? . 249
11.8.4 Performance of Examined Routing Protocols . . . . . . 251
11.8.5 Summary of Results . . . . . . . . . . . . . . . . . . . 257
12 Summary and Conclusion 259
12.1 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 259
12.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
12.3 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
13 Acknowledgments 263
A Definitions 265
A.1 Terms Generally Used in this Dissertation . . . . . . . . . . . 265
A.2 Terms Used in Simulation and Application Scenario Context . 266
A.3 Terms Used in Routing Protocol Context . . . . . . . . . . . . 268
B GPS Empirical Data 275
B.1 Location Trace . . . . . . . . . . . . . . . . . . . . . . . . . . 275
B.2 Direction Changes . . . . . . . . . . . . . . . . . . . . . . . . 275
B.3 Speed Changes . . . . . . . . . . . . . . . . . . . . . . . . . . 275
B.4 Distance Distribution . . . . . . . . . . . . . . . . . . . . . . . 276
C Data from Smooth Model 281
C.1 Distributions of Turns, Distance and Speed . . . . . . . . . . . 281
C.1.1 Direction Change Distribution . . . . . . . . . . . . . . 282
C.1.2 Distance Distribution . . . . . . . . . . . . . . . . . . . 283
C.1.3 Speed Distribution . . . . . . . . . . . . . . . . . . . . 285
C.2 Example node results . . . . . . . . . . . . . . . . . . . . . . . 287
C.2.1 Location Traces . . . . . . . . . . . . . . . . . . . . . . 287
C.2.2 Directions and Direction Changes . . . . . . . . . . . . 289
C.2.3 Distances . . . . . . . . . . . . . . . . . . . . . . . . . 292
C.2.4 Speed and Speed-changes . . . . . . . . . . . . . . . . 293