Performance issues of MAC and routing protocols in wireless sensor networks [Elektronische Ressource] / vorgelegt von Alexander Klein

Sujets

• Informatik

Informations

• Publié par: julius-maximilians-universitat_wurzburg
• Publié le: 01 janvier 2010
• Nombre de lectures: 48
• Langue: Deutsch
• Poids de l'ouvrage: 5 Mo

Extrait

Bayerische Julius-Maximilians-Universität Würzburg
Institut für Informatik
Lehrstuhl für Verteilte Systeme
Prof. Dr. P. Tran-Gia
Performance Issues
of MAC and Routing Protocols
in Wireless Sensor Networks
Alexander Klein
Würzburger Beiträge zur
Leistungsbewertung Verteilter Systeme
Bericht 3/10Würzburger Beiträge zur
Leistungsbewertung Verteilter Systeme
Herausgeber
Prof. Dr. P. Tran-Gia
Universität Würzburg
Institut für Informatik
Lehrstuhl für Verteilte Systeme
Am Hubland
D-97074 Würzburg
Tel.: [phone]
Fax.: [phone]
email: [e-mail]
Satz
Reproduktionsfähige Vorlage vom Autor.
AGesetzt in LT X Computer Modern 9pt.E
ISSN 1432-8801Performance Issues
of MAC and Routing Protocols
in Wireless Sensor Networks
Dissertation zur Erlangung des
naturwissenschaftlichen Doktorgrades
der Bayerischen Julius–Maximilians–Universität Würzburg
vorgelegt von
Alexander Klein
aus
Würzburg
Würzburg 2010Eingereicht am: 25.05.2010
bei der Fakultät für Mathematik und Informatik
1. Gutachter: Prof. Dr.-Ing. P. Tran-Gia
2. Gutachter: Prof. Dr.-Ing. R. Kolla
Tag der mündlichen Prüfung: 16.11.2010Danksagung
Zunächst möchte ich allen danken, die mich im Rahmen dieser Promotion be-
gleitet, motiviert und unterstützt haben.
An erster Stelle möchte ich hiermit meinen besonderen Dank meinem Doktor-
vater Prof. Dr.-Ing. Phuoc Tran-Gia aussprechen, der sich zusammen mit mir auf
das Abenteuer einer Promotion im industriellen Umfeld eingelassen hat. Seine
uneingeschränkte Unterstützung hat es mir selbst in diesem oft marktgetriebe-
nen Umfeld ermöglicht, die aus wissenschaftlicher Sicht interessantesten The-
men zu bearbeiten. Ohne seine Hilfe und seinen fachlichen Rat wäre eine derart
detaillierte Bearbeitung der Themen nicht möglich gewesen.
Des Weiteren möchte ich Herrn Prof. Dr. Reiner Kolla für das Erstellen des
Zweitgutachtens, seine Funktion als Prüfungsvorsitzender und nicht zuletzt für
die ansprechenden Diskussionen und Anmerkungen bezüglich der Kommunika-
tionsprotokolle danken. Darüber hinaus gilt mein Dank Prof. Dr. Klaus Schilling,
der in seinem stets gut gefüllten Terminkalender zeitnah Platz für meine Dispu-
tation gefunden hat.
Für die Hilfe und fachliche Unterstützung möchte ich mich bei Dr. Dirk Stähle
und Dr. Rastin Pries bedanken. Ihr ehrliches Feedback und die sich daraus en-
twickelnden Diskussionen haben wesentlich zu dieser Arbeit beigetragen. In
meiner Zeit als Doktorand bei EADS konnte ich viel über die Arbeitsabläufe
im industriellen Umfeld lernen. Neben dem fachlichen Know-how konnte ich
dort auch zahlreiche positive menschliche Erfahrungen sammeln. Dabei möchte
ich meinen ehemaligen Kollegen bei EADS einen besonderen Dank aussprechen:
Martin Kluge, Manuel Saez, Jirka Klaue, Sebastian Voss, Johannes Schels, Thilo
Fath, Pascal Vermeer, Christoph Aulitzky, Christoph Heller, Dr. Bernhard Schön-
iDanksagung
linner, Dr. Sergio Bovelli, Stefan Schneele und Josef Schalk.
Mein herzlichster Dank gebührt Frau Helga Bayer, die mir mit ihrer
schnellen, unbürokratischen Unterstützung insbesondere bei zeitkritischen or-
ganisatorischen Angelegenheiten das Leben bei EADS sehr erleichtert hat. Das
letzte halbe Jahr meiner Promotionszeit durfte ich an der Technischen Univer-
sität München am Lehrstuhl für Netzarchitekturen und Netzdienste verbringen.
Mein Dank gilt an dieser Stelle Prof. Dr. Georg Carle, der mir insbesondere in der
Endphase der Promotion den nötigen Freiraum gegeben hat, die Arbeit zeitnah
fertigzustellen.
Neben dem fachlichen Umfeld trägt vor allem das private Umfeld zum erfol-
greichen Abschluss einer Promotion bei. Deshalb möchte ich meinen aufrichti-
gen Dank meinen Eltern Brigitte und Erich Klein sowie meiner Schwester An-
nette Klein widmen, die mich immer ungefragt unterstützt und motiviert haben.
Abschließend möchte ich meinen tiefsten Dank meiner Partnerin Madeleine
von Bodisco aussprechen, die mit großem Verständnis Einschränkungen in der
gemeinsamen Freizeit akzeptiert hat und meine wichtigste private Stütze in dieser
entbehrungsreichen Zeit war.
iiContents
1 Introduction 1
1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Medium Access Control in Wireless Sensor Networks 9
2.1 Aspects of Communication . . . . . . . . . . . . . . . . . . . . 10
2.2 Taxonomy of MAC Protocols . . . . . . . . . . . . . . . . . . . 16
2.2.1 Random Access . . . . . . . . . . . . . . . . . . . . . . 16
2.2.2 Slotted Access . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.3 Frame-based Access . . . . . . . . . . . . . . . . . . . . 17
2.2.4 Hybrid Access . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.5 Polling . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.6 Token-Passing . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 A Survey on MAC Protocols . . . . . . . . . . . . . . . . . . . 21
2.3.1 CSMA . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.2 S-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.3.3 Sift . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.3.4 Wise-MAC . . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.5 X-MAC . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4 Communication Issues of Low-Power Transceivers . . . . . . . . 37
2.4.1 Impact of the Turnaround Time . . . . . . . . . . . . . . 38
2.4.2 The Problem of Clear Channel Assessment Delay . . . . 41
iiiContents
2.5 Backoff Preamble-based MAC Protocol with Sequential Con-
tention Resolution . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.5.1 Single-Sequence Medium Access Procedure . . . . . . . 44
2.5.2 Multiple-Sequence Medium Access Procedure . . . . . . 46
2.5.3 Single-Sequence - Analysis of the Contention Resolution 49
2.5.4 Multiple-Sequence - Analysis of the Contention Resolution 53
2.5.5 Backoff Optimization . . . . . . . . . . . . . . . . . . . 56
2.5.6 Simulative Performance Comparison of the CSMA and
the BPS-MAC Protocol . . . . . . . . . . . . . . . . . . 62
2.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3 Routing in Wireless Sensor Networks 73
3.1 Classification of Routing Protocols . . . . . . . . . . . . . . . . 75
3.1.1 Route Establishment . . . . . . . . . . . . . . . . . . . 75
3.1.2 Network Structure . . . . . . . . . . . . . . . . . . . . . 79
3.1.3 Protocol Operation . . . . . . . . . . . . . . . . . . . . 82
3.2 Routing Tasks . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.2.1 Forwarding . . . . . . . . . . . . . . . . . . . . . . . . 85
3.2.2 Processing . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.2.3 Topology . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2.4 Dissemination of Routing Information . . . . . . . . . . 87
3.3 Routing Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . 90
3.3.1 Classification of Routing Metrics . . . . . . . . . . . . . 90
3.3.2 Discussion of Different Routing Metrics . . . . . . . . . 92
3.4 Survey on Routing Protocols . . . . . . . . . . . . . . . . . . . 96
3.4.1 Ad hoc On-Demand Distance Vector . . . . . . . . . . . 97
3.4.2 Dynamic Source Routing . . . . . . . . . . . . . . . . . 99
3.4.3 Open Link State Routing . . . . . . . . . . . . . . . . . 100
3.4.4 Directed Diffusion . . . . . . . . . . . . . . . . . . . . . 101
3.4.5 Low-Energy Adaptive Clustering Hierarchy . . . . . . . 103
3.4.6 Multipath Multi-Speed Protocol . . . . . . . . . . . . . . 104
ivContents
3.5 Statistic-Based Routing Protocol . . . . . . . . . . . . . . . . . 105
3.5.1 Basic Functionality . . . . . . . . . . . . . . . . . . . . 106
3.5.2 Topology Changes . . . . . . . . . . . . . . . . . . . . . 109
3.5.3 Routing Metric . . . . . . . . . . . . . . . . . . . . . . 111
3.5.4 Extended Functionality . . . . . . . . . . . . . . . . . . 113
3.5.5 Delay-based Approach . . . . . . . . . . . . . . . . . . 116
3.5.6 Simulative Performance Evaluation of the SBR Protocol . 125
3.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
4 Evaluation of Routing Protocols 135
4.1 Simulation Framework . . . . . . . . . . . . . . . . . . . . . . 137
4.1.1 Introduction to the OPNET Modeler . . . . . . . . . . . 138
4.1.2 Basic Framework . . . . . . . . . . . . . . . . . . . . . 139
4.1.3 Co-operative Simulation . . . . . . . . . . . . . . . . . 146
4.1.4 Hardware-In-The-Loop . . . . . . . . . . . . . . . . . . 147
4.1.5 Video Quality Evaluation . . . . . . . . . . . . . . . . . 150
4.1.6 Extended Framework . . . . . . . . . . . . . . . . . . . 151
4.2 Mobility Patterns . . . . . . . . . . . . . . . . . . . . . . . . . 155
4.2.1 Characteristics of Mobility Patterns . . . . . . . . . . . . 157
4.2.2 Survey on Mobility Patterns . . . . . . . . . . . . . . . . 161
4.2.3 Impact of Mobility on Routing . . . . . . . . . . . . . . 177
4.2.4 Real World Traces vs. Mobility Patterns . . . .