A generalized broadcasting technique for mobile ad hoc networks

Abstract

Broadcasting is a major communication primitive required by many applications and protocols in Mobile Ad Hoc Networks (MANETs). It is frequently deployed for content distribution, service discovery or advertisement, and sensor data dissemination. Broadcast protocols are also a fundamental building block to realize principal middleware functionalities such as replication, group management and consensus. Broadcasting in MANETs has therefore been an active area of research recently. Most of the research conducted on broadcasting in MANETs has primarily focused only on carefully selected application and evaluation scenarios. Consequently, the developed broadcasting schemes do not yield good performance for other scenarios. Different comparative studies show that the existing broadcasting techniques are tailored to only one class of MANETs with respect to node density and node mobility, and are unfortunately not likely to operate well in other classes. Node spatial distribution is a key issue for the performance of broadcast protocols, since it determines the connectivity of the MANET. Our survey of potential MANET application scenarios shows a wide range of possible node spatial distributions and node mobilities. This leads to that a MANET generally shows a continuously changing network connectivity over space and time. Therefore, a generalized solution for broadcasting that accounts for the requirements of the various applications and adapts to the heterogeneous and evolving node spatial distribution and mobility is a major contribution. In this thesis, we present hypergossiping, a novel generalized broadcasting technique for MANETs. Hypergossiping integrates two adaptive schemes and efficiently switches between them depending on local node density. The first scheme is adaptive gossiping, which distributes messages within connected parts of the MANET. We adapted gossiping as follows. First, we established an analytical model for gossiping through adopting the SI mathematical model from the epidemiology. Then, we used the model to adapt the gossiping forwarding probability to local node density. As a result, we provide a simple analytical expression that nodes use to set the appropriate forwarding probability depending on the current number of neighbors. Simulation results showed that adaptive gossiping efficiently propagates messages within a network partition independent of the node spatial distribution and node mobility in that network partition. The second scheme is a broadcast repetition method, which detects partition joins using an efficient and localized heuristic and efficiently repeats the needed broadcasts upon detection of a partition join. Our approach is mobility-assisted since it exploits the mobility of nodes to efficiently deliver messages in frequently partitioned scenarios. We defined mobility metrics that simplify the design of mobility-assisted concepts, and used some of them to design a mobility-aware buffering strategy, which can significantly reduce the buffer overhead of hypergossiping. Simulation results in the standard network simulator ns-2 show that hypergossiping outperforms all existing strategies. Hypergossiping significantly increases the delivery ratio for a broad range of MANETs with respect to node density, node mobility and network load while providing high efficiency and scalability.

Broadcast ist eine wichtige Kommunikationsprimitive, die für die Realisierung zahlreicher Anwendungen und Protokolle in Mobilen Ad-Hoc-Netzen (MANETs) essentiell ist. Broadcast ist ein grundsätzlicher Baustein, um Middleware-Funktionalitäten wie Replikation, Gruppenkommunikation und Konsensus zu realisieren. Außerdem wird Broadcast dazu verwendet, Ressourcen zu finden und bereitzustellen, und Informationen wie beispielsweise Warnungen oder Meldungen auf alle Netzwerk-Knoten zu verteilen. Broadcast ist folglich ein sehr aktiver Forschungsbereich in MANETs in den letzten Jahren geworden. Die meisten, existierenden MANET-Broadcast-Methoden sind hauptsächlich für sorgfältig ausgewählte Anwendungsszenarien entwickelt worden. Infolgedessen sind diese Methoden nur für spezifische Szenarien optimiert. Unterschiedliche, vergleichende Studien haben gezeigt, daß die existierenden Verfahren sich nur für eine Klasse von MANET-Szenarien bezüglich der Kontendichte und Knotenmobilität eignen. Vorherige Arbeiten haben gezeigt, daß die räumliche Knotenverteilung einen klaren Einfluß auf die Performanz von MANET-Broadcast-Protokollen hat. Aufgrund möglicher Knotenmobilität weisen MANETs eine sehr stark variierende, räumliche Knotenverteilung und folglich eine ständig variierende Konnektivität über Zeit und Raum auf. Die Vielfalt der möglichen Anwendungsszenarien für MANETs erhöhen diese Dynamik und weiten außerdem die Bandbreite der möglichen Netzwerkgrößen und folglich die Raumverteilung der Knoten aus. Deshalb ist eine verallgemeinerte, adaptive Broadcast-Methode erforderlich, die mit den ständig variierenden MANET-Eigenschaften und Anwendungsanforderungen ohne explizite Vorkonfiguration funktioniert. In dieser Arbeit präsentieren wir Hypergossiping, eine neue, verallgemeinerte Broadcast-Methode für MANETs. Hypergossiping integriert zwei adaptive Methoden und wechselt zwischen ihnen in Abhängigkeit von der Knotendichte. Die erste Methode ist adaptives Gossiping, welches Nachrichten innerhalb einer Netzwerkpartition effizient verteilt. Wir adaptieren Gossiping an die lokale Knotendichte wie folgt: Zuerst entwickeln wir ein analytisches Modell für Gossiping durch das Anpassen des mathematischen SI-Modells aus der Epidemiologie. Dann benutzten wir das Modell, um die optimale Gossiping-Weiterleitungswahrscheinlichkeit in Abhängigkeit von der lokalen Knotendichte zu bestimmen. Infolgedessen stellen wir einen einfachen analytischen Ausdruck zur Verfügung, welchen die Knoten verwenden, um die passende Weiterleitungswahrscheinlichkeit in Abhängigkeit von der aktuellen Anzahl der Nachbarn zu wählen. Die Simulationsergebnisse zeigen, daß das adaptive Gossiping Nachrichten innerhalb einer Netzwerkpartition unabhängig von der Knotendichte und Knotenmobilität zuverlässig und effizient verteilt. Die zweite Methode ist die effiziente Broadcast-Wiederholung bei Partitionsfusionierungen. Unser Ansatz besteht aus einer effizienten Heuristik zur Erkennung der Partitionsfusionierungen und aus einem Protokoll zur Wiederholung des Gossipings von benötigten Nachrichten. Hierfür speichern die Knoten die Broadcast-Nachrichten in einem lokalen Puffer zwischen. Für die Broadcast-Wiederholung spielt die Mobilität auf einer großen Zeitskala eine Schlüsselrolle, deshalb definieren wir neue Mobilitätsmetriken, die wir verwenden, um eine effiziente mobilitätsbewußte Pufferung für Hypergossiping zu entwerfen. Simulationen in ns-2 haben gezeigt, daß Hypergossiping alle vorhandenen Broadcast-Methoden an Performanz übertrifft. Hypergossiping vergrößert die Zustellungsrate auf effiziente und skalierbare Weise und für eine breite Reihe von MANETs in Bezug auf die Knotendichte, Knotenmobilität und Netzlast.