Diplomarbeit Routing in Sensornetzen (fast) ohne Speicher

Transcrição

Diplomarbeit
Informatik
Routing in Sensornetzen
(fast) ohne Speicher
vorgelegt von
Kerstin Voß
Matrikelnummer: 6096475
Betreuer:
Dr. rer. nat. Christian Schindelhauer
Diplomarbeit
Routing in Sensornetzen (fast) ohne Speicher
an der:
Universität Paderborn
Fachgebiet Algorithmen und Komplexität
Dr. rer. nat. Christian Schindelhauer
Fürstenallee 11
33102 Paderborn
Erklärung
Ich versichere, dass ich diese Arbeit selbstständig angefertigt und keine anderen als die
angegebenen und bei Zitaten kenntlich gemachten Quellen und Hilfsmittel benutzt habe.
Paderborn, den 29. März 2005
—————————
(Kerstin Voß)
i
Inhaltsverzeichnis
1 Einleitung
1.1
2
Motivation für das Forschungsinteresse in Sensornetzen . . . . . . . . . . .
2
1.1.1
Algorithmische Probleme . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2
Ziel und Aufbau der Arbeit . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Einführung in Sensornetze . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.3.1
Charakteristische Eigenschaften . . . . . . . . . . . . . . . . . . . .
5
1.3.2
Einsatzgebiete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
2 Aufgabenstellung
12
2.1
Hardwarespezifikation
2.2
Das Szenario “Supermarkt“ . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1
Situationsbeschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2
Explizite Voraussetzungen . . . . . . . . . . . . . . . . . . . . . . . 15
3 Stand der Forschung
3.1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
30
Das 1 QK-Protokoll im Überblick . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.1
Ein erster Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.2
Distanz zum Server - die Expected Power Distance . . . . . . . . . 35
3.1.3
uplink-Kommunikation . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.1.4
downlink Kommunikation . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.5
weitere Nachrichtentypen . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.6
Bezug zum ISO/OSI Modell . . . . . . . . . . . . . . . . . . . . . . 44
INHALTSVERZEICHNIS
3.1.7
3.2
iii
Schwachstellen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Bestehende Routingverfahren . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.2.1
Routingverfahren für mobile Ad-hoc Netze . . . . . . . . . . . . . . 51
3.2.2
Das Pulse Protokoll . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.3
Data Collection Protokoll . . . . . . . . . . . . . . . . . . . . . . . 56
3.2.4
Direct Diffusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2.5
Insgesamte Beurteilung der Routingverfahren . . . . . . . . . . . . 61
4 Synchronisation
62
4.1
Einsatz klassischer Synchronisierungsalgorithmen in Sensornetzen . . . . . 62
4.2
Synchronisationsverfahren für Sensornetze . . . . . . . . . . . . . . . . . . 63
4.3
4.2.1
Time Stamp Synchronization . . . . . . . . . . . . . . . . . . . . . 64
4.2.2
Reference Broadcast Synchronization . . . . . . . . . . . . . . . . . 65
4.2.3
Timing Sync Protocol for Sensor Networks . . . . . . . . . . . . . . 69
4.2.4
Beurteilung der drei Verfahren . . . . . . . . . . . . . . . . . . . . . 71
Globales kontra lokales synchrones Aufwachen . . . . . . . . . . . . . . . . 72
4.3.1
Regalweise Synchronisation . . . . . . . . . . . . . . . . . . . . . . 72
4.3.2
Global synchronisierter Aufwachpunkt . . . . . . . . . . . . . . . . 74
4.3.3
Vergleich der Ansätze . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5 Frequenzwahl
5.1
82
Gleichverteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.1.1
Abschätzungen für den Erfolg der Gleichverteilung
. . . . . . . . . 86
5.2
Geometrische Verteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.3
Faktorisierte geometrische Verteilung . . . . . . . . . . . . . . . . . . . . . 95
5.3.1
Abschätzungen für den Erfolg der faktorisierten geometrischen Verteilung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
5.4
Beurteilung der einzusetzenden Wahrscheinlichkeitsverteilung . . . . . . . . 100
5.4.1
Beispielrechnungen für die regalweise Synchronisation . . . . . . . . 100
5.4.2
Einzusetzender Faktor in der faktorisierten geometrischen Verteilung 110
INHALTSVERZEICHNIS
iv
5.4.3
Vergleichsverläufe des Erwartungswertes . . . . . . . . . . . . . . . 117
5.4.4
Kombination für das optimierte 1 QK-Protokoll . . . . . . . . . . . 119
6 Fairness des Routings
124
7 Auswirkungen auf das 1 QK-Protokoll
134
7.1
Beschreibung der Modifikationen . . . . . . . . . . . . . . . . . . . . . . . 134
7.2
Veränderte Spezifikation - Release 3.0 . . . . . . . . . . . . . . . . . . . . . 136
8 Zusammenfassung
8.1
138
Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
A Quellcode
140
A.1 Dokumentation und Code zur regalweisen Synchronisation . . . . . . . . . 140
A.2 Release 3.0 des 1 QK-Protokolls . . . . . . . . . . . . . . . . . . . . . . . . 148
B Verzeichnisse
160
B.1 Literaturverzeichnis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
B.2 Glossar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
Abbildungsverzeichnis
168
INHALTSVERZEICHNIS
1
Kapitel 1
Einleitung
1.1
Motivation für das Forschungsinteresse in Sensornetzen
Sensornetze sind die Datenerfassungsnetzwerke der Zukunft! Die integrierten Stationen
erfassen sensorisch physische Umwelteigenschaften und leiten diese an eine Zentralstation
weiter. Die Stationen, genannt Sensorknoten, können Eigenschaften wie zum Beispiel
Licht, Temperatur, Feuchtigkeit, Erschütterung, Beschleunigung, aber auch akustische
Signale messen. Die Aufgabe eines einzelnen Knotens besteht zunächst aus dem Auslesen
der Sensordaten, anschließender Bearbeitung sowie dem Versenden von diesen [Fr 03].
Eines der wichtigen Ziele in der Entwicklung von Sensorknoten ist ihre Kostengünstigkeit.1
So werden Sensorknoten oft nur bis zur Erschöpfung ihrer eigenen Energiequelle verwendet. Um sie möglichst preiswert zu produzieren, werden die Kleinstrechner nur
mit einer stark begrenzten Hardware ausgestattet. Auf kleinstem Raum sind Sensor,
Prozessor, Speicher (RAM und FLASH), eine Kommunikationseinheit sowie eine autarke
Energiequelle integriert (siehe Abbildung 1.1) (siehe auch [Wa 01]). In den meisten
Einsatzgebieten wird eine Funkeinheit zur Kommunikation benutzt. Eine drahtlose
Kommunikation hat schließlich den Vorteil, dass die Stationen ihre Position verändern
können. Zudem ist das Netz leichter zu installieren.
Das Ziel eines Sensornetzes ist es, erfasste Sensordaten an eine zentrale Einheit
weiterzuleiten [Va, Ch]. Da die Knoten meistens batteriebetrieben sind, besitzen sie in
der drahtlosen Kommunikation nur eine geringe Sendereichweite. So ist im Allgemeinen
1
Der vorausgesagte Preis in zwei Jahren für einen Knoten wie in Abbildung 1.1 wird auf 10 US-Dollar
geschätzt [Va, Ch].
1 Einleitung
3
Abbildung 1.1: Beispiel eines Sensorknotens, Quelle: [Va, Ch]
keine direkte Kommunikation mit dem Server möglich. Nachrichten müssen mit Hilfe
von anderen Stationen zum Server weitergeleitet werden. Die wichtigste Aufgabe eines
Sensorknotens beschränkt sich damit nicht mehr auf die Datenerfassung und - versendung. Ein ebenso elementares Problem ist die Nachrichtenweiterleitung durch das Netz,
das Routing .
Sensorknoten stehen am Ende einer Entwicklung von immer kleiner werdenden
mobilen Endgeräten (Laptops, PDAs, programmierbare Handies . . . ) [Hae 05]. Sie sind
die kleinsten und energieeffizientesten aller vorherigen Entwicklungen. Wegen diesen
Eigenschaften sind sie von großem Nutzen und haben undenkbar viele Einsatzgebiete.
In Zukunft werden solche Netze vermutlich in vielen alltäglichen Gegenständen integriert
sein. Eingebaut zum Beispiel in intelligenten Gebäuden oder in Fahrzeugen. Ihre Aufgabe
besteht dann im “Erfühlen“ der Umgebung und der automatischen Anpassung des
jeweiligen Verhaltens technischer Systeme aus den erfassten Umweltveränderungen.
Netze aus vielen solchen Knoten gestatten die weiträumige Beobachtung von
”
Phänomenen der realen Welt mit großer Genauigkeit, ohne dabei die physischen
Prozesse wesentlich zu beeinflussen. Sensornetze sollen daher in vielen Anwendungsgebieten einen hohen Nutzen stiften.“[Fr 03]
Entgegen der starken Ressourcenbeschränkungen ist die Anzahl der Knoten in einem Sensornetz meistens hoch. Die Knoten in näherer Umgebung dienen als direkte
Kommunikationspartner. In vielen Fällen entsteht so aus der Vielzahl der Knoten
ein dichter Kommunikationsgraph. Besteht ein dichter Graph, kann die nicht sehr
ausgeprägte Sendereichweite vernachlässigt werden.
1 Einleitung
1.1.1
4
Algorithmische Probleme
Algorithmische Probleme in Sensornetzen (wie zum Beispiel das Routing) sind im
Prinzip auch schon von Kommunikationsnetzen bzw. Ad-Hoc-Netzen bekannt [Ka 05].
Aufgrund der begrenzten Hardwareeigenschaften von Sensorknoten sind allerdings neue
algorithmische Modelle und Verfahren erforderlich (siehe dazu 3.2).
Alle Algorithmen für Sensornetze sind darauf bedacht, die Vielzahl der Knoten so
auszunutzen, dass im gemeinsamen Zusammenspiel die bestehenden Anforderungen
(zum Beispiel eine große Sendereichweite, großer Speicherplatz, Erkennung der räumliche
Anordnung der Sensorknoten . . . ) erfüllt werden. Gelingt dies, so sind Sensornetze nicht
nur sehr mächtig2 sondern auch extrem robust gegenüber Ausfällen. Daher skalieren sie
gut mit zu- oder abnehmender Knotenanzahl.
1.2
Ziel und Aufbau der Arbeit
Die Diplomarbeit beschäftigt sich mit einer der elementarsten Aufgaben in Sensornetzen, dem Routing. Dabei wird auf einer speziellen Hardwarekonfiguration der Knoten
aufgesetzt. So sind die Knoten zum Beispiel mit nur 256 Byte RAM ausgestattet. Des
Weiteren wird als Grundlage das 1 QK-Protokoll genutzt, welches an der Universität
Paderborn in der Fachgruppe Meyer auf der Heide unter der Leitung von Dr. Christian
Schindelhauer entwickelt wurde [Sch 04/04], [Sch 04-R02].
Das Routingverhalten des 1 QK-Protokolls wird auf zwei Wegen modifiziert: Die
Veränderungen liegen in der Frequenzwahl für den Sende- und Empfangsvorgang sowie
in der Weiterleitung von Nachrichten. Mittels dieser Modifikationen treten weniger
Störungen in der Kommunikation auf. Das Protokoll wird effizienter und gewinnt an
Fairness.
Die Arbeit gliedert sich wie folgt:
Der folgende Abschnitt (siehe 1.3) wird eine kleine Einführung in Sensornetze geben. Im
zweiten Kapitel wird die genaue Aufgabenstellung der Arbeit erläutert. Anschließend
folgt ein Überblick über den Stand der Forschung. Mit dem vierten Kapitel beginnt die
Beschreibung der Modifikationen:
Das 1 QK-Protokoll arbeitet mit unsynchronisierten Knoten. In der Diplomarbeit
wird eine Synchronisation eingesetzt. Geeignete Synchronisationsverfahren werden im
vierten Kapitel “Synchronisation“ beschrieben. Im Kapitel “Kanalwahl“ gehe ich auf
2
Mit Hilfe einer räumlichen Orientierung eröffnen sich viele weitere Einsatzgebiete.
1 Einleitung
5
die Modifikationen bezüglich der Frequenzwahl beim Senden und Empfangen ein. Die
Erreichung von Fairness im Routingverhalten wird im sechsten Kapitel erläutert. Im
Anschluss an diese Veränderungen werden die Auswirkungen auf das 1 QK-Protokoll
aufgeführt. Die Arbeit endet mit einer Zusammenfassung und einem Ausblick auf weitere
Optimierungen des 1 QK-Protokolls.
1.3
Einführung in Sensornetze
Zum besseren Verständnis von Sensornetzen wird eine kurze Einführung gegeben.
Zunächst werden die wichtigsten Eigenschaften, die bereits zuvor angemerkt wurden,
zusammengefasst und erläutert. Anschließend stelle ich einige Einsatzgebiete zur Veranschaulichung vor.
1.3.1
Charakteristische Eigenschaften
Sensorknoten bestehen aus Speicher, Rechenleistung, einer Kommunikationseinheit und
einer Energieversorgung [Hae 05]. Diese Ressourcen sind meistens stark begrenzt. Vor
allem wird die Leistungsfähigkeit eines Knotens dadurch beschränkt, dass er seine Energie
aus einer Batterie erhält. Daher ist die Hauptaufgabe aller Algorithmen der sparsame
Energieverbrauch.
Trotz der starken Ressourceneinschränkungen ist auf vielen Sensorknoten ein Betriebssystem lauffähig. TinyOS ist ein weitverbreitetes speziell für Sensorknoten entwickeltes
Betriebssystem der University of California in Berkeley [Ti 04]. Es unterstützt eine
einfache Programmierung der Sensorknoten sowie Flexibilität im Scheduling durch eine
ereignisgesteuerte Ausführung. Damit werden die Eigenschaften von drahtlosen Sensornetzen und ihrer physischen Umgebung vollkommen berücksichtigt. Schließlich sollen
auf gewisse Ereignisse ohne Verzögerung Reaktionen erfolgen. Für schnellst mögliche
Reaktionen ist es notwendig, dass diese im Scheduling an die erste Position rückt.
Die Architektur von TinyOS ist komponentenbasiert. So sind zum Beispiel Netzwerkprotokolle oder Treiber für Sensoren in den Bibliotheken enthalten und können in den
eigenen Applikationen problemlos eingesetzt werden.
Die Hardware der Kommunikationseinheit entscheidet über drahtlosen oder drahtgebundenen Nachrichtenaustausch. Die drahtlose Kommunikation hat sicherlich einige
Vorteile: Es werden keine festen Verbindungen zwischen den Knoten benötigt, sie sind
1 Einleitung
6
somit leichter zu installieren und beweglich. Je nach Eigenschaften der Funkeinheit
(Radio-Transceiver) stehen den Knoten verschiedene Frequenzbereiche (Kanäle) zur
Verfügung, auf denen sie senden und empfangen können. Die Funkeinheit sendet innerhalb eines Senderadius und alle Sensorknoten innerhalb des Bereiches (und im gleichen
Frequenzbereich) können die Signale hören. In einer dichten Umgebung sind damit mit
einem Kommunikationsversuch zahlreiche Nachbarn erreichbar.
Um die gleiche Anzahl von Nachbarn mit einer festen Verkabelung zu erreichen,
bedarf es ohne Netzwerk einer hohen Anzahl von Kabeln:
Sollen N Knoten mit jedem anderen Knoten kommunizieren können, müssen alle
miteinander verbunden sein. Es werden
T = N − 1 + N − 2 + N − 3 . . . + 1 ≤ N2
Kabel benötigt, wenn mit jedem Kabel die Kommunikation in beide Richtungen möglich
ist.
Werden die Sensorknoten in einem Netzwerk betrieben, so genügt meistens ein Kabel.
Das Medium wird dann jedoch zum Flaschenhals der Kommunikation [Cr 00, S.3 f].
Die drahtlose Kommunikation hat jedoch auch Nachteile: Störungen3 können auftreten.
Diese Interferenzen resultieren zum einen aus einer gegenseitigen Behinderung, das heißt
wenn zwei Knoten auf dem gleichen Kanal senden. Zum anderen treten Störungen durch
Einflüsse der unmittelbaren Umwelt auf: Gesendete Signale können von Gegenständen
oder Personen in unmittelbarer Umgebung abgelenkt werden. Wenn Gegenstände oder
Personen nur temporär die Verbindung stören, sind einige Nachbarn zeitweise nicht
erreichbar. Beim Routing bedarf es somit eines Handlings von dynamischen Nachbarn.
Die Dynamik ist ebenso erforderlich, da die Sensorknoten ihre Position ändern können
(sei es selbstständig oder durch menschlichen Einfluß). Ein Knoten muss daher die
Informationen über seine Nachbarschaft stets aktualisieren.
Aufgrund der Dynamik in den Routingalgorithmen sind drahtlose Sensornetze selbsterzeugend und selbstorganisierend [Ra, Mi, S.1]. Die Kommunikationspfade bestehen aus
Multi-Hops, da eine direkte Kommunikation mit dem Server meistens nicht möglich ist.
3
Definition Störung: negative Beeinträchtigungen der übertragenen Signale mit eventueller Konse”
quenz einer Nachrichtenverfälschung bzw. eines Nachrichtenverlustes“ [Wo 04, S.23]
1 Einleitung
1.3.2
7
Einsatzgebiete
Der Einsatz von Sensornetzen ist vielfältig. Die ersten Prototypen für drahtlose Sensornetze sind für die Umweltüberwachung, Katastrophenverhütung oder für Aufklärungszwecke
konzipiert worden ( Smart Dust“-Projekte). Anwendungsgebiete sind in der Beobachtung
”
großer Gebiete zu finden:
Umweltforscher erhoffen sich umfassendere und genauere Möglichkeiten zur
”
Überwachung der Ausbreitung von Verschmutzungen in Luft und Wasser; durch
Einbringen von Sensornetzen in Gebäude und Brücken will man den Einfluss von
seismischen Aktivitäten auf deren strukturelle Integrität besser erkennen; und Militärs
sind stark daran interessiert, Aktivitäten in unzugänglichem Gelände durch den Einsatz
von Sensornetzen zu überwachen.“[Fr 03] (vergleiche [Ak,Su 02])
Zudem sind Sensornetze bei einer Früherkennung sowie als Lokalisierungshilfe von
Brandherden in Waldbränden, der Tierbeobachtung und der Gebäude-/Geländesicherung
einzusetzen. Es folgen vier Beispielszenarien für Einsatzgebiete.
1. ZebraNet
ZebraNet ist der Name eines Forschungsprojektes der Princeton University. Das Migrationsverhalten von Zebras wird mittels GPS erforscht. Durch die alle acht Minuten
aufgenommenen GPS Angaben können detaillierte Angaben zu den Bewegungsmustern
der Tiere gemacht werden. Diese Angaben werden im zwei-Stunden-Rhythmus versucht
an einen Empfänger zu übermitteln (siehe Abbildung 1.2). Als Empfänger dienen andere
Zebras zur Weiterleitung, falls keine Basisstation erreichbar ist. Also liegt eine store-and
forward Kommunikation vor.
Abbildung 1.2: Kommunikation im ZebraNet, Quelle: [Sa 04, S.2]
1 Einleitung
8
Die Zebras tragen eine Halsmanschette (siehe Abbildung 1.3), in welcher der Sensorknoten befestigt ist. Sehr bedeutend für dieses Projekt ist eine lange Funktionsweise ohne
menschlichen Einfluss von etwa einem Jahr. Für diese lange wartungsfreie Zeit muss
stets ausreichend Energie vorhanden sein. Eine entsprechende Batterie wiegt jedoch zehn
Kilogramm, da ein relativ hoher Energieverbrauch stattfindet (0.03-0.07 Watt). Aus
diesem Grund sind die eingesetzten Batterien mit Solarenergie wiederaufladbar.
Abbildung 1.3: Zebra mit Halsmanschette, Quelle: [Zh, Sa 04, S.9]
Die Latenzzeit für die Nachrichtenübertragung ist unkritisch, aber die erfolgreiche
Übermittlungswahrscheinlichkeit soll hoch sein. Der Fokus der sendenden Daten liegt
auf der aktuellen Position des Zebras. Denkbar ist natürlich auch die Angabe von
Temperatur, weiteren Wetterdaten, Gesundheitsdaten des Zebras und so weiter.
Probleme im ZebraNet bestehen zur Zeit noch in der Weiterleitung der Nachrichten.
Die Funkeinheit wurde für eine Reichweite von fünf Meilen spezifiziert, in Wirklichkeit
wird jedoch nur eine Sendereichweite von etwa einer Meile erreicht. Bisher bestehen nur
Vermutungen für die Gründe der geringeren Sendereichweite:
Störend kann die Grundplatte der Antenne oder einfach die Tatsache sein, dass beim
Grasen des Zebras die Halsmanschette nahe am Boden ist. Bei einer geringen Distanz
zum Boden werden Signale verzerrt (Absorption) und die Sendereichweite reduziert.
Die zukünftige Forschungsarbeit soll realisieren, dass eine Übertragung losgekoppelt vom
zwei-Stunden-Rhythmus stattfindet. Immer wenn sich ein Empfänger in Sendereichweite
befindet, soll eine Übertragung erfolgen. Um diese Funktion mit den gegebenen Ressourcen zu erreichen, soll eine energiesparendere Funkeinheit eingesetzt werden.
Für weitere Informationen über das ZebraNet kann die eingesetzte Literatur [Zh,
Sa 04] und [Sa 04] genutzt werden.
1 Einleitung
9
2. Supermarkt
Jede Artikelgruppe in den Regalen wird mit einem Sensorknoten ausgestattet. Sein
Sensor mißt die Artikelanzahl und schickt bei Veränderung des Bestandes, sei es durch
Entnahme oder Auffüllen, eine Nachricht an den Server [Sch 03/04]. Dieser hat somit
stets einen aktuellen Überblick über den gesamten Warenbestand im Supermarkt.
Mit diesen Informationen kann er automatisch entsprechende Bestellungen aufgeben.
Ebenfalls denkbar ist eine Meldung, falls der Warenbestand im Regal aufgefüllt werden
muss.
Abbildung 1.4: Sensorknoten der Artikelgruppe ’Cigaret’, In Anlehnung an [Sch 03/04,
S.2]
Des Weiteren verfügen die Sensorknoten über ein elektronisches Display, welches für die
Preisanzeige genutzt wird. Der Server hat die Möglichkeit jedem beliebigen Sensorknoten
eine Nachricht mit einer Preisänderung zukommen zu lassen. Der neue Preis wird dann
automatisch auf dem elektronischen Display angezeigt.
3. Gebäudesicherung
In erdbebengefährdeten Gebieten könnte mit Hilfe von intelligenten Gebäuden mehr
Sicherheit geschaffen werden. Dazu werden an den Außenseiten der Hochhäuser Sensorknoten befestigt. Mit Hilfe der Messungen von Schwankungen ist es möglich, die
Menschen rechtzeitig zu evakuieren, falls das Gebäude einsturzgefährdet ist.
1 Einleitung
10
4. Waldbrände
Ein weiteres Einsatzgebiet von Sensornetzen ist in ausgebrochenen Waldbränden zu
sehen: Im Brandgebiet werden Sensorknoten aus einem Flugzeug abgeworfen, welche
dann jeweils die an ihrer Position gemessene Temperatur an die Zentrale mittels Routing
durch das Sensornetz weiterleitet. Brandherde können identifiziert und das Feuer schnell
eliminiert werden.
An diesem Szenario werden drei Eigenschaften von Sensornetzen deutlich: Zum einen
befinden sich die Sensorknoten nach dem Absturz in keiner festgelegten Reihenfolge. Die
neuen Kommunikationsnachbarn müssen gefunden und verarbeitet werden. Daher spielt
die dynamische Verwaltung der Nachbarschaftsinformationen eine große Rolle.
Zudem muss das Netz selbstorganisierend und selbstkonfigurierend erzeugt werden,
schließlich ist kein menschlicher Einfluss nach dem Abwurf mehr möglich.
Als weitere Eigenschaft sollten die Sensorknoten möglichst preiswert sein. Ein zweiter
Einsatz der Knoten ist aufgrund der Hitzeauswirkungen wahrscheinlich nicht möglich.
1 Einleitung
11
Kapitel 2
Aufgabenstellung
Dieser Kapitel gibt eine genaue Definition der Aufgabenstellung. Für die Diplomarbeit
werden spezielle Hardwareeigenschaften der Sensorknoten vorausgesetzt, welche in
der Fakultät für Elektrotechnik im Fachgebiet Sensorik an der Universität Paderborn
entwickelt und produziert werden. Das Ziel dieser Entwicklungen ist es, eine äußerst
preisgünstige Hardware herzustellen.
Nach der expliziten Hardwarespezifikation wird das Szenario für die Arbeit im Detail
erläutert.
2.1
Hardwarespezifikation
Allgemein zeichnen sich Sensorknoten durch geringe Rechenleistung, wenig Speicher und
eine spärliche Sendereichweite aus. In meiner Diplomarbeit betrachte ich folgende expliziten Hardwareeinschränkungen:
Die Sensorknoten besitzen einen Micro-Controller der Firma Texas Instruments 1 mit 256
Byte RAM und einen FLASH-Speicher von acht Kilobyte. Der Micro-Controller ist mit
einem RISC Prozessor ausgestattet. Dieser Prozessor hat nur geringe Rechenpower: Additionen sind in der Hardware verankert, Multiplikationen müssen bereits mittels Software
gelöst werden.
Mit dem Radio-Transceiver Chipcon CC1000 ist die Übertragungsweite regulierbar. Frequenzbereiche können gewählt werden und es existieren Energiespar-Funktionen. Der
Radio-Transceiver ist individuell programmierbar.2 Der Frequenzbereich zum Senden und
1
des Typs MSP430F413
Es wird derzeit Frequency Shift Keying(FSK), mit Manchester Codierung und einer Kanaltrennung
von 64kHz genutzt.
2
2 Aufgabenstellung
13
Empfangen im 443MHz Band beträgt etwa 1, 75 MHz. Die Kanäle haben einen Bereich
von 64 kHz. Mit der gleichen Breite als Sicherheitsbereich zur Kanaltrennung stehen dreizehn Frequenzbereiche zur Verfügung.
Des Weiteren besitzen die Sensorknoten eine Uhr, welche für die Knotensynchronisierung eingestellt werden kann. Mit Hilfe der Uhr können die Knoten in eine Standby-Zeit
(Schlafphase) versetzt werden. Nach einer gewünschten Schlafphase nimmt der Knoten
seinen gewohnten Betrieb erneut auf.
Die betrachteten Sensorknoten (siehe Abbildung 2.1) verfügen außerdem über ein elektronisches Display (beschriftet mit A). Der Sensor zur Datenerfassung ist auf einer Schiene
angebracht (B).
Abbildung 2.1: Sensorknoten zur Erfassung des Warenbestandes, Quelle: [Sch 04, S.2]
Da die Knoten batteriebetrieben sind, ist eins der primären Ziele Energie zu sparen.
Durch die Energiespar-Funktionen in Schlafphasen wird eine Einsparung um den Faktor
hundert erreicht.
In den Eigenschaften von Sensornetzen (vergleiche 1.3.1) habe ich erwähnt, dass auf
vielen Sensorknoten das Betriebssystem TinyOS genutzt werden kann. Wegen der harten
Ressourceneinschränkungen der genutzten Hardware ist der Einsatz von TinyOS nicht
möglich.
Aufgrund des knappen zur Verfügung stehenden Speichers heißt die Diplomarbeit
auch Routing in Sensornetzen (fast) ohne Speicher.“
”
Die Informationen der Spezifikation sind in [Sch 04, S.8] sowie [Sch 03/04, S.4] zu finden.
2 Aufgabenstellung
2.2
14
Das Szenario “Supermarkt“
Als Einsatzgebiet des Sensornetzes für die Diplomarbeit wird das Augenmerk auf das
Szenario “Supermarkt“ gerichtet. Natürlich können die Ergebnisse auf ähnliche Szenarien
übertragen werden.
Die Beschreibung des Szenarios erfolgt im ersten Abschnitt durch eine allgemeine
Situationsdarstellung. Anschließend werden explizite Annahmen beschrieben, die zur
Ergebnisfindung vorausgesetzt wurden.
2.2.1
Situationsbeschreibung
Die Wahl fällt auf das Szenario Supermarkt, da die entwickelte Hardware (vgl. 2.1) speziell für einen solchen Einsatz angefertigt ist (siehe Abbildung 2.1).
Das elektronische Display zeigt den Preis der Artikelgruppe an. Auf der Schiene mit der
Sensortechnik werden die Artikel positioniert. Mittels Schienenauslastung kann die Anzahl der aktuell vorhandenen Artikel bestimmt werden. In den Regalen steht für jede
Artikelgruppe ein solcher Sensorknoten.
Wird die Ausnutzung der Schienenlänge verändert, liegt eine Modifikation des Warenbestandes vor und eine Nachricht wird generiert. Mit Hilfe der anderen Sensorknoten wird
diese über Multi-Hops zum Server geleitet. Fließen Nachrichten von einem Sensorknoten
zum Server spricht man von der uplink -Kommunikation.
Nachrichten werden downlink versendet, wenn sie vom Server zu einem Serverknoten
geschickt werden. Für Preisänderungen oder Nachrichten an alle Sensorknoten wird diese
Kommunikationsrichtung genutzt.
In Abbildung 2.2 werden die Kommunikationswege visualisiert. Dabei symbolisiert s0
den Server, si ist ein beliebiger Sensorknoten. Wie in der Abbildung zu sehen ist befinden
sich zeitweise Einkäufer/-innen in den Durchgängen zwischen den Regalen. Diese können
Störungen hervorrufen, da sie gegebenenfalls Signale ablenken und Kommunikationswege
versperren.
2 Aufgabenstellung
15
Abbildung 2.2: Kommunikation über Regale im Supermarkt, Quelle: [Sch 03/04, S.4]
2.2.2
Explizite Voraussetzungen
In dem oben geschilderten Szenario gibt es viele unbekannte Faktoren:
Zum einen ist ungewiss, wie häufig sich der Artikelbestand ändert und eine Nachricht zu
versenden ist. Dies entspricht der Wahrscheinlichkeit, dass ein Artikel verkauft wird oder
Artikel aufgefüllt werden.
Zum anderen liegen keine Informationen über ein Verhältnis von Sendern und Empfängern
vor. Ein derartiges Verhältnis ist aber sehr wichtig, um eine Erfolgswahrscheinlichkeit für
das Versenden einer Nachricht zu bestimmen. Schließlich sinkt die Erfolgswahrscheinlichkeit bei mehr Sendern und erhöht sich mit wachsender Anzahl von Empfängern.
Die Abschätzung oder Annahme einer Wahrscheinlichkeit, dass eine Nachricht generiert
wird, ist realistisch kaum zu veranschlagen. Einerseits gibt es gewisse Stoßzeiten mit
viel Betrieb und wiederum Zeiten mit wenig Einkäufen. Andererseits werden einige
Artikel häufiger gekauft als andere. Wichtig ist natürlich ebenso, dass das gesamte
Verkaufsvolumen und die Stoßzeiten von Supermarkt zu Supermarkt variieren. Jedoch
sollten Annahmen möglichst generell gültig sein. Letztendlich könnte höchstens eine sehr
fehlerhafte Durchschnittswahrscheinlichkeit abgeschätzt werden.
Realistische Abschätzungen kann ich jedoch für das Verhältnis von potentiellen
Sendern und potentiellen Empfängern treffen. Die Summe von potentiell störenden
2 Aufgabenstellung
16
Knoten und potentiell verfügbaren Empfängern ist abhängig von der Knotenanzahl
im Sendebereich. Dabei betrachte ich entweder uplink- oder downlink-Kommunikation.
Somit zählen als Empfänger nur die Sensorknoten “in der richtigen Richtung“. Mit
anderen Worten: Bei der uplink-Kommunikationen sind potentielle Empfänger die
Knoten, welche sich näher zum Server befinden. Anvisierte Nachbarschaftsknoten zur
Weiterleitung bei der downlink-Kommunikation sind die Sensorknoten, welche weiter
vom Server entfernt sind. Als Maß für die Distanz wird die Hopdistanz eingeführt:
Definition 2.2.1 Hopdistanz
Die Hopdistanz wird definiert als Maß der Distanz zum Server. Es gilt:
1. Der Server besitzt eine Hopdistanz von Null.
2. Die Hopdistanz d ist beschränkt: 0 ≤ d ≤ ROU T ELEN GT H, dabei ist ROUTELENGTH die bereits im Protokoll existierende Konstante.
3. Die Hopdistanz wird in Beacons, uplink-Nachrichten sowie den zugehörigen Acknowledgements übertragen.
4. Die Hopdistanz ist in den meisten Fällen eine Fließkommazahl (Datentyp real). Zur
Bestimmung des Aufwachpunktes sowie bei der Versendung von Nachrichten wird
die nächste ganze Zahl genutzt.
5. Sei d die gerundete Hopdistanz eines Knotens. Empfängt dieser ein Acknowledgement oder ein Beacon mit Hopdistanz h − 1 < d , so verringert er seine Hopdistanz
um einen konstanten Faktor (zum Beispiel
1
).
3
Ansonsten bildet der Knoten das
arithmetische Mittel der Hopdistanzen.
6. Da Kommunikationswege ausfallen können, kann sich die Hopdistanz eines Knotens
ändern. Wurde eine uplink-Nachricht während einer Wachphase nicht versendet und
es traten keine Interferenzen auf, so ist ein vorheriger Kommunikationsweg wahrscheinlich gestört. Ist noch nicht die maximale Hopdistanz erreicht, wird die eigene
Hopdistanz inkrementiert.
7. Sendet der Server eine downlink-Nachricht zu einem Knoten, teilt er ihm die Hopdistanz der vorgeschlagenen Route mit. Diese übernimmt der Knoten.
2 Aufgabenstellung
17
Bemerkung 2.2.2
Die Hopdistanz ist das neue Maß für die Distanz zum Server und löst damit die im
1 QK-Protokoll definierte Expected Power Distance (siehe Abschnitt 3.1.2) ab. Da die
Knoten für die Diplomarbeit synchronisiert sind, kann die Distanz einfacher erkannt
werden. Schließlich kann jeder Knoten nur zu gewissen Zeitpunkten eine Nachricht
empfangen. Ohne Synchronisation konnten Nachrichten zu jeder Zeit in der Wachphase
eintreffen.
Des Weiteren weisen sich Knoten der Hopdistanz zu, von welcher sie die meisten
Nachrichten erhalten. Dieses wird durch das arithmetische Mittel erreicht.
Obige Definition gilt nur, wenn Knoten mit Hopdistanz i auch noch lauschen, wenn
Knoten mit der niedrigeren Hopdistanz i − 1 uplink senden. Andernfalls muss die
Hopdistanz nicht gerundet werden und nicht in uplink-Acknowledgements enthalten sein.
Die Sicherung bei Ausfällen von Kommunikationswegen besteht dann alleine aus der
Erhöhung nach einer erfolglosen Wachphase.
Die Distanz wird nur schrittweise herunter gesetzt, damit die “mühevolle“ Erhöhung
nicht zu schnell wieder rückgängig gemacht wird. Mit dieser Hopdistanz ist die maximale
Distanz im Netz dynamisch. Das Netz passt sich dem aktuellen Nachrichtenaufkommen
an: Kleine maximale Hopdistanz bei wenig Verkehr und gropße Hopdistanz bei hohem
Nachrichtenvolumen. Die Anzahl der Interferenzen wird damit verringert.
Die Konstante, welche zur Verringerung der Distanz genutzt wird, muss mit Bedacht gewählt werden. Denn die gleiche Knotenanzahl soll in etwa für jede Hopdistanz
gelten.
Knoten mit der gleichen Hopdistanz befinden sich in einer virtuellen Regalreihe. Dies
ist nur eine virtuelle und keine physikalische Regalreihe. Mittels Reflektionen von Nachrichten durch Gegenstände in der direkten Umwelt können kürzere Kommunikationswege
für einen Sensorknoten aus einer weiter entfernten Regalreihe entstehen. Durch die dynamische Anpassung kann man jedoch davon ausgehen, dass ungefähr gleich viele Knoten
pro Hopdistanz (und damit pro virtuelle Regalreihe) zu verzeichnen sind.
Beispiel 2.2.3 Zugehörigkeit zum virtuellen Regalreihen
Dieses Beispiel ist visualisiert in Abbildung 2.3. Der rote Knoten besitzt eine Hopdistanz zum Server von Eins. Die roten Striche stellen versendete Beacons dar. Eins
dieser Signale wird durch einen Gegenstand so reflektiert, dass der grüne Knoten
2 Aufgabenstellung
18
Abbildung 2.3: Virtuelle Regale
in der dritten Regalreihe die Signale empfängt, obwohl er eigentlich außerhalb der Sendereichweite ist. Anhand des erhaltenen Beacons setzt der Knoten seine Hopdistanz auf
zwei. Diese Hopdistanz besitzen auch die Knoten in Regalreihe zwei. Somit ist der grüne
Knoten in der virtuellen Regalreihe zwei, befindet sich aber physikalisch in der dritten
Regalreihe.
Mit Hilfe der Hopdistanz ist die Knotenanzahl pro Entfernungsschritt in etwa gleich.
Zwei aneinander stehende Regale werden als eine Regalreihe angesehen. Die Anzahl
der potentiellen Empfänger und Sender wird als Durchschnitt in der Regalreihenmitte
gemessen. Bei der Berechnung der Strecke werden jeweils nur die Regale der Regalreihen
“in der richtigen Richtung“ sowie mit der Öffnung zum Regalgang betrachtet. Wie die
Trennwände die Signale beeinflussen, ist nämlich schwer abzuschätzen.
Da diese Annahmen bei der Berechnung der Sender und der Empfänger gemacht werden,
ist der Fehler auf beiden Seiten gleich und wirkt sich für das Verhältnis nicht aus. Ebenso
wird das Verhältnis nur für eine Regalebene berechnet. Ein Regal besitzt natürlich
mehrere Einlegeböden und damit befinden sich mehrere Stationen in verschiedenen
Ebenen vertikal übereinander (siehe Abbildung 2.4). Wie sich der Nachrichtenempfang
zwischen Stationen verschiedener Ebenen verhält, ist schwer abzuschätzen. Je nach
verwendetem Regalmaterial werden schließlich die Signale unterschiedlich stark zerstreut
oder verzerrt. Für das Verhältnis von Empfängern und Sendern kann die Abgrenzung sich
aber auf eine Ebene beschränken. Bei mehreren Ebenen erhöht sich natürlich die Anzahl
der Empfänger. Die Anzahl der konkurrierenden Sender wächst jedoch gleichermaßen.
So bleibt das Verhältnis von Sendern und Empfängern unabhängig von der Anzahl der
2 Aufgabenstellung
19
Ebenen in etwa gleich.
Abbildung 2.4: Visualisierung der Regalbegriffe
Es folgt zunächst eine Funktion zur Ermittlung des Empfänger-Sender-Verhältnisses. Dabei wird ohne Beeinschränkung der Allgemeinheit die uplink-Kommunikation betrachtet.
Anschließend werden einige Beispielrechnungen durchgeführt.
Um ein gültiges Verhältnis zu finden, bedarf es zum einen der Betrachtung der
Topologieeigenschaften. Alle Knoten im Sendebereich zählen jedoch nicht zu Sendern
oder Empfängern. Für die Klassifizierung der Knoten ist die Distanz zum Server ausschlaggebend. Knoten im Sendebereich mit niedrigerer Hopdistanz zählen als Empfänger.
Es hängt von der Realisierung des Protokolls ab, welche Knoten als potentielle Sender
gezählt werden müssen. So kann gelten, dass nur Knoten mit identischer Hopdistanz
zeitgleich senden (lokaler synchroner Aufwachpunkt, siehe 4.3). Ein anderer Realisierungsansatz ist, dass alle Knoten im Sendebereich zur gleichen Zeit senden (globaler
synchroner Aufwachpunkt). Dieser Aspekt wird im zweiten Schritt zur Ermittlung eines
Empfänger-Sender-Verhältnisses betrachtet.
1. Topologieeigenschaften
Die Sendereichweite verläuft theoretisch kreisrund um den sendenden Knoten. In der
neuesten Forschung wird die Sendereichweite nicht mehr als Kreisform gesehen. Diese
Erkenntnisse werden für diese theoretische Arbeit allerdings nicht betrachtet. Des
Weiteren werden in den Untersuchungen keine Regalenden einbezogen.
2 Aufgabenstellung
20
Abbildung 2.5: Senkrechte Anordnung der Regale zum Server
Problematisch ist, dass die Regalanordnungen in Bezug zum Server variable sind. So sind
Anordnungen wie in den Abbildungen 2.5, 2.6 und 2.7 zu berücksichtigen.
Abbildung 2.6: Querstehende Regale zum Server
Für das Verhältnis von Knoten in Sendereichweite wird der Senderadius eines beliebigen
Knotens betrachtet (siehe 2.7), der sich nicht am Regalende befindet. Zu Knoten Zwei
2 Aufgabenstellung
21
gehört der gelb visualisierte Senderadius. Knoten Eins besitzt den roten. Das ermittelte
Knotenverhältnis von Eins kann für jeden anderen Knoten übertragen werden. Schließlich
ist b nicht in allen Sendebereichen der Knoten im Radius von Eins. Dies ist visualisiert
für Knoten c: Er befindet sich im Senderadius von Zwei, ist jedoch für Eins nicht mehr
erreichbar. Damit kann das Verhältnis für einen beliebigen Senderadius untersucht und
für alle anderen Knoten übertragen werden.
Abbildung 2.7: Überschneidungen vom Sendebereich
Zur Ermittlung der Strecke, auf welcher sich Knoten im Sendebereich befinden können,
sind einige Parameter erforderlich. Für die Knotenanzahl wird diese Strecke durch die
durchschnittliche Artikelbreite dividiert. Als Parameter werden eingesetzt:
• r ist der Radius der Sendereichweite
• b ist die Länge zwischen zwei Regalreihenmitten und ergibt sich aus der Durchgangsbreite sowie der Breite einer Regalreihe
Der Satz von Pythagoras wird zur Streckenberechnung genutzt. Die Visualisierung der
Berechnung für zwei unterschiedlich weit entfernten Regalreihen ist in Abbildung 2.8 visualisiert. In rot wird der Radius, in blau die gesuchte Strecke und in schwarz die
Entfernung zur anderen Regalmitte dargestellt. Die Hypothenusen sind gleichzusetzen mit dem Radius. Die rechts anliegenden Katheten entsprechen der Entfernung zur
Mitte der anderen Regalreihen.
Die Summe der zweiten Kathetenlängen ist gleich dem Bereich, in welchem sich andere
Knoten befinden. Zusätzlich muss die eigene Regalreihe bedacht werden. Der Durchmesser
ist die Länge, auf welchem sich zusätzlich Knoten verteilen. Die Länge der Strecke in
2 Aufgabenstellung
22
Abbildung 2.8: Visualisierung der Dreiecksberechnung
anderen Regalreihen wird mit vier mutlipliziert, da Regalreihen in beide Richtungen für
die Knoten betrachtet werden müssen. Hierbei wird zunächst noch keine Unterscheidung
zwischen gegebenenfalls störenden oder anvisierten Knoten gemacht. Von der Realisierung
des 1 QK-Protokolls ist abhängig, welcher Knoten welche Rolle übernehmen kann.
r
Knotenstrecke (r, b) = 2 · r +
bbc
X
4·
p
r2 − (ib)2
i=1
2. Knotenklassifizierung
Von der Hopdistanz der Knoten ist abhängig, ob diese als störender Sender oder als
Empfänger in Frage kommen. Ich betrachte hier ohne Beeinschränkung der Allgemeinheit
den Kommunikationsfluss zum Server. Die Ergebnisse sind dann auf die Gegenrichtung
übertragbar.
Werden Nachrichten zum Server von Knoten k versendet, sind alle lauschenden Knoten
mit geringerer Hopdistanz potentielle Empfänger. Zur Klassifizierung der Sender muss die
Realisierung des 1 QK-Protokolls und der Synchronisation genauer betrachtet werden:
In jedem Fall sind Knoten mit gleicher Hopdistanz wie k stets potentiell störende Nachbarknoten. Des Weiteren sind Knoten Sender, wenn ihre Sendephasen zu denen von k
nicht disjunkt sind. Die Aufwachphasen können so gestaltet sein, dass alle Knoten gleichzeitig erwachen und senden (global). Auf der anderen Seite ist auch ein lokaler synchroner
Aufwachpunkt möglich. Dabei überschneiden sich die Sendephasen nur von Knoten mit
gleicher oder ähnlicher Hopdistanz:
Sei h die Hopdistanz des betrachteten Knotens k. Nicht disjunkt seien die Sendephasen
von k und den Knoten mit einer Hopdistanz, welche sich um s Einheiten unterscheidet
(also mit Hopdistanz (h−s−1) . . . (h+s+1)). Beim globalen Ansatz entspricht s der maximalen Differenz zu anderen Hopdistanzen. Senden nur Knoten mit gleicher Hopdistanz,
2 Aufgabenstellung
23
ist s Null. Knoten mit gleicher Hopdistanz liegen im gleichen virtuellen Regal. Die Anzahl
der Knoten pro virtuellem Regal wird aufgrund der dynamischen Anpassung der Distanz
ähnlich der Knotenanzahl im physikalischen Regal sein. Daher setze ich hier das virtuelle
mit dem physikalischen Regal gleich (dieser Ansatz wird in 4.3.1 weiter fortgeführt).
Senden nur Knoten mit identischer Hopdistanz zeitgleich, so sind in den vorigen Abbildungen in Cyan stets die Sender und in Grün die Empfänger dargestellt. Eine waagerechte
Regalanordnung wie in Abbildung 2.7 ist dann einfach zu handhaben: Der Abstand zu
den Empfängern ist mittels der Durchgangsbreite zu berechnen.
Liegt jedoch eine senkrechte Anordnung wie in 2.5 vor, wird dieses problematischer:
Als Sendern zählen die Knoten in einem gewissen Radius um k. Die Empfänger befinden
sich im gleichen und in anderen Regalen nach einer gewissen Distanz in der richtigen Richtung. Dies führt dazu, dass wenn man virtuelle Regalreihen betrachtet, man wieder an
die Ansicht aus Abbildung 2.7 herantritt. Der Abstand zwischen den virtuellen Regalreihen entspricht dann aber nicht dem Durchgang. Ebenso muss bei der Senderberechnung
der Regaldurchgang betrachtet werden. Daher wird nur eine Regalseite in einer beliebigen Richtung betrachtet. Durchschnittswerte der Knotenentfernungen sind notwendig, um
wieder mit dem Satz des Pythagoras zu argumentieren. Damit werden folgende Parameter
benötigt:
• r ist der Radius der Sendereichweite
• x ist die minimale Entfernung zu Knoten mit einer anderen Hopdistanz im gleichen
Regal. Der Faktor ist nur von Bedeutung einer senkrechten (siehe Abbildung 2.5)
oder schiefen (siehe Abbildung 2.6) Regalanordnung vorliegt. Der Parameter wird
als Hypothenuse bei der Berechnung der Sender eingesetzt.
Für die waagerechte Regalanordnung entspricht dies dem Parameter b der vorigen
Funktion.
• y ist bei einer senkrechten oder schiefen Anordnung die durchschnittliche Entfernung zu Knoten gleicher Hopdistanz. Für die waagerechte Anordnung ist sie
gleich Null, da die Verhältnisse von virtuellen und physikalischen Regalen in etwa übereinstimmen.
Daraus resultiert die Strecke für störende Nachbarknoten von:
1. Fall: s > b xr c
a) y = 0
r
Senderstrecke (r, x, y, s) = 2 · r +
bxc
X
i=1
4·
√
r 2 − x2
2 Aufgabenstellung
24
b) y > 0
Senderstrecke (r, x, y, s) = 2 ·
p
x2
y2
− +2·
p
= 2 · ( r2 − y 2
p
r2
−
y2
−
p
x2
−
y2
Abbildung 2.9: Streckenverhältnisse der senkrechten Regalanordnung
Die genutzten Summen über i sind für die Sender anderer Hopdistanzen, welche den
Sendevorgang stören können. Die angegebene durchschnittliche Entfernung gilt für
alle Knoten mit gleicher Hopdistanz. Dies ist eine Vereinfachung anstatt die Knoten
jedes physikalisch benachbarten Regals genau zu untersuchen. Daher stützen sich alle
Berechnungen auf Ausschnitte des Dreieck mit einer Kathete (= y) und Hypothenuse
(= r) (siehe Abbilung 2.9). Bei der Senderstrecke gleicher Hopdistanz wird die Hypothenuse durch die minimale Entfernung x ersetzt. Zählen alle Knoten im Sendebereich
zu den Sendern, so muss für die Strecke der anderen Hopdistanzen nur die Strecke der
gleichen Hopdistanz subtrahiert werden. Die Strecken werden mit 2 multipliziert, da die
Dreiecksberechnungen symmetrisch sind (in Richtung zum und vom Server entfernt).
2. Fall: s ≤ b xr c
a) y = 0
Senderstrecke (r, x, y, s) = 2 · r +
s
X
4·
√
r 2 − x2
i=1
b) y > 0
Senderstrecke (r, x, y, s) = 2 ·
p
x2
=2·
−
y2
+2·
q
2
((s + 1)x) −
y2
−
p
x2
−
y2
q
((s + 1)x)2 − y 2
Als Empfänger zählen alle Nachbarknoten mit geringerer Hopdistanz. Zum Empfangen
2 Aufgabenstellung
25
müssen diese jedoch wach sein und auf einem Kanal lauschen. Daher werden für die
waagerechte Anordnung nur Knoten der Regalreihen w näher zum Server betrachtet, die
zur Sendezeit von k ihre Empfangsphase haben. Bei anderen Regalanordnungen kann
die Empfängerstrecke mit Hilfe der Senderstrecke berechnet werden. In der Dreiecksberechnung für die Senderstrecke wird schließlich die minimale Strecke als Hypothenuse
genutzt, in welcher Knoten anderer Hopdistanz vertreten sind. :
1. Fall: w > b xr c
a) y = 0
r
Empfängerstrecke (r, x, y, w) =
bxc
X
2·
p
r2 − (ix)2
i=1
b) y > 0
p
r2 − y 2 −
p
x2 − y 2
2. Fall: w ≤ b xr c
a) y = 0
w
X
2·
p
r2 − (ix)2
i=1
b) y > 0
q
p
Empfängerstrecke (r, x, y, w) = ((w + 1)x)2 − y 2 − x2 − y 2
Anstatt der Fallunterscheidung kann für die Strecke jeweils die Summe bis zum Minimum
von b xr c und s oder w berechnet werden.
3. Verhältnis von Sendern zu Empfängern
Nimmt man obigen Berechnungen zusammen, ergibt sich ein Verhältnis von potentiellen
Sendern und potentiellen Empfängern von:
a) y = 0
Pmin(b xr c,w) √ 2
Empfängerstrecke
2 · r − x2
i=0
=
Pmin(b r c,s) √
Senderstrecke
2 · r + i=1 x 4 · r2 − x2
Pmin(b xr c,w) √ 2
r − x2
i=0
=
Pmin(b r c,s) √ 2
r + 2 · i=0 x
r − x2
2 Aufgabenstellung
26
b) y > 0
q
p
2
2
min
−
((w + 1)x) − y − x2 − y 2
Empfängerstrecke
q
=
p
Senderstrecke
2
2
2
2
2 · min
((s + 1)x) − y , r − y
p
r2
y2,
Beim lokalen Ansatz gilt w ≥ (0, 5 · s + 1). Schließlich sind alle Knoten, die beim lokalen
Ansatz wach sind entweder Sender oder Empfänger. Besitzen die Knoten keine eigene
Nachricht, so handelt es sich um Empfängern. Da aber der Kommunikationsfluss zum
Server betrachtet wird, zählen nur die Knoten mit geringerer Hopdistanz. Des Weiteren
müssen Sensorknoten mit Hopdistanz h − s − 2 wach sein, wenn welche mit Distanz
h − s − 1 senden. Ansonsten wären die Sendeversuche der Sensorknoten unnütz.
Lemma 2.2.4
Es ist zu erkennen, dass zur Bestimmung des Empfänger-Sender-Verhälntisses bei einer
senkrechten oder schiefen Regalanordnung es an wesentlich mehr Informationen bedarf.
Zudem wird der Fehler deutlich größer sein, da es sich nur um Durchschnittswerte von
Entfernungen handelt. Eine genauerer Analyse dieses Szenarios ist aber wesentlich umfangreicher und in dieser Diplomarbeit nicht zu bewältigen. Daher beschränke ich mich
bei den Beispielszenarien sowie der Untersuchungen auf eine senkrechte Regalanordnung.
Die Ergebnisse der Arbeit können bei allen Regalanordnungen eingesetzt werden. Zur Findung der Optimierungen des Protokolls ist es jedoch leichter, eine senkrechte Anordnung
vorauszusetzen.
Beispielszenarien
Nach eigenen Untersuchungen sind Regale in Supermärkten entweder dreißig Zentimeter
oder fünfzig Zentimeter tief, Einkaufswagen meistens zwischen vierzig und sechszig
Zentimetern breit. Regaldurchgänge in Supermärkten mit Einkaufwagen müssen gemäß
der Verkaufstättenrichtlinien in Österreich mindestens 1, 20 Meter breit sein (siehe [Ma
02, S.9]). Ein Referenzsupermarkt in Deutschland hatte eine Durchgangsbreite von 2, 10
Metern.
2 Aufgabenstellung
27
Abbildung 2.10: Regalproportionen
Betrachtet wird zum Vergleich eine “große“ und eine “kleine Konstruktion“. Im 1. Fall
ist der Durchgang 2, 10 Meter und die Regale sind fünfzig Zentimeter tief. Im Gegensatz dazu steht der 2. Fall mit 1, 20 Metern Durchgang und dreißig Zentimetern Regaltiefe.
1. Fall: Durchgangsbreite 2,10 m
Die Regaltiefe betrage fünfzig Zentimeter. Damit ergibt sich eine Gesamttiefe der
Regalreihe von 1 Meter.
Die Entfernung von einer Regalmitte zur nächsten beträgt 2, 10m + 0, 50m + 0, 50m =
3, 10m (= Parameter x). Damit die jeweils äußersten Sensorknoten miteinander kommunizieren können, benötigt man mindestens eine Sendereichweite von 4, 10 Metern. Die
Sendereichweite kann nicht so gut justiert werden, dass nur die nachfolgende Regalreihe
inkludiert ist. Mit Hilfe der regalweisen Synchronisation kann realisiert werden, dass
nur Knoten zweier benachbarter virtueller Regalreihen gleichzeitig wach sind. Damit
entspricht der Nenner dem Senderadius. Die Variable s wird auf Null gesetzt und w auf
Eins.
a) Der Senderadius r sei 4, 50 Meter.
p
p
Länge für potentielle Empfänger: 4, 502 m2 − 3, 102 m2 = 10, 64m2 = 3, 26m
Empfängerstrecke
3, 26m
=
= 0, 724
Senderlänge
4, 50m
Das heißt, etwa 72,4 Prozent der Sender sind als Empfänger erreichbar. Also knapp 3/4
der Sender sind als Empfänger vertreten.
2 Aufgabenstellung
28
b) Der Senderadius sei nun 4, 80 Meter.
p
p
Länge für potentielle Empfänger: 4, 802 m2 − 3, 102 m2 = 13, 43m2 = 3, 65m
Empfängerstrecke
3, 65m
=
= 0, 7604
Senderlänge
4, 80m
Etwa 76,0 Prozent der Sender sind als Empfänger erreichbar. Also gut 3/4 der Sender
sind als Empfänger in Sendereichweite.
Insgesamt kann man somit davon ausgehen, dass etwa 1/4 weniger Empfänger als
Sender zur Verfügung stehen. Bei n potentiellen Sendern sind dies 3/4 · n Empfänger.
Die Sendereichweite wird nicht variiert und so liegt stets ein gleichmäßiger Energievebrauch vor.
2. Fall: Durchgangsbreite 1, 20 Meter
Die Regaltiefe betrage nun dreißig Zentimeter, daraus resultiert eine Tiefe der Regalreihe
von sechzig Zentimetern.
Parameter x beträgt 1, 20m + 0, 30m + 0, 30m = 1, 80m. Damit die jeweils äußersten
Sensorknoten miteinander kommunizieren können, wird mindestens eine Sendereichweite
von 2, 40 Metern benötigt.
a) Der Senderadius sei 2, 50 Meter.
p
p
Länge für potentielle Empfänger: 2, 502 m2 − 1, 802 m2 = 3, 01m2 = 1, 73
Empfängerstrecke
1, 73m
=
= 0, 694
Senderlänge
2, 50m
Etwa 69,4 Prozent der Sender sind als Empfänger erreichbar. Dies entspricht etwas
weniger als 3/4.
b) Der Senderadius sei nun 3, 00 Meter.
p
p
Länge für potentielle Empfänger: 3, 002 m − 1, 802 m = 5, 76m2 = 2, 40m
Empfängerstrecke
2, 40m
=
= 0, 80
Senderlänge
3, 00m
Etwa 80 Prozent der Sender sind als Empfänger erreichbar. Damit wird das EmpfängerSender-Verhältnis von 3 : 4 etwas übertroffen.
2 Aufgabenstellung
29
Insgesamt kann man somit davon ausgehen, dass etwa 1/4 weniger Empfänger in
Reichweite sind als Sender.
Resultat aus beiden Fällen
Die Abschätzung n Sender und 3/4 · n Empfänger hat sich für beide Fälle herausgestellt.
Mit Sicherheit liegt ein gewisser Fehler in der Abschätzung vor allem wenn in Bezug
auf die Regalenden. Werden diese zusätzlich berücksichtigt, führt das kombinatorisch
zu noch mehr Fallunterscheidungen. Diese können aufgrund ihres Umfanges im Rahmen
einer Diplomarbeit nicht betrachtet werden. Zudem ist die Sendereichweite individuell
konfiguierbar und mit Hilfe der regalweisen Synchronisation kann diese Verhältnis
annähernd erreicht werden.
Für eine genaue Knotenanzahl in Reichweite ist natürlich die Artikelbreite entscheidend.
Ein gebildeter Durchschnittswert der Breite kann mit der Empfänger- und Senderlänge
eine Aussage treffen.
Beispiel 2.2.5
Haben die Artikel zum Beispiel eine Durschnittsbreite von 8 Zentimetern.
Für Fall 1b gilt dann:
Anzahl der Sender = 480/8 = 60, pro Regalrichtung. Damit 120 Sender im Senderadius.
Für die Empfänger bedeutet dieses 120 · 3/4 = 90.
Für Fall 2b gilt dann:
Anzahl der Sender = b300/8c = 37, pro Regalrichtung. Damit 74 Sender im Senderadius.
Die Anzahl der Empfänger beträgt resultierend b74 · 3/4c = 55.
Kapitel 3
Stand der Forschung
Dieses Kapitel gibt einen Überblick über entwickelte Routingverfahren. Zunächst wird
das 1 QK-Protokoll beschrieben, welches ich im Rahmen der Diplomarbeit optimiere.
Dieses Protokoll kann bei der vorausgesetzen Hardwarespezifikation (vgl. 2.1) eingesetzt
werden. Im Abschnitt 3.2 wird eine Auswahl bereits bestehender Verfahren vorgestellt.
Die Einsatzmöglichkeit jedes Verfahrens wird auf die gegebenen Problemdarstellung
untersucht.
3.1
Das 1 QK-Protokoll im Überblick
Das 1 QK-Protokoll wurde im Jahre 2004 an der Universität Paderborn in der Fachgruppe Meyer auf der Heide unter der Leitung von Dr. Christian Schindelhauer entwickelt
[Sch 04/04], [Sch 04-R02]. Es ist darauf spezialisiert, minimalen Speicher in Anspruch zu
nehmen:
Das Protokoll benötigt 128 Bytes =
1
8
Kilobyte RAM. Zur Verfügung stehen gemäß der
Hardwarespezifikation für das Routingprotokoll sowie der Applikation zur Sensordatenerfassung und -verarbeitung auf den Knoten 256 Byte. Aufgrund dieser Tatsache ist auch
der Name des Protokolls entstanden.1
Die Beschreibung des 1 QK-Protokolls ist gegliedert in mehrere Abschnitte:
Zunächst wird ein erster Überblick über die Funktionsweise und die Ideen des Protokolls
geliefert. In Abschnitt 3.1.2 wird das im Protokoll genutzte Maß für die Distanz zum
Server definiert und erklärt. Dieses Maß, die Expected Power Distance, ist vor allem
1
1Kilobyte = 1024 Byte. Es gilt
RAM benötigt.
1024
4
= 256. Somit wird ein Viertel(=1 Quarter) eines Kilobytes an
31
für die uplink-Kommunikation von Bedeutung. Im Anschluss folgt eine Erläuterung
der Funktionsweise der uplink- und der downlink-Kommunikation. Abschnitt 3.1.5
liefert eine kurze Beschreibung weiterer Nachrichtentypen, die eine untergeordnete
Rolle im Protokoll spielen. Es folgt eine Strukturanalyse des Protokolls in Bezug zu
dem bekannten OSI-Referenzmodell (siehe 3.1.6). Abschließend werden die Probleme
und Schwachstellen des 1 QK-Protokolls beschrieben. Durch Feststellung der Probleme werden meine Ansätze zur Optimierung des Routings (siehe Kapitel 5 und 6) deutlich.
3.1.1
Ein erster Überblick
Das Protokoll arbeitet mit unsynchronisierten Knoten. Dieses wurde hauptsächlich so
verwirklicht, da zum Entwicklungszeitpunkt eine Synchronisierung nicht realisierbar war:
Die Applikation erzeugte einen zu starken Uhrendrift. Dieses Softwareproblem ist behoben worden.
Die Sensorknoten besitzen eine lokale und eine globale Identifikationsnummer (ID). Aufgrund der Speicherersparnis werden lokale IDs, genannt auch NetIDs, bei der Versendung
von Nachrichten eingesetzt. Sie sind vom Datentyp int. Für eine globale Unterscheidung
aller Sensorknoten genügen jedoch gegebenenfalls keine 655535 Identifikationsnummern
(1 int=2 Bytes)2 . Daher wird für die globale ID (GID) der Datentyp long verwendet (4
Bytes).
Abbildung 3.1: Verhalten in der Round-Time, Quelle:[Sch 03/04, S.12]
Das Protokoll besteht aus einem Zyklus, der für alle gleich lang ist und endlos durchlaufen wird. In dieser Round-Time befindet sich jeder Knoten zunächst in der Schlafphase
2
Eine ID wird als Konstante für Speicherungszwecke verwendet, wenn der Wert unbelegt ist. Konstante
heißt NO NODE
¯
32
(in Abbildung 3.2: Zustand Idle Sleep). Nach einer zufälligen Wartezeit innerhalb der
Round-Time wacht jeder Knoten auf3 . Nach dem Erwachen eines Knotens überprüft er,
ob neue Sensordaten vorliegen (Abb. 3.2: Zustand Check for Sensor Data). Bei neuen
Daten wird eine Nachricht für den Server generiert. Diese wird so lange versendet, bis
der Sender eine Empfangsbestätigung (Acknowledgement) erhalten hat (Abb. 3.2: Zustand Send). In den meisten Fällen ist der Empfänger ein anderer Sensorknoten. Handelt
es sich um eine uplink-Nachricht und ist die Basisstation in Reichweite, kann auch die
Basisstation das Acknowledgement senden.
Abbildung 3.2: Zustandsübergänge, Quelle:[Sch 04/04, S.6]
Liegen zum Aufwachpunkt keine neuen Sensordaten vor, wird innerhalb einer gewissen
Zeitspanne4 nach einer fremden Nachricht gelauscht (Abb. 3.2: Zustand Listen, Abb.
3.1: treceive ). Falls eine empfangen wird und diese den Weiterleitungskriterien entspricht
(siehe Abschnitte 3.1.3, 3.1.4), schickt der Sensorknoten ein Acknowledgement zum
3
4
vergleiche Abbildung 3.1: Beginn von tactive
Zeit pro Frequenzbereich entspricht der Variablen Treceive
33
Sender. Anschließend sendet er diese Nachricht weiter (Abb. 3.2: Zustand Send).
Wird keine Nachricht empfangen und liegen keine eigenen neuen Daten vor, wird ein
sogenanntes Beacon versendet (Abb. 3.2: Zustand Send, Abb. 3.1: tsendBeacon ). Ein
Beacon enthält Informationen über die Identifikationsnummer, die Distanz zum Server
(die so genannte Expected Power Distance, siehe Abschnitt 3.1.2) sowie der Round-Time
des Knotens.
Nach dem Erhalt einer uplink- oder downlink-Nachricht und vor Versenden des
Acknowledgements wird diese im Buffer zwischengespeichert. Der Buffer kann gleichzeitig
eine uplink- und eine downlink-Nachricht speichern. Zudem ist Speicherplatz für eine
Route vorhanden. Falls sich im Buffer beide Nachrichtentypen befinden, ist stets die
downlink-Route im Buffer. Diese ist nämlich weitaus wichtiger als die uplink-Route (siehe
dazu 3.1.4). Priorität bei der Weiterleitung der Nachrichten hat das uplink-Paket, da der
Server mit möglichst geringer Latenz die Informationen verarbeiten soll.
Abbildung 3.3: Aktivitätendiagramm zu Process Packet, Quelle:[Sch 03/04, S.10]
34
Der Zustand Process Packet (siehe Abbildung 3.3) wird eingesetzt, um den korrekten
Nachrichtentyp der empfangenen Nachricht (uplink, downlink, Beacon . . . ) zu bearbeiten.
Die meisten Übergänge der internen Zustände führen in Send, um eine neue Nachricht
(meistens die Weiterleitung) zu verschicken. Wird hier eine andere Nachricht als ein Beacon versendet, erfolgt der Wechsel zu Blocked. Dieser Zustand realisiert eine kürzere
Schlafphase als Idle Sleep.
Idle Sleep impliziert nur dann eine Schlafphase, wenn der Knoten nichts zu tun hat.
Deshalb prüft er vor dem Schlafengehen, ob keine Nachricht im Buffer ist oder neue
Sensordaten vorliegen. Falls noch eine Aufgabe zu erledigen ist, wechselt der Knoten unverzüglich in den Zustand Check for new Sensor Data.
Abbildung 3.4: Das hidden terminal problem, Quelle:[Si,Ra 99, S.2]
Ein besonderer Aspekt des 1 QK-Protokolls ist, dass ein Sender das Übertragungsmedium
nicht reserviert, sondern Kollisionen in Kauf nimmt. Die Nachrichten werden einfach
gesendet, solange bis ein Acknowledgement empfangen wird. Diese Designentscheidung
resultiert aus der Nachrichtengröße (kleiner als 36 Bytes) und der damit verbundenen
geringen Übertragungsdauer. Das Verfahren ALOHA verfolgt zum Beispiel ebenfalls die
Strategie, dass Kollisionen nicht explizit vermieden werden [Ab 70], [Ro 75].
Die meisten anderen Kommunikationsprotokolle wie zum Beispiel PAMA oder MACA arbeiten mit einem Kanalzugangsprotokoll [Si,Ra 99], [Ka 90,S.134-140]. Als Ankündigung
und Nachfrage zum Versenden einer Nachricht wird ein “RequestToSend“(RTS) geschickt. Ist ein Knoten bereit die Nachricht entgegen zu nehmen, wird die Antwort
“ClearToSend“(CTS) gesendet. Erst nach dem Erhalt des CTS wird die eigentliche
Nachricht übertragen. Anhand dieser Methode werden Interferenzen durch gleichzeitiges
Senden mehrerer Knoten vermieden. Angemerkt sei allerdings, dass in diesen Protokollen
auch Probleme bei Überschneidungen und Überhören der RTS- und CTS-Nachrichten
existieren. Diese Schwierigkeiten, visualisiert in Abbildung 3.4, fallen unter den Begriff
35
“hidden terminal problem“.5
3.1.2
Distanz zum Server - die Expected Power Distance
Um bei der uplink-Kommunikation zu entscheiden, ob eine empfangene Nachricht weitergeleitet wird, ist ein Maß für die Distanz zum Server notwendig. Schließlich sollen
Nachrichten auf möglichst direktem Wege zum Server gelangen.
Definition 3.1.1 Expected Power Distance
1. Der Server besitzt eine Expected Power Distance von Null.
2. Sei m die Länge des erhaltenen Beacons, p die Übertragungsstärke und T die Länge
der Round-Time. Die Expected Power Distance eines Sensorknotens u wird dann
definiert durch:
EPD(u) := m · p +
X EPD(v)
p·T
+
|A(u)|
|A(u)|
vA(u)
mit A(u) := {vV |EPD(v) < EPD(u) ∧ u kann v erreichen }.
Problematisch bei dieser Definition ist die Realisierung mit der gegebenen Hardware:
• Die gesamte Nachbarschaft kann aufgrund des geringen Speichers nicht erfasst werden.
• Der Micro-Controller unterstützt keine Hardwaremultiplikation und - division.
• Die Gleichung ist rekursiv.
Deswegen entstand eine etwas abgewandelte Realisierung der Expected Power Distance:
Algorithmus 3.1.2 Vereinfachte Expected Power Distance
Max-EPD sei initialisiert mit einem beliebigen Wert größer Null.
Initialisierung der EPD(u) und der Hilfsvariablen M (u) mit Max-EPD.
5
Für ausführliche Informationen zum hidden terminal problem wird auf [Si,Ra 99] verwiesen.
36
Im Hintergrund:
u wacht einmal in der Round-Time T auf.
if u ein Beaconsignal von v empfängt:
XXXif EPD(v) < EPD(u) then
XXXXXXM (u) = Minimum{EPD(v) + m · p, Max-EPD}
XXXend-if
end-if
M (u) = Minimum{M (u) +
2p
, Max-EPD}
tsb
EPD(u) = (1 − α)EPD(u) + αM (u)
Mit tsb als die benötigte Zeit zur Versendung eines Beacons, m und p wie
oben sowie α ≈
tsb
.
T
Abbildung 3.5: Verlauf von Hilfsvariablen M und der EPD, Quelle:[Sch 03/04, S.17]
Die Expected Power Distance wird in jeder Wachphase verändert. Beim Eintritt in
den Zustand Process Packet läuft obiger Algorithmus ab. Zudem wird bei jedem
uplink-Sendeversuch die EPD um eine Konstante EPD MALUS erhöht. So steigt sie
¯
automatisch an, wenn eine Nachrichten von keinem Knoten mit geringerer EPD entgegen
genommen wird. Die Dynamik des Sensornetzes durch Ausfälle von Kommunikationswegen ist damit gut abgebildet. Nach Erhalt eines “näheren“ Beacons fällt die Expected
Power Distance nicht abrupt. Sie sinkt langsam, da M nur mit dem Faktor α für die
37
Berechnung der EPD angenommen wird.
Beispiel 3.1.3
In Abbildung 3.5 ist Weiß der Server. Nur Grün (Knoten 1) und Cyan (Knoten
2) haben eine direkte Verbindung zu ihm. Daraus resultieren auch die EPDs von Blau
(Knoten 3) und Braun (Knoten 4).
M zeigt jeweils eine stark schwankende Kurve (im Zick-Zack-Verlauf ). Immer wenn der
Knoten ein entsprechendes Beacon erhält, fällt M rapide ab. Anschließend wächst M
solange an, bis ein weiteres “näheres“ Beacon empfangen wird.
Betrachte man die Kurve von M (1) genauer:
Zu den Zeitpunkten t1 und t2 empfing der Knoten jeweils ein Beacon der Zentralstation.
Bei t3 hingegen wird ein Beacon von Knoten 2 verarbeitet. M (1) fällt damit weniger
steil ab als bei den vorherigen Empfangszeitpunkten. Das Beacon von Knoten 2 wird
verarbeitet, da dieser Knoten eine niedrigere EPD zum Zeitpunkt t3 besitzt.
3.1.3
uplink-Kommunikation
Bei der uplink-Kommunikation werden Nachrichten von einem Sensorknoten zum Server
geleitet.
Definition 3.1.4 uplink-Nachricht
Eine uplink-Nachricht besteht aus:
• sender id: int;
¯
Die lokale ID des aktuell versendenden Knotens. Diese Information wird übertragen,
damit sie im Acknowledgement ebenfalls enthalten ist.
• packet id: byte;
¯
Die ID des Paketes wird mittels einer internen Variablen hochgezählt bzw. beim
Weiterleiten die ursprüngliche ID übernommen und im ACK übertragen. Mit der
Angabe der sender ID und der packet ID ist eine Verwechselung des ACK damit
¯
¯
ausgeschlossen. Schließlich wartet ein Sender immer auf das ACK seiner aktuell
versendeten Nachricht.
• EPD: int;
Die Expected Power Distance des aktuell versendenden Knotens.
38
• origin GID: long;
¯
Globale ID des Knotens, welcher die Nachricht erzeugt hat. Sie dient dem Server
zur Identifizierung des Nachrichtenursprungs.
• application data : array [UP APPL LENGTH] of byte;
¯
¯
¯
Beinhaltet die Applikations-/Sensordaten für den Server.
Die
Konstante
UP APPL LENGTH ist obere Schranke für den Umfang der Applikationsdaten.
¯
¯
• route : array [ROUTELENGTH] of int;
Entspricht der bisher zurückgelegten Route. Die Route ist dabei beschränkt durch
die Routenlänge. Ist das Array vollständig gefüllt, werden beim Weiterleiten keine
Informationen mehr hinzugefügt. Die letzten Hops zum Server werden dann nicht
mehr dokumentiert.
Versendet ein Knoten eine uplink-Nachricht, wird diese auf einem gewählten Kanal
ausgestrahlt. Wurde innerhalb einer bestimmten Zeit kein Acknowledgement erhalten,
wird die Kanalnummer erhöht und ein neuer Sendeversuch gestartet. Dabei durchläuft
der Knoten eine bestimmte Anzahl von Kanälen rückwärts6 . Wird der Kanal Null
erreicht, war der Sendeversuch wahrscheinlich erfolglos.
Erhält ein Knoten eine uplink-Nachricht im Zustand Listen, wird in Process Packet
übergegangen. Dort folgt aufgrund des empfangenen Nachrichtentyps eine Weiterleitung
in den untergeordneten Zustand Process Uplink (vergleiche Abbildung 3.3). Der Sender
des Paketes wird in die Nachbarschaftsliste aufgenommen. Ist der gesamte Speicherplatz
belegt, wird ein zufälliges Element überschrieben.
Anschließend muss der Empfänger entscheiden, ob er die Nachricht weiterleitet. Das
erste Kriterium dabei ist, ob im Buffer bereits eine uplink-Nachricht existiert. Die
Entscheidung erfolgt mittels der boolschen Variablen B.up ready to send7 . Sie ist auf
¯
¯ ¯
jeden Fall mit true gesetzt, falls nach dem Aufwachen eigene Sensordaten vorhanden
waren. Andernfalls ist sie true, wenn noch eine “alte“ uplink-Nachricht verschickt werden
muss.
Ist B.up ready to send true, wird in den Zustand Send gewechselt, um einen Sendeversuch
¯
¯ ¯
für die uplink-Nachricht im Buffer zu starten. Ist die Variable auf false gesetzt, erfolgt
die zweite Überprüfung: Dabei wird die eigene EPD mit der EPD der Nachricht verglichen.
1. Fall:
Ist die eigene EPD größer, soll die Nachricht nicht weitergeleitet werden. Es erfolgt
6
7
Konstante NR OF CHANNELS, gesetzt in [Sch 04-R02] auf drei.
¯ ¯
Im Quellcode [Sch 04-R02] heißt die Variable B.uplink buffer full
¯
¯
39
ein Übergang zu Blocked. In diesem Status beginnt nach einer Schlafphase erneut der
Zyklus mit dem Zustand Check for Sensor Data.
Abbildung 3.6: Prepare Uplink Packet From Buffer, Quelle:[Sch 03/04, S.19]
2. Fall:
Ist die eigene EPD geringer, so ist der Empfängerknoten näher zum Server. Der Empfänger
wird die Nachricht weiterleiten. Dazu speichert er die erhaltenen Daten im Buffer und
sendet ein Acknowledgement (Zustand Send ACK-Packet(up)). Dieses beinhaltet die
packet id, die ID des Senders und die eigene ID. Anschließend erfolgt das Umkehren der
¯
Belegung von B.up ready to send und ein Übergang in Send, um die uplink-Nachricht zu
¯
¯ ¯
versenden.
Beim Erstellen einer neuen Nachricht aus dem Buffer werden die meisten Inhalte direkt
übernommen (vgl. Abbildung 3.6). Bezüglich der Route der Nachricht gibt es ein besonderes Verfahren:
40
Ist keine downlink-Route im Buffer abgespeichert, wird die Route der Nachricht schrittweise in den Buffer geladen. Dies wird fortgeführt bis kein Knoten mehr in der Route
enthalten ist oder die Arraykapazität nicht mehr ausreicht. Ist noch Kapazität nach dem
Einladevorgang frei, wird die eigene NetID an die letzte Position gefügt.
Bemerkung 3.1.5
Nehme an, dass Knoten A eine uplink-Nachricht versendet. Aufgrund von temporären
Störungen und Verzerrungen sei keiner seiner vorherigen Nachbarn mit geringerer EPD
erreichbar. Haben alle Empfänger seiner Nachricht eine höhere EPD, nimmt keiner die
Nachricht an. So sendet Knoten A solange bis seine EPD größer ist als die einer der
hörenden Knoten. Die EPD wächst schließlich mit jedem uplink-Sendeversuch an (Zustand Punish EPD). Damit wird die Chance bewahrt, dass ein Knoten seine Nachricht
erfolgreich versenden kann, auch wenn vorherige Kommunikationswege ausfallen.
Bemerkung 3.1.6
Ein Knoten sendet seine Nachricht solange, bis er das erste Acknowledgement erhalten
hat. Dies kann natürlich dazu führen, dass mehrere Empfänger die Nachricht gleichzeitig
abarbeiten. Nach dem ersten erhaltenen Acknowledgement oder nach Ablauf der vorgegebenen Sendezeit stoppt der Sender (zunächst) seine Sendeversuche.
Im Zustand Listen ist es möglich, dass ein ACK erhalten wird. Durch die angegebene
Sender ID der zugehörigen Nachricht kann der Knoten bestimmen, ob das ACK für ihn
¯
bestimmt war. Falls das ACK an ihn gerichtet war, vergleicht der Knoten die packet id
¯
des Acknowlegement mit den IDs im Buffer. Stimmen die packet ids überein, kann er die
¯
entsprechende Nachricht als erfolgreich versendet betrachten.
Eine Schwierigkeit ist darin zu sehen, dass ein Knoten nach einem für ihn erfolglosen Sendeversuch zwischenzeitlich im Status Blocked schläft. Das zugehörige ACK wird wahrscheinlich nicht solange gesendet, dass der Sender es im Zustand Listen hört. So erfährt
er nicht, dass sein vorheriger Sendeversuch bereits erfolgreich war.
3.1.4
downlink Kommunikation
Der Nachrichtenfluss geht vom Server zu einem Sensorknoten. Durch die Routen in den
erhaltenen uplink-Nachrichten besitzt der Server Informationen über Wege im Netz. Er
wählt eine Knotenfolge zum gewünschten Empfänger aus und speichert diese in der Nachricht. Aufgrund der Dynamik eines Sensornetzes ist diese Route aber nicht starr zu verfolgen, sondern wird als Anhaltspunkt für die Weiterleitung genommen.
Zunächst folgt die Definition der downlink-Nachricht, anschließend wird das genaue Sendeund Empfangsverhalten beschrieben.
41
Definition 3.1.7 downlink-Nachricht
Eine downlink-Nachricht besteht aus:
• sender id: int;
¯
Die lokale ID des aktuell versendenden Knotens. Diese Information wird zur Integration im Acknowledgement übertragen.
• packet id: byte;
¯
Die ID des Paketes entspricht der ursprünglich vom Server generierten ID und ist
im ACK enthalten.
• target GID : long;
¯
Dient zur Identifizierung des Zielknotens. Entspricht die eigene globale ID dieser
Variablen, muss die Nachricht nicht mehr weitergeleitet werden. Stattdessen werden
die Applikationsdaten verarbeitet.
• new NetID : byte;
¯
Die NetID für den Zielknoten. Diese muss sich nicht von der aktuellen NetID des
Knotens unterscheiden. Jedoch ist mit Hilfe dieser Variablen eine Rekonfiguration
der NetID durch den Server möglich.
• application data : array [DOWN APPL LENGTH] of byte;
¯
¯
¯
Beinhaltet die Anweisungen des Servers für die Applikation des Zielknotens. Das Datenvolumen ist durch die Konstante DOWN APPL LENGTH beschränkt. Im Pro¯
¯
tokoll ist diese Konstante mit dem Wert sechs belegt.
• route : array [ROUTELENGTH] of int;
Wird vom Server gesetzt und soll als Anhaltspunkt für die Richtung des Routings
dienen. Die Länge der Route ist begrenzt durch die Konstante ROU T ELEN GT H.
Mit dieser Beschränkung wird auch eine Beschränkung für die Größe des Sensornetzes gegeben. ROU T ELEN GT H + 1 Hops ist die maximale Entfernung zwischen
dem Server und jedem Knoten.
Erhält ein Knoten eine downlink-Nachricht, wechselt er mit Hilfe des Zustandes Listen in Process Packet in Process Downlink (vergleiche Abbildung 3.3). Dort
wird zunächst mit der boolschen Variablen B.down ready to send8 überprüft, ob
¯
¯ ¯
bereits eine downlink-Nachricht im Buffer gespeichert ist. In einen solchem Fall wird in
den Zustand Blocked gewechselt. Ist die Variable false, wird geprüft, ob die Nachricht
für den Knoten selbst bestimmt ist. Dieser Test findet mit GID = Paket.target GID statt.
¯
8
Im Quellcode [Sch 04-R02] heißt die Variable B.downlink buffer full
¯
¯
42
1. Fall: GID = Paket.target GID
¯
Die downlink-Nachricht wird in den Buffer geschrieben. Das Acknowledgement mit
eigener NetID, der NetID des Senders sowie der Paketnummer wird versendet. Anschließend werden die Daten des Arrays zur Applikation geschickt. Die boolsche Variable
B.already sent wird auf true gesetzt. Im Folgezustand Send besteht dann die Chance
¯
zum Versenden eines anderen Nachrichtentyps (uplink, Beacon . . . ).
2. Fall: GID <> Paket.target GID
¯
Die downlink-Nachricht ist nicht für den betrachteten Knoten bestimmt. Nun wird
überprüft, an welcher Position die eigene NetID in der Route der Nachricht steht. Ist
der Index nach dem Durchlaufen eines Arrays gleich 255, wurde keine Übereinstimmung
gefunden.
a) NetID in Route enthalten
Die eigene NetID stehe an Position k <> 255 der Route. Alle Arrayeinträge nach Index
k werden schrittweise als Route in den Buffer gespeichert. Eine vorhandene uplink-Route
wird in jedem Fall verworfen. Die Variablen B.route is up sowie B.route is down
¯ ¯
¯ ¯
werden entsprechend gesetzt. Im untergeordneten Zustand Buffer downlink message
werden die anderen Daten der Nachricht in den Buffer geladen. Der Knoten versendet
wie im ersten Fall das Acknowledgement und es erfolgt ein Übergang in Send.
Falls im Zustand Send keine uplink-Nachricht zum Versenden existiert, wird ein Sendeversuch für die downlink-Nachricht gestartet. Das Sendeverfahren sowie der Prozess
der Paketherstellung aus dem Buffer sind fast analog zur uplink-Kommunikation. Die
einzigen Unterschiede bestehen darin, dass die Kanäle aufsteigend durchlaufen werden
und die EPD pro Sendeversuch nicht verändert werden. Schließlich ist die EPD für
downlink-Nachrichten nicht von Belang.
Wurde innerhalb der vorgegebenen Zeit erfolgreich versendet, geht der Knoten in
Blocked. Andernfalls wird der erste Knoten der Route als Nachbar gelöscht. Die
Nachricht wird verworfen und die boolschen Prüfvariablen entsprechend gesetzt. Der
Folgezustand ist Check for new Sensor Data.
b) NetID nicht in Route enthalten
In der Route der erhaltenen Nachricht ist die eigene NetID nicht aufgeführt. Nun wird
die Route erneut durchlaufen und geprüft, ob die Route einen Knoten der eigenen
Nachbarschaft beinhaltet. Ist ein Nachbar in der Route unter Index k <> 255 abgelegt,
wird analog zu Fall a) verfahren. Andernfalls wird die Nachricht verworfen. Falls im
43
Buffer eine uplink-Nachricht zum Senden bereitliegt, erfolgt der Übergang zum Status
Blocked. Liegt keine Nachricht vor, so wird in Idle Sleep gewechselt.
Bemerkung 3.1.8
Die downlink-Nachricht kann im Fall 2a) verworfen werden, falls ein vorheriger Nachbarknoten nicht mehr erreichbar ist. Schließlich kann der Knoten nicht davon ausgehen,
dass die Kommunikation nur temporär gestört ist. Wurde die Nachricht nicht gleichzeitig von mehreren Knoten bearbeitet, ist die Nachricht verloren gegangen. Der Server hat die Möglichkeit, dass er mittels der Applikationsdaten ein ACK vom Zielknoten
für die downlink-Nachricht anfordert. Dieses ACK wäre dann in einer uplink-Nachricht
“verpackt“. So existiert für den Server eine Kontrollmöglichkeit und er kann bei Bedarf
die Nachricht erneut schicken.
Bemerkung 3.1.9
Im Fall 2b) wird deutlich, dass die vorgegebene Route nur als Anhaltspunkt dient:
Die Nachricht wird auch von einem Empfänger weiterverarbeitet, der benachbart zu einem Knoten der gegebenen Route ist. So wird die Dynamik des Kommunikationsnetzes
berücksichtigt.
Zudem ist zu beachten, dass die unsynchronisierten Knoten zu einem beliebigen Zeitpunkt
in der Round-Time aufwachen. Da die Route nur als Anhaltspunkt dient, kann gegebenenfalls eine schnellere Weiterleitung erfolgen. Schließlich muss nicht gewartet werden
bis ein bestimmter Knoten erwacht (und empfangsbereit ist).
3.1.5
weitere Nachrichtentypen
In dem Diagramm von Process Packet (siehe Abbildung 3.3) ist zu erkennen, dass es
neben Beacons, uplink- und downlink-Nachrichten noch weitere Nachrichtentypen gibt.
Im 1 QK-Protokoll werden ebenfalls die Nachrichten Inquire, Dump und Reset definiert.
Der Einsatz dieser Typen steht nicht im Vordergrund des Protokolls. Deswegen folgen
hier nur zwei kurze Definitionen:
Definition 3.1.10 Dump und Inquire
Ein Dump ist die Antwort auf ein Inquire und beinhaltet die NetID und GID des gefragten
Knotens sowie seine Nachbarschaftsliste. Für die Zuordnung des Dumps auf das Inquire,
wird zudem die ID des Senders angegeben.
Ein Inquire kann mit unbestimmten Empfänger oder zu einem bestimmten Knoten gesendet werden. Die Knoten müssen aber direkt erreichbar sein, da keine Weiterleitung der
Nachricht erfolgt.
44
Definition 3.1.11 Reset
Das Reset ist an alle Knoten oder einen Bestimmten gerichtet. Die Überprüfung erfolgt
mittels der GID. Nach Erhalt eines Resets wird der Sensorknoten neu initialisiert.
Auch hier erfolgt keine Weiterleitung der Nachricht durch das Protokoll. Die einzige
Möglichkeit besteht darin, dass die Applikation die Weiterleitung veranlasst und die Nachricht in Form eines Dumps oder einer downlink-Nachricht versendet.
3.1.6
Bezug zum ISO/OSI Modell
Die internationale Organisation für Standardisierung (ISO) hat das OSI Referenzmodell
(siehe Abbildung 3.7) als Methode zur genauen Beschreibung von Netzwerken entwickelt
[CR 00, S.8 f]. In dem Modell wird ein ideales Kommunikationsnetzwerk in sieben Ebenen
aufgeteilt. Bestimmte Funktionen zur Netzwerkkommunikation werden für jede Ebene
definiert.
Abbildung 3.7: Das OSI Referenzmodell, in Anlehnung an Quelle:[CR 00, S.9]
Zu der niedrigsten Ebene - 1 - Physical Layer - zählt das Kommunikationsmedium wie
zum Beispiel Fiberkabel oder der Luftraum bei einer drahtlosen Kommunikation. Die
”
meisten Netzwerke implementieren nicht alle Ebenen des Referenzmodells.“[CR 00, S.9].
Die Ebenen eins (Physical), zwei (Data Link) sowie sieben (Application) sind jedoch in
den meisten Netzwerken vertreten. In vielen Sensornetzen sind die Funktionen der übrigen
Ebenen in der siebten Schicht integriert. Mit der geforderten Hardwarespezifikation
(siehe 2.1) stehen nur 256 Byte zur Verfügung. Damit ist eine strenge Unterscheidung
nach dem OSI-Modell nicht möglich.
45
Ich gebe zunächst eine kurze Beschreibung der Ebenen eins, zwei, drei sowie sieben. Dann analysiere ich die Schichten des 1 QK-Protokolls.
Ebene 1 - Physical Layer
Die physikalische Ebene bildet als tiefste Ebene des Modells den Grundstein. In ihr
sind Funktionen zur Konvertierung zwischen der symbolischen Datendarstellung von
Nachrichten und einer physikalischen Repräsentation für das Netzwerkmedium verankert.
Insgesamt werden in dieser Ebene die physikalischen Voraussetzungen für eine Kommunikation geschaffen.
Ebene 2 - Data Link Layer
Zum einen regelt diese Ebene den Zugang zum Netzwerkmedium (MAC, Medium
Access Control). Zum anderen strukturiert sie die Bits in wohl-definierte Gruppen,
“frames“ oder Nachrichten. Darüber hinaus sind in der Data Link Schicht noch weitere
Aufgaben spezifiziert: Die Identifikation von Quell- und Zielstationen im Netzwerk und
die Unterstützung einer fehlerfreien Nachrichtenübertragung.
IEEE 802.3 - auch bekannt als Ethernet - ist als Beispiel eines der zahlreichen Standard
Data Link Protokollen zu nennen.
Ebene 3 - Network Layer
Die Netzwerkebene umschließt Funktionen zugehörig zum Routing von Nachrichten.
Dazu zählt teilweise auch die Suche nach freien Kommunikationswegen. Typischerweise
werden dazu eigene Adressen (zum Beispiel IP-Adressen) eingesetzt.
Ebene 7 - Application Layer
Die Benutzung von Kommunikationsdiensten für die Benutzerapplikation wird in der
siebten Ebene unterstützt. Benutzer interagieren mit dem Netzwerk durch Funktionsund Dienstaufrufe der Applikationsebene. Sie senden oder erhalten Daten zum oder vom
Netzwerk durch alle Ebenen des OSI Modells.
Bezug zum 1 QK-Protokoll
Wie bereits zuvor angemerkt, ist es nicht möglich im 1 QK-Protokoll alle Ebenen des
OSI Modells zu unterscheiden. Im Protokoll werden der Physical und der Application
Layer verwendet [Sch 03/04, S.2]. Dies geht konform mit den meisten Protokollen für
Kommunikationsnetze. Die Data Link Ebene wird aus dem Grund nicht realisiert, da
das Protokoll keine Kollisionsvermeidung besitzt. So können fehlerhafte Übertragungen
46
aufgrund von Interferenzen vorkommen.
Die Netzwerkschicht ist seltener eigenständig in Netzen vertreten, wird jedoch im
1 QK-Protokoll unterschieden. Der Routingmechanismus und die Weiterleitung von
Nachrichten bilden schließlich die Hauptaufgaben des Protokolls. Adressen werden
im eigentlichen Sinne im Protokoll nicht verwendet: Bei der uplink-Kommunikation
existieren keine ausgezeichneten Empfänger. Die Route in der downlink-Kommunikation
dient nur als Anhaltspunkt.
Abbildung 3.8: Schnittstellen der Ebenen, Quelle:[Sch 03/04, S.2]
In Abbildung 3.8 werden die Schnittstellen der Ebenen gezeigt. Neben den unterschiedlichen Schichten werden zudem die Interfaces zum Schlafmodus und zur Uhr dargestellt.
47
Im Mittelpunkt steht die Netzwerkschicht. Sie tauscht sich mit der Applikationsebene
hauptsächlich bezüglich Daten der Sensorik oder der Anwendung aus. Sowohl die Applikationsebene als auch die Netzwerkschicht können den Schlafmodus des Sensorknotens
hervorrufen.
Mit Hilfe der Uhr kann die bereits vergangenen Zeit nach einem festgelegten Zeitpunkt
kontrolliert werden. Dieses wird nicht nur zum Erwachen, sondern auch bei den zeitbegrenzten Sendeversuchen eingesetzt. Des Weiteren generiert die Uhr eine beliebige Zahl
innerhalb eines Intervalls. Diese Zahl wird einerseits für eine randomisierte Schlafzeit
genutzt. Andererseits bedarf es einer probabilistischen Ersetzung eines Nachbarschaftsknotens bei Speicherplatzmangel.
Die Kommunikation zwischen physikalischer und Netzwerkebene beschränkt sich auf den
Austausch von Nachrichten vom/für das Netz. Dabei gibt die Netzwerkebene die Dauer
und den Frequenzbereich für den Sende-/Empfangsvorgang an.
3.1.7
Schwachstellen
Im Folgenden beschreibe ich die Schwachstellen des Protokolls [Sch 04-R02], [Sch 04/04]
und gebe Lösungsansätze für die Behebung.
Unsynchronität
Primär ist natürlich zu bemerken, dass eine Synchronisierung der Sensorknoten viel
Energie einsparen würde. Schließlich wird nur dann gesendet, wenn auch potentielle
Empfänger wach sind. Zudem bestände nicht die Möglichkeit ACKs zu überhören:
Wenn eine Nachricht gegen Ende der zulässigen Sendedauer empfangen wird, kann es
sein, dass der Sender sich während der Sendung des Acknowledgements in der Schlafphase
befindet oder in einem anderen Frequenzbereich sendet.
Die Anzahl der Duplikate wird dadurch erhöht und Energie für unnötiges Senden verschwendet. Bei synchronisierten Knoten würde das Überhören aufgrund der gleichzeitig
eintretenden Schlafphase und gleichzeitigem Kanalwechsel wegfallen.
Daher ist eine Synchronisierung vorteilhaft. Mit der jetzigen Applikationssoftware kann
die Uhrzeit für Synchronisierungszwecke gestellt werden, daher gehe ich in Kapitel 4 auf
einsetzbare Synchronisierungsmethoden ein.
Ausnutzung der Frequenzen
Zum Senden und Empfangen stehen den Knoten NR OF CHANNELS Frequenzbe¯ ¯
48
reiche zur Verfügung. Der Wert dieser Konstante ist in [Sch 04-R02] auf drei gesetzt. Die
Kanäle werden von der Konstante bis Null (oder umgekehrt) durchlaufen und auf jedem
Kanal wird eine gewisse Zeit gesendet.
Da ich nun von einer Synchronisierung ausgehe, werden alle Knoten, die eine uplinkNachricht senden, es zur gleichen Zeit auf dem gleichen Kanal versuchen. Damit stören
sie sich bei jedem Sendeversuch gegenseitig. Der Durchsatz wird gleich Null, wenn
Knoten mit nicht disjunkten Reichweiten eine uplink-Nachricht senden. Die downlinkNachrichten werden in umgekehrter Reihenfolge auf den Frequenzbereichen ausgestrahlt.
So interferieren uplink- und downlink-Nachrichten auf dem zweiten Kanal.
Lösungsidee: Aufgrund des eher dichten Kommunikationsgraphen sollte auf jeden Fall
die Konstante einen höheren Wert zugewiesen bekommen. Zudem wäre es gut, wenn
die Knoten nicht die Frequenzbereiche hintereinander abarbeiten. Gesucht ist eine
Wahrscheinlichkeitsverteilung, mit der ein Kanal für das Senden oder Empfangen
gewählt wird. Mit der Synchronisierung und einer oberen Schranke für einen erfolgreichen
Sendeversuch geht dann kein ACK aufgrund eines Kanalwechsels verloren.
Ich habe mich entschieden diese Lösungsidee weiterzuverfolgen (siehe Kapitel 5).
Schließlich bedarf das Sendeverhalten auf jeden Fall einer Optimierung, wenn die
Knoten synchronisiert werden. Mittels einer guten Wahrscheinlichkeitsverteilung wird
der Nachrichtendurchsatz aufgrund von weniger Interferenzen deutlich erhöht.
Verhungern von Sensordaten
Knoten mit niedriger EPD werden oft in die Weiterleitung von uplink- oder downlinkNachrichten involviert. Daher kann es vorkommen, dass sie im Zustand Listen stets neue
Nachrichten empfangen. Liegen diesen Sensorknoten selbst jedes Mal eigene Daten vor,
so werden die anderen Nachrichten nie weiterverarbeitet. Damit entsteht ein Nachrichtenstau (siehe 6). Weit entfernte Nachrichten haben somit eine lange Bearbeitungszeit
bei einem hohen Nachrichtenvolumen.
Lösungsidee: Jeder Knoten sollte gegebenenfalls in einem ausgewogenem Verhältnis
andere Nachrichten vor den eigenen Daten bevorzugen. Auf diese Idee wird das Kapitel
6 aufgebaut und verschiedene Methoden werden untersucht. Es ist schließlich wichtig,
dass eine gewisse Fairness im Routing besteht. Zudem besitzt der Server bei einer
hohen Latenzzeit von Nachrichten weit entfernter Sender nie einen wirklich aktuellen
Warenbestand.
Asymmetrie
Probleme tauchen auf, falls Sensoren nicht symmetrisch senden und empfangen können.
49
Dieser Unterschied wird im Protokoll nicht berücksichtigt, kann aber in der Realität
durch ungünstige Umwelteinflüsse auftreten.
Lösungsidee: Einführung einer neuen Variablen “reached“:
Bei Erhalt eines Beacon wird der Sender in der Nachbarschaftliste aufgenommen und der
reached-Wert auf false gesetzt. Erst wenn von diesem Knoten ein ACK erhalten wurde,
ist ganz sicher, dass die symmetrische Kommunikation momentan gewährleistet ist.
Ergänzend folgende Fallunterscheidung: Ist ein Wechsel zwischen Symmetrie und Asymmetrie häufig, dann sollte reached wie die EPD dynamisch ansteigen und keine boolsche
Variable sein. Der Einsatz einer boolschen Variable genügt, wenn ein Wechsel selten ist.
Duplikate
Da ein Sender immer so lange sendet, bis er ein ACK erhalten hat, besteht die Gefahr
von redundanten Nachrichtenkopien.
Lösungsidee: Erhält der Sender ein ACK, kann er ein weiteres Signal, ein zweites ACK,
versenden. In diesem zweiten ACK würde bekannt gegeben, welcher Knoten das Paket
weiterleitet. Der eine auserwählte Knoten leitet die Nachricht weiter. Alle anderen
Sensorknoten, die dieses Paket empfangen haben, können es verwerfen.
Diese Lösungsidee muss aber kritisch betrachtet werden. Schließlich erhöht sich dadurch
der Nachrichtenverkehr und die Abarbeitung verzögert sich. Vor dem Einsatz einer
solchen Lösung sollte daher das Aufwand-Nutzen-Verhältnis genauer betrachtet werden.
Anpassung der Round-Time
Die zu Beginn konfigurierte Round-Time wird immer beibehalten. Außerhalb der
Öffnungzeiten müssen die Sensorknoten eigentlich gar nicht erwachen. Die Knoten
verschwenden daher viel Energie.
Lösungsidee: Im Beacon ist die Round-Time eines Knotens enthalten. Nach Erhalt
eines Beacons übernimmt der Empfänger die Round-Time des Senders. So ist es dem
Server mit der Versendung eines geeigneten Beacons möglich die Round-Time aller
Sensorknoten zu verändern. Zum Beispiel könnte der Server nach Ladenschluss am
Samstag eine entsprechende Round-Time festlegen, so dass erst kurz vor der Öffnung
am Montag die Sensorknoten erwachen. Dies ist natürlich nicht nur beim Wochenende,
sondern auch für Feiertage und jeden Tag nach Ladenschluss einsetzbar. Mit Hilfe einer
solchen Anpassung wird eine weitere Energieeinsparung hervorgerufen.
Eine Erweiterung des Lösungsansatzes besteht darin, dass je nach Nachrichtenaufkommen
die Round-Time ebenfalls angepasst wird. Der Server überwacht dazu, wie viele Nachrichten ihn in der Round-Time erreichen. Sind es zu wenige, dann erhöht er die Round-Time:
50
Im Laden herrscht wenig Betrieb und damit ein geringes Nachrichtenaufkommen.
Werden zu viele Nachrichten empfangen, so wird die Round-Time für alle Knoten
verlängert. Mit dieser Verlängerung verringert sich die Kollisionsanzahl und der Nachrichtendurchsatz erhöht sich.
Speicherersparnis
Das 1 QK-Protokoll benötigt etwa 128 Byte RAM-Speicher. Die anderen 128 Byte stehen
der Applikation zur Verfügung. Es kann sein, dass aufgrund der obigen Optimierungen
oder durch eine größere Applikation mehr RAM benötigt wird.
Lösungsidee: Daten können in den FLASH-Speicher ausgelagert werden. Diese sollten
sich aber nicht zu häufig ändern, da der FLASH-Speicher nur eine begrenzte Anzahl von
Überschreibungen unterstützt.
Für eine Sicherung im FLASH-Speicher sind zum Beispiel die genauen Angaben
der
Frequenzbereiche
geeignet.
Zur
Zeit
werden
sie
im
int-Array
FREQUENCY OF CHANNEL gespeichert.
¯ ¯
Eine weitere Möglichkeit besteht in der Auslagerung der Nachbarschaftsinformationen. In
einem Array im FLASH-Speicher könnten alle NetIDs von erfassten Nachbarn gesichert
werden. Um die Dynamik des Sensornetzes abzubilden, würde dann im RAM ein
0-1-Vektor angelegt. Anhand dieses Präsenzvektors könnte entschieden werden, ob der
entsprechende Nachbar in Reichweite ist oder nicht. Bei einer zwischenzeitigen Störung
würde das entsprechende Präsenzbit von Eins auf Null gesetzt. Ist der Knoten wieder
erreichbar, schaltet das Präsenzbit wieder um. Diese Auslagerung ist bei dem wenig zur
Verfügung stehenden Speicher ratsam.
3.2
Bestehende Routingverfahren
Im vorherigen Abschnitt wurde das 1 QK-Protokoll vorgestellt. Ich möchte darüber hinaus
einen ausgedehnteren Blick über den Stand der Forschung geben: Viele Routingverfahren
wurden bereits für Kommunikationsnetze und auch speziell für Sensornetze entwickelt.
Zunächst betrachte ich das Routing in mobilen Ad-hoc Netzen, um abzuschätzen, ob
gleiche Verfahren genutzt werden können. In den anschließenden Abschnitten werden
spezielle Protokolle für Sensornetze vorgestellt.
3.2.1
51
Routingverfahren für mobile Ad-hoc Netze
Sensornetze haben viele gleiche Anforderungen bezüglich des Routings wie mobile Ad-hoc
Netze. Zunächst gehe ich kurz auf die Charakteristiken von mobilen Ad-hoc Netzen
ein. Anschließend werden die Anforderungen an Routingverfahren beschrieben. Dabei
erfolgt stets ein Bezug auf die Eigenschaften von Sensornetzen. Zum Schluss werden zwei
Routingansätze vorgestellt und es erfolgt eine insgesamte Beurteilung über den Einsatz
der Verfahren in Sensornetzen.
Charakteristische Eigenschaften von mobilen Ad-hoc Netzen
Mobilitätscharakteristiken für Knoten in Ad-hoc Netzen sind ein geringer Energievorrat,
wenig Ressourcen, eine dynamische Topologie sowie die problematische Adressierung [Ho
04, S.3f]. Bei drahtlosen Kanälen gilt es eine relativ hohen Fehlerrate, hohe Schwankungen
in der Qualität, der niedrigen Bandbreite, der Broadcast-Natur sowie Sicherheitsaspekte
zu bedenken (vergleiche [Ho 04, S.10]). Diese Charakteristika treffen auch teilweise auf
Sensornetze zu.
Betrachte man zunächst den Aspekt der Adressierung:
Die Vergabe von IP-Adressen kann zum Beispiel mittels eines Buddy-Systems erfolgen
[Ho 04, S.4]. Bezüglich der Adressierung besteht ein großer Unterschied zwischen Sensornetzen und den meisten anderen Kommunikationsnetzen [Mu 04, S.8f]. In Sensornetzen
wird meistens ein Broadcast an alle erreichbaren Knoten durchgeführt. Nachrichten haben
damit keinen ausgewählten Empfänger. Im Extremfall verfügen Sensorknoten über gar
”
keine Identifikation. Der Zugriff erfolgt dann über die Adressierung ihres Aufenthaltsortes
oder über den Typ und Inhalt der von ihnen lieferbaren Daten.“[Mu 04, S.8]
Das 1 QK-Protokoll beinhaltet zwar eine Identifikation mittels der NetID und der
globalen ID ein, beim Routing werden diese aber nur in der downlink-Kommunikation
als Anhaltspunkte eingesetzt [Sch 04-R02], [Sch 04/04].
Anzumerken ist, dass in den meisten Sensornetzen nur eine uplink-Kommunikation
benötigt wird. Die downlink-Kommunikation erfordert gerade im 1 QK-Protokoll den
Einsatz von NetIDs und globalen IDs.
Routinganforderungen
Zu den Anforderungen an das Routing in mobilen Ad-hoc Netzen zählen ein minimaler
Overhead für Kontrollfunktionen und für Prozessorleistung. Zudem soll die RoutingFunktionalität über mehrere Hops realisiert sein. Es bedarf der Verwaltung einer
dynamischen Topologie und eines autonomen, selbst-startenden Betriebes [Ho 04, S.4].
52
Diese Anforderungen sind ebenfalls in Sensornetzen gegeben. Jedoch muss bei den
Routingverfahren für Ad-hoc Netzen betrachtet werden, ob die Voraussetzungen auch
mit den minimalen Ressourcen eines Sensorknotens in Einklang zu bringen sind. Zunächst
stelle ich zwei Verfahren für Routingprotokolle vor.
Routing mittels proaktiver Methode
Dieser Ansatz basiert auf den traditionellen Distance-Vector und Link-State Protokollen
und ist tabellenbasiert. Jeder Knoten verwaltet eine Route zu jedem anderen Knoten.
Ein Austausch der Routinginformationen erfolgt periodisch und/oder ereignisgesteuert.
Der Overhead im Vergleich zu dem im Anschluss vorgestellten reaktiven Verfahren ist
meistens höher. Folgende Protokolle verwenden den proaktiven Ansatz:
• Destination-Sequenced Distance-Vector Routing (DSDV);
siehe [Pe, Bh], [Ho 04, S.5f]
• Topology Broadcast Based on Reverse-Path Forwarding (TBRPF);
mehr Informationen in [Lu,Ko 03., S.9f]
• Optimized Link State Routing (OLSR);
beschrieben in [Lu,Ko 03., S.8f]
Beispiel 3.2.1 Destination-Sequenced Distance-Vector Routing
Beim DSDV bedarf es für die Beurteilung der Aktualität einer Abspeicherung von einer
Sequenznummer zu jeder Route. Zudem wird eine Routingtabelle für alle Knoten im Netz
in der Form
<Zielknoten Addresse, Zielknoten Sequenznummer, nächster Hop, Hopanzahl,
¯
¯
¯
Installierungszeit>
gesichert. Updates der Routinginformationen gibt es in drei Formen: Full, Incremental
und Routing. Full Updates enthalten die gesamte Routingtabelle und werden relativ selten
verschickt. Incremental Updates bestehen nur aus den Informationen, die sich nach dem
letzten Full Update geändert haben. Das Routing Update senden Knoten periodisch an ihre
Nachbarn. Zusätzlich zu diesen periodischen Aktualisierungen schicken Knoten Updates,
wenn sich gravierende Änderungen wie zum Beispiel der Ausfall eines Kommunikationsweges ereignet haben. Erhält ein Knoten von zwei verschiedenen Nachbarn zwei Routen
zum selben Betimmungsort, wählt der Knoten die Route mit der größten Sequenznummer.
Falls die Nummern gleich sind, wird die Route mit der kleinsten Hopanzahl übernommen.
53
Bemerkung 3.2.2
Routingverfahren mit dem proaktiven Ansatz können in Sensornetzen nicht eingesetzt werden. Das Handling einer Routingtabelle ist aufgrund der geringen Speicherverfügbarkeit
und der Dichte von Sensornetzen nicht realisierbar. Mit den gegebenen Ressourcen scheidet ein tabellenbasiertes Routing somit im Vorhinein aus.
Routing mittels reaktiver Methode
Beim reaktiven Ansatz bauen die sendenden Knoten Routen on-demand auf. Knoten
verwalten stets nur aktive Routen. Der Overhead ist normalerweise durch Kontrollfunktionen kleiner als in der proaktiven Methode. Zudem skalieren diese Verfahren besser. Der
Nachteil in diesem Verfahren ist die Latenz bei der Routen-Berechnung.
Protokolle dieser Methode sind:
• Ad Hoc On-Demand Distance Vector Routing (AODV);
siehe [Pe, Ro 00], [Ho 04, S.8f], [Yu 05]
• Dynamic Source Routing (DSR);
eine Beschreibung ist in [Jo, Ma] sowie [We 04] zu finden
Beispiel 3.2.3 Ad Hoc On-Demand Distance Vector Routing
Da AODV aus DSDV enstanden ist, werden auch hier Sequenznummern als RouteAuffrischungskriterium und für die Loop-Prävention verwendet. Es unterstützt sowohl
Unicast- als auch Multicast-Kommunikation. Im Folgenden wird eine Routenanforderung
beschrieben (vergleiche Abbildung 3.9).
Benötigt ein Knoten S eine Route zu einem Bestimmungsort Z wird ein Route-Request
(RREQ) der Form
<Zielknoten Addresse, Zielknoten SequenzNummer, Senderknoten Addresse,
¯
¯
¯
Senderknoten SequenzNummer, Hopanzahl(=0)>
¯
an alle Nachbarn versendet.
Der einzige Nachbar von S ist in diesem Beispiel A. Knoten A überprüft, ob er eine Route
zum Zielknoten hat und die Sequenznummer größer als die des RREQ ist. Ist dieses nicht
der Fall, versendet A seinerseits ein RREQ. Zudem setzt A einen Eintrag für S in der
Reverse-Route (die entgegengesetzte Route) der Form
54
Abbildung 3.9: Beispiel AODV, in Anlehnung an Quelle:[Ho, S.8f]
Zielknoten=S, Nächster Hop=S, Hopanzahl=1.
¯
Nach Erhalt des RREQ, setzt C ebenfalls einen Reverse-Route Eintrag mit
Zielknoten=S, Nächster Hop=A, Hopanzahl=2.
¯
Da C über eine direkte Verbindung zu Z verfügt, und diese Route eine höhere Sequenznummer besitzt, antwortet C mit einem Route-Reply (RREP). Dieses Route-Reply
empfängt A, setzt einen Eintrag in der Forward-Route für Z von
Zielknoten = Z, Nächster Hop=A, Hopanzahl=2.
¯
Anschließend wird das RREP an S weitergesendet, welcher einen ähnlichen Eintrag in
Forward-Route vornimmt. Nun sind allen Knoten auf dem Pfad beide Routenrichtungen
bekannt. S kann seine Datenpakete an Z versenden. Ebenso können problemlos Antworten
von Z nach S verschickt werden, da alle Knoten die Route in beiden Kommunikationsrichtungen kennen.
Bemerkung 3.2.4
Ein reaktiver Ansatz kommt sicherlich eher als die proaktive Methode für das Routing
in Sensornetzen in Frage. Der Einsatz in Sensornetzen ist jedoch nicht sonderlich effizient, wenn nur kleine Datenmengen innerhalb eines Paketes zum Server gesendet werden.
Variieren die Empfänger oder bestehen die Nachrichten aus mehreren Paketen ist diese
55
Methode sicherlich gut: Aufgrund der Störanfalligkeit beim Senden müssen daher bei einem Fehler nur kleine Pakete wiederholt werden.
Im Sensornetz sind die Nachrichten von Knoten fast immer an den Server gerichtet.
Meistens werden lediglich Informationen für die Nachbarschaftsaktualisierung (die Beacons) mit anderen Knoten ausgetauscht. Zudem ist der Aufbau einer festen Route sehr
umständlich, wenn nicht viele Datenpakete übertragen werden müssen. Im 1 QK-Protokoll
sind alle Daten in einer kleinen uplink-Nachricht enthalten. Dies ist vor allem wesentlich
effizienter, wenn viele Knoten Nachrichten senden.
Des Weiteren zeichnet sich ein Sensornetz meistens durch eine hohe Dichte aus. Zudem
können mehrere Knoten mit dem Server direkt kommunizieren. Dies führt beim reaktiven
Ansatz dazu, dass es zahlreiche verschiedene Routen gibt. Bei einem RREQ versuchen
viele Knoten eine geeignete Route zu finden. Dies ruft natürlich ein hohes Nachrichtenaufkommen hervor. Die gleichzeitigen RREQ Anfragen können zudem gegenseitige Interferenzen hervorrufen.
Reaktive Methoden empfehlen sich nicht für Sensornetzen mit geringem übertragenen Datenvolumen und hoher Dichte. Allerdings wurde ein reaktiver Ansatz auch für ein Routingprotokoll speziell für Sensornetze entwickelt. Dieses Protokoll stelle ich in 3.2.2 vor
[Aw,Ho 04].
Resumee
Identische Routingprotokolle für Sensornetze und mobile Ad-hoc-Netze sind kritisch
zu betrachten. Beide Netze basieren zwar auf einer Multi-Hop Kommunikation, die
unterschiedlichen Anforderungen bezüglich Adressierung und der Nutzung des Speichers
können jedoch gravierend auseinandergehen.
Als Charakteristik für Mobiliät wird ein geringer Energievorrat genannt. Trotzdem muss
die Energieeffizienz für Sensornetze bedeutend ausgeprägter sein als die Effizienz für
Netze mit Laptops. Die weitere Anforderung über einen geringen Nachrichtenoverhead
und -aufwand wird bei jedem Netzwerk gewünscht.
Mit der speziellen Hardwarespezifikation der Diplomarbeit (siehe 2.1) ist zudem Speicher
eine sehr knappe Ressource. Damit scheidet ein tabellenbasiertes Routingverfahren
glänzlich aus. Aber auch die reaktive Methode ist für einen Einsatz nur bedingt geeignet.
Die speziellen Anforderungen in Sensornetzen erfordern somit eigene Routingprotokolle.
Eine Auswahl von entwickelten Verfahren wird in den folgenden Abschnitten gegeben.
Weitere Informationen und Beispiele zu den hier vorgestellten Routingansätzen sind in
[Ho 04, S.4f], [Yu 05, S.9 f] und [Wi 04] zu finden.
3.2.2
56
Das Pulse Protokoll
Im Pulse Protokoll [Aw,Ru 04], [Aw,Ho 04] werden zum ersten Mal Routing und Synchronisation vereint. Das Protokoll dient der so genannten “viele-zu-einem-Kommunikation“
(viele Knoten senden zu einem Server). Periodisch wird eine Nachricht durch das Netz
geflutet und gleicht dabei einem Puls. Diese Nachrichtenflut (Flooding) wird initialisiert
vom Server und bildet einen Spannbaum innerhalb des Netzes. Anhand des Pulses wird
jeder Knoten mit der besten Route zum Server sowie Informationen über die Uhrzeit aktualisiert.
Jeder Sensorknoten merkt sich alleine den Knoten, welcher ihm die geflutete Nachricht
übermittelt hat und die geringste Metrik besitzt. Falls ein Sensorknoten Nachrichten senden oder empfangen möchte, wird als Antwort auf die Flutung eine Reservierungsnachricht
gesendet. In dem zum Server weitergeleiteten Reservierungspaket ist die Adresse des Ursprungsknotens enthalten. Zudem wird in der Nachricht der genutzte Pfad zum Server
dokumentiert. Damit stehen dem Server Informationen über Knotenwege zur Verfügung.
Der genutzte Reservierungsmechanismus ist analog zu Route-Response in AODV (siehe
Abschnitt 3.2 sowie [Pe, Ro 00], [Ho 04, S.8f]).
Eine Reservierungsnachricht ist natürlich unnötig zum Server zu senden, wenn keine Kommunikation mit dem Server gewünscht ist. Besteht während des Floodings noch eine Kommunikation mit dem Server, muss der Senderknoten diese Route erneut aufbauen. Knoten,
die nicht in den Transport von einem Reservierungspaket involviert werden, können bis
zum nächsten Flooding schlafen. Dadurch wird die Energieeffizienz im Pulse Protokoll
erreicht. Ebenso ist der Speicherverbrauch für das Routing sehr gering. Schließlich wird
nur der Knoten mit der geringsten Metrik als Kommunikationspartner abgespeichert.
Bemerkung 3.2.5
Wie bereits in der Bemerkung zum reaktiven Ansatz (siehe 3.2.4) hervorgehoben, ist dieses Verfahren gut, wenn große Datenmengen unterteilt in mehreren Pakete transportiert
werden. Da im Szenario für die Diplomarbeit aber das zum Server übertragen Datenvolumen eines jeden Knotens nur sehr gering ist (etwa 36 Byte), lohnt sich ein vorheriger
Routenaufbau für eine Kommunikation nicht.
3.2.3
Data Collection Protokoll
Das Data Collection Protokoll (DCP) [Ha,Gr 04], [Sen 05] involviert, dass vor der Nachrichtenweiterleitung Daten gesammelt und gepackt losgeschickt werden. Zur Realisierung
des Routings schließen sich benachbarte Knoten zu einem Cluster zusammen. Bei diesem
so genannten Clustering koordinieren die Knoten die Datenerfassung und -verarbeitung
57
auf lokaler Ebene. Ein Knoten des Zusammenschlusses, der Clusterkopf, übernimmt eine
besondere Rolle: Er sammelt die Daten und überträgt sie zum Server.
Nun gibt es zwei Ansätze für die Übertragung zwischen Clusterköpfen und dem Server
[Sen 05]:
Eine direkte Kommunikation zwischen diesen Teilnehmern wird in dem LEACH-Protokoll
Low-Energy Adaptive Clustering Hierarchy verfolgt. Für weitere Informationen
zum LEACH-Protokoll wird auf [He,Ba 00], [He,Ch 00] sowie [Yu 05, S.8 f] verwiesen. Da
im Szenario der Arbeit keine direkte sondern eine Multi-Hop Kommunikation stattfinden
soll, verweise ich an dieser Stelle nur kurz auf diese Lösung.
Die Nachrichtenübertragung vom Clusterkopf zum Server kann aber auch mit Hilfe von
Mulit-Hops erfolgen (Clustered-Multihop-Transmission) [Ha,Gr 04]. Eine solche Kombination von Multihop-Übertragung und dem Clustering-Ansatz wird im Data Collection
Protokoll realisiert. Deswegen folgt eine genauere Betrachtung der Clusterorganisation
und des lokalen Routingverhaltens.
DCP ist aufzuteilen in zwei Phasen:
Zunächst wird im Setup das Netzwerk formiert. Dabei erkunden und demonstrieren die
Sensorknoten und der Server ihre Nachbarschaft (zum Beispiel mit Hilfe von Beacons).
Beim Abschluss der Setup-Phase wissen alle Knoten in der Nähe des Servers, dass sie
direkt mit diesem kommunizieren können. Alle anderen Knoten (Clustermitglieder)
kennen “ihren“ Clusterkopf, zu welchem sie ihre erfassten Daten schicken. Die Adresse
dieses Knotens wird Packet Forward Address (PFA) genannt.
Es folgt die zweite Phase, der “Dauerzustand“. In diesem Zustand werden die Nachrichten
zum Server geleitet. Doch die Bezeichnung Dauerzustand ist irrtümlich: Aufgrund der
Dynamik der Kommunikationswege muss die Setup-Phase immer wieder aufgerufen
werden. Die Häufigkeit des Phasenwechsels hängt natürlich von der Häufigkeit von
Ausfällen und Topologieänderungen ab.
Das Netz ist damit untergliedert in mehrere Cluster, die aus einem Clusterkopf und
mindestens einem Clustermitglied bestehen. Wie bereits oben erwähnt, sammeln die
Clusterköpfe die Daten der Clustermitglieder und leiten diese zum Server weiter. Die
Wahl eines geeigneten Clusterkopfes ist nicht trivial: Zum Beispiel muss der ausgewählte
Knoten über genügend Energie verfügen. Die Datenaggregation sowie das Routing
verbrauchen schließlich Energieressourcen. Um den Energieverbrauch innerhalb des
Clusters möglichst klein zu halten, sollte der Clusterkopf sich in der Mitte des Clusters
befinden.
Ein Knoten kann mehrere PFA zugewiesen bekommen. Dies erhöht die Robustheit und
die Energieeffizienz des Protokolls. Hat ein Knoten mit mehreren PFAs eine Nachricht
zu versenden, schickt er diese an den Clusterkopf mit der geringsten Distanz.
58
Bemerkung 3.2.6
Die clusterbasierte Datensammlung ist sicherlich ein enormer Vorteil gegebenüber der einzelnen Datenweiterleitung. Das globale Nachrichtenaufkommen wird drastisch reduziert.
Erfassen die Sensordaten mittelbare Werte wie zum Beispiel die Temperatur, kann der
Clusterkopf eine Durchschnittstemperatur anstatt die Sammlung aller Temperaturen in
seiner uplink-Nachricht versenden. Die Nachrichtengröße wird damit wahrscheinlich deutlich verringert.
Jedoch ist eine Datensammlung mit der gegebenen Hardwarspezifikation der Diplomarbeit
nicht möglich. Die Beschränkung des RAMs auf 256 Byte lässt keine Datensammlung zu.
Für weitere Informationen verweise ich auf [Ha,Gr 04] und [Sen 05]. [Ha,Gr 04] beschreibt
zwar das DCP für Sensorknoten mit Bluetooth, die generelle Funktionsweise des DCP
Protokolls wird darin jedoch deutlich.
3.2.4
Direct Diffusion
Im Ansatz von Direct Diffusion [In,Go 00], [Go 05] steht die Datenübertragung bestimmter
Daten im Mittelpunkt (Diffusion=Verbreitung). Die Auswahl einer Route wird in der
Applikationsebene getroffen.
Ein Knoten bekundet sein Interesse in gewissen Daten. In einer solchen interest-Nachricht
wird das Ereignis genau beschrieben, über welches der Knoten Informationen erhalten
möchte. Die Ereignisbeschreibung erfolgt durch so genannte Attribut-Wert-Paare (siehe
Abbildung 3.10). Der Sender der interest-Nachricht wird mit Sink bezeichnet.
Abbildung 3.10: Attribut-Wert-Paare, Quelle:[In,Go 00, S.3]
Der Typ in den Attribut-Wert-Paaren gibt an, welche Daten erfasst werden sollen. Die
Intervallangabe ist die Zeitspanne, in welcher neue Daten zum Sink gesendet werden.
Da dies nur eine zeitlich begrenzte Aufgabe sein soll, bedarf es der Angabe der Dauer
der Datenerfassung (in duration). Neben der zeitlichen gibt es auch eine räumliche
Beschränkung: Ausschließlich Sensorknoten, die sich in einer gewissen Entfernung zum
59
Sink befinden, sollen den Sensing-Task durchführen.
Abbildung 3.11: Periodische interest-Nachricht eines sinks, Quelle:[In,Go 00, S.4]
Damit der Sink sein Interesse laufend bekundet, sendet er für alle aktiven Tasks
eine interest-Nachricht an seine Nachbarn (siehe Abbildung 3.11). In dieser wird der
Timestamp automatisch erhöht.
Jeder Knoten verfügt über einen Speicher für aktuell bestehende Interessensanfragen.
Dabei werden nur wirklich unterschiedliche Interessen gesichert. Zwei Interessensanfragen
gelten als unterschiedlich, wenn der type, das interval oder das rect nicht übereinstimmen.
Im Interessenspeicher werden keine Sinks abgelegt. Da nur aktive Interessen gespeichert
werden, skaliert dieser Ansatz gut.
Nach Erhalt einer interest-Nachricht überprüft der Knoten, ob diese Anfrage bereits
im Speicher enthalten ist. Zudem setzt er einen Verweis (genannt Gradient) auf den
anfragenden Knoten. Existiert bereits ein Eintrag mit Gradient, werden nur die Attribute
timestamp und duration aktualisiert. Im Gradienten werden zudem die Datenrate und
die Richtung für die Datenweiterleitung festgehalten.
Kann er die Daten selbst nicht liefern, sendet er die interest-Nachricht an seine Nachbarn weiter. Bei dem Weiterleiten kann der Knoten sich für einen weiteren Broadcast
entscheiden. Dieses entspricht dem Flooding. Falls dem Knoten keinerlei Informationen
zur Verfügung stehen, welcher Sensorknoten den Sensing-Task erfüllen kann, ist der
Re-Broadcast die einzige Möglichkeit. Liegen derartige Informationen vor, kann er die
Nachricht nur an Knoten “in der richtigen Richtung“ weiterleiten. Für die Nachbarn ist
der weiterleitende Knoten der Sink. Dieses heißt lokale Interaktion. Falls ein Knoten bereits Daten von einer Quelle zum Sink leitet, sendet er eine interest-Nachricht nicht weiter.
Erhält ein Knoten eine interest-Nachricht, dessen Daten er liefern kann und er sich in der
geforderten Region befindet, wird dieser zur Datenquelle. Er startet mit der gewünschten
Sensordatenerfassung und sendet zunächst einmal Daten an alle seine benachbarten
Gradienten. Diese Daten dienen der Erforschung des günstigsten Pfades: Mit Hilfe der
60
Weiterleitung zu allen Gradienten eines involvierten Knotens wird die “erforschende
Nachricht“ zum Sink weitergeleitet. Dieser antwortet mit einer Bestätigungsnachricht
(reinforcement-Message) dem ersten Knoten, von dem er die Nachricht erhalten hat.
Diese Bestätigungsnachricht wird zur Quelle geleitet. So entsteht der Kommunikationspfad (vergleiche Abbildung 3.12) und die Quelle sendet im gewünschten Intervall die
Daten zum Sink. Zusätzlich verschickt die Quelle periodisch die erforschende Nachricht
an alle verzeichneten Gradienten. Jedoch werden Gradienten nur eine beschränkte Zeit
gespeichert, auch wenn neue Interessen angekommen sind.
Abbildung 3.12: Ablauf von Direct-Diffusion, Quelle:[In,Go 00, S.4]
Bestehen zu einem Interesse mehrere Sinks, erhalten alle eine erforschende-Nachricht.
Für jeden Sink besteht ein Pfad zur Quelle. Dieser Pfad kann mit Pfaden anderer Sinks
übereinstimmen. Für das Nachrichtenaufkommen ist es sogar besonders gut, wenn Pfade
von mehreren Sinks gemeinsam genutzt werden. Schließlich wird dann für mehrere Sinks
nur eine Nachricht produziert. Erst wenn sich die Wege trennen, entstehen mehrere
Nachrichten, so dass auch jeder Sink informiert wird.
Direct Diffusion nutzt einen Interessenspeicher, um Flooding zu vermeiden. So
werden Nachrichten nur einmal wiederholt. Es wird meistens ein guter Pfad mit kurzer
Verzögerungszeit zwischen Quelle und Sink gefunden. Die periodische Wiederholung der
interest- und der erforschenden-Nachrichten sind wichtig, um die Dynamik im Netz zu
unterstützen. Fehlerhafte Kommunikationspfade zwischen Quelle und Sink können damit
repariert werden.
Bemerkung 3.2.7
Direct Diffusion ist sicherlich eine Verbesserung eines reinen Flooding-Protokolls. Die
61
Nachrichtenflut wird reduziert. Falls Daten nur einmal zwischen zwei Knoten versendet
werden, sollten diese in der erforschenden-Nachricht enthalten sein. Dann müsste der
Sink keine Bestätigungsnachricht versenden. Dieses Verfahren entspricht dann aber genau dem Flooding, da die interest-Nachricht meistens mittels Broadcast an alle Nachbarn
geflutet wird.
Das zugrunde gelegte Modell bei Direct Diffusion kann kaum auf das Szenario der Diplomarbeit übertragen werden. Der Sink ist stets der Server, die Quellen sind alle Sensorknoten. Der Server ist allerdings nur an Nachrichten interessiert, wenn ein Ereignis beim
Sensorknoten aufgetreten ist (die Änderung des Warenbestandes). Um zudem Informationen von allen Knoten zu erhalten, müsste der Server eine interest-Nachricht pro Knoten
stellen.
Interessant ist der Ansatz von Direct Diffusion sicherlich für Sensornetze mit Kommunikation zwischen Sensorknoten oder mit verschiedenen Servern. Gut einzusetzen ist das
Protokoll, wenn unterschiedliche Quellen periodisch Daten an einen oder mehrere Knoten
liefern sollen.
3.2.5
Insgesamte Beurteilung der Routingverfahren
Anhand der bereits gegebenen Bemerkungen ist zu sehen, dass kein in 3.2 vorgestelltes
Verfahren auf die Gegebenheiten des Szenarios besser angepasst ist als das 1 QK-Protokoll.
Alle Protokolle können nicht das geringe Datenvolumen der Nachrichten ausnutzen. Aufgrund der Größe ist es effizienter die Nachricht gleich zu versenden, anstatt zunächst eine
Route aufzubauen. Die tabellenbasierten Routingalgorithmen fallen natürlich aufgrund
des geringen RAM-Speichers aus.
Es ist also festzuhalten, dass das 1 QK-Protokoll für eine unabhängige downlink- und
uplink-Kommunikation mit kleiner Nachrichtengröße am besten geeignet ist. Die anderen
Routingverfahren sind sicherlich bei einem höheren Datenvolumen oder für eine Kommunikation unter den Sensorknoten effektiver einzusetzen.
Kapitel 4
Synchronisation
Im 1 QK-Protokoll wurde mit unsynchronisierten Knoten gearbeitet. Für meine Weiterentwicklungen des Protokolls setze ich eine Synchronisierung voraus. Daher stelle ich in
diesem Kapitel einige Synchronisierungsmethoden vor.
Zunächst erfolgt eine Beurteilung, ob klassische Synchronisationsalgorithmen in Sensornetzen eingesetzt werden können (siehe 4.1). Speziell für die Synchronisierung von
Sensorknoten wurden bereits einige Verfahren entwickelt. In Abschnitt 4.2 wird die
Beschreibung von drei bekannten Verfahren sowie eine Beurteilung über die zu nutzende
Methode abgegeben. Gegenüber der alleinigen Synchronisation der Uhren könnte zudem
der Aufwachpunkt der Knoten abhängig von ihrer Position (“regalweise“) koordiniert
werden. Daher bildet den Abschluss dieses Kapitels eine Untersuchung, ob ein globaler
oder lokaler synchroner Aufwachpunkt der Sensorknoten einen höheren Nachrichtendurchsatz ermöglicht (siehe 4.3).
4.1
Einsatz klassischer Synchronisierungsalgorithmen in Sensornetzen
Eine einmalige Uhrensynchronisierung der Knoten ist keine dauerhafte Synchronisation.
Zur Dauerhaftigkeit bedarf es einer stetigen Korrektur des Uhrendrifts [Rö 04].
Klassische Synchronisierungsalgorithmen wurden für traditionelle verteilte Systeme
entwickelt, in denen die Energieeffizienz keine Rolle spielte [Kr 03, S.3f] und keine
dynamischen Kommunikationsverbindungen betrachtet wurden [Rö 04]. Beim Design
der klassischen Algorithmen wurde davon ausgegangen, dass das Netzwerk ohne
Einschränkungen benutzt werden kann. Ebenso war der Einsatz des Prozessors uneinge-
4 Synchronisation
63
schränkt. Diese Argumente führen dazu, dass klassische Zeitsynchronisationsalgorithmen,
wie zum Beispiel das im Internet eingesetzte Network Time Protokoll (NTP) (siehe [Bü
93]), in Sensornetzen nicht eingesetzt werden sollten [Ya 05].
Für eine Zeitsynchronisierung in Sensornetzen ist eine hohe Präzision erforderlich.
“Wegen der engen Kopplung der Sensornetze an die Realität sollte die Synchronisation
sehr genau sein. Nur so kann die Beobachtung hinreichend wirklichkeitsgetreu gemacht
werden. Um ein Objekt anhand von Laufzeitunterschieden akustischer Signale zentimetergenau zu orten, ist bereits eine Präzision im µs-Bereich nötig.“ [Kr 03, S.2]
Die Genauigkeit eines Verfahrens hängt von der Häufigkeit der Synchronisierung ab. Eine
häufige Synchronisation impliziert allerdings einen hohen Energieverbrauch.
Selbst wenn ein Protokoll wie NTP trotz des hohen Energieverbrauches eingesetzt werden
könnte1 , würde die Präzision nicht ausreichen. Dies ist ein zusätzlicher Grund dafür, dass
keine klassischen Algorithmen in Sensornetzen realisiert werden sollten.
Weitere Anforderungen für Synchronisationsalgorithmen für Sensornetze sind aufgrund ihrer Dichte die Skalierbarkeit sowie Robustheit [Kr 03, S.2]. Über diese Punkte
hinaus gilt es noch einer Betrachtung der Kosten und Größe der Hardware: Sensorknoten
sollen möglichst preiswert produziert werden. Bei einem Entwurf eines Algorithmus muss
daher auch die Hardwareausstattung und Größe des Knotens betrachtet werden. Es ist
zum Beispiel unmöglich eine Synchronisation zu erreichen, indem jeder Knoten mit einer
Atomuhr ausgestattet wird [Kr 03, S.2].
4.2
Synchronisationsverfahren für Sensornetze
Da klassische Algorithmen keinen praktikablen Einsatz in Sensornetzen versprechen,
wurden eigene Synchronisationsverfahren entwickelt. Ich stelle hier in chronologischer
Entwicklungsreihenfolge drei bekannte Algorithmen vor. Im Anschluss erfolgt die Bewertung der Verfahren für den Einsatz der gegebenen Voraussetzungen der Diplomarbeit.
Der Vollständigkeit halber möchte ich an dieser Stelle den Uhrendrift zunächst
definieren [Rö 01, S.2f]:
1
Der hohe Energieverbrauch entsteht dadurch, dass die Clients immer am Netzwerk auf Nachrichten
lauschen.
4 Synchronisation
64
Definition 4.2.1 Uhrendrift
Die interne Uhr wird hardwaremäßig unterstützt von einem Oszillator und führt eine
Approximation C(t) für die reale Uhrzeit aus.
Z t
C(t) = k ·
ω(τ )dτ + C(t0 )
t0
ist eine reale Funktion über der Realzeit t. Die Funktion ist abhängig von der Kreisfrequenz ω(τ ) des Oszillator. k ist ein zur Kreisfrequenz proportionaler Faktor.
Für eine perfekte Uhr würde dC/dt = 1 gelten. Jedoch besitzt jede Uhr einen Uhrendrift
und ist damit nicht perfekt. Eine genaue Bestimmung des Drifts ist aufgrund von Umwelteinflüssen nicht möglich. Jedoch wird angenommen, dass der Uhrendrift das Maximum
von etwa ρ = 10−6 nicht übersteigt:
1−ρ≤
4.2.1
dC
≤1+ρ
dt
Time Stamp Synchronization
Das Time Stamp Synchronization - Verfahren wurde in 2001 von Kay Römer von der
Eidgenössischen Technischen Hochschule (ETH) Zürich entwickelt. Die Intuition bei
dieser Synchronisierung ist, dass Nachrichten von anderen Sensorknoten mit den eigenen
Nachrichten in einen zeitlichen Zusammenhang gebracht werden sollen [Rö, Bl 05],
[Rö 04], [Rö 01]. Die lokalen Uhren der Knoten werden nicht synchronisiert. Es bedarf
schließlich nur einer korrekten zeitlichen Zuordnung der Nachrichten. Dazu setzt der
Sender in seinen Nachrichten als Zeitstempel die Universial Time (UTC) seiner eigenen
unsynchronisierten Zeit. Jeder Empfänger transformiert diesen Zeitstempel dann in seine
lokale Zeit. Dabei wird UTC als Format für die Zeitübertragung genutzt.
Aufgrund der Nachrichtenübertragung kann eine Transformationen nicht mit einer hohen
Präzision durchgeführt werden. Für die Erreichung eines exakten Wertes werden eine
obere und untere Grenze der aufgetretenen Verzögerungszeit eingesetzt. Der Algorithmus
schätzt daher vor der Transformation die vergangene Realzeit zwischen Erzeugung des
Zeitstempels und Ankunft beim Empfänger nach unten und oben ab. Diese Grenzen
werden dann in die Empfängerzeit umgewandelt und jeweils vom Empfangszeitpunkt
subtrahiert. Das resultierende Intervall beschreibt die untere und obere Grenze für den
Zeitpunkt der lokalen Zeit des Empfängers.
Bemerkung 4.2.2
Dieses Synchronisationsverfahren ist ausreichend, wenn Nachrichten von unterschiedlichen Knoten in ein Verhältnis gesetzt werden sollen. Jedoch wird mit der Time Stamp
4 Synchronisation
65
Synchronization keine Uhrensynchronisation realisiert. Diese ist gerade wichtig für das
Szenario der Diplomarbeit, da die Sensorknoten gleichzeitig erwachen sollen.
4.2.2
Reference Broadcast Synchronization
Der Algorithmus Reference Broadcast Synchronization (RBS) wurde von Jeremy Elson,
Lewis Girod und Deborah Estrin im Jahr 2002 an der University of California, Los Angeles
entwickelt [El, Gi 02], [Kr 03]. Das Verfahren kann eine Präzision der internen Synchronisation (Uhrensynchronisation) im Mikrosekunden-Bereich erzeugen. Die signifikanteste
Anforderung von RBS ist, dass ein Broadcast fähiges Netzwerkmedium erforderlich ist.
RBS kann zum Beispiel nicht in einem Netzwerk von Punkt-zu-Punkt-Verbindungen eingesetzt werden.
Bei der Reference-Broadcast Synchronization senden Knoten Reference-Beacons mittels
Broadcast zu ihren Nachbarn. Dieses Reference-Beacon enthält keinen expliziten Zeitstempel, vielmehr nutzen die Empfänger die Ankunftszeit als Referenzpunkt zur Uhrensynchronisation. Eine besonders hohe Präzision wird erreicht, wenn hardewaremässig ein
Interrupt unterstützt wird: Bei der Ankunft der ersten Bits der Synchronisationsnachricht wird dieses Interrupt ausgelöst, damit sich die interne Verzögerungszeit minimiert.
Um nun eine Synchronisation zu erreichen, werden die Ankunftszeiten mit den anderen
empfangenen Nachbarn verglichen.
Eine bessere Präzision kann durch mehrere aufeinander folgende Reference-Broadcast
Nachrichten erreicht werden:
1. Ein Sender sendet m Reference-Beacons mittels Broadcast.
2. Jeder der n Empfänger, zeichnet die Empfangszeiten in seiner lokalen Uhrzeit auf.
3. Die Empfänger tauschen ihre Beobachtungen aus.
4. Jeder Empfänger i kann seine Offset-Phase zu einem beliebigen anderen Empfänger
j berechnen. Der Offset wird anhand der durchschnittlichen Empfangszeiten der
Reference-Beacons ermittelt, welche i und j empfangen haben.
Sei n die Anzahl der Empfänger, m die Anzahl der versendeten Reference-Beacons,
Tr,b die Uhrzeit von r als Broadcast b erhalten wurde. Dann gilt:
m
1 X
∀i, j ∈ n : Offset[i, j] =
Tj,k − Ti,k .
m k=1
Dieses Verfahren wurde aber in realer Hardware noch nicht realisiert, da es falsch gehende
Uhren nicht ausschließt. Daher wird eine numerische Lösung benutzt, in welcher auch die
obige Gleichung eingesetzt wird. Das maximale Offset wird Group Dispersion genannt.
4 Synchronisation
66
Abbildung 4.1: Präzisionsverbesserung der Group Dispersion, Quelle:[El, Gi 02, S.8]
Beispiel 4.2.3
Mit dem numerischen Verfahren und einer einfachen Konstruktion von zwei Empfängern
wird die Präzision mit Hilfe von dreißig Reference Broadcasts von 11µs auf 1, 6µs verbessert (visualisiert in Abbildung 4.1 (rot)). Dabei ist 11µs der durchschnittliche Fehler bei
der Synchronisierung zweier Empfänger mit einem Reference Beacon.
Sind zwanzig Empfänger vorhanden, kann mit der gleichen Anzahl von Reference Broadcasts eine Präzision von 5, 6µs erreicht werden (schwarz eingezeichnet in Abbildung 4.1).
Die bisherige Beschreibung diente einer Synchronisierung von Knoten, welche sich in einer einzigen Broadcastregion befanden. In einer Erweiterung für RBS werden Knoten
synchronisiert, welche sich innerhalb von mehreren Broadcastregionen befinden. Zur Visualisierung der folgenden Erläuterung wird auf Abbildung 4.2 verwiesen.
Die mit A und B bezeichneten Knoten senden einen Synchronisationspuls. A und B
können sich gegenseitig nicht hören, jedoch empfängt Knoten 4 beide Reference-Beacons.
Die Knoten 1 − 3 und 5 − 7 vergleichen untereinander ihre Uhrzeiten wie zuvor beschrieben. Knoten 4 hat als Einziger beide Beacons empfangen und ist damit in einer anderen
Situation: Er kann die Uhrzeiten beider Broadcastregionen miteinander in einen Bezug
setzen. Damit wird ein Vergleich von Ereignissen aus getrennten Nachbarschaften möglich:
Sei PA der Zeitpunkt vom Versenden des Pulses von A. Für B ist PB analog. Des Weiteren
sei Ereignis 1 (E1 ) bei Knoten 1 zwei Sekunden nach Hören des Pulses von A eingetreten.
¯
Vier Sekunden vor dem Puls von B verzeichnete Knoten 7 das Ereignis 7 (E7 ). Knoten 1
¯
und 7 können 4 über die temporäre Zuordnung ihrer Ereignisse informieren. Anhand der
4 Synchronisation
67
eignen Empfangszeiten kann Knoten 4 bestimmen, dass der Puls von A zehn Sekunden
später als der von B erfolgt (Pa = PB + 10).
Abbildung 4.2: MultiHop-Synchronisation, Quelle:[El, Gi 02, S.12]
Folgende Gleichungen entstehen:
E1 = PA + 2
E7 = PB − 4
PA = PB + 10
⇒ E1 = E7 + 16
Die beiden Ereignisse E1 und E7 können damit in eine globale Beziehung gebracht
werden, da der Durchschnitt der Broadcast Regionen von A und B nicht leer war.
In der Realität liegt jedoch meistens kein einzelner Gateway wie in Abbildung 4.2
vor, welcher die Uhrzeiten der einzelnen Nachbarschaften umrechnet.
In Abbildung 4.3a) sind die mit Buchstaben bezeichneten Knoten Synchronisationssender
und die nummerierten Knoten stellen Empfänger dar. Jeder Sender baut eine eigene
Nachbarschaft auf, in welcher der gleichen Sender zur Synchronisation gehört wird.
Werden diese Nachbarschaftsbeziehungen als Kanten in einem Graphen visualisiert,
entsteht Abbildung 4.3b). Gilt es Ereignisse aus verschiedenen Nachbarschaftsbereichen
miteinander zu vergleichen, hilft der Pfad im Graphen bei der Zeitkonvertierung: Sollen
Ereignisse von Knoten eins (E1 (R1 ), Ereignis 1 in lokaler Zeit von Knoten 1) und zehn
¯
(E10 (R10 )) in Beziehung gebracht werden, so erfolgt eine Transformation der Zeit von
Ereignis 1 in die Zeit von Knoten zehn:
¯
E1 (R1 ) → E1 (R4 ) → E1 (R8 ) → E1 (R10 )
4 Synchronisation
68
Der Transfomationsfehler erhöht sich bei jeder Umwandlung. Aber er wächst nur mit der
Wurzel der Anzahl von Hops.
Abbildung
4.3:
Allgemeines
Modell
für
die
MultiHop-Synchronisation,
Quelle:[El, Gi 02, S.14]
Bemerkung 4.2.4
Dieses Protokoll kann mit der vorgegebenen Hardware für die Arbeit eingesetzt werden.
Schließlich findet die gesamte Kommunikation mittels eines Broadcast statt. Jeder Knoten hat die Möglichkeit als Synchronisationssender zu agieren. Wechseln die Synchronisationssender, kann eine globale Uhrensynchronisation stattfinden. Die Sendereichweiten
überschneiden sich schließlich auf jeden Fall.
Der Austausch der Empfangszeiten zwischen den Sendern kann einfach realisiert werden: Der Synchronisationssender bestimmt zufällig aus seiner Nachbarschaftsliste eine
NetID, welcher seinen Empfangszeitpunkt allen anderen Knoten bekannt gibt. Die anderen Empfänger können mit dieser Propagierung ihren Offset berechnen.
Eine Transformation wird in der Arbeit nicht benötigt, da Nachrichten von unterschiedlichen Knoten nicht in eine gegenseitigen Beziehung gebracht werden müssen.
Hilfreich wäre es, wenn bei der Initialisierung der Knoten eine Zeit vom Server mitgeteilt
würde, welche dann direkt lokal jeder Knoten übernimmt. So entsteht zu Beginn nur ein
geringer Offset pro Hop. Da die Sendereichweite Knoten mit verschiedenen Hopdistanzen
beinhaltet, sollte eine gute globale Synchronisation schnell erreicht werden.
4 Synchronisation
4.2.3
69
Timing Sync Protocol for Sensor Networks
Das Timing Sync Protocol for Sensor Networks (TPSN) wurde von Saurabh Ganeriwal,
Ram Kumar und Mani B. Srivastava in 2003 an der University of California in Los Angeles entwickelt [Ga,Ku 03], [Ma,Fr 02]. Es soll eine zweimal bessere Leistung vollbringen
als das Verfahren Reference-Broadcast Synchronization. Zudem zeigen die Autoren, dass
die Synchronisationsexaktheit nicht deutlich mit der steigenden Anzahl von Knoten abnimmt. Daher skaliert das Protokoll gut.
Das Protokoll ist aufgeteilt in zwei Phasen: Level Discovery Phase sowie Synchronization Phase. In der ersten Phase wird eine hierarchische Topologie aufgebaut: Ein Knoten
(“Root Node“) hat Level Null. Knoten von Level i können wenigstens mit Knoten der
Stufe i − 1 kommunizieren.
Nach dem Aufbau der Hierarchie erfolgt in der Synchronization Phase eine Synchronisation der Knoten auf Level i mit den Knoten auf i − 1.
Annahmen 4.2.5
Für das Protokoll werden einige Annahmen getätigt:
Zum einen müssen die Sensorknoten über eine eindeutige Identifikation verfügen. Andererseits wird für die paarweise Synchronisation eine bidirektionale Kommunikation
benötigt. Zudem soll mit Hilfe dieser bidirektionalen Verbindungen ein Spannbaum im
Netz aufgebaut werden können. Der Aufbau des Spannbaums wird nicht als Overhead betrachtet, da viele Applikationen diesen Spannbaum zum Beispiel für die Datenaggregation
benötigen (siehe zum Beispiel TinyDB [Ma,Fr 02]).
Level Discovery Phase
Der Root-Node versendet mittels Broadcast ein Level Discovery-Paket, in welchem die
¯
Identität des Senders und sein Level enthalten sind. Empfängt ein Knoten eine solche
Nachricht, inkrementiert er das Level und sichert dieses in seinem Speicher. Anschließend
versendet er seinerseits ein Level Discovery. Wird eine zweite Level Discovery-Nachricht
¯
¯
erhalten, ignoriert der Knoten diese. Damit endet diese Phase, wenn alle erreichbaren
Knoten ihr Level ermittelt haben.
Synchronization Phase
In dieser Phase erfolgt eine paarweise Synchronisation. Dazu wird zunächst beschrieben,
wie dies mit dem Austausch zweier Nachrichten realisiert werden kann (siehe Abbildung
4.4). Eine paarweise Synchronisation finde zwischen Knoten A und B statt. T1 und T4
sind Uhrzeiten gemessen in der lokalen Zeit von A, T2 und T3 wurden in der Zeit von B
festgehalten.
4 Synchronisation
70
Abbildung 4.4: Paarweise Synchronisation, Quelle: [Ga,Ku 03, S.4]
A sendet zum Zeitpunkt T1 einen Synchronisationspuls zu B. Diese Nachricht enthält
das Level von A und den Zeitstempel T1. Zum Zeitpunkt T2 wird diese Nachricht von B
empfangen. Dabei gilt T 2 = T 1 + δ + d mit δ als Uhrendrift der beiden Uhren und d der
Zeit zwischen Generation des Zeitstempels und Verarbeitung in B (Propagierungszeit [Ya
05, S.5]). Anschließend sendet B beim Punkt T3 ein Acknowledgement an A mit seinem
Level sowie den Stempeln T1,T2 und T3. Zum Zeitpunkt T4 wird dieses Paket empfangen.
Da es unwahrscheinlich ist, dass in dieser geringen Zeitspanne sich die Propagierungszeit
und der Uhrendrift ändern, kann A diese beiden Unbekannten berechnen:
δ=
(T 2 − T 1) − (T 4 − T 3)
2
d=
(T 2 − T 1) + (T 4 − T 3)
2
Da Knoten A nun sein Uhrendrift bezüglich B bekannt ist, kann er seine Uhr mit B
synchronisieren. Diese Methode ist eine Sender-initiierte Annäherung, da der Sender sich
mit der Uhrzeit des Empfängers synchronisiert.
Der paarweise Nachrichtenaustausch wird vom Root Node mit Hilfe der BroadcastNachricht time synch angestoßen. Die Knoten eines höheren Levels i starten den
¯
Nachrichtenaustausch mit dem niedrigeren Level i − 1. Dabei überhören Knoten des
Levels i + 1 den Austausch in den unteren Levels.
TSPN realisiert ebenfalls eine Multi-Hop-Synchronisation. Diese wird im Paper
[Ga,Ku 03, S.9] für eine post-facto Synchronization beschrieben. Die Synchronisation
wird nicht zu Beginn sondern erst später bei Bedarf ausgeführt. Das folgende Beispiel
erläutert das Verfahren mit Multi-Hops.
Beispiel 4.2.6 Eine post-facto Synchronisation mit Multi-Hops
Sei ein Paket von der Quelle A zum Sink F mit Hilfe des Pfades A → B → C →
4 Synchronisation
71
D → E → F zu transportieren. Bei jedem Empfänger wird nach Erhalt der Nachricht
mit Hilfe von TSPN die eigene Uhrzeit mit dem Sender synchronisiert. Anschließend
wird der nächste Hop durchgeführt. Zum Beispiel synchronisiert sich B erst mit A bevor
das Paket zu C weitergeleitet wird. So werden bei Bedarf alle Knoten des Pfades mit A’s
Uhrzeit synchronisiert. Im Verfahren wird absichtlich eine Verzögerung von zwei Sekunden
eingebaut, um die Bearbeitungszeit in einem Knoten sowie die Zeit zur Versendung in
einem sehr großen Netzwerk abzubilden.
Bemerkung 4.2.7
Mit der Hardwarespezifikation der Diplomarbeit ist keine Datenaggregation möglich und
daher muss der Aufbau des Spannbaums als Overhead gesehen werden. Dabei kann man
jedes Level mit einer virtuellen Regalreihe gleichsetzen. Die Knoten in einem Level müssen
sich nicht physikalisch in der gleichen Regalreihe befinden, da aufgrund von Spiegelungen
und Reflektionen Knoten unterschiedlicher physikalischer Distanz gleich weit (in Hops)
vom Server entfernt sind (siehe Abschnitt 2.2.2).
Der Aufbau des Spannbaums bedarf wegen der Dynamik einer periodischen Wiederholung. Ein großes Wiederholungsintervall könnte gewählt werden, wenn die Level auch den
physikalischen Regalreihen entsprächen. Denn dann sind auch bei Ausfall von Kommunikationswegen noch ausreichend Knoten eines niedrigeren Levels in Reichweite. Aufgrund
der zuvor beschrieben Spiegelungen, kann aber ein Sensorknoten sich virtuell näher zum
Server befinden als physikalisch. Wenn jedoch ein Kommunikationsweg ausfällt, der aus einer solchen Spiegelung entsteht, hat dieser Knoten keine Synchronisationspartner. Dieser
Fehler muss natürlich schnell behoben werden und daher bedarf es einer häufigen Wiederholung der Level Discovery Phase.
Problematisch ist zudem, dass eine paarweise Synchronisation stattfinden soll: Versuchen
alle Knoten eines Levels eine Synchronisation mit einem zufällig gewählten Nachbarn des
niedrigeren Levels, führt dieses sicherlich zu Interferenzen und mehrfachen Anfragen bei
Knoten. Einzelne Knoten können diese Synchronisation nicht stellvertretend für alle machen: Die Knoten müssten explizit bestimmt werden, aber es gibt nur gleichberechtigte
Knoten bei der Synchronisierung.
4.2.4
Beurteilung der drei Verfahren
Für die Synchronisation in dem Szenario der Diplomarbeit können die Verfahren
Reference Broadcast Synchronization (RBS) und das Timing Sync Protocol for Sensor
Networks (TSPN) eingesetzt werden. Das TSPN erzeugt einen gewissen Overhead, da
vor der Synchronisation ein Spannbaum aufgebaut wird. Da jedoch im Protokoll mit der
Hopdistanz (siehe 2.2.2) gearbeitet wird, ist ein Level der Hopdistanz gleichzusetzen.
4 Synchronisation
72
Daher entsteht nur ein Overhead, wenn der Spannbaum explizit aufgebaut wird.
Unabhängig von diesem gegebenenfalls erzeugten Overhead besteht in TSPN das Problem
bei der Realisierung der paarweisen Synchronisation (siehe Bemerkung 4.2.7). Aus diesem
Grund tendiere ich zum Einsatz des RBS. Wird RBS für die Synchronisation genutzt,
sollte die Vereinfachung hinzugenommen werden, dass ein zufällig vom Synchronisationssender ausgewählter Knoten seine Empfangszeit propagiert (siehe Bemerkung 4.2.4).
4.3
Globales kontra lokales synchrones Aufwachen
Die zuvor beschriebenen Verfahren zur internen Synchronisation dienen dazu, dass jeder
Knoten nahezu eine identische Uhrzeit besitzt. Da alle Knoten zudem über die gleiche
Round-Time verfügen, kann der Aufwachpunkt der Knoten synchronisiert werden.
Im folgenden Abschnitt 4.3.1 wachen die Knoten in der gleichen Distanz zum Server
zeitgleich auf (lokal synchroner Aufwachpunkt). Anschließend wird der global synchronisierte Aufwachpunkt beschrieben, das heißt alle Knoten im Netz wachen gleichzeitig auf.
4.3.1
Regalweise Synchronisation
Ein lokaler synchroner Aufwachpunkt ist gegeben, wenn alle Sensorknoten innerhalb der
gleichen Hopdistanz zum Server parallel erwachen.2 Statt vom lokalen synchronen Aufwachpunkt wird auch von der regalweisen Synchronisation gesprochen.
Abbildung 4.5: Sende-und Empfangsphasen in der regalweisen Synchronisation
2
Die Hopdistanz wurde in Abschnitt 2.2.2 genau definiert.
4 Synchronisation
73
Damit eine Kommunikation bei der regalweisen Synchronisation stattfinden kann, müssen
sich die Wachphasen der virtuellen Regale in Sendereichweite überschneiden. Daher
gilt: Alle Stationen in einem Regal (mit gleicher Hopdistanz) besitzen den gleichen
Aufwachpunkt. Die Stationen im hinteren und im vorderen Regal wachen zeitversetzt
auf. Jedoch sind zwei benachbarte Regale immer einige Runden lang gleichzeitig wach.
Die Abbildung 4.5 zeigt die Wach- und die Sendephasen bei einer uplink-Kommunikation.
Knoten mit Distanz sechs haben dabei die größte Entfernung aller Knoten zum Server.
Daher benötigen sie für die uplink-Kommunikation keine Empfangsphase, da keine
Nachrichten von weiter entfernten Knoten gesendet werden können.
Abbildung 4.6: Verhältnis uplink- und downlink- Treppen
Da nun die Phasen zum Senden und Empfangen wohl-definiert sind, kann Energie gespart
werden. Liegt eine Nachricht im Buffer, da sie noch nicht erfolgreich versendet wurde,
muss dieser Sensorknoten erst zur Sendephase erwachen. Analog kann Energie gespart
werden, wenn ein Knoten seine Nachricht oder das Beacon erfolgreich verschickt hat.
Dieser Knoten kann anschließend direkt schlafen gehen, falls er keine Nachricht mehr zu
versenden hat und keine Nachricht mehr empfangen kann.
Die Aufwachphasen verlaufen in Treppenstufen. Da die uplink-Kommunikation wahrscheinlich häufiger vertreten ist als die downlink-Kommunikation, kann man uplinkTreppenstufen häufiger durchlaufen (vielleicht im Verhältnis 3:1, siehe Abbildung 4.6).
Empfängt ein Knoten eine Nachricht und bearbeitet sie zum Weiterleiten vor, bedarf
dieser Vorgang einer gewissen Bearbeitungszeit. Die Empfangsphase sollte mindestens
dieser Dauer plus einer Konstante entsprechen. Ansonsten sind gegebenenfalls in der
Sendephase nur die Nachrichten sendebereit, welche bereits im Buffer waren.
Die Dauer des Empfangsvorgangs inklusive des Erhalts des zugehörigen Acknowledgements kann aufgrund der Synchronisation nach oben abgeschätzt werden. Somit ist es
möglich, den Sendevorgang in Runden aufzuteilen, welche jeweils dieser Abschätzung
entsprechen.
4 Synchronisation
74
Da alle Knoten synchronisiert sind, entspricht die Rundendauer der Transferzeit
der Nachricht bis hin zum Empfangen des Acknowledgements. Ist die obere Grenze
überschritten, beurteilt der Sender den Sendeversuch als erfolglos.
Beschrieben wurde hier die einfache Variante der regalweisen Synchronisation. Senden
Knoten mit Distanz i eine uplink-Nachricht, sind nur Knoten der Entfernung i + 1 wach.
Damit ist die Anzahl der potentiellen Sender gleich der Anzahl der Knoten mit gleicher
Hopdistanz in Sendereichweite. Die Anzahl der Empfänger spricht mit den Knoten aus
dem virtuellen Regal i + 1 im Senderadius überein, die keine Nachricht im Buffer besitzen.
Für die Steigerung des Nachrichtendurchsatzes sollten sich die Treppenstufen deutlicher überschneiden. In Abbildung 4.7 bestehen nicht nur eindeutig definierte Sende- und
Empfangsphasen. Es gibt zudem eine Mischphase: Liegt eine Nachricht versandbereit,
wird gesendet. Ansonsten wird weiter versucht eine Nachricht zu empfangen. Die
Empfangsdauer sollte die obere Grenze für die Dauer des Empfangsvorganges jedoch
auch jetzt nicht unterschreiten.
Abbildung 4.7: Regalweise Synchronisation mit deutlicherer Überschneidung
4.3.2
Global synchronisierter Aufwachpunkt
Wird das 1 QK-Protokoll so verändert, dass alle Knoten direkt zu Beginn der RoundTime erwachen, liegt ein globaler synchroner Aufwachpunkt vor. Schließlich erwachen
alle Sensorknoten des Netzes zum gleichen Zeitpunkt (abgesehen von minimalen Verschiebungen, die auf die Präzision des Synchronisationsverfahrens zurückzuführen sind).
Der globale synchronisierte Aufwachpunkt ist sicherlich leicht zu realisieren. Sind die
4 Synchronisation
75
Uhren synchronisiert worden, muss das Protokoll lediglich so angepasst werden, dass die
Knoten stets zu Beginn der Round-Time aufwachen.
Diese Synchronisation hat jedoch zwei gravierende Nachteile:
Zum einen wird die Sendereichweite mindestens so eingestellt, dass Knoten im vorderen
und im hinteren Regal erreicht werden. Dieses ist für die Kommunikation zwingend
notwendig. Die Anzahl der potentiellen Sender im eigenen Sendebereich werden dadurch
drastisch erhöht. Alle Knoten, die eine Nachricht im Buffer haben, beginnen direkt nach
dem Aufwachen zu senden. Da alle Netzknoten den gleichen Aufwachpunkt besitzen, sind
alle Knoten im eigenen Sendebereich potentielle Sender und Konkurrenten. Betrachtet
man die Funktion für das Empfänger-Sender-Verhältnis mit waagerechter Regalanordnung aus Abschnitt 2.2.2 gilt für den globalen Ansatz:
Pb xr c √ 2
r − x2
Empfängerstrecke
i=0 2 ·
=
r
Pb x c √ 2
Senderstrecke
4 · r − x2
2 · r + i=1
2A
2·r+4·A
Die Sendereichweite kann nicht genau justiert werden. Daher wäre im günstigsten Fall
=
die Sendereichweite so begrenzt, dass nur benachbarte Regalreihen kontaktiert werden.
Laut den Beispielszenarien in 2.2.2 entspricht dann n = 2 · r und A = 3/4 · n. Dies ergibt
zusammen :
2 · 43 · n
Empfängerstrecke
=
Senderstrecke
n + 4 · 34 · n
=
3
n
2
4n
und damit ein Verhältnis von 3:8. Die Wahrscheinlichkeit von auftretenden Interferenzen
ist gegenüber dem lokalen Ansatz deutlich gestiegen.
Zum anderen liegt ein Problem in der Realisierung folgender wünschenswerten Anforderung:
Die Wachphase sollte für eine geringe Latenz so lang sein, dass innerhalb einer RoundTime eine uplink-Nachricht vom entferntesten Knoten zum Server gelangen kann. Für
eine downlink-Nachricht soll natürlich die umgekehrte Weiterleitung innerhalb einer
Round-Time möglich sein. Diese Anforderungen implizieren, dass alle Knoten mindestens
die minimale Dauer einer Weiterleitung durch das gesamte Netz wach sind. Eine derartig
lange Wachphase ruft einen nicht zu vernachlässigen Energieverbrauch hervor.
4 Synchronisation
76
4.3.3
Vergleich der Ansätze
Es
interessant,
ist
reicht.
Für
welcher
Beispielszenarien
“GlobalerAufwachpunkt.mnb“
Ansatz
habe
einen
ich
zwei
höheren
MuPad
Nachrichtendurchsatz
Programme
er-
entwickelt3 .
realisiert den globalen synchronen Aufwachpunkt,
“RegalweiseSynchronisation.mnb“ den lokalen.
In den Implementierungen wird bereits der Aspekt der Fairness (siehe Kapitel 6)
berücksichtigt, so dass eigene Nachricht nicht immer bevorzugt werden. Wird eine
Nachricht empfangen und liegen eigene Daten vor, werden die fremden Nachrichten mit
einer Wahrscheinlichkeit der Variablen “verhaeltnis“ weitergeleitet. Anhand des Parameters “ps“ wird die Wahrscheinlichkeit festgelegt, dass eigene Sensordaten vorhanden
sind. Die Arrays “erhieltBeacon“, “sendWeiter“ sowie “bearbeitetNachricht“ dienen der
Berechnung der aktuell vorhandenen Sender und Empfänger.
Der Server wird mit einer konfigurierbaren Anzahl von Empfängern4 simuliert. Des
Weiteren stehen mehrere Kanäle zur Verfügung (Variable “C“), welche alle mit der
gleichen Wahrscheinlichkeit gewählt werden. Hardwaremäßig können nur dreizehn Kanäle
realisiert werden. Es kann aber mit Hilfe von mehreren internen Runden eine Vielzahl von
Kanälen simuliert werden (siehe Kapitel 5). Daher setze ich hier keine Einschränkungen
für die Belegung der Variablen.
Implementiert wurde die uplink-Kommunikation, da schließlich nur hier die Problematik
mit den eigenen Sensordaten auftritt. Die Sendephasen sind in Runden aufgeteilt, welche
der Dauer einer Zeiteinheit entsprechen. Es wurde exemplarisch festgelegt, dass die
Bearbeitung eines empfangenen Beacons einer Zeiteinheit bedarf. Die Erstellung einer zu
versendenen Nachricht wird mit drei Zeiteinheiten berechnet. Diese drei Zeiteinheiten
werden also benötigt, wenn eine fremde Nachricht empfangen wurde oder eigene Sensordaten vorliegen. Gemäß dieser Zeiteinheit und vor allem der Kanalanzahl sowie der
oberen Abschätzung des Empfangsvorganges werden die Sende- und Empfangsphasen in
Runden eingeteilt.
Um den Erfolg des Verfahrens messen zu können, werden die Nachrichten gezählt,
welche der Server empfängt. Beacons sind in dieser Zählung nicht inbegriffen. Als weitere
Ausgabe erfolgt pro virtuelle Regalreihe die Anzahl der verbliebenen Nachrichten.
Im Anschluss werden die Ergebnisse beider Verfahren mit folgenden Voraussetzungen
präsentiert:
3
4
Diese befinden sich auf der beigefügten CD im Verzeichnis Mupad Quellen
¯
Im Array empfaenger bei Index 6
4 Synchronisation
77
• Variable ps;
Entspricht der Wahrscheinlichkeit, dass ein Knoten eigene Sensordaten vorliegen
hat und eine eigene uplink-Nachricht versenden möchte.
• Variable verhaeltnis;
Speichert die Wahrscheinlichkeit zur Weiterleitung einer fremden empfangenen
Nachricht, wenn selbst neue Sensordaten vorliegen.
• Es gibt fünf Regalreihen.
• In der Sendereichweite eines jeden Sensorknotens befinden sich zehn Sensorknoten
pro Regalreihe. Das heißt als Empfänger stehen zehn Knoten zur Verfügung. Diese Konfiguration von Sendern und Empfängern ist in den Arrays “sender“ und
“empfaenger“ möglich.
• Zur Vereinfachung des Modells kann jeder Knoten jeden anderen Knoten in dieser Sendereichweite kontaktieren. Dies ist eine akzeptable Vereinfachung: Für jeden
Knoten befinden sich in seiner Reichweite neun weitere Knoten des gleichen Regals. Für jeden der neun Knoten sind jedoch auch wiederum neun Sensorknoten des
eigenen Regals in Reichweite. Analog verhält es sich bei den Empfängern.
Die regalweise Synchronisation ist so realisiert, dass nur benachbarte Regale gleichzeitig
wach sind. Dies entspricht einer Sendereichweite, die keinen weiteren Regale erreicht. Der
gleiche Ansatz wurde für einen Vergleich beim globalen Aufwachpunkt implementiert:
Als störende Sender werden nur die Knoten der beiden direkt benachbarten Regalreihen
angesehen.
Anmerkungen zur Realisierung der regalweisen Synchronisation
Die Regalreihen sind so synchronisiert, dass sie gleichzeitig stets vier Runden wach
sind: Eine Runde zum Empfangen einer Nachricht und drei Runden für die interne
Bearbeitung. Empfängt somit ein Knoten in Runde Eins, versendet er diese auch in
Runde Eins. Erhält ein Knoten eine Nachricht in Runde drei, versendet er die Nachricht
auch in der dritten Runde der folgenden Round-Time. Eine ausführliche Dokumentation
sowie der Quellcode sind im Anhang A.1 zu finden.
Die Stationen sind damit maximal vier Runden beim Empfangsvorgang und vier Runden
für das Senden wach. Wenn ein Sensorknoten seine Nachricht abgeliefert oder ein Beacon
versendet hat, kann er bis zum nächsten Aufwachpunkt schlafen. Somit sind die Knoten
im Minimum zehn Runden wach (nur jeweils in den beiden Empfangsphasen sowie zum
Beacon-/einmaligem Nachrichtenversand).
4 Synchronisation
78
Anmerkungen zur Realisierung des globalen Aufwachpunktes
Damit eine Nachricht der äußersten Regalreihe (Eins) die Möglichkeit hat innerhalb
einer Round-Time zum Server zu gelangen, muss die Wachphase mindestens zwanzig
Runden andauern. Schließlich wird eine minimale Bearbeitungszeit von vier Runden
pro Regalreihe benötigt. Für die gleiche Energie können die Knoten mit der regalweisen
Synchronisation mindestens zwei Round-Times durchlaufen. Bei einem zweimaligen
Durchlauf, besteht jedoch für die Knoten zweimal die Möglichkeit eine eigene Nachricht
zu versenden. Daher wird bei dem globalen Ansatz innerhalb einer Round-Time zweimal
die Möglichkeit für die eigene Nachrichtengenerierung eingeräumt. Aufgrund dieser Ungleichheit des Energieverbrauchs wird bei den folgenden Vergleichen stets eine doppelte
Anzahl von Durchläufen für die regalweise Synchronisation durchgeführt.
Als weitere Besonderheit ist zu betrachten, dass der eigene Nachrichtenversand erst in der
zweiten Runde abläuft. Schließlich muss jeder Knoten vor dem Versenden einer eigenen
Nachricht aufgrund der eventuellen Weiterleitung von fremden Nachrichten erst lauschen,
ob er eine fremde empfängt. Bei der allerersten Round-Time führt dieses natürlich dazu,
dass alle Knoten nur lauschen und keiner sendet. In den folgenden Durchläufen senden
aber in der ersten Runde die Knoten, bei denen eine Nachricht im Buffer sendebereit
vorliegt.
Ergebnisse
In der folgenden Tabelle sind die Ergebnisse einiger Beispielauswertungen aufgeführt.
Verschiedene Werte und Kombinationen der Parameter ps, verhaeltnis, C (= Kanäle) und
der absolvierten Anzahl von Round-Times(R-Ts) wurden getestet. Bei den Ergebnissen
der wird die Anzahl der in den verschiedenen Regalen verbliebenen Sensorknoten mit
Nachrichten im Buffer ausgegeben. Zudem folgt eine Angabe der Gesamtanzahl der
Nachrichten, welche der Server empfangen hat. Die Ergebnisse beziehen sich darauf, dass
der Server wie fünf Empfänger realisiert ist. Bei den Angaben in den Klammern sind die
resultierenden Daten angegeben, wenn der Server wie zehn Empfänger arbeitet.
Regal eins ist das Regal von, welchem der Treppenfluss der uplink-Kommunikation
4 Synchronisation
79
beginnt und ist damit am weitesten vom Server entfernt.
ps verhaelt- Kanäle R-Ts
Regalweise
nis
Global
regalw./
global
0,1 0,75
0,1 0,75
0,1 0,75
0,1 0,75
10
10
30
30
2/1
10/5
2/1
10/5
Verblieben:
Verblieben:
Regal 1= 1; X(1)
Regal 1:= 0; X(0)
Regal 2= 4; X(4)
Regal 2:= 7; X(7)
Regal 3= 4; X(4)
Regal 3:= 10;X(10)
Regal 4= 3; X(2)
Regal 4:= 10;X(10)
Regal 5= 4; X(2)
Regal 5:= 6; X(2)
Empfang:= 4 X(7)
Empfang:= 10 X(15)
Verblieben:
Verblieben:
Regal 1:= 1; X(1)
Regal 1:= 0; X(0)
Regal 2:= 5; X(5)
Regal 2:= 7; X(7)
Regal 3:= 7; X(8)
Regal 3:= 10; (10)
Regal 4:= 8; X(6)
Regal 4:= 10; (10)
Regal 5:= 9; X(8)
Regal 5:= 6; X(2)
Empfang:= 15 X(19)
Empfang:= 59 X(66)
Verblieben:
Verblieben:
Regal 1:= 1; X(1)
Regal 1:= 0; X(0)
Regal 2:= 4; X(4)
Regal 2:= 6; X(6)
Regal 3:= 4; X(4)
Regal 3:= 8; X(8)
Regal 4:= 3; X(3)
Regal 4:= 8; X(8)
Regal 5:= 3; X(3)
Regal 5:= 4; X(2)
Empfang:= 3 X(4)
Empfang:= 8 X(12)
Verblieben:
Verblieben:
Regal 1:= 2; X(2)
Regal 1:= 0; X(0)
Regal 2:= 6; X(6)
Regal 2:= 6; X(6)
Regal 3:= 7; X(7)
Regal 3:= 8; X(8)
Regal 4:= 7; X(7)
Regal 4:= 8; X(8)
Regal 5:= 8; X(8)
Regal 5:= 4; X(2)
Empfang:= 16 X(18)
Empfang:= 46 X(52)
4 Synchronisation
ps
80
verhaelt- Kanäle
R-Ts
nis
regalw./
Regalweise
Global
Verblieben:
Verblieben:
Regal 1:= 5; X(5)
Regal 1:= 1; X(1)
Regal 2:= 6; X(6)
Regal 2:= 5; X(5)
Regal 3:= 6; X(6)
Regal 3:= 8; X(8)
Regal 4:= 6; X(6)
Regal 4:= 8; X(8)
Regal 5:= 4; X(3)
Regal 5:= 6; X(2)
Empfang:= 5 X(10)
Empfang:= 12 X(16)
Verblieben:
Verblieben:
Regal 1:= 9; X(9)
Regal 1:= 5; X(5)
Regal 2:= 10;X(10)
Regal 2:= 9; X(9)
Regal 3:= 9; X(9)
Regal 3:= 9; X(9)
Regal 4:= 9; X(9)
Regal 4:= 9; X(9)
Regal 5:= 8; X(8)
Regal 5:= 7; X(2)
Angekommen:= 17
Angekommen:= 69
X(21)
X(75)
Verblieben:
Verblieben:
Regal 1:= 5; X(5)
Regal 1:= 1; X(1)
Regal 2:= 6; X(6)
Regal 2:= 5; X(5)
Regal 3:= 6; X(6)
Regal 3:= 8; X(8)
Regal 4:= 6; X(6)
Regal 4:= 8; X(8)
Regal 5:= 4; X(3)
Regal 5:= 3; X(2)
Empfang:= 5 X(9)
Empfang:= 9 X(16)
Verblieben:
Verblieben:
Regal 1:= 9; X(9)
Regal 1:= 5; X(5)
Regal 2:= 9; X(9)
Regal 2:= 9; X(9)
Regal 3:= 9; X(9)
Regal 3:= 9; X(9)
Regal 4:= 9; X(9)
Regal 4:= 9; X(9)
Regal 5:= 8; X(8)
Regal 5:= 5; X(2)
Angekommen:= 16
Angekommen:= 56
X(21)
X(72)
global
0,4 0,75
0,4 0,75
0,4 0,30
0,4 0,30
10
10
10
10
2/1
10/5
2/1
10/5
Beim Vergleichen der Daten wird deutlich, dass bei der globalen Synchronisation
deutlich mehr Duplikate entstehen. Dies ist in der Tatsache erkennbar, dass mehr
Nachrichten beim Server empfangen werden, aber trotzdem noch viele Nachrichten bei
4 Synchronisation
81
den Sensorknoten verblieben sind. Daher ist der insgesamte Nachrichtenaufwand höher
und die Knoten verbrauchen mehr Energie zum Senden und Empfangen.
Ist die Wahrscheinlichkeit gering, dass eigene Sensordaten vorhanden sind, ist auf jeden
Fall die regalweise Synchronisation besser. Hier sieht es zunächst so aus, dass bei einer
höheren Wahrscheinlichkeit die globale Synchronisation bessere Ergebnisse erzielt. Dieses
ist allerdings zum einen auf die längere Wachphase (zwanzig statt sechzehn Runden) und
zum anderen auf die folgende Vereinfachung zurückzuführen: Die Sensorknoten können
nur in bestimmten Runden ihre eigene Nachricht senden. Wird in den entscheidenen
Runden (beim lokalen in der ersten, beim globalen in der zweiten und zehnten) eine
andere Nachricht zur Weiterleitung ausgewählt, ist die eigene Nachricht verworfen.
Bei dem global synchronisierten Aufwachpunkt sind zudem die Unterschiede in
den verbliebenen Nachrichten aufgrund der Simulation des Servers mit fünf oder zehn
Empfängern deutlicher. In den Daten des lokalen Ansatzes spielt dieser Faktor eigentlich
nur bei der Anzahl der empfangenen Nachrichten eine Rolle. Dass in diesem Punkt
Unterschiede zu verzeichnen sind, ist klar, da mehr simulierte Empfänger auch mehr
Duplikate erzeugen.
Außer Acht gelassen werden darf auch nicht, dass bei der regalweisen Synchronisation die Sensorknoten (außer im ersten Regal) minimal acht und maximal sechzehn
Runden pro Round-Time wach sind. Beim globalen Ansatz hingegen sind alle Knoten
stets zwanzig Runden wach.
Lemma 4.3.1
Die regalweise Synchronisation erzeugt weniger Nachrichtenaufkommen und ist zudem
unanfälliger gegenüber Präsenz des Servers. Da in diesem Ansatz auch mehr Energie
eingespart wird, plädiere ich die Uhrensynchronisation sowie einen lokal synchronen Aufwachpunkt in das 1 QK-Protokoll zu integrieren.
Kapitel 5
Frequenzwahl
Als erste Optimierung des 1 QK-Protokolls stelle ich die Verbesserung der Frequenzwahl
vor. Zunächst folgt die Problemdarstellung sowie die Lösungsidee.
Problemdarstellung 5.0.2 Frequenzwahl
Im 1 QK-Protokoll werden bei der uplink-Kommunikation die Kanäle bei der höchsten
Kanalnummer beginnend abwärts durchlaufen. Dabei wird auf jedem Kanal eine gewisse
Zeit gesendet.
Dies führt zu zwei Problemen:
1. Versenden mehr als zwei Sensorknoten mit nicht disjunkten Sendebereichen eine
uplink-Nachricht, treten auf jeder Frequenz Interferenzen auf. Schließlich sind die
Knoten synchronisiert und starten bei der gleichen Kanalnummer. Damit ist der
Nachrichtendurchsatz für diese Knoten immer gleich Null. Nur Knoten, bei denen
sich kein anderer Sendewilliger im Sendebereich befindet, haben die Chance ihre
Nachricht zu verschicken.
Beim global synchronisierten Aufwachpunkt gilt dieses für beliebige Sensorknoten. In
der regalweisen Synchronisation senden nur die Knoten mit bestimmten Hopdistanzen zeitgleich. Daher ist diese Problematik “nur“ für Knoten ähnlicher Distanzen
von Bedeutung.
2. Im 1 QK-Protokoll kann es bei einem Kanalwechsel dazu kommen, dass Acknowledgements überhört werden. Da die Knoten unsynchronisiert sind, kann folgender
Fall eintreffen: Ein Empfänger hat eine Nachricht erhalten, aber das Acknowledgement wurde aufgrund eines Kanalwechsels oder der Beendigung des Sendevorganges
nicht mehr vom Sender gehört. Damit weiß der Sender nicht, dass sein Sendevorgang erfolgreich war und verbraucht unnötige Energie. Ebenso werden vermeidbare
Duplikate durch weitere Sendeversuche erzeugt.
5 Frequenzwahl
83
Das zweite Problem ist bereits gelöst: Mit der Synchronisierung und der oberen Schranke
für einen Sendevorgang konnten die Sende- und Empfangsphasen in Runden eingeteilt
werden. Wurde in einer Runde kein Acknowledgement erhalten, war der Sendevorgang
definitiv nicht erfolgreich. Schließlich entspricht die Rundenzeit der oberen Schranke.
Der erste angesprochene Problempunkt ist allein mit Hilfe der Synchronisierung
nicht gelöst und weitaus gravierender. Mit dem 443MHz-Band steht die Möglichkeit
offen, dass dreizehn Kanäle genutzt werden. Ohne Sicherheitsbereiche ist der Einsatz
von 26 Kanälen möglich, jedoch erhöht dieses die Gefahr von Interferenzen auch durch
Sendungen auf unterschiedlichen Kanälen. Mit dreizehn Kanälen kann jedoch eine
Vielzahl von Kanälen simuliert werden:
Sollen zum Beispiel 130 Kanäle eingesetzt werden, wird ein Block von zehn Runden als
eine Sende- oder Empfangsrunde genutzt. Fällt die Wahl auf einen Kanal zwischen 0
und 12, wird in der ersten Runde des Blockes agiert. Soll ein Kanal zwischen 13 und 25
genutzt werden, geschieht dieses in der zweiten Runde des Blockes usw..
Die expliziten Frequenzbereiche zu jedem Kanal werden im FLASH-Speicher abgelegt.
Damit ergibt sich kein Speicherproblem aufgrund der vorhandenen 256 Byte. Im
Folgenden gehe ich davon aus, dass beliebig viele Kanäle simuliert werden können. Die
interne Rundenzeit ist aufgrund der geringen Nachrichtengröße sehr kurz. Der meiste
Energiebverbrauch ist zudem für das Aufwachen sowie das Senden und Empfangen
anzusetzen. Wartet der Knoten nur auf die korrekte interne Runde zum Senden oder
Empfangen, wird der Energieverbrauch nicht sehr hoch sein. Daher ist der höhere
Energieverbrauch resultierend aus der längeren Wachphase vernachlässigbar. Mit einer
Vielzahl von Kanälen steigt jedoch die Wahrscheinlichkeit für einen erfolgreichen Sendeversuch deutlich. Somit werden weniger Sendeversuche benötigt. Dieses verringert nicht
nur die Latenz, sondern wirkt sich auch positiv auf den Energieverbrauch aus.
Für eine synchrone Abarbeitung des Sendevorganges ist es sehr bedeutend, dass die
Kanäle nicht schrittweise durchlaufen werden. Gesucht wurde eine Wahrscheinlichkeitsverteilung für die Kanalwahl, welche einen guten Nachrichtendurchsatz gewährleistet.
Dabei wird die gleiche Wahrscheinlichkeitsverteilung sowohl in der Sende- als auch in der
Empfangsphase genutzt.
Das Wichtige ist zum einen, dass nur ein Sender den Kanal gewählt hat. Versuchen mehr
als ein Sender in dem gleichen Frequenzbereich zu senden, treten Interferenzen auf. Auch
wenn ein Empfänger den gleichen Kanal gewählt hat, kann kein erfolgreicher Sendevorgang stattfinden. Damit soll in erster Linie die Wahrscheinlichkeit möglichst gering sein,
dass zwei Sender den gleichen Kanal wählen. Hingegen muss die Wahrscheinlichkeit, dass
ein Sender und ein Empfänger den gleichen Kanal wählen noch ausreichend groß sein.
Sender und Empfänger nutzen die gleiche Wahrscheinlichkeitsverteilung bei der Ka-
5 Frequenzwahl
84
nalwahl um den Durchsatz hoch zu halten. Schließlich kann eine Nachricht auch nicht
erfolgreich versendet werden, wenn kein Empfänger auf dem Kanal lauscht und ein
analoges Verhalten von Sendern und Empfängern ist empfehlenswert.
Bei der Suche nach einer geeigneten Wahrscheinlichkeitsverteilung kann kein dichtes Netzwerk vorausgesetzt werden. Das Finden eines Kommunikationspartners soll
auch in Extremsituationen eine akzeptable Wahrscheinlichkeit besitzen. Es ist schließlich
denkbar, dass viele Störungen auftreten oder nur noch wenige Knoten als Kommunikationspartner zur Verfügung stehen.
Im Folgenden wird zunächst die Gleichverteilung als geeignete Wahrscheinlichkeitsverteilung untersucht. Anschließend folgt eine Betrachtung der dazu im Gegensatz
stehenden geometrischen Verteilung. In den Abschnitten werden jeweils die Konstellationen zusammengefasst, bei welchen die Verteilungen gut oder schlecht einzusetzen sind.
Im Abschnitt 5.3 stelle ich eine Verbesserung der “reinen“ geometrischen Verteilung vor.
Abschließend erfolgt eine Beurteilung der Wahrscheinlichkeitsverteilungen im Einsatz für
die Kanalwahl.
5.1
Gleichverteilung
Liegt ein dichtes Kommunikationsnetzwerk vor, ist intuitiv die Gleichverteilung die beste
Wahrscheinlichkeitsverteilung für eine Kanalwahl. Schließlich wird jeder Kanal mit der
gleichen Wahrscheinlichkeit gewählt und die Sender verteilen sich ausgewogen über die
Kanäle (siehe 5.1).
Definition 5.1.1 Gleichverteilung
Es stehen n Sender, m Empfänger sowie C Kanäle zur Verfügung. Jeder Kanal wird mit
der Wahrscheinlichkeit
1
C
gewählt. Damit sind im Erwartungswert
n
C
Sender auf jedem
Kanal vertreten.
Die erwartete Anzahl von erfolgreich versendeten Nachrichten entspricht der Summe der
im Erwartungswert versendeten Nachrichten pro Kanal. Pro Kanal ist die Anzahl Null
oder Eins. Die Wahrscheinlichkeit für eine versendete Nachricht auf Kanal i, entspricht
der Wahrscheinlichkeit, dass genau einer der n Sender und mindestens einer der m
Empfänger den Kanal gewählt haben.
5 Frequenzwahl
85
Abbildung 5.1: Gleichverteilung für acht Kanäle
Damit ergibt sich:
E(erfolgreich versendeten Nachrichten auf Kanal i)
= 0 · P (keine Nachricht auf Kanal i erfolgreich) + 1 · P (eine Nachricht auf i erfolgreich)
P(eine Nachricht auf Kanal i erfolgreich)
= P (genau ein Sender auf i) · P (mind. ein Empfänger auf i)
(n−1) m 1
1
1
=n· · 1−
· 1− 1−
C
C
C
E(erfolgreiche Nachrichten insgesamt)
=
C
X
i=1
(n−1) m 1
1
1
n· · 1−
· 1− 1−
C
C
C
(n−1) m 1
1
1
· 1− 1−
=C ·n· · 1−
C
C
C
Am besten ist es, wenn genauso viele Kanäle wie Sender zur Verfügung stehen. Dann
befindet sich im Erwartungswert auf jedem Kanal ein Sender. Es wäre schlechter eine
höhere Anzahl von Kanälen zu wählen. Schließlich steigt dann die Wahrscheinlichkeit,
dass ein Empfänger einen Kanal wählt, auf dem sich kein Sender befindet. Daher kann
bei der Initialisierung der Knoten die Menge der zu nutzenden Kanäle gleich der Anzahl
der Knoten der gleichen physikalischen Regalreihe in Sendereichweite eingestellt werden.
5 Frequenzwahl
86
Schließlich ist gewiss, dass in der ersten Runde alle Sensorknoten in Reichweite senden
(entweder ein Beacon oder eine Nachricht).
5.1.1
Abschätzungen für den Erfolg der Gleichverteilung
Die Gleichverteilung ist bei einer hohen Anzahl von Sendern und Empfängern unschlagbar. Sie liefert gute Ergebnisse, wenn die Anzahl der Sender in etwa der der zur Verfügung
stehenden Kanäle entspricht. Dabei spielt es keine Rolle, wie viele Empfänger vorhanden
sind.
Es ist wichtig, den Erwartungswert der versendeten Nachrichten sowie sein Minimum
und Maximum für verschiedene Kombinationen von Sendern, Empfängern und Kanälen
einschätzen zu können. Daher folgen Abschätzungen nach oben und unten für den Erwartungswert der erfolgreichen Nachrichten mit n Sendern und m Empfängern und C
Kanälen.
Zuvor werden die wichtigsten Ungleichungen zusammengefasst, welche bei den
Abschätzungen genutzt werden. Für die im Lemma aufgeführten Gleichungen sowie deren
Beweise verweise ich auf [Sch 05].
Lemma 5.1.2
1. Für alle n ≥ 1:
1
1−
n
n
1
≤ ≤
e
1
1−
n
n−1
2. Für alle p ∈]0, 1]:
1
(1 − p) p ≤
1−p
1
1
≤ (1 − p) p −1 = (1 − p) p
e
3. Für alle x ∈ [0, 1]:
−x
1−e
1
≤1− 1−
e
x
4. Für alle p ∈]0, 1] und m ≥ 1:
1 − pm ≤ (1 − p)m ≤ 1
Für alle m ∈ N, p ∈ [0, 1] gilt:
1
min{1, pm} ≤ 1 − (1 − p)m ≤ min{1, pm}
1−
e
5 Frequenzwahl
87
Korollar 5.1.3
Aus der letzten Abschätzung 1 −
1
e
min{1, pm} ≤ 1−(1−p)m ≤ min{1, pm} des Lemmas
5.1.2 folgt [Sch 05]:
Falls pm ≥ 1 gilt:
Falls pm ≤ 1 gilt e−pm
1
1 − (1 − p)m ≥ 1 − e−pm ≥ 1 −
e
1
≤ 1 − 1 − e pm und es folgt die Ungleichung:
1
m
−pm
1 − (1 − p) ≥ 1 − e
≥ 1−
pm
e
1. Abschätzung nach oben
P (Erfolg auf Kanal i) = P (genau 1 Sender auf i) · P (mindestens 1 Empfänger auf i)
(n−1)
1
1
· (1 − P (kein Empfänger auf i))
=n· · 1−
C
C
C· n−1 m 1 ( C )
1
1
· 1− 1−
=n· · 1−
C
C
C
!
n−1
C·
C· m
C
1
1 ( C )
1
=n· · 1−
· 1− 1−
C
C
C
!
n−1
m
1
1 C
1 C
≤n· ·
· 1−
C
e
e
Insgesamt:
!
n−1
m
1 C
1 C
E (erfolgreiche Nachrichten) ≤
· 1−
e
e
i=1
!
n−1
m
C
1 X 1 C
1 C
≤n· ·
·
· 1−
C i=1
e
e
!
n−1
m
1
1 C
1 C
≤n· ·C ·
· 1−
C
e
e
!
n−1
m
1 C
1 C
≤n·
· 1−
e
e
C
X
1
n· ·
C
5 Frequenzwahl
88
1. Fall: n > C ⇒
n−1
C
≥1
Es gilt:
n−1
n−1
1 C
= e− C
e
a) m ≥ C ⇒
m
C
≥1
Folgende Ungleichung ist erfüllt:
m
1 C
1
1
= m ≤ ⇒
e
e
eC
!
m
1 C
1−
≤1
e
⇒ E (erfolgreiche Nachrichten) ≤ n · e−
b) m < C ⇒
m
C
n−1
C
· 1 ≤ n · e−
<1
Mit Lemma 5.1.2 kann gezeigt werden:
!
m
m
1 C
m
1 C
≤1⇒ 1−
−→ 0, für
→0
e
e
C
!
m
C−1
m
1
m
1−
= 1 − e− C−1 ≤
e
C −1
⇒ E (erfolgreiche Nachrichten) ≤ n · e−
2. Fall: n ≤ C ⇒
n−1
C
<1
Es gilt:
1
e
a) m ≥ C ⇒
m
C
n−1
C
≤1
≥1
Es folgt wie oben:
!
m
1 C
≤1
1−
e
n−1
C
·
m
C −1
n−1
C
5 Frequenzwahl
89
⇒ E (erfolgreiche Nachrichten) ≤ n · 1 · 1 ≤ n
b) m < C ⇒
m
C
<1
Analog zu Fall 1b) ist zu zeigen:
!
m
1 C
m
1−
≤
e
C −1
⇒ E (erfolgreiche Nachrichten) ≤ n · 1 ≤ n
2. Abschätzung nach unten
P (Erfolg auf Kanal i) = P (genau 1 Sender auf i) · P (mindestens 1 Empfänger auf i)
(n−1)
1
1
=n· · 1−
· (1 − P (kein Empfänger auf i))
C
C
C· n−1 m 1
1 ( C )
1
=n· · 1−
· 1− 1−
C
C
C
Insgesamt:
n−1 m C 1 X
1
1
E(erfolgreiche Nachrichten) = n ·
1−
· 1− 1−
C i=1
C
C
n−1 m 1
1
1
=n· ·C · 1−
· 1− 1−
C
C
C
n−1 m 1
1
=n· 1−
· 1− 1−
C
C
1.Fall: n > C
Es gilt:
1
1−
C
n−1
=
1
1−
C
n−1
(C−1)· C−1
n−1
≥ e− C−1
5 Frequenzwahl
90
a) m ≥ C
n−1
− C−1
⇒ E (erfolgreiche Nachrichten) ≥ n · e
1
· 1−
e
b) m < C
1
1− 1−
C
m −m
C
≥ 1−e
≥
1
1−
e
·
m
C
m
1
·
· 1−
C
e
n−1
− C−1
⇒ E (erfolgreiche Nachrichten) ≥ n · e
2.Fall: n ≤ C
1
1−
C
n−1
≥
1
1−
n
n−1
≥
1
e
a) m ≥ C
1
1− 1−
C
m ≥
1
1−
e
1
1
⇒ E (erfolgreiche Nachrichten) ≥ n · · 1 −
e
e
b) m < C
1
1− 1−
C
m ≥
1
1−
e
·
m
C
1
1
m
⇒ E (erfolgreiche Nachrichten) ≥ n · · 1 −
·
e
e
C
5 Frequenzwahl
91
Trägt man die Abschätzungen nach unten und oben zusammen, ergibt sich:
Falls n > C und m ≥ C
− n−1
C
n·e
n−1
− C−1
≥ E (erfolgreiche Nachrichten) ≥ n · e
1
· 1−
e
Falls n > C und m < C
− n−1
C
n·e
n−1
m
m
1
− C−1
·
≥ E (erfolgreiche Nachrichten) ≥ n · e
·
· 1−
C −1
C
e
Falls n ≤ C und m ≥ C
1
1
n ≥ E (erfolgreiche Nachrichten) ≥ n · · 1 −
e
e
Falls n ≤ C und m < C
1 m
1
m
≥ E (erfolgreiche Nachrichten) ≥ n · ·
· 1−
n·
C −1
e C
e
Theorem 5.1.4
Die Abschätzungen beweisen, dass die höchste Anzahl von erfolgreichen Nachrichten bei
n ≤ C und m ≥ C zu erwarten ist.
5.2
Geometrische Verteilung
Die geometrische Verteilung ist eine sehr gegensätzliche Wahrscheinlichkeitsverteilung gegenüber der Gleichverteilung.
Definition 5.2.1 Geometrische Verteilung
Stehen C Kanäle zur Verfügung, so gilt für die Wahl des Kanals t in der geometrischen
Verteilung folgende Wahrscheinlichkeit:
(
P (C = t) =
t < C,
t = C,
1
;
2t
1
.
2C−1
5 Frequenzwahl
92
Abbildung 5.2: Geometrische Verteilung für acht Kanäle
Der zweite Fall wird genutzt, damit die Summe aller Wahrscheinlichkeiten Eins ergibt.
Der Erwartungswert für die Anzahl der erfolgreichen Nachrichten wird analog zur
uniformen Verteilung berechnet. Es ergibt sich:
E(erfolgreich versendete Nachrichten auf Kanal i)
= 0·P (keine erfolgreiche Nachricht auf Kanal i)+1·P (eine erfolgreiche Nachricht auf i)
P(eine Nachricht auf Kanal i erfolgreich)
= P (genau ein Sender auf i) · P (mind. ein Empfänger auf i)
= n · P (C = i) · (P (C = i))(n−1) · (1 − (1 − P (C = i))m )
=
C
X
n · P (C = i) · (1 − P (C = i))(n−1) · (1 − (1 − P (C = i))m )
i=1
Eine weitere Vereinfachung der Summe ist hier nicht möglich, da die P (C = i) fast alle
unterschiedlich sind.
Die Nummerierung erfolgt hier aufsteigend. Eine Permutation der Kanalnummern
ist natürlich unabhängig vom Erwartungswert.
5 Frequenzwahl
93
Die geometrische Verteilung ist sehr ungünstig für viele Sender. Schließlich hat der erste Kanal die gleiche Wahrscheinlichkeit wie die Summe aller übrigen Kanäle. Sie liefert
gute Ergebnisse bei extremen Konstellationen. Hat man zum Beispiel nur einen Sender
und einen Empfänger, ist die Wahrscheinlichkeit gleich 1/2, dass beide den ersten Kanal
wählen. Hingegen ist bei der uniformen Verteilung die Wahrscheinlichkeit, dass beide den
gleichen Kanal wählen nur 1/C.
Abbildung 5.3: 1. Vergleichsdarstellung der geometrischen Verteilung und Gleichverteilung
In den Abbildungen 5.3 und 5.4 ist auf der y-Achse der Erwartungswert1 der erfolgreich
versendeten Nachrichten aufgetragen. Die x-Achse beschreibt die Anzahl der Kanäle.
In der ersten Abbildung wurden die Daten für eine Konstellation von fünf Empfängern
und zehn Sendern aufgetragen. Die Daten in der zweiten Abbildung sind die Werte von
zehn Empfängern und zehn Sendern. In blau ist die Gleichverteilung eingezeichnet, in
grün die geometrische Verteilung. Die rot gekennzeichneten Punkte sind jeweils das
Maximum des Erwartungswertes innerhalb des Darstellungsraumes.
Ist nur ein Kanal vorhanden, liegt der Erwartungswert bei Null, da keine Nachricht versendet werden kann, wenn alle Sender auf dem gleichen Kanal senden. Zudem
erkennt man in beiden Abbildungen, dass die geometrische Verteilung einen steilen Anstieg hat und dann nahezu konstant bleibt. Geringfügige Anstiege des Erwartungswertes
sind zwar noch zu verzeichnen, in der Zeichnung sind die Unterschiede aber bereits nicht
mehr sichtbar. Schließlich haben der neunzehnte und zwanzigste Kanal nur noch eine
Wahrscheinlichkeit von
1
1
219
≈ 1.9 · 10−6 .
in den Zeichnungen abgekürzt mit EW
5 Frequenzwahl
94
Abbildung 5.4: 2. Vergleichsdarstellung der geometrischen Verteilung und Gleichverteilung
Die Zeichnungen belegen, dass die geometrische Verteilung bis zu drei Kanälen besser
ist. Allerdings muss auch der Erwartungswert betrachtet werden: Dieser liegt deutlich
unter Eins und damit wird im Erwartungswert pro Runde keine Nachricht erfolgreich
versendet.
Es folgt ein Beispiel an dem deutlich wird, wie schlecht die uniforme und wie gut die
geometrische Verteilung in Extremsituationen ist.
Beispiel 5.2.2
Seien zwanzig Kanäle, ein Sender und ein Empfänger gegeben. Bei der Gleichverteilung
1
.
20
1
≈ 3.
ergibt sich ein Erwartungswert für erfolgreiche Nachrichten von
Die geometrische Ver-
teilung hat jedoch einen deutlich besseren Erwartungswert von
Die geometrische Ver-
teilung bleibt bei dieser Kanalanzahl und einem Empfänger einschließlich einer Senderzahl
von fünf im Erwartungswert besser als die Gleichverteilung.
Lemma 5.2.3
Problematisch bei der geometrischen Verteilung ist, dass der Erwartungswert nie über Eins
steigt. Bei der Gleichverteilung liegt hingegen der Erwartungswert in vielen Fällen über
Eins. Ungünstig ist sie jedoch bei vielen Kanälen und wenig Sendern und Empfängern.
5 Frequenzwahl
5.3
95
Faktorisierte geometrische Verteilung
Die geometrische Verteilung ist zwar in Extremsituationen gut, aber in den meisten Konstellationen schneidet sie schlecht ab. Daher habe ich die so genannte faktorisierte geometrische Verteilung entwickelt.
Definition 5.3.1 Faktorisierte geometrische Verteilung
Die “reine“ geometrische Verteilung (siehe 5.2) wird um einen Faktor gestreckt. Die
Streckung bedeutet, dass nicht nur ein Kanal mit der höchsten Wahrscheinlichkeit gewählt
wird. Einer dem Faktor entsprechenden Anzahl von Kanälen wird die gleiche hohe Wahrscheinlichkeit zugewiesen.
Die Wahrscheinlichkeit muss zur Erfüllung der totalen Wahrscheinlichkeit angepasst werden und kann nicht mehr den Wert 1/2 betragen. Sei s der Faktor, um welchen die reine
geometrische Verteilung gestreckt wird, dann gilt:
(
t mod s = 0 und t < C − s, s·21t/s ;
P (C = t) =
sonst,
P (C = t − 1);
Abbildung 5.5: Faktorisierte geometrischen Verteilung für acht Kanäle und Faktor zwei
Zur Vereinfachung der Darstellung nehme ich hier an, dass immer hintereinander folgende Kanalnummern die gleiche Wahrscheinlichkeit annehmen. Welche Kanalnummern
die gleiche Wahrscheinlichkeit besitzen, ist für den Erwartungswert unerheblich. Daher
ist jede beliebige Permutation der Nummern zulässig.
Der insgesamte Erwartungswert kann vereinfacht ausgedrückt werden, da mehrere Kanäle
5 Frequenzwahl
96
die gleiche Wahrscheinlichkeit besitzen. Hier gehe ich nur auf den gesamten Erwartungswert ein, da die anderen Daten den der geometrischen Verteilung mit entsprechenden
P (C = t) gleichen:
=
C
X
n · P (C = i) · (1 − P (C = i))n−1 · (1 − (1 − P (C = i))m )
i=1
=n·s·
C/s
X
i=1
n−1 m 1
1
1
· 1− 1−
· 1−
·
s · 2i
s · 2i
s · 2i
Abbildung 5.6: 2. Beispiel einer faktorisierten geometrischen Verteilung
Für die Wahl eines geeigneten Faktors s sollte bedacht werden, dass C mod s = 0 gilt.
Wird die Gleichung nicht erfüllt, ergibt die Summe aller Wahrscheinlichkeiten nicht Eins.
Die Abbildungen 5.5 sowie 5.6 visualisieren die Wahrscheinlichkeitsverteilung. Im ersten
Diagramm wird der Faktor zwei genutzt, im zweiten Diagramm der Faktor drei. Für
die Gültigkeit der totalen Wahrscheinlichkeit besitzt die doppelte Kanalanzahl des
Faktors die kleinste Wahrscheinlichkeit. Je größer der Faktor desto ähnlicher wird die
faktorisierte geometrische Verteilung der Gleichverteilung. Bei einem Faktor von
beide Verteilungen gleich. Daher schließe ich die Nutzung dieses Faktors aus.
C
2
sind
5 Frequenzwahl
5.3.1
97
Abschätzungen für den Erfolg der faktorisierten geometrischen Verteilung
In den Abschätzungen werden einige Ungleichungen eingesetzt, welche ich im folgenden
Lemma vorstelle. Die Ungleichungen sowie die Beweise sind in [Sch 05] zu finden.
Lemma 5.3.2
1. Für alle t > 1:
n
1
1 − t−1
e
≤
t
t
Das Maximum wird mit
n
e
1
1−
t
n
t
1 n
≤ e− t ,
t
erreicht für t = n.
2. Für t ≥ n:
Für
n
1
1
≤
et
t
n
1
1−
t
n
≤
1
,
t
≥ ln n:
1
t
Für 1 ≤
n
t
1
1−
t
1 n
1
≤ e− t ≤
t
tn
≤ ln n:
1
t
1
1−
t
n
≤
ln n
n
Es folgt eine Abschätzung des Erwartungswertes der erfolgreichen Nachrichten für n Sender, m Empfänger sowie C Kanälen. Sei b = d Cs − 1e.
E (erfolgreiche Nachrichten) = n·s·
b
X
i=1
n−1 m !
1
1
1
· 1−
· 1− 1−
s · 2i
s · 2i
s · 2i
n−1 m 1
1
1
· 1−
+
· 1− 1−
s · 2b
s · 2b
s · 2b
 C

dse
n−1 m X
1
1
1

· 1−
· 1− 1−
≈n·s·
i
i
i
s
·
2
s
·
2
s
·
2
i=1
Sei T (i, n, s, m) :=
1
s2i
1−
C
G(n, s, m) := n · s
dse
X
i=1
1 n−1
s2i
1− 1−
1 m
s2i
und
dC
e
n−1 m s
X
1
1
1
T (i, n, s, m) = n · s
1− i
1− 1− i
i
s2
s2
s2
i=1
5 Frequenzwahl
98
Lemma 5.3.3
Es gelte n0 = n − 1. Genutzt werden Ungleichungen aus Lemma 5.1.2.
1. Für s · 2i ≥ n0 :
n mo
n mo
1
1
1
1
min 1, i ≤ T (i, n, s, m) ≤
· · 1−
min 1, i
s · 2i e
e
s2
s · 2i
s2
2. Für s · 2i ≤
n0
:
ln n0
T (i, n, s, m) ≤
3. Für
n0
ln n0
n mo
1
min
1, i
n0 s · 2i
s2
≤ s2i ≤ n:
n mo
n mo
ln n0
1
≤
T
(i,
n,
s,
m)
≤
min
1,
min
1, i
n0 ln n0
s2i
n0
s2
Zum Finden von Schranken bedarf es erneut der Fallunterscheidung, ob mehr Sender
oder Empfänger vorhanden sind. Dabei wird die Abschätzung nach oben benutzt, da die
untere sich nur um einen Faktor unterscheidet.
Fall a) n > m
1. Für s · 2i ≥ n0 aus Lemma 5.3.3 ergibt sich:
C
dse
X
1 m
n·s
s2i s2i
i=1
C
dse
X
1 m
≤n·s
·
n n
i
s·2 >n
m
=θ s·
n
2. Für s · 2i ≤
n0
ln n0
gilt m ≥ s · 2i .
Damit kann T(i,n,s,m) abgeschätzt werden durch
3. Für
n0
ln n0
m
s2i
= θ(1)
≤ s2i ≤ n ergibt sich:
n · s · (log log n) ·
(ln n)2 m
·
n
n
m
=θ s·
· (log n)2 · (log log n)
n
m
θ̃ s ·
n
Der zweite Fall ist eher unwichtig, das diese Konstellation selten auftritt. Die insgesamte
5 Frequenzwahl
99
Abschätzung des Erwartungswertes kann daher durch θ̃ s ·
m
n
erfolgen. Da die untere
Schranke sich nur um einen Faktor unterscheidet, genügt diese Kalkülangabe.
Fall b) n < m
1. Für s2i ≥ n0 :
n·s·
m
X
s·2i ≥n
=n·s·(
1
·1
s · 2i
1
1
1
+
+
+ . . .) = θ(s)
n 2n 3n
Da der zweite Fall unwichtig für die Abschätzung ist, wird nur noch der dritte Fall aus
Lemma 5.3.3 überprüft:
3. Für
n0
ln n0
≤ s2i ≤ n gilt die Abschätzung:
θ s · (log n)2 · (log log n) = θ̃ (s)
Theorem 5.3.4
Der Erwartungswert für die erfolgreich versendeten Nachrichten unter der Nutzung der
faktorisierten geometrischen Verteilung ist abhängig vom Empfänger-Sender-Verhältnis.
Vorausgesetzt wird die Erfüllung von C ≥ s log ns sowie n ≥ s:
Falls n ≥ m dann gilt E(erfolgreiche Nachrichten) = θ̃ s · m
.
n
Sonst E(erfolgreiche Nachrichten) = θ̃ (s).
Die Voraussetzungen bezüglich C, n und s können ohne Einschränkung angenommen
werden. Schließlich muss C groß genug sein für den Streckungsfaktor s. Gelte n < s
so würden sich die n Sender sehr wahrscheinlich auf den s Kanälen mit höchster
Wahrscheinlichkeit verteilen. Dieser Fall entspricht dann fast der uniformen Verteilung
für s Kanäle.
5 Frequenzwahl
5.4
100
Beurteilung der einzusetzenden Wahrscheinlichkeitsverteilung
Vorgestellt habe ich zuvor die Gleichverteilung, die “reine“ sowie die faktorisierte
geometrische Verteilung für die Kanalwahl. Wie in Abschnitt 5.2 bereits gesehen, ist die
geometrische Verteilung nur in Extremsituationen gut. Daher ist es ungünstig, sie für die
Kanalwahl einzusetzten.
Des Weiteren ist bekannt, dass in bestimmten Runden2 alle Knoten eine Nachricht oder
ein Beacon senden (siehe 4.3). Die Gleichverteilung erzielt in diesen Runden stets die
besten Ergebnisse, wenn die Kanalanzahl der Knotenanzahl in Reichweite des gleichen
Regals entspricht. Für die Runden mit weniger Kommunikationsteilnehmern ist die
faktorisierte geometrische Verteilung gut nutzbar. Resultierend aus diesen Beobachtungen heraus wird im Folgenden geprüft, inwiefern eine Kombination der Verteilungen zu
nutzen ist:
Für die regalweise Synchronisation erfolgt ein Vergleich der Erwartungswerte beider
Verteilungen. Anschließend wird der optimalen Faktor für die faktorisierte geometrische
Verteilung gesucht. Mit einem gegebenen Faktor ist es möglich, Verläufe von Erwartungswerten unterschiedlicher Empfänger-Sender-Verhältnissen gegenüberzustellen (siehe
5.4.3). Anhand dieser Untersuchungen werden die Konstellationen deutlich, in welchen
die Gleichverteilung besser ist und in welchen nicht. Zum Abschluß erfolgt eine genaue
Beschreibung, wie die Gleichverteilung und die faktorisierte geometrische Verteilung zu
kombinieren sind.
5.4.1
Beispielrechnungen für die regalweise Synchronisation
Die regalweise Synchronisation wird genauer untersucht. Sie eignet sich zum einen besser
für die Illustration der zu nutzenden Kombination (siehe 5.4.4). Zum anderen ist sie dem
globalen Ansatz zu bevorzugen (siehe 4.3.3).
Es werden im Folgenden zwei Konstellationen für Supermärkte laut den expliziten
Voraussetzungen (vergleiche 2.2.2) untersucht.
2
in der ersten Runde bei der regalweisen Synchronisation oder in der zweiten und zehnten Runde des
globalen Ansatzes
5 Frequenzwahl
101
1. Szenario, 2, 10 m Durchgangsbreite
Mit einer durchschnittlichen Artikelbreite von acht Zentimetern, befinden sich 120
Knoten im Sendebereich des eigenen Regals (siehe 2.2.5). Die Empfängerzahl beruft sich
damit auf neunzig.
Diese Daten setze ich in die im Anhang A.1 vorgestellte regalweise Synchronisation ein.
In den ersten drei Runden der Sendephasen wird die Gleichverteilung für die Kanalwahl
genutzt. In den folgenden Runden kommt die faktorisierte geometrische Verteilung
zum Einsatz. Allgemein wird eine fremde Nachricht mit einer Wahrscheinlichkeit von
0, 75 weitergeleitet, wenn eigene neue Sensordaten vorhanden sind. Der Server simuliert
zunächst neunzig verschiedene Empfänger.
a) Liege die Wahrscheinlichkeit, dass bei einem Knoten eigene Sensordaten zum
Aufwachpunkt existieren, bei zehn Prozent. Die Ergebnisse der regalweisen Synchronisation nach drei Runden lauten:
Verbleibende Nachrichten:
Regal 1: 1
Regal 2: 21
Regal 3: 36
Regal 4: 43
Regal 5: 44
Angekommene Nachrichten: 25
damit ergibt sich für die vierte Runde:
für Regal 1: 1 Sender und 74 Empfänger
für Regal 5: 44 Sender
Die Erwartungswerte für die Anzahl von erfolgreich versendeten Nachrichten in
der vierten Runde sind von der Gleichverteilung und der faktorisierten geometrischen
Verteilung zu vergleichen. Diese werden für die durchschnittliche Anzahl von verbleiben
Sendern, also 33 (Mittelwert der Regale 2, 3 und 4) und 120 Kanälen berechnet. Als
Anzahl der Empfänger wird ebenso der Mittelwert von 59 betrachtet.
Diese Empfängerzahl entsteht durch Zahl aller Empfänger in Sendereichweite,welches
−3/4· verbleibende Sender im folgenden Regal entspricht.
Das erste und das fünfte Regal werden bei der Mittelung der Werte außer Betracht
5 Frequenzwahl
102
gelassen, da für beide eine besondere Situation besteht: Im ersten Regal finden schließlich
keine Empfangsoperationen statt und das fünfte Regal kommuniziert direkt mit dem
Server.
Die Gleichverteilung hat für diese Konstellation einen Erwartungswert von etwa 9, 83.
Abbildung 5.7: Erwartungswert der faktorisierten Verteilungzu 1a)
In Abbildung 5.7 ist die Kurve des Erwartungswertes auf der y-Achse aufgetragen. Auf
der x-Achse werden unterschiedliche Faktoren zur Streckung getestet.
Die faktorisierte geometrische Verteilung erreicht einen besseren Erwartungswert von
etwa 10, 27 bei Faktor 28.
b) Die Wahrscheinlichkeit für eine eigene Nachricht liege nun bei ps= 0,05.
Regal 1: 0
Regal 2: 8
Regal 3: 13
Regal 4: 17
Regal 5: 19
5 Frequenzwahl
103
Bei der Überprüfung für den Erwartungswert werden wiederum die Mittelwerte
von Sendern und Empfängern genommen: 13 Sender und 78 Empfänger.
Abbildung 5.8: Erwartungswert der faktorisierten Verteilung zu 1b)
Die Gleichverteilung hat einen Erwartungswert von 5, 63. Die Kurve des Erwartungswertes für unterschiedliche Faktoren der faktorisierten geometrischen Verteilung ist in
Abbildung 5.8 zu sehen. Der maximale Erwartungswert liegt bei 14 mit einem Wert von
6, 97. Dieser Erwartungswert ist deutlich höher als der Wert der Gleichverteilung!
Für die nächsten beiden Überprüfungen wird eine durchschnittliche Artikelbreite von
zehn Zentimetern betrachtet. Damit sind 96 Sender und 72 Empfänger in Reichweite.
Die Kanalanzahl entspricht weiterhin der Anzahl der Sender in Reichweite und wird
somit auf 96 gesenkt. Der Server simuliert nun fünfzig Empfänger.
c) ps = 0.1
Regal 1: 1
Regal 2: 16
Regal 3: 28
5 Frequenzwahl
104
Regal 4: 34
Regal 5: 39
Es ergeben sich die Mittelwerte von 26 Sendern und 65 Empfängern zur Berechnung des Erwartungswertes.
Bei der Gleichverteilung beträgt der Erwartungswert 8, 85. Der maximale Erwartungswert
für die faktorisierte geometrische Verteilung ist 9, 62 (siehe Abbildung 5.9) bei einem
Faktor von 22.
Abbildung 5.9: Erwartungswert der faktorisierten Verteilungzu 1c)
d) ps = 0.05
5 Frequenzwahl
105
Regal 1: 0
Regal 2: 6
Regal 3: 10
Regal 4: 14
Regal 5: 18
Abbildung 5.10: Erwartungswert der faktorisierten Verteilung zu 1d)
Als Mittelwerte werden zur Berechnung des Erwartungswertes 10 Sender und 80
Empfänger genutzt.
Das Maximum für die faktorisierte geometrische Verteilung beträgt 5, 91 für x = 12. Für
die Gleichverteilung ist der Erwartungswert 4, 53.
5 Frequenzwahl
106
2. Szenario, 1, 20 m Durchgangsbreite
Mit einer durchschnittlichen Artikelbreite von acht Zentimetern befinden sich 74 Knoten
im Sendebereich der eigenen Regalreihe (siehe Beispiel 2.2.5). Damit ergibt sich eine
Empfängerzahl von 55.
Der Server simuliert vierzig verschiedene Empfänger. Die weiteren Annahmen sind wie
oben gewählt.
a) Die Wahrscheinlichkeit für eigene Sensordaten zum Aufwachpunkt liegen bei
zehn Prozent. Ergebnisse der regalweisen Synchronisation nach drei Runden:
Regal 1: 1
Regal 2: 12
Regal 3: 21
Regal 4: 26
Regal 5: 30
20 Sender und 37 Empfänger sind die resultierenden Durchschnittswerte.
Die Gleichverteilung hat für diese Konstellation einen Erwartungswert von etwa 6, 11.
In Abbildung 5.11 ist zu erkennen, dass die faktorisierte geometrische Verteilung einen
besseren Erwartungswert von etwa 6, 73 bei x = 30 erreicht.
b) Die Wahrscheinlichkeit für eine eigene Nachricht liege nun bei ps= 0,05.
Regal 1: 0
Regal 2: 5
Regal 3: 9
Regal 4: 11
5 Frequenzwahl
107
Abbildung 5.11: Erwartungswert der faktorisierten Verteilung zu 2a)
Regal 5: 13
Zur Überprüfung des Erwartungswertes in der vierten Runde werden die Mittelwerte von acht Sendern und 47 Empfänger eingesetzt.
Die Kurve des Erwartungswertes zeigt Abbildung 5.12. Bei x = 8 wird das Maximum
von 4, 33 angenommen. Dieser Erwartungswert ist deutlich höher als der Wert der
Gleichverteilung, welcher nur einen Wert von 3, 44 erreicht.
Für die nächsten beiden Überprüfungen wird eine durchschnittliche Artikelbreite von
zehn Zentimetern betrachtet. Damit befinden sich 30 Sender und 23 Empfänger in
Reichweite. Die Kanalanzahl wird entsprechend der Senderzahl auf 30 gesenkt. Der
5 Frequenzwahl
108
Abbildung 5.12: Erwartungswert der faktorisierten Verteilung zu 2b)
Server simuliert nun zwanzig Empfänger.
c) ps = 0.1
Regal 1: 0
Regal 2: 5
Regal 3: 9
Regal 4: 11
Regal 5: 12
Es ergeben sich die Mittelwerte von 8 Sendern und 15 Empfängern zur Berechnung des
Erwartungswertes.
5 Frequenzwahl
109
Abbildung 5.13: Erwartungswert der faktorisierten Verteilung zu 2c)
Für die Gleichverteilung beträgt der Erwartungswert 2, 52. Der maximale Wert für
die faktorisierte geometrische Verteilung nimmt 2, 66 (siehe Abbildung 5.13) bei einem
Faktor von sechs an.
d) ps = 0.05
Regal 1: 0
Regal 2: 2
Regal 3: 4
Regal 4: 4
Regal 5: 5
5 Frequenzwahl
110
Abbildung 5.14: Erwartungswert der faktorisierten Verteilung zu 2d)
3 Sendern und 19 Empfängern sind die Durchschnittswerte für die Berechnung.
Das Optimum für die faktorisierte geometrische Verteilung ist 1, 75 für x = 4. Für die
Gleichverteilung beträgt der Erwartungswert 1, 33.
Beobachtung
Die faktorisierte geometrische Verteilung besitzt stets einen besseren Erwartungswert als
die Gleichverteilung, auch wenn die Unterschiede manchmal nur geringfügig sind.
Es gibt natürlich trotzdem eine Vielzahl von Konstellationen, für welche die Gleichverteilung bessere Ergebnisse liefert. Das Verhältnis der Erwartungswerte beider Verteilungen
wird in Abschnitt 5.4.3 noch einmal genauer untersucht. Für diese Untersuchungen muss
jedoch ein Faktor bekannt sein, mit welchem die faktorisierte geometrische Verteilung
stets gute Ergebnisse erzielt. Dies folgt im nächsten Abschnitt.
5.4.2
Einzusetzender Faktor in der faktorisierten geometrischen
Verteilung
Als zu nutzender Faktor zur Streckung der “reinen “ geometrischen Verteilung kann jede
beliebige Zahl zwischen 1 und C/2 eingesetzt werden. Beim Faktor Eins erhält man die
“reine “ geometrische Verteilung, bei C/2 die uniforme Verteilung.
5 Frequenzwahl
111
Abbildung 5.15: 1. Beispielverlauf für ansteigenden Streckungsfaktor
Daher ist nicht jeder Faktor für eine Nutzung gleich gut geeignet. Schließlich soll die faktorisierte geometrische Verteilung nicht polarisieren und in vielen Konstellationen Abhilfe
schaffen, in denen die Gleichverteilung keine so guten Werte liefert.
Zur Findung eines geeigneten Faktors wurden neben den bereits im vorherigen Abschnitt
gegebenen Kurven, weitere Graphen angefertigt. Dabei wird als Kanalanzahl der Wert
von 120 genutzt. Auf der y-Achse ist der Erwartungswert und auf der x-Achse wird der
Streckungsfaktor aufgetragen . In den Abbildungen 5.15 bis 5.18 sind stets 28 Sender vertreten, die Anzahl der Empfänger nimmt von Darstellung zu Darstellung kontinuierlich
ab.
In Abbildung 5.19 wurde für die Bestimmung des Erwartungswertes die Anzahl der Sender
auf fünfzig erhöht.
Die Graphen zeigen, dass gute Erwartungswerte für einen Faktor von etwa 12 oder 14
angenommen werden. Der maximal erreichte Erwartungswert wird zwar manchmal für
eine größere Streckung erreicht, allerdings ist dieser Wert nicht deutlich größer als der
Erwartungswert bei 12 oder 14. Um sicher zu gehen, dass ein solcher Faktor wirklich gut
ist, werden im Anschluss verschiedene Konstellationen miteinander verglichen.
5 Frequenzwahl
112
Erwartungswerte von unterschiedlichen Konstellationen können schlecht miteinander verglichen werden. Schließlich geht in den Erwartungswert stets die Anzahl der Sender, der
Empfänger und der Kanäle ein. Daher definiere ich eine Erfolgsquote.
Definition 5.4.1 Erfolgsquote
Sei n die Anzahl der Sender, m die Anzahl der Empfänger und C die Anzahl der
genutzten Kanäle.
Die Erfolgsquote EQ wird definiert als:
EQ(n, m, C) =
E(erfolgreiche Nachrichten)
n
m
C
Im Nenner der Erfolgsquote steht das Verhältnis von Empfängern zu Kanälen, im Zähler
das Verhältnis von erfolgreichen Nachrichten zu Sendern.
Diese Erfolgsquote kann sowohl für die uniforme Verteilung als auch für die faktorisierte
geometrische Verteilung mit entsprechenden Erwartungswerten berechnet werden.
Die
te
ter
Dateien
sind
den
zur
auf
der
Namen
Berechnung
beigefügten
und
CD
Visualierung
unter
der
Erfolgsquo-
Mupad Quellen
¯
“FaktorisiserteGeometrische Erfolgsquote.mnb“
¯
unsowie
5 Frequenzwahl
113
“Gleichverteilung Erfolgsquote.mnb“ zu finden.
¯
In den folgenden Abbildungen werden auf der y-Achse die Erfolgsquote (EQ) und auf der
x-Achse der Streckungsfaktor aufgetragen. Die Daten sind Mittelwerte der Erfolgsquote
von verschiedenen Empfänger-Sender-Verhältnissen. Für die erste Abbildung 5.20 bedeutet dieses, dass die Erfolgsquote für 5, 15, 25 und 35 Empfänger mit jeweils 10, 20, 30, 40,
50 und 60 Sender gemittelt wurde. Angemerkt sei, dass für die erste Mittelwertberechnung eine Kanalzahl von 120 genutzt wurde und die Gleichverteilung eine Erfolgsquote
von 0, 704 erreicht.
Für die Daten in Abbildung 5.21 werden für die Bestimmung der Mittelwerte 192 Kanäle
eingesetzt. Die Gleichverteilung liefert hier eine Erfolgsquote von 0, 677. Die faktorisierte
geometrische Verteilung hat ihr Maximum bei 1.55.
Die Kurve für 96 Kanäle ist in Abbildung 5.22 zu sehen. Die Gleichverteilung hat eine
Erfolgsquote von 0, 647, die faktorisierte geometrische Verteilung eine höhere Quote von
etwa 0, 8.
5 Frequenzwahl
114
Lemma 5.4.2
Insgesamt bestätigen die Kurvenverläufe der Erfolgsquote, dass für die meisten
Verhältnisse ein Faktor um 12-14 gut ist. Erfolgreich ist jedoch auch ein Faktor von
C
.
5
Dieses ist verständlich, da in diesem Fall nur vier unterschiedliche Wahrscheinlichkeiten
bei der Kanalwahl existieren. Damit gelangt man schon nahe an die Uniforme.
Zudem rechtfertigt die Erfolgsquote einen Einsatz zusätzlich zur Gleichverteilung, da in
den obigen Durchschnittswerten diese Wahrscheinlichkeitsverteilung besser als die Gleichverteilung ist.
5 Frequenzwahl
Abbildung 5.20: 1. Beispiel der Erfolgsquote für ansteigenden Streckungsfaktor
115
5 Frequenzwahl
116
5 Frequenzwahl
5.4.3
117
Vergleichsverläufe des Erwartungswertes
Zum besseren Vergleichen der beiden Verteilungen, sind in den folgenden Abbildungen
die Erwartungswerte (y-Achse) für eine ansteigende Anzahl von Sendern (x-Achse) dargestellt. Für alle Diagramme wurden 120 Kanäle, für die faktorisierte geometrische Verteilung ein Streckungsfaktor von zwölf und eine feste Anzahl von Empfängern vorausgesetzt.
Die blaue Kurve zeigt die Gleichverteilung, die faktorisierte geometrische Verteilung wird
in grün dargestellt.
Abbildung 5.23: 1. Vergleich der faktorisierten geom. Verteilung und der Gleichverteilung
In Abbildung 5.23 war die Empfängerzahl gleich zwanzig. Es ist deutlich zu erkennen,
dass bei wenigen Sendern die faktorisierte geometrische Verteilung einen besseren Erwartungswert als die Gleichverteilung aufweist. Die uniforme Verteilung wird mit zunehmender Anzahl von Sendern immer besser, schließlich sind im Erwartungswert immer mehr
Kanäle mit Sendern belegt. Bei n = 60 liegt damit auch das Maximum. Im Erwartungswert befindet sich dann auf jedem zweiten Kanal ein Sender.
Die Daten in Abbildung 5.24 sind für vierzig Empfänger berechnet worden. Mit einer
höheren Senderanzahl ist die faktorisierte geometrische Verteilung in der Anfangsphase
nicht mehr wesentlich besser.
Bei der faktorisierten geometrischen Verteilung finden sich wenige Sender auf den Kanälen
5 Frequenzwahl
118
ein, welche am wahrscheinlichsten auch ein Empfänger wählt. Da bei der Gleichverteilung
alle Kanäle die gleiche Wahrscheinlichkeit besitzen, gibt es keine Kanäle auf denen sich
Knoten eher begegnen als auf anderen.
Eine extreme Konstellation ist in Abbildung 5.25 zu sehen. Dort sind die Daten für 80
Empfänger dargestellt. Hier ist die faktorisierte geometrische Verteilung bis zu einer
Senderanzahl von 21 überlegen. Wichtig zu bemerken ist, dass bei vierzig Sendern die
Gleichverteilung schon ab einer Anzahl von 14 Sendern einen besseren Erwartungswert
5 Frequenzwahl
119
liefert. Jedoch ist die Differenz zwischen den Erwartungswerten in dieser Abbildung
deutlich größer.
Diese Darstellungen zeigen, dass ein zu früher Einsatz der faktorisierten geometrischen Verteilung nicht gut ist. Allgemein sind Abschätzungen der Verhältnisse von
sendenden Stationen und verfügbaren Empfängern schwer zu tätigen. Daher ist es
sinnvoll, ein ausgewogenes Verhältnis der genutzten Wahrscheinlichkeitsverteilungen zu
nutzen. Wird in der Hälfte der Runden die Gleichverteilung und in der andere Hälfte die
faktorisierte geometrische Verteilung eingesetzt, sind alle Konstellationen berücksichtigt.
5.4.4
Kombination für das optimierte 1 QK-Protokoll
In den vorherigen Abschnitten wurde gezeigt, dass sowohl der Einsatz der Gleichverteilung als auch der faktorisierten geometrischen Verteilung berechtigt ist.
Zunächst wird die einfache Variante der regalweisen Synchronisation betrachtet.
Dabei sind die Sendephasen der Regalreihen disjunkt (siehe 4.3.1). Aufgrund der
Ergebnisse darf die Gleichverteilung nicht zu früh für die Kanalwahl abgelöst werden.
Wenn k die Anzahl der Runden der Sendephase ist, empfiehlt sich eine Nutzung der
Gleichverteilung ungefähr für die ersten b k2 c Runden und anschließend der faktorisierte
geometrische Verteilung mit einem Faktor um 12 oder 14. Der wirklich eingesetzte
Faktor hängt natürlich von der Anzahl der Kanäle ab. Schließlich muss für die totale
Wahrscheinlichkeit bezüglich des Faktors s C mod s = 0 gelten.
Ist die Wahrscheinlichkeit für eigene Sensordaten nach dem Aufwachen höher als 0.15,
senden mehr Sender in Reichweite. Daher ist ein längerer Einsatz der Gleichverteilung
sinnvoll und es sollte erst nach b 32 · kc Runden ein Wechsel der genutzten Wahrscheinlichkeitsverteilung erfolgen.
Für die regalweise Synchronisation, in der sich die Sendephasen benachbarter Hopdistanzen sich überschneiden (siehe zur Verdeutlichung die Abbildung 5.26) ist die
faktorisierte geometrische Verteilung von besonders großem Nutzen.
Es werden Knoten der Distanz i betrachtet, welches Nachrichten zum Server sendet. Die
Sensorknoten des nächsten Hops befinden sich somit in Distanz i − 1. Zudem wird ohne
5 Frequenzwahl
120
Abbildung 5.26: Aufgabe der disjunkten Sendebereiche der einfachen Variante
Einschränkung der Allgemeinheit festgelegt, dass i gerade ist.
In der ersten Runde der Sendephase (blau) empfangen ausschließlich die Sensorknoten
in Regalreihe i + 1. Daher sollte auf jeden Fall die Gleichverteilung genutzt werden. Für
die zweite Runde setzte ich ebenfalls die Gleichverteilung an, da auch hier die meisten
Sensorknoten in i noch senden werden.
Ab der dritten oder vierten Runde werden wahrscheinlich viele Nachrichten bereits
verschickt worden sein. Dies führt dazu, dass die Anzahl der Sender in Regal i verringert
ist und die Anzahl der Sender in Regal i + 1 erhöht wurde.
Um nun einen guten Nachrichtendurchsatz zu erreichen, wird die faktorisierte geometrische Verteilung genutzt. Dabei besitzen die Knoten mit verschiedenen Hopdistanzen
jedoch für den Sendevorgang nicht die gleiche Wahrscheinlichkeitsverteilung:
Knoten mit gerader Hopdistanz nutzen für das Senden die faktorisierte geometrische
Verteilung so, dass die Kanäle 0 . . . s − 1 die höchste Wahrscheinlichkeit besitzen.
Sensorknoten ungerader Distanz setzen die umgekehrte Kanalnummerierung ein. Den
letzten s Kanälen wird somit die höchste Wahrscheinlichkeit zugesprochen. Für den
Empfangsvorgang nutzen die Knoten jeweils die umgekehrte Kanalnummerierung.
Falls die Sendereichweite in etwa so begrenzt ist, dass Sensorknoten aus i nur Knoten aus
den Regalen i − 1 und i + 1 erreichen, bedarf es nur der Unterscheidung für die Kanalnummerierung von zwei benachbarten Regalen. Umfaßt die Sendereichweite mehr virtuelle
Regalreihen, dessen Sender keine disjunkten Sendephasen haben (siehe Abbildung 5.27),
müssen mehr Variationen der Kanalnummerierung genutzt werden.
Setzt man die regalweise Synchronisation mit der von der Hopdistanz abhängigen faktorisierten geometrischen Verteilung ein, werden mit Sicherheit bessere Ergebnisse als mit
dem globalen Ansatz erreicht. Zudem ist das Verfahren besser als die Gleichverteilung:
Zwei Knoten benachbarter Regale senden bei der uniformen Verteilung mit der Wahr-
5 Frequenzwahl
121
Abbildung 5.27: Regalweise Synchronisation mit vielen Sendephasenüberschneidungen
scheinlichkeit von 1/C auf dem gleichen Kanal. Die Wahrscheinlichkeit unterscheidet sich
dabei nicht von der Wahrscheinlichkeit, dass zwei Knoten der gleichen Distanz auf dem
gleichen Kanal senden.
Bei dem obigen Ansatz mit den umgekehrten Kanalnummerierungen für die Wahrscheinlichkeiten senden Knoten mit gerader Hopdistanz mit der höchsten Wahrscheinlichkeit
auf den ersten s Kanälen. Die Knoten mit ungerader Distanz senden auf den gleichen
Kanälen nur mit der geringsten Wahrscheinlichkeit. Zur Verdeutlichung der Dimensionen
wird hier ein Beispiel gegeben:
Beispiel 5.4.3
Es seien 120 Kanäle gegeben und ein Faktor von 12 wird für die Streckung der faktorisierten geometrischen Verteilung genutzt. Knoten aus dem Regal i, mit i gerade, senden auf
den Kanälen 0 . . . 11 mit einer Wahrscheinlichkeit von
1
24
≈ 0, 0417. Knoten des Regals
i + 1 senden auf den gleichen Kanälen jedoch nur noch mit einer Wahrscheinlichkeit von
1
12·210
=
1
12288
≈ 8, 14 · 10−5 .
In der Gleichverteilung hat jeder Kanal die Wahrscheinlichkeit von
1
120
≈ 8, 33 · 10−3 .
Anhand des Beispiels ist erkennbar, dass Störungen ziemlich unwahrscheinlich sind,
die aufgrund von gleichzeitigen Sendern verschiedener Regale resultieren könnten. Da
durch eine deutliche Überschneidung der Sendephasen die Latenzzeit für die Nachrichtenübertragung zum Server drastisch reduziert wird, ist dieses Verfahren sehr gut geeignet.
Bemerkung 5.4.4
In Abschnitt 5.4.2 wurde festgestellt, dass ein Faktor zwischen 12 und 14 gute Ergebnisse
erzielt. Da die Hardware dreizehn Kanäle unterstützt, empfiehlt sich der Faktor dreizehn.
5 Frequenzwahl
122
So besitzt bei der Simulation mehrerer Kanäle jeder Kanal in der internen Runde die
gleiche Wahrscheinlichkeit.
Des Weiteren ist anzumerken, dass die faktorisierte geometrische Verteilung nahezu die
gleichen Ergebnisse erzielt, wenn statt C zum Beispiel 3/4 · C Kanäle genutzt werden.
Dies ist damit zu begründen, da die geringsten Wahrscheinlichkeiten sehr kleine Werte
sind.
Wenn für die Gleichverteilung C/13 interne Runden existieren, kann für die faktorisierte
geometrische Verteilung die Anzahl der internen Runden verringert werden. Dies führt
zu einen schnelleren Rundendurchlauf, sowie zur Einsparung von Energie.
Darüber hinaus ist beweisbar, dass keine andere Wahrscheinlichkeitsverteilung eine bessere absolute Anzahl von erfolgreichen Nachrichten in einer Runde aufweist.
Ausgenommen ist dabei die uniforme mit gleicher Anzahl von Sendern und Kanälen.
Beim globalen synchronen Aufwachpunkt ist die Anzahl der konkurrierenden Sender
deutlich höher als bei der regalweisen Synchronisation. Jedoch kann auch mit einer
versetzten Nutzung der faktorisierten geometrischen Verteilung die Zahl der Interferenzen
verringert werden.
5 Frequenzwahl
123
Kapitel 6
Fairness des Routings
Als zweiten Optimierungsansatz für das 1 QK-Protokoll habe ich die Nachrichtenweiterleitung gewählt. Zunächst folgt die Problemdarstellung sowie die Lösungsidee.
Problemdarstellung 6.0.5 Fairness
Im 1 QK-Protokoll werden die eigenen Nachrichten immer bevorzugt. Liegen eigene neue
Sensordaten vor, wird aus diesen Daten eine Nachricht erstellt, auch wenn eine fremde
Nachricht empfangen wird.
Dies kann zu einem Nachrichtenstau führen. Die Nachrichten von weiter entfernten Knoten werden benachteiligt. Damit existiert im Routing keine Fairness.
Zunächst möchte ich die Problematik eines aufkommenden Nachrichtenstaus verdeutlichen, anschließend gehe ich auf Wahrscheinlichkeitsfunktionen ein, welche
Entscheidungsfunktionen über eine Weiterleitung beinhalten.
In Abbildung 6.1 ist ein Sensornetz dargestellt. Die blauen Knoten leiten Nachrichten zum Server weiter. Ein magenta farbener Nachrichtenumschlag bedeutet,
dass eigene Sensordaten vorliegen. Ein später erscheinender grüner Nachrichtenumschlag zeigt an, dass eine fremde Nachricht bearbeitet wird. Anhand von schwarzen
Strichen werden Sendeversuche dargestellt. Dabei wird das 1 QK-Protokoll bereits mit
Synchronisierung eingesetzt. Die Kanalwahl ist hier nicht von Interesse. Als erfolgreiche
Übermittlung wird daher als Vereinfachung für dieses Kapitel definiert, wenn ein
Empfänger in Reichweite die Nachricht annehmen kann.
Die Sensorknoten haben eine Sendereichweite, so dass sie nur alle direkt benachbarten
Knoten erreichen können. Knoten sind nicht erreichbar für andere Sender, wenn sie
eigene Daten oder eine fremde Nachricht zum Aufwachzeitpunkt besitzen. Dies wird mit
125
einem gelben Blitz symbolisiert. Knoten mit eigenen Daten lauschen zwar nach einer
Nachricht, aber es folgt definitiv keine Weiterleitung.
Abbildung 6.1: Visualisierung des Nachrichtenstaus - Ausgangsposition
Abbildung 6.2: Visualisierung des Nachrichtenstaus - Erste Sendephase
In der Ausgangsposition haben vereinzelte Knoten neue Sensordaten zum Weiterleiten.
Die Sendephase ist in Abbildung 6.2 visualisiert. Es waren nicht alle Sendeversuche in der
126
ersten Sendephase erfolgreich und ein Knoten hat seine eigene Nachricht nicht versenden
können (vergleiche Abbildung 6.3).
Abbildung 6.3: Visualisierung des Nachrichtenstaus - Nach der ersten Sendephase
Vor der nächsten Wachphase wurden viele Warenbestände verändert und die meisten
Knoten im Netz besitzen versandbereite Daten (Abbildung 6.4).
Abbildung 6.4: Visualisierung des Nachrichtenstaus - Vor der zweiten Sendephase
127
Dadurch verringert sich der Nachrichtendurchsatz innerhalb des Netzes deutlich, erkennbar in Abbildung 6.5.
Abbildung 6.5: Visualisierung des Nachrichtenstaus - Die zweite Sendephase
Die Abbildung 6.6 zeigt, dass nun auch die restlichen Knoten neue Sensordaten aufzuweisen haben. Das Netz ist ziemlich ausgelastet, und es existiert immer noch ein geringer
Nachrichtendurchsatz. Die Knoten in der ersten Reihe haben bei jedem Aufwachen die
Chance eigene Daten zum Server zu leiten. Knoten in den hinteren Reihen erreichen nicht
annähernd diese geringe Latenz.
Die Wahrscheinlichkeit im Release 2.1, dass eine fremde Nachricht nach dem Hören eines
Knotens weitergeleitet wird, beträgt (1 − p). Dabei entspricht p der Wahrscheinlichkeit,
dass der Knoten eigene neue Sensordaten vorliegen hat. Eine Nachricht wird somit mit
der Wahrscheinlichkeit von (1 − p)x hintereinander folgende x Hops befördert. Der Verlauf
der Wahrscheinlichkeit für p = 0.45 ist in Abbildung 6.7 zu sehen. Auf der y-Achse wird
die Wahrscheinlichkeit aufgetragen, dass die Nachricht durchgängig x Hops weitergeleitet
wird.
Wie intuitiv zu vermuten nimmt die Wahrscheinlichkeit für die Weiterleitung mehrerer
Hops mit sinkendem p zu (vergleiche 6.8).
128
Abbildung 6.6: Visualisierung des Nachrichtenstaus - Nach der zweiten Sendephase
Bei der Realisierung der regalweisen Synchronisation (siehe A.1) wurde angenommen, dass
eine fremde Nachricht mit 75 Prozent weitergeleitet wird, wenn eigene Daten vorliegen.
Dies führt zu der Wahrscheinlichkeitsfunktion abgebildet in 6.9 und stellt schon eine
wesentliche Verbesserung dar.
Gesucht wird jedoch eine Wahrscheinlichkeitsfunktion, so dass der Wert für alle Hops nahezu gleich ist. Diese soll also möglichst konstant sein. Dazu müssen bei der Überprüfung,
ob die fremde Nachricht weitergeleitet werden kann, die bereits zurückgelegten Hops
einberechnet werden.
Die maximale Differenz der Funktionswerte liegt stets zwischen dem Wert für einen
Hop und der maximalen Hopanzahl (entspricht der Konstante ROUTELENGTH im 1
QK-Protokoll).
Ich gehe an dieser Stelle von einer maximalen Hopdistanz von 24 aus. ROUTELENGTH bekommt im 1 QK-Protokoll nur einen Wert von zehn zugewiesen. Wenn ich
aber die Fairness bis zu 24 Hops optimiere, ist die Funktion für Weiterentwicklungen
immer noch zulässig. Zudem differieren die Werte dann auch für höhere Hopanzahlen
wenig. Schließlich ist die gesuchte Wahrscheinlichkeitsfunktion nur gering fallend oder
sogar konstant.
129
Abbildung 6.7: Verlauf der Wahrscheinlichkeitsfunktion für p=0.45
Entwickelt wurde zunächst folgende Funktion, welche die bereits zurückgelegte Hopanzahl
(x) für eine Weiterleitung betrachtet:
x
f 1(x) := f 1 (x − 1, p) · (1 − p) + p ·
x+1
mit f 1 (1) := (1 − p) + p · 0.5
Bei f1 wird eine fremde vor der eigenen Nachricht im Verhältnis “zurückgelegte
Hops : 1“ bevorzugt. Wie man in Abbildung 6.10 erkennen kann, ist die Kurve bereits
weniger steil abfallend als die Kurven der vorigen Darstellungen. Um mehr Ausgewogenheit zu erreichen, bedarf es jedoch einer weiteren Verbesserung. Daher muss bei der
Hilfsfunktion
x
x+1
Nenner und Zähler gegen Eins konvergieren. Abhilfe schafft der Einsatz
höherer Potenzen sowie der Exponentialfunktion.
1. f 2 (x) := f 2 (x − 1, p) · (1 − p) + p ·
x2 +x
x2 +x+1
2. f 3 (x) := f 3 (x − 1, p) · (1 − p) + p ·
2·x2
2·x2 +1
3. f 4 (x) := f 4 (x − 1, p) · (1 − p) + p ·
x4 +x
x4 +x+1
4. f 5 (x) := f 5 (x − 1, p) · (1 − p) + p · 1 −
1
mit f 5 (1) := (1 − p) + p · 1 − e2x
mit f 3 (1) := (1 − p) + p ·
1
e2x
mit f 2 (1) := (1 − p) + p ·
2·x2
2·x2 +1
mit f 4 (1) := (1 − p) + p ·
x2 +x
x2 +x+1
x4 +x
x4 +x+1
130
Abbildung 6.8: Verlauf der Wahrscheinlichkeitsfunktion für p=0.25
Die Funktionen sind in der Abbildung 6.11 visualisiert. Diese Abbildung kann aufgrund
des geringen Darstellungsbereiches der y-Achse leicht falsch gedeutet werden. Daher ist
in Abbildung 6.12 die y-Achse im Bereich von 0 . . . 1 dargestellt.
F2 bis f5 sind jeweils für eine Wahrscheinlichkeit von p = 0.25 dargestellt. Je kleiner die
Wahrscheinlichkeit p wird, desto geringer ist der Kurvenabfall.
f 5(x) liefert sichtbar die besten Ergebnisse. Die maximale Differenz zwischen 1 und 24
Hops beträgt nur 0, 005. Damit ist eine gute Funktion zur Entscheidung über eine Weiterleitung einer fremden Nachricht gefunden (wenn der Knoten selbst neue Sensordaten
vorliegen hat).
Abbildung 6.13 zeigt den Funktionsgraphen für p = 0.5. Die maximale Differenz beträgt
nur 0, 0098. F5 ist auch für höhere Wahrscheinlichkeitswerte von p geeignet.
Theorem 6.0.6
F5 ist eine gut einzusetzende Fairnessfunktion, da sie gegen eine Konstante konvergiert:
∞
Y
(1 − p) + p 1 − e−2x
x=1
konvergiert, wenn folgende Summe konvergiert [Sch 05]:
∞
X
x=1
ln(1 − pe−2x )
131
Abbildung 6.9: Weiterleitung mit Wahrscheinlichkeit von 75 Prozent der fremden Nachricht bei Vorliegen einer eigener Nachricht
Es gilt:
x
2
≤ ln(1 + x) ≤ x für x > 1 − 2e . Damit ergibt sich
∞
X
x=1
ln(1 − pe
−2x
) ≥ −p
∞
X
e−2x − e−4x
x=1
Da die Fairnessfunktion gegen eine Konstante konvergiert, ist die Differenz zwischen verschiedenen Hopdistanzen asymptotisch gleich Null.
Damit eigene Sensordaten nun nicht vernachlässigt werden, sollte bei der Bevorzugung
einer fremden Nachricht ein interner Hopzähler hochgezählt werden. Übertrifft dann der
1
) für die interne Hopzahl den Wert der fremden Nachricht, werden
Wert von h(x) = (1− e2x
die eigenen Daten versendet.
Die Funktionsauswertungen sind natürlich mit der gegebenen Hardware nicht trivial. Deswegen werden die ausgewerteten Werte von h(x) = (1 −
1
)
e2x
für x =
1 . . . 3ROU T ELEN GT H im FLASH-Speicher abgelegt. Des Weiteren müssen in den
uplink-Nachrichten die Anzahl der Hops überliefert werden.
Abbildung 6.10: Darstellung der Wahrscheinlichkeitsfunktion f1(x)
Abbildung 6.11: f2(x), f3(x), f4(x) und f5(x) mit p=0,25
132
133
Abbildung 6.12: f2(x), f3(x) f4(x) und f5(x) mit p=0,25 und y im Bereich von Null bis
Eins
Abbildung 6.13: Visualisierung von f5(x) mit p=0,5
Kapitel 7
Auswirkungen auf das
1 QK-Protokoll
Die in den Kapiteln 5 und 6 beschriebenen Optimierungen werden in diesem Kapitel in
das 1 QK-Protokoll integriert. Als Ausgangstand des 1 QK-Protokolls wird das Release
2.1 gesetzt [Sch 04-R02]. Die Synchronisierung ist nicht im neuen Protokoll enthalten.
Es kann der regalweise oder globale Ansatz realisiert sein. Beim globalen Ansatz wird
jedoch für die korrekte Nutzung der faktorisierte geometrische Verteilung die Existenz
der Hopdistanz vorausgesetzt. Da die Änderungen keinen Synchronisierungsansatz
voraussetzt, können uplink- und downlink-Nachrichten in jeder Sendephase verschickt
werden.
Die Variable Hopdistanz wird zum einen intern verwaltet, als auch in Beacons, uplinkNachrichten sowie deren Acknowledgements versendet. Die Expected Power Distance
fällt im Gegenzug aus dem Protokoll heraus.
Im Anschluss folgt eine Beschreibung der getätigten Änderungen. Im Abschnitt 7.2 wird
die Spezifikation zum Release 3.0 verändert.
7.1
Beschreibung der Modifikationen
Betrachtet wird zunächst die Modifikation für die Kanalwahl:
Bei der Konfiguration der Knoten bedarf es einer Anpassung der Konstanten T RECIEVE
¯
sowie POWER MSG SEND so, dass sie den Runden für den Empfangs- und Sende¯
¯
vorgang entsprechen. Bei jedem Sende- und Empfangsversuch wird dann ein Kanal
gemäß der zu nutzenden Wahrscheinlichkeitsverteilung ausgewählt. Dabei wird hier die
135
genutzte Kanalnummerierung der faktorisierten geometrischen Verteilung nach gerader
oder ungerader Hopdistanz unterschieden.
Bei der Initialisierung wird festgelegt, wie viele Runden die maximale Empfangsdauer
(Konstante count maxReceive) sowie die Wachphase (Konstante rounds wake) andauern
¯
¯
darf. Wird beim ersten Empfangsversuch eine uplink-Nachricht empfangen, wird diese
oder eine eigene Nachricht weiterversendet. Der Empfangsvorgang wird spätestens nach
count maxReceive Runden abgebrochen. Ist dann keine fremde oder eigene Nachricht
¯
zu versenden, sendet der Knoten ein Beacon und kann anschließend schlafen. Bei den
Rundenzahlen handelt es sich um Angaben für die Blockrunden, in welcher intern alle
Kanäle simuliert werden.
Da bei der regalweisen Synchronisation unterschiedliche Phasen für die downlink- und
uplink-Kommunikation existieren, können zur Synchronisation benötigten Nachrichten
in diesen Phasen versendet werden.
Zum Erreichen der Fairness, muss in den uplink-Nachrichten eine Variable integriert
werden, welche die Anzahl der bereits zurückgelegten Hops zählt (Variable counter hops).
¯
Werte für die Hilfsfunktion h(x) = (1 − e−2x ) der Fairnessfunktion mit exponentiellen
Ansatz (f5, siehe Kapitel 6) werden bei der Initialisierung in den FLASH-Speicher
abgelegt. Zur Betrachtung und Funktionsauswertung der Counter wird die Reihenfolge
verändert, in welcher eigene Daten in den Buffer gelegt werden. Ansonsten könnte nicht
unterschieden werden, ob eine bereits angenommene fremde Nachricht oder die eigenen
Daten im Buffer liegen.
Damit eigene Nachrichten nicht vernachlässigt werden, bedarf es für die eigenen Daten
der Zählung der bereits bevorzugten fremden Nachrichten (Variable counter rounds. Diese
¯
Anzahl wird mit der bereits zurückgelegten Hopanzahl fremder Nachrichten gleichgesetzt.
Die Counter werden bei jedem erfolglosen Sendeversuch inkrementiert. Aus diesem Grund
sind die Funktionswerte der Hilfsfunktion h(x) auch für x = 1 . . . 3 · ROU T ELEN GT H
in den FLASH-Speicher abgelegt.
Die neue Abarbeitung sieht wie folgt aus:
Nach dem Erhalt einer uplink-Nachricht wird zunächst überprüft, ob der Buffer mit
einer uplink-Nachricht gefüllt ist. Dies entspricht dem bisherigen Vorgehen. Liegt
keine uplink-Nachricht im Buffer, folgt ein Test ob neue Sensordaten zur Verfügung
stehen. Falls dieses nicht der Fall ist, wird ein Acknowledgement geschickt und die
Nachricht wie in der bisherigen Spezifikation zur Weiterleitung bearbeitet. Liegen
eigene Daten vor, werden die Funktionswerte aus dem FLASH-Speicher für die Counter
beider Nachrichten geholt und verglichen. Die Daten der Nachricht mit dem höheren
Funktionswert werden weiterverarbeitet. Dies impliziert die Sendung eines entsprechenden Acknowlegements, falls die empfangene Nachricht den höheren Funktionswert besitzt.
136
Für die korrekte Nutzung der Wahrscheinlichkeitsverteilungen bei der Kanalwahl
wird die Variable useEqual eingeführt. In useEqual wird die Rundennummer gespeichert,
bis welcher die Gleichverteilung genutzt wird. Als Hilfe für die Realisierung der Sendeund Empfangsphasen werden die Variablen actFrequency und actRound genutzt. Für die
Ermittlung der Funktionswerte einer fremden und einer eigenen Nachricht werden die
Variablen selfFairValue sowie foreignFairValue eingesetzt.
Die Konstanten haben einen unveränderlichen Wert. Den Variablen sind noch keine
Werte zugewiesen. Vor der Auslieferung der Knoten können Werte bei der Initialisierung festgelegt werden. Wird das Netz dann in Betrieb genommen, bedarf es einer
reset-Nachricht an alle Knoten vom Server. In dieser reset-Nachricht sind einige Werte
für den Sende- und Empfangsvorgang vorhanden. Im Release 3.0 werden nun auch
reset-Nachrichten weitergeleitet, die an keinen bestimmten Empfänger haben. Dabei
haben reset-Nachrichten die höchste Priorität bei der Versendung einer Nachricht.
Der Streckungsfaktor für die faktorisierte geometrische Verteilung wird auf dreizehn
gesetzt, da dies die hardwaremäßig unterstütze Anzahl ist.
7.2
Veränderte Spezifikation - Release 3.0
Zunächst gebe ich die neue Speicherorganisation inklusive aller Variablen an. In den
Buffer wurden zusätzlich wie zuvor beschrieben einige Variablen integriert. Des Weiteren
muss nur noch die Anzahl der Kanäle abgespeichert werden, da die Frequenzbereiche
im FLASH-Speicher gehalten werden. Das Array FREQUENCY OF CHANNEL entfällt
¯ ¯
damit.
Der Buffer benötigt folgenden Speicherplatz:
2 · long + 4 · bit + 2 · byte-Array der Länge 6 + 5 · byte + 1 · int-Array der Länge 10
1
= 2 · 4 + 4 · + 2 · 6 + 5 · 1 + 1 · 2 · 10 (alles in Byte)
8
= 8 + 0, 5 + 12 + 5 + 10 = 35, 5 Bytes
Der gesamte RAM-Speicher benötigt:
Buffer + Paket + Ack-Paket+1· real+3· bit+14· byte+1· long+2· int+1· int-Array der Länge 10
1
35, 5 + 36 + 6 + 1 · 2 + 3 · + 14 + 1 · 4 + 2 · 2 + 1 · 2 · 10 (in Byte)
8
137
= 122 Bytes
Mit Hilfe der Auslagerung einiger Daten in den FLASH-Speicher wird der genutzte
RAM durch die Protokolloptimierungen nicht deutlich vergrößert. Das 1 QK-Protokoll
im Release 2.1 benötigte 101 Bytes. Die Zählung erfolgt jeweils ohne Konstante. Der
Datentyp real wird mit Hilfe von 2 Bytes realisiert. Ein Byte für die Zahlen > 0 und ein
Byte für die Zahlen < 0.
Die genaue Beschreibung des genutzten Speichers sowie der Code des Release 3.0
ist im Anhang A.2 zu finden.
Kapitel 8
Zusammenfassung
Die Diplomarbeit realisiert zwei Optimierungen des 1 QK-Protokolls. Es wird vorausgesetzt, dass die Knoten synchronisiert werden. Daher war es unerlässlich, den Sendeund Empfangsvorgang zu modifizieren. Mit synchronisierten Knoten und gleichem
Sendeverhalten des 1 QK-Protokolls ist der Nachrichtendurchsatz gleich Null, wenn mehr
als ein Sender mit nicht disjunkten Sendereichweiten sendet. Daher wird im Release 3.0
eine Kombination von Wahrscheinlichkeitsverteilungen für die Kanalwahl eingesetzt. Das
Zusammenspiel der Gleichverteilung sowie der faktorisierten geometrischen Verteilung ist
besonders bei einer regalweisen Synchronisation gut einsetzbar.
Bei der faktorisierten geometrischen Verteilung haben einige Kanäle nur sehr geringe
Wahrscheinlichkeiten. Von der Distanz zum Server ist die Reihenfolge der zugeordneten
Wahrscheinlichkeiten zu den Kanalnummern abhängig. Damit sind Interferenzen aufgrund von Sendern in unterschiedlichen Regalen wesentlich unwahrscheinlicher als bei
gleicher Kanalreihenfolge oder der Gleichverteilung.
Die zweite Optimierung brachte Fairness in das Routingverhalten. In dem 1 QK-Protokoll
wurden stets eigene Nachrichten bevorzugt. War eine eigene Nachricht vorhanden, so
wurde diese stets weitergeleitet unabhängig davon, ob eine fremde Nachricht empfangen
wurde. Mit Hilfe der so genannten Fairnessfunktion werden die Ungleichheiten im
Routing verbessert. Die Fairnessfunktion konvergiert und damit haben alle Nachrichten
im Netz bis auf minimale Unterschiede die gleiche Wahrscheinlichkeit in einem Sendefluss zum Server zu gelangen. Dazu wurde in den Nachrichten die Anzahl der bereits
zurückgelegten Hops gezählt. Die Hopanzahl einer Nachricht wird auch inkrementiert,
wenn die Nachricht innerhalb einer Wachphase nicht versendet werden konnte. Damit
eigene Daten nicht vernachlässigt werden, existiert ein eigener Hopzähler für die internen
Daten. Liegen neue Sensordaten vor und eine fremde Nachricht wird weitergeleitet, wird
der Hopzähler für die internen Nachrichten erhöht.
8 Zusammenfassung
139
Die Optimierungen im Release 3.0 erzeugen einen besseren Nachrichtendurchsatz
und Fairness. Zudem kann eine Rekonfiguration für das gesamte Netz vom Server
durchgeführt werden. Diese Rekonfiguration ist möglich, da reset-Nachrichten ohne
bestimmten Adressaten durch das Netz weitergeleitet werden.
Durch Auslagerungen von Daten in den FLASH-Speicher benötigt das Protokoll trotz der
Optimierungen nur 122 Bytes. Damit sind die Ressourcenbeschränkungen eingehalten.
Zudem wird mit Hilfe der Synchronisation und besseren Nachrichtendurchsatz Energie
eingespart.
8.1
Ausblick
Es existieren noch einige Modifikationsmöglichkeiten zur Verbesserung des 1 QKProtokolls:
Eine Behandlung der Asymmetrie ist zum Beispiel als ein weiterer Ansatz zu nennen.
Methoden zur Vermeidung von Duplikate könnten darüber hinaus integriert werden. Zur
Energieeinsparung wäre es sinnvoll, wenn die Round-Time an Wochenenden, Feiertagen
und nach Ladenschluss anpaßt werden würde. Da nun die reset-Nachrichten durch das
Netz geleitet werden, kann die Round-Time auf Initiative des Servers bereits umgestellt
werden. Dies sollte aber durch einen Automatismus in den Knoten optimiert werden.
In der Diplomarbeit wurde an einer statische Kanalanzahl festgehalten und mit Hilfe der
faktorisierten geometrischen Verteilung wurde der Nachrichtendurchsatz über die RoundTime optimiert. Eine andere Optimierungsmöglichkeit zur Verbesserung des 2.0 Releases
des 1 QK-Protokolls ist es, die Anzahl der genutzten Kanäle dynamisch zu integrieren:
Erfährt ein Sender ein hohes Nachrichtenaufkommen durch viele Interferenzen, so kann er
die Kanalanzahl erhöhen. Treten keine Interferenzen auf und die Nachricht wird von keinem Empfänger entgegen genommen, wird die Kanalanzahl verringert. Die Veränderung
√
der Kanalanzahl C könnte zum Beispiel um C nach oben oder nach unten erfolgen. Eine
weitere Möglichkeit wäre es, eine statisch abnehmende Folge von Kanalanzahlen mit der
uniformen Verteilung zu nutzen.
Eine wichtige Erweiterung muss noch für die Knoten integriert werden, welche direkt mit
dem Server kommunizieren. Diese können ein anderes Sendeverhalten aufweisen, da der
Server immer empfangsbereit ist.
Anhang A
Quellcode
A.1
Dokumentation und Code zur regalweisen Synchronisation
Da ich den lokalen gegenüber dem globalen synchronisierten Aufwachpunkt bevorzuge,
möchte ich an dieser Stelle auf seine Implementierung genauer eingehen. Es wird
zunächst die Dokumentation des Quellcodes folgen, in welcher alle Variablen erklärt
werden. Anschließend folgt der Code.
Dokumentation und Erläuterungen
Die erste Runde ist unterschiedlich von den Folgenden: In der ersten Runde senden alle
Stationen, die keine “alte “ Nachricht bearbeiten, eine eigene oder einen Beacon. Bei
der Zählung der realen Empfänger muss unterschieden werden, welcher Nachrichtentyp
empfangen wurde. Schließlich benötigt ein Beacon nur eine Bearbeitungszeit von einer
Runde. Wurde jedoch eine uplink-Nachricht empfangen, bedarf es zunächst einer internen
Bearbeitungszeit von drei Runden sowie der Weiterleitung dieser Nachricht. Regal eins
ist dabei das Regal bei welchem der Sendefluss beginnt und steht damit am weitesten
vom Server entfernt.
Es folgt die Beschreibung der eingesetzten Variablen:
n = Anzahl der Sensorknoten in Reichweite im betrachteten Regal.
m = Anzahl der empfangsbereiten Knoten im Regal in Richtung Sendefluss. Knoten, die noch eine alte Nachricht bearbeiten, sind von der Zählung ausgenommen.
nhelp = Sensorknoten im betrachteten Regal, welche keine alte Nachricht bear-
A Quellcode
141
beiten
haveMsg = erwartete Anzahl von zuvor erreichbaren Empfängern, die nach der
aktuellen Runde eine Nachricht bearbeiten. Dabei leiten sie entweder ihre eigene (mit
Verhältnis der Variablen verhaeltnis) oder eine fremde weiter. Falls ein Empfänger keine
Nachricht hat und keine empfängt, ist er auch für eine kommende Runde empfangsbereit
und fließt nicht in haveMsg als Wert ein. HaveMsg ist die Summe der Hilfsvariablen
received, own1, own2, own3,erhieltBeacon.
received ist der Erwartungswert der Sensorknoten, die ab der nächsten Runde eine Nachricht bearbeiten. Dazu zählen neue sowie noch nicht erfolgreich weitergeleitete
Nachrichten. Zu den erfolglosen Sendeversuchen der aktuellen Runde zählen sowohl für
die Nachrichten, die mehrere oder ihren ersten erfolglosen Sendeversuch hatten.
own1 ist der Erwartungswert der Sensorknoten, die keine Nachricht empfangen
und eine eigene Nachricht besitzen.
own2 ist der Erwartungswert der Sensorknoten, die eine Nachricht empfangen,
aber ihre eigene Nachricht weiterleiten.
own3 ist der Erwartungswert der Sensorknoten, die ein Beacon empfangen haben
und eine eigene Nachricht haben.
erhieltBeacon = erwartete Anzahl der Empfänger, die nur ein Beacon enthielten
und keine eigene Nachricht haben. Diese Empfänger sind nach Bearbeitung des Beacons
(eine Runde) wieder empfangsbereit.
s = erwartete Anzahl der Sender, die eine eigene Nachricht erfolgreich in der betrachteten Runde versenden konnten.
erfolg = erwartete Anzahl der Sender, die eine bearbeitete oder noch nicht
weitergeleitete Nachricht erfolgreich versenden konnten.
sendWeiter speichert für jede Runde und jedes Regal die Sender, die in der folgenden Runde noch weiter senden. Das sind alle Sensorknoten im Regal außer denen, die
mit einer alten oder neuen erfolgreich versendeten Nachricht sowie die Knoten, die nur
einen Beacon gesendet hatten.
SendWeiter wird als Summe der Erwartungswerte dieser genannten Ereignisse berech-
A Quellcode
142
net. Abgezogen werden müssen jedoch die Sensorknoten, die gerade noch eine Nachricht
zum Versenden fertig stellen und diese erst in einer der kommenden Runden versenden.
bearbeitetNachricht = Erwartungswert der Sensorknoten, die eine fremde oder
eigene Nachricht zur Weiterleitung bearbeiten. (exklusive der Beacons in der ersten
Runde)
msg = Anzahl der Nachrichten, die zum Server übermittelt wurden
verhaeltnis entspricht der prozentualen Wahrscheinlichkeit, dass eine fremde Nachricht
weitergeleitet wird, auch wenn der Knoten eine eigene besitzt.
Quellcode angepaßt in eine lesbare Form
Der Quellcode wurde aus der Datei nicht eins zu eins übernommen, damit die mathematischen Formeln lesbarer sind.
Initialisierung
C:=10:verhaeltnis:=0.75:ps:=0.4:r:=1:msg:=0:s:=’ ’;
print(’Fremde Nachricht wird weitergeleitet mit ’. XXXXX
expr2text(verhaeltnis));
print(’Wahrscheinlichkeit für neue Sensordaten ps=’.expr2text(ps));
sender:= array(1..5, 1=10, 2=10, 3=10, 4=10, 5=10):
empfaenger:= array(1..6, 1=10, 2=10, 3=10, 4=10,5=10, 6=10):
sendWeiter:= array(1..4, 1..6,
XXXXXXXXXXXXXXX(1,1)=0, (2,1)=0, (3,1)=0, (4,1)=0,
XXXXXXXXXXXXXXX(1,6)=0, (2,6)=0, (3,6)=0, (4,6)=0):
bearbeitetNachricht:=array(1..4, 1..6,
A Quellcode
143
XXXXXXXXXXXXXXX(1,6)=0, (2,6)=0, (3,6)=0, (4,6)=0):
roundTime:=1:
Ablauf der Round-Time
while (roundTime<=10) do
i:=1:
print(’---------------------------------------------------------------’);
print(’Durchgang ’.expr2text(roundTime));
print(’---------------------------------------------------------------’);
while(i<=5) do
print(’Regal ’.expr2text(i));
XXXX print(’----------------------------’);
XXXX print(’Runde 1’);
XXXX n:=sender[i];
XXXX m:=empfaenger[i+1];
XXXX print(’Empfänger: ’.expr2text(m));
XXXX nhelp:= round(empfaenger[i]);
XXXX EmpfOhneNachricht:= round(min(m,m · (1 − ps)));
XXXX EmpfMitNachricht:= round(m − EmpfOhneNachricht);
XXXX erhieltBeacon:=
XXXXXXXXmax(0, round(C · C1 · (1 − C1 )n−1 · (nhelp · (1 − ps))
PEmpfOhneNachricht
XXXXXXXX · j=0
j · EmpfOhneNachricht
·
j
1 EmpfOhneNachricht−j
XXXXXXXX·(1 − )
));
1j
C
C
XXXX received:=
XXXXXXXXmax(0, C ·
1
C
· (1 − C1 )n−1 · (nhelp · ps
XXXXXXXX+bearbeitetNachricht[1,i]+ sendWeiter[4,i]) ·
XXXXXXXX·( C1 · ((1 − ps) + verhaeltnis · ps))j1
XXXXXXXX·(1 − ( C1 · ((1 − ps) + verhaeltnis · ps)))m−j1 );
XXXX print(’received =’. expr2text(received));
XXXX if i=5 then
XXXXXXXX own1:= 0;
XXXXXXXX own2:= 0;
XXXXXXXX own3:= 0;
XXXX else
Pm
j1=0 j1 ·
m
j1
A Quellcode
144
XXXXXXXXown1:=
XXXXXXXXXXXXC · (1 − ( C1 · (1 − C1 )n−1 ))
1
P
m
1
g
m−g
XXXXXXXXXXXX· m
;
g=0 g · g · ( C · ps) · (1 − ( C · ps))
XXXXXXXX own2:=
· (1 − C1 )n−1 · (nhelp · ps + bearbeitetNachricht[1,i]
Pm
m
XXXXXXXXXXXX+sendWeiter[4,i]) ·
· ( C1 · ps · (1 − verhaeltnis))g
g=0 g ·
g
XXXXXXXXXXXXC ·
1
C
XXXXXXXXXXXX·(1 − ( C1 · ps · (1 − verhaeltnis)))m−g ;
XXXXXXXX own3:=
XXXXXXXXXXXXC · C1 · (1 − C1 )n−1 · (nhelp · (1 − ps))
PEmpfMitNachricht
XXXXXXXXXXXX· g=0
g · EmpfMitNachricht
·
g
XXXXXXXXXXXX·(1 − 1 )EmpfMitNachricht−g ;
C
XXXX end:
XXXX haveMsg:= received+own1+own2+own3;
XXXX s:=C ·
1
C
· (1 − C1 )n−1 · (1 − ((1 − C1 ) +
1
C
XXXXXXXX·(1 − verhaeltnis) · ps)m ) · (nhelp · ps);
XXXX empf:= round(m-haveMsg);
1g
C
A Quellcode
145
XXXX erfolg:=
XXXXXXXXC · (n − nhelp) ·
XXXXXXXX·(1 − ((1 − C1 ) +
1
· (1 − C1 )n−1
C
1
· (1 − verhaeltnis)
C
· ps)m );
XXXX empfaenger[i+1]:=empf-erhieltBeacon;
XXXX print(’haveMsg,s,erfolg, schickte Beacon, eigene Nachricht’);
XXXX print(float(haveMsg),float(s),float(erfolg), float(nhelp· (1-ps)),
XXXXXXXX float(own1+own2+own3));
XXXX sendWeiter[1,i]:=
XXXXXXXXmax(0, nhelp · ps − s − erfolg+ bearbeitetNachricht[1,i]
XXXXXXXX+sendWeiter[4,i]);
XXXX if i<=4 then
XXXXXXXX bearbeitetNachricht[1,i+1]:= haveMsg;
XXXX else
XXXXXXXX msg:= msg+received;
XXXX end:
XXXX print(’Sender mit Nachricht für nächste Runde: ’
XXXXXXXXX.expr2text(round(sendWeiter[1,i])));
XXXX r:= 2:
XXXX while (r<=4) do
XXXXXXXX print(’Runde ’.expr2text(r));
XXXXXXXX n:=round(sendWeiter[r-1,i]+bearbeitetNachricht[r,i]);
XXXXXXXX m:=empfaenger[i+1];
XXXXXXXX if (r=3) then
XXXXXXXXXXXX m:= m+ erhieltBeacon;
XXXXXXXX end:
XXXXXXXX print(’Sender,Empfänger,sendWeiter[r-1,i],
XXXXXXXXXXXXX bearbeitetNachricht[r,i]’);
XXXXXXXX print(n,m, float(sendWeiter[r-1,i]),
XXXXXXXXXXXXXfloat(bearbeitetNachricht[r,i]));
XXXXXXXX received:=
XXXXXXXXXXXXmax(0, C · n · C1 · (1 − C1 )n−1 ·
1j
P
m
1 m−j
XXXXXXXXXXXX m
);
j=0 j · j · C · (1 − C )
XXXXXXXX s:=
XXXXXXXXXXXXmax(0, n · (1 − C1 )n−1 · (1 − (1 − C1 )m ));
A Quellcode
XXXXXXXX empf:= round(m-received);
XXXXXXXX empfaenger[i+1]:=empf;
XXXXXXXX print(float(received),float(s));
XXXXXXXX sendWeiter[r,i]:= max(0, (n − s));
XXXXXXXX if i<=4 then
XXXXXXXXXXXX bearbeitetNachricht[r,i+1]:= max(0, received);
XXXXXXXX else
XXXXXXXXXXXX msg:= msg+received;
XXXXXXXX end:
XXXXXXXX print(’Sender mit Nachricht für nächste Runde: ’
XXXXXXXXXXXXXXX.expr2text(round(sendWeiter[r,i])));
XXXXXXXX r:= r+1:
XXXXXXXX end while:
¯
XXXX empf2:= sender[i];
XXXX empf2:=
XXXXXXXXmax(0, round(empf2-sendWeiter[4,i]
XXXXXXXX-bearbeitetNachricht[1,i]-bearbeitetNachricht[2,i]
XXXXXXXX-bearbeitetNachricht[3,i] -bearbeitetNachricht[4,i]));
XXXX empfaenger[i]:= empf2;
XXXX i:=i+1:
XXXX end while:
¯
roundTime:= roundTime+1:
end while;
¯
print(’Verbleibende Nachrichten:’);
i:=1:
while(i<=5) do
XXXX print(’Regal ’.expr2text(i).’:
XXXXXXXXX verblieben ’.expr2text(sender[i]-empfaenger[i]));
XXXX i:= i+1;
end while:
¯
print(’Angekommene Nachrichten: ’.expr2text(round(msg)));
146
A Quellcode
147
A Quellcode
A.2
Release 3.0 des 1 QK-Protokolls
buffer: { record of
XX up GID : long;
¯
XX down GID : long;
¯
XX uplink buffer full: bit;
¯
¯
XX downlink buffer full: bit;
¯
¯
XX up application data : array [UP APPL LENGTH] of byte;
¯
¯
¯
¯
XX down application data : array [DOWN APPL LENGTH] of byte;
¯
¯
¯
¯
XX up packet id :byte;
¯
¯
XX down packet id :byte;
¯
¯
XX down new NetID :byte;
¯
¯
XX route : array [ROUTELENGTH] of int;
XX route is up :bit;
¯ ¯
XX route is down :bit;
¯ ¯
XX counter hops : byte;
¯
XX counter rounds :byte;
¯
end of record
---- Konstanten ---ROUTELENGTH : 10;
ADJ LENGTH : 10;
¯
UP APPL LENGTH : 6;
¯
¯
DOWN APPL LENGTH : 6;
¯
¯
NO NODE : 65535;
¯
T UPLINK WAIT : T/2;
¯
¯
T SEND : T;
¯
T INIT : 15000;
¯
T RECEIVE : 300;
¯
POWER MSG SEND : 100;
¯
¯
POWER MSG ACK : 120;
¯
¯
POWER MSG BEACON: 80;
¯
¯
---- Variablen ----
148
A Quellcode
B : buffer;
P : packet;
channels :byte;
count maxReceive : byte;
¯
T roundDuration : byte;
¯
Neighbor : array [ADJ LENGTH] of int;
¯
Ack P : ack packet;
¯
¯
NetID : int;
hop distance : real;
¯
T : int;
T SLEEP : int;
¯
P nr : byte;
¯
clear to send : bit;
¯ ¯
drop out of receive loop : bit
¯
¯ ¯
¯
useEqual:byte;
reset ID: byte;
¯
rounds wake;
¯
received reset: bit;
¯
selfFairValue : byte;
foreignFairValue :byte;
actFrequency:byte;
actRound :byte;
i : byte;
j : byte;
k : byte;
149
A Quellcode
150
Wie bereits zuvor erwähnt, wird nach dem Aufwachen direkt in den Zustand Listen gewechselt. Die Abarbeitung des Zustandes Check for new Sensor Data wird in
der neuen Funktion prepareOwnData ausgeführt:
prepareOwnData(){
XX B.uplink buffer full = 1;
¯
¯
XX up application data = get data from application();
¯
¯
¯
¯
¯
XX UP GID = GID;
¯
XX B.hop distance = round(hop distance);
¯
¯
XX B.counter hop= B.counter rounds;
¯
¯
XX if( B.route is down = 0) {
¯
XXXX B.route is up =1;
¯
XXXX B.route[0] = Net ID;
¯
XXXX for i = 1 to ROUTELENGTH {
XXXXXX B.route[i] = NO NODE;
¯
XXXX }
XX }
}
Zur Bearbeitung einer erhaltenen Hopdistanz wird die folgende Funktion genutzt:
checkHop distance(int packet distance){
¯
¯
XXif (P.hop distance < (round(hop distance)-1)){
¯
¯
XXXX hop distance = hop distance -1/3;
¯
¯
XX } else {
XXXX hop distance = (hop distance +P hop distance )/2;
¯
¯
¯
XX}
In der Unterprozedur getChannelNumber wurde die Kanalwahl realisisert. Dabei erfolgt die Wertrückgabe stets in der internen Runde, in welcher gesendet werden
soll. Übergeben wird dann eine Kanalzahl zwischen Null und Zwölf, schließlich werden
hardwaremäßig nur dreizehn Kanäle unterstützt. Bei der Wahl wird berücksichtigt, ob
der Knoten sich in einer geraden oder ungeraden Hopdistanz befindet. Zudem wird für
Empfangsoperationen die entgegengesetzte Kanalnummerierung bei der faktorisierten
geometrischen Verteilung realisiert.
byte getChannelNumber(int hop distance, int round, boolean sending) {
¯
A Quellcode
151
{
XX if ((round ≤ useEqual) OR (round > count maxReceive AND
¯
XXXXXX round ≤ (count maxReceive + useEqual)){
¯
---- Equal Distribution has to be used ---XXXX k= random(channels)/13;
XXXX wait((k · round duration)-1);
¯
XXXX return (k);
XX } else {
XXXX j= getChannelinterval(channels,13);
XXXX if (round(hop distance) mod 2 <> 0) then {
¯
XXXXXX if (send ==true) then {
XXXXXXXX j= (channels/13)-j+1;
XXXXXX }
XXXX } else if (send ==false){
XXXXXX j= (channels/13)-j+1;
XXXX }
XXXX k= random (12);
XXXX wait((j· round duration)-1);
¯
XXXX return (k);
XX }
}
Die Empfangsphase wurde auch verändert, da die Kanalwahl anders funktioniert
und nun die Sendevorgänge in Runden eingeteilt sind. Die Dauer einer Runde ist in
der Variablen roundDuration abgespeichert. Da eine interne Abarbeitungszeit variieren
kann, wird diese Bearbeitungszeit berechnet. Damit wird festgestellt, in welcher Runde
sich der Knoten befindet.
actRound=0;
drop out of receive loop = 0;
¯
¯ ¯
¯
---- receive -while starts ---while (actRound <= count maxReceive AND !drop out of receive loop) do
¯
¯
¯ ¯
¯
XX actFrequency = getFrequencyOfChannel(
A Quellcode
152
XXXXXXXXXXXXXXXXXgetChannelNumber(hop distance, actRound, false));
¯
XX P = listen(actFrequency,T RECEIVE);
¯
XX case P.type of
XXXX uplink:
XXXXXX if (B.uplink buffer full == 0) then {
¯
¯
XXXXXXXX if (round(hop distance) >= P.hop distance) AND (
¯
¯
XXXXXXXX (Ack P.type != waiting) OR
¯
XXXXXXXX (Ack P.sender id != P.sender id) OR
¯
¯
¯
XXXXXXXX (Ack P.received packet = P.packet id) OR
¯
¯
¯
XXXXXXXX (time since(t start) <= T UPLINK WAIT))then {
¯
¯
¯
¯
XXXXXXXXXX t start = now();
¯
XXXXXXXXXX Ack P.type = waiting;
¯
XXXXXXXXXX Ack P.sender id = P.sender id;
¯
¯
¯
XXXXXXXXXX Ack P.received packet = P.packet id;
¯
¯
¯
XXXXXXXXXX clear to send = 0;
¯ ¯
XXXXXXXXXX set sleep time = 1;
¯
¯
XXXXXXXX} else {
XXXXXXXXXX selfFairValue = getValueForFairness(B.counter rounds);
¯
XXXXXXXXXX foreignFairValue = getValueForFairness(P.counter hops);
¯
XXXXXXXXXX if (selfFairValue > foreignFairValue) then {
XXXXXXXXXXXX prepareOwnData();
XXXXXXXXXX } else {
XXXXXXXXXXXX B.counter rounds = B.counter rounds+1;
¯
¯
XXXXXXXXXXXX Ack P.type = ack;
¯
XXXXXXXXXXXX Ack P.received id = P.id;
¯
¯
XXXXXXXXXXXX Ack P.hop distance= round(hop distance);
¯
¯
¯
XXXXXXXXXXXX send(actFrequency,POWER MSG ACK,P);
¯
¯
XXXXXXXXXXXX B.uplink buffer full = 1 ;
¯
¯
XXXXXXXXXXXX B.up application data = P.application data;
¯
¯
¯
XXXXXXXXXXXX B.up ID = P.origin ID;
¯
¯
XXXXXXXXXXXX if (B.route is down == 0) then {
¯ ¯
XXXXXXXXXXXXXX B.route is up = 1;
¯ ¯
XXXXXXXXXXXXXX j = 0;
XXXXXXXXXXXXXX while ((j < ROUTELENGTH) AND (P.route[i] != NO NODE)) do {
¯
XXXXXXXXXXXXXXXX B.route[j] = P.route[j];
XXXXXXXXXXXXXXXX j = j+1;
XXXXXXXXXXXXXX }
XXXXXXXXXXXXXXXX if (j < ROUTELENGTH) then {
A Quellcode
XXXXXXXXXXXXXXXXXX B.route[i] = Net ID;
¯
XXXXXXXXXXXXXXXX }
XXXXXXXXXXXXXX}
XXXXXXXXXXXX }
XXXXXXXXXX }
XXXXXXXX }
XXXX downlink:
XXXXXX if (GID == P.target ID) then {
¯
XXXXXXXX NetID= P.new NetID;
¯
XXXXXXXX Ack P.type = ack;
¯
XXXXXXXX Ack P.sender id = Net ID;
¯
¯
¯
XXXXXXXX Ack P.received packet id = P.packet id;
¯
¯
¯
¯
XXXXXXXX Ack P.received id = P.id;
¯
¯
XXXXXXXX send(actFrequency,POWER MSG ACK,P);
¯
¯
XXXXXXXX deliver data to application(B.down application data);
¯
¯ ¯
¯
¯
XXXXXX } else if (B.downlink buffer full == 0) then {
¯
¯
XXXXXXXX i = 0;
XXXXXXXX k = 255;
XXXXXXXX B.route is down = 1;
¯ ¯
XXXXXXXX while ((i < ROUTELENGTH) AND (P.route[j] != NO NODE) AND
¯
XXXXXXXXXXXX (P.route[j] != Net ID) AND (k == 255)) do {
¯
XXXXXXXXXX k = find in neighborlist(B.route[j]);
¯ ¯
XXXXXXXXXX j = j+1;
XXXXXXXX }
XXXXXXXX j=j-1 ;
XXXXXXXX if (k != 255) AND (P.route[j] != Net ID) then {
¯
XXXXXXXXXX Ack P.type = ack;
¯
XXXXXXXXXX Ack P.sender id = Net ;
¯
¯
¯
XXXXXXXXXX Ack P.received packet id = P.packet id;
¯
¯
¯
¯
XXXXXXXXXX Ack P.received id = P.id;
¯
¯
XXXXXXXXXX send(actFrequency,POWER MSG ACK,P);
¯
¯
XXXXXXXXXX B.downlink buffer full = 1;
¯
¯
XXXXXXXXXX B.down application data = P.application data;
¯
¯
¯
XXXXXXXXXX k = 0;
XXXXXXXXXX while (k < j) do {
XXXXXXXXXXXX P.route[k]=P.route[k];
XXXXXXXXXXXX B.route[k]=P.route[k];
153
A Quellcode
XXXXXXXXXXXX k = k+1;
XXXXXXXXXX }
XXXXXXXXXX while (k < ROUTE LENGTH) do {
¯
XXXXXXXXXXXX B.route[k] = NO NODE;
¯
XXXXXXXXXXXX B.down GID = P.target GID;
¯
¯
XXXXXXXXXXXX P.route[k]= NO NODE;
¯
XXXXXXXXXXXX k = k+1;
XXXXXXXXXX}
XXXXXXXX}
XXXXXX}
XXXX ack:
XXXXXX clear to send = 0;
¯ ¯
XXXXXX drop out of receive loop = 0;
¯
¯ ¯
¯
XXXXXX if (type=uplink AND P.hop distance < (round(hop distance)-1)){
¯
¯
XXXXXXXX hop distance = hop distance -1/3;
¯
¯
XXXXXX }
XXXX beacon:
XXXXXX checkHop distance(P.hop distance);
¯
¯
XXXXXX T NEW = P.T;
¯
XXXXXX add to neighbor list(P.sender id);
¯ ¯
¯
¯
XXXX inquire:
XXXXXX if (P.GID = GID) then {
XXXXXXXX P.received sensor id = P.sensor id;
¯
¯
¯
XXXXXXXX P.type = dump;
XXXXXXXX P.ID = Net ID;
¯
XXXXXXXX P.GID = GID;
XXXXXXXX adjacency list = neighborlist;
¯
XXXXXXXX clear-to send = 1;
¯
XXXXXXXX drop out of receive loop = 1;
¯
¯ ¯
¯
XXXXXX } else { XXXXXXXX clear to send = 0;
¯ ¯
XXXXXX }
XXXX dump:
¯ ¯
XXXXXX drop out of receive loop = 1;
¯
¯ ¯
¯
154
A Quellcode
XXXX reset:
XXXXXX if (((P.GID = GID) OR P.GID= NO NODE))
¯
XXXXXXXXXXXXAND P.reset ID > reset Id) then {
¯
¯
XXXXXXXX Net ID = P.NID;
¯
XXXXXXXX T = P.T;
XXXXXXXX B.uplink buffer full = 0;
¯
¯
XXXXXXXX B.downlink buffer full = 0;
¯
¯
XXXXXXXX B.route is up = 0;
¯ ¯
XXXXXXXX B.route is down = 0;
¯ ¯
XXXXXXXX clear-to send = 0;
¯
XXXXXXXX drop out of receive loop=0;
¯
¯ ¯
¯
XXXXXXXX channels := C;
XXXXXXXX count maxReceive:= maxReceive;
¯
XXXXXXXX hop distance := hop distance+1;
¯
¯
XXXXXXXX useEqual := useEqualProbability ;
XXXXXXXX rounds wake = P.rounds wake;
¯
¯
XXXXXXXX if (P.GID= NO NODE) then {
¯
XXXXXXXXXX received reset =1;
¯
XXXXXXXXXX clear-to send = 1;
¯
XXXXXXXX }
XXXXXX }
XXXX empty:
¯ ¯
XX end of case
XX if (new sensor data available() AND (B.uplink buffer == 0)) then {
¯
¯
¯
¯
XXXX prepareOwnData();
XXXX B.counter rounds=0;
¯
XX }
XX if (uplink buffer full==1) OR (downlink buffer full ==1) then
¯
¯
¯
¯
XXXX drop out of receive loop = 1;
¯
¯ ¯
¯
XX wait(channels/13 · round duration -(now () - t start ) -1);
¯
¯
XX actualRound = (now () - t start) / roundDuration;
¯
}
---- receive -while ends ---Das Sendeverhalten musste natürlich auch bearbeitet werden:
155
A Quellcode
---- send-if-begin ---if (clear to send == 1) then {
¯ ¯
XX} if(received reset ==1) then {
¯
---- received a global reset, send it to others ---XXXX P.type = reset;
XXXX P.T = T;
XXXX P.C = channels;
XXXX P.maxReceive = count maxReceive;
¯
XXXX P.hop distance := round(hop distance);
¯
¯
XXXX P.useEqualProbability= useEqual;
XXXX P.rounds wake = rounds wake;
¯
¯
XXXX t start = now();
¯
---- send-reset-loop starts ------- reset has same power as Ack ---XXXX actFrequency = getFrequencyOfChannel(
XXXXXXXXXXXX getChannelNumber(hop distance, actRound, true));
¯
XXXX send(actFrequency, POWER MSG ACK, P);
¯
¯
XX else if (P.type = dump) then {
XXXX while (actualRound < rounds wake AND uplink buffer full == 1) do {
¯
¯
¯
XXXXXX actFrequency = getFrequencyOfChannel(
XXXXXXXXXXXXXXX getChannelNumber (hop distance, actRound, true));
¯
XXXXXX send(actFrequency, POWER MSG SEND, P);
¯
¯
XXXXXX ++ actualRound;
XXXX }
XX } else if (uplink buffer full == 1) then {
¯
¯
XXXX P.type = uplink;
XXXX P nr = P nr + 1;
¯
¯
XXXX P.packet id = B.up packet id ;
¯
¯
¯
XXXX P.origin GID = B.UP GID;
¯
¯
XXXX P.application data = B.up application data;
¯
¯
¯
XXXX P.counter hops = B.counter hops;
¯
¯
156
A Quellcode
157
---- send-uplink-loop starts ---XXXX t start = now();
¯
XXXX do {
XXXXXX while (actualRound < rounds wake AND uplink buffer full == 1) do {
¯
¯
¯
XXXXXXXX actFrequency = getFrequencyOfChannel(
XXXXXXXXXXXXXXXX getChannelNumber(hop distance, actRound, true));
¯
XXXXXXXX send(actFrequency, POWER MSG SEND, P);
¯
¯
XXXXXXXX ACK P = listen-for-ack(actFrequency);
¯
XXXXXXXX ++ actualRound;
XXXXXXXX if (ACK P.type == ack) AND (ACK P.received id == NetID) AND
¯
¯
¯
XXXXXXXXXXXX (ACK P.received packet id == P.packet id) then {
¯
¯
¯
¯
XXXXXXXXXX uplink buffer full == 0;
¯
¯
XXXXXXXX add neighbor to neighborlist(ACK P.sender id);
¯
¯ ¯
¯
¯
XXXXXXXX checkHop distance(P.hop distance);
¯
¯
XXXXXX }
XXXX }
XX }
XX while (uplink buffer full ==1 OR time since(t start) < T SEND)
¯
¯
¯
¯
¯
---- send-uplink-loop ends ---- if there is still a message in buffer, sending wasn’t sucessfull XXif(uplink buffer full==1) then {
¯
¯
XXXX B.counter hops ++
¯
XXXX hop distance ++;
¯
XX }
---- no dump, no uplink message, but perhaps a downlink message ---XX } else if (downlink buffer full == 1) then {
¯
¯
¯
XXXX ++ actualRound;
XXXX P.type = downlink;
XXXX P nr = P nr + 1;
¯
¯
XXXX P.packet id = B.down packet id;
¯
¯
¯
XXXX P.sender id = Net ID;
¯
¯
A Quellcode
158
XXXX P.target GID = B.downd GID;
¯
¯
XXXX P.application data = down application data;
¯
¯
¯
---- send-downlink-loop starts ---XXXX do {
XXXXXX while (actualRound < rounds wake AND uplink buffer full == 1) do {
¯
¯
¯
XXXXXXXX actFrequency = getFrequencyOfChannel(
XXXXXXXXXXXXXXXXXX getChannelNumber(hop distance, actRound, true));
¯
XXXXXXXX send(actFrequency, POWER MSG SEND, P);
¯
¯
XXXXXXXX ACK P = listen-for-ack(actFrequency);
¯
XXXXXXXX if (ACK P.type == ack) AND (ACK P.received id == NetID) AND
¯
¯
¯
XXXXXXXXXXXX (ACK P.received packet id == P.packet id) then {
¯
¯
¯
¯
XXXXXXXXXX downlink buffer full == 0; XXXXXXXXXX B.route is down = 0;
¯
¯
¯ ¯
XXXXXXXXXX add neighbor to neighborlist(ACK P.sender id);
¯
¯ ¯
¯
¯
XXXXXXXX }
XXXXXX }
XXXX }
XX }
XX while (downlink buffer full ==1 OR time since(t start) < T SEND)
¯
¯
¯
¯
¯
---- send-downlink-loop ends ---XXXX } else {
---- Nothing to send. So let’s send a beacon ---XXXX P.type = beacon;
XXXX P.T = T;
XXXX P.sender id = Net ID;
¯
¯
XXXX P.hop distance = round(hop distance);
¯
¯
¯
---- send-beacon-loop starts ---XXXX actFrequency = getFrequencyOfChannel(
XXXXXXXXXXXX getChannelNumber(hop distance, actRound, true));
¯
XXXX send(actFrequency, POWER MSG BEACON, P);
¯
¯
A Quellcode
XXXX }
XX }
---- send-if-end ---T SLEEP = GetSleepTime(now, hop distance);
¯
¯
---- outer-while-end ----
159
Anhang B
Verzeichnisse
B.1
Literaturverzeichnis
[Ab 70] N. Abramson
The Aloha System - Another Alternative for Computer Communications,
in Fall Joint Computer Conference, AFIPS Conference Proceedings, Vol. 37, pp. 281-285,
1970
[Ak,Su 02] Akyildiz, I. F., W. Su, Y. Sankarasubramaniam und E. Cayirci
Wireless Sensor Networks: A Survey,
in Computer Networks, 38(4):393-422, März 2002
[Aw,Ho 04] Baruch Awerbuch, David Holmer, Herbert Rubens und I.-J. Wang
(Johns Hopkins University), Kirk Chang (Applied Research Telcordia Technologies)
The Pulse Protocol: Sensor Network Routing and Power Saving, 2004
www.cnds.jhu.edu/research/networks/archipelago/publications/AwerbuchMilcom2004-SensorPulse.pdf
[Aw,Ru 04] Baruch Awerbuch, David Holmer und Herbert Rubens, Johns Hopkins University
The Pulse Protocol: Energy Efficient Infrastructure Access,
IEEE 2004
www.ieee-infocom.org/2004/Papers/31 5.PDF
¯
[Bü 93] Thomas Bürger, Technische Universität Clausthal
Network Time Protocol - Ein Zeitservice für Computernetze, Juli 1993
B Verzeichnisse
161
http://ftp.tu-clausthal.de/pub/EXPERT/docs/
DV-info/Network Time Protocol.pdf
¯
¯
[El, Gi 02] Jeremy Elson, Lewis Girod und Deborah Estrin, University of California, Los Angeles
Fine-Grained Network Time Synchronization using Reference Broadcasts,
in Proceedings of the Fifth Symposium on Operating Systems Design and Implementation
(OSDI 2002), Boston, MA, December 2002.
http://lecs.cs.ucla.edu/Publications/papers/broadcast-osdi.pdf
[Fr 03] Friedemann Mattern und Kay Römer, Institut für Pervasive Computing
ETH Zürich
Informatik Spektrum, Springer-Verlag Berlin Heidelberg, 2003
http://www.gi-ev.de/informatik/lexikon/inf-lex-drahtloses-sensornetze.shtml
[Ga,Ku 03] Saurabh Ganeriwal, Ram Kumar und Mani B. Srivastava, University
of California Los Angeles
Timing-sync Protocol for Sensor Networks,
ACM Conference on Embedded Networked Sensor Systems (SENSYS 2003)
http://www.ee.ucla.edu/ saurabh/publications/Sensyspaper03.pdf
[Go 05] Ines Bebea Gonzalez, Universität Paderborn
Topology Control for Mobile Ad Hoc Sensor Networks: Clustering, 7. März 2005
Projektgruppe Large Scale Ad Hoc Networks 2004/2005
[Hae 05] Thomas Haenselmann, Universität Mannheim,
Veranstaltungsseite zur Vorlesung ’Sensornetze’ im Wintersemester 2004/2005
http://www.informatik.uni-mannheim.de/pi4/lectures/ws0405/sensornetze/
[Ha,Gr 04] Matthias Handy, Frank Grassert, Dirk Timmermann, Universität Rostock
DCP: A New Data Collection Protocol for Bluetooth-Based Sensor Networks,
EUROMICRO Symposium on Digital System Design, S. 566-573, ISBN: 0-7695-2203-3,
Rennes, Frankreich, 2004
http://www-md.e-technik.uni-rostock.de/veroeff/handym dsd2004.pdf
¯
[He,Ba 00] Wendi Rabiner Heinzelman, Anantha Chandrakasan und Hari Bala-
B Verzeichnisse
162
krishnan, Massachusetts Institute of Technology, Cambridge
Energy-Efficient Communication Protocol for Wireless Microsensor Networks,
Hawaii International Conference on System Sciences, 4-7 Januar 2000
http://www-mtl.mit.edu/ wendi/papers/hicss00.ps
[He,Ch 00] Wendi Rabiner Heinzelman, Anantha Chandrakasan und Hari Balakrishnan, Massachusetts Institute of Technology, Cambridge
Energy-Efficient Communication Protocol for Wireless Microsensor Networks,
33. Hawaii International Conference on System Sciences 2000
hsnl.ee.tku.edu.tw/WLAN/Chuang/chuang–0227.ppt
[Ho 04] Prof. Dr. Dieter Hogrefe, Georg-August-Universität Göttingen
Mobile Ad Hoc Netze
in der Veranstaltung Mobilkommunikation 2 im Wintersemester 2004/2005
http://user.informatik.uni-goettingen.de/ elanmk/mk2 ws0405/pdf/MobileAdHoc.pdf
¯
[In,Go
00]
Chalermek
Intanagonwiwat,
Ramesh
Govindan,
Deborah
Estrin,
USC/Information Sciences Institute
Directed diffusion: A scalable and robust communication paradigm for sensor networks,
in Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCOM 2000), August 2000, Boston, Massachussetts.
http://lecs.cs.ucla.edu/ estrin/papers/diffusion.ps
[Jo, Ma] David B. Johnson David A. Maltz, Carnegie Mellon University
Dynamic Source Routing in Ad Hoc Wireless Networks
www.ics.uci.edu/ atm/adhoc/paper-collection/johnson-dsr.pdf
[Ka 90] P. Karn,
’MACA- a New Channel Access Method for Packet Radio’,
in ARRL/CRRL Amateur Radio 9th Computer Networking Conference,1990
[Ka 05] Universität Karlsruhe
Veranstaltungsseite zum Seminar ’Algorithmen für Sensornetze’ im Wintersemester
2004/2005
http://i11www.informatik.uni-karlsruhe.de/teaching/WS 0405/sensornetze/
¯
[Kr 03] Tobias Krauer,
Zeitsynchronisation in Sensornetzen
B Verzeichnisse
163
in Seminar Verteilte Systeme: Sensornetze, Sommersemester 2003
http://www.vs.inf.ethz.ch/edu/SS2003/DS/reports/05 time report.pdf
¯
¯
[Lu,Ko 03] Andreas Lundin, Jon Kolstad, National University of Singapore
Ad
Hoc
Routing,
13.April
2003
www.comp.nus.edu.sg/˜cs4274/termpapers/0203-
II/group24/paper.pdf
[Ma,Fr 02] S. R. Madden, M. J. Franklin, J. M. Hellerstein und W. Hong
’TAG: A Tiny AGgregation Service for Ad-hoc Sensor Networks’, OSDI Conference, 2002.
[Ma 02] Magistratsabteilung 36, Feuerpolizei und Veranstaltungswesen Wien
Verkaufsstätten-Richtlinie der MA 36, 01.03.2002
www.wien.gv.at/ma36/pdf/verkaufsstaettenrichtlinie.pdf
[Mu 04] Daniel Mutschler, Fachhochschule Gießen
Seminararbeit Ubiquitous Computing - Drahtlose Sensornetze, März 2004
homepages.fh-giessen.de/˜hg51/Seminar-0304/mutschler-seminar.pdf
[Pe, Bh] Charles E. Perkins (IBM, Watson Research Center ), Pravin Bhagwat
(Computer Science Department)
Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile
Computers
www.cs.umass.edu/ mcorner/courses/691M/papers/perkins.pdf
[Pe, Ro 00] Charles E. Perkins (Sun Microsystems Laboratories), Elizabeth M.
Royer (University of California, Santa Barbara)
Ad hoc On-Demand Distance Vector Routing,
in Ad hoc Networking, Addison- Wesley, 2000
www.cs.brown.edu/courses/cs295-1/aodv.pdf
[Ra, Mi] Srajan Raghuwanshi, Amitabh Mishra, Bradley Department of Electircal
and Computer Engineering, Virginia - USA
An Approach Towards Improved Energy-efficiency in Wireless Sensor Nets
filebox.vt.edu/users/sraghuwa/srajan RAWCON 2003.pdf
¯
¯
[Ro 75] L. G. Robert,
ALOHA packet system with and without slots and capture
in Computer Communication Rev., vol.5, no.2, April 1975
B Verzeichnisse
164
[Rö 01] Kay Römer, ETH Zürich
Time Synchronization in Ad Hoc Networks,
in Proceedings of MobiHoc 2001, ACM, October 2001
www.vs.inf.ethz.ch/publ/papers/mobihoc01-time-sync.pdf
[Rö 04] Kay Römer, ETH Zürich
Zeitsynchronisation in Sensornetzen, 3. Summer School - Schloss Dagstuhl, 12-15.
September 2004
http://www.ibr.cs.tu-bs.de/events/summerschool2004/roemer-time.pdf
[Rö, Bl 05] Kay Römer, Philipp Blum und Lennart Meier, ETH Zürich
Time Synchronization and Calibration in Wireless Sensor Networks,
in Ivan Stojmenovic (Ed.): Wireless Sensor Networks, John Wiley and Sons, 2005
www.vs.inf.ethz.ch/publ/papers/wsn-time-book.pdf
[Sa 04] Christopher M. Sadler, Pei Zhang, Stephen Lyon, Margaret Martonosi,
Princeton University
Hardware Design Experiences in ZebraNet, SenSys 2004, Baltimore, MD, 5 November
2004
http://www.princeton.edu/ csadler/ZNet HW Sensys04.ppt
¯
¯
[Sch 04] Christian Schindelhauer, Ulrich Hilleringmann, Universität Paderborn
Entwicklung
eines
drahtlosen
energieeffizienten
Sensornetzwerkes
zur
Füllstandbestimmung am Beispiel eines Regalsystems im Einzelhandel, Paderborn
2004
Dateiname: Sch 04 Hardware.pdf
¯ ¯
[Sch 03/04] Christian Schindelhauer, Michelle Jing Liu, Stefan Rührup, Klaus
Volbert, Universität Paderborn
Sensor Networks using Sleeping Routers, Paderborn März 2004
Dateiname: Sch 0304 VortragÜberblick.pdf
¯
¯
[Sch 04/04] Christian Schindelhauer, Universität Paderborn
1QK - Sensor Network Protocol - Version 2.3, Paderborn 21.04.04
Dateiname:Sch 0404 Main-spec-sensor.pdf
¯
¯
[Sch 04-R02] Christian Schindelhauer, Universität Paderborn
B Verzeichnisse
165
Specification Document Network Layer - Sensor Part of the 1 QK-Protocol, Release 2.0,
Paderborn 21.03.2004
Dateiname: Sch 04-R02 SENSOR-SPEC.rtf
¯
¯
[Sch 05] Christian Schindelhauer, Universität Paderborn
Abschätzungen zu Wahrscheinlichkeitsverteilungen, Paderborn 28.03.2005
Dateiname: Sch 05 Abschaetztungen.pdf
¯ ¯
[Sen 05] Senets Project, Universität Rostock
Vorstellungsseite des Projektes, 2005
http://rtl.e-technik.uni-rostock.de/˜bj/software/senets/index.php?id=routing
[Si,Ra 99] Suresh Singh (Oregon State University), C.S. Raghavendra (Aerospace
Corporation)
PAMAS - Power Aware Multi-Access protocol with Signalling for Ad Hoc Networks, 1999
http://citeseer.ist.psu.edu/157040.html
[Ti 04] TinyOS, UC Berkeley
Mission Statement, 2004
http://www.tinyos.net/special/mission
[Va, Ch] Prof. Pravin Varaiya, Dr. Chin-Woo Tan, UC Berkeley
TinyOS sensor network for detecting vehicles
http://path.berkeley.edu/˜singyiu/singyiu/resume/projects/tinyos.htm
[Wa 01] Warneke, B., M. Last, B. Leibowitz und K. S. J. Pister
Smart Dust: Communicating with a Cubic-Millimeter Computer,
in IEEE Computer Magazine, 34(1):44-51, Januar 2001
[We 04] Aline Wetjen, Brandenburgische Technische Universität Cottbus
Dynamic Source Routing, im Wintersemester 2004/2005
www.ihp-ffo.de/systems/lv/ws0405/AW Text.pdf
¯
[Wi 04] Simon Wilkinson
Routing in Mobile Ad Hoc Networks, Frühling 2004
www.site.uottawa.ca/ kuruvila/Site 09/Presentations/Final 5 Routing.ppt
¯
¯¯
[Wo 04] Prof. Dr. rer. nat. Bernd E. Wolfinger, Universität Hamburg
B Verzeichnisse
166
Veranstaltung “Datenkommunikation und Rechnernetze“ im Wintersemester 2004/2005
www.informatik.uni-hamburg.de/TKRN/world/abro/DKR/DKR1.pdf
[Ya 05] Yuhan Yan, Universität Paderborn
Time synchronization in sensor network, März 2005
[Yu 05] Jianchi Yu, Universität Paderborn
Routing Protocols for Wireless Sensor Networks, 28.02.2005,
[Zh, Sa 04] Pei Zhang, Christopher M. Sadler, Stephen A. Lyon und Margaret
Martonosi, Princeton University
Hardware Design Experiences in ZebraNet, Proceedings of SenSys 2004, November 2004
http://www.princeton.edu/ csadler/sensys04.pdf
B.2
Glossar
FSK (Frequency Shift Keying)
FSK ist eine beliebte Methode zur drahtlosen Übermittlung digitaler Signale. Es wird
vor allem im Betrieb von Funkfernschreibern eingesetzt(RTTY). Die meisten Transceiver
unterstützen einen FSK Regler, um ein klares und stabiles RTTY Signal zu erzeugen.
Manchester Codierung
Serielle Übertragungsmethode für Bits, die dem Empfänger die Synchronisation mit dem
Sender ohne externes Taktsignal ermöglicht.
Die einfachste Methode, Bits zu signalisieren, besteht darin, für ein 1-Bit eine bestimmte
Periode lang ein High-Signal (z.B. hohe Spannung) und für ein 0-Bit ein Low-Signal (z.B.
niedrige Spannung) zu verwenden. Wenn jedoch mehrere gleiche Bits hintereinander
verschickt werden, hat der Empfänger keine Möglichkeit, Anfang und Ende der einzelnen
Bits zu erkennen.
Die Manchester Kodierung teilt daher jede Bitperiode in zwei Hälften und stellt
sicher, daß immer ein Wechsel des Signals in der Mitte der Bitperiode stattfindet. So
ist der Empfänger in der Lage, sich mit dem Sender zu synchronisieren. Siehe dazu
http://www.it-administrator.de/lexikon/manchester kodierung.html
¯
B Verzeichnisse
167
Flash-Speicher
Flash-Speicher sind digitale Speicher(-Chips). Die Bytes können dabei einzeln adressiert
und gelesen werden. Bytes können einzeln geschrieben werden. Das Löschen einzelner
Bytes ist jedoch nicht möglich. Will man Speicherwerte löschen, muss ein ganzer
Sektor (meistens ein Viertel, Achtel, Sechzehntel usw. der Gesamtspeicherkapazität)
gelöscht werden. Zum Schreiben auf den Flash-Speicher, Löschen einzelner Sektoren
bzw. Löschen des gesamten Speichers müssen spezielle Kommandos (z.B. eine so genannte Unlock-Sequenz) an den Flash-Speicher geschrieben werden. Das verhindert das
unbeabsichtigte, ßufällige”Beschreiben oder Löschen des Speichers. Im Gegensatz dazu
kann bei EEPROMs jedes Byte auch einzeln gelöscht werden. Flash-Speicher haben eine
begrenzte Lebensdauer die in einer maximalen Anzahl an Lösch-Zyklen angegeben wird
(ca. 100.000 Zyklen).
Schlafphase
Die Stationen sind im Standby-Betrieb. Es erfolgt keine Aktionen bis der Timer einen
gewissen Zeitpunkt erreicht hat. Durch ein Interrupt wird dann die Station wieder in
Betrieb genommen und nimmt Aktionen vor.
Kanal
Frequenzbereich zum Senden oder Empfangen von Signalen
B Verzeichnisse
168
Abbildungsverzeichnis
1.1
Beispiel eines Sensorknotens, Quelle: [Va, Ch] . . . . . . . . . . . . . . . .
3
1.2
Kommunikation im ZebraNet, Quelle: [Sa 04, S.2] . . . . . . . . . . . . . .
7
1.3
Zebra mit Halsmanschette, Quelle: [Zh, Sa 04, S.9] . . . . . . . . . . . . . .
8
1.4
Sensorknoten der Artikelgruppe ’Cigaret’, In Anlehnung an [Sch 03/04, S.2]
9
2.1
Sensorknoten zur Erfassung des Warenbestandes, Quelle: [Sch 04, S.2] . . . 13
2.2
Kommunikation über Regale im Supermarkt, Quelle: [Sch 03/04, S.4] . . . 15
2.3
Virtuelle Regale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4
Visualisierung der Regalbegriffe . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5
Senkrechte Anordnung der Regale zum Server . . . . . . . . . . . . . . . . 20
2.6
Querstehende Regale zum Server . . . . . . . . . . . . . . . . . . . . . . . 20
2.7
Überschneidungen vom Sendebereich . . . . . . . . . . . . . . . . . . . . . 21
2.8
Visualisierung der Dreiecksberechnung . . . . . . . . . . . . . . . . . . . . 22
2.9
Streckenverhältnisse der senkrechten Regalanordnung . . . . . . . . . . . . 24
2.10 Regalproportionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1
Verhalten in der Round-Time, Quelle:[Sch 03/04, S.12] . . . . . . . . . . . 31
3.2
Zustandsübergänge, Quelle:[Sch 04/04, S.6] . . . . . . . . . . . . . . . . . . 32
3.3
Aktivitätendiagramm zu Process Packet, Quelle:[Sch 03/04, S.10] . . . . . 33
3.4
Das hidden terminal problem, Quelle:[Si,Ra 99, S.2] . . . . . . . . . . . . . 34
3.5
Verlauf von Hilfsvariablen M und der EPD, Quelle:[Sch 03/04, S.17] . . . . 36
3.6
Prepare Uplink Packet From Buffer, Quelle:[Sch 03/04, S.19] . . . . . . . . 39
3.7
Das OSI Referenzmodell, in Anlehnung an Quelle:[CR 00, S.9] . . . . . . . 44
ABBILDUNGSVERZEICHNIS
170
3.8
Schnittstellen der Ebenen, Quelle:[Sch 03/04, S.2] . . . . . . . . . . . . . . 46
3.9
Beispiel AODV, in Anlehnung an Quelle:[Ho, S.8f] . . . . . . . . . . . . . . 54
3.10 Attribut-Wert-Paare, Quelle:[In,Go 00, S.3] . . . . . . . . . . . . . . . . . . 58
3.11 Periodische interest-Nachricht eines sinks, Quelle:[In,Go 00, S.4] . . . . . . 59
3.12 Ablauf von Direct-Diffusion, Quelle:[In,Go 00, S.4] . . . . . . . . . . . . . . 60
4.1
Präzisionsverbesserung der Group Dispersion, Quelle:[El, Gi 02, S.8] . . . . 66
4.2
MultiHop-Synchronisation, Quelle:[El, Gi 02, S.12] . . . . . . . . . . . . . . 67
4.3
Allgemeines
Modell
für
die
MultiHop-Synchronisation,
Quelle:[El, Gi 02, S.14] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4
Paarweise Synchronisation, Quelle: [Ga,Ku 03, S.4] . . . . . . . . . . . . . 70
4.5
Sende-und Empfangsphasen in der regalweisen Synchronisation . . . . . . . 72
4.6
Verhältnis uplink- und downlink- Treppen . . . . . . . . . . . . . . . . . . 73
4.7
Regalweise Synchronisation mit deutlicherer Überschneidung . . . . . . . . 74
5.1
Gleichverteilung für acht Kanäle . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2
Geometrische Verteilung für acht Kanäle . . . . . . . . . . . . . . . . . . . 92
5.3
1. Vergleichsdarstellung der geometrischen Verteilung und Gleichverteilung
93
5.4
2. Vergleichsdarstellung der geometrischen Verteilung und Gleichverteilung
94
5.5
Faktorisierte geometrischen Verteilung für acht Kanäle und Faktor zwei . . 95
5.6
2. Beispiel einer faktorisierten geometrischen Verteilung . . . . . . . . . . . 96
5.7
Erwartungswert der faktorisierten Verteilungzu 1a) . . . . . . . . . . . . . 102
5.8
Erwartungswert der faktorisierten Verteilung zu 1b) . . . . . . . . . . . . . 103
5.9
Erwartungswert der faktorisierten Verteilungzu 1c) . . . . . . . . . . . . . 104
5.10 Erwartungswert der faktorisierten Verteilung zu 1d) . . . . . . . . . . . . . 105
5.11 Erwartungswert der faktorisierten Verteilung zu 2a) . . . . . . . . . . . . . 107
5.12 Erwartungswert der faktorisierten Verteilung zu 2b) . . . . . . . . . . . . . 108
5.13 Erwartungswert der faktorisierten Verteilung zu 2c) . . . . . . . . . . . . . 109
5.14 Erwartungswert der faktorisierten Verteilung zu 2d) . . . . . . . . . . . . . 110
5.15 1. Beispielverlauf für ansteigenden Streckungsfaktor . . . . . . . . . . . . . 111
ABBILDUNGSVERZEICHNIS
171
5.20 1. Beispiel der Erfolgsquote für ansteigenden Streckungsfaktor . . . . . . . 115
5.23 1. Vergleich der faktorisierten geom. Verteilung und der Gleichverteilung . 117
5.26 Aufgabe der disjunkten Sendebereiche der einfachen Variante . . . . . . . . 120
5.27 Regalweise Synchronisation mit vielen Sendephasenüberschneidungen . . . 121
6.1
Visualisierung des Nachrichtenstaus - Ausgangsposition . . . . . . . . . . . 125
6.2
Visualisierung des Nachrichtenstaus - Erste Sendephase . . . . . . . . . . . 125
6.3
Visualisierung des Nachrichtenstaus - Nach der ersten Sendephase . . . . . 126
6.4
Visualisierung des Nachrichtenstaus - Vor der zweiten Sendephase . . . . . 126
6.5
Visualisierung des Nachrichtenstaus - Die zweite Sendephase . . . . . . . . 127
6.6
Visualisierung des Nachrichtenstaus - Nach der zweiten Sendephase . . . . 128
6.7
Verlauf der Wahrscheinlichkeitsfunktion für p=0.45 . . . . . . . . . . . . . 129
6.8
Verlauf der Wahrscheinlichkeitsfunktion für p=0.25 . . . . . . . . . . . . . 130
6.9
Weiterleitung mit Wahrscheinlichkeit von 75 Prozent der fremden Nachricht bei Vorliegen einer eigener Nachricht . . . . . . . . . . . . . . . . . . 131
6.10 Darstellung der Wahrscheinlichkeitsfunktion f1(x) . . . . . . . . . . . . . . 132
6.11 f2(x), f3(x), f4(x) und f5(x) mit p=0,25 . . . . . . . . . . . . . . . . . . . . 132
6.12 f2(x), f3(x) f4(x) und f5(x) mit p=0,25 und y im Bereich von Null bis Eins 133
6.13 Visualisierung von f5(x) mit p=0,5 . . . . . . . . . . . . . . . . . . . . . . 133

Diplomarbeit Routing in Sensornetzen (fast) ohne Speicher

Transcrição

Documentos relacionados

Institution Herzog Anton Ulrich-Museum Signatur ADürer AB 3.216H

Institution Herzog Anton Ulrich-Museum Signatur ADürer WB 3.218

Du bist Suchma- schine!

Anleitung Strickliesel VS.indd

PDF herunterladen - Ein Herz für Tiere

HD AUSTRIA CAM CI+

Ein Halfter zum selber basteln

Wireless Rear I Sound Perfekter Sound braucht keine Kabel

Occhi-Knoten 1x1 – international V0.85, 2012

1. Einleitung und Aufgabenstellung - users.etech.haw