Sensornetzwerke

Verteilte Sensornetzwerke

(Distributed Sensor Networks DSN)

• Ein verteiltes Sensornetzwerk besteht aus einer Menge von Sensor Knoten N={n₁,n₂,…}, die in einem Kommunikationsnetzwerk miteinander verbunden sind.

• Ein Sensorknoten besteht aus:

  • Einer Menge von Sensoren S={s₁,s₂,…}, wenigstens einem Sensor s (inkl. virtuellen),
  • Analoger Signalverarbeitung inkl. ADC A={a₁,a₂,…}
  • Digitale Signal- und Datenverarbeitungeinheiten P={p₁,p₂,..} und Speicher M={m₁,..}
  • Kommunikationsmodule C={c₁,c₂,…},
  • Energieversorgung und Managementmodule E={e₁,e₂,..}

Verteilte Sensornetzwerke

Verteilte Sensornetzwerke

• Verteilte Sensornetzwerke unterscheiden sich von klasschischer Datenverarbeitung

• DSN können räumlich und zeitlich verteilt sein - ohne zentralen Rechner

• Das Netzwerk selber ist der Rechner - eine virtuelle Maschine

Verteilte Sensornetzwerke

Anforderungen an und Fähigkeiten von DSN

• niedrige Kosten
• zuverlässig und robust gegen Störungen (Kommunikation, Energie, Ausfall von Knoten)
• Autonomie eines Sensorknotens
• schnelle Antwortzeit (Latenz)
• Eignung für echtzeitfähige datenstrombasierte Verarbeitung
• lange Betriebszeiträume
• Kombination von verschiedenen senorischen Größen zu neuen Informationen, die durch einen einzlnen Sensor bzw. Sensorknoten nicht verfügbar wären → Daten- und Sensorfusion
• Erhöhter Datendurchsatz durch nebenläufige Datenverarbeitung der einzelnen Sensorknoten
• Redundanz und Fehlertoleranz durch komplimentäre Gruppenbildung und Wettbewerb sowie Kooperation von Sensorknoten
• Zeitliche Synchronität → Synchronisation von Uhren

Taxonomie von DSN Architekturen

Taxonomie von DSN Architekturen

• Die Hauptaufgabe eines DSN ist die Sammlung und Verarbeitung sensorischer Daten

• Eingabe, Berechnung, Kommunikation, und Programmierung müssen zusammenhängend und nicht unabhängig betrachtet werden à Entwurf eines Systems

• Für jeden dieser Bestandteile gibt es unterschiedliche Teilaspekte und Variationen, die die Struktur und die Performant des gesamten DSN bestimmen.

• Es wird zwischen Funktion und Implementierung unterschieden:

Funktion

Die Funktion beschreibt die grundlegenden Operationen und Fähigkeiten des DSN.

Implementierung

Die Implementierung beschreibt die Methoden mit denen die Funktionen erfüllt werden können.

Taxonomie von DSN Architekturen

Taxonomie von DSN Architekturen

Taxonomie von DSN Architekturen

Taxonomie von DSN Architekturen

Netzwerkarchitekturen und Topologien

Parameter und Metriken von Netzwerken

Knotenzahl N

Gesamtzahl der Knoten, die ein Netzwerk oder ein Subnetzwerk bilden

Knotengrad (Konnektivität) K

Jeder Knoten hat mindestens eine, maximal K Verbindungen zu Nachbarknoten

Skalierbarkeit

Lässt sich das Netzwerk für belibiege Anzahl N von Knoten erweitern?

Netzwerkarchitekturen und Topologien

Routing

Strategie für die Weiterleitung und Zustellung von Daten von einem Senderknotenns n_s zu einem oder mehreren Empfängerknoten {n_e1,n_e2,…}

• Unicast: nur ein Empfänger
• Multicast: eine Gruppe von ausgezeichneten Empfängern
• Broadcast: alle Knoten (in einem Bereich) sind Empfänger

Ausdehnung D

Maximaler Abstand (Distanz) zwischen zwei Knoten

Kosten O

Anzahl der Kanten NC

Effizienz η

Anzahl der Kanten NC im Verhältnis zur Anzahl der Knoten N

Netzwerkarchitekturen und Topologien

Latenz τ

Verzögerung Τ bei der Zustellung von Daten durch Vermittlung (normiert und vereinfacht in Anzahl von Zwischenknoten)

Durchsatz B

Datendurchsatz (Bandbreite)

Nachrichtenbasierte Vermittlungsnetzwerke

• Ein Knoten eines Netzwerkes ist
  1. Quelle von Nachrichten, die Daten kapseln,
  2. Empfänger von Nachrichten, und
  3. Vermittler (Router) von Nachrichten (Zwischenknoten)

Geschaltete Netzwerke

• Direkte Datenvermittlung, ein Knoten eines Netzwerkes ist
  1. Quelle von Daten, und
  2. Empfänger von Daten

Dynamische Verbindungsnetzwerke

Kreuzmatrixschalter

• Direkte Schaltung von Verbindungen ermöglicht die Übertragung von einem Sender- zu einem Empfängerknoten.

Dynamische Verbindungsnetzwerke

Parameter

• Knotenzahl: N
• Knotengrad: 1
• Skalierbar: Ja
• Routing: Nicht erforderlich - konfliktfrei
• Ausdehnung: 1
• Kosten: N²

Vorteile

• Jeder Knoten kann mit jedem anderen Knoten jederzeit verbunden (geschaltet) werden → Dynamische Konnektivität des Netzwerkes
• Ausdehnung optimal klein (und Latenz minimal)
• Keine Nachrichtenkapselung und kein Kommunikationsprotokoll erforderlich
• Skalierung bezüglich Leistung ist gut

Dynamische Verbindungsnetzwerke

Nachteile

• Hohe Kosten und hoher Hardware-Aufwand, der quadratisch mit der Anzahl der Knoten wächst
• Skalierung bezüglich Kosten ist schlecht
• Fehlende Synchronisation zwischen Sender und Empfänger

Busbasierte Verbindung

• Alle Knoten nutzen eine gemeinsame Kommunikationsverbindung
• Bus-basierte Netzwerke skalieren bezüglich Kosten gut, aber nicht bezüglich der Leistung (Flaschenhals!)

Dynamische Verbindungsnetzwerke

Parameter

• Knotenzahl: N
• Knotengrad: 1
• Skalierbar: Jein
• Routing: Nicht erforderlich - aber nicht konfliktfrei
• Ausdehnung: 1
• Kosten: N (1)

Dynamische Verbindungsnetzwerke

Mehrstufen (Multistage) Verbindungsnetzwerke

• Mehrstufiger Aufbau des Netzwerkes
• Kompromiss bezüglich Skalierung zwischen Kreuzschaltern und Bussystemen

Dynamische Verbindungsnetzwerke

Parameter

• Knotenzahl: N
• Knotengrad: 1
• Skalierbar: Ja
• Routing: Nicht erforderlich - aber nicht konfliktfrei!
• Ausdehnung: 1 (oder n - Stufenzahl)
• Kosten: Nlog₂N

Dynamische Verbindungsnetzwerke

Mehrstufiges Permutations-Netzwerk

• Jede Stufe besteht aus Binärschaltern, die entweder durchgeschaltet oder gekreuzt geschaltet sind.
• Die Ausgänge einer Stufe k werden über ein Permutationsverfahren mit den Eingängen der nächsten Stufe k+1 verbunden.

Dynamische Verbindungsnetzwerke

I2C

I2C: Inter-Integrated Circuit

• Für I2C sind nur zwei Drähte erforderlich, z. B. asynchrone serielle Kabel.

• Diese beiden Drähte können jedoch bis zu 1008 Slave-Geräte unterstützen.

• Im Gegensatz zu SPI kann I2C ein Multi-Master-System unterstützen, sodass mehr als ein Master mit allen Geräten am Bus kommunizieren kann (obwohl die Master-Geräte nicht über den Bus miteinander kommunizieren können und sich über die Busleitungen abwechseln müssen ).

• Die Datenraten liegen zwischen asynchroner serieller und SPI. Die meisten I2C-Geräte können mit 100 kHz oder 400 kHz kommunizieren.

• Mit I2C ist ein gewisser Overhead verbunden. Für jeweils 8 zu sendende Datenbits muss ein zusätzliches Bit Metadaten (das “ACK / NACK” -Bit) übertragen werden.

Dynamische Verbindungsnetzwerke

• Die zur Implementierung von I2C erforderliche Hardware ist komplexer als SPI, jedoch weniger als asynchrone serielle Schnittstellen (UART). I2C kann einfach in Software implementiert werden.

Dynamische Verbindungsnetzwerke

• Das Inter-Integrated Circuit (I2C) -Protokoll ist ein Protokoll, mit dem mehrere integrierte digitale Slave-Schaltkreise (“Chips”) mit einem oder mehreren “Master”-Chips kommunizieren können.

• Es ist nur für die Kommunikation über kurze Entfernungen innerhalb eines einzelnen Geräts vorgesehen.

• Wie bei asynchronen seriellen Schnittstellen (wie RS-232 oder UARTs) sind für den Informationsaustausch nur zwei Signalleitungen erforderlich.

Protokoll

• Die Kommunikation über I2C ist komplexer als bei einer UART- oder SPI-Lösung. Die Signalisierung muss einem bestimmten Protokoll entsprechen, damit die Geräte am Bus diesen als gültige I2C-Kommunikation erkennen können.

Dynamische Verbindungsnetzwerke

• Nachrichten werden in zwei Arten von Frames unterteilt:
  • Ein Adress-Frame, in dem der Master den Slave angibt, an den die Nachricht gesendet wird, und
  • Einen oder mehrere Daten-Frames, bei denen es sich um 8-Bit-Datennachrichten handelt, die von Master zu Slave oder umgekehrt weitergeleitet werden.

• Die Daten werden auf die SDA-Leitung gelegt, nachdem die SCL-Leitung 0-Pegel hat, und werden abgetastet, nachdem der SCL-Leitung von 0- nach 1-Pegel übergeht.

Statische Verbindungsnetzwerke

• Nachrichtenbasierte Kommunikation, d.h. die zu übertragenen Daten werden in Nachrichten gekapselt
• In den meisten Topologien ist die Vermittlung von Nachrichten durch andere Knoten entlang eines Pfades (S → n_i1 → n_i2 → .. →→ E) erforderlich

Sternnetzwerk

• Master-Slave Netzwerk Hierarchie
• Ein ausgezeichneter Knoten ist Master, der mit jedem anderen Knoten (Slave) verbunden ist
• Kommunikation findet immer über den Master (=Router) statt

Parameter

• Knotenzahl: N
• Knotengrad: 1 (Slave), N-1 (Master)
• Skalierbar: Ja
• Routing: erforderlich - wähle Ziel in zwei Schritten über Master
• Ausdehnung: 2
• Geschlossen: nein
• Kosten: N-1

Statische Verbindungsnetzwerke

Vollständig verbundenes Maschennetzwerk

• Es gibt keinen ausgezeichneten Master, alle Knoten sind mit jedem anderen verbunden

Parameter

• Knotenzahl: N
• Knotengrad: N-1
• Skalierbar: Ja
• Routing: (nicht) erforderlich - wähle Ziel in einem Schritt
• Ausdehnung: 1
• Geschlossen: ja
• Kosten: N(N-1) ≈ N²

Statische Verbindungsnetzwerke

Statische Verbindungsnetzwerke

Binärer Baum

Parameter

• Knotenzahl: N
• Knotengrad: 3
• Skalierbar: Ja
• Routing: erforderlich - laufe vom Start aufwärts zum gemeinsamen Vorfahren und dann abwärts zum Ziel
• Ausdehnung: 2k (k - Höhe des Baums)
• Geschlossen: nein
• Kosten: Nlog₂N

Statische Verbindungsnetzwerke

Statische Verbindungsnetzwerke

Lineares Array - Kette - und Ring

Parameter

• Knotenzahl: N
• Knotengrad: 2
• Skalierbar: Ja
• Routing: erforderlich - wähle Richtung und laufe in diese Richtung
• Ausdehnung: N-1 (Kette), N/2 (Ring)
• Geschlossen: nein (Kette), ja (Ring)
• Kosten: N-1 (Kette), N (Ring)

Statische Verbindungsnetzwerke

2D Gitter

• ökonomisch und techn. geeignet für material-integrierte verdrahtete Sensornetzwerke

Parameter

• Knotenzahl: N
• Knotengrad: 4
• Skalierbar: Ja
• Routing: erforderlich (Δ-Distanz Routing)
• Ausdehnung: 2(√N-1)(ohne wraparound), 1+(√N-1) (mit wraparound)
• Geschlossen: nein (ohne wraparound), ja (mit wraparound)
• Kosten: 2(N-√N) (ohne wraparound)

Statische Verbindungsnetzwerke

• Routing: Wandere horizontal (erste Dimension) bis zur Zielspalte, dann wandere vertikal bis zur Zielzeile (zweite Dimension) → Δ-Distanz Routing

Algorithm 1.

Statische Verbindungsnetzwerke

3D Gitter

• ökonomisch und techn. geeignet für material-integrierte verdrahtete Sensornetzwerke

Parameter

• Knotenzahl: N
• Knotengrad: 6
• Skalierbar: Ja
• Routing: erforderlich (Δ-Distanz Routing)
• Ausdehnung: 3*(√3N-1)
• Kosten: 3(N-√3N)

Statische Verbindungsnetzwerke

Ad-hoc Netzwerke:

• Ad-hoc Netzwerke deren Struktur und Verbindungen sich erst zur Laufzeit bilden.

• Dabei kann sich die Struktur (Netzwerktopologie) dynamisch ändern.

• Es können Knoten und Verbindungen zwischen Knoten hinzukommen und verschwinden.

• Selbstorganisation und Selbstkonfiguration können wesentliche Prinzipien wärend der Bildung und danach sein.

Sensorknoten (aka motes)

• Übliches Designziel: klein und gunstig

• Mikroprozessor

  • wenige MHz bis einige hundert MHz
  • energiesparende Zustande

• Speicher

  • haufig nur wenige KB Arbeitsspeicher
  • teils zusatzlich Flashspeicher fur Code und Daten

Ad-hoc Netzwerke

• Sensorik

  • Temperatur, Licht, Druck, Beschleunigung, Ultraschall uvm.

• Drahtlose Kommunikation

  • Reichweiten von wenigen Metern bis einige hundert Meter
  • Erste Standards, z. B. IEEE 802.15.4 (WPAN) und ZigBee

• Energieversorgung

  • heute meist Batterien
  • in Zukunft: Solarzellen und anderes Energy Harvesting

Ausbringung

• Keine zentrale Infrastruktur

  • Initiale Position haufig unbekannt
  • Multihop-Kommunikation

• Aufgaben

  • Erkennen / Melden von Ereignissen
  • Beantworten von Anfragen

Ad-hoc Netzwerke

Ad-hoc Netzwerke

Herausforderungen

• Geringes Energiebudget

  • geringe Leistung ↔ (jahre-)lange Bereitschaft
  • Lastbalancierung, Aufteilung von Aufgaben

• Geringer Speicher, geringe Rechenleistung

  • verteilte Losungen ↔ komplexe Selbstorganisation

• Viele Sensorknoten

  • Algorithmen mussen gut mit Große des Netzes skalieren

• Geometrie

  • enger Zusammenhang zwischen Positionen und Daten/Aufgaben
  • gemeinsame Nutzung und Storung der Funkkanale ̈

• Redundanz, Unzuverlassigkeit und Dynamik

  • Knoten konnen ausfallen, sich bewegen
  • viele Knoten konnen Aufgaben redundant ausfuhren

Ad-hoc Netzwerke

Anwendungen

IP Kommunikation

• Internet Kommunikation mit dem Internet Protocol (IP)
  • Netzwerkknoten benötigen eindeutige IP Adresse (nicht für MISS geeignet!)

• Das Internet ist ein Netz aus Netzen (hierarchisch und verteilt)
  • Netzwerkadressen werden in räumlichen Domains zusammengefasst (IP4)
  • Mobile Geräte benötigen daher lokale IP Adressen (u.U. wechselnd)
  • IP6 ordnet Geräten eindeutige Adressen zu (mobil)

IP Kommunikation

IP Kommunikation

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

Remote Procedure Call

• Der RPC dient der Klienten-Server Kommunikation, wobei anders als bei HTTP Servern die Rolle von Klient und Server beliebig getauscht werden kann

• Es gibt drei Operationen:

Get Request (port)

Der Serverprozess gibt die Verarbeitung von RPC Anfragen auf einem bestimmten Port bekannt.

PutReply (client)

Der Serverprozess sendet eine Antwort auf eine RPC Anfrage

Transaction (port,data)

Der Klientenprozess sendet eine RPC Anfrage an einen Server (port) und wartet auf die Antwort

Remote Procedure Call

LUAOS

rpc = rpc:new()

rpc:getreq

function (host:string,port:number,handler: function (data:table) → table|nil)

Ein Server wird gestartet. Die benutzerdefinierte Handlerfunktion wird bei jedem Request aufgerufen und muss einen Datenrekord zurückgegben (oder nil)

rpc:putrep

function (client:userdata, data:table)

Der Server sendet die Rückantwort (implizit in rpc:getreq enthalten)

rpc:trans

function (host:string,port:number,data:table) → error:nil|string,table|nil

Ein Servertransktion durch einen Klienten.

Remote Procedure Call

local rpc = rpc:new()
rpc:getreq('127.0.0.1',12345, function (request) 
  local reply = {}
  print(request)
  case request.cmd of
    "square" => y=request.x*request.x;  reply = { status = "OK", y = y } end
    "sqrt"   => y=math.sqrt(request.x); reply = { status = "OK", y = y } end
    else reply = {status = "EINVALIDMCD" } end
  end
  return reply
end)

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