Enabling disruption tolerant services

Disruption tolerant networking allows us to provide communication and information services in low connectivity and challenged network scenarios. These range from previously underserved rural areas to highly energy constrained special purpose sensor networks. Compared to wired-to-the-last-hop, infrastructure-based networks, infrastructure-less networks face a number of additional challenges, the fundamental one being varying connectivity over time. Building successful services for disruption tolerant networking requires three different key steps: (1) identification and characterization of possible applications and services, (2) optimization of neighbor discovery, and (3) efficient routing of data bundles.

We developed an initial model for users and services in the context of disruption tolerant networks that combines the service communication structure, with user experience and user expectations to predict a user's Quality of Experience. For this, we identify key characteristics of services and networks that make them suitable for challenged scenarios. These characteristics include: (1) Data Prefetching and Bundling, (2) Bursty Communication Style, (3) Soft Time Constraints, (4) Lenient Delivery Order Constraints, (5) One-Way Communication, and (6) Hop-to-Hop Usability. We propose initial quantitative metrics that may capture the user perceived quality. These metrics are: (1) Speed of Interaction, (2) Comfort and Frustration Level, (3) Delivery Effectiveness, and (4) Intercontact Times / Idle Period.

Overall, we argue that there is no particular killer app for DTNs, but rather, we show how considering these challenges to network communication in the design of an application can lead to a universally better experience for all users. In this context, we develop a set of sample applications particularly well-suited for challenging network environments, which are a collaborative event scheduling and a Wikipedia access application. We further explored map dissemination for indoor navigation and mobile sensor networks for wildlife monitoring.

We propose a new scheme for wireless neighbor discovery between unsynchronized nodes based on perfect difference sets. The construction is a mathematically provable optimal trade-off between the discovery delay and power consumption for discovering the presence of a potential communication partner in range. The application of Perfect Difference Sets (PDS) allows the provable optimal trade-off. Using PDS with a duty cycle of 2 % only has a discovery latency of about 4 min whereas U-Connect, the best related work, has a latency of 9 min, assuming a slot length of 100 ms. We further investigate discovery between devices with differing energy budgets. Through an exhaustive search of all possible combinations of schedule lengths and phase shifts, we show that PDS also performs fair in practice, that is with a duty cycle of greater or equal to 1%.

To enable efficient routing of messages, we model human mobility in a novel way using only local information. We propose two routing protocols: SimBetAge which bases on the frequency that particular people met in the past, and GeoDTN, which works on the frequency at which certain locations were visited in the past. Instead of modeling the social interactions in a binary graph, in SimBetAge, we capture the temporal change of a social network in a weighted graph. Edges in the graph degrade over time, if not refreshed. In turn, we extend the definition of similarity and betweenness to capture real-valued edge weights and further propose the directed ego flow betweenness as a novel metric to capture the usefulness of a node as a carrier for data bundles. We evaluated this approach against a number of existing routing schemes, in particular: Direct Delivery, Epidemic Routing, Prophet and the original SimBet. Using the MIT Reality Mining trace, the Haggle imote trace, and the Dartmouth Outdoor Experiment traces, we show that routing performance can be drastically improved when temporal changes are considered.

In GeoDTN, we modeled human mobility as a time dependent probability distribution around known anchor points. Based on this model, we developed a heuristic to predict future connectivity. To be able to evaluate this approach in the absence of widely deployed disruption tolerant consumer applications, we presented traces of self reported global mobility from an online social network website for 221 active users. The evaluation shows that geoDTN works similarly well as algorithms based on social group characteristics such as SimBetAge and outperforms binary movement algorithms as Move. In less periodic networks, geoDTN significantly outperformed the other algorithms in hop count and delivery time. It performs in general 130%, in individual cases even 200%, better in hop count. In terms of delivery time, it outperforms the related work on average by a factor of 3, PRoPHET by factor 6.

In combinations, these algorithms and methods can contribute to an overall disruption tolerant networking architecture, enabling improved services for all users, but in particular extending data network availability further into areas previously devoid of the otherwise necessary communication infrastructure.
 
Unterbrechungstolerante Kommunikation (Delay Tolerant Networking, DTN) erlaubt die Datenübertragung in Netzwerken mit geringer Konnektivität. Hierzu gehören beispielsweise bisher diesbezüglich unterversorgte ländliche Gebiete als auch sehr energiebeschränkte Sensornetze. Im Gegensatz zu vollständig verkabelten, infrastruktur-basierten Netzwerken bringen solche infrastrukturlosen Sensornetze eine Reihe von zusätzlichen Problemen mit sich, wobei die sich über die Zeit ändernde Konnektivität die größte Herausforderung darstellt. Für die Entwicklung von unterbrechungstoleranten Netzen und diese Netze nutzende Dienste bedarf es also dreier grundlegender Schritte: (1) die Identifikation sinnvoller Anwendungen und Dienste sowie deren Beschreibung, (2) die effiziente Erkennung von potentiellen Kommunikationspartnern in Funkreichweite und (3) die effiziente Vermittlung von Nachrichten.

Im Rahmen dieser Arbeit wurde ein initiales Nutzer- und Dienstmodell zur Verwendung in unterbrechungstoleranten Netzen entwickelt. Dieses Modell kombiniert Aspekte der Kommunikationsstruktur eines Dienstes mit dem Nutzerkontext, der aus bisherigen Erfahrungen und Erwartungen des Nutzers an einen Dienst aus besteht. Basierend darauf kann letztlich dessen Zufriedenheit, die "Quality of Experience", vorausgesagt werden. Hierfür wurden die Kerncharakteristika identifiziert, welche Dienste und Netzen für diese Art von Kommunikation besonders geeignet machen. Die sind (1) "Data Prefetching" und "Bundling", (2) stoßweise, diskontinuierliche Kommunikation, (3) weiche Zeitschranken, (4) weiche Schranken zur Auslieferungsreihenfolge, (5) Einwegkommunikation und (6) Nützlichkeit von Daten auf jedem Hop. Ergänzend schlagen wir folgende initialen quantitativen Metriken zur Bewertung der Nutzerzufriedenheit vor: (1) die Interaktionsgeschwindigkeit, (2) Komfort- und Frustrationslevel, (3) die Effektivität einer eingegangenen Nachricht im Auslösen von Nutzerreaktionen, sowie (4) die Dauer zwischen technischen Kommunikationsgelegenheiten.

Insgesamt gibt es keine spezielle Killeranwendung für DTNs. Eine bessere Berücksichtigung der begrenzten Netzwerkressourcen kann aber universell zu einer besseren Nutzererfahrung führen. In diesem Kontext wurden eine Reihe von Beispielanwendungen entwickelt, die besonders für DTNs geeignet sind. Hierzu gehören eine kollaborative Terminfindung, der Zugriff auf Wikipedia, die Verteilung von Kartenmaterial zur Gebäudenavigation sowie mobile Sensornetze zur Tierbeobachtung.

Weiterhin wurde ein neues Schema (PDS) zur drahtlosen Erkennung zeitlich nicht synchronisierter Netzknoten in Funkreichweite vorgeschlagen, das auf Differenzenmengen basiert. Mathematisch beweisbar erzeugt diese Konstruktion den optimalen Kompromiss zwischen Erkennungslatenz und Energieverbrauch. PDS erreicht bei einer angenommen Funkbakenrate von 10 Hz und einem Tastgrad von 2% eine maximale Latenz von 4 min, während U-Connect, die bisher beste verwandte Lösung, unter gleichen Bedingungen auf eine maximale Latenz von 9 min kommt. Weiterhin wurde die Erkennungsrate von Netzknoten mit unterschiedlichen Energiebudgets untersucht. Durch eine vollständige Suche aller Kombinationen von Zykluslängen und Phasenverschiebungen konnte gezeigt werden, dass PDS sich in der Praxis bei allen Tastgraden größer 1% fair verhält.

Zur effizienten Weiterleitung von Nachrichten wurden menschliche Bewegungsmuster auf eine neue Art modelliert, welche nur lokale Daten in einem Netzknoten benötigt. Hierbei werden zwei neue Routingprotokolle vorgeschlagen: SimBetAge basiert auf der bisherigen Häufigkeit des Treffens von Personenpaaren während GeoDTN auf den bisherigen geographischen Aufenthaltswahrscheinlichkeiten von Personen basiert. So wird in SimBetAge eine soziale Beziehung nicht als binärer, sondern als gewichteter Graph modelliert, was es erlaubt, zeitliche Veränderungen zu erfassen. Entsprechend werden die Definitionen von Ähnlichkeit und Intermediationszentralität auf reellwertig-gewichtete Graphen erweitert. Außerdem wird eine Metrik der gerichteten Egozentralität vorgeschlagen, welche die Eignung eines Netzknotens zur Weiterleitung von Nachrichten abbildet. Der Ansatz wurde mit einer Reihe von Routingsalgorithmen verglichen, insbesondere mit "Direct Delivery", epidemisches Fluten, PRoPHET und dem originalen SimBet. Unter Verwendung der Datensätze "Reality Mining", "Haggle iMote" und "Dartmouth Outdoor Experiment" wurde gezeigt, dass die Berücksichtigung der zeitlichen Veränderlichkeit von sozialen Beziehungen die Performanz drastisch verbessern kann.

In GeoDTN wird menschliche Mobilität als eine zeitabhängige Aufenthaltswahrscheinlichkeit um Ankerpunkte modelliert. Dies erlaubt die Entwicklung einer Heuristik zur Vorhersage der zukünftigen Konnektivität. Da bisher noch keine weitverbreiteten DTN Anwendungen existieren, wurde als Datenbasis zur Bewertung des Ansatzes die selbstdeklarierte Mobilität von 221 sehr aktiven Nutzern aus einem sozialen Online-Netzwerk verwendet. Die Evaluation zeigt, dass geoDTN eine ähnliche Performanz aufweist wie Algorithmen auf der Basis sozialer Charakteristika, wie etwa SimBetAge, und Algorithmen wie Move deutlich übertrifft. In Netzwerken mit weniger periodischer Mobilität übertrifft geoDTN andere Algorithmen in seiner Performanz deutlich in Bezug auf Hop-Anzahl; im Durchschnitt um 130% und in Einzelfällen um bis zu 200%. Bezüglich der Zustellungsgeschwindigkeit ist geoDTN im Schnitt um einen Faktor 3, gegenüber PRoPHET sogar um den Faktor 6, performanter.

In Kombination tragen diese Algorithmen und Methoden zu einer übergeordneten DTN Architektur dabei, erlauben verbesserte Dienste für Nutzer und verbessern den Zugang zu Datennetzen insbesondere in Gebiete, in denen die sonst nötige Kommunikationsinfrastruktur fehlt.