The astronomical increase in the number of wireless devices such as smart phones in 21th century has revolutionized the way people communicate with one another and share information. The new wireless technologies have also enabled researchers to collect real data about how people move and meet one another in different social settings. Understanding human mobility has many applications in different areas such as traffic planning in cities and public health studies of epidemic diseases. In this thesis, we study the fundamental properties of human contact graphs in order to characterize how people meet one another in different social environments. Understanding human contact patterns in return allows us to propose a cost-effective routing algorithm for spreading information in Delay Tolerant Networks. Furthermore, we propose several contact predictors to predict the unobserved parts of contact graphs when only partial observations are available. Our results show that we are able to infer hidden contacts of real contact traces by exploiting the underlying properties of contact graphs. In the last few years, we have also witnessed an explosion in the number of people who use social media to share information with their friends. In the last part of this thesis, we study the running times of several information spreading algorithms in social networks in order to find the fastest strategy. Fast information spreading has an obvious application in advertising a product to a large number of people in a short amount of time. We prove that a fast information spreading algorithm should efficiently identify communication bottlenecks in order to speed up the running time. Finally, we show that sparsifying large social graphs by exploiting the edge-betweenness centrality measure can also speed up the information spreading rate. / Graduate

Mit der zunehmenden Verbreitung mobiler Endgeräte und Dienste ergeben sich auch neue Herausforderungen für ihre Sicherheit. Diese lassen sich nur teilweise mit herkömmlichen Sicherheitsparadigmen und -mechanismen meistern. Die Gründe hierfür sind in den veränderten Voraussetzungen durch die inhärenten Eigenschaften mobiler Systeme zu suchen. Die vorliegende Arbeit thematisiert am Beispiel von Wireless LANs die Entwicklung von Sicherheitsmechanismen für drahtlose Ad-hoc- und Infrastrukturnetze. Sie stellt dabei den umfassenden Schutz der einzelnen Endgeräte in den Vordergrund, die zur Kompensation fehlender infrastruktureller Sicherheitsmaßnahmen miteinander kooperieren. Den Ausgangspunkt der Arbeit bildet eine Analyse der Charakteristika mobiler Umgebungen, um grundlegende Anforderungen an eine Sicherheitslösung zu identifizieren. Anhand dieser werden existierende Lösungen bewertet und miteinander verglichen. Der so gewonnene Einblick in die Vor- und Nachteile präventiver, reaktiver und angriffstoleranter Mechanismen führt zu der Konzeption einer hybriden universellen Rahmenarchitektur zur Integration beliebiger Sicherheitsmechanismen in einem kooperativen Verbund. Die Validierung des Systementwurfs erfolgt anhand einer zweigeteilten prototypischen Implementierung. Den ersten Teil bildet die Realisierung eines verteilten Network Intrusion Detection Systems als Beispiel für einen Sicherheitsmechanismus. Hierzu wird eine Methodik beschrieben, um anomalie- und missbrauchserkennende Strategien auf beliebige Netzprotokolle anzuwenden. Die Machbarkeit des geschilderten Ansatzes wird am Beispiel von infrastrukturellem WLAN nach IEEE 802.11 demonstriert. Den zweiten Teil der Validierung bildet der Prototyp einer Kooperations-Middleware auf Basis von Peer-to-Peer-Technologien für die gemeinsame Angriffserkennung lose gekoppelter Endgeräte. Dieser kompensiert bisher fehlende Mechanismen zur optimierten Abbildung des Overlay-Netzes auf die physische Struktur drahtloser Netze, indem er nachträglich die räumliche Position mobiler Knoten in die Auswahl eines Kooperationspartners einbezieht. Die zusätzlich definierte Schnittstelle zu einem Vertrauensmanagementsystem ermöglicht die Etablierung von Vertrauensbeziehungen auf Kooperationsebene als wichtige Voraussetzung für den Einsatz in realen Umgebungen. Als Beispiel für ein Vertrauensmanagementsystem wird der Einsatz von Reputationssystemen zur Bewertung der Verlässlichkeit eines mobilen Knotens diskutiert. Neben einem kurzen Abriss zum Stand der Forschung in diesem Gebiet werden dazu zwei Vorschläge für die Gestaltung eines solchen Systems für mobile Ad-hoc-Netze gemacht. / The increasing deployment of mobile devices and accompanying services leads to new security challenges. Due to the changed premises caused by particular features of mobile systems, these obstacles cannot be solved solely by traditional security paradigms and mechanisms. Drawing on the example of wireless LANs, this thesis examines the development of security mechanisms for wireless ad hoc and infrastructural networks. It places special emphasis on the comprehensive protection of each single device as well as compensating missing infrastructural security means by cooperation. As a starting point this thesis analyses the characteristics of mobile environments to identify basic requirements for a security solution. Based on these requirements existing preventive, reactive and intrusion tolerant approaches are evaluated. This leads to the conception of a hybrid and universal framework to integrate arbitrary security mechanisms within cooperative formations. The resulting system design is then validated by a twofold prototype implementation. The first part consists of a distributed network intrusion detection system as an example for a security mechanism. After describing a methodology for applying anomaly- as well as misuse-based detection strategies to arbitrary network protocols, the feasibility of this approach is demonstrated for IEEE 802.11 infrastructural wireless LAN. The second part of the validation is represented by the prototype of a P2P-based cooperation middleware for collaborative intrusion detection by loosely coupled devices. Missing mechanisms for the improved mapping of overlay and physical network structures are compensated by subsequently considering the spatial position of a mobile node when choosing a cooperation partner. Furthermore, an additional interface to an external trust management system enables the establishment of trust relationships as a prerequisite for a deployment in real world scenarios. Reputation systems serve as an example of such a trust management system that can be used to estimate the reliability of a mobile node. After outlining the state of the art, two design patterns of a reputation system for mobile ad hoc networks are presented.

This thesis investigates both theoretical and practical aspects of the design and analysis of modern error-control coding schemes, namely low-density parity-check (LDPC) codes and rateless codes for unequal error protection (UEP). It also studies the application of modern error-control codes in efficient data dissemination in wireless ad-hoc and sensor networks. Two methodologies for the design and analysis of UEP-LDPC codes are proposed. For these proposed ensembles, density evolution formulas over the binary erasure channel are derived and used to optimize the degree distribution of the codes. Furthermore, for the first time, rateless codes that can provide UEP are developed. In addition to providing UEP, the proposed codes can be used in applications for which unequal recovery time is desirable, i.e., when more important parts of data are required to be recovered faster than less important parts. Asymptotic behavior of the UEP-rateless codes under the iterative decoding is investigated. In addition, the performance of the proposed codes is examined under the maximum-likelihood decoding, when the codes have short to moderate lengths. Results show that UEP-rateless codes are able to provide very low error rates for more important bits with only a subtle loss in the performance of less important bits. Moreover, it is shown that given a target bit error rate, different parts of the information symbols can be decoded after receiving different numbers of encoded symbols. This implies that information can be recovered in a progressive manner, which is of interest in many practical applications such as media-on-demand systems. This work also explores fundamental research problems related to applying error-control coding such as rateless coding to the problem of reliable and energy-efficient broadcasting in multihop wireless ad-hoc sensor networks. The proposed research touches on the four very large fields of wireless networking, coding theory, graph theory, and percolation theory. Based on the level of information that each node has about the network topology, several reliable and energy-efficient schemes are proposed, all of which are distributed and have low complexity of implementation. The first protocol does not require any information about the network topology. Another protocol, which is more energy efficient, assumes each node has local information about the network topology. In addition, this work proposes a distributed scheme for finding low-cost broadcast trees in wireless networks. This scheme takes into account various parameters such as distances between nodes and link losses. This protocol is then extended to find low-cost multicast trees. Several schemes are extensively simulated and are compared.

Mit der zunehmenden Verbreitung mobiler Endgeräte und Dienste ergeben sich auch neue Herausforderungen für ihre Sicherheit. Diese lassen sich nur teilweise mit herkömmlichen Sicherheitsparadigmen und -mechanismen meistern. Die Gründe hierfür sind in den veränderten Voraussetzungen durch die inhärenten Eigenschaften mobiler Systeme zu suchen. Die vorliegende Arbeit thematisiert am Beispiel von Wireless LANs die Entwicklung von Sicherheitsmechanismen für drahtlose Ad-hoc- und Infrastrukturnetze. Sie stellt dabei den umfassenden Schutz der einzelnen Endgeräte in den Vordergrund, die zur Kompensation fehlender infrastruktureller Sicherheitsmaßnahmen miteinander kooperieren. Den Ausgangspunkt der Arbeit bildet eine Analyse der Charakteristika mobiler Umgebungen, um grundlegende Anforderungen an eine Sicherheitslösung zu identifizieren. Anhand dieser werden existierende Lösungen bewertet und miteinander verglichen. Der so gewonnene Einblick in die Vor- und Nachteile präventiver, reaktiver und angriffstoleranter Mechanismen führt zu der Konzeption einer hybriden universellen Rahmenarchitektur zur Integration beliebiger Sicherheitsmechanismen in einem kooperativen Verbund. Die Validierung des Systementwurfs erfolgt anhand einer zweigeteilten prototypischen Implementierung. Den ersten Teil bildet die Realisierung eines verteilten Network Intrusion Detection Systems als Beispiel für einen Sicherheitsmechanismus. Hierzu wird eine Methodik beschrieben, um anomalie- und missbrauchserkennende Strategien auf beliebige Netzprotokolle anzuwenden. Die Machbarkeit des geschilderten Ansatzes wird am Beispiel von infrastrukturellem WLAN nach IEEE 802.11 demonstriert. Den zweiten Teil der Validierung bildet der Prototyp einer Kooperations-Middleware auf Basis von Peer-to-Peer-Technologien für die gemeinsame Angriffserkennung lose gekoppelter Endgeräte. Dieser kompensiert bisher fehlende Mechanismen zur optimierten Abbildung des Overlay-Netzes auf die physische Struktur drahtloser Netze, indem er nachträglich die räumliche Position mobiler Knoten in die Auswahl eines Kooperationspartners einbezieht. Die zusätzlich definierte Schnittstelle zu einem Vertrauensmanagementsystem ermöglicht die Etablierung von Vertrauensbeziehungen auf Kooperationsebene als wichtige Voraussetzung für den Einsatz in realen Umgebungen. Als Beispiel für ein Vertrauensmanagementsystem wird der Einsatz von Reputationssystemen zur Bewertung der Verlässlichkeit eines mobilen Knotens diskutiert. Neben einem kurzen Abriss zum Stand der Forschung in diesem Gebiet werden dazu zwei Vorschläge für die Gestaltung eines solchen Systems für mobile Ad-hoc-Netze gemacht. / The increasing deployment of mobile devices and accompanying services leads to new security challenges. Due to the changed premises caused by particular features of mobile systems, these obstacles cannot be solved solely by traditional security paradigms and mechanisms. Drawing on the example of wireless LANs, this thesis examines the development of security mechanisms for wireless ad hoc and infrastructural networks. It places special emphasis on the comprehensive protection of each single device as well as compensating missing infrastructural security means by cooperation. As a starting point this thesis analyses the characteristics of mobile environments to identify basic requirements for a security solution. Based on these requirements existing preventive, reactive and intrusion tolerant approaches are evaluated. This leads to the conception of a hybrid and universal framework to integrate arbitrary security mechanisms within cooperative formations. The resulting system design is then validated by a twofold prototype implementation. The first part consists of a distributed network intrusion detection system as an example for a security mechanism. After describing a methodology for applying anomaly- as well as misuse-based detection strategies to arbitrary network protocols, the feasibility of this approach is demonstrated for IEEE 802.11 infrastructural wireless LAN. The second part of the validation is represented by the prototype of a P2P-based cooperation middleware for collaborative intrusion detection by loosely coupled devices. Missing mechanisms for the improved mapping of overlay and physical network structures are compensated by subsequently considering the spatial position of a mobile node when choosing a cooperation partner. Furthermore, an additional interface to an external trust management system enables the establishment of trust relationships as a prerequisite for a deployment in real world scenarios. Reputation systems serve as an example of such a trust management system that can be used to estimate the reliability of a mobile node. After outlining the state of the art, two design patterns of a reputation system for mobile ad hoc networks are presented.