Filtern
Erscheinungsjahr
- 2016 (3) (entfernen)
Dokumenttyp
- Bachelorarbeit (2)
- Dissertation (1)
Schlagworte
- Ad-hoc-Netz (1)
- Algorithmische Geometrie (1)
- Beaconless (1)
- Distributed Algorithm (1)
- Drahtloses Sensorsystem (1)
- Drahtloses vermachtes Netz (1)
- Ebener Graph (1)
- Geographic routing (1)
- Geometric spanner (1)
- Graph (1)
Die folgende Arbeit zeigt eine Möglichkeit auf, Lokalisierung eines Objektes mittels Ultraschall zu realisieren. Dazu werden drei bis fünf im Raum verteilte Sensoren genutzt, um anhand von Distanzinformationen die Position eines Objekts relativ zu den Positionen der Sensoren zu bestimmen. Eine Besonderheit besteht dabei darin, dass die Sensoren nahezu beliebig in der Ebene verteilt sein können. Ihre Anordnung wird vom System in der Kalibrierungsphase mit Unterstützung des Anwenders ermittelt. Dabei dürften ein gleichseitiges Dreieck, ein Quadrat oder Pentagramm je nach Sensoranzahl die besten Ergebnisse liefern. Um die relative Bewegung in eine Absolute zu übertragen, findet eine Umrechnung in Meter anhand der Taktung der Mikrocontroller, des Prescalers des verwendeten Timers und der Schallgeschwindigkeit statt.
Die vorliegende Arbeit befasst sich mit der Realisierung eines Schrittmo- tortreibers auf einem 8-Bit Mikrocontroller des Unternehmens Atmel. Der Schwerpunkt liegt hierbei in der Entwicklung einer Stromregelung, welche neben den grundlegenden Betriebsmodi wie Voll- und Halbschritt auch den Mikroschritt ermöglicht. Hierfür wird mithilfe physikalischer und regelungs- technischer Grundlagen ein PI-Regler hergeleitet, welcher auf dem Mikro- controller implementiert wird. In diesem Zusammenhang wird auf die erfor- derlichen Kenntnisse für die praktische Umsetzung eingegangen. Zusätzlich wird die Entwicklung der Hardware dokumentiert, welche für die benötigte Strommessung von großer Bedeutung ist.
Reaktiv lokale Algorithmen sind verteilte Algorithmen, die den Anforderungen großer, batteriebetriebener, Drahtloser Ad Hoc und Sensornetzwerke im besonderen Maße gerecht werden. Durch Vermeidung überflüssiger Nachrichtenübertragungen sowie Verzicht auf proaktive Ermittlung von Nachbarschaftstabellen (d.h. beaconing) minimieren solche Algorithmen den Kommunikationsaufwand und skalieren gut bei wachsender Netzgröße. Auf diese Weise werden Ressourcen wie Bandbreite und Energie geschont, es kommt seltener zu Nachrichtenkollisionen und dadurch zu einer Erhöhung der Paketempfangsrate, sowie einer Reduktion der Latenzen.
Derzeit wird diese Algorithmenklasse hauptsächlich für Geografisches Routing, sowie zur Topologiekontrolle, insbesondere zur Ermittlung der Adjazenzliste eines Knotens in zusammenhängenden, kantenschnittfreien (planaren) Repräsentationen des Netzgraphen, eingesetzt. Ersteres ermöglicht drahtlose multi-hop Kommunikation auf Grundlage von geografischen Knotenpositionen ohne Zuhilfenahme zusätzlicher Netzwerkinfrastruktur, wohingegen Letzteres eine hinreichende Grundlage für effiziente, lokale Lösungen einer Reihe algorithmischer Problemstellungen ist.
Die vorliegende Dissertation liefert neue Erkenntnisse zum Forschungsgebiet der reaktiven Algorithmen, zum Einen auf einer abstrakten Ebene und zum Anderen durch die Einführung neuer Algorithmen.
Erstens betrachtet diese Arbeit reaktive Algorithmen erstmalig im Ganzen und als eigenständiges Forschungsfeld. Es wird eine umfangreiche Literaturstudie zu dieser Thematik präsentiert, welche die aus der Literatur bekannten Algorithmen, Techniken und Anwendungsfelder systematisch auflistet, klassifiziert und einordnet. Weiterhin wird das mathematische Konzept der O- und Omega-reaktiv lokalen Topologiekontrolle eingeführt. Dieses Konzept ermöglicht erstmals die eindeutige Unterscheidung reaktiver von konventionellen, beacon-basierten, verteilten Topologiekontrollalgorithmen. Darüber hinaus dient es als Klassifikationsschema für existierende, sowie zukünftige Algorithmen dieser Art. Zu guter Letzt ermöglicht dieses Konzept grundlegende Aussagen über die Mächtigkeit des reaktiven Prinzips, welche über Entwurf und Analyse von Algorithmen hinaus reichen.
Zweitens werden in dieser Arbeit neue reaktiv lokale Algorithmen zur Topologiekontrolle und Geografischem Routing eingeführt, wobei drahtlose Netze durch Unit Disk bzw. Quasi Unit Disk Graphen modelliert werden. Diese Algorithmen berechnen für einen gegebenen Knoten die lokale Sicht auf zusammenhängende, planare, Euklidische bzw. Topologische Spanner mit konstanter Spannrate bzgl. des Netzgraphen und routen Nachrichten reaktiv entlang der Kanten dieser Spanner, wobei die Nachrichtenauslieferung garantiert wird. Alle bisher bekannten Verfahren sind entweder nicht reaktiv oder gewährleisten keine konstanten Euklidischen oder Topologischen Spannraten. Ein wesentliches Teilergebnis dieser Arbeit ist der Nachweis, dass die partielle Delaunay Triangulierung (PDT) ein Euklidischer Spanner mit konstanter Spannrate für Unit Disk Graphen ist.
Die in dieser Dissertation gewonnenen Erkenntnisse bilden die Basis für grundlegende und strukturierte Forschung auf diesem Gebiet und zeigen, dass das reaktive Prinzip ein wichtiges Werkzeug des Algorithmenentwurfs für Drahtlose Ad Hoc und Sensornetzwerke ist.