Direkt zum Inhalt

Informatik: Fliegen als Vorbild für Computeralgorithmus

TaufliegeLaden...
Forscher ließen sich vom Nervensystem einer Taufliege inspirieren, um vernetzte Computersysteme besser zu organisieren. Der neue Algorithmus sei nicht nur effizienter als vorherige Ansätze, sondern auch einfacher und stabiler. Mit seiner Hilfe könnten drahtlose Sensorennetzwerke und andere verteilte Rechnernetze womöglich besser funktionieren.

Besonders interessierte das Team um Ziv Bar-Joseph von der Carnegie Mellon University in Pittsburgh die Anordnung der winzigen Borsten auf den Insekten, mit denen diese ihre Umwelt wahrnehmen. Jede Borste entspringt einem besonderen Typ von Nervenzelle, so genannten Vorläuferzellen der Sinnesorgane, die zwar benachbarte Nervenzellen verbindet, nicht aber mit anderen Vorläuferzellen in Kontakt steht. Dieser distributive Ansatz ist ähnlich in heutigen Computersystemen zu finden: Tausende oder sogar Millionen von Prozessoren arbeiten zusammen, um eine Aufgabe auszuführen. Dabei muss keine Komponente wissen, was im gesamten System passiert – also alle In- und Outputs kennen. Zudem sollte das System auch funktionieren, wenn einzelne Elemente ausfallen.

Taufliege in VergrößerungLaden...
Taufliege in Vergrößerung | Am Deckschild einer erwachsenen Taufliege wachsen kleine (hier umrandet) und größere Borsten in einem typischen Muster.
Um diese beiden Ziele zu erreichen, sucht man nach einer kleinen Gruppe von Prozessoren, die möglichst schnell mit den restlichen Prozessoren im Netzwerk kommunizieren kann, aber untereinander nicht verbunden ist. Mathematiker sprechen dabei von einer maximal unabhängigen Menge (MIS). Um diese Gruppe zu finden, verwenden Wissenschaftler meist wahrscheinlichkeitstheoretische Methoden: Einige ausgewählte Prozessoren geben sich als Hauptknoten – also als ein Mitglied der MIS – aus, und es wird geprüft, mit wie vielen anderen Prozessoren sie verknüpft sind. Nach vielen Durchgängen, in denen immer wieder neue Hauptknoten ernannt und solche mit wenigen Kontakten aberkannt werden, findet sich schließlich die gesuchte Menge.

Dieser Prozess läuft zwar sehr schnell ab, so Bar-Joseph, doch müssen viele komplizierte Botschaften hin und her über das Netzwerk gesendet werden. Außerdem müssen alle Prozessoren im Voraus wissen, wie sie im Netzwerk verbunden sind. Und das sei beispielsweise ein Problem für drahtlose Netzwerke, wo Sensoren zufällig verteilt und möglicherweise nicht alle in Funkreichweite voneinander entfernt sind.

Genau mit diesem Problem sind auch die Nervenzellen der Fliege während des Larven- und Puppenstadiums konfrontiert – denn sie wissen nicht, wie sie untereinander verknüpft sind. Ebenfalls zufällig werden einige der Zellen zu Vorläuferzellen der Sinnesorgane beziehungsweise Hauptknoten auserkoren und senden daraufhin chemische Signale an benachbarte Zellen, so dass diese nicht zu Vorläuferzellen werden. Drei Stunden dauert es, bis mit diesem Verfahren alle Zellen zugeordnet sind – und das mit einem Minimum an Kommunikation, berichten die Forscher. Anders als im Computersystem steige die Wahrscheinlichkeit, mit der eine Zelle zu einem Hauptknoten wird, hier nicht mit der Anzahl ihrer Verbindungen, sondern mit der Zeit.

Nach diesem Vorbild erstellten die Wissenschaftler nun einen Computeralgorithmus. "Die Laufzeit ist etwas länger als bei derzeitigen Ansätzen, aber unser Algorithmus ist effizienter und vor allem stabiler", fasst Bar-Joseph zusammen. Besonders gut geeignet sei der neue Ansatz für Netzwerke, in denen die Anzahl und Position der Knoten nicht genau bekannt ist. Dazu zählen etwa drahtlose Sensornetzwerke, wie sie zur Umweltbeobachtung in Seen oder Flüssen zum Einsatz kommen, oder Systeme zur Kontrolle von Roboterschwärmen. (mp)
2. KW 2011

Dieser Artikel ist enthalten in Spektrum - Die Woche, 2. KW 2011

Lesermeinung

Beitrag schreiben

Wir freuen uns über Ihre Beiträge zu unseren Artikeln und wünschen Ihnen viel Spaß beim Gedankenaustausch auf unseren Seiten! Bitte beachten Sie dabei unsere Kommentarrichtlinien.

Tragen Sie bitte nur Relevantes zum Thema des jeweiligen Artikels vor, und wahren Sie einen respektvollen Umgangston. Die Redaktion behält sich vor, Leserzuschriften nicht zu veröffentlichen und Ihre Kommentare redaktionell zu bearbeiten. Die Leserzuschriften können daher leider nicht immer sofort veröffentlicht werden. Bitte geben Sie einen Namen an und Ihren Zuschriften stets eine aussagekräftige Überschrift, damit bei Onlinediskussionen andere Teilnehmer sich leichter auf Ihre Beiträge beziehen können. Ausgewählte Lesermeinungen können ohne separate Rücksprache auch in unseren gedruckten und digitalen Magazinen veröffentlicht werden. Vielen Dank!

  • Quellen

Partnervideos