Dokument: Efficient Connection Establishment, Message Handling and Content Delivery in Opportunistic Networks

Titel:	Efficient Connection Establishment, Message Handling and Content Delivery in Opportunistic Networks
Weiterer Titel:	Efficient Connection Establishment, Message Handling and Content Delivery in Opportunistic Networks
URL für Lesezeichen:	https://docserv.uni-duesseldorf.de/servlets/DocumentServlet?id=42917
URN (NBN):	urn:nbn:de:hbz:061-20170725-083433-7
Kollektion:	Dissertationen
Sprache:	Englisch
Dokumententyp:	Wissenschaftliche Abschlussarbeiten » Dissertation
Medientyp:	Text
Autor:	M.Sc. Sati, Salem Omar [Autor]
Dateien:	[Dateien anzeigen] Adobe PDF [Details] 541,6 KB in einer Datei [ZIP-Datei erzeugen] Dateien vom 20.07.2017 / geändert 20.07.2017
Beitragende:	Jun.-Prof. Dr. Graffi, Kalman [Betreuer/Doktorvater] Prof. Dr. Mauve, Martin [Betreuer/Doktorvater]
Stichwörter:	Dissertation, Opportunistic Networks, Scheduling, Active Queue Management, Routing, Delay-Tolerant Networks
Dewey Dezimal-Klassifikation:	000 Informatik, Informationswissenschaft, allgemeine Werke » 004 Datenverarbeitung; Informatik
Beschreibungen:	Opportunistische Netzwerke haben in den vergangenen Jahren einige Aufmerksamkeit der Forschungsgemeinschaft auf sich gezogen. Opportunistische Netzwerke zeichnen sich durch Knoten mit typischerweise drahtlosen Kommunikationsfähigkeiten aus, die sich typischerweise bewegen und entweder keine, ein oder mehrere Kommunikationspartner zur gleichen Zeit haben. Das Netzwerk gilt oft als so spärlich belegt, dass die meisten Pfade zwischen beliebigen Knotenpaaren zu einem gegebenen Zeitpunkt nicht existieren. Oft bewegen sich die Knoten auch nur alleine, ohne Kommunikationsmöglichkeiten. Um Nachrichten von einem Quellknoten an den Zielknoten zu übermitteln, wurde das Store-Carry-Forward-Paradigma vorgeschlagen, wobei die Quell- oder Weiterleitungsknoten die Nachricht speichern und transportieren können, bis ein besserer Weiterleitungsknoten angetroffen wird. Ziel dieses Ansatzes ist es, eine Nachricht mit mehreren Trageperioden, Knoten für Knoten an ihren Zielknoten weiterzuleiten. Oft umfasst der Multihop-Pfad zwischen dem Quellknoten und dem Zielknoten eine lange Verzögerung oder kommt letztlich doch nicht zustande. Viele Flooding-basierte Routing-Protokolle wurden für Opportunistische Netzwerke vorgeschlagen, um die Wahrscheinlichkeit der Nachrichtenzustellung zu verbessern. Diese Protokolle leiden jedoch unter einem übermäßigen Ressourcenverbrauch bei dem Nachrichtenpuffer, der Bandbreite und der Energie. Diese übermäßige Ressourcennutzung führt zu einer signifikanten Verschlechterung der Routingperformance, da Nachrichten aufgrund voller Puffer in den mobilen Knoten übermäßig verworfen werden. Dies kommt insbesondere bei einem hohen Nachrichtenaufkommen kombiniert mit einem übermäßigen Flutungsprotokoll vor. Weiterleitungsstrategien müssen identifiziert werden, die entscheiden, welche Nachrichten für die Weiterleitung ausgewählt werden sollen, wenn die Bandbreite und Übertragungszeit knapp ist und eine Übertragung möglich ist. Es müssen auch Verwerfrichtlinien identifiziert werden, die entscheiden, welche Nachrichten aus einem vollen Puffer gelöscht werden sollen. Neben den Herausforderungen des effizienten Routings sind auch die Schritte der Nachbarknotenentdeckung und der Prozess des Linkaufbaus hervorzuheben, da sie auch Ressourcen konsumieren. Der Mechanismus der Nachbarknotenerkennung ist besonders im Fokus, wenn Links durch den IEEE 802.11 Wi-Fi Infrastrukturmodus aufgebaut werden. Diese Verbindungsoption ist derzeit die am meisten verfügbare Link-Option für Smartphones, die wiederum die am weitesten verbreiteten mobilen Kommunikationsknoten sind. Darüber hinaus bietet Wi-Fi die größte Bandbreite im Vergleich zu anderen drahtlosen Kommunikationsoptionen wie Bluetooth oder NFC. Daher ist es notwendig, bei diesem Schritt der Nachbarknotenerkennung und des Linkaufbaus, den Signalisierungsoverhead und die Verzögerung beim Aufbau zu untersuchen. Es ist wünschenswert, den Signalisierungsverkehr zum Aufbau einer stabilen und zuverlässigen Verbindung zu reduzieren und somit die verfügbare Bandbreite im Link weiter zu erhöhen und den Energieverbrauch zu senken. Beschleunigt man den Linkaufbau, so verkürzt sich auch die Übertragungsverzögerung und die Nachrichtenzustellung im Routing verbessert sich. Um die Herausforderungen der Verbesserung von Kommunikations- und Routing-Protokolle in opportunistischen Netzwerken zu bewältigen und den Nachrichtenaufwand und -verzögerung zu senken, konzentriert sich diese Arbeit auf die folgenden Hauptentwurfsziele. Zuerst entwerfen und bewerten wir ein neues Beacon-Intervall im Prozess der Nachbarknotenentdeckung und Linkeinrichtung für infrastrukturbasierte Wi-Fi-Kommunikation. Dafür untersuchen und analysieren wir das traditionelle Beacon-Intervall und beurteilen die Leistung der Nachbarknotenentdeckungsmechanismen. Wir schlagen vor, das traditionelle Beacon-Intervall für eine bessere Kanalauslastung und eine höhere Energieeffizienz zu duplizieren. Verschiedene Szenarien werden verwendet, um die Leistung des vorgeschlagenen Double Hundred Kilo Beacon Intervalls in Bezug auf Kontaktwahrscheinlichkeit, Verzögerung und die Kanalauslastung im Vergleich zum herkömmlichen Beacon-Intervall zu bewerten. Das vorgeschlagene Beacon-Intervall erreicht die gleiche Leistung wie die vorangegangene Lösung, halbiert dabei aber die Signalisierungskosten und spart somit wertvolle Energie. Zweitens evaluieren wir systematisch und ganzheitlich alle möglichen Weiterleitungs- und Verwerfrichtlinien, die auf einem einzigen Nachrichtenparameter basieren, nämlich Ankunftszeit, Replikationszahl, Anzahl der weitergeleiteten Knoten, Time-to-Live und Nachrichtengröße. Wir analysieren systematisch die Frage, wie die Performance des Routingprotokolls hinsichtlich Zustellwahrscheinlichkeit, Verzögerung und Nachrichtenoverhead beeinflusst wird, wenn Nach\-richten zum Weiterleiten oder Verwerfen auf Basis des höchsten / niedrigsten Werts eines der Nachrichtenparameter ausgewählt werden. Wir haben die Auswirkungen von 121 Weiterleitungs- und Verwerfrichtlinien-Kombinationen anhand von drei Szenarien mit unterschiedlichen Knoten\-geschwindigkeiten und Bandbreiten sowie unterschiedlichen Nachrichtengrößen und Generierungsintervallen ausgewertet. Unsere ausführliche Studie zeigt, dass die Auswirkungen der einzelnen Nachrichtenparameter auf die Routingqualität in hohem Maße von den Netzwerkbedingungen abhängen. Der jeweilige Nachrichtenparameter, der zu der höchsten Zustell\-wahr\-scheinlichkeit oder der niedrigsten Verzögerung und dem niedrigsten Nachrichtenoverhead führt, in jedem der Szenarien unterschiedlich ist. Die Studie ist sehr nützlich, um die Abhängigkeiten der spezifischen Netzwerkbedingungen und der Nachrichtenparameter zu identifizieren, die in den Weiterleitungs- und Nachrichtenverwerfrichtlinien relevant sind. Drittens nutzen wir diese Erkenntnisse, um optimierte Weiterleitungs- und Nachrichtenverwerfrichtlinien für floodingbasierte und utilitybasierte Routingprotokolle für opportunistische Netzwerke zu entwerfen und zu evaluieren. Die Evaluation mit mehreren Simulations-Setups zeigt, dass unsere optimierten Weiterleitungs- und Nachrichtenverwerfrichtlinien für das epidemische Routing-Protokoll und das utility-basiertes Routing-Protokoll PRoPHET entweder gleichauf oder besser sind als vergleichbare Routing-Protokolle, während die Verzögerung und der Nachrichtenoverhead deutlich reduziert werden. Darüber hinaus entwerfen und evaluieren wir ein replikationsgesteuertes Multi-Copy-Routing-Schema, das vor allem darauf abzielt, die Notwendigkeit einer Nachrichtenreplikation abzuwägen, um die Nachrichtzustellung zu verbessern und das Netzwerk nicht zu verstopfen. Unser Ansatz untersucht die Möglichkeit, lokale Knoten- und Nachrichteninformationen in der Nachrichtenreplikation zu berücksichtigen um so die Zustellwahrscheinlichkeit zu erhöhen und den Overhead und die Verzögerung der Nachrichten zu minimieren. Wir betrachten dazu nicht nur die Mobilitätsmodelle, sondern berücksichtigen auch Nachrichtenverkehrs- und Netzwerkbedingungen. Unsere Arbeit zeigt, dass Knoten- und Nachrichteninformation als sinnvolle lokale Information dienen können, um eine geeignete Nachrichtenreplikationsentscheidung in jedem Knoten treffen zu können. Um diese Beiträge zu unterstützen, haben wir zunächst einen Überblick über verfügbare Evaluationsumgebungen für opportunistische Netzwerke erstellt und die Werkzeuge, die weiter zur Bewertung der Auswirkungen unserer Beiträge genutzt wurden, identifiziert. Im Rahmen dieser Arbeit bieten wir mehrere Beiträge zur Steigerung der Effizienz von opportunistischen Netzwerken. Dafür erhöhen wir entweder die Leistung oder senken die Kosten für die Nachbarknotenentdeckung, den Linkaufbau sowie für verzögerungstolerantes Routing. Durch unsere Arbeit hoffen wir, die Verbreitung opportunistischer Netzwerke weiter zu unterstützen. Opportunistic networking has recently gained decent attention from the research community. Opportunistic networks in general are characterized by nodes with typically wireless communication capabilities that typically move around and have either no, a single or a few communication partners present. The network is considered as often being so sparsely populated that most paths between arbitrary node pairs do not exist at a given time. Often nodes also just walk alone without communication opportunities. In order to deliver messages from a source node to the destination of a message, the store-carry-forward routing paradigm has been proposed, whereby the source or relay nodes may store the message and carry it until a better forwarding node is encountered. Here the perspective is to forward a message with several carry periods hop-by-hop to its destination node. Nevertheless, the path between the source node and the destination node have a long delay and may never exist. Many flooding-based routing protocols have been proposed for opportunistic networking environments in order to improve the probability of the message delivery ratio. However, these protocols suffer from excessive resource consumption regarding storage, bandwidth, and energy. This excessive resource usage leads to a significant degradation of the routing performance, especially if we consider the fact that each node in the opportunistic network could be a mobile and battery-powered device with physically limited buffer size. With such buffer limitations of the mobile node, message drop events could occur due to buffer overflow especially with a high traffic pattern combined with an excessive flooding protocol. Forwarding strategies have to be identified to decide which messages should be selected for forwarding if the bandwidth is scarce and the transmission time limited. Also drop policies have to be identified that decide which messages to delete from the buffer once the buffer is full. Besides the routing challenges, the neighbor discovery and link establishment process are noteworthy, as they also consume resources. The mechanism of neighbor discovery is needed especially when links are established using the infrastructure mode of the IEEE 802.11 Wi-Fi capabilities of the mobile nodes. This connection option is currently the most available link option for smartphones and in addition this option provides the highest possible bandwidth compared to other wireless communication options such as Bluetooth or NFC. Therefore, it is needed to investigate this step of neighbor discovery and link establishment with special consideration with regard to the signaling overhead and link establishment delay. It is desirable to reduce the control traffic required to build a stable and reliable link connectivity and thus to improve channel utilization and energy conservation. A further effect of improving the neighbor discovery is an impact on the performance of applied routing protocol in form of decreasing the transmission delay and increasing the message delivery ratio. To address the challenges of improving the performance of communications and routing protocols in opportunistic networks and to lower the message overhead and delay costs, this thesis focuses on the following main design objectives. First, we design and evaluate a new beacon interval in the process of neighbor discovery and link establishment for infrastructure-based Wi-Fi communications. For that we investigate and analyze the traditional beacon interval and assess the performance of the neighbor discovery mechanisms. We propose to duplicate the traditional beacon interval for a better channel utilization and a higher energy efficiency. Various scenarios are used to evaluate the performance of the proposed Double Hundred Kilo Beacon Interval in terms of contact probability, delay and the channel utilization in comparison to the traditional beacon interval. The proposed beacon interval results in an equal performance of the neighbor discovery mechanism while the signaling costs are halved and thus valuable energy conserved. Second, we systematically and holistically evaluate all possible scheduling and dropping policies based on a single parameter of the message characteristics, namely arrival time, replication count, number of relayed nodes, time to live and message size. We systematically analyze the question of how the performance of the routing protocol in terms of delivery ratio, delay and message overhead is influenced if messages are selected for scheduling or dropping based on the message with the highest / lowest value with regard to a single of these parameters. We evaluated the impact of 121 scheduling and drop policy combinations using three scenarios with varying node speeds and bandwidths, as well as varying message sizes and generation intervals. Our exhaustive study shows that the impact of each specific message information in the scheduling and drop policies is highly depending on the network conditions. The specific message parameter which leads to the highest delivery ratio or lowest delay and overhead is different in each of the scenarios. The study is very useful to identify the interdependencies of the specific network conditions and the information relevant in the scheduling and drop policies. Third, we use this insights to design and evaluate optimized scheduling and drop policies for flooding-based and utility-based routing protocols for opportunistic networks that lead to less message loss due to less buffer overflow and further increase the routing performance in terms of delivery ratio in comparison to prominent strategies in literature. Evaluation with several simulation setups shows that our proposed optimized scheduling and drop policies for the epidemic routing protocol and PRoPHET, an utility-based routing protocol, are either on par or better that comparable routing protocols while the traffic overhead and message delivery delays as significantly reduced. In addition, we design and evaluate a replication-controlled multi-copy routing scheme, which especially aims to balance the need for message replication to improve the chances of the message to be delivered and the risk of congesting the network. This leads to a reduction of the message delivery probability. The proposed Replication Probability-based Routing Scheme explores the possibility of taking local node and message information into account to control the message replication and so increasing the delivery ratio and minimizing the overhead and delay of the messages. In our approach, the best carrier for a message is characterized by the message’s delivery probability considering the replication count and hop count in a Markov chain model as well as the network status, information on the mobility of the node and its buffer information. We not only consider the mobility model statistics but also consider the user traffic and network conditions, such as congestion and buffer occupancy, especially when there is a contact with another node. The thesis shows that the node and the message information can serve as meaningful local information to achieve an appropriate message replication decision at each node. Therefore, the implemented routing scheme achieves high efficiency via an adaptive and precise routing design considering different network conditions. In order to support these contributions, initially we created an overview on available evaluation environments for opportunistic networks and identified the tools that were used further on to evaluate the impact of our contributions. Within this thesis, we provide several contributions to increase the efficiency of opportunistic networks. For that we either increase the performance or decrease the costs for neighbor discovery, link establishment as well as delay-tolerant routing. Through this work, we hope to further support the spread of opportunistic networks.
Lizenz:	Urheberrechtsschutz
Fachbereich / Einrichtung:	Mathematisch- Naturwissenschaftliche Fakultät » WE Informatik » Rechnernetze
Dokument erstellt am:	25.07.2017
Dateien geändert am:	25.07.2017
Promotionsantrag am:	03.05.2017
Datum der Promotion:	17.07.2017