Verteilte Sensornetzwerke

Mit Datenaggregation und Sensorfusion

PD Stefan Bosse

Universität Bremen - FB Mathematik und Informatik

1 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 -

Modellierung von Sensornetzwerken - Teil 2: Interferenzmodelle

Um Algorithmen für Sensornetzwerke zu entwickeln und mathematische Korrektheits- und Leistungsnachweise zu liefern, werden Modelle für verschiedene Aspekte von Sensornetzwerken benötigt.

Teil 1: Verbindungsmodelle

Teil 2: Interferenzmodelle

Teil 3: Algorithmen

2 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Überblick

Überblick

Wichtige Fragestellungen

Wann können Sensorknoten kommunizieren?

Wann und warum stören sich Sensorknoten gegenseitig?

Was ist Interferenz, wie kann man sie modellieren?

Wie können Störungen minimiert werden?

3 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Interferenz

Interferenz

In drahtlosen Netzwerken wird das Kommunikationsmedium gemeinsam genutzt und Übertragungen sind Interferenzen (Überlagerungen mit Störung) ausgesetzt.
Konkret ist ein Knoten u möglicherweise nicht in der Lage, eine Nachricht eines benachbarten Knotens v korrekt zu empfangen, da in der Nähe eine gleichzeitige Übertragung stattfindet.
Interferenz == Überlappung hängt ab von vier Räumen:
- Ortsraum
- Leistungsraum (Elektromagnetisch)
- Frequenzraum
- Zeitraum
In gewissem Sinne erklärt ein Interferenzmodell, wie sich gleichzeitige Übertragungen gegenseitig blockieren.

4 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Interferenz

Interferenz ist ein schwieriges Phänomen mit vielen schwer zu erfassenden Eigenschaften. Ein Signal kann sich beispielsweise aufgrund einer Mehrwegausbreitung selbst stören (z. B. eine direkte Pfadunterbrechung mit einem längeren Pfad, der ein Objekt reflektiert).

Interferenz kann zu einer Veränderung des digitalen Inhalts einer Nachricht M führen.
- Probabilistischer Prozess!
- Je länger die Nachricht, desto höher die Wahrscheinlichkeit einer Veränderung
- Veränderung kann erkannt werden (oder nicht)
- Veränderung kann korrigiert werden (oder nicht)
- Wiederholung der Nachrichtenübertragung (Retransmission)

5 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Leistungs- und Ortsraum

Leistungs- und Ortsraum

Einzelne drahtlose Kommunikationsknoten senden mit einer bestimmtem (wenn auch veränderlichen) Sendeleistung P(x) an einem bestimmten Ort x, wobei in mobilen Netzwerken x(t) gilt.
Die Sendeleistung kann durch Randbedingungen von Knoten zu Knoten unterschiedlich sein:
- Maximale Sendeleistung
- Energiesparmodus bzw. Engeriemangel
- Anpassung an aktuelle Kommunikation und Verbindungen (Minimierung Interferenz)
- Antennenausrichtung! (anisotrope Abstrahlungscharakteristik)

6 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Leistungs- und Ortsraum

Netzwerk mit heterogenen Übertragungsbereichen. Zum Beispiel spart der Knoten u ganz links Energie und reduziert Störungen, indem er nur einen kleinen Leistungspegel verwendet.

7 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Signal-to-Interference Plus Noise (SINR) Modell

Signal-to-Interference Plus Noise (SINR) Modell

Sei P_r die von einem (anderen) Knoten v_r empfangene Signalleistung und I_r die von anderen Knoten erzeugte Interferenzleistung. Sei P_e die Umgebungsrauschleistung.
Dann empfängt ein Knoten v_r eine Übertragung genau dann, wenn

$\frac{{P}_{{r}}}{{{P}_{{e}}+{I}_{{r}}}}\ge\beta$

β eine kleine Konstante (abhängig von der Hardware) und bezeichnet das minimale Signal-Interferenz-Verhältnis, das erforderlich ist, damit eine Nachricht erfolgreich empfangen werden kann.

8 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Signal-to-Interference Plus Noise (SINR) Modell

Der Wert der empfangenen Signalleistung P_r ist eine abnehmende Funktion des Abstandes d(v_s, v_r) zwischen Sender v_s und Empfänger v_r.
Genauer gesagt wird die empfangene Signalleistung fällt mit dem Abstand d(v_s, v_r) ab als

$\frac{{1}}{{\left({d}{\left({v}_{{s}},{v}_{{r}}\right)}\right)}^{α}}$

Der sogenannte Pfadverlustexponent α ist eine Konstante zwischen 2 und 6 und hängt von den äußeren Bedingungen des Mediums sowie von der genauen Sender–Empfänger-Distanz ab.

9 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Signal-to-Interference Plus Noise (SINR) Modell

Sei P_i die Sendeleistung des Knotens v_i.
Eine von einem Knoten v_s ∈ V übertragene Nachricht wird von einem Knoten v_r erfolgreich empfangen, wenn gilt:

$\frac{{\frac{{P}_{{s}}}{{\left({d}{\left({v}_{{s}},{v}_{{r}}\right)}\right)}^{α}}}}{{{P}_{{e}}+\sum_{{{v}_{{i}}\in{V}\ne{v}_{{s}}}}{\left(\frac{{P}_{{i}}}{{\left({d}{\left({v}_{{i}},{v}_{{r}}\right)}\right)}^{\alpha}}\right)}}}\ge\beta$

10 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Signal-to-Interference Plus Noise (SINR) Modell

Im SINR-Modell empfängt ein Knoten eine Übertragung korrekt, wenn die empfangene Signalleistung - die von der Sendeleistung und dem Abstand zwischen Sender und Empfänger abhängt - im Vergleich zur Signalleistung gleichzeitiger (störender) Übertragungen und dem Umgebungsrauschpegel groß genug ist.

Manchmal wird eine Variation dieses SINR-Modells in der Literatur verwendet. Es hat eine zusätzliche Anforderung: Für einen erfolgreichen Empfang muss die empfangene Signalleistung einen minimalen Schwellwert θ überschreiten, d.h. P_r ≥ θ.
In vielen Situationen kann ein solcher Schwellwert implizit durch den Umgebungsrauschleistungspegel P_e angegeben werden.

11 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Funkregionen

Funkregionen

Übertragungsbereich (Transmission): Kommunikation mit niedriger Fehlerrate möglich

Erkennungsbereich (Detection): Erkennung des Sendesignals möglich, aber Kommunikation aufgrund hoher Fehlerrate nicht möglich

Interferenzbereich: Signal wird nicht eindeutig erkannt, und überlagert sich zum allgemeinen Empfangsrauschen (und kann stören)

Störung: Fehlerhafte oder nicht empfangene Nachricht.

12 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Funkregionen

Empfangs, Interferenz- und Erkennungsbereiche bei drahtloser Kommunikation

13 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Sendeleistungsmodelle

Sendeleistungsmodelle

CONST: Alle Knoten verwenden die gleiche konstante Sendeleistung.

DIST: Der Leistungspegel hängt vom Abstand d zwischen Sender und Empfänger ab. Konkret ist die Sendeleistung durch c d^α für α ≥ 2 und die Konstante c> 0 gegeben.

GEN: Am Sender wird ein allgemeiner (oder beliebiger) Leistungspegel angenommen, der sich im Laufe der Zeit ändern kann. Die vorherige Abbildung zeigt ein Netzwerk, in dem jeder Knoten einen anderen Leistungspegel hat.

14 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Inteferenzmodelle

Inteferenzmodelle

SUM: Alle störenden Übertragungen werden berücksichtigt.

ONE: Nur die schlechteste (oder am nächsten gelegene) störende Übertragung ist wichtig.

NULL: Reine Konnektivitätsmodelle, die Interferenzaspekte nicht berücksichtigen

15 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - UDG mit Distanzinterferenz (UDI)

UDG mit Distanzinterferenz (UDI)

Knoten sind arbiträr in der Ebene angeordnet.Zwei Knoten können genau dann direkt kommunizieren, wenn ihr euklidischer Abstand höchstens 1 beträgt, und wenn der Empfänger nicht durch einen dritten Knoten mit einem euklidischen Abstand kleiner oder gleich einer konstanten R ≥ 1 gestört wird.

Oft wird die Konstante R des UDI-Modells so approximiert, dass Interferenzen auf einen Parameter der UDG reduziert werden können.
Es wird angenommen, dass nur die k-Nachbarschaft eines Empfängers u diesen stören kann. Dies ist eindeutig eine starke Vereinfachung, da in einem UDG ein (k + 1)-Nachbar nahe am Empfänger sein kann.

16 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - UDG mit Distanzinterferenz (UDI)

Das UDI-Modell hat zwei Radien: einen Übertragungsradius (Länge 1) und einen Interferenzradius (Länge R ≥ 1). In diesem Beispiel kann Knoten v keine Übertragung von Knoten u empfangen, wenn Knoten x gleichzeitig Daten an Knoten w überträgt - obwohl v nicht an x angrenzt

17 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - UDG mit Hop-Interferenz (UHI)

UDG mit Hop-Interferenz (UHI)

Knoten befinden sich an beliebigen Positionen in ℝ². Zwei Knoten sind genau dann benachbart, wenn ihr euklidischer Abstand höchstens 1 beträgt. Zwei Knoten können genau dann direkt kommunizieren, wenn sie benachbart sind und wenn in der k-Nachbarschaft des Empfängers (in dem UDG) kein gleichzeitiger Sender vorhanden ist.

Es ist zu beachten, dass das UHI—Modell — für jedes k - manchmal Interferenzbeiträge übersieht, die das UDI berücksichtigen würde, das Gegenteil jedoch nicht gilt.

18 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - UDG mit Hop-Interferenz (UHI)

Beispiel, bei dem UHI fehlschlägt: Die Knoten v₁ und v_k+2 sind durch einen Pfad von k + 1 Knoten getrennt, befinden sich jedoch in der Nähe (Abstand 1 + ε). Somit können gleichzeitige Übertragungen der Knoten v₂ und v_k+2 bei v₁ trotz ihrer großen Knoten-Entfernung stören

19 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Konkurrentes UDI

Konkurrentes UDI

Das UDI Modell kann wie folgt "quasifiziert" werden:

Wenn zwei Knoten näher als ein gegebener Schwellwert R₁ sind, werden gleichzeitige Übertragungen immer stören; wenn der Abstand größer als ein zweiter Schwellwert R₂ ist, wird es keine Interferenz geben. Wenn der Abstand zwischen R₁ und R₂ liegt, können Übertragungen stören oder nicht.

Diese Modelle sind jedoch oft zu kompliziert, um algorithmisch behandelt zu werden.

20 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Protokollmodell (PM)

Protokollmodell (PM)

Sei u₁, u₂, .. , u_k eine Menge U von Knoten, die gleichzeitig jeweils an andere Empfänger v₁, v₂, ... , v_k ∈ V übertragen (U ∩ V = ∅). Die Übertragung von u_j wird von v_i erfolgreich empfangen, wenn für alle j ≠ i gilt, dass d(u_j, v_i)> λ · d(u_j, v_j), wobei λ ≥ 1 eine gegebene Konstante ist. Das heißt, v_i darf nicht in eine "Schutzzone" um irgendeinen Sender u_j fallen, der einen Faktor (1 + λ) größer als der Sendebereich von u_j ist.

21 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Richtungsmodelle

Richtungsmodelle

Kommunikationsverbindungen können bi- und unidirektional sein
Kommunikationsprotokolle können bi- und unidirektional sein (Beispiel: Request-Reply oder Request-Acknowledge Protokolle)

DIR: Diese Klasse von Interferenzmodellen unterscheidet zwischen Sendern und Empfängern (Interferenzscheiben um Sender herum).

UNDIR: Interferenz entsteht durch ungerichtete Verbindungen (Interferenz "Brezeln" um Verbindungen).

22 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Richtungsmodelle

DIR vs. UNDIR: Links überträgt nur der Sender Daten (Interferenzscheiben um Absender). Auf der rechten Seite gibt es keine Unterscheidung zwischen Sender und Empfänger, und daher entsteht eine Störung durch den gesamten Link ("Brezeln" um Links herum)

23 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Allgemeiner g. Interferenzgraph (GWG)

Allgemeiner g. Interferenzgraph (GWG)

Ein gewichteter Interferenzgraph H sei gegeben. Ein Empfänger v empfängt dann erfolgreich eine Nachricht von einem Sender u, wenn die empfangene Signalstärke (das Gewicht der Verbindung zwischen u und v in H) dividiert durch die Gesamtinterferenz (die Summe oder das Maximum der Gewichte der Verbindungen von gleichzeitig sendenden Knoten mit einem Empfänger v in H) über dem Schwellwert liegt, der durch das Signal-Interferenz-plus-Rausch-Verhältnis gegeben ist.

Das allgemeine gewichtete Graphenmodell ist ziemlich pessimistisch, da es nicht natürliche Netzwerktopologien zulässt.
Auch hier benötigen wir — wie beim BIG Konnektivitätsmodell - ein gewichtetes Graphenmodell, dass die geometrischen Einschränkungen erfasst, ohne zu viele vereinfachende Annahmen zu treffen.
- Auch hier besteht ein Ansatz darin, anzunehmen, dass die Knoten eine Verdopplungsmetrik bilden

24 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Technologien

Technologien

Technologie	Sendeleistung	Reichweite	Kanäle	Bandbreite
Bluetooth	1mW^K3/10mW^K2/100mW^K1	1m^K3/10m^K2/100m^K1	40 (3)	1Mb/s
ZigBee	1-10mW	10-75m	10(UB)+15(OB)	250kb/s
WLAN	100mW-1W	10-100m	14(UB)	100Mb/s
RFID	1-100mW¹	10cm	1	LF 1kb/s, HF 100kb/s
4G Cellular Net.	5W²/50W³	1-5km	1-10/Band	100Mb/s

Beispiele für verschiedene Technologien und ihre Kennzahlen für drahtlose Kommunikation ¹:Energieübertragung, ²:Mobiles Gerät, ³:Basisstation

25 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Mobile Ad-hoc Netzwerke

Mobile Ad-hoc Netzwerke

Mobile Ad-hoc Netzwerke (Sensor und Cellular 3G/4G usw) zeigen besondere Eigenschaften:
1. Der Verbindungsgraph ist dynamisch und räumlich und zeitlich veränderlich
2. Der Ort von Knoten ist veränderlich, daher auch Nachbarschaftseigenschaften
3. Physische Nachbarschaft bedeutet nicht Kommunikation (Sensornetzwerke)
4. Pfade (Kommunikationsrouten) sind veränderlich
5. Interferenz ist dynamisch

26 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Mobile Ad-hoc Netzwerke

Mobile Ad-hoc Sensornetzwerke mit kleinen eingebetteten Sensorknoten

27 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Mobile Ad-hoc Netzwerke

PANA,Tusch,2006 Pfade (Kommunikatiosnrouten) in mobilen ad-hoc Netzwerken

28 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Basisstationen

Basisstationen

Kommunikation in Ad-hoc Netzwerken kann Peer-to-Peer oder mit Master-Slave Architektur via Basisstationen erfolgen

Optimale Anordnung der Basisstationen kann Interferenz minimieren und Abdeckung maximieren.

Benachbarte Funkzellen (Basisstationen) sollten verschiedene Frequenzen verwenden um Interferenz zu vermeiden

29 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Basisstationen

Hexagonale Wabenstruktur (Zellen) ist häufig optimale Abdeckung mit Basisstationen und benötigt nur drei verschiedene Frequenzkanäle f₁,f₂f₃

30 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Mobilität

Mobilität

Wenn Peer-to-Peer Kommunikation genutzt wird ändern sich bei räumlicher Mobilität von Knoten der Verbindungsgraph und Interferenzregionen
Wenn Basisstationen benutzt werden können mobile Knoten mit mehreren Basisstationen beim Übergang zwischen Funkzellen temporär verbunden sein!

Übergang eines mobilen Knotens zwischen zwei Funkzellen mit Basisstationen

31 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Fehlerraten

Fehlerraten

Bisher wurde nur die Interferenz als Störung qualitativ diskutiert.
Die quantititative Bewertung muss Bitfehlerraten berücksichtigen

Bitfehlerraten hängen von SINR und von der Kodierung ab!

32 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Fehlerraten

7 Symbolfehlerrate als Funktion des Signal-Rausch-Verhältnisses (SNR) für vier verschiedene Modulations- / Codierschemata

33 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Simulation

Simulation

In einer experimentellen Aufgabe soll die Kommunikation von mobilen ad-hoc Netzwerken mit einfachen Modellen simuliert werden (mit Hilfe eines Ereignisdiskreten Simulators und Programmierung von Empfangs, Sende- und Routingfunktionen in Lua)

34 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Zusammenfassung

Zusammenfassung

Interferenz der Kommunikation kommt durch Überlagerung von elektromagnetischen Wellen zustande und hängt von räumlichen, zeitlichen, und Frequenzparametern ab

35 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Zusammenfassung

Zusammenfassung

Interferenz der Kommunikation kommt durch Überlagerung von elektromagnetischen Wellen zustande und hängt von räumlichen, zeitlichen, und Frequenzparametern ab

Interferenz in Grapahenmodellen ist nicht einfach zu modellieren

36 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Zusammenfassung

Zusammenfassung

Interferenz der Kommunikation kommt durch Überlagerung von elektromagnetischen Wellen zustande und hängt von räumlichen, zeitlichen, und Frequenzparametern ab

Interferenz in Grapahenmodellen ist nicht einfach zu modellieren

Optimale räumliche Knotenabdeckung kann Interferenz minimieren; aber mobile ad-hoc Netzwerke sind nicht planbar!

37 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Zusammenfassung

Zusammenfassung

Interferenz der Kommunikation kommt durch Überlagerung von elektromagnetischen Wellen zustande und hängt von räumlichen, zeitlichen, und Frequenzparametern ab

Interferenz in Grapahenmodellen ist nicht einfach zu modellieren

Optimale räumliche Knotenabdeckung kann Interferenz minimieren; aber mobile ad-hoc Netzwerke sind nicht planbar!

Häufig bietet nur eine Simulation Einblicke um Kommunikationsstörungen qualitativ und quantitativ zu bewerten

38 / 39

PD Stefan Bosse - DSN - Modul C - Modellierung Teil 2 - Vertiefung

Vertiefung

[1] S. SCHMID and R. WATTENHOFER, “Modeling Sensor Networks,” in Algorithms and Protocols for Wireless Sensor Networks, Springer, 2008.

[2] Guowang Miao, Jens Zander, Ki Won Sung, Slimane Ben Slimane, Fundamentals of Mobile Data Networks

39 / 39