251 pages
Deutsch

Modeling and Optimization Methods for Wireless Sensor and Mesh Networks [Elektronische Ressource] / Barbara Staehle. Betreuer: Phuoc Tran-Gia

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

Julius-Maximilians-UniversitätWürzburgInstitutfürInformatikLehrstuhlfürKommunikationsnetzeProf.Dr.P.Tran-GiaModeling and Optimization Methods forWireless Sensor and Mesh NetworksBarbara StaehleWürzburgerBeiträge zurLeistungsbewertungVerteilterSystemeBericht01/11Würzburger Beiträge zurLeistungsbewertung Verteilter SystemeHerausgeberProf. Dr. P. Tran-GiaUniversität WürzburgInstitut für InformatikLehrstuhl für KommunikationsnetzeAm HublandD-97074 WürzburgTel.: +49-931-31-86631Fax.: +49-931-31-86632email: trangia@informatik.uni-wuerzburg.deSatzReproduktionsfähige Vorlage der Autorin.AGesetzt in LT X Computer Modern 9pt.EISSN 1432-8801Modeling and Optimization Methods forWireless Sensor and Mesh NetworksDissertation zur Erlangung desnaturwissenschaftlichen Doktorgradesder Julius–Maximilians–Universität Würzburgvorgelegt vonBarbara StaehleausAnsbachWürzburg 2011Eingereicht am: 10.05.2011bei der Fakultät für Mathematik und Informatik1. Gutachter: Prof. Dr.-Ing. P. Tran-Gia2. Prof. em. Dr.-Ing. Dr. h.c. mult. Paul J. Kühn3. Gutachter: Prof. Dr.-Ing. Christoph MecklenbräukerTag der mündlichen Prüfung: 28.07.2011DanksagungDank für die Sonne, Dank für den Wind,Dank für die Menschen, die um mich sind.Dank für die Freunde, die mit mir gehn,und Dank für alle, die mich verstehn.

Sujets

Informations

Publié par
Publié le 01 janvier 2011
Nombre de lectures 30
Langue Deutsch
Poids de l'ouvrage 2 Mo

Julius-Maximilians-UniversitätWürzburg
InstitutfürInformatik
LehrstuhlfürKommunikationsnetze
Prof.Dr.P.Tran-Gia
Modeling and Optimization Methods for
Wireless Sensor and Mesh Networks
Barbara Staehle
WürzburgerBeiträge zur
LeistungsbewertungVerteilterSysteme
Bericht01/11Würzburger Beiträge zur
Leistungsbewertung Verteilter Systeme
Herausgeber
Prof. Dr. P. Tran-Gia
Universität Würzburg
Institut für Informatik
Lehrstuhl für Kommunikationsnetze
Am Hubland
D-97074 Würzburg
Tel.: +49-931-31-86631
Fax.: +49-931-31-86632
email: trangia@informatik.uni-wuerzburg.de
Satz
Reproduktionsfähige Vorlage der Autorin.
AGesetzt in LT X Computer Modern 9pt.E
ISSN 1432-8801Modeling and Optimization Methods for
Wireless Sensor and Mesh Networks
Dissertation zur Erlangung des
naturwissenschaftlichen Doktorgrades
der Julius–Maximilians–Universität Würzburg
vorgelegt von
Barbara Staehle
aus
Ansbach
Würzburg 2011Eingereicht am: 10.05.2011
bei der Fakultät für Mathematik und Informatik
1. Gutachter: Prof. Dr.-Ing. P. Tran-Gia
2. Prof. em. Dr.-Ing. Dr. h.c. mult. Paul J. Kühn
3. Gutachter: Prof. Dr.-Ing. Christoph Mecklenbräuker
Tag der mündlichen Prüfung: 28.07.2011Danksagung
Dank für die Sonne, Dank für den Wind,
Dank für die Menschen, die um mich sind.
Dank für die Freunde, die mit mir gehn,
und Dank für alle, die mich verstehn.
Johannes Jourdan (1923 - )
Diese Arbeit ist das Resultat fünfjähriger Forschungsarbeit am Lehrstuhl für
Kommunikationsnetze, während derer ich nicht nur Höhen sondern auch Tiefen
erlebt habe. Im Folgenden möchte ich daher all den Menschen danken die mir
während dieser Zeit in vielfältiger Weise beigestanden sind.
Mein erster Dank gebührt natürlich meinem Doktorvater Prof. Dr.-Ing. Phuoc
Tran-Gia dessen Impulse und Denkanstöße meiner Arbeit die richtige Richtung
gaben und der mir die Freiheit gab, die Ideen zu verwirklichen, die ich spannend
fand. Weiteren Dank schulde ich Prof. em. Dr.-Ing. Dr. h.c. mult. Paul J.
Kühn und Prof. Dr.-Ing. Christoph Mecklenbräuker für die Begutachtung meiner
Arbeit und ihre wertvollen Kommentare. Ein Dankeschön geht außerdem an
Prof. Dr. Klaus W. Wagner für die souveräne Leitung meiner Disputation und an
Prof. Dr. Reiner Kolla der sich als weiterer Prüfer zur Verfügung stellte.
Herrn Prof. Tran-Gia habe ich es zu verdanken dass ich im Zuge der Mitarbeit
an Projekten und Konferenzteilnahmen Kontakte zu anderen Wissenschaftlern
knüpfen und so meinen Horizont in vielen Richtungen erweitern konnte. Ins-
besondere bin ich Dr. Norbert Vicari und Michael Bahr für praxisrelevante Ein-
sichten in die IEEE 802.15.4 und IEEE 802.11s Standards dankbar. Je me sais
redevable de m’avoir permis partager leurs connaissances en géometrie stochas-
iDanksagung
tique à Prof. Dr. Bartłomiej Błaszczyszyn et Prof. Dr. François Baccelli. I also
˙owe many thanks to Prof. Dr. Michał Pióro, Dr. Mateusz Zotkiewicz, and Prof.
Dr. Di Yuan for showing me new dimensions of optimization methodologies.
Den Studenten deren Bachelor- oder Diplomarbeiten ich betreut habe, ver-
danke ich neue Sichtweisen auf Problemstellungen, Technik, oder Präsentations-
methoden. Insbesondere sind hier Matthias Kuhnert, Markus Weiß, Viktor Wen-
del, Matthias Hirth, Desheng Fu, Sebastian Deschner, Johann Scherer, Andreas
Wendl, Markus Leimbach, David Stezenbach und Andreas Blenk zu nennen.
Unabdingbar für meinen wissenschaftlichen Erfolg war jedoch auch das Klima
das Prof. Tran-Gia an seinem Lehrstuhl geschaffen hat und in dem ich mich sehr
wohl gefühlt habe. Meinen Kollegen bin ich dafür dankbar dass sie mich als eine
der ihren akzeptiert und mir mein Leben durch sehr viele technische, fachliche,
und programmiertechnische Hilfestellungen oder schlichtes Zuhören erleichtert
haben. Viele Kollegen sind auch zu Freunden geworden mit denen ich sehr viele
schöne Stunden außerhalb des Lehrstuhls beispielsweise mit Feiern, Radfahren,
Laufen, Cachen oder Klettern verbracht habe.
In fachlicher Hinsicht bin ich am meisten den Kollegen schuldig, die vor mir
ihre Doktorarbeit abgeschlossen. Insbesondere gilt mein Dank hier Dr. Dirk
Staehle der sehr oft meine fachliche Dunkelheit wie ein leuchtendes Feuer er-
hellte. Von Dr. Andreas Binzenhöfer, Dr. Andreas Mäder, Dr. Tobias Hossfeld,
Dr. Kenji Leibnitz und Dr. Rastin Pries lernte ich nicht nur fachliche Details,
sondern auch viel über die korrekte wissenschaftliche Sprache, Interpretation und
Aufbereitung von Ergebnissen, den Umgang mit Projektpartnern, Marathontak-
tik oder Skitechnik. Dr. Robert Henjes und Dr. Simon Oechsner möchte ich
besonders dafür danken dass sie immer ein offenes Ohr für mich hatten und mir
mit Rat und Tat zur Seite standen. Meinem CTO Florian Wamser habe ich es
zu verdanken dass alle Bewohner unseres AquareYoums aufs Vortrefflichste har-
monierten. Daniel Schlosser danke ich für seinen unerschütterlichen Optimismus
dass schon alles gut werden würde, Thomas Zinner für unzählige virtuelle zusam-
men gerauchte Zigaretten, Michael Duelli für manch strafenden Blick über den
Rand seiner Brille dem meist ein wertvoller Rat folgte. Meinen Mitbewohnern
iiDanksagung
Dr. Rüdiger Martin und Dominik Klein schulde ich tiefsten Dank für ihre Toler-
anz des Zustandes meiner Bürohälfte. Meinen Seilpartnern Matthias Hartmann
und Frank Lehrieder danke ich dafür dass sie mich an ihrem Wissen teilhaben
lassen und dass ich ihnen mein Leben anvertrauen kann so wie sie mir ihres an-
vertrauen. Für die Beantwortung technischer Fragen bin ich insbesondere meinen
jüngeren Kollegen Steffen Gebert, Matthias Hirth, David Hock, Michael Jarschel
und Christian Schwartz dankbar.
Nicht vergessen möchte ich Frau Gisela Förster deren organisatorische Unter-
stützung mir das Leben erleichtert hat. Frau Susann Schmitt ist es zu verdanken
dass ich nicht an den letzten Hürden vor der Disputation gescheitert bin.
Außer Frage steht dass die Unterstützung meiner Familie einen wesentlichen
Beitrag an dieser Arbeit hat. Vor allem meinen Eltern Monika und Dr. Leonhard
Emmert kann ich es nie vergelten dass sie immer an mich geglaubt haben, beson-
ders in den Zeiten in denen ich dies selbst nicht tat. Das Wissen dass sie immer
vier offene Ohren, frisches Gemüse und einen Platz am Feuer für mich haben war
und ist eine beruhigende Konstante in meinem Leben.
Mein Mann Dirk Staehle freut sich wahrscheinlich ebenso sehr über die Vol-
lendung dieser Arbeit wie ich, da er mich oft an Abenden und Wochenenden mit
der Wissenschaft hat teilen müssen. Zum Glück hat er hierfür, genauso wie für
alle meine durch die Arbeit verursachten guten und schlechten Launen, immer
großes Verständnis gezeigt. Während ich diese Arbeit erstellt habe, hat er im-
mer zu mir gehalten und wenn er es auch nicht immer geschafft hat mich aufzu-
muntern, hat er doch stets für mein leibliches Wohl gesorgt. Dafür dass er mich
insbesondere in letzter Zeit in Liebe ertragen und so das Band des Friedens zwis-
chen uns bewahrt hat, bin ich ihm über alle Maßen dankbar.
iiiContents
1 Introduction 1
1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Modeling Wireless Sensor Network Energy Consumptions 9
2.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.1 A Survey on Wireless Sensor Networks . . . . . . . . . . 12
2.1.2 Modeling Energy Consumptions . . . . . . . . . . . . . 19
2.2 Framework for Energy Consumption Modeling . . . . . . . . . . 22
2.2.1 Radio Operation Costs . . . . . . . . . . . . . . . . . . 23
2.2.2 Daily Radio-Related Energy Consumptions . . . . . . . . 27
2.3 Influence of Energy Consumption Modeling . . . . . . . . . . . 31
2.3.1 Transmission Costs . . . . . . . . . . . . . . . . . . . . 31
2.3.2 Energy Efficient Routing Trees . . . . . . . . . . . . . . 33
2.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . 42
3 Enabling Standards-Based Wireless Sensor Networks 45
3.1 Background and Related Work . . . . . . . . . . . . . . . . . . 47
3.1.1 An Overview on IEEE 802.15.4 . . . . . . . . . . . . . . 48
3.1.2 An Introduction to ZigBee and AODV . . . . . . . . . . 55
3.1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . 59
3.2 Optimizing the IEEE 802.15.4 Nonbeacon-enabled Association
Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.2.1 Standard and Enhanced Asssociation Procedure . . . . . 64
vContents
3.2.2 Evaluation Framework . . . . . . . . . . . . . . . . . . 67
3.2.3 Association Mechanism Performance Evaluation . . . . . 69
3.3 Routing in Duty Cycing ZigBee Networks . . . . . . . . . . . . 78
3.3.1 Two Simple Sleep Scheduling Possibilities . . . . . . . . 78
3.3.2 Smooth AODV . . . . . . . . . . . . . . . . . . . . . . 79
3.3.3 Evaluation Framework . . . . . . . . . . . . . . . . . . 80
3.3.4 Comparison of Smooth and Regular AODV . . . . . . . 82
3.4 Sleep Scheduling in ZigBee Multi-hop Networks . . . . . . . . . 91
3.4.1 Cross-Layer Sleep Scheduling . . . . . . . . . . . . . . 91
3.4.2 Evaluation Framework . . . . . . . . . . . . . . . . . . 94
3.4.3 CLS Performance Evaluation . . . . . . . . . . . . . . . 95
3.5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . 100
4 Assessing the Max-Min Fair Wireless Mesh Network Through-
put 103
4.1 Background and Related Work . . . . . . . . . . . . . . . . . . 106
4.1.1 A Survey on Wireless Mesh Networks . . . . . . . . . . 106
4.1.2 Formal Description of a Wireless Mesh Network . . . . . 111
4.1.3 Wireless Mesh Network Topology Generation . . . . . . 114
4.1.4 Related Work . . . . . . . . . . . . . . . . . . . . . . . 116
4.2 Max-Min Fair Flow Rate Allocation Algorithms . . . . . . . . . 119
4.2.1 Existing Contributions . . . . . . . . . . . . . . . . . . 119
4.2.2 Multi-Hop Multi-Rate Extensions . . . . . . . . . . . . 125
4.3 Comparison of Max-Min Fair Rate Allocations . . . . . . . . . . 129
4.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . 133
5 Optimizing the Wireless Mesh Network Performance via Link
Rate Assignment 137
5.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
5.2 Link Rate Assignment . . . . . . . . . . . . . . . . . . . . . . . 142
vi