Überblick

Inhalte in diesem Kurs

Einführung des Sensormodells als Datenquelle

Erweiterung des Sensormodells auf Sensornetzwerke, IoT, Edge- und Cloud Computing

Virtualisierung und Netzwerke aus Virtuellen Maschinen (VM)

Kommunikation und Datenaggregation in Sensornetzwerken

Architekturen und Topologien von Sensornetzwerken, Simulation von Netzwerken mit zellulären Automaten und Diskreter Ereignissimulation

Algorithmen und Architekturen der Datenaggregation und Datenfusion

Parallel zu 1-7: Programmierung eines verteilten Sensornetzwerks mit Smartphones, Notebooks, und dem Raspberry Pi, und der Lua Programmiersprache

Formale Grundlagen von verteilten Systemen; Metriken; Effizienz; Skalierung

Begleitet von Übungen um obige Techniken konkret anzuwenden

Vorlesung

2 SWS mit Grundlagen und Live Programming
→ Präsenzunterricht/Synchroner Livestream + Chat
→ Tutorial Videos

Übung

1 SWS mit Programmierung und angewandter Vertiefung → LuaOS und LuaOS WEB mit Online Hilfe Funktion und Einreichungssystem

Voraussetzungen

Grundlegende Programmierfähigkeiten, Grundkenntnisse in Rechnerarchitektur und Netzwerken

Zielgruppen des Kurses

Informatiker, Wirtschaftsinformatiker

Systemingenieure (Systems Engineering)

Produktionstechniker und Logistiker

Elektrotechniker

[tiridifilm/istockphoto.com]

Ziele/Kompetenzen

Die Studenten erwerben/gewinnen/lernen

Verständnis der Grundprinzipien und Architekturen verteilter Sensornetzwerken und Fähigkeit zum Transfer auf technische Systeme, vor allem mit Fokus auf VMs

Verständnis und Fähigkeit der Programmierung mit Synchronisation und Kommunikation einfacher Sensorapplikationen

Verständnis der Probleme und dem Betrieb von verteilten Systemen im Vergleich klassischen Serversysteme (Effizienz, Blockierung, Skalierung, Ressourcenbedarf)

Praktische Kenntnisse der Programmierung und Programmierübungen mit Lua, der PLVM, und LuaOS

Erkenntnisse von Grenzen und Möglichkeiten der Verteilung und die Fähigkeit effiziente Systeme zu entwickeln

Studenten sind am Ende des Kurses in der Lage mit Lua einfache verteilte Sensorapplikation z.B. mit Smartphones zu programmieren und zu analysieren.

Materialien

Die Vorlesungsinhalte (Skript, Folien) werden auf https://edu-9.de unter der Rubrik Lehre zusammengestellt und angeboten. Achtung: Kürzel dsn2k beachten!

Weitere Materialien (Tutorials, Übungen, Software) werden ebenfalls auf https://edu-9.de bereitgestellt

Die Videos sind über https://edu-9.de verfügbar (Video Stream Server)

Interaktion der Teilnehmer findet über einen Wiki statt! (dokuwiki). Dieser ist über https://ag-0.de erreichbar und in den jeweiligen Veranstaltungszeiten auf https://edu-9.de verlinkt.

Es wird noch einen online Chat geben.

Alle weiteren Hinweise und Einführungen (z.B. in Software) auf dem Wiki und StudIP.

Leistungen

Folgende Möglichkeiten einer Prüfungsleistung stehen zur Auswahl:

Mündliche Prüfung

Schriftliche Ausarbeitung zu einer Fragestellung zu dem Thema (Review/Survey)

Die Bearbeitung einer experimentellen Arbeit (Lua) mit kleiner schriftlicher Arbeit (Dokumentation)

Literatur

Vorlesungsskript und Folien

Die Inhalte der Vorlesung werden sukzessive bereitgestellt, das Vorlesungsskript steht im HTML und ebook Format zur Verfügung!

Sensornetzwerke in Theorie und Praxis

Ansgar Meroth, Petre Sora, Springer 2018, ISBN 9783658183868

Distributed Sensor Networks

S. S. Iyengar and R. R. Brooks, CRC Press, 2005

Sensor Technologies - Healthcare, Wellness, and Environmental Applications

Michael J. McGrath, Cliodhna Ní Scanaill, Apress Open, 2014

Lua Scripting Language

Tutorial Points, K. K. Panigrahi, 2016.

Software

lvm

edu-9.de

LuaJit VM mit Multithreading

Ausführung von der Kommandozeile

Wird auch für Live Programming und mit Digitalen Notebooks genutzt

Einsatz auf verschiedenen Hostplattformen : PC, Smartphone, Raspberry Pi, Server, ..

Einsatz auf Betriebssystemen: Windows, Linux, Solaris, MacOS, Android

> lvm parfib.lua
Thread [fe5af458:4] released
Thread [fe5afa00:5] released
{
  1 = 9227465,
  2 = 24157817,
  3 = 63245986,
  4 = 165580141,
  5 = 14930352,
  6 = 39088169,
  7 = 102334155,
  8 = 267914296,
}
686478381
Time 6235 ms

Ausführung Kommandozeile

Konzept

Abbildung 1-1. LVM kann über einen WEB Proxy direkt vom WEB Browser aus benutzt werden

Abbildung 1-2. Das LuaOS bietet die vernetzung von lvm Knoten und die Anbindung an den WEB Browser über die LuaOS WEB IDE

Lokale Datenverarbeitung, Globale Fusion

Es sollen verteilte Systeme betrachtet werden

Typisch in verteilten Systemen sind drei Phasen:

Verteilungsphase von Daten und Aufgaben

Ausführung der Aufgaben

Zusammenführung der Ergebnisse

In verteilten Sensornetzwerken sind die Daten meistens schon inhärent verteilt.

Daher (semi-)autonome lokale Datenverarbeitung mit Reduktion der Sensordaten auf relevante Informationen

Kommunikation und Zusammenführung der reduzierten Informationen

Virtuelle Maschinen

Die Verwendung von virtuellen Maschinen nimmt in der Datenverarbeitung immer mehr zu (Skriptverarbeitung und Abstraktion)

Ein Schwerpunkt liegt in der Verteilung und Parallelisierung von Datenverarbeitung in und mit virtuellen Maschinen

Vor allem kommunizierende Systeme sollen betrachtet werden!

local R = rpc:new()
local ips = {
  "192.168.8.141",
  "192.168.8.142",
  "192.168.8.143",
}
local sensors={}
for i=1,5 do
  local err,reply=R:trans(ips[i],12345,{cmd="get"})
  if (err==nil) then
    sensors[i]=reply.sensor
  end
end

Virtuelle Maschinen und Interpreter

Abbildung 1-3. Interpreter Zyklus: Editieren → Übersetzen → Ausführen

Just-in-Time Compiler

Interpreter können im wesentlichen auf drei Arten (Architekturklassen) implementiert werden:

Direkte Ausführung des Quelltextes (die Nutzereingabe und bereits geschriebene Skripte) (Parse → Execute)

Virtuelle Maschine und Übersetzung des Quelltextes in eine Zwischenrepräsentation die von einer virtuellen Maschine ausgeführt werden kann → Bytecode

Virtuelle Maschine mit Bytecode Übersetzung, Ausführung des Bytecodes, und ausgewählter Übersetzung des Bytecodes in nativen Maschinencode → JIT Compiler!

Virtuelle Maschine: Virtualisierung ≡ Abstraktion und Automatisches Speichermanagement

Beispiele

BASIC: Klasse 1

Python: Klasse 2 (Bytecode)

JavaScript: Klasse 2 (Spidermonkey, WEB Browser) und Klasse 3 (Google Chrome/V8, nodejs)

OCaML: Klasse 2 (und native Codeerzeugung mit Compiler)

Lua: Klasse 2 (Lua) und Klasse 3 (LuaJit/lvm)

Parallelisierung der Datenverarbeitung von VM schwierig, Verteilung hingegen ist prinzipiell möglich.

Abstraktion

Was kann durch eine VM abstrahiert oder virtualisert werden?

Programmiersprachen

Welche Programmiersprachen werden häufig verwendet?

Welche parallelen Programmiersprachen sind bekannt?

Parallele und Verteilte Programmierung mit Lua

In diesem Kurs soll die Programmierung mit der Skriptsprache Lua erfolgen und mit der virtuellen Maschine lvm ausgeführt werden;

Der Lua Quelltext wird durch einen Übersetzer in Bytecode übersetzt der von lvm direkt ausgeführt wird.

Besonderheit: Der Bytecode wird direkt während des Parservorgangs erzeugt (kein AST-IR)

Die LuaJit VM (lvm) unterstützt parallele sowie netzwerkbasierte Datenverarbeitung und das Konzept der Prozessblockierung

Prozesse

Threads

Coroutinen (Fibers)

Kontrollpfadparallelität benötigt i.A. Kommunikation und das Konzept der Blockierung!

Formales Ausführungsmodell: Communicating Sequential Processes (CSP)

Programmfluß = Kontrollfluß + Datenfluß

Parallele und Verteilte Datenverarbeitung: Übergang vom Shared Memory (SM) zum Distributed (Shared) Memory (DSM) Modell!

Verteilte Programmierung mit Lua

/shelllvm

size

rpc

rpc=require('plugins/rpc');

server

local rpcA = rpc:new()
rpcA:getreq('127.0.0.1',12345, function (request)
  local y=1
  print(request)
  case request.cmd of
    "square" => y=request.x*request.x end
    "sqrt"   => y=math.sqrt(request.x) end
    else y=0 end
  end
  return {status='OK',clock=clock(),y=y}
end)
print('RPC Server started on port 12345');

client

local rpcB = rpc:new()
local err,reply = rpcB:trans('127.0.0.1',12345,
  {
    cmd='square',
    x=math.random()
  })
if err then print(err) else print(reply) end
local err,reply = rpcB:trans('127.0.0.1',12345,
  {
    cmd='sqrt',
    x=math.random()
  })
if err then print(err) else print(reply) end

Verteilte Programmierung mit LuaOS und LuaWEB

/luaweb.html"

Labor

Das Labor soll den praktischen Einstieg in verteilte Sensornetzwerke bieten und findet im Kurs und @home statt!

Sensorknoten können Notebooks, Smartphones, und eingebettete Rechner (Raspberry) sein!

Die Sensorknoten werden über das Internet vernetzt

Die Sensoren werden über Schnittstellen angeschlossen (I2C)

Programmierung mit Lua und LVM + LuaOS

Abbildung 1-4. Vernetzung von Rechnern über lvm/LuaOS und Aufbau eines verteilten Sensornetzwerkes

Grundlagen und Anwendungsbereiche

Wo findet man Sensornetzwerke?

Wo liegen die Anwendungsbereiche?

Wie ist die räumliche Ausdehnung von Verteilten Sensornetzwerken?

Metriken und Taxonomie von Sensornetzwerken

Die Sensorevolution

Historisch exponentieller Anstieg der eingesetzten Sensoren und ansteigender Sensordichte

Abbildung 2-1. Alles begann mit einzelnen Sensoren getrennt von der Signalverarbeitung (erst analog, dann digital), zunehmende Kopplung von Analog- und Digitaltechnik, und schließlich Sensornetzwerke (1950-2010)

Verteilte Sensornetzwerke

Datenverarbeitung und Kommunikation unterscheidet sich bei Verteilten Sensornetzwerken grundlegend von klassischer netzwerkbasierter Datenverarbeitung wie das Internet

Abbildung 2-2. (a) Klassische zentralisierte Architektur und zentralen Services und Separation von Sensoren und Datenverarbeitung (b) Dezentrale Sensoren und Datenverarbeitung mit verteilten Services

Services

Ein Service ist eine öffentlich bekannte Schnittstelle um Daten durch Operationen zu erlangen, zu verarbeiten, oder zu speicher.

Welche Services könnte es für sensorische Anwendungen geben?

Anwendungsgebiete

Industrie

Sensornetzwerke in Fertigungs- und Produktionsanlagen, häufig gekoppelt mit Maschinen (Cyber-physical Systems, CPS)

Logistik

Monitoring von Waren und Warenlieferketten, Lagern und Transporteinheiten

Gesundheit (Smart Health)

"Wearables", Sensoren die nahe am Körper eines Menschen getragen werden und biometrische Daten liefern, häufig über ein Smartphone und an Server gekoppelt (Gesundheitaanwendungen)

Verkehr

Sensorische Überwachung von Verkehrsflüssen, häufig mit zentraler Verarbeitung zum Zwecke der Optimierung von Verkehrsflüssen

Georäumliche Überwachung

Überwachung von georäumlichen Veränderung der Umwelt, z.B. Erdbebenüberwachung, Pegelständen und Fließverhalten von Flüssen, Wetter, Klima, Gletscher, Überwachung aus dem Weltall, usw.

Strukturüberwachung

Erfassung von Bauteilveränderungen zur Betriebszeit, z.B. von Maschinen, Eisenbahnen, Flugzeugen, Windkraftflügeln, Brücken, Gebäuden, usw.

MISS

Materialintegrierte intelligente Sensornetzwerke als Unterklasse der Strukturüberwachung, Gesundheitsanwendungen, und Produktsensorierung.

Was fehlt noch?

Gesundheitsbereich

Abbildung 2-3. Szenario einer Gesundheitsanwendung mit Körpersensoren und Einbindung in ein Kommunikationsnetzwerk [1]

Ebenen von Kommunikation und Datenverarbeitung

Abbildung 2-4. Funktionalen Ebenen: Drei horizontale Ebenen (Erfassung, Zusammenführung, Applikation) die durch die gleichen vertikalen Ebenen (Datenverarbeitung und Kommunikation) durchzogen sind [1]

Abbildung 2-5. Die drei vertikalen horizontalen Schichten (Funktionalen Ebenen) können sich über verschiedene Netzwerkbereiche verteilen: Intranet und lokales WLAN Netz (innerhalb von Gebäuden), im und über das Internet, und verbunden mit Cloud Services

Industrielle Sensornetzwerke

Industrielle Drahtlose Sensornetzwerke (IWSN)

[2]

Das sind IWSN Anwendungen in den drei Gruppen:

Umweltsensorik,

Zustandsüberwachung von Maschinen und

Prozessautomatisierung,

die auf den spezifischen Anforderungen der Anwendungsgruppen basieren.

Taxonomie von IWSN

Abbildung 2-6. Taxonomie der drei IWSN Anwendungsbereiche [2]

Abbildung 2-7. Industreille Branchen und Uordnung zu den IWSN Anwendungsbereichen [2]

Zustandsüberwachung von Maschinen

[2]

Abbildung 2-8. Wichtiges Merkmal: Dezentrale aktive Sensoren die die Sensordatenverarabeitung und Informationsberechnung bereits integrieren

Abbildung 2-9. Maschinenüberwachung mittels diskreter Sensoren: Ansicht des Versuchsaufbaus. (a) Gesamtes Motorüberwachungssystem mit WSN. (b) Beschleunigungsmesser, Schwungrad und Massenungleichgewichtsblock. [2]

Materialintegrierte Sensornetzwerke

Häufig sind Sensoren und Elektronik getrennt

Die Sensoren (wie im vorherigen Beispiel) werden appliziert

Es gibt teils hohen Verdrahtungsaufwand Sensor-Elektronik bei hohen Sensordichten

Materialintegrierte Sensornetzwerke (MISS) integrieren alle Bestandteile inklusive Energieversorgung in ein Hostmaterial

Das Hostmaterial ist i.A. gleichzeitig funktionales Material (mechanische Struktur)

Bei gegossenen Betonbauiteilen einfach!

Bei Laminatstrukturen kann die Einbettung zwischen Lagen erfolgen ("System-in-Foil" Verfahren)

Bei Gussbauteilen (vor allem Poylmere) können die Sensorknoten eingegossen werden

Häufig verdrahtete Kommunikation!

Abbildung 2-10. Vollständige Einbettung von Sensoren und Elektronik in folienbasierten Systemen

Abbildung 2-11. Nanowire Kommunikationsstrukturen (Kette von Sensoren)

Intelligente Transport- und Logistikanwendungen

Abbildung 2-12. DSN für automatisches Platzieren und Bewegen von fahrzeugen ("Automatisches Parken")

Smart City

Abbildung 2-13. Verteilte drahtlose Sensornetzwerke können um urbanen Bereich im Smart City Konext eingesetzt werden [3]

Sensoren

Klimatische Größen: Temperatur, Luftfeuchte, Luftdruck, Windgeschwindgekeit

Optische Größen: Licht, Farbe, Dynamik

Chemische und physikalische Luftgrößen: Konzentration von Staub und chemischen Gasen

...

Was fehlt noch?

Verkehrsüberwachung und Steuerung

Abbildung 2-14. Lokale Sensoren nehmen Verkehrsbewegungen auf (Sensing), melden diese Daten an Sammelstellen (Aggregation), die dann schließlich durch zentrale Server verarbeitet werden ⇒ Neu: Auch Fahrzeugsensoren und Smartphones können als mobile Sensoren dienen!

Entwurf und Ziele in industriellen drahtlosen Sensornetzwerken

Parameter

Abbildung 2-15. Wichtige Parameter beim Entwurf von DSN sind Anwendungen: Antwortzeiten, Sensorintervalle, und räumliche Sensordichte [2]

Abbildung 2-16. Wichtige Parameter beim Entwurf von DSN sind die Sensoren: Antwortzeiten, Sensorintervalle, und räumliche Sensordichte [2]

Taxonomie von Sensorntzwerken

Übersicht

Die Taxonomie von (verteilten) Sensornetzwerken unterteilt sich in:

Schichten: Eingabedaten, Berechnung, Kommunikation, Programmierung

Funktion und Implementierung (jeweils)

[3]

Eingabendaten

[3]

Berechnung

[3]

Kommunikation

[3]

Programmierung

[3]

Vertiefende Literatur

[1] V. Ç. Güngör and G. P. Hancke, Eds., Industrial Wireless Sensor Networks - APPLICATIONS, PROTOCOLS, AND STANDARDS. CRC Press, 2013.

[2] M. J. McGrath and C. N. Scanaill, Sensor Technologies Healthcare, Wellness, and Environmental Applications. Apress Open, 2014.

[3] S. S. Iyengar and R. R. Brooks, Distributed Sensor Networks. CRC Press, 2005. (Taxonomie: 33 pp)

[4] S. S. Iyengar and R. R. Brooks, Distributed Sensor Networks - Sensor Networking and Applications. CRC Press, 2013. (Anwendungen: 749 pp)

[5] F. Hu and Q. Hao, Intelligent Sensor Networks. CRC Press, 2013. (Sensor IO: 58 pp (fig 3.3))

Modellierung von Sensornetzwerken (Teil 1)

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: Inferenzmodelle

Teil 3: Algorithmen

Überblick

Wichtige Fragestellungen

Wann sind Sensorknoten logisch benachbart?

Wann sind Sensorknoten räumlich benachbart?

Wann sind Sensorknoten kommunikativ benachbart?

Wann sind Sensorwerte von Sensorknoten physikalisch benachbart (korrliert)?

Was stört und beeinflusst Kommunikation

Welche Algorithmen können in Sensornetzwerken eingesetzt werden (z.B. für Routing)?

In diesem Modul geht es um die Modellierung der Verbindungsstrukuren und Eigenschaften in verteilten Sensornetzwerken

Abbildung 3-1. Überblick über die Verbindungs- und Inferenzmodelle die in diesem Modul eingeführt werden

Sensornetzwerke

Der Hauptzweck der Bereitstellung von Sensornetzwerken ist die Erfassung physikalischer Daten wie Lichtintensität, Schall oder Temperatur.

Um die Daten zu aggregieren (z.B. Berechnung der Mindesttemperatur oder dem Durchschnitt usw.), die an den einzelnen Knoten gespeichert sind - und die somit im Raum verteilt sind - werden Protokolle oder Algorithmen benötigt, die angeben, wie diese Operationen ausgeführt werden.

Beispielsweise müssen Sensorknoten aufgrund der begrenzten Funkkommunikationsreichweite "multihop" miteinander kommunizieren (z.B. Daten sammeln), d.h., die Nachrichten müssen von Zwischenknoten weitergeleitet werden — und daher muss ein Routing-Algorithmus definiert werden, wie Nachrichten über welche anderen Knoten weitergeleitet werden sollen.

Graphen

Graphen und Inferenzmodelle sind Grundlage für die Algorithmen

Referenz (alle Abbildungen, überwiegend alle Modelle) und für die Vertiefung dieses Modules:

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

Da die Topologie eines Sensornetzwerks als Graph betrachtet werden kann, sind Verteilte Sensornetzwerke mit der Graphentheorie modellierbar, deren Sensorknoten die Graphenknoten und drahtgebundene oder drahtlose Verbindungen die Kanten darstellen.

Ein weiterer wichtiger Bestandteil von Sensornetzwerkmodellen ist die Geometrie.

Geometrie kommt ins Spiel, da die Verteilung von Sensorknoten im Raum sowie der Ausbreitungsbereich von drahtlosen Verbindungen normalerweise geometrischen Einschränkungen unterliegt.

Graphen könenn die Kommunikationsstruktur, aber auch Informationsflüsse oder Energieaustausch modellieren!

Modellierung der Kommunikation

Eine erste Modellierungsfrage betrifft in erster Linie die Konnektivität von Sensorknoten:

Bei einer Reihe von Knoten, die im Raum verteilt sind, müssen wir angeben, welche Knoten eine Übertragung eines anderen Knotens empfangen können.

Wenn ein Knoten u im Empfangsbereich von v ist, dann sind u und v benachbart (angrenzend).Bedeutet dass auch räumliche Nähe? (Beispiel Internet)

Die Nachbarschaft kann symmetrisch oder asymmetrisch sein:

Symmetrisch: Wenn u Nachrichten von v empfangen kann, dann auch v von u! ⇒ ungerichtete Kommunikation (bidirektional)

Asymmetrische: Wenn u Nachrichten von v empfangen kann, dann nicht v von u! ⇒ gerichtete Kommunikation (unidirektional)

Die Konnektivität eines Sensornetzwerks wird durch einen Graphen G = (V, E) beschrieben, wobei V (Eckpunkte) die Menge der Sensorknoten und E (Kanten) die Nachbarschaftsbeziehung zwischen Knoten beschreibt.

Das heißt, für zwei Knoten u, v ∈ V,(u, v) ∈ E wenn v ist benachbart zu u.

In einem ungerichteten Graphen gilt, dass wenn (u, v) ∈ E , dann auch (v, u) ∈ E ⇒ Kanten können eher durch Mengen {u, v}∈ E als durch Tupel dargestellt werden.

Graphenmodelle

Einheitsscheibengraph (Unit Disk Graph, UDG)

Allgemeiner Graph (General graph, GG)

Quasi-Einheitsscheibengraph (Quasi Unit Disk Graph, QUDG)

Variationen

Kommunikationsgraph

Ein Kommunikationsknoten kann drei Rollen in einem Sensornetzwerk einnehmen:

Kommunikationsquelle (Sender)

Kommunikationsenke (Empfänger)

Vermittler (Router)

Es wird angenommen dass beanchbarte Knoten eines Verbindungsgraphen G (Konten, zwischen denen eine Verbindung besteht) Nachrichten msg austauschen können.

Direktes Graphenmodell: Nur Knoten die benachbart sind und zwischen denen eine Verbindung (Kante) existiert können Nachrichten austauschen

Indirektes Graphenmodell: Nachrichten können durch Routing auch von einer Quelle zu einer Senke übertragen werden wenn es zwischen den Knoten einen Pfad im Graphen gibt

Einheitsscheibengraph UDG

Sei V ⊂ ℝ² eine Menge von Knoten in der zweidimensionalen euklidischen Ebene. Der euklidische Graph G = (V, E) wird als Einheitsscheibengraph bezeichnet, wenn zwei beliebige Knoten genau dann benachbart sind, wenn ihr euklidischer Abstand höchstens 1 beträgt. Die Kanten sind ungerichtet.

Das bedeutet für beliebige u, v ∈ V gilt:
{u, v}∈ E ⇔ |u, v|≤ 1.

Der Einheitskreis entspricht nicht der physikalischen Verbindung (Funkwellen). Warum nicht? Betrachte folgendes Beispiel.

Das UDG-Modell ist idealistisch: In Wirklichkeit ist Funkkommunikation nicht omnidirektional, und selbst kleine Hindernisse wie Pflanzen können die Konnektivität verändern.

u ist benchbart mit Knoten v (Abstand ≤ 1), aber nicht mit Knoten w (Abstand > 1)

Abbildung 3-2. Unit Disk Graph: Knoten

Gerichteter Einheitsscheibengraph DUDG

Bisher wurde symmetrische (bidirektionale) Verbindung zwischen zwei Knoten u und v angenommen.

Durch physikalische Effekte kann teilweise odewr vollständig die Verbindung undirektional sein

Beispiele sind Up- und Downlinks von Satelliten und Weltraumraketen (Beim Start einer Rakete gibt es in den ersten Minurten praktisch keinen Downlink)

Der unidirektionale Graph G = (V, E) besteht dann aus gerichteten Kanten {u → v} ∈ E oder (u,v) ∈ E

u ist benchbart mit Knoten v (Abstand ≤ 1), aber nicht mit Knoten w (Abstand > 1), und nur undirektionale Verbindung

Abbildung 3-3. Directed Unit Disk Graph: Knoten

Generischer Graph GG

Das UDG Modell ist spezialisiert, bildet aber weder physikalische noch logische Modelle (Internet) ab.

Das GG Modell ist das Kontrastbeispiel

Jeder Knoten u kann mit jedem anderen Knoten v verbunden (benachbart) sein.

Der Verindungsgraph G ist ungerichtet. Sei V ⊂ ℝk eine Menge von Knoten in einem k-dimensionalen Raum. Jedes Knotenpaar {ni, nj} ∈ E ist möglich mit i,j ∈ {1,2,..,N} und N die Anzahl der Knoten.

Die Komplexität eines vollständig verbundenen Graphens ist O(N²)

Während ein UDG zu optimistisch ist, ist das GG oft zu pessimistisch, da die Konnektivität der meisten Netzwerke nicht willkürlich ist, sondern bestimmten geometrischen Einschränkungen unterliegt.

In einigen Anwendungsszenarien kann es jedoch korrekt sein, entweder auf der UDG oder auf der GG zu arbeiten.

In der Tat gibt es Algorithmen, die für die UDG entwickelt wurden und auch in allgemeineren Modellen eine gute Leistung erbringen.

Darüber hinaus sind einige für das GG entwickelte Algorithmen derzeit auch die effizientesten für UDGs

Quasi-Einheitsscheibengraph (QUDG)

Die Knoten befinden sich in ℝ² an beliebigen Positionen. Alle Knotenpaare mit euklidischem Abstand höchstens ρ für einige gegebene ρ ∈ (0, 1] sind benachbart. Paare mit einem Abstand größer als 1 befinden sich niemals im Übertragungsbereich des anderen. Schließlich können Paare mit einem Abstand zwischen ρ und 1 benachbart sein oder nicht.

Für ρ = 1 ein QUDG ein UDG ist und daher gilt: Ein UDG ist ein Spezialfall eines QUDG.

Die Grenze des Nachbarschaftsbereichs kann jetzt anisotrop sein (Polygon statt eines Kreise)

u

Der Knoten

u grenzt immer an den Knoten v 1 ( d ( u , v ₁) ≤ ρ), aber niemals an v ₅ ( d ( u , v ₅) > 1). Alle anderen Knoten können sich im Übertragungsbereich von u befinden oder nicht. In diesem Beispiel grenzt der Knoten u an v ₃ und v ₄, jedoch nicht an v ₂

Abbildung 3-4. Quasi Unit disk Graph aus der Perspektive des Knotens

QUDG Variationen

Das vorherige QUDG gibt nicht genau an, was passiert, wenn der Abstand zwischen ρ und 1 liegt. Es gibt mehrere Optionen.

Man könnte sich beispielsweise vorstellen, dass ein Auswahlprozess wählt, ob sie sich im Übertragungsbereich des anderen befinden oder nicht.

Alternativ kann es eine gewisse Erfolgswahrscheinlichkeit geben, benachbart zu sein: Die entsprechende Wahrscheinlichkeitsverteilung könnte von der Zeit und/ oder Entfernung abhängen.

Zum Beispiel könnte das QUDG verwendet werden, um Rayleigh-Fading zu untersuchen; Das heißt, die Funksignalintensität könnte entsprechend einer Rayleigh-verteilten Zufallsvariablen variieren.

Außerdem ist ein probabilistisches Ein / Aus-Modell sinnvoll, bei dem sich der Zustand eines Links in jeder Runde mit einer bestimmten Wahrscheinlichkeit von gut zu schlecht und umgekehrt ändert.

Während das QUDG für Modellknoten attraktiv sein kann, die in Bereichen mit wenigen Hindernissen eingesetzt werden, ist es für innerstädtische oder gebäudeinterne Netzwerke, in denen Hindernisse nicht ignoriert werden können, nicht sinnvoll: Da ein Knoten möglicherweise mit einem anderen Knoten kommunizieren kann, der Dutzende von Metern entfernt ist, aber nicht mit einem dritten Knoten, der gleich um die Ecke liegt, wäre ρ nahe 0.

Begrenzter Unabhängigkeitsgraph (BIG)

Sei Yr(u) die Menge aller unabhängiger Knoten, die höchstens r Sprünge vom Knoten u (d.h. Knoten der r-Nachbarschaft von u) im Konnektivitätsdiagramm G entfernt sind.

Somit wird eine Menge S ⊂ V von Knoten als unabhängig bezeichnet, wenn alle Knoten in der Menge paarweise nicht benachbart sind; das heißt, für alle u, v ∈ S gilt {u, v} ∉ E.

Graphh G hat eine begrenzte Unabhängigkeit genau dann, wenn für alle Knoten u ∈ G, |Y(u)| = O (poly (r)) (typischerweise |Yr(u)| ∈ O(rc) für eine kleine Konstante c ≥ 2).

Da die Anzahl der unabhängigen Nachbarn in einer Scheibe mit dem Radius r eines UDG höchstens O(r²) beträgt, haben wir die folgende Feststellung:

Das UDG-Modell ist ein Sonderfall des BIG-Modells. In ähnlicher Weise ist, wenn ρ konstant ist, auch ein QUDG ein BIG. BIG bildet die Realität gut ab!

u und v sind durch eine Wand getrennt. Knoten auf der gleichen Seite der Wand sind vollständig verbunden. Aufgrund der Wand kann u zwar einen entfernten Knoten w erreichen, den nahen Knoten v jedoch nicht hören. Solche Situationen können durch den BIG, aber nicht durch den UDG oder den QUDG modelliert werden.

Abbildung 3-5. Knoten

Generalisierter (Q)UDG

Eine Erweiterung der UDG- und QUDG-Modelle besteht darin, Knoten in ℝ³ zu berücksichtigen. Außerdem können die Entfernungen zwischen den Knoten unter Verwendung der Manhattannorm (L1-norm) modelliert werden. In der Manhattan-Norm ist der Abstand zwischen zwei Punkten u = (x₁ , y₁) und v = (x₂ , y₂) in der Ebene gegeben durch d(u, v) = |x₂ − x₁| + |y₂ − y₁|, während in der euklidischen Norm (L2−Norm) der Abstand d(u, v) = √(|x₂ − x₁|² + |y₂ - y₁|²) ist . Alternativ ist auch die Maximalnorm (𝕃∞ norm) beliebt, wobei d(u, v) = max |x₂ − x₁|, |y₂ − y₁|.

Metrische Räume und Einheitskugelräume (UBG)

Ein metrischer Raum definiert Abstände zwischen allen Knotenpaaren und garantiert gleichzeitig Nicht-Negativität, Identität des Ununterscheidbaren, Symmetrie und Dreiecksungleichheit. Eine Verdoppelungsmetrik ist einfach ein metrischer Raum mit einigen zusätzlichen Einschränkungen

(UBG) Für einen Knoten u sei die Kugel Bu(r) die Menge aller Knoten in einem Abstand von höchstens r von u. Es gilt für alle Knoten u und alle r ≥ 0, dass die Kugel Bu(r) von einer konstanten Anzahl von Kugeln mit dem Radius r / 2 abgedeckt werden kann; das heißt, Bu(r) ⊆ Ui=1...c Bui(r / 2), wobei ui beliebige Knoten sind und c eine (normalerweise kleine) Konstante ist. Im UBG-Modell wird angenommen, dass Knoten einen Verdopplungsmetrikraum bilden. Zwei Knoten u und v mit d(u, v) ≤ 1 sind benachbart, wohingegen alle anderen Knoten nicht sind.

r / 2 reichen aus, um alle Knoten in B u( r ) abzudecken; das heißt, B u( r ) = B u1(( r / 2) ∪ B u2 (r / 2) ∪ B u3( r / 2).

Abbildung 3-6. Die euklidische Ebene bildet eine Verdopplungsmetrik. In diesem Beispiel sind die Knoten in ℝ^2^ verteilt, und drei Kugeln mit dem Radius

Es ist möglich, einen UDG mit einem UBG zu modellieren, indem die euklidischen Abstände des UDG verwendet werden und die Knotenpaare verbunden werden, die höchstens eine Entfernung von 1 aufweisen. Darüber hinaus kann sogar ein QUDG mit einem UBG modelliert werden.

Um einen metrischen Raum zu bilden, müssen die Abstände zwischen den Knoten die folgenden Eigenschaften erfüllen: (1) Nicht-Negativität, (2) Identität des Ununterscheidbaren, (3) Symmetrie,und (4) Dreiecks-Ungleichung.

Es gilt:

Ein UDG ist ein UBG,

Ein ungerichteter QUDG mit konstanten ρ isz auch ein UBG.

Ein UBG ist ein BIG

Stern- und Maschennetzwerke

Spezialform des GG/UDG

Sternnetzwerk häufig bei Master-Slave Anwendungen vorzufinden (Senornetzwerke)

Abbildung 3-7. (Links) GG Maschennetzwerk (Rechts) UDG Sternnetzwerk

Gitternetzwerke

Weitere Spezialformen des GG/UDG sind Gitternetzwerke in zwei und drei Dimensionen (oder 1D: Kette und Ring).

Findet man bei fest installierten und eingebetteten Netzwerken

Abbildung 3-8. (Oben) 1D Netzwerk Kette (a) und Ring (b); (Links) 2D Gitternetzwerk mit Nachrichtenvermittlung über Zwischenknoten (Rechts) 3D (Kubus) Gitternetzwerk

Bussysteme

Ein UDG Modell wo in der logischen Netzwerkstruktur alle Knoten übereinander mit gleichen Kreisradius angeordnet sind

Es kann immer nur ein Knoten gleichzeitg senden!

Zu finden bei eingebetteten Netzwerken

Abbildung 3-9. Bussysteme (Links) Allgemeine Busnetzwerktopologie und Transformation in ein gerichtetes sequenzielles Maschenntzwerk (DGG) (rechts) Mit getrennten Daten- und Steuerungsverbindungen und Vermittler (Arbiter)

Abdeckungsoptimierung und Probleme

In Sensornetzwerken ist die Frage ob alle Knoten erreichbar sind wichtig für das Systemverhalten des Senornetzwerkes und die Erfüllung der Erfassungsaufgabe.

Die vollständige Kommunikationsabdeckung in mobilen und ad-hoc Netzwerken ist nicht trivial.

Vielfach kann mit der Graphentheorie, probabilistischen Modellen und Verfahren, und geormetrischen Modellen und Überlegungen eine möglichst hohe Wahrscheinlichkiet erreicht werden, das meistens alle Knoten (wenigstens indirekt) erreichbar sind.

Weitere Faktoren wie Energie und externe Störungen müssen ggfs. auch berücksichtigt werden

Weitere Modellierungsaspekte

Neben Graphen und geometrischen Modellen spielen in drahtlosen Sensornetzwerken weitere Modellierungsaspekte eine wichtige Rolle:

Antennen

Neben omnidirektionalen Antennen gibt es eine breite Palette anspruchsvollerer Antennenmodelle. Zum Beispiel kann ein Knoten eine Richtfunkantenne mit mehr Verstärkung in bestimmten Richtungen haben.

Verbindungsfehler

Jedes graphbasierte Modell kann durch probabilistische Verbdindungen erweitert werden. D.h., es gibt eine zeitlich und geometrisch abhängige Wahrscheinlichkeit, dass eine Verbindung zwischen zwei Knoten u und v zustande kommt.

Kosten

Bei drahtgebundenen Systemen ist der Verbuindungsaufwand ein wesentlicher Paramter (Kosten des Netzwerkes)

Energie

Energieversorgung, Energiemangel, und Störungen in der Energieversorgung haben direkten Einfluss auf die Kommunikation zwischen Knoten.

Zusammenfassung

Die Topologie eines Sensornetzwerkes kann als Graph systematisch und methodisch modelliert werden

Es gibt unterschiedlichen Graphenmodelle die Nachbarschaft (d.h. Fähigkeit zur Kommunikation) beschreiben

Unterschiedliche räumliche Randbedingungen werden berücksichtigt

Teilweise sind die Modelle ineinander transformierbar

Die Graphen können sowohl statische als auch dynamische (mobile und ad-hoc) Netzwerke beschreiben

Die Abdeckung eines geometrischen Raums mit Sensorknoten und Kommunikationsfähigkeit aller Knoten sind zentrale Fragestellungen

Referenzen

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

[2] S. S. Iyengar and R. R. Brooks, Distributed Sensor Networks - Sensor Networking and Applications. CRC Press, 2013. Sensor model: pp 33 (1.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

Ü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?

Interferenz

[7]

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.

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)

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)

u ganz links Energie und reduziert Störungen, indem er nur einen kleinen Leistungspegel verwendet.

Abbildung 4-1. Netzwerk mit heterogenen Übertragungsbereichen. Zum Beispiel spart der Knoten

Signal-to-Interference Plus Noise (SINR) Modell

Sei Pr die von einem Knoten vr empfangene Signalleistung und Ir die von anderen Knoten erzeugte Interferenzleistung. Sei Pe die Umgebungsrauschleistung.

Dann empfängt ein Knoten vr eine Übertragung genau dann, wenn

image-placeholder
(4-1)

Somit ist β 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.

Der Wert der empfangenen Signalleistung Pr ist eine abnehmende Funktion des Abstandes d(vs, vr) zwischen Sender vs und Empfänger vr.

Genauer gesagt wird die empfangene Signalleistung fällt mit dem Abstand d(vs, vr) ab als

image-placeholder
(4-2)

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.

Sei Pi die Sendeleistung des Knotens vi.

Eine von einem Knoten vs ∈ V übertragene Nachricht wird von einem Knoten vr erfolgreich empfangen, wenn gilt:

image-placeholder
(4-3)

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. Pr ≥ θ.

In vielen Situationen kann ein solcher Schwellwert implizit durch den Umgebungsrauschleistungspegel Pe angegeben werden.

Funkregionen

Übertragungs (Transmission) Bereich

Kommunikation mit niedriger Fehlerrate möglich

Erkennungs (Detection) Bereich

Erkennung des Sendesignals möglich, aber Kommunikation aufgrund hoher Fehlerrate nicht möglich

Interferenz Bereich

Signal wird nicht eindeutig erkannt, und überlagert sich zum allgemeinen Empfangsrauschen

Abbildung 4-2. Empfangs, Interferenz- und Erkennungsbereiche bei drahtloser Kommunikation

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.

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

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.

Zum Beispiel wurden einige MAC-Protokolle vorgeschlagen, um Interferenzen zu reduzieren, indem ein bestimmter Hop-Abstand zwischen zwei Sendern sichergestellt wird.

Konkret 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

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

Abbildung 4-3. Das UDI-Modell hat zwei Radien: einen Übertragungsradius (Länge 1) und einen Interferenzradius (Länge

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.

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

Abbildung 4-4. Beispiel, bei dem UHI fehlschlägt: Die Knoten

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 gehandhabt zu werden.

Protokollmodell (PM)

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

Richtungsmodelle

Kommunikationsverbindungen können bi- und unidirektional sein

Kommuniationsprotokolle 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).

Abbildung 4-5. 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)

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

Technologien

Technologie | Sendeleistung | Reichweite | Kanäle | Bandbreite
Bluetooth | 1mWK3/10mWK2/100mWK1 | 1mK3/10mK2/100mK1 | - | 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

Mobile Ad-hoc Netzwerke

Mobile Ad-hoc Netzwerke (Sensor und Cellular 3G/4G usw) zeigen besondere Eigenschaften:

Der Verbindungsgraph ist dynamisch und räumlich und zeitlich veränderlich

Der Ort von Knoten ist veränderlich, daher auch Nachbarschaftseigenschaften

Physische Nachbarschaft bedeutet nicht Kommunikation (Sensornetzwerke)

Pfade (Kommunikationsrouten) sind veränderlich

Interferenz ist dynamisch

Abbildung 4-6. Mobile Ad-hoc Sensornetzwerke mit kleinen eingebetteten Sensorknoten

Abbildung 4-7. Pfade (Kommunikatiosnrouten) in mobilen ad-hoc Netzwerken [PANA,Tusch,2006]

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

f ₁, f ₂ f ₃

Abbildung 4-8. Hexagonale Wabenstruktur (Zellen) ist häufig optimale Abdeckung mit Basisstationen und benötigt nur drei verschiedene Frequenzkanäle

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!

Abbildung 4-9. Übergang eines mobilen Knotens zwischen zwei Funkzellen mit Basisstationen

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!

Abbildung 4-10. Symbolfehlerrate als Funktion des Signal-Rausch-Verhältnisses (SNR) für vier verschiedene Modulations- / Codierschemata [7]

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)

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

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

Kommunikationstechnologien und Protokolle im IoT

Wie kann praktisch Kommunikation von Sensorknoten untereinander und mit Berechnungsknoten stattfinden?

Welche Protokolle können verwendet werden?

Es sollen das Internet der Dinge (IoT) betrachtet werden, d.h. Einbindung von Sensorknoten in das Internet

Welche physikalischen Übertragungstechnologien sind nutzbar?

Kommunikationtechnologien

Klassifizierung

Drahtlose Kommunikation

Drahtlose Kommunikation ist durch 1:N Kommunikation (Broadcasting) gekennzeichnet, d.h., i.A. findet keine direkte Kommunikation mit anderen Knoten (Peer-to-Peer) statt. Z.B. Radiowellen können in einem Umkreis von vielen Knoten empfangen werden.

Drahtgebundene Kommunikation

Hier findet immer gerichtete Kommunikation zwischen zwei Knoten statt. Aber: Auch Bussysteme sind 1:1 Kommunikationsnetze, wo auch Broadcasting stattfindet!

Physikalischen Medien

Drahtlose Kommunikation

Radiowellen (Elektromagnetische Felder) in unterschiedlichen Frequenzbereichen, Lichtwellen, quantenmechanische Interaktion (Quantencomputer!), magnetische Felder,

Drahtgebundene Kommunikation

Elektrische Leitungen mit elektrischen Strom, aber auch optische Leitungen wie Lichtwellenleiter, oder auch mittels Laserdioden gerichtete Lichtwellenausstrahlung, geht auch mit Radiowellen und Antenntenarrays (MIMO) → 5G Netze!!

Technologien

WLAN

Radiowellen im frequenzbereich 2.4GHz und 5GHz, Reichweite ca. 100m, über Zeit- und Kanalmultiplexing können 1:N Netzwerke aufgebaut werden;

Bluetooth

Radiowellen im frequenzbereich 2.4GHz, Reichweite ca. 1-10m, i.A. nur durch Kanalmultiplexing können 1:N Übertragungskanäle ermöglicht werden

RFID

Radiowellen im Frequenzbereich 1MHZ/14MHz, Reichweite ca. 10cm (durch gleichzeitige Energieübertragung limitiert) , nur 1:1 Kommunikation

UHF

Einfache Radiowellenübertragung im Frequenzbereich 400 MHz, Reichweite ca. 10m, nur 1:1 Übertragung (ansonsten Interferenz)

LoRa

LoRa ist eine Funktechnologie, die das Senden kurzer Datenpakete über eine große Reichweite (in der Regel einige Kilometer) bei einer UHF Frequenz von 915 MHz ermöglicht. Long Range Wide Area Network (LoRaWAN) ist ein Low-Power-Wireless-Netzprotokoll auf der Ebene der Vermittlungsschicht. Endgeräte und Gateways im LoRaWAN nutzen ein proprietäres und patentiertes Übertragungsverfahren.

ZigBee

Zigbee ist ein Funkstandard der unterschiedliche Geräte auf kurzen Strecken miteinander verbindet – die Funkreichweite beträgt je nach Leistung und baulicher Umgebung zwischen 10 und 20 Metern, unter idealen Bedingungen auch bis zu 100 Meter. Im Gegensatz zu bekannteren Standards wie WLAN oder Bluetooth zeichnet sich Zigbee durch Energieeffizienz, Einfachheit in der Anwendung und hohe Flexibilität aus. Die Endgeräte verwalten das Netzwerk autark. Das bedeutet, die Geräte treten dem Netzwerk nach einer ersten Einbindung selbständig bei, werden gefunden und kommunizieren darüber. Bei ZigBee ist das 2,4-GHz-Frquenzband unterteilt in 16 Kanäle mit einem Kanalraster von 5 MHz.

Protokollschichten

Abbildung 5-1. Verschiedene Protokollschichten in Sensornetzwerken (ähnlich ISO Schichtenmodell) [https://de.wikipedia.org/wiki/ZigBee]

Netzwerke und Protokolle

Häufig werden Sensorknoten über vorhandene Netzwerke eingebunden

WLAN (Intra- und Internet)

4G/5G Mobiles Internet

Dann werden gängige Kommunikationsprotokolle verwendet, gegeben durch das ISO Schichtenmodell der Netzwerkkommunikation und der physikalischen Technologie:

User Datagram Protocol (UDP)

Transmission Control Protocol (TCP)

Hypertext Transfer Protocol (HTTP/HTTPS)

WebSockets

Web Real Time Communication (WebRTC)

Man unterscheidet:

Klienten-Server Kommunikation

Es gibt ein oder mehrere Klientenknoten die mit einem Serverknoten kommunizieren (1:N Master-Slave Architektur). Die Klientenknoten können nicht untereinander kommunizieren. Die Kommunikation kann unidirektional, bidirektional, oder semibidirektional sein (d.h. nur der Klient kann einen Kommunikationskanal aufbauen).

Punkt-zu-Punkt Kommunikation

Ein Knoten A kann direkt mit einem Knoten B bidirektional kommunizieren.

Der Kommunikationsendpunkt muss durch den Kommunikationsstartpunkt erreichbar und adressierbar sein! D.h. der Endpunkt muss öffentlich sichtbar sein wenn sich A und B nicht kennen.

Hier fangen jetzt die Problem an:

Welches Adressierungsschema soll für die Knoten verwendet werden? Gibt es öffentliche oder private Adressen? Wann und wo müssen die Adressen eindeutig sein (keine Dopplung)?

Sind zwei Knoten A und B nicht direkt (in einem Netzwerk) verbunden wird Routing (Pfadfindung) benötigt

IP Kommunikation

Internet Kommunikation mit dem Internet Protocol (IP)

Netzwerkknoten benötigen eindeutige IP Adresse

IP-4

IP-6

Das Internet ist ein Netz aus Netzen (hierarchisch und verteilt)

Netzwerkadressen werden in räumlichen Domains zusammengefasst (IP4)

Geräte benötigen daher lokale IP Adressen (u.U. wechselnd), Auflösung über Namen und Domain Name Service (DNS)

IP6 ordnet Geräten eindeutige Adressen zu (mobil)

Die Anzahl der Geräte (gerade durch IoT und Sensornetzwerke) übersteigt die tatsächlich möglichen IP4 Adressen. IP6 ist derzeit davon noch nicht betroffen.

Abbildung 5-2. Domainen im Internet und Netze aus Netzen

Private Netzwerke und die immer größer werdende Anzahl von Geräten erfordern bei IP4 NAT (nicht bei IP6)

NAT: Network Address Translation

Abbildung 5-3. Kommunikation zwischen privaten IP Netzwerken über NAT

Network Address Translation

Zwischen einem Rechner A und B befindet sich ein NAT Gerät

Dieses NAT Gerät ist nach außen durch eine IP Adresse ipaddrpub öffentlich sichtbar (wobei es auch hierarchische Netze mit mehreren NAT Ebenen geben kann)

Rechner in dem NAT Netzwerk haben verschiedene private IP Adressen ipaddrprv,i.

Wenn nun Kommunikation unter Verwendung der öffentlichen IP Adresse stattfindet muss das NAT die Nachrichten verändern (Austausch privater Adresse mit öffentlicher, ipaddrprv,i → ipaddrpub)

Von außen empfangene Nachrichten müssen ebenfalls wieder umgerechnet werden (ipaddrpub → ipaddrprv,i) und dem richtigen Rechner zugeführt werden!

Daher können in privaten Netzwerken keine öffentlich sichtbaren Services angeboten werden (also z.B. HTTP Server)!

Neben der Adressumrechnung sind weitere Umrechnungen über Zuordnungstabellen erforderlich, z.B. ein Kommunikationsport port

Port-preserving NATs rechnen nur die Adressen um, aber nicht die Portnummern

Not-Port-preserving NATs rechnen auch die Portnummer um (in mobilen Netzwerken immer der Fall, da dort auch verschiedene Geräte die gleiche IP Adresse besitzen können)

Man unterscheidet:

Symmetrische NATs (Not-Port-preserving NATs); jeder ausgehende Verbindung ist unterscheidbar, d.h., es gibt nicht zwei gleichzeitige ausgehende Verbindungen (auch zu unterschiedlichen Servern) mit der gleichen Portnnumer

Asymmetrische NATs (Eventuell Port-preserving)

Symmetrische NAT Netzwerke sind eine echte Hürde für direkte 1:1 Kommunikation von Sensorknoten (und sonstigen Rechnern), vor allem wenn A und B durch symmetrische NATs getrennt sind

Eine Methode um 1:1 Verbindungen durch NATs herzustellen (zumindest via UDP) ist das sogennante Hole-Punshing Verfahren

Transportprotokolle

UDP

User Datagram Protocol. Es wird für die Übertragung einzelner unabhängiger Datenpakete von einem Senderknoten A das Tupel ⟨ipaddrB,portB⟩ des Empfängerknoten B benötigt. Es wird Routing benötigt. Der Sender muss aber nicht auffindbar sein! Der Port ist einem Verarbeitungsprozess zugeordnet.

TCP

Transmission Control Protocol. Es findet ein Verbindungsaufbau statt mit zwei unidrektionalen Kommunikationskanälen zwischen A und B. Sowohl das Tupel ⟨ipaddrA,portA⟩ als auch das Tupel ⟨ipaddrB,portB⟩ müssen bekannt sein

Anwendungsprotokolle

HTTP

Hypertext Transfer Protocol. Benutzt TCP, nur 1:N Serverkommunikation, wobei auch jeder Sensorknoten mit einem ⟨ipaddr,port⟩ Tupel einen Service anbieten kann. Alle HTTP Anfragen sind bidirektional (GET/PUT)

WebSockets

Benutzt initial HTTP(S) und dann TCP. Reine bidirektionale Datenübertragung (Datenkanal)

WebRTC

Benutzt nur UDP. Echtzeitfähige Datenstromübertragung (Audio, Video, Daten)

HTTP

GET

Es können nur Daten vom Server (B) zum Klienten (A) auf Anfrage gesendet werden. Eine Parametrisierung einer Anfrage ist durch URL Parameter eingeschränkt möglich.

PUT/POST

Es können Daten von A nach B und dann von B nach A gesendet werden,

Node B

hs=http:new()
hs:service('a:9099',
  function (url,address,params,body)
    data = JSON.decode(body)
    return JSON.encode({3,2,1})
  end
)

Node A

hs=http:new()
hs:put('a:9099',JSON.encode({1,2,3}),
       function (text,err)
         data = JSON.decode(text)
       end)

Abbildung 5-4. (Links) HTTP POSt Anfrage (Rechts) TCP Kommunikation für eine HTTP GET Anfrage [Zoltan Horvat/Israel Cidon]

WebSockets

WebSockets werden ebenfalls primär für die Klienten-Server Kommunikation verwendet, sind aber bidirektional.

Datenübertragung mit HTTP GET/PUT Anfragen können nur vom Klienten initiiert werden, nicht vom Server

WebSocket Datenübertragung kann von beiden Seiten initiativ erfolgen (aber Verbindungsaufbau nur durch Klienten)

Verbindungsaufbau eines Sockets über HTTP als eine Art "Upgrade" der Verbindung

Übertragung von Daten mit WebSockets ist zuverlässig

Abbildung 5-5. Vergleich WebSockets mit WebRTC Datenkanälen [bloggeek.me/webrtc-vs-websockets]

Da der Verbindungsaufbau immer mit einem öffentlichen Server (ggfs. nur im Intranet) stattfindet kann ein Klientenknoten sich in einem privaten Netzwerk befinden (nicht öffentlich sichtbar).

Auch wenn zwei Knoten A und B über WebSockets kommunizieren wollen wird dieses nur über den öffentlichen Server stattfinden und keiner der Knoten A und B müssen öffentlich sichtbar sein → Kommunikation über Relaisknoten C

Eine direkte Kommunikation zwischen zwei Sensorknoten über WebSockets geht nur dann wenn wenigstens ein Knoten direkt erreichbar ist (also ohne NAT) und einen HTTP Service anbietet. Aber im WEB Browser kann kein Service angeboten werden!

Abbildung 5-6. Initierung von WebSocket Kanälen über eine HTTP Anfrage und schließlich direkte Kommunikation via TCP [Renuka B S,2020]

WebRTC

WebRTC stellt echtzeitfähige Datenstromkommunikation via UDP zur Verfügung

Übertragung von Daten mit WebRTC/UDP ist daher nicht grundsätzlich zuverlässig (obliegt der eigenen Anwendungsschicht)

Abbildung 5-7. Vergleich der Protokollarchitektur von WebSockets und WebRTC [hpbn.co/webrtc]

Daten: primär Audio und Videodatenströme, sekundär generische Datenkanäle

Neben der strom- und kanalbasierten Kommunikation bietet die WebRTC Schicht auch den Aufbau und die Einbeziehung von externen Services durch den ICE Agenten

Es gibt zwei Fragestellung:

Wie können zwei Endgeräte (Prozesse) A und B protokollarisch und technologisch mit einander kommunizieren (Verbindung), d.h. wie finden sie sich physisch

Welche Knoten sollen Verbindungen aufbauen und Daten austauschen (Auktionsserver! Biete Sensor, Suche Sensor), d.h. wie finden sie sich logisch/funktional

Abbildung 5-8. RTCPeerconnection Architektur [hpbn.co/webrtc]

NAT und UDP Hole Punching

https://bford.info/pub/net/p2pnat

Das Problem: Das öffentlich sichtbare Tupel ⟨ipaddr,ipport⟩ eines Peer Ports muss auch für eingehende Datenströme verwendet werden.

Wenn ein Klient Daten über einen Port mit NAT sendet merkt sich der NAT das Mapping und eine Rücksendung an den Senderport wird an das richtige Gerät und den Prozess vermittelt.

Aber wie soll Klient A mit Klient B Kontakt aufnehmen wenn zuvor Klient B keinen Kontakt mit A aufgenommen hat? Es muss versucht werden den NAT von B "durchzuschalten"

Dazu werden (leere Ping) UDP Pakete zwischen den Klienten gegenseitig zugesendet.

STUN, TURN

https://help.estos.com/help/de-DE/procall/7/erestunservice/dokumentation/htm/IDD_FUNCTIONALITY.htm

[help.estos.com]

Signaling Server

Signaling Server dienen zum indirekten Austausch von Daten zwischen zwei Klienten. Dies kann ein Dienst sein, der von beiden Klienten erreichbar ist oder auch mehrere Dienste die mittels Zusammenschluss miteinander verbunden sind

Abbildung 5-9. Klient A ist direkt erreichbar. Klient B kann Daten direkt an Klient A senden

Abbildung 5-10. Erfolgloser Verbindungsaufbau über einen NAT-Router hinweg.

STUN - Session Traversal Utilities for NAT (RFC5389)

Dieses Protokoll ermöglicht es einem Klienten in einem lokalen Netzwerk (LAN), seine eigene, öffentliche IPv4-Adresse zu ermitteln. Der rufende Client im LAN kann auf diese Weise dem angerufenen Klienten außerhalb des LAN mitteilen, welche IPv4-Adresse (und Portnummer) verwendet werden kann um eine direkte Kommunikation mit ihm zu ermöglichen ("Peer-to-Peer" Verbindung).

Abbildung 5-11. Erfolgreiche Kommunikation unter Zuhilfenahme eines STUN-Servers.

TURN - Traversal Using Relays around NAT (RFC5766)

Ein Server im Internet, der das TURN-Protokoll implementiert, ermöglicht es zwei Klienten, Daten ohne eine direkte Verbindung auszutauschen ("Relais Server"). Dies wird notwendig, wenn es keine Möglichkeit gibt, eine direkte Klient-zu-Klient-Verbindung aufzubauen.

Abbildung 5-12. Erfolgloser Kommunikationsversuch über ein "Symmetric NAT".

Abbildung 5-13. Erfolgreicher Kommunikationsversuch über ein "Symmetric NAT" durch Nutzung eines TURN-Servers.

ICE - Interactive Connectivity Establishment (RFC5245)

Zwei Klienten können die mit Hilfe von STUN und TURN ermittelten Verbindungsinformationen (und andere Daten) mit Hilfe des ICE Protokolls austauschen. Die Übermittlung der Informationen muss dabei über einen eigenen Dienst erfolgen, einen sog. "Signaling Server". Dieser Dienst muss von beiden Klienten erreichbar sein.

WEB Browser

Im WEB Browser (als Sensor-, Aggregations-, oder Anwendundgsknoten) stehen zur Verfügung:

HTTP GET/PUT

WebSockets

WebRTC mit Peer Services

Aber: Berechnung sollte in separate Threads (WEB Worker) ausgelagert werden. In einem WEB Worker stehen dann nur noch zur Verfügung:

HTTP GET/PUT

WebSockets

Auch unsere Lua VM im WEB Browser wird in einem separaten Worker Threadprozess ausgeführt (unabhängig vom Hauptthread der nur für den Zugriff und Veränderung des DOM zuständig ist)

Vernetzung und Kommunikation in LuaOS

Abbildung 5-14. Verschiedene Arten der Kommunikation und Vernetzung von Sensorknoten mit Lua VM innerhalb und außerhalb von NAT Netzwerken

/luaweb.html"

Vertiefung

WebRTC

https://hpbn.co/webrtc

NAT/STUN

https://www.net.in.tum.de/fileadmin/TUM/teaching/masterkurs_rechnernetze/ws0910/mnet_04_Network_Layer_NAT.pdf

Das Semantisch Organisierte Sensornetzwerk und Gruppenkommunikation

Wie können Sensorknoten semantisch miteinander Daten austauschen

Wie können Sich einzelne Knoten miteinander verbinden ohne IP Adressen zu nutzen?

Services vs. Geräten

Semantik von Daten vs. IP Adressen

Geospatiale Semantische URLs

Eine URL kann neben einen Server/Service und dem verwendeten Kommunikationsprotokoll weitere Informationen über Pfade und URL Parameter enthalten:

URL Schema = PROTO://SERVER/PATH?PARAMTER

Die Idee: Pfade werden benutzt um Sensoren, d.h., Sensorknoten zu erreichen

Dabei kann ein Sensorknoten seinen Dienst in einem Verzeichnisserver (Broker) registrieren: Directory Name Service (DNS)

Die Pfade können aus geospatialen und sensorsemantischen Kennzeichnern zusammengesetzt werden

Die Verzeichnise können geospatiale Räume abbilden

Sensorknoten können in beliebig vielen Verzeichnissen registriert werden

Beispiele

dns/geo/bremen/sensor/temperatur/*
dns/sensor/temperatur/ba8b195b-6810-ea2e-457a-8b629382c80c
dns/sensor/temperatur/location/room/
dns/geo/bremen/sensor/nodes/*

Wie könnte ein geeignetes semantische Schema aussehen (Klassifiaktion)

Jeder Sensorknoten erhält eine eindeutige Portadresse im UUID Ver. 4 Format

XXXXXXXX-XXXX-XXXX-XXXX-XXXXXXXXXXXX
ba8b195b-6810-ea2e-457a-8b629382c80c
0c9c23d4-15d0-ab81-207a-7c24dba9c00b

Sensor Router: Verzeichnisserver und Kommunikationsmultiplexer

Es wird WebSocket Kommunikation zwischen einem Sensorknoten und dem öffentlich sichtbaren Sensor Router (inkl. DNS) verwendet

Der Kommuniaktionskanal überträgt RPC Nachrichten vom Endpunkt zum Router un umgekehrt

Der Sensor Router verwaltet die Verzeichnisse und trägt neue Sensorknoten in den Verzeichnissen ein

Andere Sensorknoten oder Rechner können mit einem Sensorknoten über den Sensor Router (Multiplexer) verbunden werden → Virtuelle Kanäle (Virtual Channel, VC)

Abbildung 6-1. Kommunikationsarchitektur des Sensor Routers mit DNS

Remote Procedure Call

Endpunkt

Jeder Endpunkt (Sensorknoten) kann über einen WebSocket Kanal einen RPC Service zur Verfügung stellen:

Sensor Information (Messeinheit usw.)

Sensor Lesen

Sensor Kalibrieren

Sensor Schreiben (wenn möglich)

Jedser RPC Service hat einen Port und stellt Operation via Capabilities bereit

Sensor Router

Ebenso stellt der Sensor Router auf der anderen Seite einen RPC Service zur Vefrügung:

Eintragung des Sensorknoten (bzw. dessen Kommunikationsports) in ein Verzeichnis im DNS

Erzeugung oder Entferneung von Verzeichnissen im DNS

Suche von Kommunikationspartnern über DNS Pfadsuche (ggfs. mit RegEx Mustern und Wildcards)

Verbindung mit anderen Kommunikationsendpunkten über Virtuelle Kanäle (VC)

Zugriffsrechte und Authorisierung

Bisher könnte jeder Sensorknoten der mit dem Sensor Router eine Verbindung hat alle Operationen ausgühren

Sogenannte Capabilities geben dem Klienten (Endpunkt) bestimmte Rechte für Operationen

Eine Capability besteht aus:

Serverport (bezeichnet den Service)

Objektfeld (bezeichnet ein Objekt des Service)

Rechtefeld (bestimmt mögliche RPC Operationen auf Objekten oder Service)

Sicherheitsport der die Rechte einwegverschlüsselt enthält

Capabilities

Abbildung 6-2. Capabilities und Einwegverschlüssung des Rechtefelds mit einem (privaten) randomsierten Port

GateWay Router

Der Gateway Router stellt Gruppenverwaltung, Nachrichtenvermittlung zwischen LuaOS Peers, und Garbage Collecting zu Verfügung

Es wird HTTP und WebSocket Kommunikation verwendet

HTTP für Router RPCs

WebSockets für Peer-to-Peer und Peer-to-Group Kanalkommunikation (aber auch hier RPC Semantik)

Jeder LuaOS Peer hat mindestens einen Port der mit einer eindeutigen UUIDv4 bezeichnet wird

Diese UUID kann in Gruppen eingetragen werden

Gruppen können beliebige ID Kennzeichnernamen haben, müssen aber auf einem Router unterscheidbar sein

LuaOS Route API

LuaOS Peers haben die folgende API:

Route

Basisklasse umd Gruppen zu verwalten

Groups

Gruppenzugriff und Gruppenadministration (über Route)

Ports

Steuerung des Gateway Multiplexer, d.h., Herstellen von Kanalverbindungen zwischen Peers

Routingobjekt

Jeder Zugriff auf den Router benötigt eine Route Instanz unter Angabe der Router URL (HTTP Port):

local <route> = route:new(url:string)

Jede Route Instanz ist meiner eindeutigen Port UUID verknüpft; diese wird vom Router als Remote Endpoint ID verwendet; der Port muss beim Router angemeldet werden:

<route>:ping()
local <port> = <route>:connect()
<port>:peerid

Route Group API

Mit einem Routingobjekt können Gruppen verwaltet werden:

<route>:ask(groupid:string)liefert alle Mitglieder einer Gruppe (Port UUID)

<route>:create(groupid:string) erzeugt eine neue leere Gruppe

<route>:delete(groupid:string) erzeugt eine neue leere Gruppe

<route>:join(groupid:string) fügt lokalen Peer Port zur Gruppe hinzu

<route>:unjoin(groupid:string) entfernt lokalen Peer Port zur Gruppe

Port API

Wenn ein Peer Port beim Route registriert ist können beliebige andere Peer Ports von anderen LuaOS Knoten verbunden werden (Virtual Circuit):

<port>:connect(peerid:string)

Wenn mehr als ein Remote Peer Port hinzugefügt wird erhält man Nachrichtenmulticasting, d.h. jede eingehende Nachricht wird an alle hinzugefügten Zielports dupliziert gesendet

Nachrichten können über den Port empfangen und gesendet werden:

<port>:write(data) sendet eine Nachricht (String oder Datentabelle) über den vrituellen Kanal

<port>:read() liest Daten aus einer Eingabequeue die von anderen Peer Ports an diese gesendet wurden

Tupelräume

Werden noch im Modul Gruppenkommunikation behandelt

Kommunikation von Sensorknoten über Tupelräume ist eine Koordinationssprache.

Es gibt Produzenten und Kosumenten. Datenaustausch ist anonym (nicht addressiert). Verbindung von Produzenten und Konsumenten über Tupeldaten nur durch deren Inhalt, nicht aber Ort.

Die Daten sind mit Tupeln organisiert.

Tupel-Räume stellen ein assoziiertes Shared-Memory-Modell dar, wobei die gemeinsam genutzten Daten als Objekte mit einer Reihe von Operationen betrachtet werden, die den Zugriff der Datenobjekte unterstützen

Ein Tupel ist eine lose gekoppelte Verbindung einer beliebigen Anzahl von Werten beliebiger Art /Typ/

Ein Tupel ist ein Wert und sobald es in einem Tupelraum gespeichert ist, ist es persistent.

Tupelwerte erfordern einen Mustervergleich basierend auf dem Vorlagenmuster, bestehend aus tatsächlichen (v, ε, x) und formalen Parametern (x?, Variablen, die mit Referenzsemantik verwendet werden)

Ein Tupel kann nur durch seine Verknüpfung mit Vorlagenmustern (Templates) p angesprochen werden.

Ein bekanntes Tupelraum-Organisations- und Koordinationsparadigma ist Linda [GEL85].

Basisoperation: Output, Input, Read. Die lesenden (konsumierenden) Operation blockieren den Aufrufer solange bis passende Tupel gefunden wurden.

Abbildung 6-3. Ein- und Ausgabeoperationen in Tupelräumen

Zusammenfassung

Zwei verschiedene Methoden für die semantisch getriebene organisation der Kommunikation in Sensornetzwerken wurden vorgestellt:

Verzeichnisdienst mit Services über Pfade und addressierter Remote-Procedure Call Kommunikation (servicegetriebene Kommunikation)

Ontologien werden benötigt für ein gemeinsames Verständnis von Pfadenstrukturen, Namen, und Services

Datenbank mit Tupeln und rein datengetriebene Kommunikation mittels Mustern (generative Kommunikation)

Ontologien werden benötigt für das gemeinsame Verständnis der Daten und Suchmustern

Synchronisation und Kommunikation

Wie kann mit Coroutinen (Fibers) geschachtelt mehrere Aufgaben aus der Sicht des Programmiermodells "parallel" ausführen?

Welche Synchronisation wird benötigt?

Einführung eines universellen Synchronisationsobjekts für Coroutine und Implementierung von Stanadards

Coroutinen

Eine Coroutine ist in Lua ein separates Unterprogramm

Coroutinen werden in Lua niemals parallel (gleichzeitig) ausgeführt

Eine Coroutine kann eine andere nicht unterbrechen

Aber: Eine Coroutine kann an beliebiger Stelle im Programmfluss zu einem Scheduler verzweigen (yield), der eine andere ruhende Coroutine (re)aktiviert (resume)

local co1 = coroutine.create(function ()
  ..
  coroutine.yield()
  ..
end
local co2 = coroutine.create(function ()
  ..
  coroutine.yield()
  ..
end
coroutine.resume(co1)
coroutine.resume(co2)

Coroutinen Synchronisation

Verschachtelte Ausführung von Coroutinen ist ergibt noch keine Synchronisation

Synchronisation zwischen Coroutinene wäre z.B.:

Warten auf Daten

Zeitliche Synchronisation (Barrierer, Event)

Produzenten-Konsumenten Abstimmung (Semaphore, Collector)

Schutz von zusammengesetzten (nicht atomaren) Datenstrukturen (Mutex)

Universelles Synchronisationobjekt

Einführung eines universellen Synchronisationsbjekts dessen Verhalten durch drei Funktionen gegeben sind:

oninit: Initialisierung eines Zählers

onawait: Berechnung eines neues Zählerwertes, Warten und Freigeben von Coroutinen

onsignal: Berechnung eines neues Zählerwertes, Freigeben von Coroutinen (und ggf.s Datenspeicherung in einer Queue)

Das universelle cosync Objekt bietet mit der await Operation die Möglichkeit eine Art Belegung einzuleiten

Die signal Operation ermöglicht eine Art von Freigabe

Es gibt einen optionalen Zähler (wenn es eine init Funktion gibt)

Die onawait und onsignal Funktionen bestimmen die Blockierung und Freigabe von Coroutinen (intern mit yield und resume umgesetzt)

Diese beiden Funktionen aktualisieren auch den Zähler (wenn vorhanden)

Es werden Tupel aus Rückgabewerte verwendet: ⟨counter,wait,release⟩

Beiden Funktionen erhalten den aktuellen Zählerwert und die Anzahl bereits wartender Coroutinen als Argumente

local co = cosync:new(
oninit? :
  function ()
    return value -- sets counter value
  end |
  value |
  nil
onawait :
  function (counter,waiters)
    return newcounter,wait?,release?
  end |
  function (waiters)
    return wait?,release?
  end
onsignal :
  function (counter,waiters)
    return newcounter,release?
  end |
  function (waiters)
    return release?
  end |
  nil
)

Barriere mit Cosync

Eine Barriere dient zur zeitlichen Synchronosation einer Gruppe von Prozessen / Coroutinen.

Es handelt sich um eine selbstauslösende Synchronisation nur unter Verwendung der +await* Operation

Die Gruppengröße ist vorher festgelegt

Jeder Prozess tritt der Barriere und wird blcokiert bis der N-te Prozess beitritt und alle Prozesse freigibt.

Implementierung

Barrier = function (N)
  return cosync:new(
    nil,
    function (waiters)
      return waiters~=(N-1),waiters==(N-1)
    end
  )
end

Beispiel

local ba = Barrier(4)
for i = 1,3 do
  local co = coroutine.create(function ()
    -- wait for new input data
    ba:await()
  end); coroutine.resume(co)
end
.. prepare input data for jobs ..
ba:await()

Mutex mit Cosync

Schutz "kritischer" Codeabschnitte (um Datenkonsistenz zu gewährleisten)

Immer nur ein Prozess kann einen Mutex Lock besitzen/halten (Invariante)

Die Operationen await und signal müssen immer paarweise verwendet werden.

Ist der Lock vergeben, führen await Aufrufe zur Prozessblockierung (oder einem yield)

Implementierung

Mutex = function ()
  return cosync:new(
    function () return 1 end,
    function (counter,waiters)
      if counter == 0 then return counter,true
      else return 0,false end
    end,
    function (counter,waiters)
      if waiters then return 0,1
      else return 1,0 end
    end
  )
end

Beispiel

local mu = Mutex()
local data = { ... }
for i = 1,3 do
  local co = coroutine.create(function ()
    mu:await()
    .. modifify non-atomic shared data structures ..
    mu:signal()
  end); coroutine.resume(co)
end

Semaphore mit Cosync

Semaphoren dienen klassisch zur Synchronisation von Produzenten- und Konsumentenprozessen

Der Semaphor besitzt einen Zähler der nicht negativ wird (Invariante)

Die await Operation erniedrigt den Zähler um den Wert 1, es sei denn der Zähler ist Null, dann wird der Aufrufer blockiert

Die signal Operation erhöht den Zählerwert um 1. War er vorher aud Null und gibt es wartende Prozesse, wird einer ausgewählt und freigegebn. Der Zähler bleibt auf Null

Implementierung

Semaphore = function (init)
  return cosync:new(
    function ()
      return init
    end,
    function (counter,waiters)
      if counter > 0 then
        return counter-1,false
      else
        return counter,true
      end
    end,
    function (counter,waiters)
      if waiters > 0 and counter == 0 then
        return 0,1  -- +1 consumed by release of waiter
      else
        return counter+1,0
      end
    end
  )
end

Beispiel

local sema = Semaphore(0)
for i = 1,3 do
  local co = coroutine.create(function ()
    .. produce data ..
    sema:signal()
  end); coroutine.resume(co)
end
for i = 1,3 do
  sema:await()
end

Collector mit cosync

Der Semaphore muss bei einem Produzenten-Konsumenten System mit N Produzenten N-mal dekrementiert werden um auf die Terminierung aller Arbeitsprozesse zu warten

Den Semaphore kann man einfach in einen Kollektor transformieren der nur noch einen await Aufruf benötigt

Fusion von Barriere und Semaphor

Implementierung

Collector = function (N)
  return cosync:new(
    function ()
      return 0
    end,
    function (counter,waiters)
      if counter == N then return counter,false,true
      else return counter,true,false end
    end,
    function (counter,waiters)
      counter=counter+1
      if counter == N then return counter,true
      else return counter,false end
    end
  )
end

Beispiel

local coll = Colelctor(3)
for i = 1,3 do
  local co = coroutine.create(function ()
    .. produce data ..
    coll:signal()
  end); coroutine.resume(co)
end
local status = coll:await()

Cosync und Timeouts

Bisher wurde angenommen, dass das Synchronisationsereignus auch eintritt, z.B. dass die Barriere ausgelöst wird

Gerade bei verteilter Kommunikation können Nachrcihten verloren gehen

Wenn der Nachrcihtenempfang mit einer signal Operation verknüpft ist, würde u.U. das Ereignes ausbleiben

Daher führt man Timeouts als autosynchronisierendes (negatives) Ereignis ein

local o = cosync:new(...)
local status = o:await(TimeoutInMillseconds)

Tritt das Synchronisationsereignis ein, liefert await true zurück, ansonsten false ("Interrupt")

Die Wahl des Zeitfensters bis zum Scheitern einer Synchronisation ist schwierig und kritisch.

Es besteht immer die Gefahr dass ein Ereignis nach dem Timeout noch auftreten kann (z.B. der Empfang einer Nachricht)

Ist der Timeout zu klein, steigt die Wahrscheinlichkeit ein Ereignis zu verpassen

Ist der Timeout zu groß gewählt. bremst dass die Datenverarbeitung aus und es können ggfs. andere Ereignisse verpasst werden (Echtzeitfähigkeit leidet)

Cosync und Daten

Cosync Objekte dienen zunächst der reinen Coroutinensynchronisation im Kontrollpfad

Die signal Operation kann verwendet werden, um Daten in einer Queue (Liste) zu speichern

await kann die Daten abrufen

local o = cosync:new(nil|counter0,..,..)
...
o:signal(mydata1)
o:signal(mydata2)
...
local status,data = o:await(TimeoutInMillseconds)
local status,counter,data = o:await(TimeoutInMillseconds) -- with counter
-- data={mydata1,mydata2}

Cosync Objekte Reinitialisieren

Mittels der reset Operation können cosync Objekte zurückgesetzt werden:

Zähler wird auf oninit Wert gesetzt (optional durch Funktionsargument bestimmt)

Datenliste wird gelöscht

local o = cosync:new(...)
o:reset(counterinit?)

Coroutinen Kommunikation mit CoVNC

Äquivalent zu route LuaOS API, hier aber lokal nur für Coroutinen

Simulierter Nachrichtenverlust kann mittels optionalen loss Parameter eingestellt werden [0-1)

local vc = covnc:new({
  loss?=number,
  bidir?=boolean
})
local p = vc:port(id?) -- p.id
p:connect(to)
local data = p:read()
p:send({..},to?)
p:receiver(function (data) .. end)