Schwarmbasiertes Multipath-Routing in Sensornetzen

Inhaltsverzeichnis

1 Einleitung
1.1 Motivation
1.2 Ziele
1.3 Probleme
1.4 Aufbau der Arbeit

2 Grundlagen
2.1 Sensornetze
2.1.1 Einsatzgebiete
2.1.2 Design
2.1.3 Besonderheiten
2.1.4 Kommunikation
2.1.5 Technologien
2.1.6 Anwendungen
2.2 Schwarmintelligenz
2.2.1 Selbstorganisation und Emergenz
2.2.2 Modellierung schwarmbasierter Verhaltensweisen
2.2.3 Mechanismen
2.2.4 Vorteile
2.2.5 Schwarmbasierte Anwendungen
2.2.6 Ausblick

3 Routing in Sensornetzen
3.1 Allgemeine Konzepte
3.1.1 Fluten und Gossiping
3.1.2 Multipath-Routing
3.1.3 Aggregation
3.1.4 Energiebewusstes Routing
3.2 Strategien
3.2.1 Datenzentrisches Routing
3.2.2 Lokationsbewusstes Routing
3.2.3 Hierarchisches Routing
3.2.4 Andere Arten von Routing
3.3 Systeme
3.3.1 Cougar
3.3.2 TinyDB
3.3.3 TiNA
3.4 Verwandte Arbeiten
3.4.1 Schwarmbasiertes Multipath-Routing in MANETs
3.4.2 Schwarmintelligenz in Sensornetzen
3.4.3 Amorphous Computing
3.4.4 Andere

4 Ein schwarmbasierter Routing-Algorithmus für Sensornetze
4.1 Anforderungen an den Algorithmus
4.2 Bestimmung eines angestrebten Schwarmverhaltens
4.2.1 Energieeffizientes Multipath-Routing
4.2.2 Ein Ansatz für Sensornetze
4.3 Interaktionsmechanismen
4.3.1 Etablierung von Pfaden: Erforschen und Fluten
4.3.2 Positives und negatives Feedback
4.3.3 Aggregation
4.4 Strategie des Algorithmus
4.4.1 Nachrichtentypen
4.4.2 Reguläre Arbeitsweise
4.4.3 Erweiterungen

5 Implementierung
5.1 Eingesetzte Software
5.1.1 C++
5.1.2 OTcl
5.1.3 Der Netzwerk-Simulator ns-2
5.2 Routing-Agent
5.3 Pakete
5.4 Vergleichs-Algorithmus

6 Simulation und Evaluierung
6.1 Simulationsszenarien
6.1.1 Aufbau
6.1.2 Parameter des Schwarm-Algorithmus
6.2 Vergleich der Algorithmen
6.2.1 Topologie T1
6.2.2 Topologie T2

7 Zusammenfassung
7.1 Bewertung
7.2 Ausblick

Literaturverzeichnis

Einleitung

Sensornetze stellen eine neuartige Technologie dar, deren Realisierung erst durch technische Fortschritte der letzten Jahre, wie die Entwicklung immer kleinerer Computerkomponenten, ermöglicht wurde. Im Vergleich zu herkömmlichen Computer-Netzwerken bestehen Sensornetze aus einer vergleichsweise großen Anzahl von Knoten. Mittels diverser Sensoren sind die Knoten imstande, Ereignisse in ihrer Umgebung wahrzunehmen.

Die Aufgabe der Sensorknoten ist die Beobachtung der Umwelt und das Berichten besonderer Ereignisse an eine Basisstation. Sensornetze stellen somit eine Verbindung zwischen der realen Welt und der informationstechnischen Welt der Computer dar [1].

Sensornetze müssen zur Selbstorganisation im Stande sein: Zum einen erschwert die große Anzahl der Knoten eine effektive Wartung. Zum anderen existieren Ansätze, um Sensornetze in schwer zugänglichen Gebieten fernab der Zivilisation einzusetzen. Sensorknoten werden i. Allg. mittels einer Batterie betrieben. Falls sie keine Möglichkeit - wie z.B. Solarzellen - besitzen, um sich wieder aufzuladen, ist ihre Lebenszeit begrenzt.

Auf dem Weg bis zur Integration dieser Technologie in unser alltägliches Leben sind noch zahlreiche Herausforderungen zu lösen. Ein Mittel dazu könnte Schwarmintelligenz darstellen.

Schwarmintelligenz ist ein Konzept, welches durch Verhaltensweisen von Schwärmen (besonders die von Ameisen bei der Nahrungssuche) inspiriert wurde. Das Ziel dieses Ansatzes ist es, spezielle Verhaltensweisen zu imitieren und in technischen Anwendungen somit auch deren Vorteile zu nutzen. Bei Schwärmen entsteht scheinbar intelligentes Verhalten aufgrund der Interaktionen der einzelnen Individuen, welche selbst nur ein einziges, individuelles Ziel verfolgen. Durch die spezielle Art der Interaktion wird der Schwarm zu mehr als nur der Summe seiner einzelnen Teile. Ein besonderer Vorteil im Hinblick auf die technische Umsetzung dieses Verhaltens ist die Tatsache, dass Individuen in Schwärmen größtenteils ohne direkte Kommunikation auskommen. In verteilten Systemen stellt Kommunikation, ganz abgesehen von den damit verbundenen Problemen der zeitlichen Verzögerung, auch einen Ressourcen belastenden Prozess dar [2].

1.1 Motivation

Schwarmbasierte Algorithmen besitzen einige besondere Eigenschaften, die sie für den Einsatz in Sensornetzen prädestinieren:

- Schwärme bestehen aus einer großen Anzahl von Individuen, trotzdem sind sie imstande, sich effektiv selbst zu organisieren, und sie sind gemeinsam zu erstaunlichen Leistungen fähig [2, 3]. Informationstechnische schwarmbasierte Anwendungen, die diese Eigenschaften erfolgreich imitieren, besitzen damit eine gute Skalierbarkeit. Zeigen schwarmbasierte Routing-Algorithmen für gebräuchliche Kommunikationsnetzwerke bereits beachtliche Leistungen, so sollte dies im Besonderen auch für Sensornetze gelten, die sich durch eine außerordentlich große Anzahl von Knoten auszeichnen.
- In Schwärmen existiert keine zentrale Kontrollinstanz, statt dessen resultiert ihre Selbstorganisation aus den Interaktionen relativ homogener Individuen. Dadurch verhalten sich schwarmbasierte Anwendungen robust gegenüber dem Ausfall einzelner Komponenten. Die Verhaltensmuster der einzelnen Individuen in Schwärmen sind vergleichsweise simpel. Da diese Verhaltensmuster darüber hinaus identisch sind, erleichtert dies die Implementierung schwarmbasierter Algorithmen [2].

Das Amorphou Computing Project am Massachusetts Institute of Technologyhat es sich zum Ziel gesetzt, Mechanismen zu identifizieren, mittels deren sich große Mengen programmierbarer Einheiten beobachten, kontrollieren und organisieren lassen.¹ Ein Computer-Netzwerk, welches diese Mechanismen nutzt, wird als A morphous Computer bezeichnet. Eine mögliche Anwendung dieser Technologie wären programmierbare Materialien“, d.h. Materialien, die Sensorknoten enthalten, aber noch daru” er hinausgehende Möglichkeiten besitzen, aktiv auf ihre Umwelt einzuwirken.

Ein Anwendungsbeispiel wäre smartskin für Flugzeuge: Dieses Material besteht aus einem Netzwerk aus Sensoren und beweglichen mechanischen Teilen, die in den Flügel eingebettet sind. Der Flügel kann sich an die aerodynamischen Gegebenheiten anpassen und immer die effizienteste Form für die gegenwärtigen Bedingungen annehmen [4].

1.2 Ziele

Zahlreiche technische Probleme im Bereich der Sensornetze sind noch weitgehend ungelöst, so z.B. die Frage eines möglichst effizienten Energiemanagements.

Ziel dieser Arbeit ist die Entwicklung eines schwarmbasierten Routing-Algorithmus, der es ermöglicht, die Ressourcen eines Sensornetzes effizient zu nutzen. Dies soll die Lebenszeit des Netzwerks verlängern und gleichzeitig eine möglichst große Abdeckung des mittels Sensoren überwachten Gebietes ermöglichen.

Multipath-Routing hat sich als Strategie zur energieeffizienten Verteilung der Netzlast in Sensornetzen bewährt [5]. Deshalb soll in dieser Arbeit der Einsatz von Multipath-Routing mittels eines schwarmbasierten Mechanismus entwickelt werden.

Sensornetze sind in zahlreichen Szenarien für eine Vielfalt von Aufgaben einsetzbar. Der entwickelte Algorithmus soll einfache, universell einsetzbare Mechanismen nutzen, um ein möglichst breites Einsatzgebiet zu ermöglichen.

1.3 Probleme

Selbstorganisation ist in Schwärmen kein Ergebnis zielgerichteter Bemühungen, sondern manifestiert sich emergent . Dies bedeutet, dass Organisation nur ein Nebeneffekt der kombinierten Verhaltensweisen sämtlicher Individuen ist. Es ist allerdings kaum erforscht, wie sich Algorithmen entwerfen lassen, die Leistungen zeigen, für die sie nicht explizit entwickelt wurden [4].

Zur Entwicklung eines Ansatzes werden in dieser Arbeit die Mechanismen bewährter (schwarmbasierter und anderer) Routing-Algorithmen analysiert. Um den besonderen Bedingungen in Sensornetzen zu genügen, ist es notwendig, die adaptierten Mechanismen anzupassen.

1.4 Aufbau der Arbeit

Im folgenden Kapitel 2 werden die Grundlagen dieser Arbeitet erläutert.

In Abschnitt 2.1 werden Eigenschaften von Sensornetzen diskutiert. Hierbei wird auf Unterschiede zwischen verschiedenen Anwendungen eingegangen und es werden existierende Technologien vorgestellt.

In Abschnitt 2.2 wird auf das Prinzip der Schwarmintelligenz eingegangen. Es werden grundlegende Machanismen und zwei schwarmbasierte Routing-Algorithmen besprochen.

In Kapitel 3 werden aktuelle Routing-Algorithmen für Sensornetze vorgestellt, die unterschiedliche Strategien verfolgen. Es werden einige aktuelle Systeme vorgestellt, die es gestatten, das Sensornetz wie eine verteilte Datenbank abzufragen. Abschließend wird auf verwandte Arbeiten eingegangen.

Anschließend wird in Kapitel 4 ein schwarmbasierter Routing-Algorithmus entwickelt, der eine Multipath-Strategie verfolgt. Zuerst werden lokale Mechanismen entwickelt, die ein erwünschtes globales Verhalten des Algorithmus erzeugen sollen. Diese Mechanismen werden anschließend in einen Algorithmus integriert.

In Kapitel 5 wird näher auf die Implementierung eines Routing-Agenten eingegangen, der den erarbeiteten Algorithmus ausführt. Außerdem wird näher auf die Simulationsumgebung eingegangen.

Der Algorithmus wurde in mehreren Szenarien getestet und mit einem alternativen Routing- Algorithmus verglichen. Die Auswertung diverser Versuche befindet sich in Kapitel 6.

Abschließend wird in Kapitel 7 die geleistete Arbeit zusammengefasst und bewertet. Ferner wird ein Ausblick auf weiterführende und ausstehende Aspekte der Arbeit gegeben.

2.Grundlagen

2.1 Sensornetze

Fortschritte in den Bereichen der drahtlosen Übertragungstechnik und Mikroelektronik haben die Entwicklung von Sensornetzwerken ermöglicht. Diese Netzwerke bestehen aus zahlreichen kleinen und kostengünstigen Knoten, die über einen begrenzten Energievorrat verfügen. Einsatzgebiete solcher Netzwerke sind u.a. Überwachungsaufgaben in schwer zugänglichem Gelände.

Die Knoten sind mit Sensoren ausgestattet, die gewisse Schlüsselsignale wahrnehmen können. Die Knoten werden im Allgemeinen in und um das zu beobachtende Phänomen plaziert. Aufgabe des Netzwerkes ist es, mittels der Sensoren wahrgenommene Ereignisse, z.B. Anstieg der Temperatur über ein Höchstmaß, an andere Teile des Netzwerkes zu übertragen. Man spricht bei den Sensoren deshalb auch von Quellen, bei den Empfängern der Daten innerhalb des Sensornetzes von Senken. Senken können häufig die gewonnenen Daten aus dem Sensornetzwerk hinaus übermitteln. Eine Senke wird gelegentlich auch als Basisstation bezeichnet. Aufgrund der kritischen Einsatzgebiete ist es möglicherweise notwendig, dass die Sensorknoten über dem Zielgebiet abgeworfen werden müssen. Deshalb ist es erforderlich, dass das Netzwerk über selbstorganisierende Fähigkeiten verfügt. Dies ist besonders problematisch, da ein Merkmal von Sensornetzen ihre hohe Anzahl von Knoten ist, denn sie werden über ein großes Gebiet, bzw. in einer hohen Dichte verteilt. Da die Knoten nicht alle in Sichtweite der Senke liegen, wird in der Regel über Multi-Hop-Routing kommuniziert (siehe Unterabschnitt 2.1.4).

Sensornetze besitzen viele Vorteile gegenüber herkömmlichen Sensor-Systemen. Durch die bestehende Redundanz ist das System weitgehend resistent gegenüber dem Ausfall von Komponenten [6]. Darüber hinaus bieten diverse Sensoren unterschiedliche Perspektiven auf das zu untersuchende Phänomen an. Es ergeben sich durch die Besonderheiten von Sensornetzen völlig neue Anwendungsgebiete für sie.

Mögliche Einsatzgebiete für Sensornetze werden in Unterabschnitt 2.1.1 diskutiert. Abhängig von dessen Verwendunsgzweck können bei der Entwicklung eines Sensornetzes unterschiedliche Designentscheidungen getroffen werden. Diese werden in Unterabschnitt 2.1.2 besprochen. Ein Überblick über die Besonderheiten von Sensornetzen, die es von herkömmlichen Netzwer- ken unterscheiden, wird in Unterabschnitt 2.1.3 gegeben. Gegenwärtigen Entwicklungen der Sensornetzwerk-Technologie in Bezug auf die Bitübertragungsschicht und MAC-Schicht werden in Unterabschnitt 2.1.4 beschrieben. In Unterabschnitt 2.1.5 werden aktuelle Technologien für Sensornetze vorgestellt. Dieser Abschnitt wir abgeschlossen von einem Überblick über aktuelle Anwendungen für Sensornetze, der in Unterabschnitt 2.1.6 gegeben wird.

2.1.1 Einsatzgebiete

Umweltforschung Die Anpassungsfähigkeit von Sensornetzen ermöglicht den Einsatz in für Menschen nur schlecht zugänglichen Gebieten. Auch für die Erforschung des Verhaltens diverser Tierarten eignen sich Sensornetze. Sie ermöglichen es, Tiere über einen langen Zeitraum in deren natürlichem Habitat und ohne den störenden Eingriff von Menschen zu beobachten. Darüber hinaus sind sie imstande, das Verhalten besonders kleiner Arten in einem größeren Zusammenhang (massenhaft, simultan und über ein großes Gebiet verstreut) zu betrachten [7, 1].

Katastropheneinsatz Die Vielzahl möglicher Sensoren, mit denen sich Sensorknoten ausstatten lassen, prädestinieren Sensornetze zur Erkennung einer Vielzahl von gefährlichen Substanzen (chemisch, biologisch oder radioaktiv). In diese Kategorie läßt sich auch der Einsatz von Sen- sornetzen zur Erkennung und Vermeidung von Waldbränden einordnen. Bereits realisiert wurde ein System zur Erkennung von Überschwemmungen [7].

Militär Ein mögliches Einsatzgebiet ist die Überwachung von kritischem Terrain [7, 1], d.h. Fahrzeuge und Personen werden mittels Druck-, Bildund Infrarotsensoren entdeckt. Mobile Objekte können identifiziert und deren Bewegungen verfolgt werden. Zahlreiche Arbeiten zu Sensornetzen werden von der DARPA gefördert.

Medizin Vorstellbar ist die Überwachung physiologischer Daten von Patienten in einem Krankenhaus oder Altenheim. Die Position von Patienten und A¨ rzten kann überwacht werden, oder in einem Altenheim kann der Sturz eines Patienten erkannt werden [7]. In ferner Zukunft könnte es möglich sein, Sensoren direkt in den Blutkreislauf eines Patienten zu injizieren [8].

Industrie Durch die inhärente Redundanz eignen sich Sensornetze hervorragend zur Produktkontrolle [7, 8]. Sie sind beispielsweise geeignet, Mikrofrakturen in Materialien zu entdecken.

Ökonomie Im Handel sind Sensornetze zur Inventur innerhalb von Lagerhäusern und Fabriken geeignet [7], möglicherweise in Verbindung mit Smart Labels . Es ist möglich, dass in naher Zukunft jedes Warenobjekt einen solchen Chip, der sämtliche für den Weiterverkauf relevanten Daten enthält, trägt. Diese passiven Chips, die keine Energieversorgung besitzen, können per Funk abgefragt und durch ein Sensornetzwerk verwaltet werden.

Heimanwendungen In Gebäuden könnten Sensornetze zur Messung von Temperatur und Luftfeuchtigkeit genutzt werden [8]. Die Vernetzung aller heimtechnischen Geräte realisisiert das Smart Environment [7]. D.h. Kühlschränke, die Lebensmittel nachbestellen, wenn sie fast verbraucht sind und andere technische Geräte, die sich auf den Benutzer einstellen. Bereits 1988 formuliert Mark Weiser die Idee des Ubiquitous Computing , d.h. in alltäglichen Gebrauchsgegenständen verborgene Sensorknoten, die zu einer Vernetzung unserer Umwelt führen und die Bereitstellung von Informationen und deren Zugriff über sämtliche Objekte in dieser vernetzten Welt ermöglichen.

2.1.2 Design

Abhängig vom Einsatzgebiet müssen Sensornetze besonders unscheinbar, langlebig, leistungsstark oder alles auf einmal sein. Sensornetze, die zur Erforschung seltener Arten verwendet werden, sollten die Untersuchungsobjekte nicht in deren natürlichem Verhalten beinflussen. Sensornetze, die zur Erkennung von Waldbränden in abgelegenen Wäldern eingesetzt werden, sollten möglichst wenig Wartung benötigen und eine hohe Lebensdauer besitzen. Ein Sensornetzwerk hingegen, welches zur Bestimmung von Unterwasserströmungen benutzt wird, sollte aus Knoten bestehen, die die Strömung möglichst wenig beeinflussen.

Es gibt Ansätze für Sensornetze, die Zugang zu einer Energieversorgung besitzen [9], und solche, die fernab der Zivilisation (oder aus Gründen der Autonomie) auf Batterien angewiesen sind - die Mehrheit aller Ansätze geht von batteriebetriebenenen Sensorknoten aus. Zwischen diesen beiden Möglichkeiten sind auch Hybridlösungen vorstellbar, wie Sensornetze, in denen einige Knoten in der Lage sind (z.B. über Solarzellen), Energie aus der Umwelt zu beziehen. Andere Knoten ko¨nnten sich mittels solcher Tankstellen“ wieder aufladen.

Je nach Aufgabe müssen Sensornetze einen charakteristischen Informationsfluß ermöglichen: Zulieferung einer Alarm-Nachricht an die Senke, ausschließlich bei Erkennen eines speziellen Ereignisses, Garantie eines regelmäßigen Streams oder Ablieferung repräsentativer Durchschnittswerte. Häufig wird davon ausgegangen, dass die Senke über eine externe Verbindung wie z.B. eine Satellitenverbindung mit einer Kontrollinstanz oder dem Internet verbunden ist [6]. Alternativ könnte eine Senke einen Datenspeicher enthalten, dessen Inhalt manuell kopiert wird. Es gibt außerdem Szenarien, in denen aus Gründen der Redundanz von mehreren Senken ausgegangen wird. Von der Senke aus könnten sämtliche beobachteten Ereignisse aus dem Sensornetzerk übertragen werden. Oder es ist möglich, das Sensornetzwerk als eine verteilte Datenbank zu betrachten, die von externen Abfragen durchsucht wird (siehe Abschnitt 3.3).

Eine Klassifizierung bestehender Sensornetzmodelle wird von Sastry et al. in [6] durchgeführt. Sie bestimmen vier Charakteristika von Architekturen für Sensornetze, die Designentscheidungen beeinflussen:

- Input: Notwendig ist die Konvertierung der Sensormessungen in eine Form, die zur Weiterverarbeitung geeignet ist.
- Berechnungen: Die Fähigkeit zu verteilten Berechnungen ermöglicht dem Sensornetz die Bewältigung einer Vielzahl von Aufgaben.
- Kommunikation: Der Transport von Daten ist die primäre Funktion des Sensornetzes; häufig werden Daten in andere Netzwerke übertragen.
- Programmierung: Dieser Aspekt wird häufig ignoriert, allerdings ist die Implementierung ein kritischer Aufgabenbereich, der verteilte Dienstleistungen und Fehlerbehandlungen ermöglichen muß.

Diese Charakteristika beziehen sich auf die Funktion und Implementierung eines Sensornetzes. Parallel zu diesen softwaretechnischen Designentscheidungen fordern die Umstände des Einsatzgebietes den Entwurf besonderer Hardware.

Neben besonderen Anforderungen an das Design der Hardware der Sensorknoten führt die Wahl des Einsatzgebietes zur Notwendigkeit besonderer Sensortypen, über die die Knoten verfügen müssen.

Sensorknoten beispielsweise, die die Temperaturverteilung im Meer messen, müssen wasserdicht konstruiert sein und schwimmen können (vgl. Unterabschnitt 2.1.6).

Von Advantaca sind Knoten entwickelt worden, die sich im Inneren zweier konzentrischer Kugeln befinden, wobei die innere Kugel um eine Achse in der äußeren Kugel rotiert. Nachdem solche Knoten aus der Luft abgeworfen wurden ist sichergestellt, dass die Antenne immer nach oben zeigt [1].

Sensorknoten im Bereich von Umweltforschung und Militär sollen häufig gut getarnt sein, um eine Entdeckung zu vermeiden. Neben einer Miniaturisierung der Hardware, um eine geringe

Größe der Knoten (siehe auch Unterabschnitt 2.1.3) zu erreichen, ist es möglich die Knoten als Steine oder A¨ ste zu tarnen [1].

2.1.3 Besonderheiten

Wie bereits im letzten Unterabschnitt gezeigt wurde, stellen die vielfältigen Einsatzgebiete für Sensornetze teilweise sehr spezielle Anforderungern an deren Eigenschaften. In diesem Unterabschnitt soll auf Besonderheiten von Sensornetzen eingegangen werden, die sie von herkömmlichen Netzwerken unterscheiden.

Miniaturisierung

Für zahlreiche Anwendungen ist eine möglichst geringe Größe der einzelnen Sensorknoten notwendig [10]. Die Miniaturisierung der Hardware ist ein essentieller Bestandteile der Entwicklung von Hardware für Sensornetze, wie z.B. im Smart Dust -Projekt (siehe Unterabschnitt 2.1.5).

Einer der größten Nachteile einer geringen Knotengröße ist eine Begrenzung der verfügbaren Energiereserven.

Energieeffizienz

Die Minderheit aller Ansätze für Sensornetze geht von Knoten mit einer Möglichkeit zur Energiegewinnung aus. Die Menge an Energie, die sich momentan aus der Umgebung gewinnen läßt, liegt im Bereich von 100 µ W. Energie ließe sich möglicherweise gewinnen aus Vibrationen, Umgebungswärme oder Licht [4]. Zu den Bauteilen, die Energie benötigen, zählen: Prozessor, Speicher, Funkanlage und Sensoren [11].

Deshalb ist es notwendig, um eine möglichst lange Laufzeit eines Sensornetzes zu garantieren, den Energieverbrauch im laufenden Betrieb zu minimieren. Es existieren für Hardware- Komponenten, die Energie beanspruchen, zahlreiche Möglichkeiten, den Verbrauch zu verringern:

Eine Reduzierung des Energieverbrauchs läßt sich bereits durch die Wahl besonderer Materialien für Transistoren, Gatter, usw. erreichen [11]. Mittels D ynamic Voltage Scaling (DVS) läßt sich der Energieverbrauch im laufenden Betrieb, durch Anpassung der anliegenden Spannung, regulieren [12]. Das Abschalten von ungenutzten Komponenten läßt sich in diversen Granularitäten erreichen [11].¹ Dies hat zur Entwicklung von Systemen geführt, die zwischen diversen Operations-Modi mit unterschiedlichem Energieverbrauch (und somit einer unterschiedlichen Anzahl nutzbarer System-Komponenten) wechseln können.

In Fällen, in denen das Betriebsystem eines eingebetteten Systems oder Sensornetzes für die Regulierung des Energieverbrauchs zuständig ist, wird von dynamic power management (DPM) [12] gesprochen.

Für Sensoren läßt sich pauschal sagen, dass der Energieverbrauch passiver Sensoren (Temperatur, Luftfeuchtigkeit, etc.) so gering ist, dass er im Vergleich zum Verbrauch anderer Hardwarekomponenten vernachlässigbar ist. Aktive Sensoren hingegen (Kameras, Sonar, etc.) können einen sehr hohen Energieverbrauch haben [13].

Der Großteil der Energie wird i. Allg. allerdings nicht für Prozesse an den Knoten benötigt, sondern wird durch die Kommunikation mittels der Funkanlage (siehe übernächster Unterabschnitt 2.1.4) verbraucht: Es wird 100-1000 mal so viel Energie für die Übertragung eines Bits benötigt, wie für die Ausführung einer Operation [8]. Ein Ziel vieler Routing-Algorithmen für Sensornetze ist es deshalb, durch eine möglichst geringe Anzahl versandter Nachrichten den Energieverbrauch der Funkanlage so gering wie möglich zu halten.

Eine eingeschaltete Funkanlage verbraucht aber auch dann noch Energie, wenn sie nicht sendet oder empfängt. Einige Routing-Algorithmen versuchen deshalb, die Funkanlagen der Knoten zu inaktiven Zeiten auszuschalten. Diese Strategie wird näher in Unterabschnitt 3.1.4 diskutiert. Im folgenden wird ein System-Modus, in dem die Funkanlage ausgeschaltet ist, als sleep -Modus bezeichnet.

Die Unterschiede im Energieverbrauch der Funkanlage können zwischen diversen Typen von Sensorknoten schwanken: Rockwell’s Wins Nodes verbrauchen im untätigen (aktiviert, aber nicht sendend oder empfangend) Zustand fast genau soviel (97%) Energie wie wärend des Empfangs, wärend des Sendens wird 25% mehr Energie verbraucht; bei Medusa II Nodes ergibt sich (bei maximaler Sendeenergie) das gleiche Verhältnis, wie in [13] beschrieben wurde. Stojmenovic et al. erwähnen zwei getestete, ältere Funkanlagen, wobei bei einem Typ das Verhältnis des Energiverbrauchs von aktiviert zu empfangend zu sendend 0,12:1:2 beträgt; bei dem anderen liegt dieses Verhältnis bei 0,0045:1:1,36.

Selbstorganisation

In einigen Szenarien für Sensornetze wird von einer zufälligen Verteilung der Sensorknoten ausgegangen. Sensorknoten benötigen in diesem Fall die Fähigkeit, selbständig eine Routing-Topologie etablieren zu können. Auch im laufenden Betrieb müssen die Knoten ggf. autonome Entscheidung treffen und in der Lage sein, sich neu konfigurieren zu können [8].

Sensornetze besitzen somit einige A¨ hnlichkeiten mit Ad Hoc -Netzwerken [1, 14]. Auch bei diesen ist Energieeffizienz ein vorrangiges Ziel.

Nach Schiller könnten die Knoten mittels eines Mechanismus der MAC-Schicht den Aufbau der Topologie erreichen (vgl. Unterabschnitt 2.1.4).

Wie Brooks in [15] schreibt, ist die Fähigkeit zur Selbstorganisation eines der wichtigsten Merkmale, die ein Sensornetz besitzen muss, besonders um sich an unvorhergesehene Ereignisse anzupassen.

Mobilität

Für einige Anwendungen wird die Mobilität der Sensorknoten vorausgesetzt, wie sie z.B. im Smart Dust -Projekt (siehe Unterabschnitt 2.1.5) geplant ist. Gegenwärtig werden bei ZebraNet (siehe Unterabschnitt 2.1.6) mobile Knoten genutzt.

Diverse Technologien - wie z.B. GPS - und Routing-Strategien, die in MANETs (Mobile Ad Hoc NETworks) eingesetzt wurden, sind augrund der Ad Hoc -Eigenschaften von Sensornetzen auch für mobile Sensornetze nutzbar.

Die Mehrheit der Ansätze für Sensornetze geht allerdings von immobilen Knoten aus [16].

2.1.4 Kommunikation

Funkübertragung

Die meisten Projekte zur Entwicklung von Technologie für Sensornetze gehen von einer Funkübertragung auf der Bitübertragungsschicht aus [4]. Dieser Ansatz birgt einige Probleme:

- Der Abdeckungsbereich eines sendenen Knotens ist in den seltensten Fällen kreisförmig, meistens nicht einmal konvex, häufig nicht einmal kontinuierlich [17]. Viele der in Unterabschnitt 3.2.2 genannten Algorithmen gehen allerdings von der Prämisse kreisförmiger Sendebereiche aus, ihr Einsatzgebiet wäre also möglicherweise stark eingeschränkt.

- Die Übertragungsqualität der Funkverbindung zwischen zwei Knoten kann stark variieren, d.h die Eigenschaften der Verbindung in Hinsicht auf Fehleranfälligkeit der Paketübertragung und Konnektivität können sich über die Zeit ändern.
- Es ist nicht davon auszugehen, dass alle Verbindungen symmetrisch sind, d.h. es ist möglich, dass Knoten Nachbarn besitzen, von denen sie Nachrichten empfangen können, aber nicht vice versa [18].
- Hindernisse können unabhängig von der Entfernung zwischen zwei Knoten auftauchen. Beispielsweise kann ein Knoten in einer Mulde liegen und nur zu einem entfernten aber hoch gelegenen anderen Knoten eine Verbindung haben.
- Der Energiverbrauch e einer Funkübertragung steigt exponentiell mit der Distanz d der Übertragung. Wird normalerweise davon ausgegangen, dass e ≈ d n mit n = 2, so wird in Sensornetzen hingegen von 2 ≤ n ≤ 4 ausgegangen: Sensorknoten werden häufig nahe des

Erdbodens platziert. Der Grund dämpft Funkwellen, so dass der Energieverbrauch einer Übertragung erhöht werden muss [14].² Sensornetze nutzen meistens Multi-Hop-Routing, da dadurch die Transmissionsreichweite eines Knotens - und damit dessen Energieverbrauch - reduziert werden kann [7].

Diese Probleme treten bei starker Bebauung, seltener aber in Umgebungen wie Straßen, Parkplätzen und offenen städtischen Gebieten auf [18]. Die Ursache für die Probleme liegt - neben der Dämpfung durch den Grund - darin, dass Funksignale diversen Störfaktoren unterliegen. In Bereichen mit vielen Hindernissen werden Probleme besonders verursacht durch an Objekten reflektierte Signale, die sich mit anderen Signalen überlagern. Diese und andere charakteristischen Probleme der Funkübertragung werden genauer in [19] diskutiert.

Funk ist ein Broadcast-Medium. Mit einer zunehmenden Dichte von Knoten erhöht sich deshalb (bei gleichbleibender Funkreichweite) die Wahrscheinlichkeit von Kollisionen. Ein Ansatz zur Verringerung dieser Wahrscheinlichkeit besteht im Einsatz von gerichteten Antennen, die Übertragungen innerhalb eines festen Winkels ermöglichen [14].

MAC-Schicht

Die MAC (Medium Access Control)-Schicht regelt den Zugang zum Übertragungsmedium.Versuche mit aktueller Hardware für Sensornetze zeigen, dass besonders in Umgebungen wie Gebäuden und freier Natur eine Vielzahl von Problemen im Zusammenhang mit der Funkübertragung zu lösen ist (vgl. letzter Unterabschnitt).

Aufgrund der geringen Diversität an gegenwärtig verfügbarer Hardware für Sensornetze ist es noch fraglich, ob die oben genannten Probleme durch neue Technologien nicht schon auf der

Bitübertragungsschicht zu lösen sind.³ Es besteht außerdem die Gefahr asymmetrischer Verbindungen.

Es existieren viele verschiedene Ansichten in Bezug auf die Frage, welche weiteren Dienste von der MAC-Schicht in Sensornetzen geleistet werden sollen. Von Muraleedharan & Osadciw wird in [20] vorgeschlagen, zur Optimierung der Leistung und Energieersparnis die Sicherungsschicht mit der Vermittlungsschicht zu verschmelzen.

Aufgrund der Vielzahl von Störungsquellen für Funkverkehr in Sensornetzen wird von Zhao et al. in [18] vorgeschlagen, dass auf der MAC-Schicht die zugrunde liegende Netzwerktopologie festgelegt wird, die nur aus zuverlässigen Verbindungen besteht. Darüber hinaus ist es möglich, die Anzahl der zu erreichenden Knoten durch Verstärkung der Signalstärke zu erhöhen.

Von Schiller wird in [21] vorgeschlagen, die Sendestärke eines Knotens anzupassen, so dass eine feste Anzahl anderer Knoten erreicht wird. Eine zu hohe Anzahl an Verbindungen führt zu einer Erhöhung der Wahrscheinlichkeit, dass es zu Kollisionen kommt. Deshalb ließe sich mit diesem Ansatz Kollisionen entgegen wirken.

In einigen Veruchen und Simulationen wird 802.11 [19] als MAC-Protokoll für Sensornetze eingesetzt (z.B. in [21]). Um Kollisionen zu vermeiden werden folgende Mechanismen eingesetzt: Zuerst wird überprüft, ob der Übertragungskanal bereits benutzt wird. Ist dies der Fall, so wird mit der Übertragung gewartet und der Kanal wird nach einer zufällig ermittelten Zeitspanne erneut überprüft. Dieser Mechanismus wird als Carrier Sense Medium Access with Collision A voidance (C SM A/CA) bezeichnet.

Vor dem Senden eines Datenpakets, sendet der Start-Knoten eine Ready t o Send (RTS) -Anfrage, der Empfänger antwortet, falls die Verbindung frei ist, mit einer Clear to Send (CTS) -Nachricht. Erst bei Empfang dieser Nachricht sendet der Start-Knoten das Datenpaket. Der Empfänger beantwortet dieses Paket mit einer A cknowledgemen t ( ACK ) -Nachricht, um den Startknoten über den erfolgreichen Empfang zu informieren.

Es ist für viele Anwendungen nicht möglich, die in 802.11 erreichten hohen Datenraten zu realisieren, da diese mit einem hohen Energieverbrauch verbunden ist.

Der R TS/CTS -Mechanismus ist für zahlreiche Sensornetzwerk-Anwendungen allerdings nicht geeignet, da die zusätzlich verbrauchte Energie nicht für die vermiedenen Kollisionen kompensiert. [22, 18]

Der CSMA/CA -Mechanismus hingegen wird von einigen heute verfügbaren Knoten eingesetzt (vgl. Unterabschnitt 2.1.5).

PAMAS (P ower- A ware Mul t iple A ccess protocol with Signalling) ist ein von Singh et al. entwikkeltes und in [22] vorgestelltes MAC-Protokoll für A d Hoc -Netzwerke. PAMAS macht sich die Tatsache zunutze, dass von mehreren Knoten, die sich jeweils innerhalb gegenseitiger Funkreichweite befinden, nur einer zu einem Zeitpunkt senden kann. Sensorknoten, die eine Transmission anderer Knoten mithören, gehen deshalb für eine bestimmte Zeit in einen sleep -Modus.

SMAC (sensor-MAC) [23] von Ye et al. ist ein von PAMAS inspiriertes MAC-Protokoll für Sensornetze. Ziel ist es, die Knoten möglichst effizient in Phasen der Untätigkeit in einen sleep - Modus zu versetzen. Benachbarte Knoten bilden hierzu Gruppen, als vir t ual clus t er bezeichnet, die sich mittels sogenannter sleep schedules synchronisieren. D.h. Knoten innerhalb eines vir t ual cl u ster s tauschen Informationen darüber aus, wann sie planen aktiv zu sein und wann sie ihren sleep -Modus aktivieren wollen. Ziel eines Knotens ist es, dann in den sleep -Modus zu gehen, wenn andere Knoten des vir t ual cluster s aktiv sind.

Ein andererer Ansatz zur Energiersparnis mittels eines MAC-Protokolls wird von den Entwicklern der PicoNode im Rahmen des PicoRadio Projektes (siehe auch Unterabschnitt 2.1.5) in [24] vorgeschlagen: Jeder Knoten besitzt zwei Funkempfänger: Einer ist immer aktiv, arbeitet aber mit einer sehr geringen Bitrate und verbraucht deshalb auch nur wenig Energie. Der andere Empfänger arbeitet mit einer höheren Bitrate und verbraucht mehr Energie, ist aber nur ca. 1% der Zeit aktiv.

Möchte ein Knoten eine Nachricht übertragen, sendet er vorher ein Wecksignal samt der Knoten- ID des Zielknotens. Dieses Signal wird von dem Zielknoten mittels des energiesparenden Funkempfängers erkannt. Der Knoten kann anschließend seine reguläre Funkanlage anschalten, um die vollständige Nachricht zu empfangen.

2.1.5 Technologien

Momentan existieren zahlreiche Projekte, bei denen an der Realisierung von Sensornetzwerken gearbeitet wird. Hierbei sind besonders viele Projekte im Umfeld der Berkeley Universi t y of C alifornia entstanden.

Berkeley Mica Mote

Die an der Be rkeley University of California entwickelte Mic a Mote [25] gehört zu den am häufigsten in Versuchen genutzten Sensorknoten. Sie unterstützt das, ebenfalls in Berkeley - speziell für Sensorknoten - entwickelte Betriebsystem TinyOS (siehe auch Unterabschnitt 3.3.2.4 Mittlerweile existieren mehrere Generationen von M o t e s. Wärend die erste Version CSMA/CA als MAC-Protokoll benutzt, verwendet der Mica2 -Knoten (mit schnellerem Prozessor aber minimal geringerem Durchsatz als die ursprüngliche Version) eine Variante dieses Protokolls mit Collision Detection (CD). Weiterhin existiert noch der Mic a2Do t -Knoten (mit ähnlicher Hardware wie Mica2 , aber einem langsameren Prozessor). Mote s besitzen eine Uhr, die sich mittels TinyOS mit Nachbarn auf +/- 1ms synchronisieren kann [26]. Ein Grund für die Beliebtheit von Mic a ist sicherlich die einfache Verfügbarkeit für kommerzielle Zwecke.⁵

PicoRadio

P icoRadio ist ein weiteres, an der Berkeley Universi t y of C alifornia entstandenes Projekt, das sich mit der Entwicklung von Sensorknoten beschäftigt⁶ 2002 wurden die beiden Knotentypen PicoNode I und PicoNode II fertiggestellt. 2003 demonstrierte die Projektgruppe mit P ico- Beacon einen Prototypen des ersten Sensorknotens, der (mittels einer Solarzelle) in der Lage ist Energie zu gewinnen.

Smart Dust

Das von Pister und Kahn geleitete, an der Berkeley Universi t y of C alifornia angesiedelte Smar t Dust -Projekt zielt auf die Entwicklung eines mobilen Sensornetzwerks mit besonderen Eigenschaften. In [27] stellen die Autoren einige Ergebnisse ihrer Arbeit vor.

Smart Dust -Knoten sollen die Größe eines Kubikmillimeters nicht überschreiten. Die geringe Größe soll es den Knoten ermöglichen, sich fliegend fortzubewegen, allerdings nicht mittels eines aktiven Antriebs, sondern angetrieben von Luftströmungen.

Die Knoten kommunizieren nicht über ein Funkmodul, sondern mittels eines gerichteten Laserstrahls. Nach Forschungsergebnissen der Autoren sind optische Verbindungen in der Lage wesentlich energieeffizienter zu kommunizieren als Funkverbindungen, gesetzt den Fall die Knoten besitzen Sichtkontakt.

Die Etablierung einer optischen Verbindungen ist gegenwärtig eine der größten Herausforderungen bei der Entwicklung von Smart Dust : Im Gegensatz zu einer Funkverbindung muss eine optische Verbindung zielgenau ausgerichtet sein, d.h. der sendende Knoten muss mit seinem Laserstrahl den Photodetektor des empfangenden Knotens treffen.

Um eine Vollduplex-Verbindung zwischen zwei Knoten aufzubauen, ist es also notwendig, dass jeweils der Strahl eines Knotens den Detektor des anderen Knotens treffen kann. Um Verbindungen zu mehreren Knoten gleichzeitig aufrechterhalten zu können, ist es entsprechend notwendig die Knoten mit mehreren Laserdioden und Photodetektoren auszustatten.

Als energiesparende Alternative zum Senden mittels einer Laserdiode stellen die Autoren einen Corner-Cube Retroreflector (CCR) vor: Diese aus drei winzigen Spiegeln bestehende Konstruktion ermöglicht es, von einem anderen Knoten abgestrahltes Licht direkt auf diesen zurück zu reflektieren. Die drei Spiegel sind jeweils im rechten Winkel (wie die Ecke eines Würfels, engl. corner-cube) angebracht, einer der Spiegel ist (im Kilohertz-Bereich) beweglich. Eine Bewegung des Spiegels resultiert in einer kurzen Unterbrechung des Signals, so dass eine Modulation des Signals ermöglicht wird.

Die Autoren beschreiben einen Versuch, bei dem die Senke an eine hochauflösende Videokamera angeschlossen ist und mit einem breit gefächerten Laserstrahl einen Bereich mit Smart Dust - Knoten erleuchtet. Die Knoten reflektieren mittels des CCRs diesen Strahl, der anschließend von der Kamera detektiert wird. Mittels dieser Konstruktion ist es möglich, über Entfernungen von mehreren hundert Metern Datenraten von mehreren Kilobit zu erreichen.

In einem solchen Szenario ist der mit einem höheren Energiverbrauch verbundene Einsatz der Laserdiode zur Kommunikation nur für Knoten notwendig, deren Sichtkontakt zur Senke blockiert ist.

2.1.6 Anwendungen

Die meisten gegenwärtigen Anwendungen für Sensornetze sind im Bereich der Umweltforschung angesiedelt.

Es befindet sich seit dem Frühjahr 2002 ein Sensornetz zur Beobachtung eines natürlicher Habitats auf Great Duck Island im Gulf of Maine (im gleichnahmigen Bundesstaat der USA).⁷ Die Insel liegt im Brutgebiet des Leach’s Storm-petrel (Oceanodrama leucorhoa) , eines schüchternen, nachtaktiven Seevogels, dessen Lebensgewohnheiten noch wenig erforscht sind. Das Sensornetz ist mit einer Kombination von Temperatur-, Luftfeuchtigkeits-, Luftdruckund Infrarotsensoren ausgestattet. Das Projekt wird von dem In t el Research Labora t ory a t Berkeley geleitet.

Das Princeton ZebraNet Project beschäftigt sich mit der Erforschung der Bewegungen von Zerbraherden und der Interaktionen zwischen Individuen der Herde.⁸ Seit Januar 2004 befindet sich ein entsprechendes mobiles Sensornetzwerk in Mpala, Kenya im Einsatz. Die mit GPS ausgestatteten Sensorknoten sind in einem elektronischen Halsband untergebracht, welches die Tiere tragen.

Seit dem Frühjahr 2005 befindet sich in der Ostsee, vor der Insel Umea˙ , ein Sensornetz im Einsatz [21],⁹ dessen Aufgabe es ist die Meerestemperatur zu messen. Besonders in der Nähe von Flussmündungen herrschen im Wasser große Temperaturdifferenzen. Diese lassen sich schwer vorraussagen und ändern sich im Laufe der Jahreszeiten. Sie sind für Meeresforscher aber interessant, da die Wassertemperatur großen Einfluss auf die Flora und Fauna vor Ort hat.

Auf den Sensorknoten läuft die Sensornetz-Plattform ScatterWeb [28],¹⁰ entwickelt von der Arbeitsgruppe Computer Systems & Telematics am Institut für Informatik der Freien Universität Berlin.

Die Sensorknoten sind jeweils an einer Boje befestigt, wobei jeder Sensorknoten zahlreiche Temperatursensoren besitzt, die an einem Bus wie an einer Perlenschnur befestigt sind. Ein Gewicht befindet sich am Ende dieser Leitung. Durch diese Konstruktionsweise läßt sich die ermittelte Temperaturverteilung des Meeres dreidimensional darstellen.

2.2 Schwarmintelligenz

Von Schwarmintelligenz im biologischen Sinne spricht man, wenn in einem Schwarm durch Interaktionen einzelner Individuen ein emergentes Verhalten (vgl. Unterabschnitt 2.2.1) entsteht. Durch die Interaktion einzelner Entitäten mit gleichen Verhaltensmustern erreicht der Schwarm höhere Effektivität und ist zu wesentlich höheren Leistungen als ein einzelnes Individuum imstande: Ameisen tragen gemeinsam Beutestücke, welche für ein einzelnes Individuum zu schwer sind; sogar in kleinere Teile zerlegt, müsste es von insgesamt mehr Ameisen getragen werden []. Termiten bauen gemeinsam meterhohe Bauten, welche über ein ausgeklügeltes Belüftungssystem verfügen. In Vogelschwärmen verbraucht durch deren charakteristische Form ein einzelner Vogel weniger Energie, da er Luftströmungen vorausfliegender Vögel ausnutzen kann.

Wenn heute von Schwarmintelligenz gesprochen wird, ist meistens die informationstechnische Umsetzung der biologischen Prinzipien mittels (im weitesten Sinne) Agentensystemen gemeint.¹¹ Besonders in der Selbstorganisation von verteilten Anwendungen sind bisherige Versuche vielversprechend. Die überwiegende Mehrheit aller technischen Verfahren ist fast ausschließlich durch das Verhalten von Insekten motiviert worden, weniger durch das Schwarm-Verhalten von Vögeln und Fischen.

Lösungen für Probleme der Selbstorganisation müssen Schwärme schon vor langer Zeit gefunden haben. Betrachtet man die Evolution als Optimierungsprozess, liegt der Gedanke nahe, dass Verfahren von Insektenschwärmen im Verlaufe einer mehrere Millionen Jahre andauernden Optimierung reichlich perfektioniert wurden.

2.2.1 Selbstorganisation und Emergenz

In vielen Arbeiten wird der Begriff der Selbstorganisation als Synonym von Emergenz (von lateinisch emergere : auftauchen, hervorkommen, sich zeigen) verwendet. Manchmal wird Emergenz aber auch lediglich als eine Spezialform der Selbstorganisation betrachtet [3]. Collier et al. [29] führen den Begriff der Selbstordnung (= engl. S el f-Ordering) als Gegensatz zur Selbstorganisation ein. Demnach läge Selbstordnung beispielsweise dann vor, wenn sich Atome zu einer Kristallstrukur neu anordnen. Auch wenn diese Benennung plausibel erscheint, ist sie lediglich eine weitere Umschreibung für den Sachverhalt der Emergenz. Als selbstorganisiert würde man nach Definition von Collier et al. ein System bezeichnen, welches autonom und koordiniert ein Ziel verfolgt, sich anpasst und ggf. optimiert.

In dieser Arbeit werden die Definitionen von De Wolf et al. [30] verwendet. Demnach spricht man von Emergenz immer dann, wenn ein sogenannter micro-macro effec t vorliegt, d.h. der globale Zustand eines Systems wird durch Interaktionen von Sub-Komponenten des Systems bewirkt. Dabei haben diese Komponenten kein Wissen über den globalen Zustand. Ihre Interaktionen werden ausschließlich durch lokale Informationen motiviert. Der globale Zustand äußert sich meistens in Mustern bzw. Strukturen oder in Charakteristika wie einem speziellen Verhalten. Ein Beispiel für ein System, welches zwar emergente Eigenschaften besitzt aber keinerlei selbstorganisierende ist beispielsweise ein Körper aus Gas, dessen Volumen durch die Bewegungen der einzelnen Gaspartikel bestimmt wird.

Als Selbstorganisation hingegen bezeichnet man den Akt des sich-selbst-organisierens. D.h. erstens, dass diese Aktion autonom ausgeführt wird. Darüber hinaus aber beinhaltet diese Defini-tion von Selbstorganisation auch den Akt der Selbstordnung, da Organisation gleichbedeutend mit einem Zuwachs an Ordnung bzw. Struktur ist. Ein klassischer Software-Agent, der ein eigenes Ziel verfolgt, ist demnach ein Beispiel für ein selbstorganisiertes System, welches keine Emergenz aufweist. Besitzt der Agent ein Modell des globalen Zustandes, so wird ein erreichter Zustand von Organisation durch striktes Befolgen eines Plans erreicht und ist implizit schon vorher im System vorhanden.

Selbstorganisation und Emergenz lassen sich also als separate Phänomene beschreiben. In technischen Anwendungen ist sicherlich, wenn ein emergentes Verfahren implementiert wird, eine Form von Organisation erwünscht. Deshalb kann man davon ausgehen, dass, wenn Emergenz gezielt eingesetzt wird, sie zur Ordnung führen soll.¹²

Der Grund, warum in den letzten Jahren Emergenz als Mittel zur Selbstorganisation beliebt wurde, ist, dass es ein mächtiges Paradigma zur Lösung von Problemen in Verteilten Systemen darstellt. Häufig stellt sich in solchen Anwendungen das Problem einer sinnvollen Zusammenarbeit der einzelnen Komponenten (Router, Knoten, ...). Diese sind kaum in der Lage, eine zuverlässige Sicht des globalen Zustandes zu erhalten. Ihnen ist in einfacher Weise lediglich der Zugriff auf lokale Ressourcen gestattet, denn Kommunikation ist ein ressourcen-zehrendes Mittel zur Koordination (besonders in Sensornetzen) und birgt Nachteile wie zeitliche Verzögerung und Belastung des Datenverkehrs durch Kontroll-Overhead. Der Grundgedanke der Optimalität biologischer Verfahren legt die Idee nahe, nach Lösungen für technische Probleme in der Biologie zu suchen.

2.2.2 Modellierung schwarmbasierter Verhaltensweisen

Die technische Modellierung von Verfahren, die auf biologischen Verhaltensweisen beruhen, ist kompliziert. Für das Verfahren dürfen nur relevante Aspekte der Verhaltensweise technisch umgesetzt werden. Biologische Aspekte des Verhaltens, die in der technischen Umsetzung nicht relevant sind, müssen ignoriert werden.

Das Schwarmverhalten, welches die meisten technischen Umsetzungen erlebt hat, ist das von Ameisen bei der Nahrungssuche. Die einzelnen Arbeiterinnen sondern dabei kontinuierlich ein Pheromon ab, welches auf andere Arbeiterinnen anziehend wirkt. Zusammengehalten durch diese anziehende Kraft konvergiert die Fortbewegung des Schwarmes zu einem geordneten Pfad.

Es existieren zahlreiche Routing-Algorithmen, die eine modellierte Variante dieser Verhaltensweise zum Finden kürzester Pade verwenden. AntNet, ein Routing-Algorithmus, der dieses Verhalten nutzt, wird in Unterabschnitt 2.2.5 vorgestellt.

Eine Kehrseite dieses Verhaltens in der biologischen Welt ist folgende: Führt ein Pfad wieder auf sich selbst zurück, kann es passieren, dass die Ameisen nicht aufhören, den entstandenen Kreis zu verstärken, sogar wenn er mehrere Kilometer durchmisst. Der Kreis bricht erst zusammen, wenn eine Mehrheit der Arbeiterinnen an Erschöpfung gestorben ist.

Bei der informationstechnischen Umsetzung wird meistens das anpassungsfähige Konzept der Software-Agenten benutzt, um das Verhalten von Individuen eines Schwarmes zu implementieren. Die größte Herausforderung bei der Programmierung ist, durch Spezifizierung der lokalen

Verhaltensweisen einzelner Individuen und deren Interaktionen miteinander das angestrebte globale Verhalten zu erreichen.

2.2.3 Mechanismen

In diesem Unterabschnitt werden Mechanismen behandelt, die die grundlegende Funktionsweise von Schwärmen bestimmen. Unter S ti g mergy versteht man das verbreitetste Koordinationsverfahren unter sozialen Insekten. Selbstorganisation durch Emergenz in Schwärmen wird meistens durch das Zusammenspiel von positivem und negativem Feedback, Verstärkung von Fluktuationen und Multiple Interaktionen bewirkt.

Stigmergy

Eine Vielzahl sozialer (d.h. in Gruppen lebender) Insekten und Software-Agenten, welche gewisse Charakteristika von sozialen Insekten besitzen, interagieren in den meisten Fällen durch eine als S t igmergy (von lat. s t igma , Zeichen) bezeichnete indirekte Form der Kommunikation: Jedes Individuum nimmt ausschließlich seine nähere Umgebung wahr und reagiert auf externe Reize, wie einem einfachen Verhaltenskatalog folgend. Durch seine Reaktion verändert das Indiviuum unter Umständen seine Umgebung. Dies bedeutet, dass nachfolgende Individuen eine veränderte Umgebung wahrnehmen und entsprechend anders reagieren. Die Individuen eines Schwarmes sind i. Allg. homogen, d.h. sie besitzen alle den gleichen Verhaltenskatalog. Die Interaktionen über die Umgebung kommen ohne jegliche Form von direkter Kommunikation aus; dennoch führen sie zu einem hohen Grad an Koordination. Koordination scheint demzufolge nur eine Folge eines Verhaltensmusters zu sein, welches sich im Laufe der Evolution entwickelt hat. Stigmergy ist die wichtigste Interaktionsform, die soziale Insekten nutzen und auf der die meisten anderen Mechanismen aufsetzen.

Es existieren allerdings auch direktere Formen der Kommunikation bei Insekten. Bienen z.B. können den Fundort einer reichhaltigen Nektarquelle mittels eines Tanzes weitergeben. Der Tanz enthält in kodierter Form die Position der Nahrungsquelle. Andere Bienen, die Zeugen dieses Tanzes sind, werden auf diese Position programmiert und unterstützen die Tänzerin beim Tanzen, um weitere Bienen zu rekrutieren, und bei der Nahrungssuche.

Wechselwirkende Selbstorganisationsmechanismen a)Positives Feedback Feedback wird im Deutschen häufig mit ” Rückkopplung“ übersetzt, in dieser Arbeit wird aber weiterhin der englische Begriff verwendet, da er sich im deutschen Sprachgebrauch etabliert hat. Unter positivem Feedback versteht man einen verstärkenden Effekt, wie den Tanz der Bienen oder bei Ameisen das Absondern von Pheromon. Individuen, die einem solchen verstärkenden Einfluss unterliegen, tendieren dazu, sich einer Arbeit anzuschließen. Positives Feedback induziert häufig einen Schneeballeffekt, da rekrutierte Individuen weitere Insekten für ihre Arbeit gewinnen. Bienen, denen zwei gleich reichhaltige und gleich weit entfernte Nahrungsquellen präsentiert werden, tendieren dazu, beide gleich stark auszubeuten. Sobald aber eine durch Ausbeutung weniger attraktiv wird, tendiert der Schwarm zur Ausbeutung der besseren Quelle. Aufgrund des verstärkenden Effekts wird auch von Reinforcement (=engl. Verstärkung) gesprochen. b) Negatives Feedback Als solches bezeichnet man einen selbstschwächenden Effekt, der zu einer Minderung von Aktivität führt. Negatives Feedback wird meistens genutzt, um positivem Feedback entgegenzuwirken und einen ehemals angestrebten, jetzt aber obsolet gewordenen Zustand zu verlassen. Bienen z.B. können wenig attraktive Nahrungsquellen mit einem abstoßend wirkenden Pheromon markieren. Andere Beispiele für negatives Feedback sind Ermüdung und Sättigung von Arbeitern, Wettbewerb zwischen Nahrungsquellen und Verdunsten von Pheromonen.

Charakteristisch für Feedback ist die selbstschwingende Eigenschaft: Eine Mischung aus stärkenden (positives Feedback) und schwächenden (negatives Feedback) Eigenschaften, wobei diese zeitversetzt ansprechen. Die Werte pendeln also zwischen bestimmten Minima und Maxima. Dies ist die Standardsituation in einem System verkoppelter Elemente, die zum größten Teil immer eine Mischung fördernder und hemmender Einflüsse darstellt und ein Spezialfall des idealen Regelkreises, der Abweichungen von einem Sollwert instantan korrigiert.¹³

In der Systemtheorie und der Biologie wird diese Fähigkeit eines Systems, sich durch Rückkopplung selbst innerhalb gewisser Grenzen in einem stabilen Zustand zu halten, als Selbstregulation oder Homöostase¹⁴ (auch Homoiostase, griechisch: µoιoσταση , zu deutsch: Gleich-Stand) bezeichnet. Dieser Begriff wurde 1929 von Walter Cannon eingeführt.

Bienen sind imstande, die Luftzirkulation innerhalb ihres Bienenstocks zu regulieren, indem sich einige Individuen des Schwarmes am Eingang des Stocks positionieren und in Intervallen synchron mit ihren Flügeln schlagen. Turner hat in diesem Zusammenhang den Term social h o meostasis geprägt [4].

Parunak bezeichnet in [3] solche zyklisch auftretenden Prozesse in Schwarrmen, die mittels Feedback zur Selbstorganisation führen, als autokatalytisch“.Demnach ist ein wichtiges Charakteristikum solcher Prozesses, dass sie sic ” egenseitig initialisieren. c) Verstärkung von Fluktuationen In diese Kategorie gehören Zufälle, die ein positives Feedback zur Folge haben. Bevor Ameisen einen Pfad etablieren, laufen zahlreiche Arbeiterinnen ziellos von ihrem Nest los und erkunden die Umgebung. Die ersten Ameisen, die erfolgreich eine Nahrungsquelle entdeckt haben, kehren als erste zurück und haben die größte Chance, mit ihrer Pheromonspur den Grundstein für einen Pfad zu legen. Dieses zufallsbasierte Konzept der Erforschung macht sich zunutze, dass in Schwärmen eine sehr große Anzahl von Individuen zur Verfügung steht. Diese Entdeckungen einzelner ermöglichen es dem System, lokalen Maxima (d.h. einer suboptimalen Lösung) zu entkommen; es wird daher im folgenden auch von Erforschung gesprochen. d) Multiple Interaktionen Das globale Verhalten eines Schwarmes resultiert aus dem Verhalten und den Interaktionen seiner Individuen. Die Art der Interaktionen besteht meistens aus einer Kombination der oben genannten Mechanismen. So kann z.B. ein Ameisenpfad nur durch eine Mindestanzahl von Ameisen aufrechterhalten werden: Bei einer zu geringen Anzahl verflüchtigt sich das Pheromon zu schnell, welches die Ameisen zusammen hält.

Spezialisierung

Eine Form der Arbeitsteilung findet bei allen sozialen Insekten statt. Viele Ameisenarten bestehen (neben der Königin und Drohnen) aus Arbeitern und Soldaten, letztere sind i. Allg. größer und besitzen stärkere Beißwerkzeuge. Bienen finden sich in Altersgruppen zusammen, die jeweils speziellen Aufgaben nachgehen. Aber auch Gruppen homogener Individuen sind in der Lage, sich zu spezialisieren. Bonabeau et al. benutzen in [2] das Konzept einer Reaktionsschwelle und eines Stimulus, die zu einer Aufgabe gehören. Ein Individuum besitzt für jede relevante Aufgabe eine Reaktionsschwelle und einen Stimulus. Als Stimulus wird hier ein (z.B. visueller oder olifaktorischer) Anreiz bezeichnet, einer Aufgabe nachzukommen. Die Reaktionsschwelle bezeichnet die Wahrscheinlichkeit, einem Stimulus nachzugeben. Reagiert ein Individuum auf einen Stimulus, wird die entsprechende Reaktionsschwelle gesenkt. In Zukunft wird dieses Individuum dieser Aufgabe mit einer höheren Wahrscheinlichkeit nachkommen. Das Nachgehen einer Arbeit ist mit dem Abbau des Stimulus verbunden: Das Füttern von Larven stoppt deren Ausstoß von Hunger-Pheromonen, das Entsorgen von Leichen senkt den Stimulus, diese zu entfernen. Über einen längeren Zeitraum bilden sich aus einer ehemals homogenen Menge von Individuen nun solche heraus, die einer speziellen Aufgabe nachkommen. Je besser sie ihrer Aufgabe nachkommen, desto geringer wird der Stimulus und damit die Wahrscheinlichkeit, dass andere Ameisen sich der Arbeit anschließen.

2.2.4 Vorteile

Durch die Kombination der in Unterabschnitt 2.2.3 beschriebenen Mechanismen, erreichen Schwärme eine einzigartige Weise der kollektiven Zusammenarbeit, die einige bemerkenswerte Stärken hat:

Robustheit Vor allem durch Nutzung des indirekten Kommunikationsverfahrens des Stig- mergy wird eine hohe Robustheit schwarmbasierter Verfahren erzielt. Subkomponenten eines Schwarmes müssen sich bei A¨ nderungen ihrer Umgebung nicht auf einen neuen Plan einigen, sondern sie reagieren kollektiv auf das veränderte Umfeld. Durch die hohe Anzahl von Individuen in einem Schwarm besitzt dieser eine hohe Redundanz. Der Ausfall einzelner Komponenten wirkt sich nur geringfügig auf die Leistung des Gesamtsystems aus.

Einen weiteren großen Vorteil schwarmbasierter Verfahren stellt die Tatsache dar, dass sie mit verhältnimäßig geringem Kommunikationsaufwand auskommen: Mittels der Nutzung von Stigmergy ist eine direkte Kommunikation nicht notwendig; insbesondere dazu werden durch Versenden von Nachrichten in Kommunikationsnetzwerken wichtige Ressourcen gebunden.

Individuen eines Schwarmes handeln nur aufgrund lokalen Wissens, deshalb skalieren schwarmbasierte Routing-Algorithmen auch gut [2].

Flexibilität Schwarmbasierte Verfahren stellen ein wandlungsfähiges Koordinationsprinzip für verteilte Systeme dar. Durch Variation der lokalen Verhaltensweisen kann emergent eine Vielzahl von globalen Verhaltensmustern erzeugt werden. Durch die Ausnutzung von Reaktionsschwellen wird eine hohe Vielseitigkeit einzelner Entitäten erreicht. Sie sind prinzipiell für mehrere Arbeiten einsetzbar und sind imstande, sich selbständig in Arbeitsgruppen aufzuteilen.

In der Kombination aus Robustheit und Flexibilität liegt die wahre Stärke der Schwarmintelligenz. Aufgrund ihrer Fähigkeit, sich schnell an neue Bedingungen anzupassen, entfalten schwarmbasierte Verfahren ihr ganzes Potential erst in dynamisch sich ändernden Umgebungen [2].

2.2.5 Schwarmbasierte Anwendungen

Kombinatorische Optimierungsverfahren

Bereits 1992 formulierte Dorigo die Idee, die Fähigkeiten von Schwärmen zum Aufspüren kürzester Wege technisch zu nutzen [31, 2]. Die meisten der aktuellen Verfahren beruhen auf der A n t C olony Op t imiza t ion ( AC O) -Metaheuristik, die er 1999 mit Caro formulierte [31, 2]. Einzelne Ameisen-Agenten belasten iterativ einzelne Lösungen mit einem Pheromon-Analogon. Die Belastung fällt bei besseren Lösungen stärker aus. In jeder Iteration sind die Agenten bestrebt, stärker belastete Lösungen zu beschreiten. Durch dieses positive Feedback wird schließ- lich eine der besten gefundenen Möglichkeiten als Lösung favorisiert. Die Qualität der von

A CO -Algorithmen gefundenen Lösungen liegt auf einer Stufe mit S i m u l a te d Annealing und Genetischen Algorithmen. Eine vollständige Übersicht über aktuelle Anwendungen der A CO - Metaheuristik für kombinatorische Optimierungsverfahren gibt Guntsch in [31].

Viele A CO -Algorithmen dienen zum Finden eines kürzesten Pfades in einem Graph. Einer der frühesten schwarmbasierten Algorithmen war ein Lösungsalgorithmus des T ravelling Salesman Problem (TSP) . Andere ACO-Algorithmen für kombinatorische Optimierungsverfahren in Graphen beinhalten Lösungen für das G raph Coloring Problem . Auch für S c h e du li n g -Probleme wie das S i n g l e Machine Total Weighted Tardiness Problem (SMTWTP) existieren Lösungen, die auf der AC O -Metaheuristik basieren.

Eine Variante des A CO -Algorithmus dient zur Lösung des Sh o rtest Common Supersequence P roblem (S C S P ) . Ziel ist das Finden einer speziellen Buchstabenkette (= engl. s t ring) in einem Su p e rstring . Anwendungen für dieses Problem beinhalten Ansätze zur DNA-Analyse.

P ar t icle Swarm Op t imiza t ion (PSO) ist eine andere schwarmbasierte Optimierungsmethode und basiert auf dem Verhalten von Fischschulen und Vogelschwärmen. Individuen solcher Schwärme koordinieren sich, indem sie adäquaten Abstand zu wenigen anderen Individuen ihres Schwarmes halten. Darüberhinaus passen sie ihre Geschwindigkeit an die eines nahen, anderen Individuums an. Dieses Verhalten wurde bereits 1987 von Reynolds [32] graphisch simuliert, um zu zeigen, dass sich die Fortbewegung eines ganzen Schwarmes durch wenige, einfache Mechanismen koordinieren lässt. Die PSO -Metaheurisitik wurde 1995 von Eberhard & Kennedy in [33] formuliert. Sie erreicht in Versuchen Lösungen, deren Qualität mit der von Genetischen Algorithmen vergleichbar ist.

Arbeitsteilung durch Spezialisierung

Es existieren bis dato relativ wenige Verfahren, die die Verbindung von Stimulus und Reaktionsschwelle nutzen, um zu einer Arbeitsteilung bei einer ehemals homogenen Gruppe von Individuen zu gelangen. In einer Simulation dieses Verhaltens durch Bonabeau et al. [2] mittels eines Agenten-Systems wurde folgendes Szenario implementiert: In einer Stadt werden Briefe von Postboten flexibel abgeholt. Die Stadt ist in 5x5 quadratische Zonen eingeteilt und es steht eine feste Zahl von Postboten bereit (anfangs 5), die regelmäßig in einer Zone die zu befördernden Briefe abholen. Müssen Bewohner lange darauf warten, dass ihre Briefe abgeholt werden, dient diese Wartezeit als Stimulus für einen Postboten, um diese Gegend wieder zu besuchen und dort überfällige Briefe abzuholen. Ziel der Anwendung ist, die Gesamtwartedauer von Kunden zu minimieren. In dem Versuch war zu beobachten, dass sich einzelne Agenten auf bestimmte Gegenden zu spezialisieren begannen. Die Agenten wurden zu Spezialisten für ein spezielles Gebiet.

Wurde allerdings einer der Spezialisten aus der Simulation entfernt, so begann für Spezialisten in benachbarten Zonen die Reaktionsschwelle zur Übernahme dieser Zone zu sinken, bis schließlich ein anderer Agent die Zone regelmäßig besuchte.

Sortieren

Eine Variation der Arbeitsweise mit Stimulus und Reaktionsschwelle kann genutzt werden, um simulierte Ameisen zum Analysieren und Sortieren von Datensätzen zu gewinnen. Die Arbeitsweise eines einzelnen Individuums lässt sich einfach folgendermaßen beschreiben: Zu sortierende Gegenstände werden aufgenommen, wenn sie sich stark von Gegenständen in ihrer Gegend unterscheiden; sie werden abgelegt, wenn ähnliche Objekte in der Nähe sind. Soziale Insekten nutzen dieses Verfahren in ihren Brutkammern, um Eier und Larven, die sich in einem ähnlichen Entwicklungsstadium befinden, bei einander zu halten, oder um tote Artgenossen oder Beutetiere zu sammeln. Ein entsprechender Algorithmus wurde von Lumer et al. (beschrieben in [2]) entwickelt, um Bankkontenprofile zu ordnen. Eine A¨ hnlichkeit zu anderen Datensätzen wird durch eine Metrik über die Einträge im Datensatz festgestellt.

Eine vereinfachte Form des Sortierverhaltens wird von Ameisen zur Sammlung toter Individuen genutzt: Über eine Fläche verteilte tote Ameisen werden solange zu anderen toten Individuen gelegt, bis sich alle Toten auf einem Haufen befinden. Eine Simulation dieses Verhaltens mittels

Roboter wird in [2] beschrieben. Die Versuche zeigen, dass sich ein komplexes Gruppenverhalten mittels einfacher Verhaltensweisen der einzelnen Roboter realisieren läßt.

Routing in Kommunikationsnetzwerken

Die Idee, die ACO-Metaheuristik zum Routing in Netzwerken einzusetzen, basiert auf ihren Erfolgen beim Einsatz in Graphen. Da sich diese Heuristik zum Finden kürzester Pfade in statischen Umgebungen bewährt hat, Schwärme aber in einer höchst dynamischen Umgebung leben, ist der Gedanke naheliegend, dass auf Schwärmen basierende Algorithmen besonders für Netzwerke geeignet sind. Die Dynamik in Netzwerken beruht vor allem auf A¨ nderungen der Ei- genschaften des Netzwerkverkehrs. Diese sind möglicherweise periodisch, z.B. durch Tageszeiten bedingt, entstehen aber vor allem durch die Einzelaktionen einzelner Akteure (in technischen

Anwendungenm meistens Agenten). Weiterhin können der Ausfall von Teilen des Netzwerks, aber besonders bei mobilen Netzwerken auch die A¨ nderung der zugrunde liegenden Topologie,zu einer hohen Dynamik führen.

Auf allgemeine Konzepte des Routing in Netzwerken wird in Abschnitt 3.1 eingegangen. In diesem Unterabschnitt wird lediglich auf die Konzepte von Knoten und Kanten aus der Graphentheorie zurückgegriffen.

AntNet Einer der populärsten schwarmbasierten Routing-Algorithmen ist AntNet [34] von Caro & Dorigo. AntNet nutzt die vier wechselwirkenden Hauptmechanismen (siehe Unterabschnitt 2.2.3: Positives und negatives Feedback, multiple Interaktionen und Verstärkung von Fluktuationen) der schwarmbasierten Selbstorganisation zur Etablierung eines Pfades von einem Startzu einem Zielknoten. AntNet hat besonders aufgrund einer Neuerung Popularität erlangt: Probabilistischer Routingtabellen.¹⁵ Einem Knoten wird für jedes Ziel nicht nur ein einzelner Knoten als nächster Hop zugeordnet, sondern jedem Nachbarn wird eine Wahrscheinlichkeit zugeordnet, als nächster Hop auf dem Weg zum Ziel zu dienen.

Es bezeichnet[Abbildung in dieser Leseprobe nicht enthalten] die Wahrscheinlichkeit am Knoten k , falls z der Zielknoten für eine Nachricht ist, diese über den Nachbarknoten n zu senden. (Werden im folgenden Übergangswahrscheinlich- keiten lediglich an einem Knoten k beschrieben, so wird teilweise die vereinfachende Schreibweise

P n,z für die Wahrscheinlichkeit eines Übergangs nach n mit dem Ziel z benutzt. Ist das Ziel - wie z.B. in Sensornetzen mit nur einer Senke - eindeutig, so wird die Schreibweise[Abbildung in dieser Leseprobe nicht enthalten]für die

Übergangswahrscheinlichkeit von Knoten k zu Nachbar n benutzt.)

Die Wahrscheinlichkeiten sind für jeden Knoten (und jedes Ziel) normiert. Seien N k die Nachbarknoten von k , dann gilt:

Abbildung in dieser Leseprobe nicht enthalten

AntNet nutzt zur Entdeckung neuer und Aufrechterhaltung bekannter Pfade zwei verschiedene Nachrichtentypen, die nach dem Vorbild von Ameisen modelliert wurden. Ihre Aufgabe ist es, die Werte in den Routingtabellen aktuell zu halten:

- Forward Ants werden vom Startknoten mit der Knoten-ID eines zu suchenden Zielknotens losgeschickt. An jedem Knoten wird ein nächster Hop entsprechend den Einträgen der Probabilistischen Routingtabellen durchgeführt. Forward Ants besitzen einen Stack, auf den die Knoten-ID jedes besuchten Knotens, inklusive der verstrichenen Zeit seit Erzeugung der Ameise, geschoben wird. Hat eine Forward Ant ihr Ziel erreicht, wird eine Backward Ant erzeugt und ihr der Stack übergeben.
- Backward Ants haben die Aufgabe, eruierte Pfadinformationen an den anfragenden Startknoten zu überbringen. Eine Backward Ant verfolgt einen Pfad anhand ihres Stacks. Hat sie den Startknoten, der durch den untersten Wert des Stacks identifiziert wird, erreicht, so wird für den letzten Hop die Wahrscheinlichkeit, als Übermittler zum Zielknoten zu dienen, in der probabilistischen Routingtabellen erhöht. Die Übergangswahrscheinlichkeiten der anderen Nachbarknoten werden entsprechend erniedrigt.

Initialisiert werden die Übergangs-Wahrscheinlichkeiten für alle n ∈ N k durch:

Abbildung in dieser Leseprobe nicht enthalten

Dieser Anfangszustand entspricht einer Abwesenheit jeglichen Pheromons. Sobald am Knoten k der Wert P k diesen Durchschnittswert überschreitet, bedeutet dies, dass die Kante zu n mit Pheromon belastet wurde.

Trifft in AntNet am Knoten k eine Backward Ant von einem Ziel-Knoten z über eine Kante von Nachbar n ein, wird die Wahrscheinlichkeit P n,z , für das Ziel z in Zukunft n als Übermittler zu wählen, verstärkt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Bewegung von Forwardund Backward Ant

Ein mögliches Szenario wird in Abbildung 2.1 beschrieben:

In (a) wird von Knoten k zur Erforschung eines Pfades zu Zielknoten z eine Forward Ant (FANT) versendet. Die Zahlen an den Kanten bezeichnen jeweils P k und P k

. In diesem Beispiel wird probabilistisch ermittelt, die Forward Ant über n zu senden. Sie trägt die ID des Knotens k auf ihrem Stack. Am Knoten n wird dessen Knoten-ID samt der bisherigen Laufzeit der Ameise auf den Stack geschoben. Es kann davon ausgegangen werden, dass jeder Knoten die Knoten-ID seiner Nachbarn kennt, also wird die F orwar d Ant von n direkt an z gesendet. Der Zielknoten z schiebt seine Knoten-ID und die Laufzeit der Ameise auf den Stack und erzeugt eine Backward Ant, der er den Stack übergibt.

In (b) bewegt sich die Backward Ant (BANT) zurück zum Startknoten. Ihren Pfad kann sie an dem Stack ablesen. Am Startknoten k angekommen wird die Wahrscheinlichkeit P n,z erhöht, da die Ameise über den Nachbar n zurückkehrte. Analog muss der Wert für P n,z verringert werden.

Sei r ein Verstärkungsfaktor, der entweder kontstant ist oder abhängig von der Güte des entdeckten Pfades - d.h. Laufzeit der Forward Ant - bestimmt wird. Dann wird die Verstärkung (engl.: Reinforcement) der Wahrscheinlichkeit für das Ziel z als nächsten Knoten n mit n ∈ N k zu wählen folgendermaßen bestimmt:

Abbildung in dieser Leseprobe nicht enthalten

Entsprechend werden die Wahrscheinlichkeiten für die anderen Nachbarn m mit m ∈ N k , m ƒ= n durch negatives Reinforcemen t normiert:

Abbildung in dieser Leseprobe nicht enthalten

Diese probabilistischen Pheromonwerte werden um einen Korrekturfaktor l n angepasst, der die Länge der ausgehenden Paket-Warteschlange zum nächsten Hop mit einbezieht:

Abbildung in dieser Leseprobe nicht enthalten

Der Wert α gibt eine Gewichtung der Metrik an, l n ist ein im Intervall [0 , 1] normierter, zur Länge der Warteschlange q n proportionaler Wert, der ermittelt wird durch:

Abbildung in dieser Leseprobe nicht enthalten

Durch diese Anpassung wird eine Verstopfung des Netzwerks vermieden: Knoten, die ein hohes Verkehrsaufkommen bewältigen müssen, werden mit einer gewissen Wahrscheinlichkeit umgangen. Diese Wahrscheinlichkeit steigt mit der Länge der betreffenden Warteschlange.

Mittels dieser Verfahren werden die probabilisitschen Routingtabellen initialisiert. Die einfachste Herangehensweise besteht darin, für Daten-Pakete die gleichen Wahrscheinlichkeitswerte wie für Ameisen-Pakete zu verwenden.

In AntNet wird, falls Daten-Pakete versendet werden, auf die Wahrscheinlichkeitswerte eine Exponentialfunktion angewendet. Die resultierenden Werte werden normiert und als aktuelle Übergangswahrscheinlichkeiten verwendet. Mit dieser Anpassung der Wahrscheinlichkeitswerte werden besonders geringe Wahrscheinlichkeiten noch kleiner und relativ große Wahrscheinlichkeiten noch größer. Suboptimale Pfade sollen mit dieser Arbeitsweise vermieden werden.

Eine

Übersicht

über Erweiterungen zu AntNet, um es an die Bedingungen in Sensornetzen anzupassen, befindet sich in Unterabschnitt 3.4.2.

BeeHive Im Gegensatz zu der Vielzahl schwarmbasierter Routing-Algorithmen, die auf dem Verhalten von Ameisen basieren, beruht BeeHive [35] auf modellierten Verhaltensweisen von Bienen. Bienen vermitteln anderen Arbeiterinnen die Position und Quantität einer Nahrungsquelle mittels eines Tanzes. Anders als bei AntNet wird nicht jeder entdeckte Pfad verstärkt; statt dessen findet bei BeeHive eine Verstärkung von Pfaden abhängig von deren Qualität statt. BeeHive nutzt zwei Sorten von Nachrichtentypen, die Bienen nachempfunden wurden: short distance bee agents und long distance bee agents: Während long distance bee agents durch das gesamte Netz gesendet werden, können short distance bee agents nur über eine begrenzte Anzahl von d short Hops gesendet werden. Ein Knoten bezeichnet die Menge aller Knoten, die er mittels short distance bee agents erreichen kann, als seine foraging zone . Beide Bienen-Analogon legen (ähnlich Backward Ants) bei jedem besuchten Knoten einen Pfad zum Knoten, der die Nachricht erzeugte. Die bee agents werden durch das Netzwerk geflutet.

Das Netzwerk wird (über die Knoten-spezifischen foraging zones hinaus) in foraging regions eingeteilt, die jede einen eindeutigen repräsentativen Knoten besitzt. Nur dieser Knoten kann long dis t ance bee agen t s versenden. Der Grundgedanke des Algorithmus ist es, mittels long distance bee agents Information im gesamten Netzwerk zu verteilen, wie der repräsentative Knoten der foraging region zu erreichen ist. Dieser Knoten wiederum besitzt Informationen - die er mittels short distance bee agents erhielt - wie Knoten zu erreichen sind, innerhalb dessen foraging zone er sich befindet.

Jeder Knoten besitzt eine Intra Foraging Zone (IFZ) -Routingtabelle, die Routing-Einträge für Knoten innerhalb derselben foraging zone enthält, eine Inter Foraging Region (IFR) - Routingtabelle, in der Routing-Einträge für sämtliche repräsentative Knoten eingetragen werden, und eine Fo rag in g Region Membership ( F RM) -Routingtabelle, in der Knoten eingetragen werden, deren Zugehörigkeit zu einer foraging region - und somit zu einem repräsentativen Knoten - bekannt ist.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: BeeHive: foraging z one und foraging region von k

Abbildung 2.2 zeigt beispielhaft die foraging region des repräsentativen Knotens k und dessen foraging zone für d short = 2.

Vorausgesetzt, Knoten m besitzt für n jeweils einen Eintrag in der F RM -Routingtabelle und der I F R -Routingtabelle, so kann m Nachrichten an n

über k senden. Die Nachricht von m wird solange in Richtung k gesendet, bis sie einen Knoten in der foraging zone von n (durch gestrichelte Linie gekennzeichnet) erreicht. Jeder Knoten innerhalb dieser Zone besitzt einen Eintrag in seiner IFZ -Routingtabelle für n .

Unmanned Air Vehicles

Von Holland et al. wird in [36] ein Ansatz zur Steuerung von U n manned Air Vehicles (UAVs) vorgestellt. Die einzelnen UAVs nutzen zur Koordination ihrer Bewegungen das von Reynolds entwickelte Verhalten, welches die Bewegungsmuster von Vogelschwärmen und Fischschulen imitiert (vgl. Unterabschnitt 2.2.5).

2.2.6 Ausblick

An dieser Stelle soll besonders auf schwarmbasierte Forschungen verwiesen werden, die von Relevanz für Sensornetze sind.

Das A morp h ous C ompu t ing Project am Massachuse tt s Ins t i t u t e of T echnology ¹⁶ hat sich zum

Ziel gesetzt:

the development of organizational principles and programming languages for obtai-

”

ning coherent behavior from the cooperation of myriads of unreliable parts that are

in t er c onne ct e d in unkn ow n, i rr e g ul ar , a nd t i m e- v arying ways . “ [4]

Ein Hauptziel der Arbeit der Projektgruppe ist die Entwicklung programmierbarer Materialien. Ein Ansatz, der gegenwärtig erforscht wird ist Programmable Self-Assembly . Dies beschreibt eine Technik, mittels der sich eine komplexe Struktur, welche aus mechanisch beweglichen Sub- Komponenten besteht, durch Umstrukturierung der Komponenten umformen kann [4]. Die Reorganisation soll verteilt von den Sub-Komponenten umgesetzt werden, wobei diese lediglich imstande sind mit angrenzenden Komponenten zur interagieren. Bonabeau schlägt in [2] Schwarmintelligenz als Ansatz zur Self- A ssembly vor.

Amorphous Computing -Ansätze, die zur Selbstorganisation von Sensornetzen genutzt werden könnten, werden in Unterabschnitt 3.4.3 vorgestellt.

Ein anderer Forschungsgebiet, in dem Überschneidungen zwischen schwarmbasierten Anwendungen und Sensornetzen existieren, sind UAVs (vgl. letzter Unterabschnitt). UAVs können eingesetzt werden, um Sensorknoten zu verteilen. In [1] werden Testflüge mit einem UAV beschrieben. Das eingesetzte Modell ist imstande ausreichend Sensorknoten zu transportieren, um damit einen Bereich von 16 km2 abzudecken.

3.Routing in Sensornetzen

Für die besonderen Bedingungen, die in Sensornetzen herrschen, wurde eine Vielzahl an Routing- Algorithmen entwickelt.

Es existieren zahlreiche unterschiedliche Ansätze, um die erhobenen Daten effizient von den zahlreichen Quellen zu den Senken zu befördern. Hierbei sind die speziellen Anforderungen an das Sensornetzwerk von großer Bedeutung (vgl Unterabschnitt 2.1.2). Ein Sensornetz beispielsweise, das mit Temperatursensoren ausgestattet ist und - um ein Feuer zu entdecken - eine Warnung bei Überschreitung einer Höchsttemperatur sendet, wird nur sehr selten aktiv. In diesem Fall kann man die Ressourcen des Netzwerkes möglicherweise am besten nutzen, indem die Warnung durch das Netz geflutet wird. Dieses Netzwerk wird nämlich nur zu sehr seltenen Gelegenheiten aktiv, so dass ein großer Aufwand zum Verwalten der Ressourcen unverhältnismäßig erscheint. Ansonsten stellt Fluten aber eine große Netzwerkbelastung dar, die zu vermeiden ist.

Für die diversen Einsatzgebiete von Sensornetzen (vgl. Unterabschnitt 2.1.1) müssen also, neben einer an das Szenario angepassten Hardware, auch unterschiedliche Routing-Verfahren entwickelt werden. Trotzdem besitzen die meisten Sensornetze viele Gemeinsamkeiten, die die Entwicklung einiger neuer Klassen von Routing-Algorithmen motiviert hat. Allgemeine Konzepte, auf die viele Routing-Algorithmen für Sensornetze zurückgreifen, werden in Unterabschnitt 3.1 beschrieben. Routing-Algorithmen für Sensornetze lassen sich grob in drei Gruppen einteilen: Datenzentrisch, Lokationsbewusst und Hierachisch. Ein Überblick über diese Strategien wird in Abschnitt 3.2 gegeben.

In Abschnitt 3.3 werden aktuelle Software-Plattformen für Sensornetze vorgestellt, die es gestatten das Netzwerk zu verwalten.

Verwandte Arbeiten, die sich mit der Anwendung von Schwarmintelligenz in Sensornetzen beschäftigen, werden in Abschnitt 3.4 vorgestellt.

3.1 Allgemeine Konzepte

Routing in Kommunikationsnetzwerken kann folgendermaßen beschrieben werden: Sei G = (V, E) ein gerichteter, gewichteter Graph, wobei jeder Knoten k ∈ V eine bearbeitende und

/ oder weiterleitende Einheit und jede Kante e ∈ E ein Übertragungssystem repräsentiert. Mit

N k ⊆ V und n ∈ N k werden im folgenden N k als die Nachbarn von k bezeichnet; sei e die Kante, die k und n verbindet, so ist e definiert durch e = (k, n).

In einem Sensornetzwerk ist V unterteilt in Quellen Q und Senken S . Es gilt jeweils: Q ∩ S = φ und Q S = V . Eine Senke wird auch häufig als Basisstation“ bezeichnet.

Viele für Sensornetze entwickelte Techniken geh ” von verhältnismäßig einfachen Bewegungs- mustern innerhalb des Netzwerkverkehrs aus: Sämtliche Quellen wollen ihre Daten lediglich zu einer Senke transportieren. Hierbei geht die Mehrheit aller gegenwärtigen Systeme und Szenarien lediglich von einer Senke aus [1]. Es wird i. Allg. angestrebt, die Senke nahe dem Zentrum der Topologie zu platzieren, da sich so die durchschnittliche Gesamtlänge aller Pfade auf ein Minimum reduziert [37].

Einige der Ansätze mit einer Senke können problemlos für Szenarien mit mehreren Senken adaptiert werden; häufig ist es ausreichend, wenn jede Quelle einen Pfad zur nächsten Senke etabliert, entfernte Senken werden ignoriert. Mehrere Senken bieten Redundanz, d.h. auch wenn ein Ansatz mit mereren Senken verfolgt wird, wird teilweise nur von einer aktiven Senke ausgegangen. Von Das & Dutta wird in [38] ein Mechanismus vorgestellt, mit Hilfe dessen Algorithmen, die für eine Senke ausgelegt sind, erweitert werden können, um eine Integration mehrerer Senken zu gestatten.

Im folgenden wird von einer einzelnen, zentralen Senke ausgegangen.

Die Hauptaufgabe eines Routing-Algorithmus’ ist es, Nachrichten in Form von Daten-Paketen mit möglichst großer Effizienz zwischen Knoten zu übertragen. In einem Sensornetzwerk ist diese Aufgabe unterteilt in zwei Unteraufgaben:

- Senken müssen (sämtliche oder eine Teilmenge der) Quellen darüber informieren können, an welcher Art von Information sie interessiert sind.
- Von Quellen müssen - entsprechend der Anfragen von Senken - Ergebnisse von Sensormessungen zu Senken übertragen werden.

Auf jedem Knoten befindet sich die Instanz eines Routing-Agenten. Ein Routing-Agent führt Operationen wie das Versenden und Bearbeiten eintreffender Nachrichten aus. Wird im Folgenden von Aktionen gesprochen, die ein Knoten ausführt, so wird impliziert, dass der Routing- Agent des Knotens diese umsetzt.

Zur Verbesserung der Leistung des Netzwerkes werden Kontrollnachrichten zwischen den Routing-Agenten versandt. In schwarmbasierten Routing-Algorithmen, die die Arbeitsweise von Ameisen bei der Pfadsuche imitieren, werden diese Nachrichten häufig nach dem Vorbild von Ameisen entworfen. Aufgabe der Agenten in solchen schwarmbasierten Routing-Algorithmen ist die Bearbeitung eintreffender Ameisen-Analogon und ggf. das Erzeugen und Versenden neuer Ameisen-Pakete.

Die große Mehrheit aller Projekte, die sich der Realisierung von Sensornetzen widmet, geht von Funk als zugrunde liegendem Übertragungsmedium aus (vgl. Unterabschnitt 2.1.4). Einige der in Sensornetzen realisierten Mechanismen sind für Funknetzwerke wie z.B. MANETs entwickelt worden oder wurden vorher in regulären Netzwerken eingesetzt.

Ein Sensornetz wird als homogen bezeichnet, falls alle Knoten identische Eigenschaften (gleiche Bauart und Sensortypen) haben. Andernfalls wird es als heterogen bezeichnet. In vielen Routing- Algorithmen für Sensornetze wird implizit von einem homogenen Sensornetz ausgegangen.

3.1.1 Fluten und Gossiping

Fluten stellt einen der einfachsten Mechanismen dar, um eine Nachricht in einem Netzwerk an alle Knoten zu verbreiten: Ausgehend von dem Initiator der Flut, der die Nachricht an alle seine Nachbarn sendet, übermittelt jeder Empfängerknoten die Nachricht an alle Nachbarn, bis auf den jeweiligen Sender der Nachricht.

Aufgrund der massenhaft zu versendenden Nachrichten stellt Fluten in Sensornetzen einen Ressourcen zehrenden Mechanismus dar [16].

[...]

---

¹ http://www.swiss.csail.mit.edu/projects/amorphous/

¹ D.h. es läßt sich z.B. zwischen der Abschaltung des gesamten Speichers bis zu einzelnen Blocks unterscheiden.

² In [1] wurden Funkreichweiten abhängig von der Höhe der einzelnen Knoten gemessen. Knoten in 10 cm Höhe besaßen eine Reichweite von etwa 30 m, während Knoten in 2 m Höhe bei gleicher Sendeleistung eine Reichweite von bis zu 100 m besaßen.

³ Smart Dust beispielsweise könnte mittels Laser-Übertragung arbeiten, siehe Unterabschnitt 2.1.5

⁴ http://www.webs.cs.berkley.edu/tos

⁵ http://www.xbow.com/Products/Wireless Sensor Networks.htm

⁶ http://bwrc.eecs.berkeley.edu/Research/Pico Radio/Default.htm

⁷ http://www.greatduckisland.net/

⁸ http://www.princeton.edu/ mrm/zebranet.html

⁹ http://www.elfenbeinturm.net/archiv/2004b/13.html

¹⁰ http://www.scatterweb.net

¹¹ Ein Software-Agent wird hier lediglich betrachtet als ein autonomer Prozess, der stellvertretend (meistens für einen Knoten) fest vorgegebene Aufgaben bearbeitet. Eine genauere Definition wird in Abschnitt 3.1 erarbeitet.

¹² Nach dieser Definition kann man so gut wie jedes physische Objekt sowohl als Beispiel für Emergenz, als auch als Beispiel für Selbstorganisation aufführen, da feste, unbelebte Objekte meistens eine kristalline Struktur besitzen und Lebewesen aus einer Unmenge von Zellen bestehen, welche wiederum aus einer Unmenge von interagierenden Proteinen (u.a.) bestehen.

¹³ Z.B. Thermostat

¹⁴ Z.B. Aufrechterhaltung der Körpertemperatur

¹⁵ Probabilistische Routingtabellen wurden zuerst 1996 von A n t - B ase d C on t ro l (ABC) eingesetzt [2]. Aufgrund seines eingeschränkten Einsatzgebietes - ABC wurde entwickelt für Telefonnetze - erreichte dieser schwarmbasierte Routing-Algorithmus allerdings nie die Popularität AntNets.

¹⁶ http://www.swiss.csail.mit.edu/projects/amorphous/