Abk ¨ urzungen

ABC

ACO ACQP BE CCR Corner-Cube Retroreflector CD Collision Detection

CSMA/CA Carrier Sense Multiple Access/Collision Avoidance

DV/DRP FF FP FRM GPS IFR IFZ MANET

MFR MPE NFP PSO RR RTS/CTS SC SCSP

SMTWTP Single Machine Total Weighted Tardiness Problem

SRT TSP UAV

i

Notationen

Namen von Personen werden in Kapit¨ alchen dargestellt, englische Begriffe kursiv und Ausdr¨ ucke aus dem Programmquelltext, sowie auch z. B. Nachrichtentypen und Attribute in Schreibmaschinenschrift. Wichtige Begriffe werden zur Auszeichnung halbfett geschrieben.

ii

Inhaltsverzeichnis

1  Einleitung  1

1.1  Motivation  1

1.2  Ziele  2

1.3  Probleme  2

1.4  Aufbau der Arbeit  3

2  Grundlagen  4

2.1  Sensornetze  4

2.1.1  Einsatzgebiete  5

2.1.2  Design  5

2.1.3  Besonderheiten  7

2.1.4  Kommunikation  8

2.1.5  Technologien  11

2.1.6  Anwendungen  12

2.2  Schwarmintelligenz  13

2.2.1  Selbstorganisation und Emergenz  13

2.2.2  Modellierung schwarmbasierter Verhaltensweisen  14

2.2.3  Mechanismen  15

2.2.4  Vorteile  17

2.2.5  Schwarmbasierte Anwendungen  17

2.2.6  Ausblick  23

3  Routing in Sensornetzen  24

3.1  Allgemeine Konzepte  24

3.1.1  Fluten und Gossiping  25

3.1.2  Multipath-Routing  26

3.1.3  Aggregation  26

3.1.4  Energiebewusstes Routing  27

3.2  Strategien  28

3.2.1  Datenzentrisches Routing  29

3.2.2  Lokationsbewusstes Routing  32

3.2.3  Hierarchisches Routing  35

3.2.4  Andere Arten von Routing  36

3.3  Systeme  36

3.3.1  Cougar  36

3.3.2  TinyDB  37

3.3.3  TiNA  38

3.4  Verwandte Arbeiten  38

3.4.1  Schwarmbasiertes Multipath-Routing in MANETs  38

3.4.2  Schwarmintelligenz in Sensornetzen  39

iii

INHALTSVERZEICHNIS iv

3.4.3  Amorphous Computing  42

3.4.4  Andere  43

4  Ein schwarmbasierter Routing-Algorithmus f ur Sensornetze  44

4.1  Anforderungen an den Algorithmus  45

4.2  Bestimmung eines angestrebten Schwarmverhaltens  45

4.2.1  Energieeffizientes Multipath-Routing  47

4.2.2  Ein Ansatz f ur Sensornetze  49

4.3  Interaktionsmechanismen  51

4.3.1  Etablierung von Pfaden: Erforschen und Fluten  51

4.3.2  Positives und negatives Feedback  53

4.3.3  Aggregation  55

4.4  Strategie des Algorithmus  56

4.4.1  Nachrichtentypen  56

4.4.2  Regul are Arbeitsweise  57

4.4.3  Erweiterungen  60

5  Implementierung  75

5.1  Eingesetzte Software  75

5.1.1  C  75

5.1.2  OTcl  75

5.1.3  Der Netzwerk-Simulator ns-2  75

5.2  Routing-Agent  77

5.3  Pakete  80

5.4  Vergleichs-Algorithmus  82

6  Simulation und Evaluierung  84

6.1  Simulationsszenarien  84

6.1.1  Aufbau  84

6.1.2  Parameter des Schwarm-Algorithmus  87

6.2  Vergleich der Algorithmen  97

6.2.1  Topologie T1  97

6.2.2  Topologie T2  99

7  Zusammenfassung  103

7.1  Bewertung  104

7.2  Ausblick  104

Literaturverzeichnis   107

Kapitel 1

Einleitung

Sensornetze stellen eine neuartige Technologie dar, deren Realisierung erst durch technische Fortschritte der letzten Jahre, wie die Entwicklung immer kleinerer Computerkomponenten, erm¨ oglicht wurde. Im Vergleich zu herk¨ ommlichen 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¨ ussen zur Selbstorganisation im Stande sein: Zum einen erschwert die große Anzahl der Knoten eine effektive Wartung. Zum anderen existieren Ans¨ atze, um Sensornetze in schwer zug¨ anglichen Gebieten fernab der Zivilisation einzusetzen. Sensorknoten werden i. Allg. mittels einer Batterie betrieben. Falls sie keine M¨ oglichkeit - wie z.B. Solarzellen - besitzen, um sich wieder aufzuladen, ist ihre Lebenszeit begrenzt.

Auf dem Weg bis zur Integration dieser Technologie in unser allt¨ agliches Leben sind noch zahlreiche Herausforderungen zu l¨ osen. Ein Mittel dazu k¨ onnte Schwarmintelligenz darstellen.

Schwarmintelligenz ist ein Konzept, welches durch Verhaltensweisen von Schw¨ armen (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¨ armen 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¨ armen gr¨ oßtenteils ohne direkte Kommunikation auskommen. In verteilten Systemen stellt Kommunikation, ganz abgesehen von den damit verbundenen Problemen der zeitlichen Verz¨ ogerung, auch einen Ressourcen belastenden Prozess dar [2].

1.1 Motivation

Schwarmbasierte Algorithmen besitzen einige besondere Eigenschaften, die sie f¨ ur den Einsatz in Sensornetzen pr¨ adestinieren:

• Schw¨ arme 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¨ ahig [2, 3]. Informationstechnische schwarmbasierte Anwendungen, die diese Eigenschaften erfolgreich imitieren, besitzen damit eine gute Skalierbarkeit. Zeigen schwarmbasierte Routing-Algorithmen f¨ ur gebr¨ auchliche Kommunikationsnetzwerke bereits beachtliche

1

1.2. ZIELE 2

Leistungen, so sollte dies im Besonderen auch f¨ ur Sensornetze gelten, die sich durch eine außerordentlich große Anzahl von Knoten auszeichnen.

• In Schw¨ armen existiert keine zentrale Kontrollinstanz, statt dessen resultiert ihre Selbst-organisation aus den Interaktionen relativ homogener Individuen. Dadurch verhalten sich schwarmbasierte Anwendungen robust gegen¨ uber dem Ausfall einzelner Komponenten. Die Verhaltensmuster der einzelnen Individuen in Schw¨ armen sind vergleichsweise simpel. Da diese Verhaltensmuster dar¨ uber hinaus identisch sind, erleichtert dies die Implementierung schwarmbasierter Algorithmen [2].

Das Amorphous Computing Project am Massachusetts Institute of Technology hat 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 Amorphous Computer bezeichnet. Eine m¨ ogliche Anwendung dieser Technologie w¨ aren ” programmierbare Materialien“, d.h. Materialien, die Sensorknoten

enthalten, aber noch dar¨ uber hinausgehende M¨ oglichkeiten besitzen, aktiv auf ihre Umwelt einzuwirken.

Ein Anwendungsbeispiel w¨ are smartskin f¨ ur Flugzeuge: Dieses Material besteht aus einem Netzwerk aus Sensoren und beweglichen mechanischen Teilen, die in den Fl¨ ugel eingebettet sind. Der Fl¨ ugel kann sich an die aerodynamischen Gegebenheiten anpassen und immer die effizienteste Form f¨ ur die gegenw¨ artigen Bedingungen annehmen [4].

1.2 Ziele

Zahlreiche technische Probleme im Bereich der Sensornetze sind noch weitgehend ungel¨ ost, so z.B. die Frage eines m¨ oglichst effizienten Energiemanagements.

Ziel dieser Arbeit ist die Entwicklung eines schwarmbasierten Routing-Algorithmus, der es erm¨ oglicht, die Ressourcen eines Sensornetzes effizient zu nutzen. Dies soll die Lebenszeit des Netzwerks verl¨ angern und gleichzeitig eine m¨ oglichst große Abdeckung des mittels Sensoren uberwachten Gebietes erm¨ oglichen. ¨

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

Sensornetze sind in zahlreichen Szenarien f¨ ur eine Vielfalt von Aufgaben einsetzbar. Der entwickelte Algorithmus soll einfache, universell einsetzbare Mechanismen nutzen, um ein m¨ oglichst breites Einsatzgebiet zu erm¨ oglichen.

1.3 Probleme

Selbstorganisation ist in Schw¨ armen kein Ergebnis zielgerichteter Bem¨ uhungen, sondern manifestiert sich emergent. Dies bedeutet, dass Organisation nur ein Nebeneffekt der kombinierten Verhaltensweisen s¨ amtlicher Individuen ist. Es ist allerdings kaum erforscht, wie sich Algorithmen entwerfen lassen, die Leistungen zeigen, f¨ ur die sie nicht explizit entwickelt wurden [4]. Zur Entwicklung eines Ansatzes werden in dieser Arbeit die Mechanismen bew¨ ahrter (schwarmbasierter und anderer) Routing-Algorithmen analysiert. Um den besonderen Bedingungen in Sensornetzen zu gen¨ ugen, ist es notwendig, die adaptierten Mechanismen anzupassen.

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

1.4. AUFBAU DER ARBEIT 3

1.4 Aufbau der Arbeit

Im folgenden Kapitel 2 werden die Grundlagen dieser Arbeitet erl¨ autert. 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¨ ur 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¨ unschtes globales Verhalten des Algorithmus erzeugen sollen. Diese Mechanismen werden anschließend in einen Algorithmus integriert.

In Kapitel 5 wird n¨ aher auf die Implementierung eines Routing-Agenten eingegangen, der den erarbeiteten Algorithmus ausf¨ uhrt. Außerdem wird n¨ aher 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¨ uhrende und ausstehende Aspekte der Arbeit gegeben.

Kapitel 2

Grundlagen

2.1 Sensornetze

Fortschritte in den Bereichen der drahtlosen ¨ Ubertragungstechnik und Mikroelektronik haben die

Entwicklung von Sensornetzwerken erm¨ oglicht. Diese Netzwerke bestehen aus zahlreichen kleinen und kosteng¨ unstigen Knoten, die ¨ uber einen begrenzten Energievorrat verf¨ ugen. Einsatzgebiete solcher Netzwerke sind u.a. ¨ Uberwachungsaufgaben in schwer zug¨ anglichem Gel¨ ande.

Die Knoten sind mit Sensoren ausgestattet, die gewisse Schl¨ usselsignale wahrnehmen k¨ onnen. Die Knoten werden im Allgemeinen in und um das zu beobachtende Ph¨ anomen plaziert. Aufgabe des Netzwerkes ist es, mittels der Sensoren wahrgenommene Ereignisse, z.B. Anstieg der Temperatur uber ein H¨ ochstmaß, an andere Teile des Netzwerkes zu ¨ ubertragen. Man spricht bei den Sensoren ¨

deshalb auch von Quellen, bei den Empf¨ angern der Daten innerhalb des Sensornetzes von Senken. Senken k¨ onnen h¨ aufig die gewonnenen Daten aus dem Sensornetzwerk hinaus ¨ ubermitteln. Eine

Senke wird gelegentlich auch als Basisstation bezeichnet. Aufgrund der kritischen Einsatzgebiete ist es m¨ oglicherweise notwendig, dass die Sensorknoten ¨ uber dem Zielgebiet abgeworfen werden m¨ ussen. Deshalb ist es erforderlich, dass das Netzwerk ¨ uber selbstorganisierende F¨ ahigkeiten

verf¨ ugt. Dies ist besonders problematisch, da ein Merkmal von Sensornetzen ihre hohe Anzahl von Knoten ist, denn sie werden ¨ uber ein großes Gebiet, bzw. in einer hohen Dichte verteilt. Da die Knoten nicht alle in Sichtweite der Senke liegen, wird in der Regel ¨ uber Multi-Hop-Routing kommuniziert (siehe Unterabschnitt 2.1.4).

Sensornetze besitzen viele Vorteile gegen¨ uber herk¨ ommlichen Sensor-Systemen. Durch die bestehende Redundanz ist das System weitgehend resistent gegen¨ uber dem Ausfall von Komponenten [6]. Dar¨ uber hinaus bieten diverse Sensoren unterschiedliche Perspektiven auf das zu untersuchende Ph¨ anomen an. Es ergeben sich durch die Besonderheiten von Sensornetzen v¨ ollig neue Anwendungsgebiete f¨ ur sie.

M¨ ogliche Einsatzgebiete f¨ ur Sensornetze werden in Unterabschnitt 2.1.1 diskutiert. Abh¨ angig von dessen Verwendunsgzweck k¨ onnen bei der Entwicklung eines Sensornetzes unterschiedliche Designentscheidungen getroffen werden. Diese werden in Unterabschnitt 2.1.2 besprochen. Ein ¨ Uberblick ¨ uber die Besonderheiten von Sensornetzen, die es von herk¨ ommlichen Netzwerken unterscheiden, wird in Unterabschnitt 2.1.3 gegeben. Gegenw¨ artigen Entwicklungen der Sensornetzwerk-Technologie in Bezug auf die Bit¨ ubertragungsschicht und MAC-Schicht werden in Unterabschnitt 2.1.4 beschrieben. In Unterabschnitt 2.1.5 werden aktuelle Technologien f¨ ur Sensornetze vorgestellt. Dieser Abschnitt wir abgeschlossen von einem ¨ Uberblick ¨ uber aktuelle

Anwendungen f¨ ur Sensornetze, der in Unterabschnitt 2.1.6 gegeben wird.

4

2.1. SENSORNETZE 5

2.1.1 Einsatzgebiete

Umweltforschung Die Anpassungsf¨ ahigkeit von Sensornetzen erm¨ oglicht den Einsatz in f¨ ur Menschen nur schlecht zug¨ anglichen Gebieten. Auch f¨ ur die Erforschung des Verhaltens diverser Tierarten eignen sich Sensornetze. Sie erm¨ oglichen es, Tiere ¨ uber einen langen Zeitraum in deren

nat¨ urlichem Habitat und ohne den st¨ orenden Eingriff von Menschen zu beobachten. Dar¨ uber hinaus sind sie imstande, das Verhalten besonders kleiner Arten in einem gr¨ oßeren Zusammenhang (massenhaft, simultan und ¨ uber ein großes Gebiet verstreut) zu betrachten [7, 1].

Katastropheneinsatz Die Vielzahl m¨ oglicher Sensoren, mit denen sich Sensorknoten ausstatten lassen, pr¨ adestinieren Sensornetze zur Erkennung einer Vielzahl von gef¨ ahrlichen Substanzen (chemisch, biologisch oder radioaktiv). In diese Kategorie l¨ aßt sich auch der Einsatz von Sen-sornetzen zur Erkennung und Vermeidung von Waldbr¨ anden einordnen. Bereits realisiert wurde ein System zur Erkennung von ¨ Uberschwemmungen [7].

Milit¨ ar Ein m¨ ogliches Einsatzgebiet ist die ¨ Uberwachung von kritischem Terrain [7, 1], d.h.

Fahrzeuge und Personen werden mittels Druck-, Bild- und Infrarotsensoren entdeckt. Mobile Objekte k¨ onnen identifiziert und deren Bewegungen verfolgt werden. Zahlreiche Arbeiten zu Sensornetzen werden von der DARPA gef¨ ordert.

Medizin Vorstellbar ist die ¨

Uberwachung physiologischer Daten von Patienten in einem Krankenhaus oder Altenheim. Die Position von Patienten und ¨ in einem Altenheim kann der Sturz eines Patienten erkannt werden [7]. In ferner Zukunft k¨ onnte es m¨ oglich sein, Sensoren direkt in den Blutkreislauf eines Patienten zu injizieren [8].

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

¨ Okonomie Im Handel sind Sensornetze zur Inventur innerhalb von Lagerh¨ ausern und Fabriken geeignet [7], m¨ oglicherweise in Verbindung mit Smart Labels. Es ist m¨ oglich, dass in naher Zukunft jedes Warenobjekt einen solchen Chip, der s¨ amtliche f¨ ur den Weiterverkauf relevanten Daten enth¨ alt, tr¨ agt. Diese passiven Chips, die keine Energieversorgung besitzen, k¨ onnen per Funk abgefragt und durch ein Sensornetzwerk verwaltet werden.

Heimanwendungen In Geb¨ auden k¨ onnten Sensornetze zur Messung von Temperatur und Luftfeuchtigkeit genutzt werden [8]. Die Vernetzung aller heimtechnischen Ger¨ ate realisisiert das Smart Environment [7]. D.h. K¨ uhlschr¨ anke, die Lebensmittel nachbestellen, wenn sie fast verbraucht sind und andere technische Ger¨ ate, die sich auf den Benutzer einstellen. Bereits 1988 formuliert Mark Weiser die Idee des Ubiquitous Computing, d.h. in allt¨ aglichen Gebrauchsgegenst¨ anden verborgene Sensorknoten, die zu einer Vernetzung unserer Umwelt f¨ uhren und die Bereitstellung von Informationen und deren Zugriff ¨ uber s¨ amtliche Objekte in dieser vernetzten Welt erm¨ oglichen.

2.1.2 Design

Abh¨ angig vom Einsatzgebiet m¨ ussen 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¨ urlichem Verhalten beinflussen. Sen-sornetze, die zur Erkennung von Waldbr¨ anden in abgelegenen W¨ aldern eingesetzt werden, sollten m¨ oglichst wenig Wartung ben¨ otigen und eine hohe Lebensdauer besitzen. Ein Sensornetzwerk

2.1. SENSORNETZE 6

hingegen, welches zur Bestimmung von Unterwasserstr¨ omungen benutzt wird, sollte aus Knoten bestehen, die die Str¨ omung m¨ oglichst wenig beeinflussen.

Es gibt Ans¨ atze f¨ ur Sensornetze, die Zugang zu einer Energieversorgung besitzen [9], und solche, die fernab der Zivilisation (oder aus Gr¨ unden der Autonomie) auf Batterien angewiesen sinddie Mehrheit aller Ans¨ atze geht von batteriebetriebenenen Sensorknoten aus. Zwischen diesen beiden M¨ oglichkeiten sind auch Hybridl¨ osungen vorstellbar, wie Sensornetze, in denen einige

Knoten in der Lage sind (z.B. ¨ uber Solarzellen), Energie aus der Umwelt zu beziehen. Andere Knoten k¨ onnten sich mittels solcher ”

Je nach Aufgabe m¨ ussen Sensornetze einen charakteristischen Informationsfluß erm¨ oglichen: Zulieferung einer Alarm-Nachricht an die Senke, ausschließlich bei Erkennen eines speziellen Ereignisses, Garantie eines regelm¨ aßigen Streams oder Ablieferung repr¨ asentativer Durchschnittswerte. H¨ aufig wird davon ausgegangen, dass die Senke ¨ uber eine externe Verbindung wie z.B.

eine Satellitenverbindung mit einer Kontrollinstanz oder dem Internet verbunden ist [6]. Alternativ k¨ onnte eine Senke einen Datenspeicher enthalten, dessen Inhalt manuell kopiert wird. Es gibt außerdem Szenarien, in denen aus Gr¨ unden der Redundanz von mehreren Senken ausgegangen wird. Von der Senke aus k¨ onnten s¨ amtliche beobachteten Ereignisse aus dem Sensornetzerk ubertragen werden. Oder es ist m¨ oglich, 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¨ uhrt. Sie bestimmen vier Charakteristika von Architekturen f¨ ur Sensornetze, die Designentscheidungen beeinflussen:

• Input: Notwendig ist die Konvertierung der Sensormessungen in eine Form, die zur Weiterverarbeitung geeignet ist.

• Berechnungen: Die F¨ ahigkeit zu verteilten Berechnungen erm¨ oglicht dem Sensornetz die Bew¨ altigung einer Vielzahl von Aufgaben.

• Kommunikation: Der Transport von Daten ist die prim¨ are Funktion des Sensornetzes; h¨ aufig werden Daten in andere Netzwerke ¨ ubertragen.

• Programmierung: Dieser Aspekt wird h¨ aufig ignoriert, allerdings ist die Implementierung ein kritischer Aufgabenbereich, der verteilte Dienstleistungen und Fehlerbehandlungen erm¨ oglichen muß.

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

Neben besonderen Anforderungen an das Design der Hardware der Sensorknoten f¨ uhrt die Wahl des Einsatzgebietes zur Notwendigkeit besonderer Sensortypen, ¨ uber die die Knoten verf¨ ugen m¨ ussen.

Sensorknoten beispielsweise, die die Temperaturverteilung im Meer messen, m¨ ussen wasserdicht konstruiert sein und schwimmen k¨ onnen (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 ¨ außeren Kugel rotiert. Nachdem solche Knoten aus der Luft abgeworfen wurden ist sichergestellt, dass die Antenne immer nach oben zeigt [1].

2.1. SENSORNETZE 7

Sensorknoten im Bereich von Umweltforschung und Milit¨ ar sollen h¨ aufig gut getarnt sein, um eine Entdeckung zu vermeiden. Neben einer Miniaturisierung der Hardware, um eine geringe Gr¨ oße der Knoten (siehe auch Unterabschnitt 2.1.3) zu erreichen, ist es m¨ oglich die Knoten als Steine oder ¨ Aste zu tarnen [1].

2.1.3 Besonderheiten

Wie bereits im letzten Unterabschnitt gezeigt wurde, stellen die vielf¨ altigen Einsatzgebiete f¨ ur Sensornetze teilweise sehr spezielle Anforderungern an deren Eigenschaften. In diesem Unterabschnitt soll auf Besonderheiten von Sensornetzen eingegangen werden, die sie von herk¨ ommlichen Netzwerken unterscheiden.

Miniaturisierung

F¨ ur zahlreiche Anwendungen ist eine m¨ oglichst geringe Gr¨ oße der einzelnen Sensorknoten notwendig [10]. Die Miniaturisierung der Hardware ist ein essentieller Bestandteile der Entwicklung von Hardware f¨ ur Sensornetze, wie z.B. im Smart Dust-Projekt (siehe Unterabschnitt 2.1.5). Einer der gr¨ oßten Nachteile einer geringen Knotengr¨ oße ist eine Begrenzung der verf¨ ugbaren Energiereserven.

Energieeffizienz

Die Minderheit aller Ans¨ atze f¨ ur Sensornetze geht von Knoten mit einer M¨ oglichkeit zur Energiegewinnung aus. Die Menge an Energie, die sich momentan aus der Umgebung gewinnen l¨ aßt, liegt im Bereich von 100 µW. Energie ließe sich m¨ oglicherweise gewinnen aus Vibrationen, Umgebungsw¨ arme oder Licht [4]. Zu den Bauteilen, die Energie ben¨ otigen, z¨ ahlen: Prozessor, Speicher, Funkanlage und Sensoren [11].

Deshalb ist es notwendig, um eine m¨ oglichst lange Laufzeit eines Sensornetzes zu garantieren, den Energieverbrauch im laufenden Betrieb zu minimieren. Es existieren f¨ ur Hardware-Komponenten, die Energie beanspruchen, zahlreiche M¨ oglichkeiten, den Verbrauch zu verringern:

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

In F¨ allen, in denen das Betriebsystem eines eingebetteten Systems oder Sensornetzes f¨ ur die Regulierung des Energieverbrauchs zust¨ andig ist, wird von dynamic power management (DPM) [12] gesprochen.

F¨ ur Sensoren l¨ aßt sich pauschal sagen, dass der Energieverbrauch passiver Sensoren (Temperatur, Luftfeuchtigkeit, etc.) so gering ist, dass er im Vergleich zum Verbrauch anderer Hardwarekomponenten vernachl¨ assigbar ist. Aktive Sensoren hingegen (Kameras, Sonar, etc.) k¨ onnen einen sehr hohen Energieverbrauch haben [13].

Der Großteil der Energie wird i. Allg. allerdings nicht f¨ ur Prozesse an den Knoten ben¨ otigt,

sondern wird durch die Kommunikation mittels der Funkanlage (siehe ¨ ubern¨ achster Unterabschnitt 2.1.4) verbraucht: Es wird 100-1000 mal so viel Energie f¨ ur die ¨ Ubertragung eines Bits

ben¨ otigt, wie f¨ ur die Ausf¨ uhrung einer Operation [8]. Ein Ziel vieler Routing-Algorithmen f¨ ur

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

2.1. SENSORNETZE 8

Sensornetze ist es deshalb, durch eine m¨ oglichst geringe Anzahl versandter Nachrichten den Energieverbrauch der Funkanlage so gering wie m¨ oglich zu halten.

Eine eingeschaltete Funkanlage verbraucht aber auch dann noch Energie, wenn sie nicht sendet oder empf¨ angt. Einige Routing-Algorithmen versuchen deshalb, die Funkanlagen der Knoten zu inaktiven Zeiten auszuschalten. Diese Strategie wird n¨ aher 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¨ onnen zwischen diversen Typen von Sensorknoten schwanken: Rockwell’s Wins Nodes verbrauchen im unt¨ atigen (aktiviert, aber nicht sendend oder empfangend) Zustand fast genau soviel (97%) Energie wie w¨ arend des Empfangs, w¨ arend des Sendens wird 25% mehr Energie verbraucht; bei Medusa II Nodes ergibt sich (bei maximaler Sendeenergie) das gleiche Verh¨ altnis, wie in [13] beschrieben wurde. Stojmenovic et al. erw¨ ahnen zwei getestete, ¨ altere Funkanlagen, wobei bei einem Typ das Verh¨ altnis des Energiverbrauchs von aktiviert zu empfangend zu sendend 0,12:1:2 betr¨ agt; bei dem anderen liegt dieses Verh¨ altnis bei 0,0045:1:1,36.

Selbstorganisation

In einigen Szenarien f¨ ur Sensornetze wird von einer zuf¨ alligen Verteilung der Sensorknoten ausgegangen. Sensorknoten ben¨ otigen in diesem Fall die F¨ ahigkeit, selbst¨ andig eine Routing-Topologie etablieren zu k¨ onnen. Auch im laufenden Betrieb m¨ ussen die Knoten ggf. autonome Entscheidung treffen und in der Lage sein, sich neu konfigurieren zu k¨ onnen [8]. Sensornetze besitzen somit einige ¨ Ahnlichkeiten mit Ad Hoc-Netzwerken [1, 14]. Auch bei diesen ist Energieeffizienz ein vorrangiges Ziel.

Nach Schiller k¨ onnten 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¨ ahigkeit zur Selbstorganisation eines der wichtigsten Merkmale, die ein Sensornetz besitzen muss, besonders um sich an unvorhergesehene Ereignisse anzupassen.

Mobilit¨ at

F¨ ur einige Anwendungen wird die Mobilit¨ at der Sensorknoten vorausgesetzt, wie sie z.B. im Smart Dust-Projekt (siehe Unterabschnitt 2.1.5) geplant ist. Gegenw¨ artig 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¨ ur mobile Sensornetze nutzbar.

Die Mehrheit der Ans¨ atze f¨ ur Sensornetze geht allerdings von immobilen Knoten aus [16].

2.1.4 Kommunikation

Funk¨ ubertragung

Die meisten Projekte zur Entwicklung von Technologie f¨ ur Sensornetze gehen von einer Funk¨ ubertragung auf der Bit¨ ubertragungsschicht aus [4]. Dieser Ansatz birgt einige Probleme:

• Der Abdeckungsbereich eines sendenen Knotens ist in den seltensten F¨ allen kreisf¨ ormig, meistens nicht einmal konvex, h¨ aufig nicht einmal kontinuierlich [17]. Viele der in Unterabschnitt 3.2.2 genannten Algorithmen gehen allerdings von der Pr¨ amisse kreisf¨ ormiger Sendebereiche aus, ihr Einsatzgebiet w¨ are also m¨ oglicherweise stark eingeschr¨ ankt.

2.1. SENSORNETZE 9

• Die ¨ Ubertragungsqualit¨ at der Funkverbindung zwischen zwei Knoten kann stark variieren, d.h die Eigenschaften der Verbindung in Hinsicht auf Fehleranf¨ alligkeit der Paket¨ ubertragung und Konnektivit¨ at k¨ onnen sich ¨ uber die Zeit ¨ andern.

• Es ist nicht davon auszugehen, dass alle Verbindungen symmetrisch sind, d.h. es ist m¨ oglich, dass Knoten Nachbarn besitzen, von denen sie Nachrichten empfangen k¨ onnen, aber nicht vice versa [18].

• Hindernisse k¨ onnen unabh¨ angig 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¨ ubertragung steigt exponentiell mit der Distanz d der ¨ Ubertragung. Wird normalerweise davon ausgegangen, dass e ≈ d ⁿ mit n = 2, so wird in Sensornetzen hingegen von 2 ≤ n ≤ 4 ausgegangen: Sensorknoten werden h¨ aufig nahe des Erdbodens platziert. Der Grund d¨ ampft Funkwellen, so dass der Energieverbrauch einer ¨ Ubertragung erh¨ oht 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¨ atzen und offenen st¨ adtischen Gebieten auf [18]. Die Ursache f¨ ur die Probleme liegt - neben der D¨ ampfung durch den Grund - darin, dass Funksignale diversen St¨ orfaktoren unterliegen. In Bereichen mit vielen Hindernissen werden Probleme besonders verursacht durch an Objekten reflektierte Signale, die sich mit anderen Signalen ¨ uberlagern. Diese und andere charakteristischen Probleme der Funk¨ ubertragung werden genauer in [19] diskutiert. Funk ist ein Broadcast-Medium. Mit einer zunehmenden Dichte von Knoten erh¨ oht sich deshalb (bei gleichbleibender Funkreichweite) die Wahrscheinlichkeit von Kollisionen. Ein Ansatz zur Verringerung dieser Wahrscheinlichkeit besteht im Einsatz von gerichteten Antennen, die ¨ Ubertragungen innerhalb eines festen Winkels erm¨ oglichen [14].

MAC-Schicht

Die MAC (Medium Access Control)-Schicht regelt den Zugang zum ¨ Ubertragungsmedium.

Versuche mit aktueller Hardware f¨ ur Sensornetze zeigen, dass besonders in Umgebungen wie Geb¨ auden und freier Natur eine Vielzahl von Problemen im Zusammenhang mit der Funk¨ ubertragung zu l¨ osen ist (vgl. letzter Unterabschnitt).

Aufgrund der geringen Diversit¨ at an gegenw¨ artig verf¨ ugbarer Hardware f¨ ur Sensornetze ist es noch fraglich, ob die oben genannten Probleme durch neue Technologien nicht schon auf der Bit¨ ubertragungsschicht zu l¨ osen 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¨ orungsquellen f¨ ur Funkverkehr in Sensornetzen wird von Zhao et al. in [18] vorgeschlagen, dass auf der MAC-Schicht die zugrunde liegende Netzwerktopologie

² In [1] wurden Funkreichweiten abh¨ angig von der H¨ ohe der einzelnen Knoten gemessen. Knoten in 10 cm H¨ ohe besaßen eine Reichweite von etwa 30 m, w¨ ahrend Knoten in 2 m H¨ ohe bei gleicher Sendeleistung eine Reichweite von bis zu 100 m besaßen.

³ Smart Dust beispielsweise k¨ onnte mittels Laser- ¨ Ubertragung arbeiten, siehe Unterabschnitt 2.1.5

2.1. SENSORNETZE 10

festgelegt wird, die nur aus zuverl¨ assigen Verbindungen besteht. Dar¨ uber hinaus ist es m¨ oglich, die Anzahl der zu erreichenden Knoten durch Verst¨ arkung der Signalst¨ arke zu erh¨ ohen. Von Schiller wird in [21] vorgeschlagen, die Sendest¨ arke eines Knotens anzupassen, so dass eine feste Anzahl anderer Knoten erreicht wird. Eine zu hohe Anzahl an Verbindungen f¨ uhrt zu einer Erh¨ ohung 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¨ ur Sensornetze eingesetzt (z.B. in [21]). Um Kollisionen zu vermeiden werden folgende Mechanismen eingesetzt: uberpr¨ uft, ob der ¨ Zuerst wird ¨ Ubertragungskanal bereits benutzt wird. Ist dies der Fall, so wird mit der ¨ Ubertragung gewartet und der Kanal wird nach einer zuf¨ allig ermittelten Zeitspanne erneut ¨ uberpr¨ uft. Dieser Mechanismus wird als Carrier Sense Medium Access with Collision Avoidance (CSMA/CA) bezeichnet.

Vor dem Senden eines Datenpakets, sendet der Start-Knoten eine Ready to Send (RTS)-Anfrage, der Empf¨ anger 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¨ anger beantwortet dieses Paket mit einer Acknowledgement (ACK)-Nachricht, um den Startknoten uber den erfolgreichen Empfang zu informieren. ¨

Es ist f¨ ur viele Anwendungen nicht m¨ oglich, die in 802.11 erreichten hohen Datenraten zu realisieren, da diese mit einem hohen Energieverbrauch verbunden ist.

Der RTS/CTS-Mechanismus ist f¨ ur zahlreiche Sensornetzwerk-Anwendungen allerdings nicht geeignet, da die zus¨ atzlich verbrauchte Energie nicht f¨ ur die vermiedenen Kollisionen kompensiert. [22, 18]

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

PAMAS (Power-Aware Multiple Access protocol with Signalling) ist ein von Singh et al. entwikkeltes und in [22] vorgestelltes MAC-Protokoll f¨ ur Ad 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¨ oren, gehen deshalb f¨ ur eine bestimmte Zeit in einen sleep-Modus.

SMAC (sensor-MAC) [23] von Ye et al. ist ein von PAMAS inspiriertes MAC-Protokoll f¨ ur Sensornetze. Ziel ist es, die Knoten m¨ oglichst effizient in Phasen der Unt¨ atigkeit in einen sleep- Moduszu versetzen. Benachbarte Knoten bilden hierzu Gruppen, als virtual cluster bezeichnet, die sich mittels sogenannter sleep schedules synchronisieren. D.h. Knoten innerhalb eines virtual clusters tauschen Informationen dar¨ uber 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 virtual clusters 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¨ anger: Einer ist immer aktiv, arbeitet aber mit einer sehr geringen Bitrate und verbraucht deshalb auch nur wenig Energie. Der andere Empf¨ anger arbeitet mit einer h¨ oheren Bitrate und verbraucht mehr Energie, ist aber nur ca. 1% der Zeit aktiv. M¨ ochte ein Knoten eine Nachricht ¨ ubertragen, sendet er vorher ein Wecksignal samt der Knoten-

ID des Zielknotens. Dieses Signal wird von dem Zielknoten mittels des energiesparenden Funkempf¨ angers erkannt. Der Knoten kann anschließend seine regul¨ are Funkanlage anschalten, um die vollst¨ andige Nachricht zu empfangen.

2.1. SENSORNETZE 11

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 University of California entstanden.

Berkeley Mica Mote

Die an der Berkeley University of California entwickelte Mica Mote [25] geh¨ ort zu den am h¨ aufigsten in Versuchen genutzten Sensorknoten. Sie unterst¨ utzt das, ebenfalls in Berkeleyspeziell f¨ ur Sensorknoten - entwickelte Betriebsystem TinyOS (siehe auch Unterabschnitt 3.3.2. ⁴ Mittlerweile existieren mehrere Generationen von Motes. W¨ arend die erste Version CSMA/CA als MAC-Protokoll benutzt, verwendet der Mica2-Knoten (mit schnellerem Prozessor aber minimal geringerem Durchsatz als die urspr¨ ungliche Version) eine Variante dieses Protokolls mit Collision Detection (CD). Weiterhin existiert noch der Mica2Dot-Knoten (mit ¨ ahnlicher Hardware wie Mica2, aber einem langsameren Prozessor). Motes besitzen eine Uhr, die sich mittels TinyOS mit Nachbarn auf +/- 1ms synchronisieren kann [26]. Ein Grund f¨ ur die Beliebtheit von Mica ist sicherlich die einfache Verf¨ ugbarkeit f¨ ur kommerzielle Zwecke. 5

PicoRadio

PicoRadio ist ein weiteres, an der Berkeley University of California entstandenes Projekt, das sich mit der Entwicklung von Sensorknoten besch¨ aftigt. ⁶ 2002 wurden die beiden Knotentypen PicoNode I und PicoNode II fertiggestellt. 2003 demonstrierte die Projektgruppe mit Pico-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 University of California angesiedelte Smart 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¨ oße eines Kubikmillimeters nicht ¨ uberschreiten. Die geringe

Gr¨ oße soll es den Knoten erm¨ oglichen, sich fliegend fortzubewegen, allerdings nicht mittels eines aktiven Antriebs, sondern angetrieben von Luftstr¨ omungen. Die Knoten kommunizieren nicht ¨ uber 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¨ artig eine der gr¨ oß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¨ onnen, ist es entsprechend notwendig die Knoten mit mehreren Laserdioden und Photodetektoren auszustatten.

⁴ 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

2.1. SENSORNETZE 12

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¨ oglicht es, von einem anderen Knoten abgestrahltes Licht direkt auf diesen zur¨ uck zu reflektieren. Die drei Spiegel sind jeweils im rechten Winkel (wie die Ecke eines W¨ urfels, 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¨ oglicht wird.

Die Autoren beschreiben einen Versuch, bei dem die Senke an eine hochaufl¨ osende Videokamera angeschlossen ist und mit einem breit gef¨ acherten Laserstrahl einen Bereich mit Smart Dust- Knotenerleuchtet. Die Knoten reflektieren mittels des CCRs diesen Strahl, der anschließend von der Kamera detektiert wird. Mittels dieser Konstruktion ist es m¨ oglich, ¨ uber Entfernungen

von mehreren hundert Metern Datenraten von mehreren Kilobit zu erreichen. In einem solchen Szenario ist der mit einem h¨ oheren Energiverbrauch verbundene Einsatz der Laserdiode zur Kommunikation nur f¨ ur Knoten notwendig, deren Sichtkontakt zur Senke blockiert ist.

2.1.6 Anwendungen

Die meisten gegenw¨ artigen Anwendungen f¨ ur Sensornetze sind im Bereich der Umweltforschung angesiedelt.

Es befindet sich seit dem Fr¨ uhjahr 2002 ein Sensornetz zur Beobachtung eines nat¨ urlicher 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¨ uchternen, nachtaktiven Seevogels, dessen Lebensgewohnheiten noch wenig erforscht sind. Das Sensornetz ist mit einer Kombination von Temperatur-, Luftfeuchtigkeits-, Luftdruck- und Infrarotsensoren ausgestattet. Das Projekt wird von dem Intel Research Laboratory at Berkeley geleitet.

Das Princeton ZebraNet Project besch¨ aftigt 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¨ uhjahr 2005 befindet sich in der Ostsee, vor der Insel Ume ˙ a, ein Sensornetz im Ein-

satz [21], ⁹ dessen Aufgabe es ist die Meerestemperatur zu messen. Besonders in der N¨ ahe von Flussm¨ undungen herrschen im Wasser große Temperaturdifferenzen. Diese lassen sich schwer vorraussagen und ¨ andern sich im Laufe der Jahreszeiten. Sie sind f¨ ur Meeresforscher aber interessant, da die Wassertemperatur großen Einfluss auf die Flora und Fauna vor Ort hat. Auf den Sensorknoten l¨ auft die Sensornetz-Plattform ScatterWeb [28], ¹⁰ entwickelt von der Arbeitsgruppe Computer Systems & Telematics am Institut f¨ ur Informatik der Freien Universit¨ at Berlin.

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

⁷ http://www.greatduckisland.net/

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

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

¹⁰ http://www.scatterweb.net

2.2. SCHWARMINTELLIGENZ 13

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¨ aten mit gleichen Verhaltensmustern erreicht der Schwarm h¨ ohere Effektivit¨ at und ist zu wesentlich h¨ oheren Leistungen als ein einzelnes Individuum im-stande: Ameisen tragen gemeinsam Beutest¨ ucke, welche f¨ ur ein einzelnes Individuum zu schwer sind; sogar in kleinere Teile zerlegt, m¨ usste es von insgesamt mehr Ameisen getragen werden []. Termiten bauen gemeinsam meterhohe Bauten, welche ¨ uber ein ausgekl¨ ugeltes Bel¨ uftungssystem

verf¨ ugen. In Vogelschw¨ armen verbraucht durch deren charakteristische Form ein einzelner Vogel weniger Energie, da er Luftstr¨ omungen vorausfliegender V¨ ogel 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 ¨ uberwiegende Mehrheit aller technischen Verfahren ist fast ausschließlich durch das Verhalten von Insekten motiviert worden, weniger durch das Schwarm-Verhalten von V¨ ogeln und Fischen.

L¨ osungen f¨ ur Probleme der Selbstorganisation m¨ ussen Schw¨ arme schon vor langer Zeit gefunden haben. Betrachtet man die Evolution als Optimierungsprozess, liegt der Gedanke nahe, dass Verfahren von Insektenschw¨ armen 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¨ uhren den Begriff der Selbstordnung (= engl. Self-Ordering) als Gegensatz zur Selbstorganisation ein. Demnach l¨ age 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¨ ur den Sachverhalt der Emergenz. Als selbstorganisiert w¨ urde 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 effect vorliegt, d.h. der globale Zustand eines Systems wird durch Interaktionen von Sub-Komponenten des Systems bewirkt. Dabei haben diese Komponenten kein Wissen ¨ uber den globalen Zustand. Ihre Interak-

tionen werden ausschließlich durch lokale Informationen motiviert. Der globale Zustand ¨ außert sich meistens in Mustern bzw. Strukturen oder in Charakteristika wie einem speziellen Verhalten. Ein Beispiel f¨ ur ein System, welches zwar emergente Eigenschaften besitzt aber keinerlei selbst-organisierende ist beispielsweise ein K¨ orper 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¨ uhrt wird. Dar¨ uber hinaus aber beinhaltet diese Defini- ¹¹ EinSoftware-Agent wird hier lediglich betrachtet als ein autonomer Prozess, der stellvertretend (meistens f¨ ur einen Knoten) fest vorgegebene Aufgaben bearbeitet. Eine genauere Definition wird in Abschnitt 3.1 erarbeitet.

2.2. SCHWARMINTELLIGENZ 14

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¨ ur 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¨ anomene beschreiben. In technischen Anwendungen ist sicherlich, wenn ein emergentes Verfahren implementiert wird, eine Form von Organisation erw¨ unscht. Deshalb kann man davon ausgehen, dass, wenn Emergenz gezielt eingesetzt wird, sie zur Ordnung f¨ uhren soll. 12

Der Grund, warum in den letzten Jahren Emergenz als Mittel zur Selbstorganisation beliebt wurde, ist, dass es ein m¨ achtiges Paradigma zur L¨ osung von Problemen in Verteilten Systemen darstellt. H¨ aufig stellt sich in solchen Anwendungen das Problem einer sinnvollen Zusammenarbeit der einzelnen Komponenten (Router, Knoten, ...). Diese sind kaum in der Lage, eine zuverl¨ assige 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¨ ogerung und Belastung des Datenverkehrs durch Kontroll-Overhead. Der Grundgedanke der Optimalit¨ at biologischer Verfahren legt die Idee nahe, nach L¨ osungen f¨ ur 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¨ ur das Verfahren d¨ urfen nur relevante Aspekte der Verhaltensweise technisch umgesetzt werden. Biologische Aspekte des Verhaltens, die in der technischen Umsetzung nicht relevant sind, m¨ ussen 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¨ urzester 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¨ uhrt ein Pfad wieder auf sich selbst zur¨ uck, kann es passieren, dass die Ameisen nicht aufh¨ oren, den entstandenen Kreis zu verst¨ arken, sogar wenn er mehrere Kilometer durchmisst. Der Kreis bricht erst zusammen, wenn eine Mehrheit der Arbeiterinnen an Ersch¨ opfung gestorben ist.

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

¹² Nach dieser Definition kann man so gut wie jedes physische Objekt sowohl als Beispiel f¨ ur Emergenz, als auch als Beispiel f¨ ur Selbstorganisation auff¨ uhren, 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.

2.2. SCHWARMINTELLIGENZ 15

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¨ armen bestimmen. Unter Stigmergy versteht man das verbreitetste Koordinationsverfahren unter sozialen Insekten. Selbstorganisation durch Emergenz in Schw¨ armen wird meistens durch das Zusammenspiel von positivem und negativem Feedback, Verst¨ arkung 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¨ allen durch eine als Stigmergy (von lat. stigma, Zeichen) bezeichnete indirekte Form der Kommunikation: Jedes Individuum nimmt ausschließlich seine n¨ ahere Umgebung wahr und reagiert auf externe Reize, wie einem einfachen Verhaltenskatalog folgend. Durch seine Reaktion ver¨ andert das Indiviuum unter Umst¨ anden seine Umgebung. Dies bedeutet, dass nachfolgende Individuen eine ver¨ anderte Umgebung wahrnehmen und entsprechend anders reagieren. Die Individuen eines Schwarmes sind i. Allg. homogen, d.h. sie besitzen alle den gleichen Verhaltenskatalog. Die Interaktionen uber die Umgebung kommen ohne jegliche Form von direkter Kommunikation aus; dennoch ¨

f¨ uhren 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¨ onnen den Fundort einer reichhaltigen Nektarquelle mittels eines Tanzes weitergeben. Der Tanz enth¨ alt in kodierter Form die Position der Nahrungsquelle. Andere Bienen, die Zeugen dieses Tanzes sind, werden auf diese Position programmiert und unterst¨ utzen die T¨ anzerin beim Tanzen, um weitere Bienen zu rekrutieren, und bei der Nahrungssuche.

Wechselwirkende Selbstorganisationsmechanismen

a) Positives Feedback Feedback wird im Deutschen h¨ aufig mit ” R¨ uckkopplung“ ¨ ubersetzt,

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¨ arkenden Effekt, wie den Tanz der Bienen oder bei Ameisen das Absondern von Pheromon. Individuen, die einem solchen verst¨ arkenden Einfluss unterliegen, tendieren dazu, sich einer Arbeit anzuschließen. Positives Feedback induziert h¨ aufig einen Schneeballeffekt, da rekrutierte Individuen weitere Insekten f¨ ur ihre Arbeit gewinnen. Bienen, denen zwei gleich reichhaltige und gleich weit entfernte Nahrungsquellen pr¨ asentiert 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¨ arkenden Effekts wird auch von Reinforcement (=engl. Verst¨ arkung) gesprochen.

b) Negatives Feedback Als solches bezeichnet man einen selbstschw¨ achenden Effekt, der zu einer Minderung von Aktivit¨ at f¨ uhrt. Negatives Feedback wird meistens genutzt, um positivem Feedback entgegenzuwirken und einen ehemals angestrebten, jetzt aber obsolet gewordenen Zu- stand zu verlassen. Bienen z.B. k¨ onnen wenig attraktive Nahrungsquellen mit einem abstoßend

2.2. SCHWARMINTELLIGENZ 16

wirkenden Pheromon markieren. Andere Beispiele f¨ ur negatives Feedback sind Erm¨ udung und S¨ attigung von Arbeitern, Wettbewerb zwischen Nahrungsquellen und Verdunsten von Pheromonen.

Charakteristisch f¨ ur Feedback ist die selbstschwingende Eigenschaft: Eine Mischung aus st¨ arkenden (positives Feedback) und schw¨ achenden (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¨ oßten Teil immer eine Mischung f¨ ordernder und hemmender Einfl¨ usse darstellt und ein Spezialfall des idealen Regelkreises, der Abweichungen von einem Sollwert instantan korrigiert. ¹³ In der Systemtheorie und der Biologie wird diese F¨ ahigkeit eines Systems, sich durch R¨ uckkopplung selbst innerhalb gewisser Grenzen in einem stabilen Zustand zu halten, als Selbstregulation oder Hom¨ oostase ¹⁴ (auch Homoiostase, griechisch: µoιoστ αση, zu deutsch: Gleich-Stand) bezeichnet. Dieser Begriff wurde 1929 von Walter Cannon eingef¨ uhrt. 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¨ ugeln schlagen. Turner hat in diesem Zusammenhang den Term social homeostasis gepr¨ agt [4].

Parunak bezeichnet in [3] solche zyklisch auftretenden Prozesse in Schwarrmen, die mittels Feedback zur Selbstorganisation f¨ uhren, als ” autokatalytisch“ . Demnach ist ein wichtiges Charakteristikum solcher Prozesses, dass sie sich gegenseitig initialisieren.

c) Verst¨ arkung von Fluktuationen In diese Kategorie geh¨ oren Zuf¨ alle, 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¨ uck und haben die gr¨ oßte Chance, mit ihrer Pheromonspur den Grundstein f¨ ur einen Pfad zu legen. Dieses zufallsbasierte Konzept der Erforschung macht sich zunutze, dass in Schw¨ armen eine sehr große Anzahl von Individuen zur Verf¨ ugung steht. Diese Entdeckungen einzelner erm¨ oglichen es dem System, lokalen Maxima (d.h. einer suboptimalen L¨ osung) 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¨ uchtigt sich das Pheromon zu schnell, welches die Ameisen zusammen h¨ alt.

Spezialisierung

Eine Form der Arbeitsteilung findet bei allen sozialen Insekten statt. Viele Ameisenarten bestehen (neben der K¨ onigin und Drohnen) aus Arbeitern und Soldaten, letztere sind i. Allg. gr¨ oßer und besitzen st¨ arkere 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¨ oren. Ein Individuum besitzt f¨ ur jede relevante Aufgabe eine Reaktionsschwelle und einen Stimulus. Als Stimulus wird hier ein (z.B. visueller oder olifak-torischer) Anreiz bezeichnet, einer Aufgabe nachzukommen. Die Reaktionsschwelle bezeichnet

¹³ Z.B. Thermostat

¹⁴ Z.B. Aufrechterhaltung der K¨ orpertemperatur

2.2. SCHWARMINTELLIGENZ 17

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¨ oheren Wahrscheinlichkeit nachkommen. Das Nachgehen einer Arbeit ist mit dem Abbau des Stimulus verbunden: Das F¨ uttern von Larven stoppt deren Ausstoß von Hunger-Pheromonen, das Entsorgen von Leichen senkt den Stimulus, diese zu entfernen. ¨ Uber

einen l¨ angeren 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¨ arme eine einzigartige Weise der kollektiven Zusammenarbeit, die einige bemerkenswerte St¨ arken hat:

Robustheit Vor allem durch Nutzung des indirekten Kommunikationsverfahrens des Stigmergy wird eine hohe Robustheit schwarmbasierter Verfahren erzielt. Subkomponenten eines Schwarmes m¨ ussen sich bei ¨ Anderungen ihrer Umgebung nicht auf einen neuen Plan einigen,

sondern sie reagieren kollektiv auf das ver¨ anderte Umfeld. Durch die hohe Anzahl von Individuen in einem Schwarm besitzt dieser eine hohe Redundanz. Der Ausfall einzelner Komponenten wirkt sich nur geringf¨ ugig auf die Leistung des Gesamtsystems aus.

Einen weiteren großen Vorteil schwarmbasierter Verfahren stellt die Tatsache dar, dass sie mit verh¨ altnim¨ aß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¨ at Schwarmbasierte Verfahren stellen ein wandlungsf¨ ahiges Koordinationsprinzip f¨ ur 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¨ aten erreicht. Sie sind prinzipiell f¨ ur mehrere Arbeiten einsetzbar und sind imstande, sich selbst¨ andig in Arbeitsgruppen aufzuteilen.

In der Kombination aus Robustheit und Flexibilit¨ at liegt die wahre St¨ arke der Schwarmintelligenz. Aufgrund ihrer F¨ ahigkeit, sich schnell an neue Bedingungen anzupassen, entfalten schwarmbasierte Verfahren ihr ganzes Potential erst in dynamisch sich ¨ andernden Umgebungen [2].

2.2.5 Schwarmbasierte Anwendungen

Kombinatorische Optimierungsverfahren

Bereits 1992 formulierte Dorigo die Idee, die F¨ ahigkeiten von Schw¨ armen zum Aufsp¨ uren k¨ urzester Wege technisch zu nutzen [31, 2]. Die meisten der aktuellen Verfahren beruhen auf der Ant Colony Optimization (ACO)-Metaheuristik, die er 1999 mit Caro formulierte [31, 2]. Einzelne Ameisen-Agenten belasten iterativ einzelne L¨ osungen mit einem Pheromon-Analogon. Die Belastung f¨ allt bei besseren L¨ osungen st¨ arker aus. In jeder Iteration sind die Agenten bestrebt, st¨ arker belastete L¨ osungen zu beschreiten. Durch dieses positive Feedback wird schließ- lich eine der besten gefundenen M¨ oglichkeiten als L¨ osung favorisiert. Die Qualit¨ at der von

2.2. SCHWARMINTELLIGENZ 18

ACO-Algorithmen gefundenen L¨ osungen liegt auf einer Stufe mit Simulated Annealing und Genetischen Algorithmen. Eine vollst¨ andige ¨ Ubersicht ¨ uber aktuelle Anwendungen der ACO- Metaheuristikf¨ ur kombinatorische Optimierungsverfahren gibt Guntsch in [31].

Viele ACO-Algorithmen dienen zum Finden eines k¨ urzesten Pfades in einem Graph. Einer der fr¨ uhesten schwarmbasierten Algorithmen war ein L¨ osungsalgorithmus des Travelling Salesman Problem (TSP). Andere ACO-Algorithmen f¨ ur kombinatorische Optimierungsverfahren in Graphen beinhalten L¨ osungen f¨ ur das Graph Coloring Problem. Auch f¨ ur Scheduling-Probleme wie das Single Machine Total Weighted Tardiness Problem (SMTWTP) existieren L¨ osungen, die auf der ACO-Metaheuristik basieren.

Eine Variante des ACO-Algorithmus dient zur L¨ osung des Shortest Common Supersequence Problem (SCSP). Ziel ist das Finden einer speziellen Buchstabenkette (= engl. string) in einem Superstring. Anwendungen f¨ ur dieses Problem beinhalten Ans¨ atze zur DNA-Analyse.

Particle Swarm Optimization (PSO) ist eine andere schwarmbasierte Optimierungsmethode und basiert auf dem Verhalten von Fischschulen und Vogelschw¨ armen. Individuen solcher Schw¨ arme koordinieren sich, indem sie ad¨ aquaten Abstand zu wenigen anderen Individuen ihres Schwarmes halten. Dar¨ uberhinaus 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¨ asst. Die PSO-Metaheurisitik wurde 1995 von Eberhard & Kennedy in [33] formuliert. Sie erreicht in Versuchen L¨ osungen, deren Qualit¨ at 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¨ aßig in einer Zone die zu bef¨ ordernden Briefe abholen. M¨ ussen Bewohner lange darauf warten, dass ihre Briefe abgeholt werden, dient diese Wartezeit als Stimulus f¨ ur einen Postboten, um diese Gegend wieder zu besuchen und dort uberf¨ allige 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¨ ur ein spezielles Gebiet. Wurde allerdings einer der Spezialisten aus der Simulation entfernt, so begann f¨ ur Spezialisten in benachbarten Zonen die Reaktionsschwelle zur ¨ Ubernahme dieser Zone zu sinken, bis schließlich ein anderer Agent die Zone regelm¨ aßig besuchte.

Sortieren

Eine Variation der Arbeitsweise mit Stimulus und Reaktionsschwelle kann genutzt werden, um simulierte Ameisen zum Analysieren und Sortieren von Datens¨ atzen zu gewinnen. Die Arbeitsweise eines einzelnen Individuums l¨ asst sich einfach folgendermaßen beschreiben: Zu sortierende Gegenst¨ ande werden aufgenommen, wenn sie sich stark von Gegenst¨ anden in ihrer Gegend unterscheiden; sie werden abgelegt, wenn ¨ ahnliche Objekte in der N¨ ahe sind. Soziale Insekten nutzen dieses Verfahren in ihren Brutkammern, um Eier und Larven, die sich in einem ¨ ahnlichen Ent- wicklungsstadium befinden, bei einander zu halten, oder um tote Artgenossen oder Beutetiere

2.2. SCHWARMINTELLIGENZ 19

zu sammeln. Ein entsprechender Algorithmus wurde von Lumer et al. (beschrieben in [2]) entwickelt, um Bankkontenprofile zu ordnen. Eine ¨ Ahnlichkeit zu anderen Datens¨ atzen wird durch eine Metrik ¨ uber die Eintr¨ age im Datensatz festgestellt.

Eine vereinfachte Form des Sortierverhaltens wird von Ameisen zur Sammlung toter Individuen genutzt: ¨ Uber eine Fl¨ ache 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¨ aß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¨ urzester Pfade in statischen Umgebungen bew¨ ahrt hat, Schw¨ arme aber in einer h¨ ochst dynamischen Umgebung leben, ist der Gedanke naheliegend, dass auf Schw¨ armen basierende Algorithmen besonders f¨ ur Netzwerke geeignet sind. Die Dynamik in Netzwerken beruht vor allem auf ¨ Anderungen der Ei-

genschaften des Netzwerkverkehrs. Diese sind m¨ oglicherweise periodisch, z.B. durch Tageszeiten bedingt, entstehen aber vor allem durch die Einzelaktionen einzelner Akteure (in technischen Anwendungenm meistens Agenten). Weiterhin k¨ onnen der Ausfall von Teilen des Netzwerks, aber besonders bei mobilen Netzwerken auch die ¨ Anderung der zugrunde liegenden Topologie, zu einer hohen Dynamik f¨ uhren.

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 Gra-phentheorie zur¨ uckgegriffen.

AntNet Einer der popul¨ arsten 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¨ arkung von Fluktuationen) der schwarmbasierten Selbstorganisation zur Etablierung eines Pfades von einem Start- zu einem Zielknoten. AntNet hat besonders aufgrund einer Neuerung Popularit¨ at erlangt: Probabilistischer Routingtabellen. ¹⁵ Einem Knoten wird f¨ ur jedes Ziel nicht nur ein einzelner Knoten als n¨ achster Hop zugeordnet, sondern jedem Nachbarn wird eine Wahrscheinlichkeit zugeordnet, als n¨ achster Hop auf dem Weg zum Ziel zu dienen. Es bezeichnet P k n,z die Wahrscheinlichkeit am Knoten k, falls z der Zielknoten f¨ ur eine Nachricht uber den Nachbarknoten n

zu senden. (Werden im folgenden ¨ ist, diese ¨ keiten lediglich an einem Knoten k beschrieben, so wird teilweise die vereinfachende Schreibweise P n,z f¨ ur die Wahrscheinlichkeit eines ¨ Ubergangs nach n mit dem Ziel z benutzt. Ist das Zielwie z.B. in Sensornetzen mit nur einer Senke - eindeutig, so wird die Schreibweise P ^k ¨ Ubergangswahrscheinlichkeit von Knoten k zu Nachbar n

benutzt.) Die Wahrscheinlichkeiten sind f¨ ur jeden Knoten (und jedes Ziel) normiert. Seien N k die Nach-

barknoten von k, dann gilt:

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:

¹⁵ Probabilistische Routingtabellen wurden zuerst 1996 von Ant-Based Control (ABC) eingesetzt [2]. Aufgrund seines eingeschr¨ ankten Einsatzgebietes - ABC wurde entwickelt f¨ ur Telefonnetze - erreichte dieser schwarmbasierte Routing-Algorithmus allerdings nie die Popularit¨ at AntNets.