201 Pages
English

Wireless multi-hop ad hoc networks [Elektronische Ressource] : evaluation of radio disjoint multipath routing / of Koojana Kuladinithi

-

Gain access to the library to view online
Learn more

Description

Communication Networks University of Bremen Prof. Dr. rer. nat. habil. C. Görg Dissertation Wireless Multi-hop Ad hoc Networks: Evaluation of Radio Disjoint Multipath Routing of Koojana Kuladinithi from Galle, Sri Lanka nd22 of December 2009 First Examiner: Prof. Dr. rer. nat. habil. C. Görg Second Examiner: Prof. Dr. -Ing. Andreas Timm-Giel ndSubmitted on: 22 of December 2009 ACKNOWLEDGEMENT This thesis was written during my research assistantship at the Communication Networks Group (ComNets) of the Center for Computer Science and Information Technology (TZI) at the University of Bremen. I sincerely thank the many people who have contributed in many different ways to make this work possible. Working for ComNets has been a very enriching experience since I got the opportunity to work side by side with some great people. Prof. Ranjit Perera introduced me to ComNets, such a nice group of people whom I consider as my extended family. Prof. Carmelita Görg made all the arrangements to commence my assistantship here. She guided me and gave me invaluable advice that provided me the direction required for my research work. She was able to place me in the right projects that let me undertake research related to my thesis area. She has been a role model for me and there are 2 things that I would like most to emulate from her.

Subjects

Informations

Published by
Published 01 January 2009
Reads 57
Language English
Document size 2 MB



Communication Networks

University of Bremen

Prof. Dr. rer. nat. habil. C. Görg








Dissertation


Wireless Multi-hop Ad hoc Networks:
Evaluation of Radio Disjoint Multipath
Routing

of
Koojana Kuladinithi
from
Galle, Sri Lanka



nd
22 of December 2009
First Examiner: Prof. Dr. rer. nat. habil. C. Görg
Second Examiner: Prof. Dr. -Ing. Andreas Timm-Giel
nd
Submitted on: 22 of December 2009 ACKNOWLEDGEMENT

This thesis was written during my research assistantship at the Communication Networks Group
(ComNets) of the Center for Computer Science and Information Technology (TZI) at the
University of Bremen. I sincerely thank the many people who have contributed in many
different ways to make this work possible.

Working for ComNets has been a very enriching experience since I got the opportunity to work
side by side with some great people. Prof. Ranjit Perera introduced me to ComNets, such a nice
group of people whom I consider as my extended family.

Prof. Carmelita Görg made all the arrangements to commence my assistantship here. She guided
me and gave me invaluable advice that provided me the direction required for my research
work. She was able to place me in the right projects that let me undertake research related to my
thesis area. She has been a role model for me and there are 2 things that I would like most to
emulate from her. The first is the discipline she has in her professional life and her social life
that I know. The second is her efforts that she makes to provide opportunities for women in
academia.

Prof. Andreas Timm-Giel is a person I always relied on to give me advice and ideas. The
innumerable discussions I had with him on topics ranging from project work to my PhD have
resulted in bringing clarity to my research.

Prof. Samir Das had discussions with me that motivated and gave me some critical ideas that
became part of my PhD focus. The early discussions that I had with Ioannis Fikouras and Niko
Fikouras as part of the NOMAD project gave me the initial direction in my research work. I got
many valuable ideas and help when performing some of the wireless related experiments of the
wearIT@Work project from Philipp Hofmann and Christian Bettstetter.

I will never forget the support and the beneficial discussions I had with my current and former
colleagues, especially the OPNET experts (Thushara Weerawardane, Xi Li, Yasir Naseer Zaki),
Mathlab expert Liang Zhao and networking experts (Chunlei An, Andreas Könsgen, Amanpreet
Singh, Bernd-Ludwig Wenning and Markus Becker). It was a pleasure to have worked in
different projects with my colleagues. Martina Kammann’s administrative skills and Karl-Heinz
Volk’s technical skills were always available whenever I needed them. The students whom I
have supervised, especially Chunlei An, Xiao Sun and Stephane Batassi, have provided me with
insights into related research areas through their work on Diploma and Master Theses.

All this work would have been practically impossible if it were not for Hasini, my little
daughter, being happy at the Uni-Kids daycare. She enjoyed her stay at Uni-Kids that provided
me the opportunity to work peacefully. Last but not least, Asanga, my husband supported me
not only concerning personal matters but also with technical issues. I can say that I had round-
the-clock tech support, especially related to programming issues.

Finally, it is with reverence and respect that I remember my mother and my late father for
creating an environment for me to pursue my education with all the hardships. ABSTRACT

A wireless multi-hop ad hoc network consists of a collection of nodes, which can communicate
without any fixed base stations or networking infrastructure. Multi-hop ad hoc networks are
ideally suited in areas such as sensor networking, community networking and networking used
in emergency situations. Since transmission is wireless and nodes could be mobile, ad hoc
networks bring about new challenges to be considered when designing routing algorithms.

Multipath routing discovers more than one route between a source node and a destination node
in a wireless multi-hop ad hoc network. These routes can be used simultaneously to distribute
traffic among several paths or used as backup paths. Multipath routing can provide benefits such
as load balancing, bandwidth aggregation, fault tolerance and improvement in QoS. The work
done in this thesis investigates the simultaneous use of multipath routes in wireless multi-hop ad
hoc networks.

In wireless multi-hop ad hoc networks, the simultaneous use of multiple routes may degrade the
performance of applications due to mutual interference of discovered paths, irrespective of
whether paths are physically node disjoint or link disjoint. Therefore, the selection of non-
interfering routes is the main criterion to be addressed when using multiple routes
simultaneously. This thesis introduces a new metric to select multiple routes by reducing the
effect of interference between paths as far as possible and also selecting the least congested
paths. The proposed protocol is named Radio Disjoint Multipath (RDM). The concept of the
RDM protocol which can be applied to both reactive and proactive ad hoc protocols is
developed and feasibility of the protocol is proven by an implementation and also through an
analytical model.

Furthermore, this thesis introduces a novel mechanism to distribute multiple flows as well as
packets of a single flow based on the properties of the discovered path, which is computed
considering the Background Traffic Load (BTL) of each path and the mutual interference
between paths. The single flow distribution is further investigated by replicating packets among
the RDM paths. This distribution is used to enhance the reliability in adverse environments such
as a fire-fighting scenario.

The evaluation of results is done considering the non-interfering RDM routing, the interfering
RDM routing and the single path routing. When using the RDM routes, two distribution
methods, viz., the single flow and the multiple flow distribution methods are considered. The
performance of the applications is compared using real application flows consisting of audio
conferencing, video transmissions, HTTP web accessing and FTP downloads that use different
scenarios with and without mobility. The analysis shows that the use of non-interfering RDM
routes simultaneously to distribute application flows significantly outperforms the use of single
path routing for most of the scenarios investigated.

In summary, all investigations presented in this thesis can help to enhance the application
performance in different kinds of wireless multi-hop ad hoc networks of Mobile Ad hoc
NETworks (MANET), Wireless Sensor Networks (WSN) and Wireless Mesh Networks
(WMN), by discovering RDM routes and using them simultaneously.

KURZFASSUNG

Ein drahtloses Multi-Hop-Ad-Hoc-Netz besteht aus einer Menge von Knoten, die ohne feste
Basisstationen oder Netzinfrastruktur miteinander kommunizieren können. Multi-Hop-Ad-Hoc-
Netze sind für Anwendungsfälle wie Sensornetze, freie Funknetze und Netze für
Notfallsituationen sehr gut geeignet. Da die Übertragung drahtlos ist und die Knoten beweglich
sein können, führen Ad-Hoc-Netze zu neuen Herausforderungen, die beim Entwurf von
Routingalgorithmen beachtet werden müssen.

Mehrwege-Routingverfahren ermitteln mehrere Routen zwischen einer Quelle und einer Senke.
Diese Routen können gleichzeitig verwendet werden, entweder um den Verkehr auf
verschiedene Pfade aufzuteilen oder als Ersatz-Pfade. Mehrwege-Routing bietet Vorteile wie
Lastverteilung, Bandbreiten-Aggregation, Fehlertoleranz und Verbesserung der Dienstgüte. Die
im Rahmen dieser Arbeit durchgeführten Untersuchungen betreffen die gleichzeitige Nutzung
von Mehrwege-Routen in drahtlosen Multi-Hop-Ad-Hoc-Netzen.

In drahtlosen Multi-Hop-Ad-Hoc-Netzen kann die gleichzeitige Verwendung mehrerer Routen
die Leistung von Anwendungen aufgrund gegenseitiger Störung beeinträchtigen, unabhängig
davon, ob die Pfade in Bezug auf ihre Knoten oder Verbindungen physikalisch disjunkt sind.
Daher ist die Auswahl interferenzfreier Routen das Hauptkriterium, das berücksichtigt werden
muss, wenn mehrere Routen gleichzeitig verwendet werden. Diese Arbeit stellt eine neue
Metrik zur Auswahl mehrerer Routen vor, bei der die Auswirkung von Interferenz zwischen
Pfaden so weit wie möglich reduziert wird und darüber hinaus die am wenigsten ausgelasteten
Pfade gewählt werden. Das vorgeschlagene Protokoll wird als Radio Disjoint Multipath (RDM)
bezeichnet. Das Konzept dieses RDM-Protokolls, das sowohl auf reaktive als auch auf
proaktive Ad-Hoc-Protokolle angewendet werden kann, wird im Rahmen dieser Arbeit
entwickelt, und die Durchführbarkeit des Protokolls wird durch eine Implementierung und
durch ein analytisches Modell nachgewiesen.

Darüber hinaus stellt diese Arbeit ein neues Verfahren vor, das sowohl mehrere Flüsse als auch
Pakete eines einzelnen Flusses basierend auf den Eigenschaften des ermittelten Pfades verteilt.
Die Berechnung dieser Eigenschaften berücksichtigt die Hintergrundlast (Background Traffic
Load, BTL) jedes Pfades und die gegenseitige Interferenz zwischen Pfaden. Die Verteilung
eines einzelnen Flusses mittels Replikation von Paketen auf den RDM-Pfaden wird weiter
untersucht. Diese Verteilung wird verwendet, um die Zuverlässigkeit in ungünstigen
Umgebungen, beispielsweise in einem Brandbekämpfungsszenario, zu verbessern.

Die Auswertung der Ergebnisse erfolgt unter Berücksichtigung des interferenzfreien RDM-
Routings, des interferenzbehafteten RDM-Routings und des Einzelpfad-Routings. Bei der
Verwendung des RDM-Routings werden zwei Verteilungsmethoden, nämlich die Verteilung
von Einzelflüssen und die Verteilung von mehreren Flüssen, berücksichtigt. Die
Leistungsfähigkeit der Anwendungen wird unter Verwendung realer Anwendungsflüsse,
bestehend aus Audiokonferenzen, Videoübertragungen, HTTP-Netzzugriffen und FTP-
Downloads, verglichen, die verschiedene Szenarien mit und ohne Mobilität verwenden. Die
Analyse zeigt, dass die Verwendung von interferenzfreien RDM-Routen zur Verteilung von
Anwendungsflüssen in den meisten untersuchten Szenarien deutlich leistungsfähiger ist als die
Verwendung eines Einzelpfad-Routings.

Zusammenfassend können alle Untersuchungen, die in dieser Arbeit präsentiert werden, dazu
beitragen, die Leistungsfähigkeit verschiedener Arten von drahtlosen Multi-Hop-Ad-Hoc-
Netzen wie mobilen Ad-Hoc-Netzen, drahtlosen Sensornetzen und drahtlosen Mesh-Netzen zu
verbessern, indem RDM-Routen ermittelt und gleichzeitig verwendet werden.
TABLE OF CONTENTS

1. Introduction ............................................................................................................................ 1
1.1 Overview of Wireless Multi-hop Ad hoc Networks ........................................... 1
1.1.1 Types of Ad Hoc Routing Protocols ...............................................2
1.1.2 Multipath Ad hoc Routing .................................................. 3
1.2 Motivation and Research Goals ........................4
1.3 Document Structure ........................................... 5
2. Related Work: A Review of Research on Multipath Routing .................................................. 7
2.1 Single Path Routing .................................................................... 7
2.2 Multipath Routing ..................................................................................9
2.2.1 Multipath Route Discovery Process ............ 9
2.2.2 Utilization of Multiple Routes ................. 11
2.2.2.1 Alternate Path Routing (APR) ........................................................... 11
2.2.2.2 Simultaneous Use of Multipath (SUM) routing ................................ 11
2.2.3 Path Maintenance, Path Evaluation and Re-discovery ............................. 12
2.3 Proposals for Multipath Routing Protocols ............................................13
2.3.1 AODV-BR: Backup Routing for AODV .................................................. 13
2.3.2 AOMDV: Ad hoc On-demand Multipath Distance Vector routing .......... 13
2.3.3 AODVM: AODV Multipath routing ...............................................14
2.3.4 MP-ODP: Multipath Routing for On-Demand Protocols ......................... 14
2.3.5 SMR: Split Multipath Routing ...............................15
2.3.6 MP-DSR: Multipath Dynamic Source Routing ........................................ 15
2.3.7 OMR: On-Demand Multipath Routing for Mobile Ad Hoc Networks ..... 17
2.3.8 DYMOM: DYMO Multipath Routing Protocol ............... 17
2.3.9 ZDR: Zone Disjoint Routes ...................................................................... 17
2.3.10 Summary of Existing Multipath Routing Protocols 18
2.4 Mutual Interference on Multipath Routing ............................... 18
2.4.1 Evaluation of Interfering Routes ............................................................... 18
2.4.2 Overview to RDM Routes .......................................20
3. Radio Disjoint Multipath Routing .......................................................................................... 23
3.1 RDM Routing Concepts ................................................................................... 23
3.1.1 RDM Route Discovery Process ......................................................24
3.1.1.1 Detection of Routing Loops .............. 25
3.1.1.2 Avoidance of Unnecessary Flooding of RREQs .....................25
3.1.2 RDM Path Selection Criteria .................................................................... 26
3.1.2.1 Computation of Background Traffic Load (BTL) ............................. 27
3.1.2.2 Computation of Interference .............................................................. 28
3.1.3 Sending of RDM RREP ..................32
3.1.4 RDM Flow Distribution Criteria ....................................... 33
3.1.5 RDM Path Maintenance ............................................................................ 34
3.1.6 RDM Dynamic Path Evaluation ........................................ 34
3.2 RDM Routing based on DYMO ............................................... 37
3.2.1 RDM aware DYMO Routing ..........38
3.3 Implementation of RDM Routing in the OPNET Simulator ............................ 39
3.3.1 DYMO Process Model ....................................................................40
3.3.2 Retrieval of NL and NI the WLAN MAC layer ............... 41
3.3.3 Distribution of Flows at the IP Layer .............................................42
3.3.3.1 Multiple Flow Distribution ................................................................ 42
3.3.3.2 Splitting of IP packets ......................................42
3.3.3.3 Replication of IP packets ................... 43
3.4 Implementation of RDM Routing in Real Environments ................................. 43
3.4.1 Node Interference Computation ................................................................ 43
3.4.2 Avoiding loss of RREQs Messages 44
3.4.3 Implementation of Distribution Methods .................................................. 45
3.5 Conclusion ........................................................................................................ 47
4. Review of Application Performance over Wireless Multi-hop Ad hoc Networks ................... 49
4.1 TCP behavior in Wireless Multi-hop Networks ............................................... 49
4.1.1 Overview of TCP Basics ........................................................................... 49
4.1.2 TCP Performance in Multi-hop Ad hoc Networks .50
4.1.2.1 TCP Reaction to Sudden Packet Losses ............................................ 50
4.1.2.2 TCP Reaction to Node Mobility ................................. 52
4.1.2.3 Triggering of Route Failure at the Network Layer ............................ 53
4.1.2.4 TCP Reaction to the Capture Condition ............................................ 53
4.1.2.5 Summary - TCP Reactions in Multi-hop Ad hoc Networks .............. 56
4.1.3 Improvement to TCP Performance in Multi-hop Ad Hoc Networks ........ 56
4.1.3.1 Modifications to Standard TCP ......................................................... 56
4.1.3.2cation to IEEE 802.11 MAC ................57
4.1.4 TCP Performance on Multipath Routing .................................. 58
4.1.4.1 TCP Performance over APR ............................58
4.1.4.2 TCPance over SUM Routing ........................ 58
4.1.5 Multipath TCP ........................................................60
4.2 UDP Performance in Wireless Multi-hop Networks ........................................ 61
4.2.1 TCP Performance in the Presence of UDP ........................ 61
4.3 TCP/UDP Performance over RDM Routing ............................ 61
5. Performance Evaluation of RDM Routing: SF and MF Distributions .................................... 63
5.1 Simulation Environment & Scenarios .............................................................. 63
5.1.1 Simulation Scenarios ................................................................................. 64
5.1.1.1 Basic Topology ................................... 64
5.1.1.2 String Topology .......... 65
5.1.1.3 Grid Topology ..................................................66
5.1.1.4 Random Topology ............................................................................. 68
5.1.1.5 Mobility Scenario 69
5.1.1.6 Evaluation of proposed algorithms .................................................... 70
5.1.2 Applications and Parameters used to Evaluate the Performance ....71
5.1.2.1 Video Transmission ................................................... 71
5.1.2.2 Audio Conferencing Flow ................................................................. 72
5.1.2.3 Single FTP Download ............................................... 73
5.1.2.4 HTTP Web Access ...................................................................73
5.2 MF and SF Distribution Algorithms ................................................................. 74
5.2.1 MF Distribution Algorithm .....................................76
5.2.1.1 Example - MF Distribution ................................................................ 77
5.2.2 SF Distribution Algorithm ......................................77
5.3 Simulative Performance Analysis: MF Distribution ........................................ 78
5.3.1 Basic Topologies .............................................................. 80
5.3.2 String Topology ................................................................ 82
5.3.3 Grid Topology .........83
5.3.4 Random Topology ...................................... 84
5.3.5 Mobility Scenario .............................................................. 85
5.3.6 Performance Analysis: SF distribution when multiple flows are present . 87
5.3.7mance Analysis: Standard SP vs SP discovered by RDM routing .. 89
5.4 Simulative Performance Analysis: SF Distribution ......................................... 90
5.4.1 Basic Topology ......................................................................................... 90
5.4.2 String Topology ................................................................ 94
5.4.3 Grid Topology .........98
5.4.4 Random Topology .................................... 100
5.4.5 Mobility Scenario ............................................................ 102
5.5 Conclusion ...................................................................................................... 105
6. Performance Evaluation of RDM Routing: Replicating ....................................................... 109
6.1 Deployment of MANET in Fire-fighting Scenarios ............... 109
6.1.1 Usage Scenario ........................................................................................ 110
6.1.2 Wireless Technology for Fire-fighting .................................................... 111
6.1.2.1 Wireless Propagation Test at BSPP ........................ 111
6.1.2.2 Performance of Multi-hop Ad hoc Networks .................................. 112
6.1.3 Research Issues – Deployment of Multiple Paths ........... 112
6.2 Issues in Replicating Packets .......................................................................... 112
6.3 Evaluation of RDM Routing (Replicating) .................................................... 115
6.3.1 Evaluation of RDM routing with replication in stationary networks ...... 116
6.3.2 Evaluaf RDM routing with replicating in mobile networks .......... 117
6.4 Conclusion ...................................................................................................... 120
7. Analytical Model: Determination of RDM Routes ............................................................... 121
7.1 Related Work .......................................................................... 121
7.2 Analytical Model: Determination of RDM Routes ...............................122
7.2.1 Model Description ........................................................... 122
7.2.2 Terminology ....................................124
7.2.2.1 Graph Theory ............ 124
7.2.2.2 Computation of Independent Sets .................................................... 126
7.2.2.3 Extended Max-Flow Problem ................................. 127
7.2.3 Interference Computation: 3x3 Grid Topology ....................................... 128
7.2.3.1 Simultaneously Not Active Links .................................................... 129
7.2.3.2 Simultaneously Active Interfering Links ................. 129
7.2.3.3 Simultaneously Active Non-Interfering Links ................................ 130
7.2.4 Selection of a Pair of RDM Routing Paths ............................................. 132
7.2.4.1 Computation of Sustainable Throughput ................. 132
7.2.4.2 Computation ofhput when BTL is Present ...... 1367.3 Implementation of Analytical Model ............................................................. 137
7.4 Evaluation of Analytical Results ............................................ 138
7.4.1 Comparison of Simulation and Analytical Environment ........................ 139
7.4.1.1 Sustainable throughput with optimal and non-optimal scheduling . 141
7.4.2 Basic Topologies ..................................................................................... 142
7.4.3 Grid Topology ................................................................. 143
7.4.4 String Topology ......144
7.4.5 5x5 Grid Topology with Background Traffic Load ................................ 146
7.5 Conclusions ............................................................................ 148
7.5.1 Comparison with Simulation results ....................................................... 148
7.5.2 Computational Cost of the Analytical Model ......................................... 149
7.5.3 Enhancements to the Analytical Model .......................... 150
8. Conclusion and Outlook ..................................................................................................... 151
9. Appendix I – Implementation Details ................................................................................. 155
9.1.1 Analytical model ..................................................................................... 155
9.1.2 Packet Replication and Discarding of Redundant Packets ..................... 158
10. Appendix II – Detailed Glossary .................................................................................... 159
10.1 Transmission Ranges used in IEEE 802.11 ................................................ 159
10.1.1 Transmission Range ................................................159
10.1.1.1 Carrier Sensing Range ..................................................................... 159
10.1.1.2 Interference Range .................................................... 159
10.2 Packet Drops in IEEE 802.11 ...................... 160
10.2.1 Hidden Node Problem ....................................................................160
10.2.2 RTS/CTS Handshake .............................................................................. 161
10.2.2.1 Unsuccessful RTS/CTS handshake ........................ 162
10.3 Effect of Maximum BTL in a node ............................................................ 166
10.4 Effect of RTS Threshold – SF & MF Distributions .................................... 167
10.5 Overhead Comparison of Promiscuous vs Non-promiscuous .................... 169
11. List of Figures ................................................................................................................ 171
12. List of Tables ................................................................................................................. 175
13. Glossary ........................................................................................................................ 179
13.1.1 List of Symbols ....................................................................................... 182
14. References .................................................................................................................... 185