Was können Informatiker von Ameisen
lernen?
Mesut Günes, Otto Spaniol
Lehrstuhl Informatik 4
Mobile Kommunikationsnetze bestehen aus zahlreichen Rechnern, deren Topologie sich schnell und unvorhersehbar ändern kann. Für ein solches Netz ist eine zentrale Verwaltung ungeeignet, denn sie kann zum Engpass werden. Im Falle einer Störung der Zentrale ist das Netz nicht mehr funktionsfähig. Daher sind Konzepte gefragt, die ohne Zentrale auskommen. Es gibt biologische Systeme, welche diese Aufgabe überraschend clever lösen. Ein solches Prinzip wird im Folgenden beschrieben und auf das Auffinden von Wegen in mobilen Netzen angewandt.
Ameisen und ihre „Schwarmintelligenz“
Ameisen leben in so genannten Kolonien, deren Größe zwischen 10.000 und einigen Millionen Tieren variiert. Die Kolonie hat ein „Nest“, das dem Bedarf entsprechend ausgebaut wird.
Die Kolonie muss organisiert und strukturiert sein, um überleben zu können. Ameisen besitzen aber keine direkte Kommunikationsmöglichkeit durch Sprache, Augenkontakt oder Tastsinn. Stattdessen kommunizieren sie indirekt miteinander über Botenstoffe (so genannte Pheromone). Dabei handelt es sich um chemische Substanzen, die bestimmte Aktivitäten veranlassen, wenn sie von Ameisen wahrgenommen werden. Die Mitglieder einer Kolonie sind in der Lage, Pheromone verschiedener Kolonien voneinander zu unterscheiden.
Die Ameisenkolonie ist also nicht zentral organisiert, sondern jede Ameise arbeitet autonom. Durch die von den Pheromonen ausgelösten Aktivitäten ergibt sich eine Gesamtorganisation, ohne dass der einzelnen Ameise dies bewusst ist. Man bezeichnet dieses Verhalten auch als Schwarmintelligenz. Am Beispiel der Futtersuche soll das Prinzip verdeutlicht werden.
Abbildung 1: Blattschneiderameisen auf Nahrungssuche.
Mit freundlicher Genehmigung von Alex Wild (photo @ Alex Wild).
Futtersuche bei Ameisen
Wenn Ameisen auf Futtersuche gehen, wissen sie zunächst nicht, wo sich Futter befindet. Sie entdecken die Nahrung also eher zufällig. Sobald eine Ameise Nahrung findet, nimmt sie etwas davon auf und tritt den Rückweg an. Dabei scheidet sie Pheromone aus und kennzeichnet so den Weg zur Futterstelle. Ameisen, die sich in der Nähe befinden, bemerken die Pheromone und werden dadurch ebenfalls zur Futterstelle geleitet. Auch sie tragen Nahrung zum Nest und scheiden dabei Pheromone aus, wodurch sich die Pheromonintensität verstärkt. Auf diese Weise entsteht eine positive Rückkopplung, denn immer mehr Ameisen entscheiden sich für den gefundenen Weg vom Nest zur Futterstelle (siehe Abbildungen 1 und 2). Dieser Rückkopplung wirkt mit der Zeit eine Verflüchtigung der Pheromone entgegen, was aber den Vorteil hat, dass Wege zu bereits ausgebeuteten Futterstellen nach kurzer Zeit nicht mehr begangen werden.
Abbildung 2: Schwarmintellligentes Verhalten von Ameisen.
a) Es gibt zwei Wege vom Nest zum Futterstelle. Der obere Weg ist länger als der untere.
b) Ameisen finden über beide Wege zur Futterstelle. Die Ameisen, die den kürzeren Weg benutzen, sind jedoch schneller. Dadurch erhält die Pheromonkonzentration auf dem kürzeren Weg einen höheren Wert.
c) Schließlich benutzen fast alle Ameisen den kürzeren Weg zur Futterstelle und zurück.
Die Kommunikation bei der Futtersuche geschieht also über Pheromone. Dabei agiert jede Ameise autonom und entscheidet selbstständig über den Weg zum Futter.
Von der Schwarmintelligenz zur Informatik
Die Futtersuche der Ameisen ist ein gutes Beispiel dafür, wie in der Natur ein komplexes Problem durch unkoordiniert arbeitende Individuen effizient gelöst wird. Es gibt sehr interessante Analogien und Anwendungsmöglichkeiten bei Kommunikationssystemen, die wir im Folgenden aufzeigen.
Ein wichtiges Problem in Kommunikationsnetzen ist das effiziente Auffinden von Wegen für den Datentransport. Dieses Problem wird in spontan entstehenden Netzen ohne feste Infrastruktur (so genannte mobile Ad-hoc-Netze) zusätzlich dadurch erschwert, dass sich die Knoten unabhängig voneinander bewegen und dass sich dadurch die möglichen Verbindungswege häufig ändern. Die Verbindungen werden meist über mehrere Zwischenknoten geführt. Alte Wege können unbenutzbar werden und es müssen möglichst schnell neue unter Einbezug anderer Zwischenknoten gefunden werden, um die Kommunikation aufrecht zu erhalten. Nebenbei bemerkt darf man durchaus darauf hinweisen, dass die Thematik „mobile Ad-hoc-Netze“ ursprünglich dem militärischen Bereich entstammt – wie so vieles aus der Informatik, was dann später nützliche nichtmilitärische Anwendungen gefunden hat (das Internet ist ein prominentes Beispiel dafür): Das Problem der Koordination von Panzern in der Wüste während des Golfkriegs hat ziemlich sicher bei den ersten Überlegungen zu mobilen Ad-hoc-Netzen Pate gestanden.
Wir stellen jetzt ein am Lehrstuhl Informatik 4 der RWTH Aachen entwickeltes Verfahren vor, das die Schwarmintelligenz von Ameisen für die Bestimmung von Wegen (so genanntes Routing) in mobilen Ad-hoc-Netzen zum Vorbild nimmt.
Der Ameisenroutingalgorithmus
Der Algorithmus besteht aus drei Phasen:
- Pfadfindung: Es werden Pfade zwischen einem Quell- und einem Zielknoten gesucht. Diese Phase entspricht der Futtersuche von Ameisen, wobei die Quelle als Nest und das Ziel als Futterstelle fungiert. Zunächst ist kein Weg zwischen Quelle und Ziel bekannt.
- Pfadpflege: Hier werden gefundene Pfade zwischen Quelle und Ziel verwaltet.
- Fehlerbehandlung: Diese Phase ist für die Behandlung von Fehlern zuständig, die z.B. dadurch entstehen, dass sich ein Knoten bewegt und eine zuvor bestehende Verbindung unterbrochen wird.
Wenn die Quelle Daten zum Ziel senden möchte, sucht sie zuerst in ihrer Routingtabelle – das ist eine Datenbank, die zunächst leer ist und sich nach und nach mit „gelernten“ Einträgen füllt - nach einem Pfad. Bei Erfolg kann mit der Datenübertragung begonnen werden, andernfalls startet Phase 1.
Pfade werden durch Vorwärtsameisen (VA) und Rückwärtsameisen (RA) erzeugt. Eine Vorwärtsameise legt eine Pheromonspur zurück zur Quelle – ebenso wie Theseus den Faden der Ariadne benutzte, um den Weg zum Eingang des Labyrinths des Minotaurus wiederzufinden. Übrigens hätte es eines solchen Fadens nicht wirklich bedurft, denn ein Labyrinth in der Antike hatte nur einen einzigen (!) verschlungenen Weg, der kreuzungsfrei ins Zentrum und wieder zurückführte. Die komplexeren Irrgärten mit zahlreichen Wegalternativen tauchten erst im ausgehenden Mittelalter auf. Irrgärten sind also eine bessere Veranschaulichung dessen, was eine Vorwärtsameise tut, als der Ariadnefaden – nämlich eine Spur zum vorherigen Abzweigungspunkt zu legen, von dem aus man sich dann sukzessive zur Quelle zurückhangeln kann. Analog dazu legt eine Rückwärtsameise eine Pheromonspur zurück zum Ziel. Beide Ameisenarten sind informatisch betrachtet kleine Datenpakete, die Informationen zu ihrer Identifikation und zur Erkennung von Duplikaten enthalten.
Die VA-Nachricht der Quelle wird von den direkt erreichbaren Nachbarn weitergeleitet (siehe Abbildung 3a). Ein Knoten, der eine VA-Nachricht zum ersten Mal empfängt, erzeugt einen Rückwärts-Eintrag in seiner Routingtabelle, woraus er erkennt, wie die VA-Nachricht von der Quelle zu ihm gelangte. Dieser Eintrag ist von der Form (Quelladresse, Nachbar, Pheromonkonzentration). Dabei ist „Nachbar“ die Adresse des Knotens, von dem die VA-Nachricht kam. Anschließend leitet der Knoten die VA-Nachricht an seine direkten Nachbarn weiter. Jede VA-Nachricht wird pro Knoten nur einmal versandt, Duplikate werden erkannt und verworfen. Der Zielknoten versendet nach Empfang einer VA-Nachricht eine RA-Nachricht zurück zur Quelle über die inzwischen bekannten Wege (siehe Abbildung 3b). Nachdem die Quelle die RA-Nachricht empfangen hat, können Daten zwischen Quelle und Ziel ausgetauscht werden.
Abbildung 3: Pfadfindung. S (= source) ist das Nest und D (= destination) ist die Futterstelle.
a) S sendet eine Vorwärtsameise VA aus, wodurch eine Pheromonspur zurück zu S gelegt wird.
b) D verschickt nach dem Empfang von VA eine Rückwärtsameise RA zurück zu S. Danach kennen die Netzknoten einen oder mehrere Wege zwischen S und D.
Einmal etablierte Pfade müssen im laufenden Betrieb gewartet und verbessert werden. Wenn die Pheromonspuren durch VA- und RA-Nachrichten ausgelegt sind, erfolgt die Pfadpflege durch nachfolgende Datenpakete, wobei die Änderung der aktuellen Pheromonwerte eine wichtige Rolle spielt. Wenn Knoten M ein für das Ziel D bestimmtes Datenpaket an seinen Nachbarn N weiterleitet, erhöht er die Pheromonkonzentration für den Routingtabelleneintrag (D, N, j) um den Wert Dj, d.h. der entsprechende Pfad zum Ziel wird verstärkt. Analog dazu erhöht N den Eintrag (S, M, j) um Dj, d.h. der Pfad zur Quelle wird ebenfalls gestärkt. Dieser positiven Rückkopplung wirkt eine negative Rückkopplung entgegen, denn die Pheromonwerte schwächen sich im Laufe der Zeit durch Verdunstung ab. Solche Effekte kann man unterschiedlich modellieren – z.B. durch konstante Verdunstung pro Zeiteinheit, aber auch andere Modelle sind denkbar: Hier sind Computer deutlich flexibler als Ameisen, die für solche Evolutionsschritte viele Tausende von Jahren benötigen würden.
Bewegt sich ein Knoten aus der Reichweite seines Nachbarn, führt dies möglicherweise zum Verbindungsabbruch. Es muss dann versucht werden, die Kommunikation über einen anderen Nachbarn weiterzuführen. Nach Möglichkeit werden mehrere Wege zwischen Quelle und Ziel in der Routingdatenbank der Netzknoten gespeichert, um bei Unterbrechungen auf alternative Wege umschalten zu können. Wenn kein anderer Weg bekannt ist, wird die Quelle informiert und Phase 1 beginnt von neuem.
Es gibt zahlreiche mit dem Ameisenalgorithmus konkurrierende Routingverfahren, aber es hat sich gezeigt, dass unser Algorithmus den Vergleich mit diesen sehr gut besteht.