Syncronisation & Timing in Sensor Networks

 Documents

 12 views
of 38
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Titel Bastian L. Blywis Synchronisation und Topologiemessung in Sensor-Netzwerken Sensornetze ● drahtlose Kommunikation ● kleine Ausmaße ● evtl. mobil…
Share
Transcript
Titel Bastian L. Blywis Synchronisation und Topologiemessung in Sensor-Netzwerken Sensornetze ● drahtlose Kommunikation ● kleine Ausmaße ● evtl. mobil ● mit verschiedensten Sensoren ● geringe Rechenleistung ● wenig Speicherplatz ● kostengünstig Quelle: Embedded Sensor Board ESB 430/1, www.scatterweb.com Aufgaben ● Gebäudeüberwachung ● erkennen von Waldbränden ● Bergung von Lawinenopfern ● detektieren von Gewässerverunreinigung ● Bewegungstracking ● Aufbau eines Netzes ohne feste Infrastruktur ● Vernetztes Haus Probleme ● begrenzte Energiequelle ● unbekannte Anzahl → Skalierbarkeit ● evtl. partitioniertes Netz ● Komplexität der Aufgaben ● gemeinsames Übertragungsmedium ● keine zentrale Steuerungsinstanz Warum Synchronisation? ● gleichzeitiges Aufwachen aller Geräte ● Datensammlung ● erkennen von Dubletten ● Zeitmultiplex ● Ausbreitungsrichtung feststellen ● Quarzoszillatoren ungenau Reference Broadcast System Broadcast Domäne Referenzsender Quelle: Elson, Girod, Estrin. „Fine-Grained Network Time Synchronization using Reference Broadcast“ RBS: Routing Broadcast Domänen Gateway Quelle: Elson, Girod, Estrin. „Fine-Grained Network Time Synchronization using Reference Broadcast“ Zusammenfassung RBS ● neuartiger Ansatz ● eine einzige Referenz genügt minimal ● wenig speicher- und rechenintensiv ● kein nicht-determinismus des Empfängers ● Synchronisation von Domänen ● Routing möglich ● Post-Facto Synchronisation möglich ● je mehr Knoten, desto mehr Abweichung ● je mehr Referenzpakete, desto Genauer Quelle: Elson, Girod, Estrin. „Fine-Grained Network Time Synchronization using Reference Broadcast“ tiny-sync ● zwei mögliche Algorithmen ● Wert eingrenzen ● Austausch mehrerer Pakete ● geringe Speicher- und Rechenanforderung Quelle: Sichitiu, Veerarittiphan. „Simple, Accurate Time Synchronization for Wireless Sensor Networks“ Abschätzung Abschätzung der Real- Zeit t durch: ti(t) = ait + bi a: Stabilität des Für zwei Knoten gilt: Oszillators t1(t) = a1t + b1 b: Versatz zu t2(t) = a2t + b2 Beginn → t12(t) = a12t + b12 Quelle: Sichitiu, Veerarittiphan. „Simple, Accurate Time Synchronization for Wireless Sensor Networks“ Zeitpunkte bestimmen K1 K2 tx message ty reply tz t t Quelle: Sichitiu, Veerarittiphan. „Simple, Accurate Time Synchronization for Wireless Sensor Networks“ Abschätzung der Parameter t/s Datenpunkt 3 tz3 tx3 Datenpunkt 2 tz2 tx2 Datenpunkt 1 tz1 tx1 a12 b12 t/s ty1 ty2 ty3 Quelle: Sichitiu, Veerarittiphan. „Simple, Accurate Time Synchronization for Wireless Sensor Networks“ mini-sync ● viele Datenpunkte → bessere Abschätzung ● begrenzter Speicherplatz → wenige Punkte speichern ● Lösung 1: nur zwei Tripel speichern ● Lösung 2: nur nützliche Werte Speichern Quelle: Sichitiu, Veerarittiphan. „Simple, Accurate Time Synchronization for Wireless Sensor Networks“ Werte filtern verwerfen von txi mit steigung(txi,txj) ≤ steigung(txj,txk) 1≤ i≤ j≤ k für tzi in ähnlicher Weise möglich Quelle: Sichitiu, Veerarittiphan. „Simple, Accurate Time Synchronization for Wireless Sensor Networks“ Zusammenfassung tiny- und mini-sync ● zwei Möglichkeiten ● je nach Speicher und CPU auswählbar ● während des Betriebs umschaltbar ● Experiment: tiny nur um 2% ungenauer Quelle: Sichitiu, Veerarittiphan. „Simple, Accurate Time Synchronization for Wireless Sensor Networks“ Römer ● kein Zeitpunkt, sondern Intervall ● Intervall wird beim routing durch Fehler größert ● Voraussetzung 1: Stabilität pi bekannt ● Voraussetzung 2: Austausch zweier Pakete Quelle: Römer. „Time Synchronization in Ad Hoc Networks“ Austausch von zwei Paketen K1 K2 M1 t1 t2 idle rtt M2 t3 t4 t3 t5 t t Quelle: Römer. „Time Synchronization in Ad Hoc Networks“ Intervall-Transformation erhalten: [tx,ty] transformiert: [t4-(t3-tx)(1+p2)/(1-p1)-(rtt-idle(1-p2)/(1+p1)), t4-(t3-ty)(1-p2)/(1+p1)] Quelle: Römer. „Time Synchronization in Ad Hoc Networks“ Zusammenfassung Römer ● Intervall zur Abschätzung, Fehler ablesbar ● Vorausetzung: mind. zwei Pakete ● Vorausetzung: pi bekannt ● idle gering halten ● idle und rtt für jedes Paket bestimmt Quelle: Römer. „Time Synchronization in Ad Hoc Networks“ Warum Topologiemessung? ● routing in eine geographische Region ● feststellen der Netztopologie ● bestimmen des Aufenthaltsortes ● Netzabdeckung testen Wodurch Topologiemessung? ● Abstände zwischen je zwei Punkten bestimmen ● abhängig von vorhandener Hardware ● Funkwellen ● Licht / Laser ● Schall / Ultraschall Wie Topologiemessung? ● inkrementieren der Sendestärke ● Empfangsstärke bestimmen ● Zeitunterschied ● Verbindungen ● Winkel Lateration ● 2D: mind. drei nicht collineare Punkte ● 3D: mind. vier nicht coplanare Punkte ● aber: Bedingungen können aufgeweicht werden Quelle: Hightower, Borriello. „Location Sensing Techniques“ Angulation ● Abstand d bekannt N ● Winkel α und β N messbar α ● festgelegter Vektor, d β z.B. Richtung Nordpol Quelle: Hightower, Borriello. „Location Sensing Techniques“ Verbindungen ● Ankernetz vorhanden ● Position der Anker bekannt ● gleiche Sendereichweite ● „range-free“ Quelle: Hightower, Borriello. „Location Sensing Techniques“ Approximate Point-In- Triangulation Test K' K C B Quelle: He, Huang, Blum, Stankovic, Abdelzaher. „Range-Free Localization Schemes for Large Scale Sensor Network Grid SCAN 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 2 1 1 1 0 0 0 1 2 2 2 1 1 0 0 0 0 3 3 1 1 1 1 0 1 2 3 3 2 1 1 1 0 1 1 2 1 1 0 0 0 0 0 1 1 1 1 0 0 0 Quelle: He, Huang, Blum, Stankovic, Abdelzaher. „Range-Free Localization Schemes for Large Scale Sensor Network Self-Positioning Algorithm jeder Knoten N0 führt aus: 1. finde alle Nachbarn Ni 2. bestimme Abstand zu allen Ni 3. sende diese Daten an alle Ni Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Local View Set N0 N1 d01 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Local View Set N2 d02 d12 N0 N1 d01 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Zwei Local View Sets N3 N2 d03 d02 d12 d34 N0 N1 N0 N4 d01 d04 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Zwei Local View Sets zusammen N4 N2 N3 N0 N1 N3 N4 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Zwei Local View Sets zusammen N2 N4 N0 N1 N3 N4 N3 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Zwei Local View Sets zusammen N2 N4 N0 N1 N4 N3 N3 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Zwei Local View Sets mit neuem Knoten N3 N2 N5 N0 N1 N4 N0 N5 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Zwei Local View Sets vereint N2 N0 N1 N4 N5 N3 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ n-hop entfernte Nachbarn N2 N1 N0 Quelle: Capkun, Hamdi, Hubaux. „GPS-free positioning in mobile ad hoc networkss“ Ende Danke Bastian L. Blywis bastian@blywis.de WS2003/04 FU-Berlin, FB Informatik
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks