Bloom-Filter zum Abgleich von großen Kollektionen in DTNs

Motivation

Im LocCom Projektes im Rahmem der NTH School for IT Ecosystems kommen Verfahren aus dem Bereich des Delay Tolerant Networking zum Einsatz. Hierbei sollen die SmartPhones von Benutzern des Systems dazu verwendet werden, die Verteilung von Daten im Netzwerk zu unterstützen. Hierzu überträgt ein SmartPhone für den Benutzer transparent Daten auf Basisstationen, in Funkreich- weite und empfängt ebenfalls neue Daten von Basistationen. Hierbei ergibt sich das Problem, dass man zwischen SmartPhone und Basistation nur Daten übertragen möchte, die der jeweilige Kom- munikationspartner nicht bereits besitzt. Dieser Abgleich von Datenbeständen ist bei sehr großen Kollektion von mehreren zehntausend Dateien auf Grund des Kommunikationsoverheads nicht mehr efifzient durch einen einfachen Listenvergleich möglich.

Aufgabe

In dieser Bachelorarbeit soll ein Verfahren entwickelt und implementiert werden, dass es erlaubt große Kollektionen zwischen 2 DTN Knoten abzugleichen, d.h. es sollen Elemente gefunden werden, die sich nur jeweils auf einem, nicht aber auf dem anderen Knoten befinden.

Zunächst sollen hierzu die Grundlagen von Bloom-Filtern erarbeitet und bestehende Varianten gesichtet werden. Auf Basis der gewonnenen Erkenntnisse soll ein geeigneter Ansatz für die Ar- beit vorgeschlagen werden. Hierzu zählt auch die Auswahl geeigneter Hashverfahren im Hinblick auf Qualität und Geschwindigkeit. Es ist zu betrachten, dass die Kollektionen auf den Geräten durch den Austausch von Daten nicht nur anwachsen, sondern durch das Entfernen von Daten auch wieder schrumpfen können. Die Implementierung erfolgt in Java und soll auf der Android Smartpho- ne Plattform lauffähig sein. Zur Evaluation soll die Geschwindigkeit (Durchsatz) der verwendeten Hashverfahren auf einem Android Telefon gemessen werden. Um die Einsetzbarkeit der Implemtie- rung zu evaluieren sollen relevante Testszenarios entworfen werfen. Hierbei soll ermittelt werden, inwieweit die gemessene False Positive Rate des Bloom-Filters mit der theoretisch erwarteten Rate übereinstimmt. Die hierzu benötigten Kollektionen sollen aus einem statischen Export der Wikipedia extrahiert werden.

Anforderungen

• Erfahrungen mit Android sind hilfreich, aber nicht Vorraussetzung
• Solide Java-Kenntnisse sind nötig