Leseprobe
Inhaltsverzeichnis
1 Problem- und Aufgabenstellung
2 Einleitung
3 Grundlagen
3.1 Mobile Ad-hoc-Netzwerke
3.1.1 Eigenschaften von mobilen Ad-hoc-Netzwerken
3.1.2 Anwendungsgebiete
3.2 Routing in mobilen Ad-hoc-Netzwerken
3.2.1 Anforderungen an MANET-Routingprotokolle
3.2.2 Kategorien von Ad-hoc-Routingprotokollen
3.3 Schwarmintelligenz
3.3.1 Selbstorganisation sozialer Insekten
3.3.2 Schwarmkommunikation
3.3.3 Ameisenalgorithmen
3.4 Fazit
4 Ausgewählte Routingprotokolle für Mobile Ad-hoc-Netzwerke
4.1 OLSR
4.2 AODV
4.3 ARA
4.4 PERA
4.5 SWARM
4.6 Fazit
5 Methodik
5.1 Der Simulator
5.2 Die Simulationsumgebung
5.3 Das Bewegungsmodell
5.4 Das Kommunikationsmodell
5.5 Metriken
5.6 Implementierung der Simulation
6 Ergebnisse der Simulation
6.1 Packet Delivery Ratio
6.2 Average End-to-End Delay
6.3 Path Optimality
6.4 Troughput
7 Fazit und Ausblick
Abbildungs- und Tabellenverzeichnis
Abkürzungsverzeichnis
Literaturverzeichnis
1 Problem- und Aufgabenstellung
Ein mobiles Ad-hoc-Netzwerk (MANET) besteht aus einer Menge von Knoten, die über Funk miteinander kommunizieren. Knoten in einem MANET bewerkstelligen dies, indem sie sich, ohne über eine Infrastruktur zu verfügen, selbst organisieren. MANETs sind darüber hinaus Netzwerke, die von hoher Dynamik gekennzeichnet sind, diese Netze müssen daher flexibel auf Topologieänderungen reagieren.
Selbstorganisation bedeutet in einem MANET, dass die einzelnen Knoten auch Routingfunk- tionalität übernehmen müssen. Aufgrund der hohen Dynamik eines MANETs ist die Routing- problematik die größte Herausforderung in MANETs. Da Ad-hoc-Netzwerkknoten nur direkt mit Knoten, die sich in ihrer Reichweite befinden, kommunizieren können, müssen sie, um weiter entfernte Knoten erreichen zu können, miteinander bezüglich des Routings kooperieren.
Um die geforderte Knotenkooperation in einem MANET effizient gewährleisten zu können, kann man sich des Vorbilds des Verhaltens sozialer Insekten, wie z. B. Bienen oder Ameisen, bedienen. In solchen Schwärmen wird durch das Zusammenarbeiten relativ einfacher Individuen eine komplexe Aufgabe gelöst.
Für das Routing in Netzwerken ist besonders das Futtersuchverhalten von Ameisen interessant, da Ameisen sehr schnell kürzeste Pfade von ihrem Nest zu einer Futterquelle finden. So wurde eine Reihe von Routingalgorithmen entwickelt, die bei der Suche des kürzesten Pfades in einem Netzwerk auf diesem Schwarmintelligenz-Paradigma und im Besonderen auf der Ant-Colony- Optimization-Metaheuristik (ACO-Metaheuristik) basieren.
Im Rahmen dieser Arbeit wird untersucht, wie sich schwarmintelligenzbasierte MANET- Routingprotokolle im Vergleich mit etablierten MANET-Routingprotokollen bewähren.
2 Einleitung
Ad-hoc-Netzwerke sind kabellose, mobile Netzwerke ohne Infrastruktur, die jederzeit überall gebildet werden können. Die Kommunikation in einem solchen dezentralen Netzwerk erfolgt typischerweise über temporäre Multihop-Relays, wobei einige Knoten als Router agieren, ohne dass eine fixe Infrastuktur vorhanden ist.
Diese Art von Netzen ist sehr flexibel und kann dort sinnvollen Einsatz finden, wo es nur wenig oder gar keine Kommunikationsinfrastruktur gibt, beispielsweise bei Katastropheneinsätzen oder militärischen Operationen.
Doch das Multihop-Routing, die willkürlichen Knotenbewegungen und andere MANET- Eigenheiten bedeuten eine große Herausforderung für das Routing – das Hauptproblem in einem Netzwerk. Dazu kommen, verglichen mit einem herkömmlichen Netzwerk, weitere Ein- schränkungen wie z. B. begrenzte Energieressourcen oder Bandbreiten der Knoten. Es stellt sich also die Frage, wie die Routenfindung und -pflege in einer solch schwierigen Umgebung möglichst effizient gelöst werden kann.
Da zumindest seit dem Jahr 1973 auf dem Gebiet der MANETs geforscht wird, gibt es be- reits eine Vielzahl von Routingalgorithmen, die speziell auf die Gegebenheiten von MANETs zugeschnitten worden sind. Einige basieren auf Routingmechanismen der tradionellen kabel- gebundenen Netzwerke und versuchen, jederzeit Routinginformationen über alle Netzknoten zu verwalten, während reaktive Ansätze nur dann neue Routen zu finden versuchen, wenn benötigt.
Seit den 1990er-Jahren existiert eine neue Gruppe von Routingalgorithmen, die, vom Schwarmintelligenz-Paradigma inspiriert, einen neuen Ansatz zur Lösung von verteilten Opti- mierungsproblemen darstellen. Hierbei bildet man das natürliche Vorbild des kollektiven Verhal- tens von sozialen Tiergesellschaften, wie z. B. das Futtersuchverhalten von Ameisenkolonien, auf mathematische Probleme wie das Finden eines kürzesten Pfades durch ein Netzwerk ab.
Ameisen sind in der Lage, innerhalb kurzer Zeit einen optimalen Pfad von ihrem Nest zu einer Futterquelle zu finden und zu erhalten. Schwarmintelligenz stellt also eine Grundlage dar, verteilte Optimierungsprobleme ohne das Vorhandensein einer zentralen Kontrollinstanz zu lösen.
Es gibt seit einigen Jahren einige Algorithmen, die sich die Eigenschaften von futtersuchen- den Ameisen zunutze machen, um mit einfachen, ameisenähnlichen Agenten die in MANETs benötigten verteilten Verfahren zur Lösung der Routingproblematik zu verwirklichen.
In dieser Arbeit werden ausgewählte schwarmintelligenzbasierte Routingprotokolle (ARA, PE- RA, SWARM) und tradionelle Routingprotokolle (OLSR, AODV) näher beschieben und mittels NS-2 Netzwerk-Simulator in einer simulierten Umgebung einem Leistungsvergleich unterzogen.
Die Arbeit ist wie folgt aufgebaut:
In Kapitel 3 werden grundlegende Eigenschaften von MANETs sowie deren mögliche An- wendungsgebiete beschrieben. Danach wird genauer auf die Routingproblematik in mobilen Ad-hoc-Netzen eingeganen, es werden die Anforderungen an Routingalgorithmen benannt und eine grobe topologische Klassifikation der Protokolle wird erstellt. In Kapitel 3.3 wird dann das Schwarmintelligenz-Paradigma eingehend erläutert: Ausgehend von den natürlichen Vor- bildern – im Falle dieser Arbeit sind dies Ameisenkolonien – wird beschrieben, wie Selbstorga- nisation und Schwarmkommunikation funktionieren. Darauf aufbauend wird das Konzept der Ameisenalgorithmen vorgestellt, im Speziellen der erste Vertreter dieser Algorithmusart: Ant System (AS).
In Kapitel 4 werden jene Routingprotokolle vorgestellt und näher beschrieben, die später einem Leistungsvergleich unterzogen werden: OLSR als Vertreter der proaktiven Protokolle, AODV als Vertreter der reakiven Protokolle sowie die schwarmintelligenzbasierten Protokolle ARA, PERA und SWARM.
In Kapitel 5 wird die Methodik, die dem praktischen Teil der Arbeit zugrunde liegt, erläutert. Zunächst wird ein grober Überblick über die Funktionalität des Netzwerk-Simulators NS-2 gegeben. Danach wird detailliert auf das Szenario der durchgeführten Simulation eingegan- gen, und die verwendeteten Metriken werden erläutert. Das Kapitel schließt mit einer kurzen Beschreibung der konkreten Simulationsimplementierung. Die Quelltexte der eigens für dieses Experiment erstellten Programme befinden sich im Anhang.
In Kapitel 6 werden die Ergebnisse der Simulation präsentiert.
Kapitel 7 schließt die Arbeit mit einer Zusammenfassung der vorgestellten Erkenntnisse und einem kurzen Ausblick ab.
3 Grundlagen
In diesem Kapitel werden kurz die Themenbereiche erläutert, die die Grundlagen für die nach- folgenden Kapitel darstellen. Zunächst werden die wichtigsten Eigenschaften und Anwendungs- gebiete von mobilen Ad-hoc-Netzwerken beschrieben. Danach wird dargelegt, welche Anforde- rungen aufgrund der speziellen Eigenschaften von mobilen Ad-hoc-Netzwerken an Routingal- gorithmen gestellt werden. Es folgt eine kurze Klassifikation der für Ad-hoc-Netzwerke üblichen Algorithmen. Den letzten Teil dieses Kapitels bildet das Thema Schwarmintelligenz: Behandelt werden relevante Bereiche wie die Selbstorganisation sozialer Insekten und die Kommunika- tion innerhalb eines Schwarmes sowie Ameisenalgorithmen – als der konkrete Teilbereich der Schwarmintelligenz, der die Grundlage für die zu untersuchenden schwarmintelligenzbasierten Routingprotokolle in dieser Arbeit darstellt.
3.1 Mobile Ad-hoc-Netzwerke
Ein mobiles Ad-hoc-Netzwerk (MANET) besteht aus mobilen Geräten (Knoten), die sich be- liebig bewegen können. Jeder dieser Knoten besteht logisch gesehen aus einem Router, der mehrere Hosts und auch mehrere drahtlose Kommunikationsgeräte besitzen kann. Ein MA- NET ist ein autonomes System von mobilen Knoten. Ein solches Netzwerk besitzt keine feste Infrastruktur und muss sich selbst organisieren. Ein MANET kann isoliert operieren oder über Gateway-Router mit anderen Netzen verbunden sein (Corson & Macker 1999, S. 3).
3.1.1 Eigenschaften von mobilen Ad-hoc-Netzwerken
In der Literatur werden Ad-hoc-Netzwerke meist nach der Art, wie Knoten miteinander kom- munizieren (single-hop oder multihop), unterschieden. Eine weitere Unterscheidung wird in flache oder hierarchische Netze vorgenommen (Perkins 2001, S. 43).
Bei Single-hop-Netzwerken befinden sich die Knoten in direkter Reichweite, d. h., zwei Kno- ten können direkt miteinander kommunizieren, ohne dass der Kommunikationsverkehr über andere Knoten weitergeleitet werden muss. In einem mobilen Multihop-Netzwerk hingegen muss der Kommunikationsverkehr zwischen einem Quell- und Zielknoten über Zwischenkno- ten weitergeleitet werden. Weil die einzelnen Knoten mobil sind, ist die Netztopologie ständigen Veränderungen ausgesetzt.
Da die Multihop-Topologie die vorherrschende Topologie in MANETs ist, wird im weiteren Verlauf dieser Arbeit nur noch auf mobile Multihop-Ad-hoc-Netzwerke eingegangen.
MANETs haben nach Corson & Macker (1999, S. 3f) folgende herausragende Eigenschaften:
Dynamische Topologie: Da sich Knoten frei bewegen können, kann sich die Netzwerkto- pologie zufällig und schnell zu unvorhersehbaren Zeiten ändern. Verbindungen zwischen Knoten können uni- oder bidirektional sein, und das Routing hat typischerweise Multihop- Charakter.
Bandbreitenbeschränkung, variable Verbindungskapazitäten: Drahtlose Verbindungen haben eine wesentlich niedrigere Kapazität als drahtgebundene Verbindungen. Außer- dem ist der tatsächliche Durchsatz von drahtlosen Verbindungen meist niedriger als der maximal mögliche Wert einer Radiowellen- Übertragung. Das wird durch verschiedene Faktoren wie mehrfacher Zugriff auf das Medium, Hintergrundrauschen, Multihopping, die exponentielle Abschwächung des Signals sowie Interferenzen nahe gelegener, draht- loser Verbindungen hervorgerufen.
Energieabhängiger Betrieb: In einem MANET haben viele oder auch alle Knoten nur eine beschränkte Energiemenge zur Verfügung. Aus diesem Grund ist die Optimierung des Energieverbrauchs dieser Knoten das wichtigste Designkriterium.
Eingeschränkte physische Sicherheit: Drahtlose Netzwerke sind prinzipiell anfälliger ge- genüber physikalischen Sicherheitsbedrohungen als drahtgebundene Netze. So besteht eine erhöhte Wahrscheinlichkeit, dass Pakete verworfen oder gefälscht werden, und auch Denial of Service“-Attacken sind einfach durchzuführen. Oft werden Punkt-zu-Punkt- ” Sicherheitsverfahren verwendet, um die Sicherheitsbedrohung zu reduzieren. Als Vor- teil eines MANETs kann jedoch der dezentralisierte Charakter gewertet werden. Das Netzwerk wird dadurch robuster gegen einzelne Knotenausfälle als bei zentralisierten Ansätzen.
3.1.2 Anwendungsgebiete
Die wichtigsten Anwendungsgebiete von MANETs sind generell Bereiche, in denen keine ent- sprechende Infrastruktur zur Verfügung steht und Netzwerke unterschiedlicher Größe schnell und dynamisch konfiguriert werden müssen. MANETs können nach Perkins (2001, S. 8–14) u. a. in folgenden Bereichen Anwendung finden:
Mobile Konferenz: Wenn sich die Benutzer von mobilen Computern außerhalb ihrer nor- malen Büroumgebung treffen, fehlt oft die nötige Netzwerkinfrastruktur, um eine Zu- sammenarbeit zu ermöglichen. Daher ist der Aufbau von Ad-hoc-Netzen zur Zusam- menarbeit von Benutzern, die mobile Computer haben, sogar dann notwendig, wenn die Internetinfrastruktur schon vorhanden ist.
Heimnetzwerk: Wenn ein Benutzer einen mobilen Computer sowohl im Büro als auch zu Hause verwendet, ist es möglicherweise bequemer, zu Hause ein Ad-hoc-Netzwerk auf- zubauen, um die IP-Adressen für den mobilen Computer nicht oft ändern zu müssen.
Katastrophensituationen: Typischerweise brechen die meisten auf drahtgebundenen Netzen basierenden Kommunikationsinfrastrukturen in Katastrophengebieten zusammen. Des- wegen können sich Rettungsteams nicht auf eine vorhandene Kommunikationsinfrastruk- tur verlassen, sondern müssen diese selbst errichten. Hier ist meist keine exakte Planung im Voraus möglich und die Errichtung eines Kommunikationsnetzes muss sehr schnell und zuverlässig geschehen.
Personal Area Network (PAN) und Bluetooth: Hier wird auf sehr begrenztem Raum ein Netzwerk geschaffen, das aus Knoten besteht, die eng mit einer einzigen Person verbun- den sind. Diese Geräte können beispielsweise am Gürtel der Person befestigt sein oder in der Handtasche transportiert werden. Diese Geräte müssen untereinander kommunizieren können, solange sie vom Benutzer benötigt werden. Mobilität wird ein entscheidendes Kriterium, wenn Interaktionen zwischen mehreren PANs erwünscht sind. Bluetooth bie- tet eine drahtlose Schnittstelle, über die sowohl mobile Kleingeräte wie Mobiltelefone und persönliche digitale Assistenten (PDAs) als auch Computer und Peripheriegeräte miteinander kommunizieren können. Hauptzweck von Bluetooth ist das Ersetzen von Kabelverbindungen zwischen solchen Geräten.
Eingebettete Computeranwendungen: Durch die fortschreitende Miniaturisierung von elektronischen Gegenständen sollen zukünftig verschiedenste Alltagsgegenstände mit eigener Rechenleistung ausgestattet sein, Sensoren besitzen und mit anderen Ge- genständen kommunizieren, wobei sie sich nahtlos und unsichtbar zum Ziel der Un- terstützung des Menschen in die Umwelt einfügen. Computer im Sinne dieses Ubiquitous Computing kommunizieren meist über ein mobiles Ad-hoc-Netz.
Sensor Dust: Ein Sensornetz besteht aus einer großen Anzahl von Sensorknoten – winzigen, drahtlos kommunizierenden Computern –, die in einem Ad-hoc-Netz zusammenarbei- ten, um ihre Umgebung mittels Sensoren zu überwachen. Solche Sensornetze können beispielsweise detaillierte Informationen über Terrain- oder Umweltveränderungen be- reitstellen. Eine weitere Einsatzmöglichkeit sind militärische Anwendungen.
Fahrzeugkommunikation: Ein sog. Vehicular Ad-hoc-Network (VANET) ist ein spezielles MANET, das die direkte Kommunikation zwischen Fahrzeugen ermöglicht. Dadurch können etwa Fahrzeugsicherheit und -komfort entscheidend verbessert werden. So kann z. B. die Kommunikation zwischen Fahrzeugen dazu benutzt werden, um aktive Sicher- heitsservices, wie etwa Bremswarnungen, Kollisionswarnungen, aktuelle Verkehrs- und Wetterinformationen oder aktive Navigationssysteme, zu realisieren (Rybicki, Scheuer- mann, Kiess, Lochert, Fallahi & Mauve 2007, S. 215).
3.2 Routing in mobilen Ad-hoc-Netzwerken
Wie bereits gezeigt worden ist, sind Verbindungen zwischen Knoten in MANETs von hoher Dynamik und Zufälligkeit gekennzeichnet. Die einzelnen Knoten müssen daher selbst Router- funktionen übernehmen, sich also um Routenfindung und -pflege kümmern.
Das Ziel eines Routingalgorithmus als Teil der Netzwerkschicht-Software eines Netzknotens ist es, aufgrund gewisser Metriken (z. B. Hop-Anzahl, Bandbreite, Verzögerung, Zuverlässigkeit, Energieverbrauch) zu entscheiden, über welchen Pfad Pakete an ein bestimmtes Ziel gelangen sollen.
3.2.1 Anforderungen an MANET-Routingprotokolle
Um die Leistung eines MANET-Routingprotokolls bewerten zu können, werden eine Reihe von qualitativen und quantitativen Metriken herangezogen. Diese Metriken müssen unabhängig vom verwendeten Routingprotokoll sein. Corson & Macker (1999, S. 6f) nennen folgende wünschenswerte qualitative Eigenschaften eines MANET-Routingprotokolls:
Verteilte Verfahren: Aufgrund der hohen Dynamik in MANETs sind Verfahren mit zentraler Steuerung für diese Netze ungeeignet.
Schleifenfreiheit: Dies ist generell eine wünschenswerte Eigenschaft, um Probleme wie z. B. Pakete, die eine willkürliche Zeit im Netz herumwandern, zu vermeiden.
Sicherheit: Die Sicherheit spielt in mobilen Ad-hoc-Netzwerken, allein schon aufgrund der Kommunikation per Funk eine wichtige Rolle. Die Funkkommunikation kann wesentlich einfacher abgehört, manipuliert oder umgeleitet werden als die Kommunikation in Fest- netzen. Daher sind ausreichende Sicherungsmaßnahmen erforderlich, um Störung oder Modifikation des Protokollbetriebs zu verhindern.
Schlafperioden: Da Knoten in MANETs oft beschränkte Energieressourcen haben, können Knoten, um Energie zu sparen, den Versand oder Empfang von Paketen für eine Dau- er einstellen. Ein MANET-Routingprotokoll muss solche Schlafperioden berücksichtigen können, ohne dass daraus allzu große Nachteile entstehen.
Unidirektionale Verbindungen: Mobile Knoten in MANETs verfügen über unterschiedliche Sende- und Empfangseinheiten. Daher sind asymmetrische Verbindungen möglich, d. h., der Transport von Paketen muss auf unterschiedlichen Hin- und Rückwegen abgewickelt werden können.
Außerdem gibt es eine Reihe quantitativer Metriken eines Routingprotokolls, wie Ende-zu-Ende- Datendurchsatz und -Verzögerung, Routenfindungszeit oder Effizienz (Corson & Macker 1999, S. 8).
3.2.2 Kategorien von Ad-hoc-Routingprotokollen
Bezüglich des Aspekts der Topologie eines Netzwerks unterscheidet man Routingalgorithmen nach der Art und Weise, wie Routinginformationen im Netz gesammelt und verteilt werden. Es existieren drei Kategorien: proaktive und reaktive (Royer & Toh 1999, S. 46) sowie hybride Routingalgorithmen (Perkins 2001, S. 221).
Proaktive Routingalgorithmen: Verfahren dieser Klasse werden auch tabellenbasierte Rou- tingalgorithmen genannt. Sie bestimmen bereits die zu verwendenden Pfade zwischen zwei Knoten, bevor diese für die Übertragung von Nutzdaten benötigt werden. Sollen dann Nutzdaten verschickt werden, so muss nicht auf die Bestimmung des Pfads zum Zielknoten gewartet werden. Da proaktive Routingalgorithmen kontinuierlich Routingin- formationen sammeln und im Netz an alle Knoten verteilen müssen, damit die Knoten über aktuelle Routinginformationen verfügen, haben Verfahren dieser Klasse einen ho- hen Overhead. Ein Beispiel für ein Protokoll aus dieser Klasse ist Optimized Link State Routing“(OLSR), das in Kapitel 4.1 näher erläutert wird. ”
Reaktive Routingalgorithmen: Verfahren dieser Klasse werden auch On-Demand Routing- algorithmen genannt, da im Gegensatz zu den proaktiven Verfahren reaktive Routing- verfahren die benötigten Pfade zwischen zwei Knoten erst dann bestimmen, wenn Nutz- daten übertragen werden sollen. Daraus ergibt sich, dass das erste Datenpaket einer Verbindung mit Verzögerung versendet werden kann, da zunächst auf den Abschluss der Routenbestimmung gewartet werden muss. Dafür werden allerdings auch nur Kontroll- pakete versendet, wenn Nutzdaten verschickt werden und dies zur Routenbestimmung notwendig ist. Ein Beispiel für ein Protokoll aus dieser Klasse ist Ad Hoc On-Demand Distance Vector“(AODV), auf das in Kapitel 4.2 genauer eingegan wird.
Hybride Routingalgorithmen: Hybride Verfahren kombinieren proaktive und reaktive Rou- tingverfahren. Ein Protokoll aus dieser Klasse ist nach Perkins (2001, S. 221–253) etwa das Zone Routing Protocol“ (ZRP).
3.3 Schwarmintelligenz
Unter dem Ausdruck Schwarmintelligenz versteht man nach Bonabeau, Dorigo & Theraulaz (1999, S. 7) jede Art von Algorithmen und verteilten Lösungsansätzen, die durch das kollektive Verhalten von sozialen Insektenkolonien oder anderen sozialen Tiergemeinschaften inspiriert ist. Es handelt sich dabei um ein sogenanntes emergentes Phänomen: durch Kommunikation innerhalb einer Gemeinschaft kommt es zu einem intelligenten Verhalten des Superorganismus, also aller Mitglieder. Schwärme, die in der Natur vorkommen und ein solch intelligentes Ver- halten aufweisen, sind z. B. Ameisen, Termiten, Vögel oder Bienen. Beispiele für Aufgaben, die durch derartiges rationales Gruppen-Handeln gelöst werden können, sind Nestpflege oder Fut- tersuche. Das herausragende Merkmal bei diesem Verhalten ist, dass innerhalb des Schwarms keine zentrale Steuerungsinstanz existiert. Die Tiere müssen sich ohne das Vorhandensein einer Kontrollinstanz selbst organisieren.
3.3.1 Selbstorganisation sozialer Insekten
Selbstorganisation ist eine Reihe von dynamischen Mechanismen, durch die Strukturen auf globaler Ebene eines Systems durch Interaktionen zwischen seinen Teilen auf unterer Ebene hervorgerufen werden. Die Regeln, welche die Interaktion zwischen den einzelnen Systemkom- ponenten spezifizieren, werden allein aufgrund von lokalen Informationen ausgeführt, ohne die Einbeziehung von globalen Zielen (Bonabeau et al. 1999, S. 6).
Beispielsweise beinhalten die emergenten Strukturen bei der Futtersuche von Ameisen zeitlich- räumlich organisierte Netzwerke aus Pheromonspuren (die bekannten, auf biochemischen Bo- tenstoffen basierenden Ameisenstraßen). Die Selbstorganisation ist im Fall der Futtersuche einer Ameisenkolonie durch vier grundlegende Funktionen bestimmt (Bonabeau et al. 1999, S. 9–12):
Positive Rückkoppelung: Die positive Rückkoppelung beeinflusst die Selbstorganisation grundlegend. Einfache Verhaltensregeln fördern die Erschaffung von neuen Strukturen. Beispiele für positive Verstärkung sind das Rekrutieren von Ameisen im Nest oder die Verstärkung von Pheromonspuren.
Negative Rückkoppelung: Negative Rückkoppelung ist das Gegengewicht zur positiven Rückkoppelung und hilft, das gesamte System zu stabilisieren. Negative Verstärkung im Falle der Ameisen-Futtersuche kann von der limitierten Anzahl der futtersuchenden Ameisen, Verknappung der Nahrungsquellen oder dem Wettbewerb um verschiedene Nahrungsquellen herrühren.
Verhaltensfluktuationen: Durch Fluktuationen (wie beispielsweise zufällige Wege, Fehler, zufällige Aufgabenwechsel) werden nicht nur zufällig neue Strukturen gebildet, sondern es wird auch die Entdeckung von neuen Problemlösungen ermöglicht. Beispiel hierfür ist das Sich-Verirren von Ameisen, das gleichzeitig auch das Entdecken neuer, bisher unbekannter Wege möglich macht.
Interaktion zwischen Individuen: Auch ein einzelnes Individuum kann eine selbstorganisier- te Struktur, wie beispielsweise einen stabilen Pfad, erzeugen. Dies ist unter der Voraus- setzung, dass das Pheromon eine ausreichende Lebensdauer hat, möglich, da dadurch das Folgen des Pfades mit dem Pfadlegen interagiert. Eine effiziente Wegsuche wird aber erst durch das Zusammenarbeiten mehrerer Individuen erreicht.
3.3.2 Schwarmkommunikation
Selbstorganisation in einem Schwarm erfordert meistens Interaktion zwischen den Individuen. Man unterscheidet im Allgemeinen zwei Arten der Kommunikation (Bonabeau et al. 1999, S. 14):
Direkte Kommunikation : Die Individuen befinden sich in direkter Reichweite. Beispiele für direkte Interaktion sind Berührung, Austausch von Nahrung oder Flüssigkeit, Sichtkon- takt.
Indirekte Kommunikation : Zwei Individuen interagieren durch Modifikation der Umgebung miteinander (Stigmergie). Man unterscheidet weiter in sematektonische Stigmergie und zeichenbasierte Stigmergie. Bei der sematektonischen Stigmergie beeinflusst der augen- blickliche Zustand der Aufgabenerfüllung (z. B. der Stand des Nestbaus) das Verhalten der Individuen. Bei der zeichenbasierten Stigmergie wird hingegen über aufgabenun- abhängige Zeichen (z. B. Pheromone), die in der Umwelt platziert wurden, kommuni- ziert.
3.3.3 Ameisenalgorithmen
Ameisen-basierte Algorithmen oder Ant Colony Optimization“-Algorithmen (ACO), als Teil- ” bereich der Schwarmintelligenz, gehören zu den Metaheuristiken für Verfahren der kombi- natorischen Optimierung, die auf dem modellhaften Verhalten von realen Ameisen bei der Futtersuche basieren. Diese ACO-Algorithmen wurden zuerst auf das Problem des Handelsrei- senden (Traveling Salesman Problem, TSP), später auf andere Optimierungsprobleme wie das Quadratic Assignment Problem“ (QAP) angewandt (Bonabeau et al. 1999, S. 25).
Natürliche Ameisen
Wie in Abschnitt 3.3.1 ausgeführt, findet die Futtersuche von natürlichen Ameisen mit Hilfe von Pheromon-markierten Ameisenstraßen statt. Ameisen, die einen Weg von ihrem Nest zu einer Futterquelle suchen, sondern laufend Pheromon auf den Boden ab. Nachfolgende Amei- sen wählen bei Wegentscheidungen mit einer höheren Wahrscheinlichkeit den Weg, auf dem bereits mehr Pheromon hinterlassen wurde. Ameisen können nun einen kürzesten Weg zwi- schen Nest und Quelle finden, weil die kürzeren Wege schneller durchlaufen werden können und so schneller eine Pheromonmarkierung erhalten als die längeren. Da mehr Ameisen über einen stärker markierten Weg laufen, wählen auch ihre Nachfolger mit höherer Wahrscheinlichkeit den stärker frequentierten und markierten Weg. Dadurch verstärkt sich die Anziehungskraft des kürzeren Weges immer weiter, bis näherungsweise eine direkte Verbindung zwischen Nest und Futterquelle entstanden ist (Bonabeau et al. 1999, S. 28f).
Algorithmen mit künstlichen Ameisen
Die Fähigkeit der Ameisen, einen kürzesten Weg zu konstruieren, wurde erstmals als Ant System (AS) auf das TSP übertragen (Bonabeau et al. 1999, S. 41–46). Beim TSP geht es darum, die kürzeste Route durch eine Anzahl von n Städten zu finden, ohne dabei eine Stadt mehrfach zu besuchen.
Im Unterschied zu ihren natürlichen Vorbildern haben künstliche Ameisen erweiterte Fähigkeiten. Sie verfügen über ein Gedächtnis (die sog. Tabu-Liste), da sie sich merken müssen, welche Stadt sie bereits besucht haben. Außerdem sind sie nicht nahezu blind, sondern können die Entfernung zu den einzelnen Städten erkennen und sich an diesem heuristischen Kriterium (die sog. Sichtbarkeit) orientieren.
In AS wird jede Ameise k initial in einer zufällig gewählten Stadt platziert. Es wird empfohlen, die Gesamtanzahl der Ameisen m = n zu setzen. Ausgehend vom Start wandern die Ameisen von Stadt zu Stadt, bis die Tour beendet ist. Während jeder Iteration des AS-Algorithmus konstruiert jede Ameise k , k = 1, . . . , m eine Tour mit n Schritten, in der eine Übergangsregel angewendet wird. Die Iterationen werden durch t , 1 ≤ t ≤ t max indiziert, wobei t max die maximale, vom Benutzer anzugebende Anzahl an Iterationen ist.
Die Übergangsregel, also die Wahrscheinlichkeit für eine Ameise k von Stadt i zu einer noch nicht besuchten Stadt j zu wandern, während sie ihre t -te Tour konstruiert, lautet
Abbildung in dieser Leseprobe nicht enthalten
wobei t die aktuelle Runde ist, [Abbildung in dieser Leseprobe nicht enthalten] die Sichtbarkeit1 ist und [Abbildung in dieser Leseprobe nicht enthalten] die Pheromonspur2 ist,
α und β zwei Parameter sind, die das relative Gewicht der Pheromonspur und der Sichtbarkeit bestimmen und [Abbildung in dieser Leseprobe nicht enthalten] die Liste der noch zu besuchenden Städte der k -ten Ameise ist. Wenn α = 0, sind die Auswahlwahrscheinlichkeiten proportional zu [Abbildung in dieser Leseprobe nicht enthalten] und die nächste Stadt wird mit höherer Wahrscheinlichkeit gewählt. Wenn β = 0, wird nur die Pheromonverstärkung als Parameter herangezogen, was zu rascher Stagnation (alle Ameisen wählen denselben Pfad und konstruieren dieselbe Lösung) führt und insofern nicht optimal ist. Daher ist ein Kompromiss zwischen Tourlänge und Pheromonintensität wichtig.
Die Lösungskonstruktion endet, nachdem jede Ameise eine Tour beendet hat, also nachdem jede Ameise eine Sequenz der Länge n konstruiert hat. Als nächstes werden die Pheromonspu- ren aktualisiert. In AS wird dies realisiert, indem zuerst die Pheromonspur um einen konstanten Faktor (die Pheromonverdunstung) reduziert wird und dann alle Ameisen Pheromon auf den Kanten, die zu ihrer Tour gehören, platzieren:
Abbildung in dieser Leseprobe nicht enthalten
wobei ρ , 0 < ρ ≤ 1 der Pheromon-Verdunstungsfaktor ist, m die Anzahl der Ameisen und [Abbildung in dieser Leseprobe nicht enthalten] die Intensität der Spur zwischen der Stadt i und j zum Zeitpunkt t ist. Der Parameter ρ wird verwendet, um ein unbeschränktes Ablagern der Pheromonspuren zu verhindern und dem Al- die gorithmus das Vergessen“ von vorhergegangenen schlechten Entscheidungen zu ermöglichen. Auf Kanten, ” nicht von Ameisen gewählt werden, verflüchtigt sich die Pheromonkonzen- tration exponentiell mit der Anzahl der Iterationen. [Abbildung in dieser Leseprobe nicht enthalten] ist die Pheromonmenge, die eine Ameise k auf den Kanten platziert, sie ergibt sich aus der Formel:
Abbildung in dieser Leseprobe nicht enthalten
wobei [Abbildung in dieser Leseprobe nicht enthalten] ( t ) die Tour der k -ten Ameise bei Iteration t ist, [Abbildung in dieser Leseprobe nicht enthalten] ( t ) ihre Länge und Q eine Konstante ist3. Gleichung (3) zeigt, dass umso mehr Pheromon auf Kanten, die zur Tour gehören, abgelagert wird, je kürzer die Tour einer Ameise ist. Dadurch werden diese Kanten in zukünftigen Iterationen des Algorithmus mit höherer Wahrscheinlichkeit ausgewählt.
Auf einer hohen Abstraktionsebene kann AS wie in Algorithmus 1 ausgeführt, beschrieben werden. Die Komplexität von AS is [Abbildung in dieser Leseprobe nicht enthalten], wobei t die Anzahl der durchgeführten Iterationen ist. Wenn m = n , also die Anzahl der Ameisen gleich der Anzahl der Städte ist, ist die Komplexität [Abbildung in dieser Leseprobe nicht enthalten] (vgl. Bonabeau et al. 1999, S. 44).
Da AS im Vergleich mit spezialisierten Algorithmen nur für TSP-Probleme mit kleinem n gute Ergebnisse liefert, wurde das Verfahren mehreren Verbesserungen, wie Ant Colony System (ACS) oder Max-Min AS, unterzogen. Es konnte gezeigt werden, dass diese verbesserten ACO-Algorithmen beispielsweise gegenüber Genetischen Algorithmen oder Neuronalen Netzen konkurrenzfähig sind bzw. teilweise sogar bessere Ergebnisse erzielen (Bonabeau et al. 1999, S. 46–55).
[...]
1 Der Wert, der die Sichtbarkeit repräsentiert, ist statisch, basiert ausschließlich auf lokalen Informationen und stellt die heuristische Attraktivit ¨ at der Auswahl einer Stadt j dar.
2 Der Wert, der die Pheromonspur repräsentiert, ist dynamisch und stellt die gel ernte Attraktivit ¨ at der Auswahl einer Stadt j dar.
3 Obwohl Q das endgültige Ergebnis nur marginal beeinflusst, sollte es mit einem Wert, welcher der optimalen Tourlänge entspricht, angenommen werden. Dieser Wert kann unter anderem durch eine einfache ” Nachbar-Heuristik“ gefunden werden.